Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
Abstract
Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate stationarity, and its minimization usually implies stronger results than those for minimization of function values. In this work, we study gradient-norm minimization for convex functions that are (L,κ)-Hölder smooth with respect to the ℓp-norms, p ≥ 1. We develop algorithms that achieve near-optimal gradient-oracle complexity for this problem. In the smooth case, our results resolve the previously open setting p>2. For Hölder-smooth objectives, we close the complexity gap throughout the full p-range, including to the best of our knowledge, a gap in the Euclidean case. We provide two families of algorithms: the first one comes with a simple iteration and generalizes a phenomenon known as mirror duality, exploiting dual behaviours of algorithms with errors and inexact computations. The second makes use of accumulating regularizers centered at different approximate solutions, which we sequentially minimize in order to provide our near-optimal rates.
Related
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Can Acceleration in Gradient-Norm Minimization Be Anytime? Sharp Last-Iterate Limits in Smooth Convex Optimization
- Efficient Optimization on the Euclidean Sphere: Riemannian Gradient Alignment as a Unifying Principle
- Hölder Gradient Estimates for (s,p)-Poisson Equations with measurable and Hölder Data
BibTeX
@misc{pelleriti2026optimal,
title = {{Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization}},
author = {Nico Pelleriti and Maryam Shiran and David Martínez-Rubio and Max Zimmer and Sebastian Pokutta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01122},
eprint = {2609.01122},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01122},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
AU - Nico Pelleriti
AU - Maryam Shiran
AU - David Martínez-Rubio
AU - Max Zimmer
AU - Sebastian Pokutta
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01122
UR - https://arxiv.org/abs/2609.01122
AB - Minimizing gradients of a convex function is an important problem across optimization and learning tasks. The gradient provides a directly computable certificate of approximate stationarity, and its minimization usually implies stronger results than those for minimization of function values. In this work, we study gradient-norm minimization for convex functions that are (L,κ)-Hölder smooth with respect to the ℓ_p-norms, p ≥ 1. We develop algorithms that achieve near-optimal gradient-oracle complexity for this problem. In the smooth case, our results resolve the previously open setting p>2. For Hölder-smooth objectives, we close the complexity gap throughout the full p-range, including to the best of our knowledge, a gap in the Euclidean case. We provide two families of algorithms: the first one comes with a simple iteration and generalizes a phenomenon known as mirror duality, exploiting dual behaviours of algorithms with errors and inexact computations. The second makes use of accumulating regularizers centered at different approximate solutions, which we sequentially minimize in order to provide our near-optimal rates.
ER -