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/\epsilon)$ iteration complexity, which improves over the $O(1/\epsilon^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/\epsilon^{2(1-\theta)})$ for non-smooth 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 semi-definite constrained distance metric learning problem demonstrate that the proposed algorithms achieve significant speed-up compared with previous algorithms.
Introduction
A fundamental challenge in convex constrained optimization is the computational overhead associated with maintaining feasibility. Standard approaches, such as Projected Gradient Descent (PGD), necessitate a projection step at every iteration to ensure the solution remains within the constraint set $\Omega = \{x : c(x) \le 0\}$. For many high-dimensional applications—including learning Positive Semi-Definite (PSD) matrices or handling complex polyhedral constraints—these projections are computationally prohibitive, often requiring expensive operations like Eigenvalue Decomposition (EVD).
This work, originally published in ICML 2017, addresses this bottleneck by proposing a framework that significantly reduces the number of required projections while maintaining or improving convergence rates. The authors demonstrate that by treating feasibility as a "soft" requirement during intermediate steps, one can achieve state-of-the-art results with far fewer computational resources.
Methodology
The core innovation lies in a "projection-reduced" framework that shifts the constraint into the objective function via a parameterized penalty function $h_\gamma(x)$.
One-Projection Theory
The authors first establish that for smooth optimization, an unconstrained accelerated gradient method can be applied to the penalized objective, requiring exactly one projection at the final step. This approach achieves an iteration complexity of $O(1/\epsilon)$, a notable improvement over the $O(1/\epsilon^2)$ complexity typically associated with non-smooth one-projection methods. This result can be further improved under conditions of strong convexity.
Local Error Bound (LEB) and Epoch-Based Algorithms
To further accelerate convergence, the paper introduces the Local Error Bound (LEB) condition. This regularity condition characterizes the functional growth rate around optimal solutions, acting as a bridge between general convexity and strong convexity. Leveraging LEB, the authors propose two stage-based algorithms:
- LoPGD (Local Projection Gradient Descent) for non-smooth problems.
- LoPNAG (Local Projection Nesterov’s Accelerated Gradient) for smooth problems.
These algorithms operate in epochs, performing gradient updates on the penalized objective within each stage and projecting onto the constraint set only at the end of each epoch. Because the number of epochs is logarithmic relative to the desired accuracy, the total number of projections is also logarithmic (i.e., $O(\log(1/\epsilon))$).
Experimental Evaluation
The proposed algorithms were evaluated on two distinct tasks: Compressive Sensing and Distance Metric Learning (DML).
Compressive Sensing
Using synthetic data for a $1000 \times 5000$ measurement matrix, LoPNAG was compared against the standard NESTA solver for solving an $\ell_1$ minimization problem with a quadratic constraint. As shown in the results, LoPNAG achieves comparable objective values with a fraction of the projections and significantly lower wall-clock time.
Distance Metric Learning
On the colon-cancer dataset (2,000 features), the task involved a PSD constraint where projections require EVD. LoPGD demonstrated a massive reduction in computation time compared to standard PGD, reaching a lower objective value in under 2 hours compared to over 57 hours for PGD.
Key Insights and Conclusion
The research demonstrates that feasibility can be treated as a "soft" requirement during intermediate iterations. By controlling constraint violation through smooth penalties (using log-exponential forms), one can delay projection until the end of an epoch. The LEB condition proves to be a powerful tool for achieving intermediate fast rates in high-dimensional settings where strong convexity is absent.
While the framework offers substantial speedups, practical implementation requires careful tuning of the penalty parameter $\lambda$ and the LEB parameter $\theta$. Future work may explore extending these logarithmic projection theories to stochastic settings, which are prevalent in deep learning applications.
Summary updated