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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The spectral bundle method proposed by Helmberg and Rendl is well establishedfor solving large-scale semidefinite programs (SDP) thanks to its low periteration computational complexity and strong practical performance. In thispaper, we revisit this classic method showing it achieves sublinear convergencerates in terms of both primal and dual SDPs under merely strong duality,complementing previous guarantees on primal-dual convergence. Moreover, we showthe method speeds up to linear convergence if (1) structurally, the SDP admitsstrict complementarity, and (2) algorithmically, the bundle method captures therank of the optimal solutions. Such complementary and low rank structure isprevalent in many modern and classical applications. The linear convergentresult is established via an eigenvalue approximation lemma which might be ofindependent interest. Numerically, we confirm our theoretical findings that thespectral bundle method, for modern and classical applications, speeds up underthese conditions. Finally, we show that the spectral bundle method combinedwith a recent matrix sketching technique is able to solve an SDP with billionsof decision variables in a matter of minutes.

Revisiting Spectral Bundle Methods: Primal-dual (Sub)linear Convergence Rates