Primal-Dual Rates and Certificates

Introduction

The massive growth of available data has moved data analysis and machine learning to center stage in many industrial as well as scientific fields, ranging from web and sensor data to astronomy, health science, and countless other applications. With the increasing size of datasets, machine learning methods are limited by the scalability of the underlying optimization algorithms to train these models, which has spurred significant research interest in recent years.

However, practitioners face a significant problem arising with the larger model complexity in large-scale machine learning and in particular deep-learning methods - it is increasingly hard to diagnose if the optimization algorithm used for training works well or not. With the optimization algorithms also becoming more complex (e.g., in a distributed setting), it can often be very hard to pin down if bad performance of a predictive model either comes from slow optimization, or from poor modeling choices. In this light, easily verifiable guarantees for the quality of an optimization algorithm are very useful — note that the optimum solution of the problem is unknown in most cases. For convex optimization problems, a primal-dual gap can serve as such a certificate. If available, the gap also serves as a useful stopping criterion for the optimizer.

So far, the majority of popular optimization algorithms for learning applications comes without a notion of primal-dual gap. In this paper, we aim to change this for a relevant class of machine learning problems. We propose a primal-dual framework which is algorithm-independent, and allows to equip existing algorithms with additional primal-dual certificates as an add-on.

Our approach is motivated by the recent analysis of SDCA (Shalev-Shwartz & Zhang, 2013). We extend their setting to the significantly larger class of convex optimization problems of the form

Contributions. The main contributions in this work can be summarized as follows:

Our new primal-dual framework is algorithm-independent, that is it allows users to equip existing algorithms with primal-dual certificates and convergence rates.

We introduce a new Lipschitzing trick allowing duality gaps (and thus accuracy certificates) which are globally defined, for a large class of convex problems which did not have this property so far. Our approach does not modify the original problems in the region of interest. In contrast to existing methods adding a small strongly-convex ($L_{2}$) term as, e.g., in (Shalev-Shwartz & Zhang, 2014; Zhang & Lin, 2015), our approach leaves both the algorithms and the optima unaffected.

Compared with the well-known duality setting of SDCA (Shalev-Shwartz & Zhang, 2013, 2014) which is restricted to strongly convex regularizers and finite sum optimization problems, our framework encompasses a significantly larger class of problems. We obtain new primal-dual convergence rates, e.g., for the Lasso as well as many $L_{1}$, Elastic Net, group Lasso and TV-regularized problems. The theory applies to any norm-regularized generalized linear model.

Existing primal-dual guarantees for the class of ERM problems with Lipschitz loss from (Shalev-Shwartz & Zhang, 2013) (e.g., SVM) are valid only for an “average” iteration. We show that the same rate of convergence can be achieved, e.g., for accelerated SDCA, but without the necessity of computing an average iterate.

Our primal-dual theory captures a more precise notion of data-dependency compared with existing results (which relied on per-coordinate information only). To be precise, our shown convergence rate for the general algorithms is dependent on the spectral norm of the data, see also (Takáč et al., 2013, 2015).

Related Work

Linearized ADMM solvers. For the problem structure of our interest here, one of the most natural algorithms is the splitting method known as the Chambolle-Pock algorithm (also known as Primal-Dual Hybrid Gradient, Arrow-Hurwicz method, or linearized ADMM) (Chambolle & Pock, 2010). While this algorithm can give rise to a duality gap, it is significantly less general compared to our framework. In each iteration, it requires a complete solution of the proximal operators of both $f$ and $g$, which can be computationally expensive. Its convergence rate is sensitive to the used step-size (Goldstein et al., 2015). Our framework is not algorithm-specific, and holds for arbitrary iterate sequences. More recently, the SPDC method (Zhang & Lin, 2015) was proposed as a coordinate-wise variant of (Chambolle & Pock, 2010), but only for strongly convex $g$.

Stochastic coordinate solvers. Coordinate descent/ascent methods have become state-of-the-art for many machine learning problems (Hsieh et al., 2008; Friedman et al., 2010). In recent years, theoretical convergence rate guarantees have been developed for the primal-only setting, e.g., by (Nesterov, 2012; Richtárik & Takáč, 2014), as well as more recently also for primal-dual guarantees, see, e.g., (Lacoste-Julien et al., 2013; Shalev-Shwartz & Zhang, 2013, 2014). The influential StochasticHere ’stochastic’ refers to randomized selection of the active coordinate. Dual Coordinate Ascent (SDCA) framework (Shalev-Shwartz & Zhang, 2013) was motivated by the $L_{2}$-regularized SVM, where coordinate descent is very efficient on the dual SVM formulation, with every iteration only requiring access to a single datapoint (i.e. a column of the matrix $A$ in our setup). In contrast to primal stochastic gradient descent (SGD) methods, the SDCA algorithm family is often preferred as it is free of learning-rate parameters, and has a fast linear (geometric) convergence rate. SDCA and recent extensions (Takáč et al., 2013; Shalev-Shwartz & Zhang, 2014; Qu et al., 2014; Shalev-Shwartz, 2015; Zhang & Lin, 2015) require $g$ to be strongly convex.

Under the weaker assumption of weak strong convexity (Necoara, 2015), a linear rate for the primal-dual convergence of SDCA was recently shown by (Ma et al., 2015b).

In the Lasso literature, a similar trend in terms of solvers has been observed recently, but with the roles of primal and dual problems reversed. For those problems, coordinate descent algorithms on the primal formulation have become the state-of-the-art, as in glmnet (Friedman et al., 2010) and extensions (Shalev-Shwartz & Tewari, 2011; Yuan et al., 2012, 2010). Despite the prototypes of both problem types—SVM for the $L_{2}$-regularized case and Lasso for the $L_{1}$-regularized case—being closely related (Jaggi, 2014), we are not aware of existing primal-dual guarantees for coordinate descent on unmodified $L_{1}$-regularized problems.

Comparison to smoothing techniques. Existing techniques for bringing $L_{1}$-regularized and related problems into a primal-dual setting compatible with SDCA do rely on the classical Nesterov-smoothing approach - By adding a small amount of $L_{2}$ to the part $g$, the objective becomes strongly convex; see, e.g., (Nesterov, 2005, 2012; Tran-Dinh & Cevher, 2014; Richtárik & Takáč, 2014; Shalev-Shwartz & Zhang, 2014). However, the appropriate strength of smoothing is difficult to tune. It will depend on the accuracy level, and will influence the chosen algorithm, as it will change the iterates, the resulting convergence rate as well as the tightness of the resulting duality gaps. The line of work of Tran-Dinh & Cevher (2014, 2015) provides duality gaps for smoothed problems and rates for proximally tractable objectives (Tran-Dinh & Cevher, 2015) and also objectives with efficient Fenchel-type operator (Yurtsever et al., 2015). In contrast, our approach preserves all solutions of the original $L_{1}$-optimization — it leaves the iterate sequences of existing algorithms unchanged, which is desirable in practice, and allows the reusability of existing solvers. We do not assume proximal or Fenchel tractability.

