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 $\tilde{O}(nd+d^6\sqrt{n})\le \tilde{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 $\tilde{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 $\tilde{O}(d)$ in total time $\tilde{O}(nd+T{d}^6)$. This data structure is used to sample a spectral sparsifier within a robust IPM framework to establish the main result.