首个可确定性构造ℓp子空间压缩的迭代算法，解决长期悬而未决的尺寸优化问题。
Deterministic Coreset for Lp Subspace
- 通过迭代保证每轮损失上下界，实现确定性ℓp子空间嵌入。
- 在ε误差下，核心集大小为O(d^{max{1,p/2}}/ε²)，消除长期存在的log因子。
- 适用于需要确定性保证的ℓp回归等场景，结果紧致最优。
本文提出首个用于构建ε-核心集的迭代算法，可对任意p∈[1,∞)和ε>0实现确定性ℓ_p子空间嵌入。给定一个满秩矩阵X∈ℝ^{n×d}（n≫d），若其子集矩阵X′∈ℝ^{m×d}满足：对任意向量q∈ℝ^d，有(1−ε)‖Xq‖_p^p ≤ ‖X′q‖_p^p ≤ (1+ε)‖Xq‖_p^p，则称X′为X的(ε,ℓ_p)-子空间嵌入。本文中，X′是X行的加权子集，即标准核心集。算法每轮确保维护集的损失在原始数据集损失的缩放范围内有上下界，从而获得确定性保证。对于误差参数ε，算法时间复杂度为O(poly(n,d,ε^{-1}))，返回的核心集大小为O(d^{max{1,p/2}}/ε²)，完全消除此前文献中的log因子，达到理论下界，为最优解。该核心集还可用于确定性近似求解ℓ_p回归问题。
原文摘要 · Abstract (English)
We introduce the first iterative algorithm for constructing a $\varepsilon$-coreset that guarantees deterministic $\ell_p$ subspace embedding for any $p \in [1,\infty)$ and any $\varepsilon > 0$. For a given full rank matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$ where $n \gg d$, $\mathbf{X}' \in \mathbb{R}^{m \times d}$ is an $(\varepsilon,\ell_p)$-subspace embedding of $\mathbf{X}$, if for every $\mathbf{q} \in \mathbb{R}^d$, $(1-\varepsilon)\|\mathbf{Xq}\|_{p}^{p} \leq \|\mathbf{X'q}\|_{p}^{p} \leq (1+\varepsilon)\|\mathbf{Xq}\|_{p}^{p}$. Specifically, in this paper, $\mathbf{X}'$ is a weighted subset of rows of $\mathbf{X}$ which is commonly known in the literature as a coreset. In every iteration, the algorithm ensures that the loss on the maintained set is upper and lower bounded by the loss on the original dataset with appropriate scalings. So, unlike typical coreset guarantees, due to bounded loss, our coreset gives a deterministic guarantee for the $\ell_p$ subspace embedding. For an error parameter $\varepsilon$, our algorithm takes $O(\mathrm{poly}(n,d,\varepsilon^{-1}))$ time and returns a deterministic $\varepsilon$-coreset, for $\ell_p$ subspace embedding whose size is $O\left(\frac{d^{\max\{1,p/2\}}}{\varepsilon^{2}}\right)$. Here, we remove the $\log$ factors in the coreset size, which had been a long-standing open problem. Our coresets are optimal as they are tight with the lower bound. As an application, our coreset can also be used for approximately solving the $\ell_p$ regression problem in a deterministic manner.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。