2019/02/17 by Alina Ene, Adrian Vladu, Ene, Alina +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Cell Image Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Slime Mold and Myxomycetes Research #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1902.06391
openalex publication_date 2019/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The iteratively reweighted least squares method (IRLS) is a popular technique\nused in practice for solving regression problems. Various versions of this\nmethod have been proposed, but their theoretical analyses failed to capture the\ngood practical performance.\n In this paper we propose a simple and natural version of IRLS for solving\n\ℓ_\∞ and \ℓ1 regression, which provably converges to a\n(1+\ε)-approximate solution in\nO(m1/3\log(1/\ε)/\ε2/3 + \log m/\ε2) iterations,\nwhere m is the number of rows of the input matrix. Interestingly, this\nrunning time is independent of the conditioning of the input, and the dominant\nterm of the running time depends sublinearly in \ε-1, which is\natypical for the optimization of non-smooth functions.\n This improves upon the more complex algorithms of Chin et al. (ITCS '12), and\nChristiano et al. (STOC '11) by a factor of at least 1/\ε2, and yields\na truly efficient natural algorithm for the slime mold dynamics\n(Straszak-Vishnoi, SODA '16, ITCS '16, ITCS '17).\n