Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism

2025/10/03 by Francisco Patitucci, Patitucci, Francisco, Ruichen Jiang +3
Computer Science · Decision Sciences · Engineering · #Stochastic Gradient Optimization Techniques #Advanced Bandit Algorithms Research #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2510.03167

Abstract

A recent breakthrough in nonconvex optimization is the online-to-nonconvex conversion framework of [Cutkosky et al., 2023], which reformulates the task of finding an ε-first-order stationary point as an online learning problem. When both the gradient and the Hessian are Lipschitz continuous, instantiating this framework with two different online learners achieves a complexity of O(ε^-1.75log(1/ε)) in the deterministic case and a complexity of O(ε^-3.5) in the stochastic case. However, this approach suffers from several limitations: (i) the deterministic method relies on a complex double-loop scheme that solves a fixed-point equation to construct hint vectors for an optimistic online learner, introducing an extra logarithmic factor; (ii) the stochastic method assumes a bounded second-order moment of the stochastic gradient, which is stronger than standard variance bounds; and (iii) different online learning algorithms are used in the two settings. In this paper, we address these issues by introducing an online optimistic gradient method based on a novel doubly optimistic hint function. Specifically, we use the gradient at an extrapolated point as the hint, motivated by two optimistic assumptions: that the difference between the hint and the target gradient remains near constant, and that consecutive update directions change slowly due to smoothness. Our method eliminates the need for a double loop and removes the logarithmic factor. Furthermore, by simply replacing full gradients with stochastic gradients and under the standard assumption that their variance is bounded by σ², we obtain a unified algorithm with complexity O(ε^-1.75 + σ² ε^-3.5), smoothly interpolating between the best-known deterministic rate and the optimal stochastic rate.

Citations

• Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
• General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization
• Adam with model exponential moving average is effective for nonconvex optimization
• Random Scaling and Momentum for Non-smooth Non-convex Optimization
• Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods
• Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε^-7/4) Complexity
• Impossible Tuning Made Possible: A New Expert Algorithm and Its\n Applications
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• Momentum Improves Normalized SGD
• Lower Bounds for Non-Convex Stochastic Optimization
• UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for\n Constrained Optimization
• Momentum-Based Variance Reduction in Non-Convex SGD
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Online Adaptive Methods, Universality and Acceleration
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• A Newton-CG Algorithm with Complexity Guarantees for Smooth\n Unconstrained Optimization
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• Neon2: Finding Local Minima via First-Order Oracles
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• Lower Bounds for Finding Stationary Points II: First-Order Methods
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Lower bounds for finding stationary points I
• Natasha 2: Faster Non-Convex Optimization Than SGD
• Complexity analysis of second-order line-search algorithms for smooth\n nonconvex optimization
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient\n Descent on Non-Convex Functions
• Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming
• Online Learning with Predictable Sequences

Related

• Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
• Anytime Online-to-Batch Conversions, Optimism, and Acceleration
• Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality
• Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness