What guarantees are possible for solving logistic regression in one pass over
a data stream? To answer this question, we present the first data oblivious
sketch for logistic regression. Our sketch can be computed in input sparsity
time over a turnstile data stream and reduces the size of a $d$-dimensional
data set from $n$ to only $\operatorname{poly}(\mu d\log n)$ weighted points,
where $\mu$ is a useful parameter which captures the complexity of compressing
the data. Solving (weighted) logistic regression on the sketch gives an $O(\log
n)$-approximation to the original problem on the full data set. We also show
how to obtain an $O(1)$-approximation with slight modifications. Our sketches
are fast, simple, easy to implement, and our experiments demonstrate their
practicality.

本文提出了第一个数据无感知草图，并介绍了可以在输入稀疏时间内计算的方法来解决逻辑回归问题，从而大大减小了数据集的大小和复杂度，实验表明这种方法是可行和实用的。

逻辑回归的遗忘素描

Oblivious sketching for logistic regression

The tensor Singular Value Decomposition (t-SVD) for third order tensors that
was proposed by Kilmer and Martin~\cite{2011kilmer} has been applied
successfully in many fields, such as computed tomography, facial recognition,
and video completion. In this paper, we propose a method that extends a
well-known randomized matrix method to the t-SVD. This method can produce a
factorization with similar properties to the t-SVD, but is more computationally
efficient on very large datasets. We present details of the algorithm,
theoretical results, and provide numerical results that show the promise of our
approach for compressing and analyzing datasets. We also present an improved
analysis of the randomized subspace iteration for matrices, which may be of
independent interest to the scientific community.

本文介绍了一种利用随机矩阵方法扩展张量 SVD 来压缩和分析数据集的方法，相对于 t-SVD，具有更高的计算效率，并提供了该算法的详细说明和数值结果。