Distributed algorithms. For $L_{1}$-problems exceeding the memory capacity of a single computer, a communication-efficient distributed scheme leveraging this Lipschitzing trick is presented in (Smith et al., 2015; Forte, 2015).

Setup and Primal-Dual Structure

In this paper, we consider optimization problems of the following primal-dual structure. As we will see, the relationship between primal and dual objectives has many benefits, including computation of the duality gap, which allows us to have certificates for the approximation quality.

We consider the following pair of optimization problems, which are dualFor a self-contained derivation see Appendix C. to each other:

see, e.g. (Bauschke & Combettes, 2011, Proposition 19.18). The stated optimality conditions are equivalent to ${\boldsymbol{\alpha}},{\bf w}$ being a saddle-point of the Lagrangian, which is given as $\mathcal{L}({\boldsymbol{\alpha}},{\bf w})=f^{*}({\bf w})-\langle A{\boldsymbol{\alpha}},{\bf w}\rangle-g({\boldsymbol{\alpha}})$ if ${\boldsymbol{\alpha}}\in\operatorname{dom}(g)$ and ${\bf w}\in\operatorname{dom}(f^{*})$.

Duality Gap. From the definition of the dual problems in terms of the convex conjugates, we always have $\mathcal{P}({\bf w})\geq\mathcal{P}({\bf w}^{\star})\geq-\mathcal{D}({\boldsymbol{\alpha}}^{\star})\geq-\mathcal{D}({\boldsymbol{\alpha}})$, giving rise to the definition of the general duality gap $G({\bf w},{\boldsymbol{\alpha}}):=\mathcal{P}({\bf w})-(-\mathcal{D}({\boldsymbol{\alpha}}))$.

Under strong duality, we have $\mathcal{P}({\bf w}^{\star})=-\mathcal{D}({\boldsymbol{\alpha}}^{\star})$ and ${\bf w}({\boldsymbol{\alpha}}^{\star})={\bf w}^{\star}$, where ${\boldsymbol{\alpha}}^{\star}$ is an optimal solution of (A). This implies that the suboptimality $\mathcal{P}({\bf w}({\boldsymbol{\alpha}}))-\mathcal{P}({\bf w}^{\star})$ is always bounded above by the simpler duality gap function

which hence acts as a certificate of the approximation quality of the variable vector ${\boldsymbol{\alpha}}$.

Primal-Dual Guarantees for Any Algorithm Solving (A)

In this section we state an important lemma, which will later allow us to transform a suboptimality guarantee of any algorithm into a duality gap guarantee, for optimization problems of the form specified in the previous section.

Consider an optimization problem of the form (A). Let $f$ be $1/\beta$-smooth w.r.t. a norm $\|.\|_{f}$ and let $g$ be $\mu$-strongly convex with convexity parameter $\mu\geq 0$ w.r.t. a norm $\|.\|_{g}$. The general convex case $\mu=0$ is explicitly allowed, but only if $g$ has bounded support.

Then, for any ${\boldsymbol{\alpha}}\in\operatorname{dom}(\mathcal{D})$ and any $s\in$, it holds that

where $G({\boldsymbol{\alpha}})$ is the gap function defined in (4) and

We note that the improvement bound here bears similarity to the proof of (Bach, 2015, Prop 4.2) for the case of an extended Frank-Wolfe algorithm. In contrast, our result here is algorithm-independent, and leads to tighter results due to the more careful choice of ${\bf u}$, as we’ll see in the following.

In this section we assume that we are using an arbitrary optimization algorithm applied to problem (A). It is assumed that the algorithm produces a sequence of (possibly random) iterates $\{{\boldsymbol{\alpha}}^{(t)}\}_{t=0}^{\infty}$ such that there exists $C\in(0,1],D\geq 0$ such that

In the next two theorems, we define \sigma:=\big{(}\max_{{\boldsymbol{\alpha}}\neq 0}\|A{\boldsymbol{\alpha}}\|_{f}/\|{\boldsymbol{\alpha}}\|_{g}\big{)}^{2}, i.e., the squared spectral norm of the matrix $A$ in the Euclidean norm case.

Let us assume $g$ is $\mu$-strongly convex ($\mu>0$) (equivalently, its conjugate $g^{*}$ has Lipschitz continuous gradient with a constant $1/\mu$). The following theorem provides a linear convergence guarantee for any algorithm with given linear convergence rate for the suboptimality $\mathcal{D}({\boldsymbol{\alpha}})-\mathcal{D}({\boldsymbol{\alpha}}^{\star})$.

Assume the function $f$ is $1/\beta$-smooth w.r.t. a norm $\|.\|_{f}$ and $g$ is $\mu$-strongly convex w.r.t. a norm $\|.\|_{g}$. Suppose we are using a linearly convergent algorithm as specified in (7). Then, for any

In this section we will assume that $g^{*}$ is Lipschitz (in contrast to smooth as in Theorem 2) and show that the linear convergence rate is preserved.

Assume that the function $f$ is $1/\beta$-smooth w.r.t. a norm $\|.\|$, $g^{*}$ is $L$-Lipschitz continuous w.r.t the dual norm $\|.\|_{*}$, and we are using a linearly convergent algorithm (7). Then, for any

In (Wang & Lin, 2014), it was proven that feasible descent methods when applied to the dual of an SVM do improve the objective geometrically as in (7). Later, (Ma et al., 2015b) extended this to stochastic coordinate feasible descent algorithms (including SDCA). Using our new Theorem 3, we can therefore extend their results to linear convergence for the duality gap for the SVM application.

2 Sub-Linear Convergence Rates

In this case we will focus only on general $L$-Lipschitz continuous functions $g^{*}$ (if $g$ is strongly convex, then many existing algorithms are available and converge with a linear rate). We will assume that we are applying some (possibly randomized) algorithm on optimization problem (A) which produces a sequence (of possibly random) iterates $\{{\boldsymbol{\alpha}}^{(t)}\}_{t=0}^{\infty}$ such that

where $D(t)$ is a function wich has usually a linear or quadratic growth (i.e. $D(t)\sim\mathcal{O}(t)$ or $D(t)\sim\mathcal{O}(t^{2})$).

The following theorem will allow to equip existing algorithms with sub-linear convergence in suboptimality, as specified in (10), with duality gap convergence guarantees.

