arXiv:2502.21099math.OCcs.CV2025-02被引 1

提出新算法,高效求解非凸复合优化问题。

Adaptive Extrapolated Proximal Gradient Methods with Variance Reduction for Composite Nonconvex Finite-Sum Minimization

  • 用迭代差值自适应调整步长,结合加速技巧提升收敛速度。
  • 在非凸有限和问题中达到最优复杂度,理论性能领先。
  • 适合需要高效求解大规模非凸优化的科研与工程场景。

本文提出 { f AEPG-SPIDER},一种用于最小化复合非凸有限和函数的自适应外推邻近梯度方法,融合自适应步长、Nesterov加速和递归随机路径积分估计器 SPIDER 三种加速技术。不同于依赖历史梯度调整步长的现有方法,{ f AEPG-SPIDER} 基于过去迭代点的差异进行更新。在全批量、非随机设置下,该方法退化为 { f AEPG},也具独立意义。据我们所知,{ f AEPG-SPIDER} 与 { f AEPG} 是首个在该类复合优化问题上实现无 Lipschitz 假设下的最优迭代复杂度的方法。具体而言,{ f AEPG} 达到 $ O(N ε^{-2})$ 的复杂度,{ f AEPG-SPIDER} 达到 $ O(N + N^{1/2} ε^{-2})$,用于寻找 $ε$-近似驻点,其中 $N$ 为分项函数数量。在 Kurdyka-Lojasiewicz (KL) 假设下,建立了两者的非遍历收敛速率。在稀疏相位恢复与线性特征值问题上的初步实验表明,{ f AEPG-SPIDER} 和 { f AEPG} 性能优于现有方法。

原文摘要 · Abstract (English)

This paper proposes {\sf AEPG-SPIDER}, an Adaptive Extrapolated Proximal Gradient (AEPG) method with variance reduction for minimizing composite nonconvex finite-sum functions. It integrates three acceleration techniques: adaptive stepsizes, Nesterov's extrapolation, and the recursive stochastic path-integrated estimator SPIDER. Unlike existing methods that adjust the stepsize factor using historical gradients, {\sf AEPG-SPIDER} relies on past iterate differences for its update. While targeting stochastic finite-sum problems, {\sf AEPG-SPIDER} simplifies to {\sf AEPG} in the full-batch, non-stochastic setting, which is also of independent interest. To our knowledge, {\sf AEPG-SPIDER} and {\sf AEPG} are the first Lipschitz-free methods to achieve optimal iteration complexity for this class of \textit{composite} minimization problems. Specifically, {\sf AEPG} achieves the optimal iteration complexity of $\mathcal{O}(N ε^{-2})$, while {\sf AEPG-SPIDER} achieves $\mathcal{O}(N + \sqrt{N} ε^{-2})$ for finding $ε$-approximate stationary points, where $N$ is the number of component functions. Under the Kurdyka-Lojasiewicz (KL) assumption, we establish non-ergodic convergence rates for both methods. Preliminary experiments on sparse phase retrieval and linear eigenvalue problems demonstrate the superior performance of {\sf AEPG-SPIDER} and {\sf AEPG} compared to existing methods.

非凸优化随机梯度复合问题收敛分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。