論文の概要: Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities

• arxiv url: http://arxiv.org/abs/2603.29128v1
• Date: Tue, 31 Mar 2026 01:23:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-01 15:25:02.983273
• Title: Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities
• Title（参考訳）: 変分不等式に対する適応遅延更新サイクルアルゴリズム
• Authors: Yi Wei, Xufeng Cai, Jelena Diakonikolas,
• Abstract要約: 周期ブロック座標法は1次アルゴリズムの基本クラスである。 我々は,単調リプシッツ作用素を用いたミニティ変分不等式に対処する巡回アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 27.43933993363973
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cyclic block coordinate methods are a fundamental class of first-order algorithms, widely used in practice for their simplicity and strong empirical performance. Yet, their theoretical behavior remains challenging to explain, and setting their step sizes -- beyond classical coordinate descent for minimization -- typically requires careful tuning or line-search machinery. In this work, we develop $\texttt{ADUCA}$ (Adaptive Delayed-Update Cyclic Algorithm), a cyclic algorithm addressing a broad class of Minty variational inequalities with monotone Lipschitz operators. $\texttt{ADUCA}$ is parameter-free: it requires no global or block-wise Lipschitz constants and uses no per-epoch line search, except at initialization. A key feature of the algorithm is using operator information delayed by a full cycle, which makes the algorithm compatible with parallel and distributed implementations, and attractive due to weakened synchronization requirements across blocks. We prove that $\texttt{ADUCA}$ attains (near) optimal global oracle complexity as a function of target error $ε>0,$ scaling with $1/ε$ for monotone operators, or with $\log^2(1/ε)$ for operators that are strongly monotone.
• Abstract（参考訳）: 循環ブロック座標法は1次アルゴリズムの基本クラスであり、その単純さと強い経験的性能のために広く使われている。 しかし、彼らの理論的な振る舞いは説明しづらいままであり、そのステップサイズは、古典的な座標降下(最小化)を超えて、通常は注意深いチューニングやライン探索の機械を必要とする。 本研究では,モノトーンリプシッツ演算子を用いたMinty変分不等式に対処する巡回アルゴリズムである $\texttt{ADUCA}$ (Adaptive Delayed-Update Cyclic Algorithm) を開発する。 $\texttt{ADUCA}$はパラメータフリーで、グローバルあるいはブロックワイズなリプシッツ定数は不要で、初期化以外はエポックな行探索は不要である。 アルゴリズムの重要な特徴は、全サイクルで遅延した演算子情報を使用することであり、これは並列および分散実装と互換性を持ち、ブロック間の同期要求が弱くなったために魅力的である。 目的誤差の関数として$\texttt{ADUCA}$が最適大域オラクル複雑性を達成できることを証明し、モノトン作用素に対して$/ε$、あるいは強いモノトン作用素に対して$\log^2(1/ε)$でスケーリングする。

関連論文リスト

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)
• Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
  我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。 我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。 これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
  論文  参考訳（メタデータ） (2021-02-16T18:15:51Z)
• Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time [16.346069386394703]
  単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。 線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。 我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
  論文  参考訳（メタデータ） (2020-09-10T16:35:54Z)
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint [13.357957711519134]
  制約されたサブモジュール問題には、パーソナライズされたレコメンデーション、チーム形成、バイラルマーケティングによる収益化など、さまざまな応用が含まれている。 我々は5.83のランダム化近似を達成し、O(n log n)$禁断時間、すなわち少なくとも$n$を他の最先端アルゴリズムよりも高速に実行する単純なグリーディアルゴリズムを提案する。 そこで我々は,非単調な目的に対する最初の定数近似である9-近似を求め,実データと合成データに改良された性能を示すアルゴリズムの実験評価を行った。
  論文  参考訳（メタデータ） (2020-07-09T18:15:01Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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