# Projection-Free Non-Smooth Convex Programming

arXiv: https://arxiv.org/abs/2208.05127 · HTML: https://mlsanity.com/paper/2208.05127/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2022.

## Built on by (most cited first, 1 of 1)

- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)

## Abstract (arXiv)

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.