論文の概要: Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization

• arxiv url: http://arxiv.org/abs/2007.06552v3
• Date: Fri, 22 Jul 2022 03:25:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-10 23:06:11.297383
• Title: Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization
• Title（参考訳）: i.i.d.仮定を緩和する:ルートエントロピー正則化による適応的ミニマックス最適後悔
• Authors: Blair Bilodeau, Jeffrey Negrea, Daniel M. Roy
• Abstract要約: 我々は、未知の制約セット内でデータを任意に生成する場合、専門家のアドバイスで予測する。 Hedgeアルゴリズムは、最近、i.d.データに対して同時にミニマックス最適であることが示されている。 我々は,すべてのレベルにおいてミニマックス後悔の上限と下限を一致させ,決定論的学習率を持つヘッジが極端外において最適以下であることを示し,すべてのレベルにおいてミニマックス後悔を適応的に得ることを証明した。
• 参考スコア（独自算出の注目度）: 16.536558038560695
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider prediction with expert advice when data are generated from distributions varying arbitrarily within an unknown constraint set. This semi-adversarial setting includes (at the extremes) the classical i.i.d. setting, when the unknown constraint set is restricted to be a singleton, and the unconstrained adversarial setting, when the constraint set is the set of all distributions. The Hedge algorithm -- long known to be minimax (rate) optimal in the adversarial regime -- was recently shown to be simultaneously minimax optimal for i.i.d. data. In this work, we propose to relax the i.i.d. assumption by seeking adaptivity at all levels of a natural ordering on constraint sets. We provide matching upper and lower bounds on the minimax regret at all levels, show that Hedge with deterministic learning rates is suboptimal outside of the extremes, and prove that one can adaptively obtain minimax regret at all levels. We achieve this optimal adaptivity using the follow-the-regularized-leader (FTRL) framework, with a novel adaptive regularization scheme that implicitly scales as the square root of the entropy of the current predictive distribution, rather than the entropy of the initial predictive distribution. Finally, we provide novel technical tools to study the statistical performance of FTRL along the semi-adversarial spectrum.
• Abstract（参考訳）: 未知の制約セット内で任意に変化する分布からデータを生成する場合、専門家のアドバイスによる予測を考える。 この半逆設定は、(極端において)未知の制約集合がシングルトンに制限される古典的なi.i.d.設定と、制約集合がすべての分布の集合である場合の非拘束逆設定を含む。 Hedgeアルゴリズム(Hedge algorithm)は、長年、敵対体制において最小値(rate)が最適であることが知られていたが、最近、i.d.データに対して同時に最小値が最適であることが示されている。 本研究では,制約集合上の自然順序の全てのレベルで適応性を求めることにより,i.i.d.仮定を緩和することを提案する。 我々は,すべてのレベルにおいてミニマックス後悔の上限と下限を一致させ,決定論的学習率を持つヘッジが極端外において最適以下であることを示し,すべてのレベルにおいてミニマックス後悔を適応的に得ることを証明した。 この最適適応性は、初期予測分布のエントロピーではなく、現在の予測分布のエントロピーの平方根として暗黙的にスケールする新しい適応正規化スキームを用いて、従順化リーダー(FTRL)フレームワークを用いて達成する。 最後に、FTRLの統計的性能を半逆スペクトルに沿って研究するための新しい技術ツールを提供する。

関連論文リスト

• Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
  我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。 私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2024-05-25T08:09:36Z)
• Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regression [12.443289202402761]
  最小ノルム過パラメータ線形回帰モデルのレンズによるバッチ分割の利点を示す。 最適なバッチサイズを特徴付け、ノイズレベルに逆比例することを示す。 また,Weiner係数と同等の係数によるバッチ最小ノルム推定器の縮小がさらに安定化し,全ての設定において2次リスクを低くすることを示した。
  論文  参考訳（メタデータ） (2023-06-14T11:02:08Z)
• Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalization [52.7137956951533]
  既存の特徴から予測器を学習するためのよりシンプルな手法を考案することは、将来の研究にとって有望な方向である、と我々は主張する。 本稿では,線形予測器を学習するための凸目標である領域調整回帰(DARE)を紹介する。 自然モデルの下では、DARE解が制限されたテスト分布の集合に対する最小最適予測器であることを証明する。
  論文  参考訳（メタデータ） (2022-02-14T16:42:16Z)
• Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers [31.102181563065844]
  量子的(そしてより一般的には、KL)後悔は、最高の個人専門家と競争する目標を緩和し、敵対的なデータに関して、ほとんどの専門家と競争するだけである。 最近では、半対人パラダイム(Bilodeau、Negrea、Roy 2020)は、完全に対人的でも対人的でもないデータを考えることによって、対人的オンライン学習の代替緩和を提供する。 我々は、FTRLと別個のルート対数正規化器を併用したFTRLを用いて、両方のパラダイムにおいて最小限の後悔を達成し、どちらも正規Hedgeの変種と解釈できる。
  論文  参考訳（メタデータ） (2021-10-27T22:38:52Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  ランダムに選択されたデータバッチの分類出力行列の構造について検討し,予測可能性と多様性について検討した。 本稿では,目標出力行列上で核ノルムを行い,目標予測能力を向上するBatch Nuclear-norm Maximization and Minimizationを提案する。 実験により,本手法は3つの典型的なドメイン適応シナリオにおいて適応精度とロバスト性を高めることができることが示された。
  論文  参考訳（メタデータ） (2021-07-13T15:08:32Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。 我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。 我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
  論文  参考訳（メタデータ） (2021-07-05T21:05:11Z)
• Optimal Stochastic Nonconvex Optimization with Bandit Feedback [45.675080529219365]
  一定の平滑さと部分レベル集合仮定の下で非コスト関数に対する連続武装バンディット問題を解析する。 次に、性能を大幅に向上させる適応分割法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T05:21:12Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。 提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。 我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
  論文  参考訳（メタデータ） (2020-11-05T08:04:34Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• A Convergent and Dimension-Independent Min-Max Optimization Algorithm [32.492526162436405]
  min-playerがパラメータを更新するために使用する分布は、滑らかで非凹凸関数に依存していることを示す。 我々のアルゴリズムは、繰り返しに依存しない多くの反復において近似的な局所平衡に収束する。
  論文  参考訳（メタデータ） (2020-06-22T16:11:30Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  そこで本研究では,対数様比統計量と正規化フローに基づく新しい分布アライメント手法を提案する。 入力領域の局所構造を保存する領域アライメントにおいて,結果の最小化を実験的に検証する。
  論文  参考訳（メタデータ） (2020-03-26T22:10:04Z)

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

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