Optimal First-Order Methods for a Class of Structured Hölder-Smooth Problems

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 ${\mathrm{\ell }}_p$ regression with $p\in (1,2)$, whose loss has a $(p-1)$-Hölder-continuous gradient and for which the universal method requires $\mathcal{O}({\epsilon }^{-2\mathrm{/}(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 $\epsilon$-optimal solution in $\mathcal{O}({\epsilon }^{-1\mathrm{/}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.