Abstract
We consider the problem of minimizing a convex function over the intersection of finitely many simple sets which are easy to project onto. This is an important problem arising in various domains such as machine learning. The main difficulty lies in finding the projection of a point in the intersection of many sets. Existing approaches yield an infeasible point with an iteration-complexity of $O(1/\varepsilon^2)$ for nonsmooth problems with no guarantees on the in-feasibility. By reformulating the problem through exact penalty functions, we derive first-order algorithms which not only guarantee that the distance to the intersection is small but also improve the complexity to $O(1/\varepsilon)$ and $O(1/\sqrt{\varepsilon})$ for smooth functions. For composite and smooth problems, this is achieved through a saddle-point reformulation where the proximal operators required by the primal-dual algorithms can be computed in closed form. We illustrate the benefits of our approach on a graph transduction problem and on graph matching.
Introduction: The Projection Bottleneck
In the world of convex optimization, we often encounter "simple" sets—constraints like boxes, spheres, or simplices where projecting a point onto the set is computationally trivial. However, many real-world machine learning problems require staying within the intersection of several such simple sets. While each individual constraint is easy to handle, their intersection is often a nightmare to project onto.
This challenge is known as the "Projection Bottleneck." Standard algorithms like Projected Subgradient Descent require a projection onto the feasible set at every step. If the feasible set is the intersection of $m$ simple sets (e.g., the set of doubly stochastic matrices, which is the intersection of row-sum, column-sum, and non-negativity constraints), calculating that single projection often requires an inner iterative loop (like Dykstra’s algorithm), which is slow and computationally expensive.
Existing "infeasible" methods avoid this by only projecting onto individual sets, but they typically suffer from two flaws:
- Slow Convergence: They often require $O(1/\epsilon^2)$ iterations to reach an $\epsilon$-accurate solution.
- Feasibility Drift: They provide no deterministic guarantee on how far the final point is from the actual intersection of the sets.
The Exact Penalty Framework
The authors' core innovation is the Exact Penalty Reformulation. Instead of solving the constrained problem directly, they solve: $$\min_{x \in X} f(x) + \lambda h_P(x)$$ where $h_P(x)$ is a penalty function based on the distance to each individual set $C_i$.
Key Innovations
- Linear Regularity: The framework leverages a geometric property called "linear regularity," which relates the distance to the intersection of sets to the distances to the individual sets. This allows the authors to prove that a finite penalty parameter $\lambda$ is sufficient to recover the exact optimal solution, avoiding the numerical instability of standard penalty methods where $\lambda$ must go to infinity.
- Split-Projection Subgradient (SPS): An adaptation of the subgradient method that only requires one projection onto each individual set per iteration.
- Exact Penalty Primal-Dual (EPPD): For smooth functions, a saddle-point reformulation allows the use of fast primal-dual machinery to reach $O(1/\epsilon)$ or even $O(1/\sqrt{\epsilon})$ rates.
- Split Mirror Prox (SMP): A technique for nonsmooth functions with specific structures (like max-functions), achieving $O(1/\epsilon)$ complexity.
Theoretical Convergence Rates
The proposed framework significantly improves the iteration complexity for various classes of functions. By using the exact penalty approach, the authors match the optimal rates typically reserved for simpler constraints, even when dealing with complex intersections.
As shown in the table above, the framework achieves $O(1/\epsilon)$ complexity for smooth convex functions and $O(1/\sqrt{\epsilon})$ for strongly convex smooth functions. For nonsmooth functions, the complexity is improved to $O(1/\epsilon)$ in the strongly convex case, a notable jump from the standard $O(1/\epsilon^2)$ rate.
Experimental Validation
The authors evaluated their algorithms on two primary tasks to demonstrate practical performance gains:
MNIST Digit Recognition
Used for a graph transduction problem (learning orthonormal embeddings), the authors constructed graphs with 1,000 nodes based on pairs of digit classes. Their SMP algorithm achieved higher classification accuracy compared to the Inexact Infeasible Proximal Method (IIPM). Crucially, SMP's objective values remained stable even after projecting the final "infeasible" point back onto the feasible set, whereas IIPM’s objective values shifted significantly, indicating poor feasibility guarantees in the baseline.
Graph Matching
For the graph matching problem, randomly generated undirected graphs with 200 nodes were used to compare the efficiency of the EPPD algorithm against Frank-Wolfe and other baselines. In these experiments, the EPPD method was significantly faster in wall-clock time than the Frank-Wolfe algorithm and the Composite Mirror-Prox (CMP) method, despite all three having similar theoretical convergence rates. This highlights the efficiency of using closed-form proximal operators enabled by the saddle-point reformulation.
Conclusion and Future Work
This work provides a robust theoretical and practical foundation for optimizing over intersections of sets. By ensuring that the "heavy lifting" (the proximal operators) can be computed in closed form using simple projections, the authors provide a path to faster, more stable optimization in constrained machine learning problems.
Future work may address the dependence on the Linear Regularity Constant ($\Upsilon$). If sets intersect at a very "shallow" angle, this constant can be large, potentially slowing down the algorithm. Additionally, extending this framework to cases with an extremely large or infinite number of sets $m$ using stochastic oracles remains an open and promising area of research.
Summary updated