mlsanityData to 7 Oct 2026

Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing

arXiv 2105.08285 ↗First posted 18 May 2021cs.DS cs.LG stat.MLcited by 15

Not on the map. Why?

Abstract (arXiv)

We present the first provable Least-Squares Value Iteration (LSVI) algorithms that have runtime complexity sublinear in the number of actions. We formulate the value function estimation procedure in value iteration as an approximate maximum inner product search problem and propose a locality sensitive hashing (LSH) [Indyk and Motwani STOC'98, Andoni and Razenshteyn STOC'15, Andoni, Laarhoven, Razenshteyn and Waingarten SODA'17] type data structure to solve this problem with sublinear time complexity. Moreover, we build the connections between the theory of approximate maximum inner product search and the regret analysis of reinforcement learning. We prove that, with our choice of approximation factor, our Sublinear LSVI algorithms maintain the same regret as the original LSVI algorithms while reducing the runtime complexity to sublinear in the number of actions. To the best of our knowledge, this is the first work that combines LSH with reinforcement learning resulting in provable improvements. We hope that our novel way of combining data-structures and iterative algorithm will open the door for further study into cost reduction in optimization.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 50 of its 94 references that are in the map. First posted on arXiv 18 May 2021.

Builds on

50 of 94 references.

References · 50

  1. 2018Is Q-learning Provably Efficient?cited by 485
  2. 2016Deep Reinforcement Learning for Dialogue Generationcited by 286
  3. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  5. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  6. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  7. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  8. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  9. 2014Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)cited by 109
  10. 2015Practical and Optimal LSH for Angular Distancecited by 105
  11. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  12. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
38 more
  1. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  2. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  3. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  4. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  5. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  6. 2018Approximate Nearest Neighbor Search in High Dimensionscited by 45
  7. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  8. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 43
  9. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  10. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  11. 2018Hashing-Based-Estimators for Kernel Density in High Dimensionscited by 31
  12. 2015Quantization based Fast Inner Product Searchcited by 29
  13. 2020A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Pathcited by 29
  14. 2020Kernel Density Estimation through Density Constrained Near Neighbor Searchcited by 26
  15. 2014On Symmetric and Asymmetric LSHs for Inner Product Searchcited by 23
  16. 2020Solving Tall Dense Linear Programs in Nearly Linear Timecited by 21
  17. 2020A Framework for Adversarially Robust Streaming Algorithmscited by 21
  18. 2016Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighborscited by 18
  19. 2019Efficient Model-free Reinforcement Learning in Metric Spacescited by 18
  20. 2014Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)cited by 15
  21. 2021Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and Morecited by 15
  22. 2018On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Productcited by 12
  23. 2014Powers of Tensors and Fast Matrix Multiplicationcited by 11
  24. 2016A Greedy Approach for Budgeted Maximum Inner Product Searchcited by 11
  25. 2020Bipartite Matching in Nearly-linear Time on Moderately Dense Graphscited by 11
  26. 2018Norm-Ranging LSH for Maximum Inner Product Searchcited by 8
  27. 2020Scaling up Kernel Ridge Regression via Locality Sensitive Hashingcited by 8
  28. 2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 8
  29. 2017On the Difference Between Closest, Furthest, and Orthogonal Pairs: Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometrycited by 6
  30. 2018An Equivalence Class for Orthogonal Vectorscited by 5
  31. 2020Climbing the WOL: Training for Cheaper Inferencecited by 5
  32. 2019(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterlesscited by 4
  33. 2016A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filteringcited by 3
  34. 2016Approximate Near Neighbors for General Symmetric Normscited by 2
  35. 2018Scaling-up Split-Merge MCMC with Locality Sensitive Sampling (LSS)cited by 2
  36. 2019Lsh-sampling Breaks the Computation Chicken-and-egg Loop in Adaptive Stochastic Gradient Estimationcited by 2
  37. 2015CoveringLSH: Locality-sensitive Hashing without False Negativescited by 1
  38. 2018Optimal Las Vegas Approximate Near Neighbors in ℓpcited by 1

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 6; 2023: 7; 2024: 1.

15 papers.

Sort:

  1. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  2. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  3. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  4. 2022A Sublinear Adversarial Training Algorithmcited by 22
  5. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  6. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  7. 2022Dynamic Tensor Product Regressioncited by 17
  8. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  9. 2023Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Accelerationcited by 11
  10. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  11. 2022Sublinear Time Algorithm for Online Weighted Bipartite Matchingcited by 7
  12. 2022Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theorycited by 6
3 more
  1. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  2. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  3. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0