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

Non-asymptotic convergence analysis of quasi-Newton methods has gainedattention with a landmark result establishing an explicit local superlinearrate of O$((1/\sqrt{t})^t)$. The methods that obtain this rate, however,exhibit a well-known drawback: they require the storage of the previous Hessianapproximation matrix or all past curvature information to form the currentHessian inverse approximation. Limited-memory variants of quasi-Newton methodssuch as the celebrated L-BFGS alleviate this issue by leveraging a limitedwindow of past curvature information to construct the Hessian inverseapproximation. As a result, their per iteration complexity and storagerequirement is O$(\tau d)$ where $\tau\le d$ is the size of the window and $d$is the problem dimension reducing the O$(d^2)$ computational cost and memoryrequirement of standard quasi-Newton methods. However, to the best of ourknowledge, there is no result showing a non-asymptotic superlinear convergencerate for any limited-memory quasi-Newton method. In this work, we close thisgap by presenting a Limited-memory Greedy BFGS (LG-BFGS) method that canachieve an explicit non-asymptotic superlinear rate. We incorporatedisplacement aggregation, i.e., decorrelating projection, in post-processinggradient variations, together with a basis vector selection scheme on variablevariations, which greedily maximizes a progress measure of the Hessian estimateto the true Hessian. Their combination allows past curvature information toremain in a sparse subspace while yielding a valid representation of the fullhistory. Interestingly, our established non-asymptotic superlinear convergencerate demonstrates an explicit trade-off between the convergence speed andmemory requirement, which to our knowledge, is the first of its kind. Numericalresults corroborate our theoretical findings and demonstrate the effectivenessof our method.

Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate