提出新型加速方法，突破非欧优化迭代瓶颈
Faster Acceleration for Steepest Descent
- 采用不同范数的对偶迭代序列，隐式插值耦合
- 在d维ℓ_p光滑问题中迭代复杂度降低O(d^{1-2/p})
- 适合处理非欧几何下的凸优化任务
近期研究（Sherman, 2017；Sidford and Tian, 2018；Cohen et al., 2021）克服了使用一阶方法求解ℓ_∞回归时维度依赖的固有障碍。然而，此类加速在一般ℓ_p光滑函数上能实现多大程度仍不明确。本文提出一种新的加速一阶方法，适用于非欧光滑假设下的凸优化。与标准加速技术不同，本方法采用以不同范数定义的原始-对偶迭代序列，并通过隐式确定的插值参数进行耦合。对于d维ℓ_p范数光滑问题，该方法将一阶预言机调用次数的迭代复杂度最多提升O(d^{1-2/p})，从而绕过了加速非欧陡下降法长期存在的障碍。
原文摘要 · Abstract (English)
Recent advances (Sherman, 2017; Sidford and Tian, 2018; Cohen et al., 2021) have overcome the fundamental barrier of dimension dependence in the iteration complexity of solving $\ell_\infty$ regression with first-order methods. Yet it remains unclear to what extent such acceleration can be achieved for general $\ell_p$ smooth functions. In this paper, we propose a new accelerated first-order method for convex optimization under non-Euclidean smoothness assumptions. In contrast to standard acceleration techniques, our approach uses primal-dual iterate sequences taken with respect to $\textit{differing}$ norms, which are then coupled using an $\textit{implicitly}$ determined interpolation parameter. For $\ell_p$ norm smooth problems in $d$ dimensions, our method provides an iteration complexity improvement of up to $O(d^{1-\frac{2}{p}})$ in terms of calls to a first-order oracle, thereby allowing us to circumvent long-standing barriers in accelerated non-Euclidean steepest descent.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。