Revisiting the Polyak step size

Introduction

Scaleable optimization for machine learning is based entirely on first order gradient methods. Besides the age-old method of stochastic approximation , three accelerated methods have proved their practical and theoretical significance: Nesterov acceleration , variance reduction and adaptive learning-rate/regularization .

Adaptive choices of step sizes allow optimization algorithms to accelerate quickly according to the local curvature and smoothness of the optimization landscape. However, in theory, there are few parameter free algorithms, and, in practice, there are many search heuristics utilized.

Let us examine this question of parameter free, adaptive learning rates for one of the most standard algorithms, namely the gradient descent method:

Although this class of algorithms is not optimal in all settings (i.e. the aforementioned accelerations can be applied), it is fundamental, and we may ask what are optimal known rates along with the optimal step size choices are for this particular algorithm. Here, Table 1 shows the best known rates for gradient descent in the standard regimes: general convex (non-smooth with bounded sub-gradients); $\beta$-smooth; $\alpha$-strongly-convex; and $\beta$-smooth&$\alpha$-strongly convex (see for more details).

From a practical perspective these step size settings are unfortunately disparate in various regimes: ranging from rapidly decaying at $\eta_{t}=O(\frac{1}{\alpha t})$ to moderately decaying at $\eta_{t}=O(\frac{1}{\sqrt{t}})$ to a constant $\eta_{t}=\frac{1}{\beta}$ (see for more details).

This work: We show that a single (and simple) choice of a step size schedule gives, simultaneously, the optimal convergence (among the class of gradient descent algorithms) in all these regimes, without knowing these parameters in advance. Perhaps surprisingly, this choice is that prescribed by , who argued that this choice was optimal for the non-smooth, convex case (marked as “convex” in Table 1, see also ).

Convexity Preliminaries

We say that $f$ is $\beta$ smooth if and only if $\forall\mathbf{x},\mathbf{y}$:

The following notation is used throughout:

$h(\mathbf{x}_{t})=h_{t}=f(\mathbf{x}_{t})-f(\mathbf{x}^{\star})$ - sub-optimality gap of the iterate

$d_{t}=\|\mathbf{x}_{t}-\mathbf{x}^{\star}\|$ - Euclidean distance of the iterate.

$\nabla_{t}=\nabla f(\mathbf{x}_{t})$ - gradient of the iterate.

$\|\nabla_{t}\|^{2}$ denotes squared Euclidean norm.

The following are basic properties for $\alpha$-strongly-convex functions and/or $\beta$-smooth functions (proved for completeness in Lemma 4):

The following standard lemma is at the heart of much of the analysis of first order convex optimization.

The sequence of iterates produced by projected gradient descent (equation 1) satisfies:

where we have used properties of convexity in the last step. ∎

Main Results

argued that, in a sense, the optimal step size choice of $\eta_{t}$ should decrease the upper bound on $d_{t+1}^{2}$ as fast as possible. This choice is:

which leads to a decrease of $d_{t}^{2}$ by:

Note that this choice utilizes knowledge of $f(\mathbf{x}^{\star})$, since $h_{t}=f(\mathbf{x}_{t})-f(\mathbf{x}^{\star})$.

showed that this choice was optimal for non-smooth convex optimization (i.e. for bounded gradients). Our first result shows that this step size schedule (which knows $f(\mathbf{x}^{\star})$) achieves the min of the best known bounds in all the standard parameter regimes (among the class of projected gradient descent algorithms). Assume $\|\nabla_{t}\|\leq G$, and define:

(GD with the Polyak Step Size) Algorithm 1 attains the following regret bound after $T$ steps:

Theorem 1 directly follows from the following lemma. It is helpful for us to state this lemma in a more general form, where, for $0\leq\gamma\leq 1$, we define $R_{T,\gamma}$ as follows:

For $0\leq\gamma\leq 1$, suppose that a sequence $\mathbf{x}_{0},\ldots\mathbf{x}_{t}$ satisfies:

then for $\bar{\mathbf{x}}=\mathbf{x}_{t^{\star}}$, where $t^{\star}=\operatorname*{\arg\!\min}_{t<T}\{f(\mathbf{x}_{t})\}$,

For convex functions with gradient bound $G$,

Summing up over $T$ iterations, and using Cauchy-Schwartz, we have

For smooth functions, equation (2) implies:

For strongly convex functions, equation (2) implies:

In other words, $d_{t+1}^{2}\leq d_{t}^{2}(1-\gamma\frac{\alpha^{2}d_{t}^{2}}{4G^{2}})\,.$ Defining $a_{t}:={\gamma}\frac{4\alpha^{2}d_{t}^{2}}{G^{2}}$, we have:

This implies that $a_{t}\leq\frac{1}{t+1}$, which can be seen by inductionThat $a_{0}\leq 1$ follows from equation (2). For $t=1$, $a_{1}\leq\frac{1}{2}$ since $a_{1}\leq a_{0}(1-a_{0})$ and $0\leq a_{0}\leq 1$. For the induction step, $a_{t}\leq a_{t-1}(1-a_{t-1})\leq\frac{1}{t}(1-\frac{1}{t})=\frac{t-1}{t^{2}}=\frac{1}{t+1}(\frac{t^{2}-1}{t^{2}})\leq\frac{1}{t+1}$.. The proof is completed as followsThis assumes $T$ is even. $T$ odd leads to the same constants. :

Thus, there exists a $t$ for which $h_{t}^{2}\leq\frac{G^{4}}{\gamma^{2}\alpha^{2}T^{2}}$. Taking the square root completes the claim.

2 Analysis: the adaptive case

The proof of Theorem 2 rests on the following lemma which shows that, given a lower bound on the objective, the subroutine in Algorithm 3 either returns a near-optimal point with desired precision or a tighter lower bound.

$h(\bar{\mathbf{x}})\leq R_{T,\frac{1}{2}}$

We will consider two cases. First, suppose that

held for $T$ steps. For this case, by Lemma 1,

using the assumed upper bound on $\eta_{t}$ in the second step and the lower bound in the last step. By Lemma 2, we can take $\gamma=1/2$ and we have that $\min_{t<T}h_{t}\leq R_{T,\frac{1}{2}}$.

Now suppose there exists a time $t^{*}$ where Equation 5 fails to hold. Hence, for some iteration,

Acknowledgements

We thank Yair Carmon for pointing out a sign error and for teaching this material. Elad Hazan acknowledges funding from NSF award Number 1704860. Sham Kakade acknowledges funding from the Washington Research Foundation for Innovation in Data-intensive Discovery, the DARPA award FA8650-18-2-7836, and the ONR award N00014-18-1-2247.

References

Appendix A Elementary properties of convex analysis

The following properties hold for $\alpha$-strongly-convex functions and/or $\beta$-smooth functions.

$\frac{1}{2\beta}\|\nabla_{t}\|^{2}\leq h_{t}$

$h_{t}\leq\frac{1}{2\alpha}\|\nabla_{t}\|^{2}$

Claim 1: $h_{t}\geq\frac{\alpha}{2}d_{t}^{2}$

where the last inequality holds by optimality conditions for $\mathbf{x}^{\star}$.

where the last inequality follows since the gradient at the global optimum is zero.

Claim 3: $h_{t}\geq\frac{1}{\beta}\|\nabla_{t}\|^{2}$

Claim 4: $h_{t}\leq\frac{1}{\alpha}\|\nabla_{t}\|^{2}$

In particular, taking $\mathbf{x}=\mathbf{x}_{t}\ ,\ \mathbf{y}=\mathbf{x}^{\star}$, we have