自适应双层优化

《ACM / IMS Journal of Data Science》：Adaptive Bilevel Optimization

自适应镜像下降算法在非凸光滑 bilevel 优化问题中的应用，提出无需李普希兹常数的新方法，在凸外目标下外函数收敛率为 O(1/T)，非凸下梯度平方范数 O(1/T)，并验证强化学习场景。

　　在机器学习领域，随着复杂模型和任务的不断扩展，优化问题的形式也变得更加多样化和复杂化。其中，** bilevel optimization（双层优化）**作为一种特殊的优化结构，因其在多个应用中展现出的强大建模能力而受到广泛关注。双层优化问题通常包含两个嵌套的优化任务，其中外层目标函数的最小化依赖于内层问题的最优解。这种结构在超参数优化、元学习、强化学习等领域具有广泛的应用价值。然而，传统的双层优化算法往往需要预先知道内层和外层目标函数的梯度Lipschitz常数，这些常数通常难以准确估计，导致算法在实际应用中面临较大的调参压力。因此，如何设计一种**无需预先知道Lipschitz常数的自适应优化方法**，成为当前研究的一个重要方向。

本文提出了一种基于镜像下降（Mirror Descent）的**自适应双层优化算法**，该算法通过“on the fly”（实时）的梯度范数累积策略，避免了对Lipschitz常数的依赖。这是目前首个针对双层优化问题的自适应方法。我们还对算法的收敛性进行了理论分析，并通过实验验证了其有效性。本文的贡献主要体现在三个方面：一是提出了一种适用于光滑双层优化问题的自适应方法，该方法在不知道任何Lipschitz常数的情况下自动调整步长；二是为凸外层目标函数和非凸外层目标函数分别建立了收敛率的理论保证；三是通过在强化学习中的实验，展示了该算法的实际应用效果。

### 双层优化问题的结构与挑战

双层优化问题通常表示为以下形式：

$$
\min_{x\in \mathcal{X}} f(x; y^{\ast}(x)),
$$

其中，$y^{\ast}(x)$是内层优化问题的最优解，即：

$$
y^{\ast}(x) = \arg \min_{y\in \mathbb{R}^d} g(x; y).
$$

这种结构意味着，外层优化问题的解依赖于内层问题的最优解。因此，内层问题的求解结果必须被准确地反馈给外层优化过程。在许多实际应用场景中，例如强化学习中的策略优化，这种结构被用来刻画决策过程中的策略和价值函数之间的相互依赖关系。

然而，传统的方法通常需要知道内层和外层目标函数的梯度Lipschitz常数。这些常数在实际问题中往往无法直接获取，因为它们依赖于问题的复杂结构和数据分布。此外，这些常数还可能涉及“超Lipschitz”常数，即与两个优化层相关的一系列参数，使得它们的估计更加困难。因此，如何设计一种**不需要依赖这些常数的自适应优化方法**，成为当前研究的一个重要挑战。

### 传统双层优化方法的局限性

在现有的双层优化方法中，如近似双层方法（Approximation Bilevel Method），其收敛性分析依赖于对这些常数的准确估计。例如，外层目标函数的梯度Lipschitz常数和内层目标函数的“超Lipschitz”常数都需要被预先设定。然而，这些常数的估计不仅需要大量的计算资源，而且在实际应用中往往存在误差，这可能导致算法的性能下降，甚至无法收敛。

例如，在一些情况下，即使使用了理论上的最优步长，如果由于某些计算误差导致步长选择不当，算法可能会在迭代过程中出现剧烈震荡，最终导致发散。这种现象在机器学习中尤为常见，尤其是在涉及复杂优化结构的场景下，如双层优化问题。因此，设计一种**能够自动调整步长的自适应方法**，对于提高算法的鲁棒性和实用性具有重要意义。

### 自适应双层镜像下降算法的设计

为了解决上述问题，本文提出了一种基于镜像下降的自适应算法。该算法的核心思想是利用**梯度范数的累积**策略，动态调整内层和外层优化过程中的步长，从而避免对Lipschitz常数的依赖。

