Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912348211511296 |
|---|---|
| author | Adil, Deeksha Jiang, Shunhua Kyng, Rasmus |
| author_facet | Adil, Deeksha Jiang, Shunhua Kyng, Rasmus |
| contents | We propose a randomized multiplicative weight update (MWU) algorithm for $\ell_{\infty}$ regression that runs in $\widetilde{O}\left(n^{2+1/22.5} \text{poly}(1/ε)\right)$ time when $ω= 2+o(1)$, improving upon the previous best $\widetilde{O}\left(n^{2+1/18} \text{poly} \log(1/ε)\right)$ 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 {\it stabiliy} and {\it robustness}, which are required for the efficient implementations of the inverse maintenance data structures.
We also design a faster {\it deterministic} MWU algorithm that runs in $\widetilde{O}\left(n^{2+1/12}\text{poly}(1/ε)\right))$ time when $ω= 2+o(1)$, improving upon the previous best $\widetilde{O}\left(n^{2+1/6} \text{poly} \log(1/ε)\right)$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_20030 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression Adil, Deeksha Jiang, Shunhua Kyng, Rasmus Data Structures and Algorithms Optimization and Control We propose a randomized multiplicative weight update (MWU) algorithm for $\ell_{\infty}$ regression that runs in $\widetilde{O}\left(n^{2+1/22.5} \text{poly}(1/ε)\right)$ time when $ω= 2+o(1)$, improving upon the previous best $\widetilde{O}\left(n^{2+1/18} \text{poly} \log(1/ε)\right)$ 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 {\it stabiliy} and {\it robustness}, which are required for the efficient implementations of the inverse maintenance data structures. We also design a faster {\it deterministic} MWU algorithm that runs in $\widetilde{O}\left(n^{2+1/12}\text{poly}(1/ε)\right))$ time when $ω= 2+o(1)$, improving upon the previous best $\widetilde{O}\left(n^{2+1/6} \text{poly} \log(1/ε)\right)$ 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. |
| title | Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression |
| topic | Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2409.20030 |