Projection-Free Non-Smooth Convex Programming

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/√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 μ-strongly convex on the feasible set, we present a direct method with error at most 32ρ2L2/[μ(T+1)]. It uses a local linear optimization oracle with expansion factor ρ 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.