Assume the function $f$ is $1/\beta$-smooth w.r.t. the norm $\|.\|$, $g^{*}$ is $L$-Lipschitz continuous, w.r.t. the dual norm $\|.\|_{*}$, and we are using a sub-linearly convergent algorithm as quantified by (10). Then, for any $t\geq 0$ such that

Let us comment on Theorem 4 stated above. If $D(t)\sim\mathcal{O}(t)$ then this shows a rate of $\mathcal{O}{(\epsilon^{-2})}$. We note two important facts:

The guarantee holds for the duality gap of the iterate $\alpha^{(t)}$ and not for some averaged solution.

For the SVM case, this rate is consistent with the result of (Hush et al., 2006). Our result is much more general as it holds for any $L$-Lipschitz continuous convex function $g^{*}$ and any $\beta$-strongly convex $f^{*}$.

Extending Duality to Non-Lipschitz Functions

By definition, this function has bounded support, and hence, by Lemma 5, its conjugate function $\bar{g}^{*}$ is Lipschitz continuous.

Motivation. We will apply this trick to the part $g$ of optimization problems of the form (A) (such that $g^{*}$ will become Lipschitz). We want that this modification to have no impact on the outcome of any optimization algorithm running on (A). Instead, this trick should only affect convergence theory in that it allows us to present a strong primal-dual rate. In the following, we will discuss how this can indeed be achieved by imposing only very weak assumptions on the original problem (A).

The modification is based on the following duality of Lipschitzness and bounded support, as given in Lemma 5 below, which is a generalization of (Rockafellar, 1997, Corollary 13.3.3). We need the following definition:

Given a proper convex function $g$, it holds that $g$ has $L$-bounded support w.r.t. the norm $\|.\|$ if and only if $g^{*}$ is $L$-Lipschitz w.r.t. the dual norm $\|.\|_{*}$.

The following Theorem 6 generalizes our previous convergence results, which were restricted to Lipschitz $g^{*}$.

For an arbitrary optimization algorithm running on problem (A), let ${\boldsymbol{\alpha}}^{(t)}$ denote its iterate sequence. Assume there is some closed convex set $\mathcal{B}$ containing all these iterates. Then, the same optimization algorithm run on the modified problem — given by Lipschitzing of $g^{*}$ using $\mathcal{B}$ — would produce exactly the same iterate sequence. Furthermore, Theorem 3 as well as Theorem 4 give primal-dual convergence guarantees for this algorithm (for $L$ such that $\mathcal{B}$ is $L$-bounded).

Assume the objective of optimization problem (A) has bounded level sets. For ${\boldsymbol{\alpha}}^{(t)}$ being the iterate sequence of a monotone optimization algorithm on problem (A) we denote $\delta_{t}:=\mathcal{D}({\boldsymbol{\alpha}}^{(t)})$ and let $\mathcal{B}_{t}$ be the $\delta_{t}$-level set of $\mathcal{D}$. Write $B_{t}>0$ for a value such that $\mathcal{B}_{t}$ is $B_{t}$-bounded w.r.t. the norm $\|.\|$. Then, at any state $t$ of the algorithm, the set $\mathcal{B}_{t}$ contains all future iterates and Theorem 6 applies for $L:=B_{t}$.

2 Norm-Regularized Problems

We now focus on some applications. First, we demonstrate how the Lipschitzing trick can be applied to find primal-dual convergence rates for problems regularized by an arbitrary norm. We discuss in particular the Lasso problem and show how the suboptimality bound can be evaluated in practice. In a second part, we discuss the Elastic Net regularizer and show how it fits into our framework.

We consider a special structure of problem (A), namely

where $f$ is some convex non-negative smooth loss function regularized by any norm $\|.\|$. We choose $\mathcal{B}$ to be the $\|.\|$-norm ball of radius $B$, such that $\|{\boldsymbol{\alpha}}\|<B$ for every iterate. The size, $B$, of this ball can be controled by the amount of regularization $\lambda$. Using the Lipschitzing trick with this $\mathcal{B}$, the convergence guarantees of Theorem 6 apply to the general class of norm regularized problems.

Note that for any monotone algorithm (initialized at ${\bf 0}$) applied to (14) we have $\|{\boldsymbol{\alpha}}\|\leq\tfrac{1}{\lambda}f({\bf 0})$ for every iterate. Furthermore, at every iterate ${\boldsymbol{\alpha}}$ we can bound $\|{\boldsymbol{\alpha}}^{+}\|\leq\tfrac{1}{\lambda}(f(A{\boldsymbol{\alpha}})+\lambda\left\lVert{{\boldsymbol{\alpha}}}\right\rVert)$ for every future iterate ${\boldsymbol{\alpha}}^{+}$. Hence, $B:=\tfrac{1}{\lambda}f({\bf 0})$ is a safe choice, e.g. $B:=\tfrac{1}{2\lambda}\|{\bf b}\|_{2}^{2}$ for least squares loss and $B:=\tfrac{m}{\lambda}\log(2)$ for logistic regression loss.

Duality Gap. For any problem of the form (14) we can now determine the duality gap. We apply the Lipschitzing trick to $g({\boldsymbol{\alpha}}):=\lambda\|{\boldsymbol{\alpha}}\|$ as in (12), then the convex conjugate of $\bar{g}$ is

where $\|.\|_{*}$ denotes the dual norm of $\|.\|$. Hence, using the primal-dual mapping ${\bf w}({\boldsymbol{\alpha}}):=\nabla f(A{\boldsymbol{\alpha}})$ we can write the duality gap of the modified problem as

As an alternative, (Mairal, 2010, Sec. 1.4.1 and App. D.2) has defined a different duality gap by shrinking the dual ${\bf w}$ variable until it becomes feasible in $\|A^{\top}{\bf w}\|_{*}\leq\lambda$.

The results from the previous section can be ported to the important special case of $L_{1}$-regularization:

We choose $\mathcal{B}$ to be the $L_{1}$-norm ball of radius $B$ and then apply the Lipschitzing trick with $\mathcal{B}$ to the regularization term in (17). An illustration of this modification as well as the impact on its dual are illustrated in Figure 1. Hence, our theory (Theorem 6) gives primal-dual convergence guarantees for any algorithm applied to the Lasso problem (17). Furthermore, if the algorithm is monotone (initialized at ${\boldsymbol{\alpha}}:={\bf 0}$) we know that $\mathcal{B}$ is $\tfrac{1}{\lambda}f({\bf 0})$-bounded.

Duality Gap. The duality gap (16) for the modified Lasso problem can be computed at every iterate ${\boldsymbol{\alpha}}$ as

for ${\bf w}={\bf w}({\boldsymbol{\alpha}})$. For the derivation, see Appendix I.1.

