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.

通过分析统计杠杆的反演问题，我们研究了杠杆得分的分布与模型参数的关系，提出了解决回归问题的非凸优化算法，包括梯度下降和牛顿法，从而为统计杠杆的研究在解释、数据恢复和安全等领域开辟了新的应用。

如何逆转杠杆得分分布？

How to Inverting the Leverage Score Distribution?

We propose a sampling-based method for computing the tensor ring (TR)
decomposition of a data tensor. The method uses leverage score sampled
alternating least squares to fit the TR cores in an iterative fashion. By
taking advantage of the special structure of TR tensors, we can efficiently
estimate the leverage scores and attain a method which has complexity sublinear
in the number of input tensor entries. We provide high-probability
relative-error guarantees for the sampled least squares problems. We compare
our proposal to existing methods in experiments on both synthetic and real
data. Our method achieves substantial speedup -- sometimes two or three orders
of magnitude -- over competing methods, while maintaining good accuracy. We
also provide an example of how our method can be used for rapid feature
extraction.

本文提出了一种基于采样的、使用杠杆分数样本交替最小二乘法的张量环分解计算方法，其中利用张量环张量的特殊结构，可高效地评估杠杆分数并获得复杂度次线性的方法，该方法在合成数据和真实数据实验中与现有方法相比具有显著加速效果，同时保持良好的准确性，提供了一个快速特征提取的示例。

张量环分解的基于采样的方法

A Sampling-Based Method for Tensor Ring Decomposition

Finding a small spectral approximation for a tall $n \times d$ matrix $A$ is
a fundamental numerical primitive. For a number of reasons, one often seeks an
approximation whose rows are sampled from those of $A$. Row sampling improves
interpretability, saves space when $A$ is sparse, and preserves row structure,
which is especially important, for example, when $A$ represents a graph.
However, correctly sampling rows from $A$ can be costly when the matrix is
large and cannot be stored and processed in memory. Hence, a number of recent
publications focus on row sampling in the streaming setting, using little more
space than what is required to store the outputted approximation [KL13,
KLM+14].
Inspired by a growing body of work on online algorithms for machine learning
and data analysis, we extend this work to a more restrictive online setting: we
read rows of $A$ one by one and immediately decide whether each row should be
kept in the spectral approximation or discarded, without ever retracting these
decisions. We present an extremely simple algorithm that approximates $A$ up to
multiplicative error $\epsilon$ and additive error $\delta$ using $O(d \log d
\log(\epsilon||A||_2/\delta)/\epsilon^2)$ online samples, with memory overhead
proportional to the cost of storing the spectral approximation. We also present
an algorithm that uses $O(d^2$) memory but only requires
$O(d\log(\epsilon||A||_2/\delta)/\epsilon^2)$ samples, which we show is
optimal.
Our methods are clean and intuitive, allow for lower memory usage than prior
work, and expose new theoretical properties of leverage score based matrix
approximation.

本研究提出了基于杠杆得分的矩阵逼近的简洁、直观的在线算法，允许比以前的工作更低的内存使用，并暴露了新的理论性质。