論文の概要: Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation

• arxiv url: http://arxiv.org/abs/2011.02987v5
• Date: Mon, 19 Jun 2023 06:52:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-22 08:28:34.826171
• Title: Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation
• Title（参考訳）: 確率的変分不等式に対する単純かつ最適手法 I:演算子外挿法
• Authors: Georgios Kotsalis, Guanghui Lan, Tianjiao Li
• Abstract要約: まず,決定論的変分不等式(VI)問題を解決するための演算子外挿法を提案する。 次に、演算子外挿法(SOE)を導入し、その最適収束挙動を異なる不等式 VI 問題を解くために確立する。
• 参考スコア（独自算出の注目度）: 9.359939442911127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we first present a novel operator extrapolation (OE) method for solving deterministic variational inequality (VI) problems. Similar to the gradient (operator) projection method, OE updates one single search sequence by solving a single projection subproblem in each iteration. We show that OE can achieve the optimal rate of convergence for solving a variety of VI problems in a much simpler way than existing approaches. We then introduce the stochastic operator extrapolation (SOE) method and establish its optimal convergence behavior for solving different stochastic VI problems. In particular, SOE achieves the optimal complexity for solving a fundamental problem, i.e., stochastic smooth and strongly monotone VI, for the first time in the literature. We also present a stochastic block operator extrapolations (SBOE) method to further reduce the iteration cost for the OE method applied to large-scale deterministic VIs with a certain block structure. Numerical experiments have been conducted to demonstrate the potential advantages of the proposed algorithms. In fact, all these algorithms are applied to solve generalized monotone variational inequality (GMVI) problems whose operator is not necessarily monotone. We will also discuss optimal OE-based policy evaluation methods for reinforcement learning in a companion paper.
• Abstract（参考訳）: 本稿ではまず,決定論的変分不等式(VI)問題を解決するための演算子外挿法を提案する。 勾配(オペレーター)投影法と同様に、oeは各イテレーションで単一のプロジェクションサブプロジェクションを解決し、1つの検索シーケンスを更新する。 oeは既存の手法よりもずっと簡単な方法で様々なvi問題を解決するために最適な収束率を達成できることを示す。 次に,確率作用素外挿法(soe)法を導入し,その最適収束挙動を定式化し,異なる確率 vi 問題を解く。 特に、soeは、文献の中で初めて、確率的滑らかかつ強い単調viという基本的な問題を解決するための最適な複雑さを達成する。 また,確率的ブロック演算子外挿法(SBOE)を提案し,あるブロック構造を持つ大規模決定論的 VI に適用した OE 法の繰り返しコストをさらに削減する。 提案アルゴリズムの潜在的な利点を示すための数値実験が実施されている。 実際、これらのアルゴリズムはすべて、作用素が必ずしも単調でない一般化単調変分不等式(GMVI)問題を解決するために適用される。 また,強化学習のためのoe に基づく最適政策評価手法について,コンパニオン・ペーパーで検討する。

関連論文リスト

• Primal Methods for Variational Inequality Problems with Functional Constraints [25.261426717550293]
  本稿では,関数的制約付き変分不等式問題に対処する手法として,制約付き勾配法(Constrained Gradient Method, CGM)を提案する。 滑らかな制約下での単調作用素による変分不等式問題に対するアルゴリズムの非漸近収束解析を確立する。 提案アルゴリズムは, 単調・強単調両方の演算子問合せにおいて, プロジェクションに基づく手法の複雑さに適合する。
  論文  参考訳（メタデータ） (2024-03-19T16:03:03Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Sample Average Approximation for Black-Box VI [31.664188645648156]
  勾配上昇の困難を回避できる新しいブラックボックスVIを提案する。 我々はそれらを決定論的に変換することで最適化問題の解を近似する。 実験の結果,本手法はVI問題を単純化し,既存手法よりも高速な性能を実現することがわかった。
  論文  参考訳（メタデータ） (2023-04-13T20:04:47Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。 この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
  論文  参考訳（メタデータ） (2022-10-27T17:59:09Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Solving Constrained Variational Inequalities via an Interior Point Method [88.39091990656107]
  制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。 本稿では,2種類の問題においてACVIの収束保証を提供する。 この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
  論文  参考訳（メタデータ） (2022-06-21T17:55:13Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  複数変数の非プロブレムに挑戦する新しい解を提案する。 提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
  論文  参考訳（メタデータ） (2020-09-09T10:45:00Z)
• On the implementation of a global optimization method for mixed-variable problems [0.30458514384586394]
  このアルゴリズムは、グットマンの放射基底関数と、レジスとシューメーカーの計量応答面法に基づいている。 これら2つのアルゴリズムの一般化と改良を目的としたいくつかの修正を提案する。
  論文  参考訳（メタデータ） (2020-09-04T13:36:56Z)
• Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
  複数の異なる損失を最小化しなければならない最適化問題を考える。 提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
  論文  参考訳（メタデータ） (2020-07-14T09:50:33Z)
• The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization [0.0]
  ネステロフの外挿は、非滑らかな問題に対して勾配降下法の個人収束を最適にする強さを持つことを証明している。 提案手法は,設定の非滑らかな損失を伴って正規化学習タスクを解くためのアルゴリズムの拡張である。 本手法は,大規模な1-正規化ヒンジロス学習問題の解法として有効である。
  論文  参考訳（メタデータ） (2020-06-08T03:35:41Z)

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

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