Benjamin Grimmer�with Kevin Shu and Alex L Wang�
Optimizing Optimization Methods�To and Beyond Minimax Optimality
Talk Outline
(i) Review of Minimax Optimal Methods
(ii) Beyond Minimax Optimality: A “Subgame Perfect Method”
(iii) Towards Minimax Optimal Gradient Descent
Smooth, Convex Optimization
Measures of Algorithms and Problem Instances
Some History of Smooth Convex Complexity Theory
Some History of Smooth Convex Complexity Theory
Some History of Smooth Convex Complexity Theory
Some History of Smooth Convex Complexity Theory
A Sample of the History of Optimized Methods
A Sample of the History of Optimized Methods
A Sample of the History of Optimized Methods
The State of Minimax Complexity Theory
The State of Minimax Complexity Theory
Talk Outline
(i) Review of Minimax Optimal Methods
(ii) Beyond Minimax Optimality: A “Subgame Perfect Method”
(iii) Towards Minimax Optimal Gradient Descent
A Case of Poor Performance from OGM
A Case of Poor Performance from OGM
A Case of Poor Performance from OGM
Beyond Minimax Optimality: Subgame Perfection
Beyond Minimax Optimality: Subgame Perfection
OGM, Perspective of [Taylor, Bach] and [Park, Park, Ryu]
OGM, Perspective of [Taylor, Bach] and [Park, Park, Ryu]
A Subgame Perfect Gradient Method (SPGM)
A Subgame Perfect Gradient Method (SPGM)
SPGM’s Subgame Perfection
SPGM’s Subgame Perfection
Talk Outline
(i) Review of Minimax Optimal Methods
(ii) Beyond Minimax Optimality: A “Subgame Perfect Method”
(iii) Towards Minimax Optimal Gradient Descent
Smooth, Convex Optimization and Gradient Descent
Conjectured Optimal Constant “Short” Steps
Conjectured Optimal Constant “Short” Steps
Better Theory from Long Steps (2018-2023)
Better Theory from Long Steps (2018-2023)
Better Theory from Long Steps (2018-2023)
Altschuler and Parrilo’s Silver Stepsizes (2023)
Altschuler and Parrilo’s Silver Stepsizes (2023)
Altschuler and Parrilo’s Silver Stepsizes (2023)
Silver Stepsizes Balance a Different s-Inequality
Silver Stepsizes Balance a Different s-Inequality
Composing Composable Sequences
Composing Composable Sequences
Examples of Basic s-Compositions and Silver Stepsizes
Examples of Basic f-Compositions�and Recovery of Numerically Minimax Optimal Steps
Gradient Descent’s Optimal Basic Stepsize Schedules
Gradient Descent’s Optimal Basic Stepsize Schedules
Talk Outline
(i) Review of Minimax Optimal Methods
(ii) Beyond Minimax Optimality: A “Subgame Perfect Method”
See Beyond Minimax Optimality: A Subgame Perfect Gradient Method
B.G., Kevin Shu, Alex L Wang arxiv:2412.06731
(iii) Towards Minimax Optimal Gradient Descent
See Composing Optimized Stepsize Schedules for Gradient Descent
B.G., Kevin Shu, Alex L Wang arxiv:2410.16249