Adaptive method speeds up convex optimization without line search
A simple adaptive accelerated optimistic dual averaging method for unconstrained convex optimization in $p$-norm geometry
Artificial IntelligenceMachine Learning
Summary
Solving large math problems efficiently is often done step-by-step, but choosing the right step sizes can be tricky. The authors introduce a new method that adapts the step sizes automatically and works well for a wide range of problem types based on different geometric settings. This method does not need trial-and-error line searches, making it simpler and faster. It also comes with theoretical guarantees that show it performs nearly as well as the best possible approaches in many cases.
What this means in practice
- •For machine learning engineers: Improve training speed of large-scale models by using a step size adaptive method that handles different data geometries without extra trial steps.
- •For optimization software developers: Incorporate a unified update algorithm for various p-norm geometries to simplify and accelerate implementations of convex optimization solvers.
Authors
Bowen Li, Danqing Zhou, Chuan He
Abstract
Efficient preconditioning plays an important role in large-scale first-order optimization. In this paper, we propose an adaptive accelerated optimistic dual averaging ($\text{A}^2$ODA) method for unconstrained convex optimization that adopts low-cost preconditioning based on $p$-norm geometry for $p\in[2,\infty]$. The method is line-search-free and employs a new stepsize selection technique based on an aggregated affine lower model. Its update structure is simple and unified across $p\in[2,\infty]$, with the case $p>2$ requiring no more elaborate updates than the Euclidean case $p=2$. Under a generalized local smoothness condition, we derive a convergence bound that separates the effects of constant and gap-dependent curvature, with the latter potentially yielding faster-decaying terms. In the special case of local smoothness, this bound recovers a nearly optimal convergence rate.