Convex optimization improved with fewer second-order calculations
Near-Optimal Convex Optimization with Lazy Second-Order Oracles
Machine Learning
Summary
Finding the best solution to a problem with curved shapes (convex optimization) often uses information about slopes and curvatures. The paper looks at a way to check slopes every step but only check curvature occasionally, making the process more efficient. The authors show a new best-possible speed for this method and create an algorithm that matches this speed nearly exactly. This improves on earlier methods by needing fewer expensive curvature checks while still finding good solutions.
What this means in practice
- •For optimization engineers: Design optimization algorithms with fewer expensive curvature calculations while maintaining reliable solution quality.
- •For machine learning practitioners: Develop training methods that balance gradient and Hessian computations to speed up model tuning for large datasets.
A theory result. No direct application yet.
Authors
Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang
Abstract
This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per $m$ iterations. Under this setting, we show a lower bound of $Ω(m+ m^{1/7} ε^{-2/7})$ on the number of total iterations to find an $ε$-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of $\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7})$ and is tight up to logarithmic factors.