論文の概要: Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving

• arxiv url: http://arxiv.org/abs/2105.13203v1
• Date: Thu, 27 May 2021 14:50:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-28 23:24:05.331723
• Title: Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving
• Title（参考訳）: コニックブラックウェルアルゴリズム:パラメータフリー凸凹サドル点解法
• Authors: Julien Grand-Cl\'ement, Christian Kroer
• Abstract要約: 我々は、新しい単純後悔最小化器、コニック・ブラックウェルアルゴリズム$+$(CBA$+$)を開発する。 CBA$+$,$ell_p$標準球,および楕円型信頼領域の実装方法を示す。 本稿では,行列ゲームと分散ロバストな最適化問題を解くための数値実験について述べる。
• 参考スコア（独自算出の注目度）: 21.496093093434357
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop new parameter and scale-free algorithms for solving convex-concave saddle-point problems. Our results are based on a new simple regret minimizer, the Conic Blackwell Algorithm$^+$ (CBA$^+$), which attains $O(1/\sqrt{T})$ average regret. Intuitively, our approach generalizes to other decision sets of interest ideas from the Counterfactual Regret minimization (CFR$^+$) algorithm, which has very strong practical performance for solving sequential games on simplexes. We show how to implement CBA$^+$ for the simplex, $\ell_{p}$ norm balls, and ellipsoidal confidence regions in the simplex, and we present numerical experiments for solving matrix games and distributionally robust optimization problems. Our empirical results show that CBA$^+$ is a simple algorithm that outperforms state-of-the-art methods on synthetic data and real data instances, without the need for any choice of step sizes or other algorithmic parameters.
• Abstract（参考訳）: 我々は凸凹型サドルポイント問題の解法として,新しいパラメータとスケールフリーアルゴリズムを開発した。 我々の結果は、新しい単純な後悔最小化器であるコニック・ブラックウェル・アルゴリズム$^+$ (CBA$^+$) に基づいており、O(1/\sqrt{T})$平均後悔となる。 直感的には、本手法は、直観的に、直観上のシーケンシャルゲームを解くための非常に強力な実用性能を持つCFR$^+$アルゴリズムから、他の決定的関心の集合に一般化する。 本稿では,simplex,$\ell_{p}$ノルムボール,楕円型信頼領域に対してcba$^+$を実装する方法を示し,行列ゲームを解くための数値実験と分布的ロバストな最適化問題を提案する。 実験の結果, CBA$^+$は, ステップサイズやアルゴリズムパラメータの選択を必要とせずに, 合成データや実データインスタンス上で最先端の手法より優れた単純なアルゴリズムであることがわかった。

関連論文リスト

• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Asymptotic Instance-Optimal Algorithms for Interactive Decision Making [35.76184529520015]
  本稿では,軽度条件下での有限個の判定問題に対して,対話型意思決定のための最初のインスタンス最適化アルゴリズムを設計する。 本研究の結果は, 具体的問題に着目し, 多腕バンディットの古典的ギャップ依存境界と, 線形バンディットに関する先行研究を復元した。
  論文  参考訳（メタデータ） (2022-06-06T02:56:10Z)
• Solving optimization problems with Blackwell approachability [31.29341288414507]
  Conic Blackwell Algorithm$+$ (CBA$+$) regret minimalr。 CBA$+$はBlackwellのアプローチ性に基づいており、$O(sqrtT)$ regretに達する。 CBA$+$に基づいて、凸凹サドル問題を解くための新しいパラメータフリーアルゴリズムSP-CBA$+$を導入する。
  論文  参考訳（メタデータ） (2022-02-24T18:19:21Z)
• Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems [9.173866646584031]
  本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。 また,非コンケーブミニマックス問題に対処できることを示す。
  論文  参考訳（メタデータ） (2021-08-01T15:23:49Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
  サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。 対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。 我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
  論文  参考訳（メタデータ） (2021-03-29T23:03:24Z)
• Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
  複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。 条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
  論文  参考訳（メタデータ） (2020-10-21T15:05:53Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)

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

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