Our algorithm-independent, primal-dual convergence guarantees and certificates presented so far are not restricted to $L_{p}$-regularized problems, but do in fact directly apply to many more general structured regularizers, some of them shown in see Table 1. This includes group Lasso ($L_{1}/L_{2}$) and other norms inducing structured sparsity (Bach et al., 2012), as well as other penalties such as e.g. the fused Lasso $g({\boldsymbol{\alpha}}):=\lambda\|M{\boldsymbol{\alpha}}\|_{1}$. The total variation denoising problem is obtained for suitable choice of the matrix $M$.

The second application we will discuss is Elastic Net regularization

for fixed trade-off parameter $\eta\in(0,1]$.

Duality Gap. For the Elastic Net problem (19) mapped to (A), we can compute the duality gap (4) as follows:

As $\eta\rightarrow 0$ we approach the pure $L_{1}$-case and this gap blows up as $G({\boldsymbol{\alpha}})\rightarrow\infty$. Comparing this to (18), we see that the Lipschitzing trick allows to get certificates even in cases where the duality gap of the unmodified problem is infinity.

Coordinate Descent Algorithms

We now focus on a very important class of algorithms, that is coordinate descent methods. In this section, we show how our theory implies much more general primal-dual convergence guarantees for coordinate descent algorithms.

We consider the coordinate descent algorithm described in Algorithm 1. Initialize ${\boldsymbol{\alpha}}^{(0)}={\bf 0}$ and then, at each iteration, sample and update a random coordinate $i\in[n]$ of the parameter vector ${\boldsymbol{\alpha}}$ to iteratively minimize (SA). Finally, after $T$ iterations output $\bar{\boldsymbol{\alpha}}$, the average vector over the latest $T-T_{0}$ iterates. The parameter $T_{0}$ is some positive number smaller than $T$.

As we will show in the following section, coordinate descent on $\mathcal{D}({\boldsymbol{\alpha}})$ is not only an efficient optimizer of the objective $\mathcal{D}({\boldsymbol{\alpha}})$, but also provably reduces the duality gap. Therefore, the same algorithm will simultaneously optimize the dual objective $\mathcal{P}({\bf w})$.

1 Primal-Dual Analysis for Coordinate Descent

We first show linear primal-dual convergence rate of Algorithm 1 applied to (SA) for strongly convex $g_{i}$. Later, we will generalize this result to also apply to the setting of general Lipschitz $g_{i}$. This generalization together with the Lipschitzing trick will allow us to derive primal-dual convergence guarantees of coordinate descent for a much broader class of problems, including the Lasso problem.

For the following theorems we assume that the columns of the data matrix $A$ are scaled such that $\|A_{:i}\|\leq R$ for all $i\in[n]$ and $\|A_{j:}\|\leq P$ for all $j\in[d]$, for some norm $\|.\|$.

Consider Algorithm 1 applied to (SA). Assume $f$ is a $1/\beta$-smooth function w.r.t. the norm $\|.\|$. Then, if $g_{i}$ is $\mu$-strongly convex for all $i$, it suffices to have a total number of iterations of

where $\epsilon_{D}^{(0)}$ is the initial suboptimality in $\mathcal{D}({\boldsymbol{\alpha}})$.

Theorem 8 allows us to upper bound the duality gap, and hence the suboptimality, for every iterate ${\boldsymbol{\alpha}}^{(T)}$, as well as the average $\bar{\boldsymbol{\alpha}}$ returned by Algorithm 1. In the following we generalize this result to apply to $L$-Lipschitz functions $g_{i}$.

Consider Algorithm 1 applied to (SA). Assume $f$ is a $1/\beta$-smooth function w.r.t. the norm $\|.\|$. Then, if $g_{i}^{*}$ is $L$-Lipschitz for all $i$, it suffices to have a total number of iterations of

Theorem 9 shows that for Lipschitz $g_{i}^{*}$, Algorithm 1 has $\mathcal{O}(\epsilon^{-1})$ convergence in the suboptimality and $\mathcal{O}(\epsilon^{-1})$ convergence in $G(\bar{\boldsymbol{\alpha}})$. Comparing this result to Theorem 4 which suggests $\mathcal{O}(\epsilon^{-2})$ convergence in $G({\boldsymbol{\alpha}})$ for $\mathcal{O}(\epsilon^{-1})$ convergent algorithms, we see that averaging the parameter vector crucially improves convergence in the case of non-smooth $f$.

Note that our Algorithm 1 recovers the widely used SDCA setting (Shalev-Shwartz & Zhang, 2013) as a special case, when we choose $f^{*}:=\frac{\lambda}{2}\|.\|_{2}^{2}$ in (SB). Furthermore, their convergence results for SDCA are consistent with our results and can be recovered as a special case of our analysis. See Corollaries 16, 18, 19 in Appendix J.

We now apply Algorithm 1 to the $L_{1}$-regularized problems, as well as Elastic Net regularized problems. We state improved primal-dual convergence rates which are more tailored to the coordinate-wise setting.

We specify the different parameters of Corollary 10 for least squares loss as well as the logistic regression loss (defined in Table 1). Both are $1$-smooth ($f^{*}$ is $1$-strongly convex) and we have $\beta:=1$. The initial suboptimality $\epsilon_{D}^{(0)}$ can be upper bounded by $\tfrac{1}{2}\|{\bf b}\|_{2}^{2}$ for the former and by $m\log(2)$ for the latter. For $B$ we choose $\frac{1}{\lambda}f({\bf 0})$.

iterations for coordinate descent on the primal (19) and

for coordinate descent on the dual of (19).

According to Corollary 11, the convergence rate is comparable for both scenarios. The constants however depend on the data matrix $A$ – for $d\gg n$ the primal version is beneficial, whereas for $n\gg d$ the dual version is leading.

Numerical Experiments

Here we illustrate the usefulness of our framework by showcasing it for two important applications, each one showing two algorithm examples for optimizing (A).

Lasso. The top row of Figure 2 shows the primal-dual convergence of Algorithm 1 (CD) as well as the accelerated variant of CD (APPROX, Fercoq & Richtárik (2015)), both applied to the Lasso problem (A). We have applies the Lipschitzing trick as described in Section 5.1. This makes sure that ${\bf w}({\boldsymbol{\alpha}})$ will be always feasible for the modified dual (B), and hence the duality gap can be evaluated.

SVM. It was shown in (Shalev-Shwartz & Zhang, 2013) that if CD (SDCA) is run on the dual SVM formulation, and we consider an ”average” solution (over last few iterates), then the duality gap evaluated at averaged iterates has a sub-linear convergence rate $\mathcal{O}(1/t)$. As a consequence of Theorem 4, we have that the APPROX algorithm (Fercoq & Richtárik, 2015) will provide the same sub-linear convergence in duality gap, but holding for the iterates themselves, not only for an average. On the bottom row of Figure 2 we compare CD with its accelerated variant on two benchmark datasets.Available from csie.ntu.edu.tw/$\sim$cjlin/libsvmtools/datasets. We have chosen $\lambda=1/n$.

