Smooth Convex Optimization

Follow this topic Ask about this topic

Latest papers

16 papers4 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity
Nov 3, 2026Cedar Site BaiSmooth Convex Optimization Oracle Complexity
Department of Computer Science, Purdue University
A simple adaptive accelerated optimistic dual averaging method for unconstrained convex optimization in $p$ -norm geometry
Nov 3, 2026Bowen Li, Danqing Zhou, Chuan HeAccelerated Gradient Methods Smooth Convex Optimization
Department of Mathematics, Linköping University, Sweden
Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$ -Smooth Functions
Nov 3, 2026Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov +1Smooth Convex Optimization Oracle Complexity
MIRIAI, Moscow Independent Research Institute of Artificial Intelligence, Moscow, Russia. · Yandex, Moscow, Russia. · Innopolis University, Innopolis, Russia, Moscow Institute of Physics and Technology, Moscow, Russia. +1
Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
Oct 30, 2026Benjamin Grimmer, Qining ShenSmooth Convex Optimization Stochastic Gradient Descent
Johns Hopkins University, Department of Applied Mathematics and Statistics
Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
Oct 30, 2026Xinliang Zhang, Lesi Chen, Zonghan Li +1Smooth Convex Optimization Second-Order Optimization
IIIS, Tsinghua University
Weak- $L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails
Oct 20, 2026Alyona Nekrasova, Makar Sidorov, Savelii Chezhegov +4Smooth Convex Optimization Gradient Clipping
Independent researcher · Yaroslavl State University · Moscow Independent Research Institute of Artificial Intelligence +2
Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
Oct 18, 2026Matan Schliserman, Tomer KorenSmooth Convex Optimization Last-Iterate Convergence
Blavatnik School of Computer Science and AI, Tel Aviv University · Blavatnik School of Computer Science and AI, Tel Aviv University, and Google Research Tel Aviv
Silver Rate Is (Almost) Optimal for Gradient Descent
Sep 8, 2026Yuhan Ye, Kaizhao LiuLearning Rate Scheduling Optimization Convergence Analysis
MIT
The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
Sep 8, 2026Ruijie Li, Kang Chen, Tianyu WangLearning Rate Scheduling Last-Iterate Convergence
School of Data Science, Fudan University · Shanghai Center for Mathematical Sciences, Fudan University
Improved Gradient Descent Lower Bounds Beyond Nesterov
Sep 2, 2026Yuhan Ye, Kaizhao LiuSmooth Convex Optimization Gradient Descent
MIT
Primal Acceleration of Newton's Method
Aug 21, 2026Nikita DoikovSmooth Convex Optimization Second-Order Optimization
School of Operations Research and Information Engineering (ORIE), Cornell University, Ithaca, NY, USA.
Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time
Jun 15, 2026Xiuyuan Wang, Vishwak Srinivasan, Qiang Fu +3Hamiltonian Dynamics Smooth Convex Optimization
Department of Computer Science, Yale University · Department of EECS, Massachusetts Institute of Technology
Randomized Subspace Nesterov Accelerated Gradient
May 1, 2026Gaku Omiya, Pierre-Louis Poirion, Akiko TakedaGradient Descent Smooth Convex Optimization
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan
Deterministic Adam-Inspired Methods with Accelerated Convergence Rate
Apr 9, 2026Yaxin Yu, Long Chen, Zeyi XuSmooth Convex Optimization Accelerated Gradient Methods
School of Mathematics, Sichuan University, Chengdu, Sichuan, 610065, CHINA · Department of Mathematics, University of California, Irvine, Irvine, CA, 92697, USA
Small Gradient Norm Regret for Online Convex Optimization
Jan 20, 2026Wenzhi Gao, Chang He, Madeleine UdellOnline Convex Optimization Sequential Decision Making
ICME, Stanford University · SIME, Shanghai University of Finance and Economics · Department of Management Science and Engineering, Stanford University
Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity
Nov 4, 2025Dan GarberConstrained Optimization Frank-Wolfe Algorithms
Faculty of Data and Decision Sciences Technion - Israel Institute of Technology

Nov 3, 2026J/K move · Enter open · S save

Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity

Cedar Site Bai

Department of Computer Science, Purdue University

Smooth Convex Optimization Oracle Complexity

Open paper AskPDF arXiv

In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose

p^{th}

-order derivatives are Hölder continuous with degree

ν

and parameter

H

, and that are uniformly convex with degree

q

and parameter

σ

. When these orders match, namely,

q = p + ν

, we show that any deterministic algorithm with access to derivatives up to order

p

requires

Ω\left(\left(\frac{H}σ\right)^{\frac{2}{3(p+ν)-2}}\log\frac{Δ_0}ε\right)

oracle calls to reduce an initial optimality gap of

Δ_0

ε

. This matches the corresponding upper bound and establishes a higher-order uniformly convex counterpart to Nesterov's classical first-order lower bound for strongly convex functions. Rather than directly generalizing Nesterov's classical quadratic-chain construction, we develop a multiscale phase-wise construction that preserves previous oracle responses while maintaining global Hölder smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.