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 Lipschitz 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.
This is a joint work with Marc Teboulle