A Practical Adaptive Subgame Perfect Gradient Method

2025/10/24 by Alan Luner, Benjamin Grimmer, Luner, Alan +1 · 1 voice · 1 citation
Mathematics · #FOS: Mathematics #Optimization and Control (math.OC) #math.OC

paper · pdf · doi:10.48550/arxiv.2510.21617

arxiv published 2025/10/24 · arxiv updated 2026/02/11

Abstract

We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on a (limited) memory/bundle of past first-order information. ASPGM is linesearch-free, parameter-free, and adaptive due to its use of recently developed auto-conditioning, restarting, and preconditioning ideas. We show that ASPGM is competitive with state-of-the-art L-BFGS methods on a wide range of smooth convex problems. Unlike quasi-Newton methods, however, our core algorithm underlying ASPGM has strong, subgame perfect, non-asymptotic guarantees, providing certificates of solution quality, resulting in simple stopping criteria and restarting conditions.

Citations

• Simple linesearch-free first-order methods for nonconvex optimization
• Gradient Methods with Online Scaling Part II. Practical Aspects
• Affine-Invariant Global Non-Asymptotic Convergence Analysis of BFGS under Self-Concordance
• Adaptive Acceleration Without Strong Convexity Priors Or Restarts
• An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization
• Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes
• Beyond Minimax Optimality: A Subgame Perfect Gradient Method
• Gradient Methods with Online Scaling
• An optimal lower bound for smooth convex functions
• Adaptive proximal gradient methods are universal without approximation
• A simple uniformly optimal method without line search for convex optimization
• Adaptive Proximal Gradient Method for Convex Optimization
• Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking
• Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient
• A first-order primal-dual method with adaptivity to local smoothness
• Optimal First-Order Algorithms as a Function of Inequalities
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods
• Potential-Function Proofs for First-Order Methods
• The exact information-based complexity of smooth convex minimization
• Julia: A Fresh Approach to Numerical Computing
• Julia: A Fresh Approach to Numerical Computing
• Bundle-Level Type Methods Uniformly Optimal for Smooth and Nonsmooth Convex Optimization
• Performance of first-order methods for smooth convex minimization: a\n novel approach
• Adaptive Restart for Accelerated Gradient Schemes
• Algorithm 778: L-BFGS-B
• Conditioning of quasi-Newton methods for function minimization
• A new approach to variable metric algorithms
• A family of variable-metric methods derived by variational means

Cited by

• Subgame Perfect Methods in Nonsmooth Convex Optimization

Discussions

• arxiv.org/abs/2510.21617 'A Practical Adaptive Subgame Perfect Gradient Method' - Alan Luner, Benjamin Grimmer Symbolic methods have played a fascinating role in the recent analysis of first-order opt [bsky, 0 points, 1 comments]

Related

• Beyond Minimax Optimality: A Subgame Perfect Gradient Method
• Subgame Perfect Methods in Nonsmooth Convex Optimization
• Adaptive Restart of the Optimized Gradient Method for Convex Optimization
• Adaptive extra-gradient methods for min-max optimization and games
• An optimal lower bound for smooth convex functions