  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 $\sigma \in \mathbb{R}^n$, the matrix $A \in \mathbb{R}^{n \times d}$,
and the vector $b \in \mathbb{R}^n$, we analyze the non-convex optimization
problem of finding $x \in \mathbb{R}^d$ to minimize $\| \mathrm{diag}( \sigma )
- I_n \circ (A(x) (A(x)^\top A(x) )^{-1} A(x)^\top ) \|_F$, where $A(x):=
S(x)^{-1} A \in \mathbb{R}^{n \times d} $, $S(x) := \mathrm{diag}(s(x)) \in
\mathbb{R}^{n \times n}$ and $s(x) : = Ax - b \in \mathbb{R}^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.
