English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work, we show that the heavy-ball ($\HB$) method provably does notreach an accelerated convergence rate on smooth strongly convex problems. Morespecifically, we show that for any condition number and any choice ofalgorithmic parameters, either the worst-case convergence rate of $\HB$ on theclass of $L$-smooth and $\mu$-strongly convex \textit{quadratic} functions isnot accelerated (that is, slower than $1 - \mathcal{O}(\kappa)$), or thereexists an $L$-smooth $\mu$-strongly convex function and an initialization suchthat the method does not converge.  To the best of our knowledge, this result closes a simple yet open questionon one of the most used and iconic first-order optimization technique.  Our approach builds on finding functions for which $\HB$ fails to convergeand instead cycles over finitely many iterates. We analytically describe allparametrizations of $\HB$ that exhibit this cycling behavior on a particularcycle shape, whose choice is supported by a systematic and constructiveapproach to the study of cycling behaviors of first-order methods. We show therobustness of our results to perturbations of the cycle, and extend them toclass of functions that also satisfy higher-order regularity conditions.

Provable non-accelerations of the heavy-ball method