# Sharper Bounds for Regularized Data Fitting

arXiv: https://arxiv.org/abs/1611.03225 · HTML: https://mlsanity.com/paper/1611.03225/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2016.

## Built on by (most cited first, 19 of 19)

- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels](https://mlsanity.com/paper/2207.06343/) (2022)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions](https://mlsanity.com/paper/2104.01101/) (2021)
- [A Novel Sequential Coreset Method for Gradient Descent Algorithms](https://mlsanity.com/paper/2112.02504/) (2021)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters](https://mlsanity.com/paper/2311.14823/) (2023)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners](https://mlsanity.com/paper/2104.14101/) (2021)
- [Faster Randomized Methods for Orthogonality Constrained Problems](https://mlsanity.com/paper/2106.12060/) (2021)
- [NoisyCUR: An algorithm for two-cost budgeted matrix completion](https://mlsanity.com/paper/2104.08026/) (2021)
- [Reweighted Solutions for Weighted Low Rank Approximation](https://mlsanity.com/paper/2406.02431/) (2024)
- [Accurate Coresets for Latent Variable Models and Regularized Regression](https://mlsanity.com/paper/2412.20189/) (2024)
- [Semi-supervised Active Regression](https://mlsanity.com/paper/2106.06676/) (2021)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2306.06611/) (2023)
- [The Fast Mixing Mechanism for Differential Privacy](https://mlsanity.com/paper/2605.30600/) (2026)
- [The Advantages of Fresh Sketching for Ridge Regression](https://mlsanity.com/paper/2609.38565/) (2026)

## Abstract (arXiv)

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 minY,X lVert YX - A rVertF2 + λ lVert YrVertF2 + λlVert X rVertF2, where Y∈ℝn× k and X∈ℝk× d, we give an approximation algorithm needing [ O(mathttnnz(A)) + tildeO((n+d)varepsilon-1k mink, varepsilon-1mathttsdλ(Y^*))+ mathttpoly(mathttsdλ(Y^*) varepsilon-1) ] time, where sλ(Y^*)≤ k is the statistical dimension of Y^*, Y^* 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 λ=0. We also study regularization in a much more general setting. For example, we obtain sketching-based algorithms for the low-rank approximation problem minX,Y lVert YX - A rVertF2 + f(Y,X) where f(·,·) is a regularizing function satisfying some very general conditions (chiefly, invariance under orthogonal transformations).