Timezone: »

 
Poster
Efficient Symmetric Norm Regression via Linear Sketching
Zhao Song · Ruosong Wang · Lin Yang · Hongyang Zhang · Peilin Zhong

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #108
in Optimization -- Convex Optimization »
We provide efficient algorithms for overconstrained linear regression problems with size $n \times d$ when the loss function is a symmetric norm (a norm invariant under sign-flips and coordinate-permutations). An important class of symmetric norms are Orlicz norms, where for a function $G$ and a vector $y \in \mathbb{R}^n$, the corresponding Orlicz norm $\|y\|_G$ is defined as the unique value $\alpha$ such that $\sum_{i=1}^n G(|y_i|/\alpha) = 1$. When the loss function is an Orlicz norm, our algorithm produces a $(1 + \varepsilon)$-approximate solution for an arbitrarily small constant $\varepsilon > 0$ in input-sparsity time, improving over the previously best-known algorithm which produces a $d \cdot \polylog n$-approximate solution. When the loss function is a general symmetric norm, our algorithm produces a $\sqrt{d} \cdot \polylog n \cdot \mathrm{mmc}(\ell)$-approximate solution in input-sparsity time, where $\mathrm{mmc}(\ell)$ is a quantity related to the symmetric norm under consideration. To the best of our knowledge, this is the first input-sparsity time algorithm with provable guarantees for the general class of symmetric norm regression problem. Our results shed light on resolving the universal sketching problem for linear regression, and the techniques might be of independent interest to numerical linear algebra problems more broadly.
Keywords: Learning Theory · Theory
[ Paper]  [ Poster] 

Author Information

Zhao Song (University of Washington)
Ruosong Wang (Carnegie Mellon University)
Lin Yang (UCLA)
Hongyang Zhang (TTIC)
Peilin Zhong (Columbia University)

More from the Same Authors