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

arXiv:2502.21099v3 Announce Type: replace-cross Abstract: 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 extit{composite} minimization problems. Specifically, {sf AEPG} achieves the optimal iteration complexity of O(N epsilon^{-2}), while {sf AEPG-SPIDER} achieves O(N + sqrt{N} epsilon^{-2}) for finding epsilon-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.

Related

• Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size
• Combined Dictionary Unfolding Network with Gradient-Adaptive Fidelity for Transferable Multi-Source Fusion
• Learning rate adaptive stochastic gradient descent optimization methods: numerical simulations for deep learning methods for partial differential equations and convergence analyses

Source: arXiv cs.CV | 2026-08-26