Faster Acceleration for Steepest Descent

2024/09/28 by Bai, Cedar Site, Bullins, Brian · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2409.19200

Abstract

Recent advances (Sherman, 2017; Sidford and Tian, 2018; Cohen et al., 2021) have overcome the fundamental barrier of dimension dependence in the iteration complexity of solving ℓ_∞ regression with first-order methods. Yet it remains unclear to what extent such acceleration can be achieved for general ℓ_p smooth functions. In this paper, we propose a new accelerated first-order method for convex optimization under non-Euclidean smoothness assumptions. In contrast to standard acceleration techniques, our approach uses primal-dual iterate sequences taken with respect to differing norms, which are then coupled using an implicitly determined interpolation parameter. For ℓ_p norm smooth problems in d dimensions, our method provides an iteration complexity improvement of up to O(d^1-(2)/(p)) in terms of calls to a first-order oracle, thereby allowing us to circumvent long-standing barriers in accelerated non-Euclidean steepest descent.

Cited by

• Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓ_p-Smooth Nonconvex Optimization

Related

• Higher-Order Accelerated Methods for Faster Non-Smooth Optimization
• Acceleration Meets Inverse Maintenance: Faster ℓ_∞-Regression
• Non-Euclidean High-Order Smooth Convex Optimization
• New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L₀, L₁)-Smoothness