論文の概要: Smoothed Analysis of Sequential Probability Assignment

• arxiv url: http://arxiv.org/abs/2303.04845v1
• Date: Wed, 8 Mar 2023 19:25:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-10 17:05:42.467956
• Title: Smoothed Analysis of Sequential Probability Assignment
• Title（参考訳）: 逐次確率割り当ての平滑化解析
• Authors: Alankrita Bhatt, Nika Haghtalab, Abhishek Shetty
• Abstract要約: 本稿では,情報理論的に最適であるminmaxレートと,最大極大推定器オラクルを含むアルゴリズム削減の枠組みについて検討する。 提案手法は,スムーズな逆数に対する逐次確率割当のためのミニマックスレートから,トランスダクティブ学習のためのミニマックスレートへの汎用的な削減を実現する。
• 参考スコア（独自算出の注目度）: 16.090378928208885
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information-theoretically optimal minmax rates as well as a framework for algorithmic reduction involving the maximum likelihood estimator oracle. Our approach establishes a general-purpose reduction from minimax rates for sequential probability assignment for smoothed adversaries to minimax rates for transductive learning. This leads to optimal (logarithmic) fast rates for parametric classes and classes with finite VC dimension. On the algorithmic front, we develop an algorithm that efficiently taps into the MLE oracle, for general classes of functions. We show that under general conditions this algorithmic approach yields sublinear regret.
• Abstract（参考訳）: 文脈を考慮した逐次確率割当問題に対する平滑化解析の研究を開始する。 我々は情報理論上最適なminmaxレートと最大ラピエーション推定子オラクルを含むアルゴリズム削減の枠組みについて研究する。 提案手法は, 逐次確率割当のためのminimaxレートから, トランスダクティブ学習のためのminimaxレートへの汎用的還元を実現する。 これにより、パラメトリック類と有限VC次元のクラスに対して最適な(対数的な)速さが得られる。 アルゴリズムの面では、関数の一般的なクラスに対してmle oracleを効率的に利用するためのアルゴリズムを開発します。 一般的な条件下では、このアルゴリズム的アプローチはサブ線形後悔をもたらす。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage [24.40306100502023]
  我々は,雑音学習アルゴリズムのクラスにおける一般化挙動を解析するために,情報理論の枠組みを採用する。 更新関数の仮定が雑音の最適選択にどのように影響するかを示す。
  論文  参考訳（メタデータ） (2023-02-28T12:13:57Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization [14.719077076351377]
  本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。 Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
  論文  参考訳（メタデータ） (2022-08-11T16:55:26Z)
• Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
  非強凸設定における最小二乗回帰問題の近似を考察する。 本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-03T14:39:33Z)
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path [29.289190242826688]
  本稿では,最短経路(SSP)モデルにおいて,後悔するアルゴリズムを開発するための汎用テンプレートを提案する。 まず、厳密な正のコストでモデルフリーとミニマックス最適の2つの新しいアルゴリズムを開発する。 どちらのアルゴリズムも高度にスパースな更新を認めており、既存のアルゴリズムよりも計算効率が良い。
  論文  参考訳（メタデータ） (2021-06-15T19:15:17Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Train simultaneously, generalize better: Stability of gradient-based minimax learners [12.691047660244331]
  コンベックス・コンベブと非コンベックス・ミニマックス・セッティングの両方において,訓練されたミニマックスモデルの性能において重要な役割を担っている。 学習したミニマックスモデルの一般化における最適化アルゴリズムの役割を示す数値的な結果について議論する。
  論文  参考訳（メタデータ） (2020-10-23T17:44:43Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)

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

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