Recently, the question of adversarially robust streaming, where the stream is
allowed to depend on the randomness of the streaming algorithm, has gained a
lot of attention. In this work, we consider a strong white-box adversarial
model (Ajtai et al. PODS 2022), in which the adversary has access to all past
random coins and the parameters used by the streaming algorithm. We focus on
the sparse recovery problem and extend our result to other tasks such as
distinct element estimation and low-rank approximation of matrices and tensors.
The main drawback of previous work is that it requires a random oracle, which
is especially problematic in the streaming model since the amount of randomness
is counted in the space complexity of a streaming algorithm. Also, the previous
work suffers from large update time. We construct a near-optimal solution for
the sparse recovery problem in white-box adversarial streams, based on the
subexponentially secure Learning with Errors assumption. Importantly, our
solution does not require a random oracle and has a polylogarithmic per item
processing time. We also give results in a related white-box adversarially
robust distributed model. Our constructions are based on homomorphic encryption
schemes satisfying very mild structural properties that are currently satisfied
by most known schemes.

在白盒对抗流媒体领域，本文构建了近乎最优的方案，解决了稀疏恢复问题，在其他任务中也有应用，如不同元素估计和矩阵与张量的低秩逼近问题。

快速白盒对抗流式处理

Fast White-Box Adversarial Streaming Without a Random Oracle

We propose and analyze an efficient algorithm for solving the joint sparse
recovery problem using a new regularization-based method, named orthogonally
weighted $\ell_{2,1}$ ($\mathit{ow}\ell_{2,1}$), which is specifically designed
to take into account the rank of the solution matrix. This method has
applications in feature extraction, matrix column selection, and dictionary
learning, and it is distinct from commonly used $\ell_{2,1}$ regularization and
other existing regularization-based approaches because it can exploit the full
rank of the row-sparse solution matrix, a key feature in many applications. We
provide a proof of the method's rank-awareness, establish the existence of
solutions to the proposed optimization problem, and develop an efficient
algorithm for solving it, whose convergence is analyzed. We also present
numerical experiments to illustrate the theory and demonstrate the
effectiveness of our method on real-life problems.

我们提出并分析了一种高效的算法，用于解决联合稀疏恢复问题，采用一种名为正交加权 ℓ2,1 （owℓ2,1）的新的正则化方法，专门设计用于考虑解矩阵的秩。该方法在特征提取、矩阵列选择和词典学习等方面有应用，与常用的 ℓ2,1 正则化和其他现有的正则化方法不同，因为它可以利用行稀疏解矩阵的完全秩，这是许多应用中的关键特性。我们提供了该方法秩感知性质的证明，建立了所提优化问题的解的存在性，并开发了一个高效的算法来求解该问题，并对其收敛性进行了分析。我们还展示了数值实验，以说明理论并展示我们的方法在实际问题上的有效性。