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/

Zendy Plus

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

Zendy Tools

Zendy Open

Banach's fixed point theorem for contraction maps has been widely used toanalyze the convergence of iterative methods in non-convex problems. It is acommon experience, however, that iterative maps fail to be globally contractingunder the natural metric in their domain, making the applicability of Banach'stheorem limited. We explore how generally we can apply Banach's fixed pointtheorem to establish the convergence of iterative methods when pairing it withcarefully designed metrics.  Our first result is a strong converse of Banach's theorem, showing that it isa universal analysis tool for establishing global convergence of iterativemethods to unique fixed points, and for bounding their convergence rate. Inother words, we show that, whenever an iterative map globally converges to aunique fixed point, there exists a metric under which the iterative map iscontracting and which can be used to bound the number of iterations untilconvergence. We illustrate our approach in the widely used power method,providing a new way of bounding its convergence rate through contractionarguments.  We next consider the computational complexity of Banach's fixed pointtheorem. Making the proof of our converse theorem constructive, we show thatcomputing a fixed point whose existence is guaranteed by Banach's fixed pointtheorem is CLS-complete. We thus provide the first natural complete problem forthe class CLS, which was defined in [Daskalakis, Papadimitriou 2011] to capturethe complexity of problems such as P-matrix LCP, computing KKT-points, andfinding mixed Nash equilibria in congestion and network coordination games.

A Converse to Banach's Fixed Point Theorem and its CLS Completeness