論文の概要: Geometry-Aware Universal Mirror-Prox

• arxiv url: http://arxiv.org/abs/2011.11203v1
• Date: Mon, 23 Nov 2020 04:17:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-22 02:46:50.882280
• Title: Geometry-Aware Universal Mirror-Prox
• Title（参考訳）: 幾何学的ユニバーサルミラープロックス
• Authors: Reza Babanezhad and Simon Lacoste-Julien
• Abstract要約: ミラープロキシ(英: Mirror-prox、MP)は、不等式(VI)問題を解決するアルゴリズムである。 近年、滑らかで有界な演算子に対するMPの普遍的な変種が導入されたが、これはMPの更新のノルムにのみ依存する。
• 参考スコア（独自算出の注目度）: 30.22021936241521
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Mirror-prox (MP) is a well-known algorithm to solve variational inequality (VI) problems. VI with a monotone operator covers a large group of settings such as convex minimization, min-max or saddle point problems. To get a convergent algorithm, the step-size of the classic MP algorithm relies heavily on the problem dependent knowledge of the operator such as its smoothness parameter which is hard to estimate. Recently, a universal variant of MP for smooth/bounded operators has been introduced that depends only on the norm of updates in MP. In this work, we relax the dependence to evaluating the norm of updates to Bregman divergence between updates. This relaxation allows us to extends the analysis of universal MP to the settings where the operator is not smooth or bounded. Furthermore, we analyse the VI problem with a stochastic monotone operator in different settings and obtain an optimal rate up to a logarithmic factor.
• Abstract（参考訳）: ミラープロキシ (MP) は変分不等式 (VI) を解くアルゴリズムとしてよく知られている。 vi モノトーン演算子は、凸最小化、min-max、saddle point 問題など、多数の設定をカバーする。 収束アルゴリズムを得るためには、古典的なMPアルゴリズムのステップサイズは、推定が難しい滑らか度パラメータなどの演算子の問題依存的な知識に大きく依存する。 近年、滑らかで有界な演算子に対するMPの普遍的な変種が導入されたが、これはMPの更新のノルムにのみ依存する。 本研究では,更新間のBregman分散に対する更新の規範を評価することへの依存を緩和する。 この緩和により、ユニバーサルMPの分析を、オペレータがスムーズでなければバウンダリのない設定にまで拡張できる。 さらに, 確率的単調作用素を用いてvi問題を異なる設定で解析し, 対数係数までの最適速度を求める。

関連論文リスト

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• First-order methods for Stochastic Variational Inequality problems with Function Constraints [3.922842284927803]
  本稿では,機能制約付き変分不等式(FCVI)問題に対して,スムーズあるいは非スムーズな設定で新しい一階法を提案する。 全てのアルゴリズムは、同じ複雑性を保ちながら、主変数と双変数を結合する関数制約を持つサドル点問題に容易に拡張できる。
  論文  参考訳（メタデータ） (2023-04-10T17:07:55Z)
• Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective [21.6146047576295]
  トップk演算子はスパースベクトルを返し、非ゼロ値は入力の k 最大の値に対応する。 我々はトップk作用素を、置換の凸包であるペルムタヘドロン上の線形プログラムとみなす。 私たちのフレームワークは既存のフレームワークよりもはるかに汎用的であり、例えば、大まかに値を選択するトップk演算子を表現できる。
  論文  参考訳（メタデータ） (2023-02-02T21:32:13Z)
• Quasi-parametric rates for Sparse Multivariate Functional Principal Components Analysis [0.0]
  最適化問題の解として固有値が表現可能であることを示す。 固有要素の平均2乗再構成誤差に基づいてミニマックス下限を定め、この手順がミニマックス感覚に最適な分散を有することを証明した。
  論文  参考訳（メタデータ） (2022-12-19T13:17:57Z)
• META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions [23.746620619512573]
  最近の研究は「メガバッチ」の勾配を計算する効果を克服している 作業は、競争力のあるディープラーニングタスクで更新された後に広く使用される。
  論文  参考訳（メタデータ） (2022-09-29T15:12:54Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。 本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。 我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2022-03-15T13:17:53Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。 リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。 このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
  論文  参考訳（メタデータ） (2021-02-27T19:28:39Z)
• Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence [29.189409618561964]
  我々は単調演算子を用いた変分不等式の新しい適応アルゴリズムを開発した。 我々のアルゴリズムは未知の問題パラメータに自動的に適応する。 我々のアルゴリズムは普遍的であり、同時に最適な収束率を達成することを示す。
  論文  参考訳（メタデータ） (2020-10-15T14:44:26Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)

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

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