論文の概要: 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$ノンゼロ成分を漸進的に学習できることを示した。 より広範に、我々の研究は、重み付き分布と敵の腐敗の存在下で、段階的な方法の漸進的な学習現象を初めて明らかにした。

関連論文リスト

• Causality-aligned Prompt Learning via Diffusion-based Counterfactual Generation [45.395353088233556]
  理論的には、$textbfDi$ffusion-based $textbfC$ounterf$textbfa$ctual $textbfp$rompt学習フレームワークを導入します。 本手法は,画像分類,画像テキスト検索,視覚的質問応答などのタスクにおいて,特に目に見えないカテゴリにおいて優れた優位性を示す。
  論文  参考訳（メタデータ） (2025-07-26T09:27:52Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Adversarial learning for nonparametric regression: Minimax rate and adaptive estimation [3.244945627960733]
  逆数$L_risks と $1 leq leq infty$ の最小収束率を確立し、極大最適性を達成する部分的局所推定器を提案する。 我々は、対数係数の中で、非対数クラスと対数クラスの広い範囲で最適な速度を達成することが示されるデータ駆動適応推定器を構築する。
  論文  参考訳（メタデータ） (2025-06-02T02:38:47Z)
• The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination [13.980910832909906]
  低次数で近似できる任意の関数クラスは、有界汚染下で効率的に学習できることを示す。 固定対数対数分布に対するハーフ空間の関数に対する耐久性試験可能学習のための最初の効率的なアルゴリズムを得る。
  論文  参考訳（メタデータ） (2025-05-26T16:17:48Z)
• Robust Representation Consistency Model via Contrastive Denoising [83.47584074390842]
  ランダムな平滑化は、敵の摂動に対する堅牢性を証明する理論的保証を提供する。 拡散モデルは、ノイズ摂動サンプルを浄化するためにランダムな平滑化に成功している。 我々は,画素空間における拡散軌跡に沿った生成的モデリングタスクを,潜在空間における識別的タスクとして再構成する。
  論文  参考訳（メタデータ） (2025-01-22T18:52:06Z)
• 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)
• Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates [7.21848268647674]
  我々は、決定のための$varepsilon$-greedybanditアルゴリズムと、疎帯域パラメータを推定するためのハードしきい値アルゴリズムを統合する。 マージン条件下では、我々の手法は、$O(T1/2)$ regret あるいは古典的な$O(T1/2)$-consistent推論のいずれかを達成する。
  論文  参考訳（メタデータ） (2024-11-10T01:47:11Z)
• 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)
• Do PAC-Learners Learn the Marginal Distribution? [19.54058590042626]
  PAC Learning の基本定理は、概念クラス $H$ の学習可能性は$H$ における経験的エラーの $textituniform convergence$ と等価であると主張している。 この研究は、PAC学習、一様収束、分布自由設定を超えた密度推定の関連を再考する。
  論文  参考訳（メタデータ） (2023-02-13T11:42:58Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。 本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。 この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
  論文  参考訳（メタデータ） (2022-09-16T09:38:38Z)
• 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)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• 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)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• 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)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。