0
$\begingroup$

If instead of the classical $1/L$ constant step size we have adaptive step sizes chosen with exact line search or Armijo (let's say) can this alter the Big-O complexity of the convergence rate?

Here: https://arxiv.org/pdf/2306.02527 the authors note that "... even an exact line-search cannot improve the convergence rate beyond what is achievable with a fixed step-size". But this is for strongly convex functions - would the same be true in general non-convex case?

$\endgroup$
1
  • 1
    $\begingroup$ I might be grossly wrong, but I think that line search will increase the averaged rate of convergence. What will not change is the order of convergence, as the search direction of the gradient descent is almost always first-order wrong. Just try out the usual test case of a slim ellipsis, that is, a quadratic function with a matrix with a small and a large eigenvalue. $L$ will be the large eigenvalue, for search directions dominated by the eigenvector of the small eigenvalue line search will be substantially better than the 1/L factor. $\endgroup$
    – Lutz Lehmann
    Commented Jun 3 at 7:52

0

Reset to default

You must log in to answer this question.