Universal and Parameter-free Gradient Sliding for Composite Optimization

Abstract

We propose a Parameter-Free Universal Gradient Sliding (PFUGS) algorithm for computing an approximate solution to the convex composite optimization ${\min }_{x\in X}\{f(x)+g(x)\}$, where $f$ has $(M_{\hat{I}}½,\hat{I}½)$-Hölder continuous subgradient and $g$ has $L$-Lipschitz continuous gradient. PFUGS computes an $\epsilon$-approximate solution with $\mathcal{O}((M_{\hat{I}}½/\epsilon {)}^{2/(1+3\hat{I}½)})$ evaluations of (sub)gradients of $f$ and $\mathcal{O}((L/\epsilon {)}^{1/2})$ evaluations of gradients of $g$, without prior knowledge of problem constants. To the best of our knowledge, PFUGS is the first gradient sliding algorithm for problems involving two functions whose distinct problem constants are both unknown a priori.