SDCA without Duality

Introduction

The following regularized loss minimization problem is associated with many machine learning methods:

As its name indicates, SDCA is derived by considering a dual problem. In this paper, we consider the possibility of applying SDCA for problems in which individual $\phi_{i}$ are non-convex, e.g., deep learning optimization problems. In many such cases, the dual problem is meaningless. Instead of directly using the dual problem, we describe and analyze a variant of SDCA in which only gradients of $\phi_{i}$ are being used (similar to option 5 in the pseudo code of Prox-SDCA given in ). Following , we show that SDCA is a variant of the Stochastic Gradient Descent (SGD), that is, its update is based on an unbiased estimate of the gradient. But, unlike the vanilla SGD, for SDCA the variance of the estimation of the gradient tends to zero as we converge to a minimum.

In recent years, many methods for optimizing regularized loss minimization problems have been proposed. For example, SAG , SVRG , Finito , SAGA , and S2GD . The best convergence rate is for accelerated SDCA . A systematic study of the convergence rate of the different methods under non-convex losses is left to future work.

SDCA without Duality

Dual-Free SDCA($P,T,\eta,\alpha^{(0)}$) Goal: Minimize $P(w)=\frac{1}{n}\sum_{i=1}^{n}\phi_{i}(w)+\frac{\lambda}{2}\|w\|^{2}$ Input: Objective $P$, number of iterations $T$, step size $\eta$ s.t. $\beta:=\eta\lambda n<1$, initial dual vectors $\alpha^{(0)}=(\alpha_{1}^{(0)},\ldots,\alpha_{n}^{(0)}$ Initialize: $w^{(0)}=\frac{1}{\lambda n}\sum_{i=1}^{n}\alpha_{i}^{(0)}$ For $t=1,\ldots,T$ Pick $i$ uniformly at random from $[n]$ Update: $\alpha_{i}^{(t)}=\alpha_{i}^{(t-1)}-\eta\lambda n\left(\nabla\phi_{i}(w^{(t-1)})+\alpha_{i}^{(t-1)}\right)$ Update: $w^{(t)}=w^{(t-1)}-\eta\left(\nabla\phi_{i}(w^{(t-1)})+\alpha_{i}^{(t-1)}\right)$

Observe that SDCA keeps the primal-dual relation

Observe also that the update of $\alpha$ can be rewritten as

namely, the new value of $\alpha_{i}$ is a convex combination of its old value and the negation of the gradient. Finally, observe that, conditioned on the value of $w^{(t-1)}$ and $\alpha^{(t-1)}$, we have that

That is, SDCA is in fact an instance of Stochastic Gradient Descent. As we will see in the analysis section below, the advantage of SDCA over a vanilla SGD algorithm is because the variance of the update goes to zero as we converge to an optimum.

Analysis

The theorem below provides a linear convergence rate for smooth and convex functions. The rate matches the analysis given in , but the analysis is simpler and does not rely on duality.

Assume that each $\phi_{i}$ is $L$-smooth and convex, and the algorithm is run with $\eta\leq\frac{1}{L+\lambda n}$. Let $w^{*}$ be the minimizer of $P(w)$ and let $\alpha^{*}_{i}=-\nabla\phi_{i}(w^{*})$. Then, for every $t\geq 1$,

In particular, setting $\eta=\frac{1}{L+\lambda n}$, then after

The theorem below provides a linear convergence rate for smooth functions, without assuming that individual $\phi_{i}$ are convex. We only require that the average of $\phi_{i}$ is convex. The dependence on $L/\lambda$ is worse in this case.

Assume that each $\phi_{i}$ is $L$-smooth and that the average function, $\frac{1}{n}\sum_{i=1}^{n}\phi_{i}$, is convex. Let $w^{*}$ be the minimizer of $P(w)$ and let $\alpha^{*}_{i}=-\nabla\phi_{i}(w^{*})$. Then, if we run SDCA with $\eta=\min\{\frac{\lambda}{2L^{2}}~{},~{}\frac{1}{2\lambda n}\}$, we have that

The advantage of SDCA over a generic SGD is that the variance of the update goes to zero as we converge to the optimum. To see this, observe that

Proofs

Observe that $0=\nabla P(w^{*})=\frac{1}{n}\sum_{i}\nabla\phi_{i}(w^{*})+\lambda w^{*}$, which implies that $w^{*}=\frac{1}{\lambda n}\sum_{i}\alpha_{i}^{*}$.

Define $u_{i}=-\nabla\phi_{i}(w^{(t-1)})$ and $v_{t}=-u_{i}+\alpha_{i}^{(t-1)}$. We also denote two potentials:

We will first analyze the evolution of $A_{t}$ and $B_{t}$. If on round $t$ we update using element $i$ then $\alpha_{i}^{(t)}=(1-\beta)\alpha_{i}^{(t-1)}+\beta u_{i}$, where $\beta=\eta\lambda n$. It follows that,

The proofs of Theorem 1 and Theorem 2 will follow by studying different combinations of $A_{t}$ and $B_{t}$.

The definition of $\eta$ implies that $\eta\leq\lambda(1-\beta)/L^{2}$, so the coefficient of $\|v_{t}\|^{2}$ is non-negative. By smoothness of each $\phi_{i}$ we have $\|u_{i}-\alpha_{i}^{*}\|^{2}=\|\nabla\phi_{i}(w^{(t-1)})-\nabla\phi_{i}(w^{*})\|^{2}\leq L^{2}\|w^{(t-1)}-w^{*}\|^{2}$. Therefore,

Using the strong convexity of $P$ we have $(w^{(t-1)}-w^{*})^{\top}\nabla P(w^{(t-1)})\geq P(w^{(t-1)})-P(w^{*})+\frac{\lambda}{2}\|w^{(t-1)}-w^{*}\|^{2}$ and $P(w^{(t-1)})-P(w^{*})\geq\frac{\lambda}{2}\|w^{(t-1)}-w^{*}\|^{2}$, which together yields $(w^{(t-1)}-w^{*})^{\top}\nabla P(w^{(t-1)})\geq\lambda\|w^{(t-1)}-w^{*}\|^{2}$. Therefore,

and repeating this recursively we end up with

which concludes the proof of the first part of Theorem 2. The second part follows by observing that $P$ is $(L+\lambda)$ smooth, which gives $P(w)-P(w^{*})\leq\frac{L+\lambda}{2}\|w-w^{*}\|^{2}$.

2 Proof of Theorem 1

In the proof of Theorem 1 we bounded the term $\|u_{i}-\alpha_{i}^{*}\|^{2}$ by $L^{2}\|w^{(t-1)}-w^{*}\|^{2}$ based on the smoothness of $\phi_{i}$. We now assume that $\phi_{i}$ is also convex, which enables to bound $\|u_{i}-\alpha_{i}^{*}\|^{2}$ based on the current sub-optimality.

Assume that each $\phi_{i}$ is $L$-smooth and convex. Then, for every $w$,

Clearly, since $\phi_{i}$ is $L$-smooth so is $g_{i}$. In addition, by convexity of $\phi_{i}$ we have $g_{i}(w)\geq 0$ for all $w$. It follows that $g_{i}$ is non-negative and smooth, and therefore, it is self-bounded (see Section 12.1.3 in ):

Using the definition of $g_{i}$, we obtain

where in the last inequality we used the assumption

References