在内层优化过程中，我们采用一种**自适应步长策略**，即在每次迭代中计算梯度的平方范数，并将其用于调整步长。具体来说，假设在第k次外层迭代中，我们进行了$t_k$次内层梯度下降步骤，那么在第t次内层迭代中，我们定义步长$\eta_t$为：

$$
\eta_t = \frac{1}{H_g G_t},
$$

其中，$H_g$是内层目标函数的强凸性参数，$G_t$是前t次迭代中梯度的平方范数的累积。这种策略能够有效地应对梯度变化较大的情况，同时避免对Lipschitz常数的依赖。

在外层优化过程中，我们引入了一种**自适应步长策略**，通过计算外层目标函数的梯度映射（Gradient Mapping）来调整步长。具体来说，我们定义外层步长$\gamma_k$为：

$$
\gamma_k = \frac{1}{\sqrt{\sum_{s=1}^{k} \Vert \nabla f(x_s; y^{\ast}(x_s)) \Vert^2}},
$$

其中，$\nabla f(x_s; y^{\ast}(x_s))$是外层目标函数的梯度。通过这种方式，我们能够在不知道任何Lipschitz常数的情况下，动态地调整步长，从而提高算法的鲁棒性和收敛性。

### 收敛性分析与理论保证

在理论分析方面，本文对所提出的自适应算法进行了收敛性研究。我们证明了在**凸外层目标函数**的情况下，该算法能够实现$\mathcal{O}(1/T)$的收敛速率，其中T是迭代次数。而在**非凸外层目标函数**的情况下，该算法能够保证**最佳迭代**的收敛性，即最小化梯度的平方范数的收敛速率也为$\mathcal{O}(1/T)$。

此外，我们还证明了该算法在**受限可行域**的情况下，其迭代序列能够**收敛到某个最优解**。这些理论结果表明，所提出的自适应方法在双层优化问题中具有良好的收敛性，同时能够避免对Lipschitz常数的依赖。

### 实验验证与应用案例

为了验证所提出算法的有效性，我们在**强化学习**的场景中进行了实验。强化学习中的策略优化问题可以被建模为双层优化问题，其中外层目标是优化策略，而内层目标是优化价值函数。在实验中，我们比较了本文提出的自适应算法与一些传统的双层优化方法，包括近似双层方法、SABA、AMIGO、BSA等。

实验结果表明，本文提出的自适应算法在多个基准测试中表现优异。特别是在**Gridworld**任务中，该算法在不依赖任何Lipschitz常数的情况下，仍然能够稳定地收敛到最优解。而在**Mnist**数据集上的实验中，该算法在**Hyper Data Cleaning**任务中表现优于其他非自适应方法，且在某些情况下能够更快地收敛。

此外，我们在**Covtype**数据集上的实验也显示，该算法能够稳定地运行，并且在大多数情况下表现优于现有的非自适应方法。值得注意的是，AMIGO在Covtype任务上表现略优于我们的算法，但在Hyper Data Cleaning任务中则无法收敛，这进一步验证了本文方法在复杂场景下的鲁棒性。

### 算法的潜力与未来研究方向

本文提出的自适应双层镜像下降算法不仅在理论上具有良好的收敛性，而且在实际应用中也展现出较高的稳定性。这种算法可以被广泛应用于机器学习中的各种双层优化问题，包括超参数优化、元学习和强化学习等。

然而，本文仍然存在一些局限性。例如，目前的算法仅适用于**光滑双层优化问题**，而对**非光滑问题**的处理仍需进一步研究。此外，本文的方法在处理**强凸性参数**的自适应调整方面也有待完善。因此，未来的研究可以探索如何将本文的方法扩展到更广泛的优化场景中，例如非光滑目标函数、高维优化问题以及多目标优化问题。

总之，本文提出了一种新的自适应双层优化方法，该方法在不需要预先知道任何Lipschitz常数的情况下，能够稳定地运行并实现良好的收敛性。通过在强化学习中的实验验证，我们展示了该算法在实际应用中的有效性。这一成果为双层优化问题的求解提供了新的思路，并有望在未来的机器学习研究中发挥重要作用。