Conclusions

We have presented a general framework allowing to equip existing optimization algorithms with primal-dual certificates. For future research, it will be interesting to study more applications and algorithms fitting into the studied problem structure, including more cases of structured sparsity, and generalizations to matrix problems.

We thank Francis Bach, Michael P. Friedlander, Ching-pei Lee, Dmytro Perekrestenko, Aaditya Ramdas, Virginia Smith and an anonymous reviewer for fruitful discussions.

References

Appendix

And analogously if the same holds for all subgradients, in the case of a general closed convex function $h$.

Appendix B Convex Conjugates

We recall some basic properties of convex conjugates, which we use in the paper.

Some useful properties, see (Boyd & Vandenberghe, 2004, Section 3.3.2):

Double conjugate: $(f^{*})^{*}=f$ if $f$ is closed and convex.

Value Scaling: (for $\alpha>0$) $f({\bf v})=\alpha g({\bf v})\qquad\Rightarrow\qquad f^{*}({\bf w})=\alpha g^{*}({\bf w}/\alpha)\,.$

Argument Scaling: (for $\alpha\neq 0$) $f({\bf v})=g(\alpha{\bf v})\qquad\Rightarrow\qquad f^{*}({\bf w})=g^{*}({\bf w}/\alpha)\,.$

Conjugate of a separable sum: $f({\bf v})=\sum_{i}\phi_{i}(v_{i})\qquad\Rightarrow\qquad f^{*}({\bf w})=\sum_{i}\phi_{i}^{*}(w_{i})\,.$

Given a proper convex function $g$, it holds that $g$ has $L$-bounded support w.r.t. the norm $\|.\|$ if and only if $g^{*}$ is $L$-Lipschitz w.r.t. the dual norm $\|.\|_{*}$.

Given a closed convex function $f$, it holds that $f$ is $\mu$-strongly convex w.r.t. the norm $\|.\|$ if and only if $f^{*}$ is $(1/{\mu})$-smooth w.r.t. the dual norm $\|.\|_{*}$.

The conjugate of a norm is the indicator function of the unit ball of the dual norm.

(Boyd & Vandenberghe, 2004, Examples 3.24 and 3.26) ∎

Appendix C Primal-Dual Relationship

The relation of the primal and dual problems (A) and (B) is a special case of the concept of Fenchel Duality. Using the combination with the linear map $A$ as in our case, the relationship is called Fenchel-Rockafellar Duality, see, e.g., (Borwein & Zhu, 2005, Theorem 4.4.2) or (Bauschke & Combettes, 2011, Proposition 15.18).

For completeness, we here illustrate this correspondence with a self-contained derivation of the duality.

Introducing dual variables ${\bf w}=[w_{1},\dots,w_{d}]$, the Lagrangian is given by:

The dual problem follows by taking the infimum with respect to ${\boldsymbol{\alpha}}$ and ${\bf v}$:

We change signs and turn the maximization of the dual problem (26) into a minimization and thus we arrive at the dual formulation $\eqref{eq:B}$ as claimed:

Appendix D Proof of Lemma 1

The proof is partially motivated by proofs in (Ma et al., 2015a; Shalev-Shwartz & Zhang, 2013) but come with some crucial unique steps and tricks.

Here we have chosen $\Delta{\boldsymbol{\alpha}}:=s({\bf u}-{\boldsymbol{\alpha}})$ with ${\bf u}$ defined as in (6) and some $s\in$. Note that for ${\bf u}$ to be well defined, i.e., the subgradient in (6) not to be empty, we need the domain of $g^{*}$ to be the whole space. For $\mu>0$ this is given by strong convexity of $g$, while for $\mu=0$ this follows from the bounded support assumption on $g$. (For the duality of Lipschitzness and bounded support, see our Lemma 5).

Now, we will use a strong convexity property of a function $g$ w.r.t. $\|.\|_{g}$ to obtain

Now let us examine the relation of the equation above with duality gap. Therefore we use the definition of the optimization problems (A) and (B), and the definition of the convex conjugates to write the duality gap as:

where we have used the mapping ${\bf w}({\boldsymbol{\alpha}})=\nabla f(A{\boldsymbol{\alpha}})$.

Now, let us analyze the expression $\Lambda$ from (29). We have

Now, using the convex conjugate maximal property and (6) we have

Plugging (32), (30) and (31) into (29) gives us

Appendix E Proof of Theorem 2

Let us upper bound the second term in (5) as given in the main Lemma 1. Recall the definition of the data complexity parameter \sigma:=\big{(}\max_{{\boldsymbol{\alpha}}\neq 0}\|A{\boldsymbol{\alpha}}\|_{f}/\|{\boldsymbol{\alpha}}\|_{g}\big{)}^{2}. We have

Now, if we choose $s=\frac{\mu}{\frac{\sigma}{\beta}+\mu}$ then this term vanishes, and therefore

After multiplying the equation above by $\frac{\frac{\sigma}{\beta}+\mu}{\mu}$ and requiring RHS to be $\leq\epsilon$ we will get

and our claimed convergence bound (8) follows. ∎

Appendix F Proof of Theorem 3

From Lemma 1 and the definition of $\sigma$ we have that

Now using Lemma 5, because $g^{*}$ is $L$-Lipschitz w.r.t. the norm $\|.\|_{*}$, we have that $g$ is $L$-bounded w.r.t. the norm $\|.\|=\|.\|_{g}=\|.\|_{f}$ and hence for ${\boldsymbol{\alpha}}\in\operatorname{dom}(g)$ we obtain $\|{\boldsymbol{\alpha}}\|<L$. From the standard characterization of Lipschitzness as by bounded subgradient norm (see e.g. (Shalev-Shwartz, 2011, Lemma 2.6) or other references) we have for any ${\bf u}\in\partial g^{*}({\bf x})$ that $\|{\bf u}\|\leq L$, and hence for any ${\bf u},{\boldsymbol{\alpha}}$ we must have $\|{\bf u}-{\boldsymbol{\alpha}}\|^{2}\leq 2L^{2}$ by the triangle inequality.

Now, let us choose $\bar{s}=\min\{1,\frac{\epsilon\beta}{2\sigma L^{2}}\}$. To have the RHS of (34) $\leq\frac{\epsilon}{2}$ it is enough to choose

and the claimed convergence bound (9) follows. ∎

Appendix G Proof of Theorem 4

