論文の概要: Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems

• arxiv url: http://arxiv.org/abs/2301.03113v3
• Date: Sat, 23 Sep 2023 05:46:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-27 04:24:33.399483
• Title: Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems
• Title（参考訳）: ルートフィンディング問題に対するランダム化ブロック座標最適勾配アルゴリズム
• Authors: Quoc Tran-Dinh
• Abstract要約: 大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
• 参考スコア（独自算出の注目度）: 8.0153031008486
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we develop two new randomized block-coordinate optimistic gradient algorithms to approximate a solution of nonlinear equations in large-scale settings, which are called root-finding problems. Our first algorithm is non-accelerated with constant stepsizes, and achieves $\mathcal{O}(1/k)$ best-iterate convergence rate on $\mathbb{E}[ \Vert Gx^k\Vert^2]$ when the underlying operator $G$ is Lipschitz continuous and satisfies a weak Minty solution condition, where $\mathbb{E}[\cdot]$ is the expectation and $k$ is the iteration counter. Our second method is a new accelerated randomized block-coordinate optimistic gradient algorithm. We establish both $\mathcal{O}(1/k^2)$ and $o(1/k^2)$ last-iterate convergence rates on both $\mathbb{E}[ \Vert Gx^k\Vert^2]$ and $\mathbb{E}[ \Vert x^{k+1} - x^{k}\Vert^2]$ for this algorithm under the co-coerciveness of $G$. In addition, we prove that the iterate sequence $\{x^k\}$ converges to a solution almost surely, and $\Vert Gx^k\Vert^2$ attains a $o(1/k)$ almost sure convergence rate. Then, we apply our methods to a class of large-scale finite-sum inclusions, which covers prominent applications in machine learning, statistical learning, and network optimization, especially in federated learning. We obtain two new federated learning-type algorithms and their convergence rate guarantees for solving this problem class.
• Abstract（参考訳）: 本稿では,非線形方程式の大規模解を近似する2つのランダム化ブロック座標勾配アルゴリズムを考案し,これをルートフィンディング問題と呼ぶ。 我々の最初のアルゴリズムは、一定の段数で加速されず、$\mathcal{O}(1/k)$ best-iterate convergence rate on $\mathbb{E}[ \Vert Gx^k\Vert^2]$ となると、基礎作用素 $G$ がリプシッツ連続で弱ミンティ解条件を満たすとき、$\mathbb{E}[\cdot]$ は期待値であり、$k$ は反復カウンタである。 第2の方法は,新しいランダム化ブロック座標勾配アルゴリズムである。 このアルゴリズムに対して,$\mathbb{e}[ \vert gx^k\vert^2]$と$\mathbb{e}[ \vert x^{k+1}x^{k}\vert^2]$の両方において,$\mathcal{o}(1/k^2)$と$o(1/k^2)$とラストイテレート収束率を両立する。 さらに、反復列 $\{x^k\}$ が解にほぼ確実に収束し、$\Vert Gx^k\Vert^2$ が $o(1/k)$ ほぼ確実に収束することを示す。 そこで我々は,機械学習,統計的学習,ネットワーク最適化,特にフェデレート学習における顕著な応用を網羅した大規模有限サム包含のクラスに適用した。 そこで本研究では,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)

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

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