mlsanityData to 14 Oct 2026

Generalization Bounds for Data-Driven Numerical Linear Algebra

arXiv 2206.07886 ↗First posted 16 Jun 2022cs.LG cs.DScited by 24

Not on the map. Why?

Abstract (arXiv)

Data-driven algorithms can adapt their internal structure or parameters to inputs from unknown application-specific distributions, by learning from a training sample of inputs. Several recent works have applied this approach to problems in numerical linear algebra, obtaining significant empirical gains in performance. However, no theoretical explanation for their success was known. In this work we prove generalization bounds for those algorithms, within the PAC-learning framework for data-driven algorithm selection proposed by Gupta and Roughgarden (SICOMP 2017). Our main results are closely matching upper and lower bounds on the fat shattering dimension of the learning-based low rank approximation algorithm of Indyk et al.~(NeurIPS 2019). Our techniques are general, and provide generalization bounds for many other recently proposed data-driven algorithms in numerical linear algebra, covering both sketching-based and multigrid-based methods. This considerably broadens the class of data-driven algorithms for which a PAC-learning analysis is available.

Key facts. Cited by 24 papers in the map (data through 14 Oct 2026). Builds on 13 of its 45 references that are in the map. First posted on arXiv 16 Jun 2022.

Builds on

13 of 45 references.

References · 13

  1. 2020Algorithms with Predictionscited by 153
  2. 2018Learning to Branchcited by 78
  3. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 64
  4. 2015A PAC Approach to Application-Specific Algorithm Selectioncited by 58
  5. 2020Learning Algebraic Multigrid Using Graph Neural Networkscited by 54
  6. 2019Learning-Based Low-Rank Approximationscited by 41
  7. 2021Sample Complexity of Tree Search Configuration: Cutting Planes and Beyondcited by 33
  8. 2016Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problemscited by 30
  9. 2019How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm designcited by 27
  10. 2020Learning the Positions in CountSketchcited by 20
  11. 2019Sample-Optimal Low-Rank Approximation of Distance Matricescited by 15
  12. 2020Refined bounds for algorithm configuration: The knife-edge of dual class approximabilitycited by 12
1 more
  1. 2020Sparse Linear Networks with a Fixed Butterfly Structure: Theory and Practicecited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 4; 2024: 4; 2025: 8; 2026: 6.

24 papers.

Sort:

By area:

  1. 2023Learning to Warm-Start Fixed-Point Optimization Algorithmscited by 32
  2. 2024Algorithm Configuration for Structured Pfaffian Settingscited by 11
  3. 2023Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programmingcited by 10
  4. 2025Offline-to-online hyperparameter transfer for stochastic banditscited by 7
  5. 2022Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximationcited by 5
  6. 2023Efficiently Learning the Graph for Semi-supervised Learningcited by 5
  7. 2024Data-Driven Performance Guarantees for Classical and Learned Optimizerscited by 5
  8. 2025Provably data-driven projection method for quadratic programmingcited by 5
  9. 2024Learning accurate and interpretable tree-based modelscited by 3
  10. 2024Accelerating data-driven algorithm selection for combinatorial partitioning problemscited by 2
  11. 2025Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Taskscited by 2
  12. 2025Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problemcited by 2
12 more
  1. 2026Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Functioncited by 2
  2. 2026Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programmingcited by 2
  3. 2025Online Learning of Pure States is as Hard as Mixed Statescited by 1
  4. 2025Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guaranteescited by 1
  5. 2025Gradient Descent with Provably Tuned Learning-rate Schedulescited by 1
  6. 2026Learning-augmented smooth integer programs with PAC-learnable oraclescited by 1
  7. 2026Learning Decision-Sufficient Representations for Linear Optimizationcited by 1
  8. 2026Generalization Guarantees on Data-Driven Tuning of Gradient Descent with Langevin Updatescited by 1
  9. 2022Learning Sparsity and Randomness for Data-driven Low Rank Approximationcited by 0
  10. 2023Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instancescited by 0
  11. 2025Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programmingcited by 0
  12. 2026Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programmingcited by 0