論文の概要: Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination

• arxiv url: http://arxiv.org/abs/2010.04157v3
• Date: Thu, 10 Jun 2021 22:54:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-09 11:49:22.105774
• Title: Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
• Title（参考訳）: オンラインと配布のないロバストネス:ハマー汚染を伴う回帰と文脈帯域
• Authors: Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau
• Abstract要約: 線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
• 参考スコア（独自算出の注目度）: 29.85468294601847
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we revisit two classic high-dimensional online learning problems, namely linear regression and contextual bandits, from the perspective of adversarial robustness. Existing works in algorithmic robust statistics make strong distributional assumptions that ensure that the input data is evenly spread out or comes from a nice generative model. Is it possible to achieve strong robustness guarantees even without distributional assumptions altogether, where the sequence of tasks we are asked to solve is adaptively and adversarially chosen? We answer this question in the affirmative for both linear regression and contextual bandits. In fact our algorithms succeed where conventional methods fail. In particular we show strong lower bounds against Huber regression and more generally any convex M-estimator. Our approach is based on a novel alternating minimization scheme that interleaves ordinary least-squares with a simple convex program that finds the optimal reweighting of the distribution under a spectral constraint. Our results obtain essentially optimal dependence on the contamination level $\eta$, reach the optimal breakdown point, and naturally apply to infinite dimensional settings where the feature vectors are represented implicitly via a kernel map.
• Abstract（参考訳）: 本研究では,2つの古典的高次元オンライン学習問題,すなわち線形回帰と文脈的帯域幅を再考する。 アルゴリズム的ロバスト統計学における既存の研究は、入力データが均等に拡散されたり、良い生成モデルから生じたりすることを保証する、強い分布的仮定を立てている。 分散的な仮定が完全になければ,解決すべきタスクのシーケンスが適応的かつ敵対的に選択されるような,強固な堅牢性保証を実現することは可能か? 我々は線形回帰と文脈的バンディットの両方について肯定的に答える。 実際、我々のアルゴリズムは従来の方法が失敗する場合に成功します。 特に、フーバー回帰やより一般に任意の凸 m-推定器に対する強い下界を示す。 提案手法は, スペクトル制約下での分布の最適再重み付けを求める単純な凸プログラムを用いて, 通常の最小二乗をインターリーブする, 交代最小化方式に基づく。 この結果は基本的に汚染レベル$\eta$ に最適依存し、最適分解点に到達し、特徴ベクトルがカーネルマップを介して暗黙的に表現される無限次元の設定に自然に適用できる。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Distributionally Robust Skeleton Learning of Discrete Bayesian Networks [9.46389554092506]
  我々は、潜在的に破損したデータから一般的な離散ベイズネットワークの正確なスケルトンを学習する問題を考察する。 本稿では,有界ワッサーシュタイン距離(KL)における分布群に対する最も有害なリスクを,経験的分布へのKL分散を最適化することを提案する。 本稿では,提案手法が標準正規化回帰手法と密接に関連していることを示す。
  論文  参考訳（メタデータ） (2023-11-10T15:33:19Z)
• Tight Certified Robustness via Min-Max Representations of ReLU Neural Networks [9.771011198361865]
  制御システムにニューラルネットワークを確実に配置するには、厳格な堅牢性を保証する必要がある。 本稿では,ReLUニューラルネットワークの凸表現に対する強靭性証明を得る。
  論文  参考訳（メタデータ） (2023-10-07T21:07:45Z)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) は、敵対的マルチアームバンディット(MAB)問題に対する最適解であると考えられている。 重み付き設定のMAB問題に対するクリッピング(INFclip)を用いたINFの新バージョン"Implicitly Normalized Forecaster"を提案する。 INFclipは線形重み付きMAB問題に対して最適であり、非線形問題に対して有効であることを示す。
  論文  参考訳（メタデータ） (2023-05-11T12:00:43Z)
• Online Statistical Inference for Matrix Contextual Bandit [3.465827582464433]
  文脈的帯域幅は、文脈情報と歴史的フィードバックデータに基づく逐次的意思決定に広く利用されている。 我々は、両方のバイアス源を同時に扱うために、新しいオンライン二重バイアス推論手法を導入する。 提案手法は, 新たに開発された低ランク勾配勾配推定器とその非漸近収束結果に基づく。
  論文  参考訳（メタデータ） (2022-12-21T22:03:06Z)
• On Kernelized Multi-Armed Bandits with Constraints [16.102401271318012]
  一般に未知の報酬関数と一般未知の制約関数を併用した帯域幅問題について検討する。 本稿では,アルゴリズムの性能解析のための一般的なフレームワークを提案する。 本稿では,数値実験により提案アルゴリズムの優れた性能を示す。
  論文  参考訳（メタデータ） (2022-03-29T14:02:03Z)
• Distribution-Free Robust Linear Regression [5.532477732693]
  共変体の分布を仮定せずにランダムな設計線形回帰を研究する。 最適部分指数尾を持つオーダー$d/n$の過大なリスクを達成する非線形推定器を構築する。 我々は、Gy"orfi, Kohler, Krzyzak, Walk が原因で、truncated least squares 推定器の古典的境界の最適版を証明した。
  論文  参考訳（メタデータ） (2021-02-25T15:10:41Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)
• High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
  一定対向分数の存在下でのロバスト平均推定の問題は勾配降下によって解けることを示す。 我々の研究は、近辺の非補題推定とロバスト統計の間の興味深い関係を確立する。
  論文  参考訳（メタデータ） (2020-05-04T10:48:04Z)

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

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