A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method

Introduction

We consider a strongly convex function $f$ defined on a convex set $K$. We denote by $\mu$ its strong convexity constant. Following , we consider a stochastic approximation scenario where only unbiased estimates of subgradients of $f$ are available, with the projected stochastic subgradient method.

More precisely, we assume that we have an increasing sequence of $\sigma$-fields $(\mathcal{F}_{t})_{t\geqslant 0}$, such that $w_{0}\in K$ is $\mathcal{F}_{0}$-measurable and such that for all $t\geqslant 1$,

$\Pi_{K}$ is the orthogonal projection on $K$,

We denote by $w^{\ast}$ the unique minimizer of $f$ on $K$.

Motivating example

Convergence analysis

Following standard proof techniques , we have:

The last inequality is obtained from the $\mu$-strong convexity of $f$. Thus, by re-arranging the function values on the LHS and taking expectations on both sides, we get:

With $\displaystyle\gamma_{t}=\frac{1}{\mu t}$, then inequality (2) becomes

and by summing from $t=1$ to $t=T$, we obtain:

2 New analysis

With $\displaystyle\gamma_{t}=\frac{2}{\mu(t+1)}$ and multiplying inequality (2) by $t$, we obtain:

By summing from $t=1$ to $t=T$ these $t$-weighted inequalities, we obtain a similar telescoping sum, but this time the term with $B^{2}$ stays constant across the sum:

So by using the weighted average $\bar{w}_{T}\doteq\frac{2}{(T+1)(T+2)}\sum_{t=0}^{T}(t+1)w_{t}$ instead of a uniform average, we get a $O(\frac{1}{T})$ rate instead of $O(\frac{\log T}{T})$. Note that these averaging schemes are efficiently implemented in an online fashion as:

For the proposed weighted averaging scheme, $\rho_{t}=2/(t+2)$ (compare with $\rho_{t}=1/(t+1)$ for the uniform averaging scheme).

Experiments

To test the empirical performance of the averaging scheme, we performed a series of experiments using the support vector machine optimization problem

where $x_{i}$ is in an Euclidean space and $y_{i}\in\{-1,1\}$.

We performed experiments on a set of freely available benchmark binary classification data sets. The quantum ($n=50000$, $p=78$) and protein ($n=145751$, $p=74$) data sets were obtained from the KDD Cup 2004 website,http://osmot.cs.cornell.edu/kddcup the sido data set ($n=12678$, $p=4932$) was obtained from the Causality Workbench website,http://www.causality.inf.ethz.ch/home.php while the rcv1 ($n=20242$, $p=47236$), covertype ($n=581012$, $p=54$), and news ($n=19996$, $p=1355191$) data sets were obtained from the LIBSVM data website.http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets We added a (regularized) bias term to all data sets, and for dense features we standardized so that they would have a mean of zero and a variance of one. We set the regularization parameter $\lambda$ to $1/n$, although we found that the relative performance of the methods was not particularly sensitive to this choice. We didn’t use any projection ($K$ is the whole space). Our experiments compared the following averaging strategies:

1: Averaging all iterates with uniform weight.

0.5: Averaging the second half of the iterates with uniform weight, as proposed in .

D: Averaging all iterates since the last iteration that was a power of 2 with uniform weight (the ‘doubling trick’), also proposed in .

W: Averaging all iterates with a weight of $t+1$, as discussed in this note.

W2: Averaging all iterates with a weight of $(t+1)^{2}$, which puts even further emphasis on recent iterations.

We plot the performance of these different averaging strategies in Figure 1, which shows the objective function against the number of effective passes through the data (the number of iterations divided by $n$). This figure uses a step size of $1/\mu t$ for all methods as we found this gave better performance than a step size of $2/\mu(t+1)$, although we include the performance of W with the latter step-size for comparison. In Figure 1, we observe the following trends:

0: Not averaging at all is typically among the worst strategies. However, this proved to be the best strategy on the sido data set. This may be because the method is still far from the solution after $50$ passes through the data.

1: Uniform averaging of all iterates is always the worst strategy.

0.5: Uniform averaging of the second half of the iterates is typically among the best strategies, provided we are in fact in the second half of the iterates.

D: The doubling trick typically gave among the best performance across the methods.

W: The proposed weighting typically performed between the doubling trick and not averaging.

W2: Weighting the iterates by $(t+1)^{2}$ always outperformed weighting them by $t+1$.

Discussion

We note that the averaging of linear approximations of $f$ (rather than the iterates) by $t+1$ is also used in the optimization strategy of Nesterov , which achieves an optimal $O(1/t^{2})$ convergence rate for optimizing (deterministic) objectives with Lipschitz-continuous gradients (see step 3 for their Equation 3.11).

At the same time that we first posted this note, Shamir and Zhang independently proposed a similar weighted average scheme in which they call ‘polynomial-decay averaging’. They consider a running average scheme as in (4), but with the more general $\rho_{t}=\frac{1+\eta}{t+1+\eta}$, where the integer $\eta\geq 0$ parameterizes the different schemes.We note that the index $t$ is shifted by one between this note and their paper as their initial point is $w_{1}$ whereas ours is $w_{0}$. We also note that they use the misnomer ‘gradient descent’ for their algorithm despite using subgradients which don’t necessarily yield a descent direction. $\eta=0$ yields the standard uniform averaging scheme, whereas $\eta=1$ yields the simple weighted average analyzed in Section 3.2. The general $\eta$ gives a weight of $O(t^{\eta})$ for each iterate, similar to what was mentioned in the previous paragraph, but with a different exact formula. They provide in a proof of a rate of $O(1/t)$ for $\eta\geq 2$. The proof that we give in Section 3.2 can be seen as complementary and is especially much simpler (as well as giving a tighter constant). We also note that the rate of $O((\log t)/t)$ for the last iterate $w_{t}$ (scheme 0 above) is proven for the first time in .

While this paper focuses on the non-smooth case, it is still interesting to relate results to the smooth case (see, e.g., and references therein), where in the strongly convex case, averaging with longer step sizes—i.e., of the form $t^{-\alpha}$ with $\alpha\in(1/2,1)$—leads to better and more robust rates. Can larger step sizes improve results for the non-smooth case?

Appendix A Finite variance bound for SVM

Applying Minkowski inequality again, we get

References