論文の概要: Fast Cyclic Coordinate Dual Averaging with Extrapolation for Generalized Variational Inequalities

• arxiv url: http://arxiv.org/abs/2102.13244v1
• Date: Fri, 26 Feb 2021 00:28:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-01 13:45:12.953470
• Title: Fast Cyclic Coordinate Dual Averaging with Extrapolation for Generalized Variational Inequalities
• Title（参考訳）: 一般化変分不等式に対する外挿を伴う高速巡回座標双対平均化
• Authors: Chaobing Song and Jelena Diakonikolas
• Abstract要約: 一般化された変分不等式問題に対するextRapolation(CODER)法によるemphCyclic cOordinate Dual avEragingを提案する。 CODERは、収束率がブロック数に依存しない最初の周期的ブロック座標法である。
• 参考スコア（独自算出の注目度）: 19.988400064884825
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose the \emph{Cyclic cOordinate Dual avEraging with extRapolation (CODER)} method for generalized variational inequality problems. Such problems are fairly general and include composite convex minimization and min-max optimization as special cases. CODER is the first cyclic block coordinate method whose convergence rate is independent of the number of blocks, which fills the significant gap between cyclic coordinate methods and randomized ones that remained open for many years. Moreover, CODER provides the first theoretical guarantee for cyclic coordinate methods for solving generalized variational inequality problems under only monotonicity and Lipschitz continuity assumptions. To remove the dependence on the number of blocks, the analysis of CODER is based on a novel Lipschitz condition with respect to a Mahalanobis norm rather than the commonly used coordinate-wise Lipschitz condition; to be applicable to general variational inequalities, CODER leverages an extrapolation strategy inspired by the recent developments in primal-dual methods. Our theoretical results are complemented by numerical experiments, which demonstrate competitive performance of CODER compared to other coordinate methods.
• Abstract（参考訳）: 一般化された変分不等式問題に対する extRapolation (CODER) を用いた \emph{Cyclic cOordinate Dual avEraging 法を提案する。 このような問題はかなり一般的であり、特別なケースとしてコンポジット凸最小化と最小値最適化が含まれる。 CODERは、収束速度がブロック数に依存しない最初の循環ブロック座標法であり、循環座標法と何年も開いていたランダム化法との間の大きなギャップを埋めるものである。 さらに、CODERは単調性およびリプシッツ連続性仮定のみの下で一般化された変分不等式問題を解くための巡回座標法に対する最初の理論的保証を提供する。 ブロック数への依存を除去するために、CODERの分析は、一般的に使用される座標方向のリプシッツ条件ではなく、マハラノビスノルムに関する新しいリプシッツ条件に基づいており、一般的な変動不等式に適用するために、CODERは、原始双対法における最近の発展に触発された外挿戦略を利用します。 我々の理論結果は,CODERと他の座標法との競合性能を示す数値実験によって補完される。

関連論文リスト

• An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
  機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。 本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
  論文  参考訳（メタデータ） (2024-07-05T08:53:06Z)
• Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
  凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。 最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
  論文  参考訳（メタデータ） (2023-06-02T04:21:59Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization [26.218670461973705]
  非漸近勾配ノルム保証を協調する問題の解法を提案する。 本研究は,ニューラルネットの深部学習における循環還元方式の有効性を実証するものである。
  論文  参考訳（メタデータ） (2022-12-09T19:17:39Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses [19.554559253046225]
  オンライン凸最適化 (OCO) において、関数のリプシッツ連続性は、サブ線形後悔を得るために一般的に仮定される。 本研究では,相対リプシッツ関数と相対凸関数のOCOを考える。 以下に示すように、正規化されたリーダーアルゴリズムとオンラインミラー降下の変種について、残念な点を示す。
  論文  参考訳（メタデータ） (2020-10-22T20:22:19Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints [8.643249539674612]
  本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。 まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。 さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
  論文  参考訳（メタデータ） (2020-06-30T23:49:38Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
  ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。 座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-03-30T20:44:56Z)

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

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