論文の概要: Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization

• arxiv url: http://arxiv.org/abs/2610.05789v1
• Date: Mon, 05 Oct 2026 04:37:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 04:20:09.945641
• Title: Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
• Title（参考訳）: 次元自由分散非平滑非凸確率最適化
• Abstract要約: 私たちは$n$ノードのネットワーク上に$()$-Goldsteinの固定子を見つけます。 $d$への依存は、高次元のレジームにおいて大きなボトルネックとなる。 対数$d$への依存は、追加の通信だけで取り除くことができることを示す。
• 参考スコア（独自算出の注目度）: 59.290497104061835
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate decentralized nonsmooth nonconvex stochastic optimization over a network of $n$ nodes, with the goal of finding an $(δ,ε)$-Goldstein stationary point. The best existing algorithm achieves $O(δ^{-1}(ε^{-3}+dε^{-1}))$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}(ε^{-3}+dε^{-1}))$ communication complexity, where $d$ is the problem dimension and $γ$ is the spectral gap of the communication matrix. However, the polynomial dependence on $d$ can be a major bottleneck in high-dimensional regimes. In this paper, we propose a novel algorithm that achieves $O(δ^{-1}ε^{-3})$ sample complexity and $\widetilde{O}(γ^{-1/2}δ^{-1}ε^{-3})$ communication complexity. The primary technique is an elegant decentralized online-to-nonconvex conversion that reduces the original problem to a decentralized online convex optimization (D-OCO) problem. A key property of our conversion is that its consensus requirements can be inherited directly from the consensus of the underlying D-OCO decisions. In particular, this property enables us to establish an explicit connection between the dimension dependence and the consensus error, which in turn shows that the polynomial dependence on $d$ can be removed with only logarithmic additional communication.
• Abstract（参考訳）: 我々は、$(δ,ε)$-Goldstein定常点を求めることを目的として、$n$ノードのネットワーク上での非平滑な非凸確率最適化について検討する。 最も優れた既存のアルゴリズムは、サンプル複雑性$O(δ^{-1}(ε^{-3}+dε^{-1})と$\widetilde{O}(γ^{-1/2}δ^{-1}(ε^{-3}+dε^{-1}))を、通信複雑性$d$は問題次元で$γ$は通信行列のスペクトルギャップである。 しかし、$d$の多項式依存は高次元のレジームにおいて大きなボトルネックとなる。 本稿では,O(δ^{-1}ε^{-3})$サンプル複雑性と$\widetilde{O}(γ^{-1/2}δ^{-1}ε^{-3})$通信複雑性を実現する新しいアルゴリズムを提案する。 第一のテクニックはエレガントな分散オンライン-非凸変換であり、元の問題を分散オンライン凸最適化(D-OCO)問題に還元する。 我々の変換の重要な特性は、そのコンセンサス要件が、基礎となるD-OCO決定のコンセンサスから直接受け継がれることである。 特に、この性質により、次元依存とコンセンサス誤差との明示的な接続が確立でき、従って$d$の多項式依存は対数的な付加的な通信だけで取り除けることを示す。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。 代理オラクル関数に対するゼロ階量子推定器を構築する。
  論文  参考訳（メタデータ） (2024-10-21T16:52:26Z)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
  Decentralized Recursive Dec. Method (DREAM) 具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。 我々の数値実験は,従来の手法の優越性を検証した。
  論文  参考訳（メタデータ） (2022-12-05T16:09:39Z)
• On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
  分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
  論文  参考訳（メタデータ） (2021-07-22T14:25:16Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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