Exact Lipschitz Regularization of Convex Optimization Problems

We consider the class of convex composite minimization problems which consists of minimizing the sum of two nonsmooth extended valued convex functions, with one which is composed with a linear map. Convergence rate guarantees for first order methods on this class of problems often require the additional assumption of Lipschitz continuity of the nonsmooth objective function composed with the linear map. We introduce a theoretical framework where the restrictive Lipschitz continuity of this function is not required. Building on a novel dual representation of the so-called Pasch-Hausdorff envelope, we derive an exact Lipshitz regularization for this class of problems. We then show how the aforementioned result can be utilized in establishing function values-based rates of convergence in terms of the original data. Throughout, we provide examples and applications which illustrate the potential benefits of our approach.