Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization
Authors: Laurent Condat, Peter Richtárik
Organizations: King Abdullah University of Science and Technology (KAUST) Thuwal, Kingdom of Saudi Arabia
Abstract
The ProbAbilistic Gradient Estimator algorithm (PAGE), a stochastic algorithm introduced by Li et al. in 2021, was designed to find stationary points for the average of smooth nonconvex functions. In this work, we study PAGE within the broad framework of τ-weakly convex functions, providing a continuous interpolation between the general nonconvex L-smooth regime (τ=L) and the convex regime (τ=0). We establish new convergence rates for PAGE, showing that its complexity improves as τ decreases.
We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve O(ε−5/3log(1/ε)) oracle complexity bound when minimizing sufficiently smooth, non-convex functions; this is the best-known bound for first-order methods on smooth non-convex objectives. Unlike existing methods possessing this rate that require a priori knowledge of smoothness constants, we use an adaptive backtracking scheme and a gradient-based restart mechanism to estimate local curvature. This yields a practical algorithm that matches best-known theoretical rates. Empirically, PF-AGD outperforms the practical variant of AGD-Until-Guilty (Carmon et al., 2017), as well as other parameter-free variants, and is a viable alternative to nonlinear conjugate gradient methods.
Lower-bound analyses for nonconvex strongly-concave minimax optimization problems have shown that stochastic first-order algorithms require at least O(ε−4) sample complexity to find an ε-stationary point. Some works indicate that this complexity can be improved to O(ε−3) when the stochastic loss gradient is Lipschitz continuous. The question of achieving enhanced convergence rates under distinct conditions, remains open. In this work, we address this question for optimization problems that are nonconvex in the minimization variable and strongly concave or Polyak-Lojasiewicz (PL) in the maximization variable. We introduce novel bias-corrected momentum algorithms utilizing efficient Hessian-vector products. We establish convergence conditions and demonstrate a lower iteration complexity of O(ε−3) for the proposed algorithms. The effectiveness of the proposed method is validated through applications to robust logistic regression and robust adaptive cruise control.
Much of the existing theory on first-order non-smooth optimization is built on a restrictive assumption that the gradients of the objective function are uniformly bounded. We introduce a much more realistic class of generalized Lipschitz functions, where the gradient norms are bounded by an affine function of the optimality gap. We then ask a natural question: what algorithm achieves the best global convergence rates for solving convex stochastic generalized Lipschitz optimization problems? To address this, we develop a new convergence analysis for several existing algorithms and find that AdamW with clipped updates, provably outperforms other popular stochastic optimization methods, such as SGD and AdaGrad. Moreover, our analysis establishes the critical role of AdamW's exponentially weighted gradient accumulation, as opposed to simple averaging. We further show that clipped AdamW is universal and achieves improved rates under the popular generalized smoothness assumption, analyze the convergence of clipped AdamW with diagonal and matrix preconditioners, and extend our results to the quasar-convex setting.