論文の概要: Accelerated Randomized Block-Coordinate Algorithms for Co-coercive Equations and Applications

• arxiv url: http://arxiv.org/abs/2301.03113v1
• Date: Sun, 8 Jan 2023 21:46:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-10 18:03:50.836522
• Title: Accelerated Randomized Block-Coordinate Algorithms for Co-coercive Equations and Applications
• Title（参考訳）: 共役方程式に対するランダム化ブロック座標アルゴリズムとその応用
• Authors: Quoc Tran-Dinh
• Abstract要約: 我々は,コヒーレンシブ方程式の解を近似する高速化されたランダム化ブロック座標アルゴリズムを開発した。 我々のアルゴリズムは[48]におけるハルパーンの不動点反復の最近のネステロフの加速解釈に依存している。 高速かつ証明可能な収束率を有する新しいフェデレーション学習型アルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 12.995632804090198
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we develop an accelerated randomized block-coordinate algorithm to approximate a solution of a co-coercive equation. Such an equation plays a central role in optimization and related fields and covers many mathematical models as special cases, including convex optimization, convex-concave minimax, and variational inequality problems. Our algorithm relies on a recent Nesterov's accelerated interpretation of the Halpern fixed-point iteration in [48]. We establish that the new algorithm achieves $\mathcal{O}(1/k^2)$-convergence rate on $\mathbb{E}[\Vert Gx^k\Vert^2]$ through the last-iterate, where $G$ is the underlying co-coercive operator, $\mathbb{E}[\cdot]$ is the expectation, and $k$ is the iteration counter. This rate is significantly faster than $\mathcal{O}(1/k)$ rates in standard forward or gradient-based methods from the literature. We also prove $o(1/k^2)$ rates on both $\mathbb{E}[\Vert Gx^k\Vert^2]$ and $\mathbb{E}[\Vert x^{k+1} - x^{k}\Vert^2]$. Next, we apply our method to derive two accelerated randomized block coordinate variants of the forward-backward splitting and Douglas-Rachford splitting schemes, respectively for solving a monotone inclusion involving the sum of two operators. As a byproduct, these variants also have faster convergence rates than their non-accelerated counterparts. Finally, we apply our scheme to a finite-sum monotone inclusion that has various applications in machine learning and statistical learning, including federated learning. As a result, we obtain a novel federated learning-type algorithm with fast and provable convergence rates.
• Abstract（参考訳）: 本稿では,共役方程式の解を近似する高速化型ランダム化ブロック座標アルゴリズムを開発した。 このような方程式は最適化と関連する分野において中心的な役割を担い、凸最適化、凸凸ミニマックス、変分不等式問題など、多くの数学モデルを特別な場合として扱う。 我々のアルゴリズムは, [48] におけるhalpernの不動点反復の最近のネステロフの加速解釈に依存している。 我々は、新しいアルゴリズムが$\mathcal{O}(1/k^2)$-convergence rate on $\mathbb{E}[\Vert Gx^k\Vert^2]$を最終定式で達成し、$G$は根底にある共役作用素、$\mathbb{E}[\cdot]$は期待値、$k$は反復カウンタであることを示す。 この値は文献の標準フォワード法や勾配法において$\mathcal{O}(1/k)$レートよりもはるかに高速である。 また、$\mathbb{E}[\Vert Gx^k\Vert^2]$と$\mathbb{E}[\Vert x^{k+1}x^{k}\Vert^2]$の両方に対して$o(1/k^2)$レートを証明します。 次に,2つの演算子の和を含む単調なインクルージョンを解くために,前向き分割とダグラス・ラフフォード分割スキームの2つの高速化ランダム化ブロック座標変種を導出する。 副産物として、これらの変種は非加速型よりも収束速度が速い。 最後に,本手法を有限単位単音包含法に適用し,フェデレーション学習を含む機械学習や統計学習に応用する。 その結果,高速かつ証明可能な収束率を持つ新しいフェデレーション学習型アルゴリズムが得られた。

関連論文リスト

• Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
  我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。 提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。 我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
  論文  参考訳（メタデータ） (2024-05-09T15:53:43Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes [23.94542304111204]
  勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。 規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
  論文  参考訳（メタデータ） (2023-06-16T17:00:51Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Convergence of a Normal Map-based Prox-SGD Method under the KL Inequality [0.0]
  我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
  論文  参考訳（メタデータ） (2023-05-10T01:12:11Z)
• An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization [25.21457349137344]
  私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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