Nearly Optimal First-Order Methods for Convex Optimization under Gradient Norm Measure: An Adaptive Regularization Approach
Nearly Optimal First-Order Methods for Convex Optimization under Gradient Norm Measure: An Adaptive Regularization Approach
复制标题
梯度范数测度下凸优化的近乎最优一阶方法：一种自适应正则化方法
DOI：
10.1007/s10957-020-01806-7
复制
发表时间：
2021
影响因子：
1.9
通讯作者：
Mituhiro Fukuda
中科院分区：
文献类型：
--
作者：
Masaru Ito;Mituhiro Fukuda
在光滑(相应地，复合)凸优化问题的一阶方法的发展中，具有Lipschitz连续梯度的光滑函数被最小化，梯度(相应地，梯度映射)范数成为基本的最优性度量。在此度量下，对于光滑情形，已知具有最优迭代复杂度的固定迭代算法，而确定该迭代次数以获得期望的精度需要知道从初始点到最优解集的距离。本文提出了一种自适应正则化方法，该方法在不知道到最优解集合的距离的情况下，获得了接近最优的迭代复杂度。为了自适应地获得更快的收敛速度，我们第二次应用这一方法构造了一个适应Hölderian误差界条件(或等价于Łojasiewicz梯度性质)的一阶方法，它覆盖了中等广泛的应用类别。该方法获得了关于梯度映射范数的近似最优迭代复杂度。
In the development of first-order methods for smooth (resp., composite) convex optimization problems, where smooth functions with Lipschitz continuous gradients are minimized, the gradient (resp., gradient mapping) norm becomes a fundamental optimality measure. Under this measure, a fixed iteration algorithm with the optimal iteration complexity for the smooth case is known, while determining this number of iteration to obtain a desired accuracy requires the prior knowledge of the distance from the initial point to the optimal solution set. In this paper, we report an adaptive regularization approach, which attains the nearly optimal iteration complexity without knowing the distance to the optimal solution set. To obtain further faster convergence adaptively, we secondly apply this approach to construct a first-order method that is adaptive to the Hölderian error bound condition (or equivalently, the Łojasiewicz gradient property), which covers moderately wide classes of applications. The proposed method attains nearly optimal iteration complexity with respect to the gradient mapping norm.