Optimal First-Order Methods for a Class of Structured Hölder-Smooth Problems
Abstract
Convex optimization with Hölder-continuous gradients has attracted considerable attention as a framework bridging smooth and nonsmooth optimization. For this class, Nesterov's universal fast gradient method attains the optimal black-box complexity, and we study whether exploiting further problem structure can further improve this bound. In this paper, we study an important class of Hölder-smooth problems, namely regularized ℓp regression with p∈(1,2), whose loss has a (p−1)-Hölder-continuous gradient and for which the universal method requires 𝒪(ε−2/(3p−2)) iterations. Exploiting the problem structure, we characterize a family of smooth approximations based on p-Huber smoothing and prove that, for any prescribed smoothness level, it minimizes the worst-case approximation error among smooth lower approximations of the scalar loss. Combined with accelerated proximal gradients, the smoothing approach attains an ε-optimal solution in 𝒪(ε−1/p) matrix--vector products, which significantly improves the complexity guarantee for 1<p<2. We show that this bound is optimal by providing a matching lower bound. Numerical experiments on synthetic and real data demonstrate the practical performance of the proposed methods.
Related
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
- Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
- Sliding Methods for Hölder-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling
- Obtaining Game-Stationary Points for Smooth Nonconvex-Nonconcave Minimax Problems via First-Order Methods
- Convergence Analysis of Newton Methods for Nonlinear Optimal Control Problems
BibTeX
@misc{xin2026optimal,
title = {{Optimal First-Order Methods for a Class of Structured Hölder-Smooth Problems}},
author = {Baiying Xin and Qi Deng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21595},
eprint = {2610.21595},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21595},
}
RIS
TY - UNPB
TI - Optimal First-Order Methods for a Class of Structured Hölder-Smooth Problems
AU - Baiying Xin
AU - Qi Deng
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21595
UR - https://arxiv.org/abs/2610.21595
AB - Convex optimization with Hölder-continuous gradients has attracted considerable attention as a framework bridging smooth and nonsmooth optimization. For this class, Nesterov's universal fast gradient method attains the optimal black-box complexity, and we study whether exploiting further problem structure can further improve this bound. In this paper, we study an important class of Hölder-smooth problems, namely regularized ℓ_p regression with p∈(1,2), whose loss has a (p−1)-Hölder-continuous gradient and for which the universal method requires 𝒪(ε^−2/(3p−2)) iterations. Exploiting the problem structure, we characterize a family of smooth approximations based on p-Huber smoothing and prove that, for any prescribed smoothness level, it minimizes the worst-case approximation error among smooth lower approximations of the scalar loss. Combined with accelerated proximal gradients, the smoothing approach attains an ε-optimal solution in 𝒪(ε^−1/p) matrix--vector products, which significantly improves the complexity guarantee for 1<p<2. We show that this bound is optimal by providing a matching lower bound. Numerical experiments on synthetic and real data demonstrate the practical performance of the proposed methods.
ER -