Projection-Free Non-Smooth Convex Programming

Abstract

We study nonsmooth convex minimization over a compact convex set without projections. For a globally $L$-Lipschitz objective, optimistic primal-dual updates give error at most $2LD/\sqrt{T}$ after $T$ iterations, where $D$ is the set's diameter. Each iteration uses at most one linear optimization call and one subgradient query at a point that may lie outside the feasible set. For objectives that are $\mu$-strongly convex on the feasible set, we present a direct method with error at most $32{\rho }^2{L}^2/[\mu (T+1)]$. It uses a local linear optimization oracle with expansion factor $\rho$ and subgradients of norm at most $L$ queried only at feasible points. The method requires neither restarts nor advance knowledge of $T$. We give self-contained proofs and a short restart argument for the convex variant of the Garber-Hazan algorithm that removes the logarithmic factor from their error bound.