論文の概要: Efficient Opportunistic Approachability
- arxiv url: http://arxiv.org/abs/2602.21328v1
- Date: Tue, 24 Feb 2026 19:54:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-26 18:19:16.59219
- Title: Efficient Opportunistic Approachability
- Title（参考訳）: 効率の良いオポチュニスト的アプローチ可能性
- Authors: Teodor Vanislavov Marinov, Mehryar Mohri, Princewill Okoroafor, Jon Schneider, Julian Zimmert,
- Abstract要約: 我々は,O(T-1/4)$のレートを達成する機会論的アプローチ性のための効率的なアルゴリズムを提案する。
相手の作用集合の次元が少なくとも2である場合、最適速度が$O(T-1/2)$であることが示される。
- 参考スコア（独自算出の注目度）: 46.51731110028152
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of opportunistic approachability: a generalization of Blackwell approachability where the learner would like to obtain stronger guarantees (i.e., approach a smaller set) when their adversary limits themselves to a subset of their possible action space. Bernstein et al. (2014) introduced this problem in 2014 and presented an algorithm that guarantees sublinear approachability rates for opportunistic approachability. However, this algorithm requires the ability to produce calibrated online predictions of the adversary's actions, a problem whose standard implementations require time exponential in the ambient dimension and result in approachability rates that scale as $T^{-O(1/d)}$. In this paper, we present an efficient algorithm for opportunistic approachability that achieves a rate of $O(T^{-1/4})$ (and an inefficient one that achieves a rate of $O(T^{-1/3})$), bypassing the need for an online calibration subroutine. Moreover, in the case where the dimension of the adversary's action set is at most two, we show it is possible to obtain the optimal rate of $O(T^{-1/2})$.
- Abstract（参考訳）: 学習者がより強い保証(すなわち、より小さな集合に近づいたい場合)を得たい場合、相手が可能なアクション空間のサブセットに限定する。
Bernstein et al (2014) はこの問題を2014年に導入し、機会論的アプローチ性に対するサブ線形アプローチ率を保証するアルゴリズムを提示した。
しかし、このアルゴリズムは、標準的な実装が周囲の次元で指数関数的な時間を必要とする問題である敵の行動の校正されたオンライン予測を生成する能力を必要とし、その結果、アプローチ可能性率は$T^{-O(1/d)}$となる。
本稿では,O(T^{-1/4})$(および,O(T^{-1/3})$)$(および非効率)$(T^{-1/4})$)を達成し,オンラインキャリブレーションサブルーチンの必要性を回避できる最適アプローチ性アルゴリズムを提案する。
さらに、相手の作用集合の次元が少なくとも 2 である場合、最適速度が$O(T^{-1/2})$であることが示される。
関連論文リスト
- Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL [6.996002801232415]
生成モデルを用いてマルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを求める際のサンプル複雑性について検討した。
我々は,知識を必要とせず,最適なスパンベース複雑性に適合するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2025-02-16T19:10:55Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。
次に,政策最適化におけるコミット率の概念を紹介する。
第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文 参考訳（メタデータ） (2021-10-29T06:35:44Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文 参考訳（メタデータ） (2020-08-13T08:56:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。