A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:39013910, 2017.
Abstract
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 timeconsuming, which render both projected gradient methods and conditional gradient methods (a.k.a. the FrankWolfe algorithm) expensive. In this paper, we develop projection reduced optimization algorithms for both smooth and nonsmooth 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/\epsilon)$ iteration complexity, which improves over the $O(1/\epsilon^2)$ iteration complexity established before for nonsmooth optimization and can be further reduced under strong convexity. Then we introduce a local error bound condition and develop faster algorithms for nonstrongly convex optimization at the price of a logarithmic number of projections. In particular, we achieve an iteration complexity of $\widetilde O(1/\epsilon^{2(1\theta)})$ for nonsmooth optimization and $\widetilde O(1/\epsilon^{1\theta})$ for smooth optimization, where $\theta\in(0,1]$ appearing the local error bound condition characterizes the functional local growth rate around the optimal solutions. Novel applications in solving the constrained $\ell_1$ minimization problem and a positive semidefinite constrained distance metric learning problem demonstrate that the proposed algorithms achieve significant speedup compared with previous algorithms.
Related Material


