pipette
ESEspañol

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

Baiying Xin, Qi Deng

Preprint

In the authors' words

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 regression with , whose loss has a -H\"older-continuous gradient and for which the universal method requires iterations. Exploiting the problem structure, we characterize a family of smooth approximations based on -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 matrix--vector products, which significantly improves the complexity guarantee for . 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.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.