3
$\begingroup$

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.

$\endgroup$

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.