論文の概要: Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions
- arxiv url: http://arxiv.org/abs/2309.11657v2
- Date: Wed, 27 Sep 2023 20:57:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 19:39:40.420782
- Title: Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions
- Title（参考訳）: 乱れを伴う一般化線形モデルに対する分布非依存回帰
- Authors: Ilias Diakonikolas, Sushrut Karmalkar, Jongho Park, Christos Tzamos
- Abstract要約: 一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
- 参考スコア（独自算出の注目度）: 49.69852011882769
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
- Abstract（参考訳）: 一般化線形モデル (glms) の回帰問題に対して, 付加的オブリベート雑音の存在下で最初のアルゴリズムを提示する。
例の$(x, ) へのサンプルアクセスがあると仮定します。
y)$ ここで$y$は$g(w^* \cdot のノイズ測定である
x)$。
特に、new{the noisy labels は $y = g(w^* \cdot である。
x) + \xi + \epsilon$, where $\xi$ は$x$ \new{and satisfies} $\Pr[\xi = 0] \geq o(1)$, $\epsilon \sim \mathcal N(0, \sigma^2)$ から独立に引かれる難聴ノイズである。
我々のゴールは、$g(w \cdot) 関数が $new{parameter vector $w$ を正確に回復することである。
x)$ \new{has} 真の値 $g(w^* \cdot と比較して任意に小さな誤差
x)$, 騒がしい測定値が$y$ではなく$である。
我々は、最も一般的な分布非依存な設定で \new{this} 問題に取り組むアルゴリズムを提示し、解が \new{even} を同定できない可能性がある。
new{Our} アルゴリズムは、その解が特定可能であれば、解のnew{an 正確な推定を返し、そうでなければ候補の小さなリストを返し、そのうちの1つは真の解に近い。
さらに、new{provide} は、幅広い設定で保持される識別可能性に対して必要かつ十分な条件である。
\new{Specifically,} 問題は、$\xi + \epsilon = 0$ の量子が知られているときや、仮説の族が翻訳された $g(w^* \cdot にほぼ等しい候補を含まないときである。
x) + a$ ある実数に対して$a$ である一方で、$g(w^* \cdot と比較すると大きな誤差がある。
x)$。
これは glm 回帰 \new{with oblivious noise} に対する最初の \new{algorithmic} の結果であり、サンプルの半分以上が任意に破損している。
以前の研究は主に線形回帰の設定に集中し、制限的な仮定の下でアルゴリズムを与えた。
関連論文リスト
- Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳（メタデータ） (2024-02-22T02:20:24Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。