Using Lemma 1 and the bound $\|{\bf u}-{\boldsymbol{\alpha}}\|^{2}\leq 2L^{2}$ derived in the previous section, we have that

Now, by choosing $s=\sqrt{\frac{C}{D(t)}\frac{2\beta}{\sigma L^{2}}}\overset{\eqref{eq:asfdwafeawf}}{\in}$ we obtain that

We see that the assumption (11) guarantees that the RHS of the above inequality becomes $\leq\epsilon$, as claimed. ∎

We note that in the special case of constrained optimization, motivated by the Frank-Wolfe algorithm, (Lacoste-Julien & Jaggi, 2015, Theorem 2) has shown another algorithm-independent bound for the convergence in duality gap, also requiring order of $1/\epsilon^{2}$ steps to reach accuracy $\epsilon$. On the other hand, for the algorithm-specific result by (Bach, 2015, Prop 4.2) for the case of an extended Frank-Wolfe algorithm, $1/\epsilon$ steps are shown to be sufficient.

Appendix H Proof of Lemma 5

Lemma 5 generalizes the result of (Rockafellar, 1997, Corollary 13.3.3) from the $L_{2}$-norm to a general norm $\|.\|$. It can be equivalently formulated as follows:

We follow the line of proof in (Rockafellar, 1997).

It can be assumed that $f$ is closed, as $f$ and its closure $cl(f)$ have the same conjugate, and the Lipschitz condition is satisfied by $f$ if and only if it is satisfied by $cl(f)$. Note that from (Rockafellar, 1997, Theorem 13.3) we know

is the support function of $\operatorname{dom}(f^{*})$. Further, from (Rockafellar, 1997, Theorem 10.5) we know: $\operatorname{dom}(f^{*})$ is bounded if and only if $f0^{+}$ is finite everywhere. In more detail, the Lipschitz condition on $f$, choosing ${\bf z}={\bf x}+{\bf y}$, is equivalent to having

and by definition (37) of $f0^{+}$ this is equivalent to

Note that $g({\bf y}):=L\|{\bf y}\|$ is a finite positively homogenous convex function, we know by (Rockafellar, 1997, Corollary 13.2.2) that it is the support function of a non-empty bounded convex set. Call this set $\mathcal{S}$. We will later show that $\mathcal{S}=L\mathcal{B}$ where $\mathcal{B}$ is the $\|.\|_{*}$-norm ball. Hence $f0^{+}({\bf y})\leq g$ means $cl(\operatorname{dom}f^{*})\subset\mathcal{S}$, as $f0^{+}$ is the support function of $\operatorname{dom}(f^{*})$. And this shows that the Lipschitz condition holds for some $L$ if and only if ${\bf x}^{\star}\in\mathcal{S}\;\;\forall{\bf x}^{\star}\in\operatorname{dom}(f^{*})$ and hence $\|{\bf x}^{\star}\|_{*}\leq L$ and $f^{*}$ is $L$-bounded for every ${\bf x}^{\star}\in\operatorname{dom}(f^{*})$. It remains to show that $g=L\|{\bf y}\|$ is the support function of $\mathcal{S}=L\mathcal{B}$: The support function of a set $\mathcal{C}$ is defined as

By the definition of the dual norm we find

and hence $g$ is the support function of the set $\mathcal{S}:=\{{\bf x}:\|{\bf x}\|_{*}\leq L\}=L\mathcal{B}$. ∎

Appendix I Duality Gaps

Consider the Lasso problem given in (17), which we directly map to our primal optimization problem (A). We use the $L_{1}$-norm ball of radius $B$ to apply the Lipschitzing trick, i.e. $\mathcal{B}:=\left\{{\bf x}:\|{\bf x}\|_{1}\leq B\right\}$ and modify the $L_{1}$ norm term $g({\boldsymbol{\alpha}}):=\lambda\|{\boldsymbol{\alpha}}\|_{1}$ as suggested in (12). The convex conjugate hence becomes:

and using the optimality condition (1a) the gap follows immediately as

where we used the first-order optimality $f^{*}({\bf w}({\boldsymbol{\alpha}}))=\langle{\bf w}({\boldsymbol{\alpha}}),A{\boldsymbol{\alpha}}\rangle-f(A{\boldsymbol{\alpha}})$ by definition of ${\bf w}({\boldsymbol{\alpha}})$.

It remains to consider the non zero part, where $\|{\bf u}\|_{\infty}>\lambda$. Lets consider the optimization

Assume the largest element of ${\bf u}$ is at index $i$ and we know $[{\bf u}]_{i}>\lambda$, hence the maximizing ${\boldsymbol{\alpha}}$ in $\{{\boldsymbol{\alpha}}:\|{\boldsymbol{\alpha}}\|_{1}\leq B\}$ is the vector with a single entry of value $B$ at position $i$, and (38) follows. ∎

I.2 Duality Gap for Elastic Net Regularized Problems

Consider the Elastic Net regularized problem formulation (19). The conjugate dual of the Elastic Net regularizer is given in Lemma 20. We first map (19) to (A), as suggested in row 2 of Table 1. Then its dual counterpart (B) is given by:

Appendix J Convergence Results for Coordinate Descent

For the proof of Theorem 8 and 9 and we will need the following Lemma, which we will prove below in Section J.3. This lemma allows us to lower bound the expected per-step improvement in terms of $\mathcal{D}$ for coordinate descent algorithms on $\mathcal{D}$.

Consider problem formulation (SB) and (SA). Let $f$ be $1/\beta$-smooth w.r.t. a norm $\|.\|$. Further, let $g_{i}$ be $\mu$-strongly convex with convexity parameter $\mu\geq 0$ $\forall i\in[n]$. For the case $\mu=0$ we need the additional assumption of $g_{i}$ having bounded support. Then for any iteration $t$ and any $s\in$, it holds that

and $u_{i}^{(t-1)}\in\partial g_{i}^{*}(-A_{:i}^{\top}{\bf w}({\boldsymbol{\alpha}}^{(t-1)}))$. The expectations are with respect to the random choice of coordinate $i$ in step $t$.

For the following, we again assume that the columns of the data matrix $A$ are scaled such that $\|A_{:i}\|\leq R$ for all $i\in[n]$ and $\|A_{j:}\|\leq P$ for all $j\in[d]$ and some norm $\|.\|$.

Consider Algorithm 1 applied to (SA). Assume $f$ is a $1/\beta$-smooth function w.r.t. the norm $\|.\|$. Then, if $g_{i}$ is $\mu$-strongly convex for all $i$, it suffices to have a total number of iterations of

where $\epsilon_{D}^{(0)}$ is the initial suboptimality in $\mathcal{D}({\boldsymbol{\alpha}})$.

