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

Tianbao Yang, Qihang Lin, Lijun Zhang

Introduction

In machine learning and signal processing, optimizing an objective function often requires satisfying complex constraints, such as ensuring a learned matrix is Positive Semi-Definite (PSD). Traditionally, algorithms like Projected Gradient Descent (PGD) handle this by taking a gradient step and then "projecting" the result back into the valid constraint space at every single iteration.

While this is computationally cheap for simple constraints like bounding boxes, it becomes a massive bottleneck for complex constraints (e.g., polyhedrons, quadratic boundaries, or PSD matrices). Alternatively, Frank-Wolfe methods require solving a linear optimization problem over the constraint domain at each step, which can also be prohibitively expensive.

This paper tackles this computational bottleneck by introducing a framework that requires only a single or a logarithmic number of projections. By addressing the theoretical gap for smooth and non-strongly convex optimization, the authors achieve improved convergence rates without the heavy burden of per-iteration projections.

The Penalty-Based Framework

The authors propose temporarily ignoring hard constraints and instead optimizing an unconstrained, augmented objective function.

The "One Projection" Theory: The constraint is moved into the objective function via a penalty term. For non-smooth problems, a hinge-loss style penalty is used. For smooth problems, the authors introduce a novel smooth penalty function (using a logarithm of exponentials) to ensure gradients remain Lipschitz continuous. The model is trained using standard unconstrained solvers (like Nesterov's Accelerated Gradient), and exactly one projection is performed at the very end to ensure the final solution is strictly valid. This smooth penalty unlocks acceleration, allowing the use of accelerated gradient methods to achieve an $O(1/\epsilon)$ iteration complexity with only one projection.

Logarithmic Projections via Local Error Bounds: Because strong convexity is a strict assumption that many real-world problems fail to meet, the authors leverage a milder assumption called a local error bound. This bound essentially states that the distance to the optimal solution is bounded by how suboptimal the current function value is.

Under this error bound, they design epoch-based algorithms (LoPGD and LoPNAG). The model optimizes the penalized objective and projects the solution only at the end of each epoch. Step sizes and penalty weights are halved between epochs. Because the epochs grow exponentially, the algorithm only requires a logarithmic number of projections overall (e.g., $O(\log(1/\epsilon))$). For non-strongly convex problems satisfying the local error bound (with constant $\theta \in (0,1]$), this achieves iteration complexities of $O(1/\epsilon^{2(1-\theta)})$ for non-smooth and $O(1/\epsilon^{1-\theta})$ for smooth optimization.

Experimental Results

The authors evaluated their algorithms on two primary tasks, demonstrating massive speedups over traditional methods.

Compressive Sensing

Evaluated on synthetic data, the goal was to reconstruct a sparse high-dimensional vector from a small number of noisy measurements. The proposed LoPNAG algorithm was compared against the standard NESTA algorithm.

Compressive Sensing Results

As shown above, LoPNAG outperformed NESTA by achieving a lower recovery error (0.0180 vs 0.0186) in a fraction of the time (87 seconds using only 5 projections, compared to over 500 seconds and 20,000 projections for NESTA).

High-Dimensional Distance Metric Learning

The framework was also evaluated on a distance metric learning task using the colon-cancer dataset (2000 features, 62 examples, generating 780 training pairs). Here, the constraint requires the learned metric matrix to be PSD, making projections highly expensive.

Distance Metric Learning Results

The proposed LoPGD algorithm absolutely crushed standard PGD. LoPGD reached an objective value of 0.0405 in just 1.89 hours, requiring only 8 projections. In stark contrast, standard PGD ran for over 57 hours, required 8,000 projections, and still only managed to reach a worse objective value of 0.0879.

Limitations and Future Work

The primary limitation of this work lies in the theoretical application of the local error bound condition. While the algorithms work exceptionally well in practice, rigorously proving the exact value of the error bound constant ($\theta$) for complex, real-world formulations—like the specific distance metric learning problem tested—remains an open mathematical challenge. Establishing these regularity conditions for a broader class of constrained matrix optimization problems is a promising direction for future theoretical work.

Summary updated

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 project...
BibTeX
@inproceedings{yang2017richer,
  author = {Tianbao Yang and Qihang Lin and Lijun Zhang},
  title = {{A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates}},
  booktitle = {International Conference on Machine Learning},
  year = {2017},
  url = {https://openreview.net/forum?id=H1Zvmj-uZS},
}
Figure