The Complexity of Convex Optimization with Mismatched Geometry

Timofei Loginov, Alexander Gasnikov, Yuriy Dorn +4

Optimal first-order methods on non-Euclidean domains such as the ${\ell }_1$ ball $B_1^n(R)=\{x\in {\mathbb{R}}^n:\Vert x{\Vert }_1\le R\}$ pair the prox-function with the norm in which smoothness…