# A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates

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

## Key facts

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

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

- [GBM-based Bregman Proximal Algorithms for Constrained Learning](https://mlsanity.com/paper/2308.10767/) (2023)

## Abstract (arXiv)

This paper focuses on convex constrained optimization problems, where the solution is subject to a convex inequality constraint. In particular, we aim at challenging problems for which both projection into the constrained domain and a linear optimization under the inequality constraint are time-consuming, which render both projected gradient methods and conditional gradient methods (a.k.a. the Frank-Wolfe algorithm) expensive. In this paper, we develop projection reduced optimization algorithms for both smooth and non-smooth optimization with improved convergence rates under a certain regularity condition of the constraint function. We first present a general theory of optimization with only one projection. Its application to smooth optimization with only one projection yields O(1/ε) iteration complexity, which improves over the O(1/ε2) iteration complexity established before for non-smooth optimization and can be further reduced under strong convexity. Then we introduce a local error bound condition and develop faster algorithms for non-strongly convex optimization at the price of a logarithmic number of projections. In particular, we achieve an iteration complexity of widetilde O(1/ε2(1-θ)) for non-smooth optimization and widetilde O(1/ε1-θ) for smooth optimization, where θ∈(0,1] appearing the local error bound condition characterizes the functional local growth rate around the optimal solutions. Novel applications in solving the constrained ℓ1 minimization problem and a positive semi-definite constrained distance metric learning problem demonstrate that the proposed algorithms achieve significant speed-up compared with previous algorithms.