2026-07-25T12:38:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23382 2025-10-02T12:53:35Z ddc:004 open_access

Acceleration Meets Inverse Maintenance: Faster 𝓁_∞-Regression Adil, Deeksha Jiang, Shunhua Kyng, Rasmus Regression Inverse Maintenance Multiplicative Weights Update We propose a randomized multiplicative weight update (MWU) algorithm for 𝓁_{∞} regression that runs in Õ(n^{2+1/22.5} poly(1/ε)) time when ω = 2+o(1), improving upon the previous best Õ(n^{2+1/18} polylog(1/ε)) runtime in the low-accuracy regime. Our algorithm combines state-of-the-art inverse maintenance data structures with acceleration. In order to do so, we propose a novel acceleration scheme for MWU that exhibits stability and robustness, which are required for the efficient implementations of the inverse maintenance data structures. We also design a faster deterministic MWU algorithm that runs in Õ(n^{2+1/12}poly(1/ε)) time when ω = 2+o(1), improving upon the previous best Õ(n^{2+1/6} poly log(1/ε)) runtime in the low-accuracy regime. We achieve this by showing a novel stability result that goes beyond previously known works based on interior point methods (IPMs). Our work is the first to use acceleration and inverse maintenance together efficiently, finally making the two most important building blocks of modern structured convex optimization compatible. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Deeksha Adil and Shunhua Jiang and Rasmus Kyng 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.5 urn:nbn:de:0030-drops-233823 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.5 eng https://creativecommons.org/licenses/by/4.0/legalcode