2024/11/04 by Wenzhi Gao, Ya-Chi Chu, Gao, Wenzhi +5 · 7 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2411.01803
openalex publication_date 2024/11/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a framework to accelerate the convergence of gradient-based methods with online learning. The framework learns to scale the gradient at each iteration through an online learning algorithm and provably accelerates gradient-based methods asymptotically. In contrast with previous literature, where convergence is established based on worst-case analysis, our framework provides a strong convergence guarantee with respect to the optimal scaling matrix for the iteration trajectory. For smooth strongly convex optimization, our results provide an O(κ^⋆ log(1/ε)) complexity result, where κ^⋆ is the condition number achievable by the optimal preconditioner, improving on the previous O(√(n)κ^⋆ log(1/ε)) result. In particular, a variant of our method achieves superlinear convergence on convex quadratics. For smooth convex optimization, we show for the first time that the widely-used hypergradient descent heuristic improves on the convergence of gradient descent.