論文の概要: Efficient Algorithms for Extreme Bandits

• arxiv url: http://arxiv.org/abs/2203.10883v1
• Date: Mon, 21 Mar 2022 11:09:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-22 23:40:29.883247
• Title: Efficient Algorithms for Extreme Bandits
• Title（参考訳）: 極端バンディットの効率的なアルゴリズム
• Authors: Dorian Baudry, Yoan Russac, Emilie Kaufmann
• Abstract要約: 我々は,学習者が最大の報酬を集めようとするマルチアーマッド・バンディットの変種であるExtreme Bandit問題に貢献する。 まず、報酬分布の尾部における軽度の仮定の下で、i.d確率変数の最大値の濃度について検討する。 次に,より適応性の高いQoMax-SDAアルゴリズムを提案し,解析する。
• 参考スコア（独自算出の注目度）: 20.68824391770909
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we contribute to the Extreme Bandit problem, a variant of Multi-Armed Bandits in which the learner seeks to collect the largest possible reward. We first study the concentration of the maximum of i.i.d random variables under mild assumptions on the tail of the rewards distributions. This analysis motivates the introduction of Quantile of Maxima (QoMax). The properties of QoMax are sufficient to build an Explore-Then-Commit (ETC) strategy, QoMax-ETC, achieving strong asymptotic guarantees despite its simplicity. We then propose and analyze a more adaptive, anytime algorithm, QoMax-SDA, which combines QoMax with a subsampling method recently introduced by Baudry et al. (2021). Both algorithms are more efficient than existing approaches in two aspects (1) they lead to better empirical performance (2) they enjoy a significant reduction of the memory and time complexities.
• Abstract（参考訳）: 本稿では,学習者が最大報酬の獲得を目指す多腕バンディットの変種である極端バンディット問題(extreme bandit problem)に寄与する。 まず,報奨分布の尾部における軽度仮定下でのi.i.d確率変数の最大値の集中度について検討した。 この分析は、Quantile of Maxima (QoMax)の導入を動機付けている。 QoMaxの特性は、単純さにもかかわらず強い漸近的な保証を達成するために、Explore-Then-Commit(ETC)戦略であるQoMax-ETCを構築するのに十分である。 次に,baudry et al. (2021) が最近導入したサブサンプリング法とqomaxを結合した,より適応的なanytimeアルゴリズムであるqomax-sdaを提案する。 どちらのアルゴリズムも,2つの面で既存のアプローチよりも効率的である (1) 経験的パフォーマンスの向上 (2) メモリと時間の複雑さの大幅な低減を享受する。

関連論文リスト

• Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
  一般化されたOneMax関数の最初のランタイム解析を提供する。 r-cGAはこのr値のOneMax問題を効率的に解くことを示す。 実験の最後には、多値OneMax関数の別の変種が期待されるランタイムに関する予想を述べる。
  論文  参考訳（メタデータ） (2024-04-17T10:40:12Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization [36.743632418094]
  マルチブロックのmin-max双レベル最適化問題に対処するシングルループアルゴリズムを提案する。 我々のアルゴリズムは数百のタスクで問題に取り組むのに利用できることを示す。
  論文  参考訳（メタデータ） (2022-06-01T06:42:36Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Distributed Statistical Min-Max Learning in the Presence of Byzantine Agents [34.46660729815201]
  本稿では,ビザンチンの敵対的エージェントと競合する新たな課題に焦点をあて,マルチエージェントのmin-max学習問題を考察する。 我々の主な貢献は、滑らかな凸凹関数と滑らかな凸凸凸関数に対する頑健な外勾配アルゴリズムのクリップ解析を提供することである。 我々の利率はほぼ最適であり、敵の汚職の影響と非汚職エージェント間の協力の利益の両方を明らかにしている。
  論文  参考訳（メタデータ） (2022-04-07T03:36:28Z)
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit [0.05076419064097732]
  推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。 この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
  論文  参考訳（メタデータ） (2021-10-20T17:58:53Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Stochastic Hard Thresholding Algorithms for AUC Maximization [49.00683387735522]
  分散分類におけるAUCのためのハードしきい値決定アルゴリズムを開発した。 提案アルゴリズムの有効性と有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-04T16:49:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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