Abstract:We consider a general class of ``inexactly smooth'' convex functions, providing a universal model capturing as special cases $L$-smooth, $M$-Lipschitz, and Hölder smooth functions, and any combination thereof. Such functions possess a calculus closely following that of smooth functions. Our main results provide inexactly smooth functions with interpolation theorems that are necessary and sufficient up to modest universal constants. These enable analysis of first-order methods for any inexactly smooth convex problem class via solving convex Performance Estimation Problems (PEPs). Further, these enable the extension of Drori and Taylor's constructive approach to algorithm design. From this, we derive an exactly minimax optimal method for $(\beta,0)$-Hölder smooth problems, methods with the best-known convergence guarantees up to constants for any $(\beta,p)$-Hölder smooth convex minimization, and a new universal fast backtracking method for any inexactly smooth convex problem.
From: Aaron Zoll [view email]
[v1]
Mon, 1 Jun 2026 00:05:46 UTC (46 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。