論文の概要: Sparse Mean Estimation in Adversarial Settings via Incremental Learning
- arxiv url: http://arxiv.org/abs/2305.15276v3
- Date: Mon, 25 Aug 2025 02:33:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-26 12:26:22.485462
- Title: Sparse Mean Estimation in Adversarial Settings via Incremental Learning
- Title（参考訳）: インクリメンタルラーニングによる対向的設定におけるスパース平均推定
- Authors: Jianhao Ma, Rui Ray Chen, Yinghui He, Salar Fattahi, Wei Hu,
- Abstract要約: 本稿では,重み付き分布と対向汚職の存在下で,スパース平均推定を学習するためのスケーラブルな手法を提案する。
提案手法は,情報理論の下界に適合する最適統計率を実現する。
より広範に、我々の研究は、重み付き分布と敵対的腐敗の存在下で、過渡的手法の漸進的な学習現象を初めて明らかにした。
- 参考スコア（独自算出の注目度）: 20.522038784234947
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the problem of sparse mean estimation under adversarial corruptions, where the goal is to estimate the $k$-sparse mean of a heavy-tailed distribution from samples contaminated by adversarial noise. Existing methods face two key limitations: they require prior knowledge of the sparsity level $k$ and scale poorly to high-dimensional settings. We propose a simple and scalable estimator that addresses both challenges. Specifically, it learns the $k$-sparse mean without knowing $k$ in advance and operates in near-linear time and memory with respect to the ambient dimension. Under a moderate signal-to-noise ratio, our method achieves the optimal statistical rate, matching the information-theoretic lower bound. Extensive simulations corroborate our theoretical guarantees. At the heart of our approach is an incremental learning phenomenon: we show that a basic subgradient method applied to a nonconvex two-layer formulation with an $\ell_1$-loss can incrementally learn the $k$ nonzero components of the true mean while suppressing the rest. More broadly, our work is the first to reveal the incremental learning phenomenon of the subgradient method in the presence of heavy-tailed distributions and adversarial corruption.
- Abstract（参考訳）: 本稿では, 対向騒音による汚染試料からの重み付き分布の$k$-sparse平均を推定することを目的とした, 対向汚損下でのスパース平均推定問題について検討する。
既存のメソッドは2つの重要な制限に直面している。それらはスパーシティレベルに関する事前の知識を$k$で要求し、高次元設定ではスケールが不十分である。
両課題に対処するシンプルでスケーラブルな推定器を提案する。
具体的には、事前に$k$を知ることなく$k$-sparse平均を学習し、周囲の次元に関してほぼ直線的な時間とメモリで動作する。
中程度の信号対雑音比では,情報理論の下界と一致する最適統計率が得られる。
大規模なシミュレーションは我々の理論的な保証を裏付ける。
我々のアプローチの核心は漸進的な学習現象である:我々は、$\ell_1$-lossで非凸二層定式化に適用された基本的な段階的手法が、残りを抑えつつ、真の平均の$k$ノンゼロ成分を漸進的に学習できることを示した。
より広範に、我々の研究は、重み付き分布と敵の腐敗の存在下で、段階的な方法の漸進的な学習現象を初めて明らかにした。
関連論文リスト
- Entangled Mean Estimation in High-Dimensions [36.97113089188035]
信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。
最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
論文 参考訳（メタデータ） (2025-01-09T18:31:35Z) - Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares [4.335413713700667]
我々は citekothari2018robust で導入された正準平方和プログラムを新たに解析する。
このプログラムは,すべての $varepsilon に対して[0,frac12)$ の誤差率を効率よく達成できることを示す。
論文 参考訳（メタデータ） (2024-11-21T16:57:05Z) - Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data [3.1138411427556445]
測定制約のある問題では、大きなデータセットが利用可能であるにもかかわらず、大きなデータセットのごく一部でラベルを観測するのに手頃な価格にしかならない。
このことは、どのデータポイントが予算制約のあるラベルに最も有益であるかという重要な疑問を引き起こします。
本稿では,測定制約付きM推定フレームワークにおける最適個別化しきい値の推定に焦点をあてる。
論文 参考訳（メタデータ） (2024-11-21T00:21:17Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Robust Nonparametric Regression under Poisoning Attack [13.470899588917716]
敵攻撃者は、$N$のトレーニングデータセットから最大$q$のサンプル値を変更することができる。
初期解法はハマー損失最小化に基づくM推定器である。
最後の見積もりは、任意の$q$に対してほぼ最小値であり、最大$ln N$ factorまでである。
論文 参考訳（メタデータ） (2023-05-26T09:33:17Z) - List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。
本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文 参考訳（メタデータ） (2022-05-28T05:13:45Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Learning Minimax Estimators via Online Learning [55.92459567732491]
確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。
混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
論文 参考訳（メタデータ） (2020-06-19T22:49:42Z) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。