The proof of this theorem is motivated by proofs in (Shalev-Shwartz & Zhang, 2013) but generalizing their result in (Shalev-Shwartz & Zhang, 2013, Theorem 5). To prove Theorem 8 we apply Lemma 15 with $s=\frac{\mu\beta}{R^{2}+\mu\beta}\in$. This choice of $s$ implies $F^{(t)}\leq 0\;\;\forall t$ as defined in (41). Hence,

Here expectations are over the choice of coordinate $i$ in step $t$, conditioned on the past state at $t-1$. Let $\epsilon_{D}^{(t)}$ denote the suboptimality $\epsilon_{D}^{(t)}:=D({\boldsymbol{\alpha}}^{(t)})-D({\boldsymbol{\alpha}}^{\star})$. As $\epsilon_{D}^{(t-1)}\leq P({\bf w}^{(t-1)})+D({\boldsymbol{\alpha}}^{(t-1)})$ and $D({\boldsymbol{\alpha}}^{(t-1)})-D({\boldsymbol{\alpha}}^{(t)})=\epsilon_{D}^{(t-1)}-\epsilon_{D}^{(t)}$, we obtain

And towards obtaining small duality gap as well, we observe that at all times

This proves the first part of Theorem 8 and the second part follows immediately if we sum (42) over $t=T_{0},...,T-1$. ∎

From Theorem 8 it follows that for $T=2T_{0}$ and $T_{0}\geq n+\frac{nR^{2}}{\mu\beta}$ we need

We recover Theorem 5 of (Shalev-Shwartz & Zhang, 2013) as a special case of our Theorem 8. We consider their optimization objectives, namely

where ${\bf x}_{i}$ are the columns of the data matrix $X$. We assume that $\Phi_{i}^{*}({\boldsymbol{\alpha}})$ is $\gamma$-strongly convex for $i\in[n]$. We scale the columns of $X$ such that $\|{\bf x}_{i}\|\leq 1$. Hence, we find that

We consider (43) and (44) as a special case of the separable problems (SA) and (SB). We set $g_{i}(\alpha):=\frac{1}{n}\Phi_{i}^{*}(-\alpha)$ and $f^{*}({\bf w}):=\frac{\lambda}{2}\|{\bf w}\|^{2}$. In this case $\mu:=\frac{1}{n}\gamma$ and $\beta:=\lambda$. Defining $A:=\frac{1}{n}X$ and using the assumption $\|{\bf x}_{i}\|\leq 1$ we have $R:=\frac{1}{n}$ and using $\Phi_{i}(0)\leq 1$ we have $\epsilon_{D}^{(0)}\leq 1$and applying Theorem 8 to this setting concludes the proof. ∎

J.2 Proof of Theorem 9

This theorem generalizes the results of (Shalev-Shwartz & Zhang, 2013, Theorem 2).

Consider Algorithm 1 applied to (SA). Assume $f$ is a $1/\beta$-smooth function w.r.t. the norm $\|.\|$. Then, if $g_{i}^{*}$ is $L$-Lipschitz for all $i$, it suffices to have a total number of iterations of

Suppose that for all $i$, $g_{i}^{*}$ is $L$-Lipschitz. Let $F^{(t)}$ be as defined in Lemma 15 (with $\mu=0$) and assume $\|A_{:i}\|\leq R\;\;\;\forall i$. Then, $F^{(t)}\leq\frac{4L^{2}}{\beta}R^{2}\>\>\forall t$.

We apply the duality of Lipschitzness and bounded support (Lemma 5) to the case of univariate functions $g_{i}$. The assumption of $g_{i}^{*}$ being $L$-Lipschitz therefore gives that $g_{i}$ has $L$-bounded support, and so $|\alpha_{i}|\leq L$ for $\alpha_{i}$ as defined in (41).

Furthermore for $u_{i}$, by the equivalence of Lipschitzness and bounded subgradient (see e.g. (Shalev-Shwartz, 2011, Lemma 2.6)) we have $|u_{i}|\leq L$ and thus, $|\alpha_{i}-u_{i}|^{2}\leq 4L^{2}$. Together with $\|A_{:i}\|\leq R$ the claimed bound on $F^{(t)}$ follows. ∎

In the case of Lasso we have $g_{i}(\alpha_{i})=\lambda|\alpha_{i}|$. Using the Lipschitzing trick, we replace $g_{i}(\cdot)$ by

which has $B$-bounded support. Hence, its conjugate

is $B$-Lipschitz and Lemma 5 and Lemma 17 apply with $L:=B$.

Now, to prove Theorem 9, let $F=\max_{t}F^{(t)}$ and recall that by Lemma 17 we can upper bound $F$ by $\frac{4L^{2}}{\beta}R^{2}$.

Furthermore, our main Lemma 15 on the improvement per step tells us that

With $\epsilon_{D}^{(t)}=D({\boldsymbol{\alpha}}^{(t)})-D({\boldsymbol{\alpha}}^{\star})\leq G({\boldsymbol{\alpha}}^{(t)})$ and $D({\boldsymbol{\alpha}}^{(t)})-D({\boldsymbol{\alpha}}^{(t-1)})=\epsilon_{D}^{(t-1)}-\epsilon_{D}^{(t)}$, this implies

Expectations again only being over the choice of $i$ in steps $t$. We next show that this inequality can be used to bound the suboptimality as

for $t\geq t_{0}=\max\left\{0,n\log\left(\frac{2\epsilon_{D}^{(0)}}{Fn}\right)\right\}$. Indeed, let us choose $s:=1$. Then at $t=t_{0}$, we have

For $t>t_{0}$ we use an inductive argument. Suppose the claim holds for $t-1$, therefore

choosing $s=\frac{2n}{2n+t-1-t_{0}}\in$ yields

This proves the bound (46) on the suboptimality. To get a result on the duality gap we sum (45) over the interval $t=T_{0}+1,...,T$ and obtain

Now if we choose $\bar{\bf w},\bar{\boldsymbol{\alpha}}$ to be the average vectors over $t\in\{T_{0}+1,T\}$, then the above implies

If $T\geq n+T_{0}$ and $T_{0}\geq t_{0}$, we can set $s=n/(T-T_{0})$ and combining this with (46) we obtain

Using Lemma 17 we can bound the total number of required iterations to reach a duality gap of $\epsilon$ by

which concludes the proof of Theorem 9. ∎

We recover Theorem 2 of (Shalev-Shwartz & Zhang, 2013) as a special case of our Theorem 9. We consider the optimization objectives in (43) and (44). We assume that $\Phi_{i}({\boldsymbol{\alpha}})$ is $M$-Lipschitz for $i\in[n]$ and $\Phi_{i}(0)\leq 1$. We scale the columns of $X$ such that $\|{\bf x}_{i}\|\leq 1$. Hence, we find that

