mlsanityData to 14 Oct 2026

Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures

arXiv 2111.15139 ↗First posted 30 Nov 2021cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

Conditional gradient methods (CGM) are widely used in modern machine learning. CGM's overall running time usually consists of two parts: the number of iterations and the cost of each iteration. Most efforts focus on reducing the number of iterations as a means to reduce the overall running time. In this work, we focus on improving the per iteration cost of CGM. The bottleneck step in most CGM is maximum inner product search (MaxIP), which requires a linear scan over the parameters. In practice, approximate MaxIP data-structures are found to be helpful heuristics. However, theoretically, nothing is known about the combination of approximate MaxIP data-structures and CGM. In this work, we answer this question positively by providing a formal framework to combine the locality sensitive hashing type approximate MaxIP data-structures with CGM algorithms. As a result, we show the first algorithm, where the cost per iteration is sublinear in the number of parameters, for many fundamental optimization algorithms, e.g., Frank-Wolfe, Herding algorithm, and policy gradient.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 46 of its 80 references that are in the map. First posted on arXiv 30 Nov 2021.

Builds on

46 of 80 references.

References · 46

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  4. 2014Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)cited by 109
  5. 2015Practical and Optimal LSH for Angular Distancecited by 106
  6. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  7. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  8. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  9. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  10. 2018Approximate Nearest Neighbor Search in High Dimensionscited by 47
  11. 2019SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systemscited by 46
  12. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 44
34 more
  1. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 44
  2. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  3. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  4. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 41
  5. 2017Iterative Machine Teachingcited by 41
  6. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  7. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  8. 2018Large-scale Interactive Recommendation with Tree-structured Policy Gradientcited by 30
  9. 2015Quantization based Fast Inner Product Searchcited by 29
  10. 2020A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Pathcited by 29
  11. 2019Scalable Nearest Neighbor Search for Optimal Transportcited by 25
  12. 2013Beyond Locality-Sensitive Hashingcited by 23
  13. 2014On Symmetric and Asymmetric LSHs for Inner Product Searchcited by 23
  14. 2020Solving Tall Dense Linear Programs in Nearly Linear Timecited by 21
  15. 2017Towards Black-box Iterative Machine Teachingcited by 20
  16. 2016Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighborscited by 18
  17. 2021Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimizationcited by 18
  18. 2014Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)cited by 15
  19. 2015An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completioncited by 15
  20. 2017Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Ballscited by 15
  21. 2021Accelerating SLIDE Deep Learning on Modern CPUs: Vectorization, Quantizations, Memory Optimizations, and Morecited by 15
  22. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  23. 2017A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfecited by 13
  24. 2018On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Productcited by 12
  25. 2019SANNS: Scaling Up Secure Approximate k-Nearest Neighbors Searchcited by 12
  26. 2016A Greedy Approach for Budgeted Maximum Inner Product Searchcited by 11
  27. 2020Bipartite Matching in Nearly-linear Time on Moderately Dense Graphscited by 11
  28. 2020Scaling up Kernel Ridge Regression via Locality Sensitive Hashingcited by 9
  29. 2021Linear Bandit Algorithms with Sublinear Time Complexitycited by 9
  30. 2018Norm-Ranging LSH for Maximum Inner Product Searchcited by 8
  31. 2018Navigating with Graph Representations for Fast and Scalable Decoding of Neural Language Modelscited by 7
  32. 2020A Statistical Perspective on Coreset Density Estimationcited by 6
  33. 2020Climbing the WOL: Training for Cheaper Inferencecited by 5
  34. 2018Approximate Nearest Neighbors in Limited Spacecited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 8; 2023: 9; 2024: 1; 2025: 0; 2026: 1.

19 papers.

Sort:

By area:

  1. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  2. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  3. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  4. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  5. 2022A Sublinear Adversarial Training Algorithmcited by 22
  6. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  7. 2022Dynamic Tensor Product Regressioncited by 17
  8. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  9. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  10. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  11. 2023Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterationscited by 8
  12. 2022Sublinear Time Algorithm for Online Weighted Bipartite Matchingcited by 7
7 more
  1. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  2. 2022Dynamic Maintenance of Kernel Density Estimation Data Structure: From Practice to Theorycited by 6
  3. 2022DIVISION: Memory Efficient Training via Dual Activation Precisioncited by 4
  4. 2026Scout Before You Attend: Sketch-and-Walk Sparse Attention for Efficient LLM Inferencecited by 4
  5. 2022Faster Maximum Inner Product Search in High Dimensionscited by 3
  6. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  7. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0