Convex Optimization over Intersection of Simple Sets: improved Convergence Rate Guarantees via an Exact Penalty Approach
[edit]
Proceedings of the TwentyFirst International Conference on Artificial Intelligence and Statistics, PMLR 84:958967, 2018.
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 iterationcomplexity of $O(1/ε^2)$ for nonsmooth problems with no guarantees on the infeasibility. By reformulating the problem through exact penalty functions, we derive firstorder algorithms which not only guarantees that the distance to the intersection is small but also improve the complexity to $O(1/ε)$ and $O(1/\sqrt{ε})$ for smooth functions. For composite and smooth problems, this is achieved through a saddlepoint reformulation where the proximal operators required by the primaldual algorithms can be computed in closed form. We illustrate the benefits of our approach on a graph transduction problem and on graph matching.
Related Material


