Optimal First-Order Methods for a Class of Structured H\"older-Smooth Problems

Convex optimization with H\"older-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\"older-smooth problems, namely regularized ${\ell }_p$ regression with $p\in (1,2)$, whose loss has a $(p-1)$-H\"older-continuous gradient and for which the universal method requires $\mathcal{O}({\epsilon }^{-2/(3p-2)})$ iterations. Exploiting the problem structure, we characterize a family of smooth approximations based on $p$-Huber smoothing and prove that it attains the exact optimal one-sided approximation–smoothness trade-off. Combined with accelerated proximal gradients, the smoothing approach attains an $\epsilon$-optimal solution in $\mathcal{O}({\epsilon }^{-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.