論文の概要: Solving optimization problems with Blackwell approachability

• arxiv url: http://arxiv.org/abs/2202.12277v1
• Date: Thu, 24 Feb 2022 18:19:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-25 18:15:55.733963
• Title: Solving optimization problems with Blackwell approachability
• Title（参考訳）: blackwell approachabilityによる最適化問題の解法
• Authors: Julien Grand-Cl\'ement and Christian Kroer
• Abstract要約: Conic Blackwell Algorithm$+$ (CBA$+$) regret minimalr。 CBA$+$はBlackwellのアプローチ性に基づいており、$O(sqrtT)$ regretに達する。 CBA$+$に基づいて、凸凹サドル問題を解くための新しいパラメータフリーアルゴリズムSP-CBA$+$を導入する。
• 参考スコア（独自算出の注目度）: 31.29341288414507
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the Conic Blackwell Algorithm$^+$ (CBA$^+$) regret minimizer, a new parameter- and scale-free regret minimizer for general convex sets. CBA$^+$ is based on Blackwell approachability and attains $O(\sqrt{T})$ regret. We show how to efficiently instantiate CBA$^+$ for many decision sets of interest, including the simplex, $\ell_{p}$ norm balls, and ellipsoidal confidence regions in the simplex. Based on CBA$^+$, we introduce SP-CBA$^+$, a new parameter-free algorithm for solving convex-concave saddle-point problems, which achieves a $O(1/\sqrt{T})$ ergodic rate of convergence. In our simulations, we demonstrate the wide applicability of SP-CBA$^+$ on several standard saddle-point problems, including matrix games, extensive-form games, distributionally robust logistic regression, and Markov decision processes. In each setting, SP-CBA$^+$ achieves state-of-the-art numerical performance, and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters.
• Abstract（参考訳）: 一般凸集合に対する新しいパラメータとスケールフリーな後悔最小化器であるconic blackwellアルゴリズム$^+$ (cba$^+$) regret minimalrを導入する。 CBA$^+$はブラックウェルのアプローチ性に基づいており、$O(\sqrt{T})$ regretに達する。 CBA$^+$ を多くの決定集合に対して効率的にインスタンス化する方法を示し、例えば、simplix, $\ell_{p}$ norm balls, and ellipsoidal confidence region in the simplex。 CBA$^+$に基づいて、凸凹サドル点問題を解くための新しいパラメータフリーアルゴリズムSP-CBA$^+$を導入し、O(1/\sqrt{T})$ ergodic rate of convergenceを実現する。 シミュレーションでは,行列ゲーム,広範な形式ゲーム,分布的ロジスティック回帰,マルコフ決定過程など,いくつかの標準サドルポイント問題に対するsp-cba$^+$の適用性を示す。 それぞれの設定において、SP-CBA$^+$は最先端の数値性能を達成し、ステップサイズや他のアルゴリズムパラメータを選択せずに古典的な手法より優れている。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization [52.25843977506935]
  有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。 そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
  論文  参考訳（メタデータ） (2022-11-03T14:41:46Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
  我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。 我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。 本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-04-11T15:08:09Z)
• Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving [21.496093093434357]
  我々は、新しい単純後悔最小化器、コニック・ブラックウェルアルゴリズム$+$(CBA$+$)を開発する。 CBA$+$,$ell_p$標準球,および楕円型信頼領域の実装方法を示す。 本稿では,行列ゲームと分散ロバストな最適化問題を解くための数値実験について述べる。
  論文  参考訳（メタデータ） (2021-05-27T14:50:31Z)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。 一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
  論文  参考訳（メタデータ） (2020-02-26T11:18:43Z)

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

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