用高阶矩提升批量鲁棒线性回归，大幅降低对数据量和误差的要求。
Batch List-Decodable Linear Regression via Higher Moments
- 基于高阶矩与SoS证明框架，结合迭代与列表修剪策略。
- 仅需n ≥ Ω_δ(α^{-δ})的批量大小，误差降至O(α^{-δ/2}/√n)。
- 适用于高噪声下小批量数据的可靠回归，适合稳健学习研究者。
研究在批量设置下的列表可解线性回归问题。一批次若由来自未知线性回归分布的独立同分布样本组成，则称其为干净批次。对于参数α∈(0,1/2)，未知α比例的批次是干净的，其余批次无任何假设。目标是输出一个小型向量列表，其中至少有一个在ℓ₂范数上接近真实回归向量。[DJKS23] 在自然分布假设下提出高效算法，要求批大小n≥~Ω(α⁻¹)，批次数m=poly(d,n,1/α)，可在多项式时间内输出大小为O(1/α²)的列表，其中至少一个向量与目标距离为~O(α⁻¹/²/√n)。本文设计新算法，在协变量分布低阶矩为Sum-of-Squares(SoS)可证有界的假设下，对任意常数δ>0，只要批大小n≥Ω_δ(α⁻δ)，且度数Θ(1/δ)的矩为SoS可证有界，即可用m=poly((dn)^{1/δ},1/α)个批次，多项式时间运行，并输出大小为O(1/α)的列表，其中至少一个向量与目标距离为O(α^{-δ/2}/√n)。该算法显著降低最小批大小与最终误差，同时实现最优列表大小。方法通过巧妙结合SoS范式、迭代机制与新型列表修剪程序，利用高阶矩信息；过程中还给出了可能具更广泛应用的Marcinkiewicz-Zygmund不等式的SoS证明。
原文摘要 · Abstract (English)
We study the task of list-decodable linear regression using batches. A batch is called clean if it consists of i.i.d. samples from an unknown linear regression distribution. For a parameter $α\in (0, 1/2)$, an unknown $α$-fraction of the batches are clean and no assumptions are made on the remaining ones. The goal is to output a small list of vectors at least one of which is close to the true regressor vector in $\ell_2$-norm. [DJKS23] gave an efficient algorithm, under natural distributional assumptions, with the following guarantee. Assuming that the batch size $n$ satisfies $n \geq \tildeΩ(α^{-1})$ and the number of batches is $m = \mathrm{poly}(d, n, 1/α)$, their algorithm runs in polynomial time and outputs a list of $O(1/α^2)$ vectors at least one of which is $\tilde{O}(α^{-1/2}/\sqrt{n})$ close to the target regressor. Here we design a new polynomial time algorithm with significantly stronger guarantees under the assumption that the low-degree moments of the covariates distribution are Sum-of-Squares (SoS) certifiably bounded. Specifically, for any constant $δ>0$, as long as the batch size is $n \geq Ω_δ(α^{-δ})$ and the degree-$Θ(1/δ)$ moments of the covariates are SoS certifiably bounded, our algorithm uses $m = \mathrm{poly}((dn)^{1/δ}, 1/α)$ batches, runs in polynomial-time, and outputs an $O(1/α)$-sized list of vectors one of which is $O(α^{-δ/2}/\sqrt{n})$ close to the target. That is, our algorithm achieves substantially smaller minimum batch size and final error, while achieving the optimal list size. Our approach uses higher-order moment information by carefully combining the SoS paradigm interleaved with an iterative method and a novel list pruning procedure. In the process, we give an SoS proof of the Marcinkiewicz-Zygmund inequality that may be of broader applicability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。