Sharper bounds for regularized data fitting

DOI10.4230/LIPICS.APPROX-RANDOM.2017.27MaRDI QIDQ5002630zbMATH OpenOpenAlexFDO

Authors Haim Avron, Kenneth L. Clarkson, David P. Woodruff

Publication date 28 July 2021

Full work available at URL https://arxiv.org/abs/1611.03225

zbMATH Keywords

canonical correlation analysislow-rank approximationmatricesregressionregularizationstatistical learning

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Measures of association (correlation, canonical correlation, etc.) (62H20) Linear regression; mixed models (62J05) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We study matrix sketching methods for regularized variants of linear regression, low rank approximation, and canonical correlation analysis. Our main focus is on sketching techniques which preserve the objective function value for regularized problems, which is an area that has remained largely unexplored. We study regularization both in a fairly broad setting, and in the specific context of the popular and widely used technique of ridge regularization; for the latter, as applied to each of these problems, we show algorithmic resource bounds in which the {em statistical dimension} appears in places where in previous bounds the rank would appear. The statistical dimension is always smaller than the rank, and decreases as the amount of regularization increases. In particular, for the ridge low-rank approximation problem $mi{n}_{Y,X}lVertYX-AVer{t}_F^2+lambdalVertYVer{t}_F^2+lambdalVertXVer{t}_F^2$, where $Yinmathbb{R}^{nimesk}$ and $Xinmathbb{R}^{kimesd}$, we give an approximation algorithm needing [ O(mathtt{nnz}(A)) + ilde{O}((n+d)varepsilon^{-1}k min{k, varepsilon^{-1}mathtt{sd}_lambda(Y^*)})+ mathtt{poly}(mathtt{sd}_lambda(Y^*) varepsilon^{-1}) ] time, where $s_{lambda}(Y^{\ast })lek$ is the statistical dimension of $Y^{\ast }$, $Y^{\ast }$ is an optimal $Y$, $varepsilon$ is an error parameter, and $mathttnnz(A)$ is the number of nonzero entries of $A$.This is faster than prior work, even when $lambda=0$. We also study regularization in a much more general setting. For example, we obtain sketching-based algorithms for the low-rank approximation problem $mi{n}_{X,Y}lVertYX-AVer{t}_F^2+f(Y,X)$ where $f(cdot,cdot)$ is a regularizing function satisfying some very general conditions (chiefly, invariance under orthogonal transformations).

Recommendations

• Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
• A statistical perspective on randomized sketching for ordinary least-squares
• Sketching as a tool for numerical linear algebra
• Fast regression with an \(\ell_{\infty}\) guarantee
• Randomized sketches for kernels: fast and optimal nonparametric regression

Cites work

• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Efficient dimensionality reduction for canonical correlation analysis
• Eigenvalues of a matrix in the streaming model
• Faster kernel ridge regression using sketching and preconditioning
• Faster least squares approximation
• Improved analysis of the subsampled randomized Hadamard transform
• Learning Theory
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Nearly tight oblivious subspace embeddings by trace inequalities
• Numerical Methods for Computing Angles Between Linear Subspaces
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Randomized Algorithms for Matrices and Data
• Randomized Sketches of Convex Programs With Sharp Guarantees
• Sampling algorithms for l₂ regression and applications
• Sketching as a tool for numerical linear algebra
• The elements of statistical learning. Data mining, inference, and prediction

Cited in

(10)

• Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten p-norms
• A statistical perspective on randomized sketching for ordinary least-squares
• Sketched ridge regression: optimization perspective, statistical perspective, and model averaging
• Faster kernel ridge regression using sketching and preconditioning
• Semi-Infinite Linear Regression and Its Applications
• High-order data sharpening with dependent errors for regression bias reduction
• M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
• Randomized Low-Rank Approximation of Monotone Matrix Functions
• Asymptotics of the Sketched Pseudoinverse
• A very sketchy talk (invited talk)

Describes a project that uses

Uses Software

• LowRankModels
• Pyglrm

This page was built for publication: Sharper bounds for regularized data fitting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002630)