# Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 17 Sep 2022.

## Builds on (most cited first, 16 of 16)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [Generalization Bounds for Data-Driven Numerical Linear Algebra](https://mlsanity.com/paper/2206.07886/) (2022)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2007.09890/) (2020)
- [Learning to Link](https://mlsanity.com/paper/1907.00533/) (2019)
- [Improved Sample Complexity Bounds for Branch-and-Cut](https://mlsanity.com/paper/2111.11207/) (2021)
- [Refined bounds for algorithm configuration: The knife-edge of dual class approximability](https://mlsanity.com/paper/2006.11827/) (2020)
- [Sparse Linear Networks with a Fixed Butterfly Structure: Theory and Practice](https://mlsanity.com/paper/2007.08864/) (2020)
- [Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search](https://mlsanity.com/paper/2205.09963/) (2022)
- [An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theory](https://mlsanity.com/paper/1710.07973/) (2017)

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

- [Algorithm Configuration for Structured Pfaffian Settings](https://mlsanity.com/paper/2409.04367/) (2024)
- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [Provably data-driven projection method for quadratic programming](https://mlsanity.com/paper/2509.04524/) (2025)
- [Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to K-Level Stochastic Optimizations](https://mlsanity.com/paper/2407.05286/) (2024)
- [Learning Sparsity and Randomness for Data-driven Low Rank Approximation](https://mlsanity.com/paper/2212.08186/) (2022)

## Abstract (arXiv)

Learning sketching matrices for fast and accurate low-rank approximation (LRA) has gained increasing attention. Recently, Bartlett, Indyk, and Wagner (COLT 2022) presented a generalization bound for the learning-based LRA. Specifically, for rank-k approximation using an m × n learned sketching matrix with s non-zeros in each column, they proved an tildeO(nsm) bound on the fat shattering dimension (tildeO hides logarithmic factors). We build on their work and make two contributions. 1. We present a better tildeO(nsk) bound (k ≤ m). En route to obtaining this result, we give a low-complexity Goldberg--Jerrum algorithm for computing pseudo-inverse matrices, which would be of independent interest. 2. We alleviate an assumption of the previous study that sketching matrices have a fixed sparsity pattern. We prove that learning positions of non-zeros increases the fat shattering dimension only by O(nslog n). In addition, experiments confirm the practical benefit of learning sparsity patterns.