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

The iteratively reweighted least squares method (IRLS) is a popular techniqueused in practice for solving regression problems. Various versions of thismethod have been proposed, but their theoretical analyses failed to capture thegood practical performance.  In this paper we propose a simple and natural version of IRLS for solving$\ell_\infty$ and $\ell_1$ regression, which provably converges to a$(1+\epsilon)$-approximate solution in$O(m^{1/3}\log(1/\epsilon)/\epsilon^{2/3} + \log m/\epsilon^2)$ iterations,where $m$ is the number of rows of the input matrix. Interestingly, thisrunning time is independent of the conditioning of the input, and the dominantterm of the running time depends sublinearly in $\epsilon^{-1}$, which isatypical for the optimization of non-smooth functions.  This improves upon the more complex algorithms of Chin et al. (ITCS '12), andChristiano et al. (STOC '11) by a factor of at least $1/\epsilon^2$, and yieldsa truly efficient natural algorithm for the slime mold dynamics(Straszak-Vishnoi, SODA '16, ITCS '16, ITCS '17).

Improved Convergence for $\ell_\infty$ and $\ell_1$ Regression via Iteratively Reweighted Least Squares