mlsanityData to 7 Oct 2026

Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration

arXiv 2305.08367 ↗First posted 15 May 2023cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

Submodular function maximization is a critical building block for diverse tasks, such as document summarization, sensor placement, and image segmentation. Yet its practical utility is often limit by the O(knd2) computational bottleneck. In this paper, we propose an integrated framework that addresses efficiency and privacy simultaneously. First, we introduce a novel matrix-based computation paradigm that accelerates function evaluations. Second, we develop approximate data structures that further streamline the optimization process, achieving a theoretical complexity of O(ε-2(nd+kn+kd2)log(k/δ)). Third, we integrate (ε, δ)-DP guaranties to address the privacy concerns inherent in sensitive optimization tasks.

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

Builds on

38 of 94 references.

References · 38

  1. 2023How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacycited by 150
  2. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  3. 2014Lazier Than Lazy Greedycited by 97
  4. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  5. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  6. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  7. 2020A Refined Laser Method and Faster Matrix Multiplicationcited by 56
  8. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  9. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  10. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  11. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  12. 2015Optimal Data-Dependent Hashing for Approximate Near Neighborscited by 43
26 more
  1. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  2. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  3. 2022A Faster Small Treewidth SDP Solvercited by 36
  4. 2018Online Continuous Submodular Maximizationcited by 35
  5. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  6. 2014Near-Optimally Teaching the Crowd to Classifycited by 32
  7. 2018Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularitycited by 31
  8. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  9. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  10. 2022Faster Algorithm for Structured John Ellipsoid Computationcited by 28
  11. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  12. 2023Differentially Private Attention Computationcited by 25
  13. 2019A near-optimal algorithm for approximating the John Ellipsoidcited by 23
  14. 2022Speeding Up Sparsification using Inner Product Search Data Structurescited by 22
  15. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  16. 2022A Sublinear Adversarial Training Algorithmcited by 22
  17. 2022Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenancecited by 22
  18. 2022Discrepancy Minimization in Input-Sparsity Timecited by 22
  19. 2016How to be Fair and Diverse?cited by 18
  20. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  21. 2023A General Algorithm for Solving Rank-one Matrix Sensingcited by 15
  22. 2022Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summationscited by 14
  23. 2019Categorical Feature Compression via Submodular Optimizationcited by 7
  24. 2022Uniform Approximations for Randomized Hadamard Transforms with Applicationscited by 7
  25. 2023Robust Algorithms on Adaptive Inputs from Bounded Adversariescited by 5
  26. 2016Submodular Variational Inference for Network Reconstructioncited by 2

Built on by

Cited by year

Citing papers per year: 2023: 8; 2024: 0; 2025: 3.

11 papers.

  1. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 805
  2. 2023Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Timecited by 247
  3. 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
  4. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  5. 2023A Unified Scheme of ResNet and Softmaxcited by 12
  6. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  7. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  8. 2023The Expressibility of Polynomial based Attention Schemecited by 7
  9. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 3
  10. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
  11. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1