publications

2024

1. 

   Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descent

   Peter Richtárik, Simone Maria Giancola, Dymitr Lubczyk, and Robin Yadav

   arXiv preprint, May 2024

   Abs Bib HTML PDF

   We contribute to the growing body of knowledge on more powerful and adaptive stepsizes for convex optimization, empowered by local curvature information. We do not go the route of fully-fledged second-order methods which require the expensive computation of the Hessian. Instead, our key observation is that, for some problems (e.g., when minimizing the sum of squares of absolutely convex functions), certain local curvature information is readily available, and can be used to obtain surprisingly powerful matrix-valued stepsizes, and meaningful theory. In particular, we develop three new methods–LCD1, LCD2 and LCD3–where the abbreviation stands for local curvature descent. While LCD1 generalizes gradient descent with fixed stepsize, LCD2 generalizes gradient descent with Polyak stepsize. Our methods enhance these classical gradient descent baselines with local curvature information, and our theory recovers the known rates in the special case when no curvature information is used. Our last method, LCD3, is a variable metric version of LCD2; this feature leads to a closed-form expression for the iterates. Our empirical results are encouraging, and show that the local curvature descent improves upon gradient descent.

   @article{richtarikLocalCurvatureDescent2024,
     title = {Local {{Curvature Descent}}: {{Squeezing More Curvature}} out of {{Standard}} and {{Polyak Gradient Descent}}},
     shorttitle = {Local {{Curvature Descent}}},
     author = {Richt{\'a}rik, Peter and Giancola, Simone Maria and Lubczyk, Dymitr and Yadav, Robin},
     year = {2024},
     month = may,
     number = {arXiv:2405.16574},
     eprint = {2405.16574},
     eprinttype = {math.OC},
     primaryclass = {math},
     publisher = {arXiv},
     keywords = {Mathematics - Optimization and Control},
     journal = {arXiv preprint},
     doi = {10.48550/arXiv.2405.16574}
   }