Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions-猫眼课题宝

DOI：

10.48550/arxiv.2309.11657

发表时间：

2023-09

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Ilias Diakonikolas;Sushrut Karmalkar;Jongho Park;Christos Tzamos

我们证明了在存在添加剂忽略噪声的情况下，通用线性模型（GLM）回归问题的第一算法。我们假设我们有示例访问示例$（x，y）$，其中$ y $是$ g（w^* \ cdot x）$的嘈杂度量。特别是，\ new {嘈杂的标签是} $ y = g（w^* \ cdot x） + \ xi + \ epsilon $，其中$ \ xi $是独立于$ x $ \ \ \ new {和满足} $ \ pr [\ xi = 0] \ geq o（1）$和$ \ epsilon \ sim \ Mathcal n（0，\ sigma^2）$。我们的目标是准确恢复一个\ new {parameter vector $ w $，以便}函数$ g（w \ cdot x）$ \ new {at new {at}与真实值相比，任意小错误$ g（w^* \） cdot x）$，而不是嘈杂的测量$ y $。我们提出了一种算法，该算法在其最一般的与分布无关的设置中解决了\ new {this}问题，在该设置中，解决方案可能无法识别\ new {偶}。 \ new {我们的}算法返回\ new {如果可以识别的解决方案的准确估计}，则否则返回了一小部分候选人列表，其中之一靠近True解决方案。此外，我们\ new {提供}是可识别性的必要条件，可以在广泛的环境中。当$ \ xi + \ epsilon = 0 $的分位数或假设家族不包含几乎等于翻译的$ g（w^*）时\ cdot x） + a $对于某些实际数字$ a $，而与$ g（w^* \ cdot x）$相比，也有很大的错误。这是GLM回归\ new {带有忽略的噪声}的第一个\ new {algorithmic}结果，它可以处理任意损坏的一半以上的样本。先前的工作主要集中在线性回归的设置上，并在限制性假设下给出了算法。

We demonstrate the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We assume we have sample access to examples $(x, y)$ where $y$ is a noisy measurement of $g(w^* \cdot x)$. In particular, \new{the noisy labels are of the form} $y = g(w^* \cdot x) + \xi + \epsilon$, where $\xi$ is the oblivious noise drawn independently of $x$ \new{and satisfies} $\Pr[\xi = 0] \geq o(1)$, and $\epsilon \sim \mathcal N(0, \sigma^2)$. Our goal is to accurately recover a \new{parameter vector $w$ such that the} function $g(w \cdot x)$ \new{has} arbitrarily small error when compared to the true values $g(w^* \cdot x)$, rather than the noisy measurements $y$. We present an algorithm that tackles \new{this} problem in its most general distribution-independent setting, where the solution may not \new{even} be identifiable. \new{Our} algorithm returns \new{an accurate estimate of} the solution if it is identifiable, and otherwise returns a small list of candidates, one of which is close to the true solution. Furthermore, we \new{provide} a necessary and sufficient condition for identifiability, which holds in broad settings. \new{Specifically,} the problem is identifiable when the quantile at which $\xi + \epsilon = 0$ is known, or when the family of hypotheses does not contain candidates that are nearly equal to a translated $g(w^* \cdot x) + A$ for some real number $A$, while also having large error when compared to $g(w^* \cdot x)$. This is the first \new{algorithmic} result for GLM regression \new{with oblivious noise} which can handle more than half the samples being arbitrarily corrupted. Prior work focused largely on the setting of linear regression, and gave algorithms under restrictive assumptions.

Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions

文献摘要

相似文献