Can I read Weighted SGD for $\ell_p$ Regression with Randomized Preconditioning on EtoBox?

Weighted SGD for $\ell_p$ Regression with Randomized Preconditioning by Yang, Jiyan; Chow, Yin-Lam; Ré, Christopher; Mahoney, Michael W. is a scholarly article available to read on EtoBox.

What is Weighted SGD for $\ell_p$ Regression with Randomized Preconditioning about?

In recent years, stochastic gradient descent (SGD) methods and randomized linear algebra (RLA) algorithms have been applied to many large-scale problems in machine learning and data analysis. We aim to bridge the gap between these two methods in solving constrained overdetermined linear regression problems---e.g., $\ell_2$ and $\ell_1$ regression problems. We propose a hybrid algorithm named pwSGD that uses RLA techniques for preconditioning and constructing an importance sampling distribution, and then performs an SGD-like iterative process with weighted sampling on the preconditioned system. We prove that pwSGD inherits faster convergence rates that only depend on the lower dimension of the linear system, while maintaining low computation complexity. Particularly, when solving $\ell_1$ regression with size $n$ by $d$, pwSGD returns an approximate solution with $\epsilon$ relative error in the objective value in $\mathcal{O}(\log n \cdot \text{nnz}(A) + \text{poly}(d)/\epsilon^2)$ time. This complexity is uniformly better than that of RLA methods in terms of both $\epsilon$ and $d$ when the problem is unconstrained. For $\ell_2$ regression, pwSGD returns an approximate solution wi

Author

Yang, Jiyan; Chow, Yin-Lam; Ré, Christopher; Mahoney, Michael W.

Published

2015

Language

EN