THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Talk
Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
Shusen Wang · Alex Gittens · Michael Mahoney

Mon Aug 07 05:30 PM -- 05:48 PM (PDT) @ C4.8
in Learning theory 1 »

We address the statistical and optimization impacts of using classical sketch versus Hessian sketch to solve approximately the Matrix Ridge Regression (MRR) problem. Prior research has considered the effects of classical sketch on least squares regression (LSR), a strictly simpler problem. We establish that classical sketch has a similar effect upon the optimization properties of MRR as it does on those of LSR---namely, it recovers nearly optimal solutions. In contrast, Hessian sketch does not have this guarantee; instead, the approximation error is governed by a subtle interplay between the ``mass'' in the responses and the optimal objective value. For both types of approximations, the regularization in the sketched MRR problem gives it significantly different statistical properties from the sketched LSR problem. In particular, there is a bias-variance trade-off in sketched MRR that is not present in sketched LSR. We provide upper and lower bounds on the biases and variances of sketched MRR; these establish that the variance is significantly increased when classical sketches are used, while the bias is significantly increased when using Hessian sketches. Empirically, sketched MRR solutions can have risks that are higher by an order-of-magnitude than those of the optimal MRR solutions. We establish theoretically and empirically that model averaging greatly decreases this gap. Thus, in the distributed setting, sketching combined with model averaging is a powerful technique that quickly obtains near-optimal solutions to the MRR problem while greatly mitigating the statistical risks incurred by sketching.

[ PDF]  [ ss Summary/Notes]  [ Video] 

Author Information

Shusen Wang (UC Berkeley)
Alex Gittens (Rensselaer Polytechnic Institute)

Alex Gittens's research focuses on using randomization to reduce the computational costs of extracting information from large datasets. His work lies at the intersection of randomized algorithms, numerical linear algebra, high-dimensional probability, and machine learning.

Michael Mahoney (UC Berkeley)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors