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/\epsilon^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/\epsilon)$ and $O(1/\sqrt{\epsilon})$ 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
In many machine learning and optimization tasks, such as matrix completion or graph matching, the objective is to minimize a function subject to several constraints simultaneously. Mathematically, this involves finding a point in the intersection of multiple convex sets $C_1, C_2, \dots, C_m$. While projecting a point onto a single "simple" set $C_i$ is often efficient, projecting onto their intersection is frequently computationally prohibitive. Existing first-order methods typically struggle with this bottleneck, often resulting in solutions that are either far from the feasible region or converge at a slow rate of $O(1/\epsilon^2)$. This paper introduces an "exact penalty" framework to bridge this gap, providing algorithms that are both computationally fast and "feasibility-aware."
Proposed Framework: Exact Penalty Reformulation
The core innovation is the transformation of the constrained problem into an unconstrained (or simpler constrained) one using an exact penalty function: $$\min_{x \in X} f(x) + \lambda h_P(x)$$ where $h_P(x)$ represents the distance to the individual sets $C_i$.
Key Technical Components
- Linear Regularity: The authors leverage "linear regularity," a property ensuring that the distance to the intersection of sets is bounded by the distances to the individual sets. This allows for a finite penalty parameter $\lambda$ to recover the exact optimal solution, avoiding the numerical instability associated with infinite penalties.
- Exact Penalty Primal-Dual (EPPD): For smooth functions, a saddle-point reformulation allows the use of fast primal-dual algorithms. These algorithms utilize proximal operators that can be computed in closed form using individual set projections.
- Split-Mirror Prox (SMP): A specialized variant designed for nonsmooth problems that possess a specific "smooth convex-concave" structure.
Theoretical Convergence
By moving to a saddle-point representation and utilizing acceleration techniques, the framework achieves a significant leap in iteration complexity. For smooth functions, the complexity improves from $O(1/\epsilon^2)$ to $O(1/\epsilon)$, and for strongly convex smooth functions, it reaches $O(1/\sqrt{\epsilon})$.
Experimental Results
Graph Matching
The authors evaluated the EPPD method on graph matching using randomly generated undirected graphs. The task involved minimizing the difference between adjacency matrices over the set of doubly stochastic matrices. As shown in the performance plot, EPPD converged significantly faster than the standard Frank-Wolfe algorithm and the Composite Mirror-Prox (CMP) method. While theoretical rates per iteration are similar, EPPD's iterations are cheaper because they rely on simple projections rather than complex linear maximization subproblems.
Graph Transduction
Tested on the MNIST database, the SMP algorithm was used to learn optimal orthonormal embeddings for digit classification. SMP achieved higher classification accuracy (e.g., 96.9% for "1 vs 2") compared to the Inexact Infeasible Proximal Method (IIPM). Crucially, IIPM often reported misleadingly low objective values because its solutions remained significantly outside the feasible set, whereas the proposed framework maintained strict feasibility guarantees.
Conclusion and Future Work
This work demonstrates that exact penalty methods can provide both superior convergence rates and explicit bounds on infeasibility for multi-constraint convex problems. Future research directions include scaling the approach to a very large number of sets $m$ via stochastic projection methods and extending the framework to non-Euclidean geometries using general Mirror Descent.
Summary updated