Faster p-Norm Regression Using Sparsity

ACO Student Seminar
Friday, March 11, 2022 - 1:00pm for 1 hour (actually 50 minutes)
Skiles 254
Mehrdad Ghadiri – Georgia Tech CS – mghadiri3@gatech.edu
Abhishek Dhawan

Given an n-by-d matrix A and a vector of size n, the p-norm problem asks for a vector x that minimizes the following

\sum_{i=1}^n (a_i^T x - b_i)^p,

where a_i is the i’th row of A. The study of p=2 and p=1 cases dates back to Legendre, Gauss, and Laplace. Other cases of p have also been used in statistics and machine learning as robust estimators for decades. In this talk, we present the following improvements in the running time of solving p-norm regression problems.

For the case of 1

For 1

The talk is based on a joint work with Richard Peng and Santosh Vempala.