We consider (43) and (44) as a special case (SB) and (SA). We set $g_{i}(\alpha):=\frac{1}{n}\Phi_{i}^{*}(-\alpha)$ and $f^{*}({\bf w}):=\frac{\lambda}{2}\|{\bf w}\|^{2}$. Hence, $g_{i}^{*}({\bf w}^{\top}{\bf a}_{i})=\tfrac{1}{n}\Phi_{i}(-n{\bf w}^{\top}{\bf a}_{i})$ is $M$-Lipschitz and we set $L:=M$ and $\beta:=\lambda$. We further use Lemma (Shalev-Shwartz & Zhang, 2013, Lemma 20) with $\Phi_{i}(0)\leq 1$ to bound the primal suboptimality as $\epsilon_{D}^{(0)}\leq 1$. Finally, by the assumption $\|{\bf x}_{i}\|\leq 1$ and the definition $A:=\frac{1}{n}X$ we have $R:=\frac{1}{n}$ and applying Theorem 9 to this setting concludes the proof. ∎

J.3 Proof of Lemma 15

The proof of Lemma 15 is motivated by the proof of (Shalev-Shwartz & Zhang, 2013, Lemma 19) but we adapt it to apply to a much more general setting. First note that the one step improvement in the dual objective can be written as

Note that in a single step of SDCA ${\boldsymbol{\alpha}}^{(t-1)}\rightarrow{\boldsymbol{\alpha}}^{(t)}$ only one dual coordinate is changed. Without loss of generality we assume this coordinate to be $i$. Writing ${\bf v}({\boldsymbol{\alpha}})=A{\boldsymbol{\alpha}}$, we find

In the following, let us denote the columns of the matrix $A$ by ${\bf a}_{i}$ for $i\in[n]$ for reasons of readability. Then, by definition of the update we have for all $s\in$:

where we chose $\Delta\alpha_{i}=s(u_{i}^{(t-1)}-\alpha_{i}^{(t-1)})$ with $-u_{i}^{(t-1)}\in\partial g_{i}^{*}({\bf a}_{i}^{\top}{\bf w}^{(t-1)})$ for $s\in$. As in Section D, in order for ${\bf u}$ to be well-defined, we again need the assumption on $g$ to be strongly convex ($\mu>0$), or to have bounded support. Using $\mu$-strong convexity of $g_{i}$, namely

We further note that from the optimality condition (1a) we have ${\bf w}({\boldsymbol{\alpha}})=\nabla f({\bf v}({\boldsymbol{\alpha}}))$ and rearranging terms yields:

Using this inequality to bound $\mathcal{D}({\boldsymbol{\alpha}}^{(t-1)})-\mathcal{D}({\boldsymbol{\alpha}}^{(t)})=(\Gamma)-(\Lambda)$ yields:

Note that for $(i)$ we used the optimality condition (2b) which translates to $u\in\partial g^{*}(-{\bf a}_{i}^{\top}{\bf w})$ and yields $g(u)=-u{\bf a}_{i}^{\top}{\bf w}-g^{*}(-{\bf a}_{i}^{\top}{\bf w})$. Similarly, by again exploiting the primal-dual optimality condition we have $f^{*}(\nabla f({\bf v}))={\bf v}^{\top}\nabla f({\bf v})-f({\bf v})$ and hence we can write the duality gap as:

using this we can write the expectation of (J.3) with respect to $i$ as

For the expectation being over the choice of coordinate $i$ in step $t$. ∎

We recover Lemma 19 of (Shalev-Shwartz & Zhang, 2013) as a special case of our Lemma 15. We consider their pair of primal and dual optimization objectives, (43) and (44) where ${\bf x}_{i}$ are the columns of the data matrix $X$. Assume that $\Phi^{*}_{i}$ is $\gamma$-strongly convex for $i\in[n]$, where we allow $\gamma=0$. Then, for any $t$, any $s\in$ and $-\hat{u}_{i}^{(t-1)}\in\partial\Phi_{i}({\bf x}_{i}^{\top}{\bf w}({\boldsymbol{\alpha}}^{(t-1)}))$ we have

We set $g_{i}({\boldsymbol{\alpha}}):=\frac{1}{n}\Phi_{i}^{*}(-{\boldsymbol{\alpha}})$ and $f^{*}({\bf w}):=\frac{\lambda}{2}\|{\bf w}\|^{2}$. From the definition of strong convexity it immediately follows that $\mu=\frac{\gamma}{n}$ and $\beta=\lambda$. As our algorithm works for any data matrix $A$, we choose $A:=\frac{1}{n}X$ and scale the input vectors ${\bf x}_{i}$, i.e. ${\bf a}_{i}=\frac{{\bf x}_{i}}{n}$ before we feed ${\bf a}_{i}$ into the algorithm. To conclude the proof we apply Lemma 15 to this setting and observe that

which yields $\hat{u}_{i}^{(t-1)}=-nu_{i}^{(t-1)}$. Further note that the conjugate of $f^{*}$ is given by $f({\bf v})=\frac{\lambda}{2}\left\|\frac{{\bf v}}{\lambda}\right\|^{2}$ and this leads to the dual-to-primal mapping

Appendix K Some Useful Pairs of Conjugate Functions

For $\eta\in(0,1]$, the Elastic Net function $g_{i}(\alpha):=\frac{\eta}{2}\alpha^{2}+(1-\eta)|\alpha|$ has the convex conjugate

where $[.]_{+}$ is the positive part operator, $[s]_{+}=s$ for $s>0$, and zero otherwise. Furthermore, this $g_{i}^{*}$ is $1/\eta$-smooth.

We start by applying the definition of convex conjugate, that is:

We now distinguish two cases for the optimal: $\alpha^{\star}\geq 0$, $\alpha^{\star}<0$. For the first case we get that

Setting the derivative to we get $\alpha^{\star}=\frac{x-(1-\eta)}{\eta}$. To satisfy $\alpha^{\star}\geq 0$, we must have $x\geq 1-\eta$. Replacing with $\alpha^{\star}$ we thus get:

Similarly we can show that for $x\leq-(1-\eta)$

See, e.g. (Boyd & Vandenberghe, 2004, Example 3.26).

The logistic classifier loss function $f$ is given as

with the box constraint $-w_{j}b_{j}\in$.

Furthermore, $f^{*}({\bf w})$ is $1$-strongly convex over its domain if the labels satisfy $b_{j}\in$.

See e.g. (Smith et al., 2015) or (Shalev-Shwartz & Zhang, 2013). ∎

Appendix L More Numerical Experiments