Online Lewis Weight Sampling

doi:10.1145/3715127

Online Lewis Weight Sampling

2025-10-01

0

PRE

AI

DOI：10.1145/3715127

原文求助

摘要

En 中文

科恩和彭（STOC 2015）的开创性工作将刘易斯权重采样引入理论计算机科学领域，该方法可生成用于近似l(p)中d维子空间的快速行采样算法，误差不超过(1 + epsilon)的相对误差。先前的工作已将这一重要基元扩展到其他场景，例如在线核心集和滑动窗口模型。然而，这些结果仅适用于p属于{1, 2}的情况，且p = 1的结果需要次优的O(d²/a²)样本。在本工作中，我们设计了在线核心集和滑动窗口模型中针对所有p属于(0, ∞)的第一个近似最优Yp子空间嵌入。在这两种模型中，我们的算法在p属于(0, 2)时存储O(d/epsilon²)行，在p属于(2, ∞)时存储O(d(p/2)/epsilon²)行。这回答了布拉沃曼等人（2020年）主要开放问题的一个实质性推广，首次给出了所有p属于/ {1, 2}的结果，并为所有p实现了近似最优的样本复杂度。为了得到这一结果，我们首次分析了单次刘易斯权重采样，即按刘易斯权重比例采样行，该方法对于p > 2的样本复杂度为O(d(p/2)/epsilon²)行。此前，此类采样方案的样本复杂度仅知为O(d(p/2)/epsilon⁵)，而若使用更复杂的递归采样算法，则可知O(d(p/2)/epsilon²)的界。注意，递归采样策略无法在在线设置中实现，因此有必要分析单次刘易斯权重采样。或许令人意外的是，我们的分析关键性地使用了一种新颖的在线数值线性代数联系，即使对于离线刘易斯权重采样也是如此。作为应用，我们获得了（1 + epsilon）近似重要广义线性模型（如逻辑回归和p-概率回归）的第一个在线核心集算法。我们的上界由蒙特亚努等人（2021年）引入的复杂度参数μ参数化，我们还提供了第一个下界，表明对μ的线性依赖是必要的。

Keyword:

Lewis weights

Online coresets

Subspace embeddings

Online Lewis Weight Sampling

摘要

期刊

机构

引用论文