Near-optimal method for highly smooth convex optimization

2018/12/19 by Sébastien Bubeck, Bubeck, Sébastien, Qijia Jiang +7 · 5 citations
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1812.08026

15 pages

openalex publication_date 2018/12/19 · arxiv created 2019/06/23 · arxiv updated 2019/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a near-optimal method for highly smooth convex optimization. More precisely, in the oracle model where one obtains the p^th order Taylor expansion of a function at the query point, we propose a method with rate of convergence O(1/k^{( 3p +1)/(2)}) after k queries to the oracle for any convex function whose p^th order derivative is Lipschitz.

Cited by

• Optimal Convex Optimization with Inexact Second-Order Oracles
• Solving Zero-Sum Games with Fewer Matrix-Vector Products
• Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
• Solving Convex-Concave Problems with O(ε^-4/7) Second-Order Oracle Complexity
• Faithful-Newton Framework: Bridging Inner and Outer Solvers for Enhanced Optimization

Related

• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• Smooth Convex Optimization using Sub-Zeroth-Order Oracles
• High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
• Non-Euclidean High-Order Smooth Convex Optimization