論文の概要: Hard labels sampled from sparse targets mislead rotation invariant algorithms
- arxiv url: http://arxiv.org/abs/2603.20967v1
- Date: Sat, 21 Mar 2026 22:38:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-24 19:11:39.171784
- Title: Hard labels sampled from sparse targets mislead rotation invariant algorithms
- Title（参考訳）: スパースターゲットの不正回転不変アルゴリズムからサンプリングされたハードラベル
- Authors: Avrajit Ghosh, Bin Yu, Manfred Warmuth, Peter Bartlett,
- Abstract要約: バイナリロジスティック回帰では、フィードバックはデータの真の条件付き確率に対応するソフトラベルか、あるいはハードラベルをサンプリングすることができる。
条件分布$(mathbfx_itopmathbfwstar)$と$mathbfwstar$が$s$-sparseである場合、回転不変アルゴリズムは確実に準最適であることを示す。
- 参考スコア（独自算出の注目度）: 6.565070116874382
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: One of the most common machine learning setups is logistic regression. In many classification models, including neural networks, the final prediction is obtained by applying a logistic link function to a linear score. In binary logistic regression, the feedback can be either soft labels, corresponding to the true conditional probability of the data (as in distillation), or sampled hard labels (taking values $\pm 1$). We point out a fundamental problem that arises even in a particularly favorable setting, where the goal is to learn a noise-free soft target of the form $σ(\mathbf{x}^{\top}\mathbf{w}^{\star})$. In the over-constrained case (i.e. the number of samples $n$ exceeds the input dimension $d$) with examples $(\mathbf{x}_i,σ(\mathbf{x}_i^{\top}\mathbf{w}^{\star}))$, it is sufficient to recover $\mathbf{w}^{\star}$ and hence achieve the Bayes risk. However, we prove that when the examples are labeled by hard labels $y_i$ sampled from the same conditional distribution $σ(\mathbf{x}_i^{\top}\mathbf{w}^{\star})$ and $\mathbf{w}^{\star}$ is $s$-sparse, then rotation-invariant algorithms are provably suboptimal: they incur an excess risk $Ω\!\left(\frac{d-1}{n}\right)$, while there are simple non-rotation invariant algorithms with excess risk $O(\frac{s\log d}{n})$. The simplest rotation invariant algorithm is gradient descent on the logistic loss (with early stopping). A simple non-rotation-invariant algorithm for sparse targets that achieves the above upper bounds uses gradient descent on the weights $u_i,v_i$, where now the linear weight $w_i$ is reparameterized as $u_iv_i$.
- Abstract（参考訳）: 最も一般的な機械学習のセットアップの1つは、ロジスティック回帰である。
ニューラルネットワークを含む多くの分類モデルにおいて、最終予測は、線形スコアにロジスティックリンク関数を適用することによって得られる。
バイナリロジスティック回帰では、フィードバックは、(蒸留のように)データの真の条件付き確率に対応するソフトラベルか、(値が$\pm 1$になる)ハードラベルのどちらかである。
特に有利な環境でも生じる根本的な問題は、目的は、$σ(\mathbf{x}^{\top}\mathbf{w}^{\star})$という形の雑音のないソフトターゲットを学ぶことである。
過制約の場合(つまり、サンプル数$n$は入力次元$d$を超える)、例えば$(\mathbf{x}_i,σ(\mathbf{x}_i^{\top}\mathbf{w}^{\star})$は$\mathbf{w}^{\star}$を回復してベイズリスクを達成するのに十分である。
しかし、同じ条件分布$σ(\mathbf{x}_i^{\top}\mathbf{w}^{\star})$と$\mathbf{w}^{\star}$が$s$スパースであれば、回転不変アルゴリズムは証明可能サブ最適である。
\left(\frac{d-1}{n}\right)$, しかし、過剰リスク$O(\frac{s\log d}{n})$の単純な非回転不変アルゴリズムが存在する。
最も単純な回転不変アルゴリズムは(早期停止を伴う)ロジスティック損失の勾配降下である。
上述の上限を達成したスパース目標に対する単純な非回転不変アルゴリズムは、重み$u_i,v_i$の勾配勾配を用いており、ここでは線形重み$w_i$を$u_iv_i$として再パラメータ化する。
関連論文リスト
- Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳（メタデータ） (2023-02-27T16:34:21Z) - 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) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - On the Power of Preconditioning in Sparse Linear Regression [24.140675945592704]
プレコンディショニングされたラッソは、大まかな線形回帰問題をほぼ最適に解くことができることを示す。
最適条件のラッソに対して証明が難しいランダム設計のインスタンスを初めて構築する。
論文 参考訳（メタデータ） (2021-06-17T02:12:01Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。