Bilevel optimization plays an essential role in many machine learning tasks,
ranging from hyperparameter optimization to meta-learning. Existing studies on
bilevel optimization, however, focus on either centralized or synchronous
distributed setting. The centralized bilevel optimization approaches require
collecting massive amount of data to a single server, which inevitably incur
significant communication expenses and may give rise to data privacy risks.
Synchronous distributed bilevel optimization algorithms, on the other hand,
often face the straggler problem and will immediately stop working if a few
workers fail to respond. As a remedy, we propose Asynchronous Distributed
Bilevel Optimization (ADBO) algorithm. The proposed ADBO can tackle bilevel
optimization problems with both nonconvex upper-level and lower-level objective
functions, and its convergence is theoretically guaranteed. Furthermore, it is
revealed through theoretic analysis that the iteration complexity of ADBO to
obtain the $\epsilon$-stationary point is upper bounded by
$\mathcal{O}(\frac{1}{\epsilon ^2})$. Thorough empirical studies on public
datasets have been conducted to elucidate the effectiveness and efficiency of
the proposed ADBO.

提出了一种异步分布式双层优化 (ADBO) 算法，旨在解决中心化和同步分布式双层优化遇到的难题，可处理具有非凸上下层目标函数的双层优化问题，理论上收敛，并且迭代复杂度上界是 O (1/ε²)；通过实验研究验证了 ADBO 的有效性和高效性。

异步分布式双层优化

Asynchronous Distributed Bilevel Optimization

Optimization algorithms and Monte Carlo sampling algorithms have provided the
computational foundations for the rapid growth in applications of statistical
machine learning in recent years. There is, however, limited theoretical
understanding of the relationships between these two kinds of methodology, and
limited understanding of relative strengths and weaknesses. Moreover, existing
results have been obtained primarily in the setting of convex functions (for
optimization) and log-concave functions (for sampling). In this setting, where
local properties determine global properties, optimization algorithms are
unsurprisingly more efficient computationally than sampling algorithms. We
instead examine a class of nonconvex objective functions that arise in mixture
modeling and multi-stable systems. In this nonconvex setting, we find that the
computational complexity of sampling algorithms scales linearly with the model
dimension while that of optimization algorithms scales exponentially.

此文讨论了优化算法与蒙特卡罗采样算法之间的关系以及在非凸优化函数中，采样算法的计算复杂度与模型维度呈线性关系而优化算法的计算复杂度呈指数关系。

采样比优化更快

Sampling Can Be Faster Than Optimization

We provide novel theoretical results regarding local optima of regularized
$M$-estimators, allowing for nonconvexity in both loss and penalty functions.
Under restricted strong convexity on the loss and suitable regularity
conditions on the penalty, we prove that \emph{any stationary point} of the
composite objective function will lie within statistical precision of the
underlying parameter vector. Our theory covers many nonconvex objective
functions of interest, including the corrected Lasso for errors-in-variables
linear models; regression for generalized linear models with nonconvex
penalties such as SCAD, MCP, and capped-$\ell_1$; and high-dimensional
graphical model estimation. We quantify statistical accuracy by providing
bounds on the $\ell_1$-, $\ell_2$-, and prediction error between stationary
points and the population-level optimum. We also propose a simple modification
of composite gradient descent that may be used to obtain a near-global optimum
within statistical precision $\epsilon$ in $\log(1/\epsilon)$ steps, which is
the fastest possible rate of any first-order method. We provide simulation
studies illustrating the sharpness of our theoretical results.

本文提供了关于正则化 M - 估计器局部最优解的新理论结果，覆盖了许多感兴趣的非凸目标函数，包括误差 - 变量线性模型的校正套索方法，具有非凸罚项的广义线性模型回归，以及高维图模型估计，我们提供了误差的上限，证明了我们的理论结果，同时提出了一种简单的修改方法，使得可以在 log (1/∊) 步内以任意精度获得近似全局最优解，这是任何一阶方法可能达到的最快速度。