Suppose we are optimizing a strongly convex function $f(x)$ via gradient descent $x_{t+1} = x_t - \eta_t \nabla f(x_t)$. By strongly convex I mean that $f(x+h) \ge f(x) + \langle \nabla f(x), h \rangle + \frac{\alpha}{2}||h||^2$.

This nice survey paper by Bansal and Gupta (Section 2.2) suggests using a step size $\eta_{t} = \frac{1}{\alpha (t+1)}$ and mentions it is optimal. I am curious how does the $1/(t+1)$ term pop up? Is there a simple-to-state reason for it?

For comparison, when optimizing a smooth function (i.e., upper bounded by some quadratic) the step size $\eta_t = \frac{1}{\beta}$ is very natural because it minimizes the upper bound.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.