{"ID":2834670,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.02003","arxiv_id":"2512.02003","title":"Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization","abstract":"Consider the empirical risk minimization (ERM) problem, which is stated as follows. Let $K_1, \\dots, K_m$ be compact convex sets with $K_i \\subseteq \\mathbb{R}^{n_i}$ for $i \\in [m]$, $n = \\sum_{i=1}^m n_i$, and $n_i\\le C_K$ for some absolute constant $C_K$. Also, consider a matrix $A \\in \\mathbb{R}^{n \\times d}$ and vectors $b \\in \\mathbb{R}^d$ and $c \\in \\mathbb{R}^n$. Then the ERM problem asks to find \\[ \\min_{\\substack{x \\in K_1 \\times \\dots \\times K_m\\\\ A^\\top x = b}} c^\\top x. \\] We give an algorithm to solve this to high accuracy in time $\\widetilde{O}(nd + d^6\\sqrt{n}) \\le \\widetilde{O} (nd + d^{11})$, which is nearly-linear time in the input size when $A$ is dense and $n \\ge d^{10}$. Our result is achieved by implementing an $\\widetilde{O}(\\sqrt{n})$-iteration interior point method (IPM) efficiently using dynamic data structures. In this direction, our key technical advance is a new algorithm for maintaining leverage score overestimates of matrices undergoing row updates. Formally, given a matrix $A \\in \\mathbb{R}^{n \\times d}$ undergoing $T$ batches of row updates of total size $n$ we give an algorithm which can maintain leverage score overestimates of the rows of $A$ summing to $\\widetilde{O}(d)$ in total time $\\widetilde{O}(nd + Td^6)$. This data structure is used to sample a spectral sparsifier within a robust IPM framework to establish the main result.","short_abstract":"Consider the empirical risk minimization (ERM) problem, which is stated as follows. Let $K_1, \\dots, K_m$ be compact convex sets with $K_i \\subseteq \\mathbb{R}^{n_i}$ for $i \\in [m]$, $n = \\sum_{i=1}^m n_i$, and $n_i\\le C_K$ for some absolute constant $C_K$. Also, consider a matrix $A \\in \\mathbb{R}^{n \\times d}$ and v...","url_abs":"https://arxiv.org/abs/2512.02003","url_pdf":"https://arxiv.org/pdf/2512.02003v1","authors":"[\"Yang P. Liu\",\"Richard Peng\",\"Colin Tang\",\"Albert Weng\",\"Junzhao Yang\"]","published":"2025-12-01T18:57:23Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.OC\"]","methods":"[]","has_code":false}