Research map / Optimization / Nonconvex and smooth optimization
Adaptive Proximal Gradient Method for Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes adaptive gradient descent and proximal gradient methods whose stepsizes come from observed gradient differences (local Lipschitz estimates), proven convergent under only local smoothness and allowing larger steps than prior AdGD.
Problem
Choosing stepsizes for gradient descent and proximal gradient on convex smooth (or composite) problems without knowing the global Lipschitz constant, with convergence guarantees requiring only local Lipschitzness of the gradient.
Approach
Refines AdGD with a new analysis (using monotonicity and a Lyapunov energy) that permits a second stepsize bound alpha_k <= alpha_{k-1}/sqrt([2 alpha_{k-1}^2 L_k^2 - 1]_+) and larger steps; extends the scheme to the composite case via a proximal gradient variant (AdProxGD) with a novel Lyapunov function.
Key results
- Theorem shows AdGD-type steps with alpha_k <= alpha_{k-1}/sqrt([2alpha_{k-1}^2L_k^2-1]_+) converge with rate min f(x^i)-f* <= LR^2/(sqrt2 k) under only local Lipschitzness, with steps allowed beyond 2/L.
- Proposed AdProxGD is reported to outperform ProxGD with Armijo linesearch across five convex problem families, per preliminary experiments (no exact numbers given in the text).
- Counterexample shows the first AdGD bound (step growth cap) is necessary: removing it makes the method diverge on a locally smooth 1D function.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AdProxGD instead of ProxGD with Armijo linesearch | ProxGD · Maximum likelihood estimation, matrix completion, piecewise-linear curve, nonnegative matrix factorization, and entropy maximization | computational operations | Helped |
Surprising findings
- Removing the step-growth constraint from AdGD makes the method diverge for any c>=1 on a specific locally smooth convex function.
- Authors note that the choice of which pairs (s,r) work best for ProxGD linesearch is not explained by theory.
Limitations
- Analysis applies only to convex problems; nonconvex case not covered.
- No formal linear convergence result for strongly convex composite case; small-gradient rate left open.
Experimental setup
Benchmarks: maximum likelihood estimate of information matrix low-rank matrix completion minimal length piecewise-linear curve nonnegative matrix factorization dual of entropy maximization
Metrics: number of projections number of SVDs number of gradients function value convergence
Baselines: ProxGD with Armijo linesearch AdGD
Builds on: AdGD (adaptive gradient descent without descent) Armijo linesearch Barzilai-Borwein method
Closest papers by meaning
- A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization (NeurIPS 2018 · similarity 0.90)
- Adaptive Proximal Gradient Methods Are Universal Without Approximation (ICML 2024 · similarity 0.90)
- Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point (ICML 2024 · similarity 0.88)
- From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization (NeurIPS 2026 · similarity 0.87)
- Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions (NeurIPS 2025 · similarity 0.87)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.