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

2016/08/11 by Tianbao Yang, Yang, Tianbao, Qihang Lin +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1608.03487

This is the long version of our ICML 2017 paper

openalex publication_date 2016/08/11 · openalex created_date 2016/09/16 · arxiv created 2017/06/12 · arxiv updated 2017/06/13 · openalex updated_date 2026/07/28

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 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/ε²) 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 ℓ₁ 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.

Citations

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• An Introduction To Compressive Sampling [A sensing/sampling paradigm that goes against the common knowledge in data acquisition]
• Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Optimal Stochastic Strongly Convex Optimization with a Logarithmic Number of Projections

Cited by

• Hinge-Proximal Stochastic Gradient Methods for Convex Optimization with Functional Constraints

Related

• Gradient Methods with Regularization for Constrained Optimization Problems and Their Complexity Estimates
• First order constrained optimization algorithms with feasibility updates
• Projection-Free Optimization on Uniformly Convex Sets
• Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets
• Efficient Projection-Free Online Convex Optimization with Membership Oracle