mlsanityData to 14 Oct 2026

How to Inverting the Leverage Score Distribution?

arXiv 2404.13785 ↗First posted 21 Apr 2024cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

Leverage score is a fundamental problem in machine learning and theoretical computer science. It has extensive applications in regression analysis, randomized algorithms, and neural network inversion. Despite leverage scores are widely used as a tool, in this paper, we study a novel problem, namely the inverting leverage score problem. We analyze to invert the leverage score distributions back to recover model parameters. Specifically, given a leverage score σ ∈ ℝn, the matrix A ∈ ℝn × d, and the vector b ∈ ℝn, we analyze the non-convex optimization problem of finding x ∈ ℝd to minimize | diag( σ ) - In circ (A(x) (A(x)^top A(x) )-1 A(x)^top ) |F, where A(x):= S(x)-1 A ∈ ℝn × d , S(x) := diag(s(x)) ∈ ℝn × n and s(x) : = Ax - b ∈ ℝn. Our theoretical studies include computing the gradient and Hessian, demonstrating that the Hessian matrix is positive definite and Lipschitz, and constructing first-order and second-order algorithms to solve this regression problem. Our work combines iterative shrinking and the induction hypothesis to ensure global convergence rates for the Newton method, as well as the properties of Lipschitz and strong convexity to guarantee the performance of gradient descent. This important study on inverting statistical leverage opens up numerous new applications in interpretation, data recovery, and security.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 29 of its 85 references that are in the map. First posted on arXiv 21 Apr 2024.

Builds on

29 of 85 references.

References · 29

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  3. 2013Intriguing properties of neural networkscited by 5,155
  4. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,517
  5. 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 864
  6. 2017Detecting Adversarial Samples from Artifactscited by 245
  7. 2017On the (Statistical) Detection of Adversarial Examplescited by 180
  8. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  9. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  10. 2021Targeted Attack against Deep Neural Networks via Flipping Limited Weight Bitscited by 49
  11. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  12. 2017Relative Error Tensor Low Rank Approximationcited by 45
17 more
  1. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  2. 2022A Faster Small Treewidth SDP Solvercited by 36
  3. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  4. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  5. 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
  6. 2020Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matchingcited by 14
  7. 2021Fast Statistical Leverage Score Approximation in Kernel Ridge Regressioncited by 14
  8. 2023Faster Algorithms for Structured Linear and Kernel Support Vector Machinescited by 13
  9. 2023A Unified Scheme of ResNet and Softmaxcited by 12
  10. 2018Distributed Adaptive Sampling for Kernel Matrix Approximationcited by 9
  11. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  12. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  13. 2023Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regressioncited by 9
  14. 2017Leverage Score Sampling for Faster Accelerated Regression and ERMcited by 7
  15. 2023Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameterscited by 7
  16. 2023Faster Rectangular Matrix Multiplication by Combination Loss Analysiscited by 5
  17. 2018Towards A Unified Analysis of Random Fourier Featurescited by 1

Built on by

Cited by year

Citing papers per year: 2024: 3; 2025: 2.

5 papers.

  1. 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32
  2. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  3. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  4. 2024Inverting the Leverage Score Gradient: An Efficient Approximate Newton Methodcited by 3
  5. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2