論文の概要: Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms

• arxiv url: http://arxiv.org/abs/2405.04480v2
• Date: Sat, 11 May 2024 00:41:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-14 20:52:15.519493
• Title: Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms
• Title（参考訳）: 共進化学習アルゴリズムと帯域学習アルゴリズムの集中位置境界解析
• Authors: Per Kristian Lehre, Shishen Lin,
• Abstract要約: 本稿では,アルゴリズムの実行時/実行時/実行時における集中テールバウンドを導出する問題について考察する。 この定理は、正、弱、零、負のドリフトが与えられた正確な指数的なテールバウンドを与える新しいドリフト定理を提供する。 我々のドリフト定理は、AIにおけるアルゴリズムのランタイム/レグレットの強い集中力を証明するのに使うことができる。
• 参考スコア（独自算出の注目度）: 1.104960878651584
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Runtime analysis, as a branch of the theory of AI, studies how the number of iterations algorithms take before finding a solution (its runtime) depends on the design of the algorithm and the problem structure. Drift analysis is a state-of-the-art tool for estimating the runtime of randomised algorithms, such as evolutionary and bandit algorithms. Drift refers roughly to the expected progress towards the optimum per iteration. This paper considers the problem of deriving concentration tail-bounds on the runtime/regret of algorithms. It provides a novel drift theorem that gives precise exponential tail-bounds given positive, weak, zero and even negative drift. Previously, such exponential tail bounds were missing in the case of weak, zero, or negative drift. Our drift theorem can be used to prove a strong concentration of the runtime/regret of algorithms in AI. For example, we prove that the regret of the \rwab bandit algorithm is highly concentrated, while previous analyses only considered the expected regret. This means that the algorithm obtains the optimum within a given time frame with high probability, i.e. a form of algorithm reliability. Moreover, our theorem implies that the time needed by the co-evolutionary algorithm RLS-PD to obtain a Nash equilibrium in a \bilinear max-min-benchmark problem is highly concentrated. However, we also prove that the algorithm forgets the Nash equilibrium, and the time until this occurs is highly concentrated. This highlights a weakness in the RLS-PD which should be addressed by future work.
• Abstract（参考訳）: AI理論の分岐として、実行時解析は、解(実行時)を見つける前に、アルゴリズムの繰り返し数がどのように取るかを、アルゴリズムの設計と問題構造に依存する。 ドリフト分析(Drift analysis)は、進化的アルゴリズムやバンディットアルゴリズムのようなランダム化アルゴリズムのランタイムを推定するための最先端のツールである。 ドリフト(Drift)とは、イテレーション毎の最適化に向けた期待される進歩を指す。 本稿では,アルゴリズムの実行時/実行時/実行時における集中テールバウンドを導出する問題について考察する。 この定理は、正、弱、零、負のドリフトが与えられた正確な指数的なテールバウンドを与える新しいドリフト定理を提供する。 以前は、弱い、ゼロ、負のドリフトの場合、そのような指数的な尾の境界は失われていた。 我々のドリフト定理は、AIにおけるアルゴリズムのランタイム/レグレットの強い集中力を証明するのに使うことができる。 例えば、Sharwabbanditアルゴリズムの後悔は極めて集中しており、以前の分析では期待された後悔のみを考慮していた。 これはアルゴリズムが与えられた時間枠内で高い確率、すなわちアルゴリズムの信頼性の形で最適な値を得ることを意味する。 さらに, 共進化アルゴリズム RLS-PD により, 双線型極小ベンチマーク問題におけるナッシュ平衡を得るのに必要な時間は, 高度に集中していることが示唆された。 しかし、このアルゴリズムはナッシュ平衡を忘れており、この現象が起こるまでの時間は高度に集中していることも証明している。 これは今後の作業で対処すべきRSS-PDの弱点を浮き彫りにする。

関連論文リスト

• Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals [10.850101961203752]
  正方形損失目標を持つガウスの辺縁部における任意のバイアスのReLU活性化(あるいはニューロン)を学習する問題を考察する。 我々の主な成果は時間統計クエリ(SQ)アルゴリズムであり、任意のバイアスに対して最初の定数係数近似を与える。 我々のアルゴリズムは、勾配降下に基づく既存のアルゴリズムから興味深い逸脱を示す。
  論文  参考訳（メタデータ） (2024-11-21T17:43:51Z)
• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29:12Z)
• Decentralized Sum-of-Nonconvex Optimization [42.04181488477227]
  我々は、平均的な非合意数である保証関数(sum-of-non function)の最適化問題を考察する。 本稿では,勾配,速度追跡,マルチコンセンサスといった手法を用いて,高速化された分散化1次アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:48:45Z)
• Online Robust Reinforcement Learning with Model Uncertainty [24.892994430374912]
  未知の不確実性集合を推定し、堅牢なQ-ラーニングと堅牢なTDCアルゴリズムを設計するためのサンプルベースアプローチを開発する。 頑健なQ-ラーニングアルゴリズムでは、最適なロバストなQ関数に収束することが証明され、ロバストなTDCアルゴリズムでは、いくつかの定常点に収束することが証明される。 我々のアプローチは、TD、SARSA、その他のGTDアルゴリズムなど、他の多くのアルゴリズムを堅牢化するために容易に拡張できる。
  論文  参考訳（メタデータ） (2021-09-29T16:17:47Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• On the Last Iterate Convergence of Momentum Methods [32.60494006038902]
  我々は、任意の一定の運動量係数に対して、最後の反復が誤差に苦しむリプシッツおよび凸函数が存在することを初めて証明する。 凸関数と滑らかな関数の設定では、新しいSGDMアルゴリズムが自動的に$O(fraclog TT)$のレートで収束することを示しています。
  論文  参考訳（メタデータ） (2021-02-13T21:16:16Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)

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

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