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

We analyze the bit complexity of efficient algorithms for fundamentaloptimization problems, such as linear regression, $p$-norm regression, andlinear programming (LP). State-of-the-art algorithms are iterative, and interms of the number of arithmetic operations, they match the current timecomplexity of multiplying two $n$-by-$n$ matrices (up to polylogarithmicfactors). However, previous work has typically assumed infinite precisionarithmetic, and due to complicated inverse maintenance techniques, the actualrunning times of these algorithms are unknown. To settle the running time andbit complexity of these algorithms, we demonstrate that a core commonsubroutine, known as \emph{inverse maintenance}, is backward-stable.Additionally, we show that iterative approaches for solving constrainedweighted regression problems can be accomplished with bounded-errorpre-conditioners. Specifically, we prove that linear programs can be solvedapproximately in matrix multiplication time multiplied by polylog factors thatdepend on the condition number $\kappa$ of the matrix and the inner and outerradius of the LP problem. $p$-norm regression can be solved approximately inmatrix multiplication time multiplied by polylog factors in $\kappa$. Lastly,linear regression can be solved approximately in input-sparsity time multipliedby polylog factors in $\kappa$. Furthermore, we present results for achievinglower than matrix multiplication time for $p$-norm regression by utilizingfaster solvers for sparse linear systems.

The Bit Complexity of Efficient Continuous Optimization