Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes
Authors: Guanghui Lan, Tianjiao Li, Yangyang Xu
Organizations: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332. · Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180.
We present a novel class of projected gradient (PG) methods for minimizing a smooth but not necessarily convex function over a convex compact set. We first provide a novel analysis of the constant-stepsize PG method, achieving a unified iteration complexity for finding an approximate stationary point for convex and nonconvex problems. We then develop an "auto-conditioned" projected gradient (AC-PG) variant that achieves the same iteration complexity without requiring the input of the Lipschitz constant of the gradient or any line search procedure. The key idea is to estimate the Lipschitz constant using first-order information gathered from the previous iterations, and to show that the error caused by underestimating the Lipschitz constant can be properly controlled. We then generalize the PG methods to the stochastic setting, by proposing a stochastic projected gradient (SPG) method and a variance-reduced stochastic gradient (VR-SPG) method, achieving new unified complexity bounds in different oracle settings. We also present auto-conditioned stepsize policies for both stochastic PG methods and establish comparable convergence guarantees.
Figure 1: Average and standard deviation results by the PG and AC-PG methods on solving 10 independently generated instances of box-constrained quadratic programming. Left: norm of projected gradient mapping at each iteration; Right: estimated local gradient Lipschitz constants by AC-PG starting from different initial estimates.
Figure 2: Average and standard deviation results by SPG, VR-SPG, AC-SPG, and AC-VR-SPG on solving 10 independently generated instances of ( 5.2 ) of dimension n=10 with pre-generated data sets for u1 and u2 .
Figure 3: Average and standard deviation results by SPG, VR-SPG, AC-SPG, and AC-VR-SPG on solving 10 independently generated instances of ( 5.2 ) of dimension n=100 with pre-generated data sets for u1 and u2 .
Figure 4: Average and standard deviation results by SPG, VR-SPG, AC-SPG, and AC-VR-SPG on solving 10 independently generated instances of ( 5.2 ) of dimension n=10 in an online manner, i.e., with samples generated for u1 and u2 while needed.
Figure 5: Average and standard deviation results by SPG, VR-SPG, AC-SPG, and AC-VR-SPG on solving 10 independently generated instances of ( 5.2 ) of dimension n=100 in an online manner, i.e., with samples generated for u1 and u2 while needed.
We propose ALFCG (Adaptive Lipschitz-Free Conditional Gradient), the first adaptive projection-free framework for stochastic composite nonconvex minimization that requires neither global smoothness constants nor line search. Unlike prior conditional gradient methods that use openloop diminishing stepsizes, conservative Lipschitz constants, or costly backtracking, ALFCG maintains a self-normalized accumulator of historical iterate differences to estimate local smoothness and minimize a quadratic surrogate model at each step. This retains the simplicity of Frank-Wolfe while adapting to unknown geometry. We study three variants. ALFCG-FS addresses finite-sum problems with a SPIDER estimator. ALFCG-MVR1 and ALFCG-MVR2 handle stochastic expectation problems by using momentum-based variance reduction with single-batch and two-batch updates, and operate under average and individual smoothness, respectively. To reach an ε-stationary point, ALFCG-FS attains O(N+Nε−2) iteration complexity, while ALFCG-MVR1 and ALFCG-MVR2 achieve O~(σ2ε−4+ε−2) and O~(σε−3+ε−2), where N is the number of components and σ is the noise level. In contrast to typical O(ε−4) or O(ε−3) rates, our bounds reduce to the optimal rate up to logarithmic factors O~(ε−2) as the noise level σ→0. Extensive experiments on multiclass classification over nuclear norm balls and ℓp balls show that ALFCG generally outperforms state-of-the-art conditional gradient baselines.
Ganzhao Yuan
Shenzhen University of Advanced Technology (SUAT), China
Achieving optimal rates for stochastic composite convex optimization without prior knowledge of problem parameters remains a central challenge. In the deterministic setting, the auto-conditioned fast gradient method has recently been proposed to attain optimal accelerated rates without line-search procedures or prior knowledge of the Lipschitz smoothness constant, providing a natural prototype for parameter-free acceleration. However, extending this approach to the stochastic setting has proven technically challenging and remains open. Existing parameter-free stochastic methods either fail to achieve accelerated rates or rely on restrictive assumptions, such as bounded domains, bounded gradients, prior knowledge of the iteration horizon, or strictly sub-Gaussian noise. To address these limitations, we propose a stochastic variant of the auto-conditioned fast gradient method, referred to as stochastic AC-FGM. The proposed method is fully adaptive to the Lipschitz constant, the iteration horizon, and the noise level, enabling both adaptive stepsize selection and adaptive mini-batch sizing without line-search procedures. Under standard bounded conditional variance assumptions, we show that stochastic AC-FGM achieves the optimal iteration complexity of O(1/ε) and the optimal sample complexity of O(1/ε2).
Yao Ji, Guanghui Lan
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, 225 North Ave, Atlanta, GA 30332, USA
In this paper, we consider a convex optimization problem, where the upper bound on the subgradient norm depends on the objective function. We establish a lower bound on the number of iterations required by any first-order method to find an approximate solution to the problem. Furthermore, we present two near-optimal algorithms that can match the lower bound up to logarithmic factors. The first algorithm is a projected GD with a carefully designed stepsize schedule which incorporates warm-up and decay phases. The second algorithm is scalar-stepsize clipped AdamW which extends the near-optimal guarantees to the stochastic setting, where only a noisy unbiased estimator of the subgradient is available.
Dmitry Kovalev, Grigory Malinovsky
Yandex Research · King Abdullah University of Science and Technology