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

• arxiv url: http://arxiv.org/abs/2301.03113v4
• Date: Mon, 27 Jan 2025 16:36:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-29 16:38:53.548988
• Title: Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems
• Title（参考訳）: ルートフィンディング問題に対するランダム化ブロック座標最適勾配アルゴリズム
• Authors: Quoc Tran-Dinh, Yang Luo,
• Abstract要約: 大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
• 参考スコア（独自算出の注目度）: 11.15373699918747
• License:
• 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 $k\Vert Gx^k\Vert$ 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つの新しいランダム化ブロック座標型楽観的勾配アルゴリズムを開発し,これをルートフィニング問題(root-finding problem)と呼ぶ。 我々の最初のアルゴリズムは、一定の段数で加速されず、$\mathcal{O}(1/k)$ best-iterate convergence rate on $\mathbb{E}[ \Vert Gx^k\Vert^2]$ となると、基礎作用素 $G$ がリプシッツ連続で弱ミンティ解条件を満たすとき、$\mathbb{E}[\cdot]$ は期待値であり、$k$ は反復カウンタである。 第2の手法は、ランダム化されたブロック座標の楽観的勾配アルゴリズムである。 我々は$\mathcal{O}(1/k^2)$と$o(1/k^2)$の両方を$\mathbb{E}[ \Vert Gx^k\Vert^2]$と$\mathbb{E}[ \Vert x^{k+1}] - x^{k}\Vert^2]$に設定する。 さらに、反復列 $\{x^k\}$ が解にほぼ確実に収束し、$k\Vert Gx^k\Vert$ が $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)
• 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)
• How Do You Want Your Greedy: Simultaneous or Repeated? [41.440943886672855]
  制約付き部分モジュラーユリアに対する決定論的アルゴリズムであるSimultaneousGreedysを提案する。 また、これらのアルゴリズムを実装するパッケージであるSubmodularGreedyも提示する。
  論文  参考訳（メタデータ） (2020-09-29T13:34:09Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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