to a given data matrix $A\in{\mathbb{R}}^{d\times n}$, and the functions $f : {\mathbb{R}}^d \rightarrow {\mathbb{R}}$ and $g : {\mathbb{R}}^n \rightarrow {\mathbb{R}}$ are allowed to be arbitrary closed convex functions. The functions $f^*,g^*$ in formulation  are defined as the *convex conjugates* of their corresponding counterparts $f,g$ in . Here ${\bm{x}}\in {\mathbb{R}}^n$ and ${\bm{w}}\in {\mathbb{R}}^d$ are the respective variable vectors. For a given function $h: {\mathbb{R}}^d\rightarrow {\mathbb{R}}$, its conjugate is defined as $$h^*({\bm{v}}) := \max_{{\bm{u}}\in{\mathbb{R}}^d} {\bm{v}}^\top {\bm{u}}- h({\bm{u}}) \, .$$ The association of problems and is a special case of Fenchel Duality. More precisely, the relationship is called *Fenchel-Rockafellar Duality* when incorporating the linear map $A$ as in our case, see e.g. [@Borwein:2005ge Theorem 4.4.2] or [@Bauschke:2011ik Proposition 15.18], see the Appendix \[app:primaldual\] for a self-contained derivation. The two main powerful features of this general duality structure are first that it includes many more machine learning methods than more traditional duality notions, and secondly that the two problems are fully symmetric, when changing respective roles of $f$ and $g$. In typical machine learning problems, the two parts typically play the roles of a data-fit (or loss) term as well as a regularization term. As we will see later, the two roles can 