Non-Euclidean High-Order Smooth Convex Optimization

Abstract

We develop algorithms for the optimization of convex objectives that have Hölder continuous $q$-th derivatives by using a $q$-th order oracle, for any $q\ge 1$. Our algorithms work for general norms under mild conditions, including the ${\ell }_p$-settings for $1\le p\le \infty$. We can also optimize structured functions that allow for inexactly implementing a non-Euclidean ball optimization oracle. We do this by developing a non-Euclidean inexact accelerated proximal point method that makes use of an \emph{inexact uniformly convex regularizer}. We show a lower bound for general norms that demonstrates our algorithms are nearly optimal in high-dimensions in the black-box oracle model for ${\ell }_p$-settings and all $q\ge 1$, even in randomized and parallel settings. This new lower bound, when applied to the first-order smooth case, resolves an open question in parallel convex optimization.

arXiv commentrandomized and parallel lower bounds (and gen. to all norms), convexity of subproblems, inexactness of unacc. alg., better writing