論文の概要: Distributed Saddle-Point Problems Under Similarity

• arxiv url: http://arxiv.org/abs/2107.10706v1
• Date: Thu, 22 Jul 2021 14:25:16 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-23 15:18:51.385342
• Title: Distributed Saddle-Point Problems Under Similarity
• Title（参考訳）: 類似性を考慮した分散saddle-point問題
• Authors: Aleksandr Beznosikov, Gesualdo Scutari, Alexander Rogozin, Alexander Gasnikov
• Abstract要約: 与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
• 参考スコア（独自算出の注目度）: 173.19083235638104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study solution methods for (strongly-)convex-(strongly)-concave Saddle-Point Problems (SPPs) over networks of two type - master/workers (thus centralized) architectures and meshed (thus decentralized) networks. The local functions at each node are assumed to be similar, due to statistical data similarity or otherwise. We establish lower complexity bounds for a fairly general class of algorithms solving the SPP. We show that a given suboptimality $\epsilon>0$ is achieved over master/workers networks in $\Omega\big(\Delta\cdot \delta/\mu\cdot \log (1/\varepsilon)\big)$ rounds of communications, where $\delta>0$ measures the degree of similarity of the local functions, $\mu$ is their strong convexity constant, and $\Delta$ is the diameter of the network. The lower communication complexity bound over meshed networks reads $\Omega\big(1/{\sqrt{\rho}} \cdot {\delta}/{\mu}\cdot\log (1/\varepsilon)\big)$, where $\rho$ is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. We then propose algorithms matching the lower bounds over either types of networks (up to log-factors). We assess the effectiveness of the proposed algorithms on a robust logistic regression problem.
• Abstract（参考訳）: 本研究では,2種類のマスタ/ワーカ(集中型)アーキテクチャとメッシュ(分散型)ネットワークのネットワーク上での(強い)凸(強結合型)サドルポイント問題(SPP)の解法について検討する。 各ノードの局所関数は、統計データの類似性などにより類似していると仮定される。 SPPを解くアルゴリズムの比較的一般的なクラスに対して、より低い複雑性境界を確立する。 与えられたサブ最適度 $\epsilon>0$ は$\Omega\big (\Delta\cdot \delta/\mu\cdot \log (1/\varepsilon)\big)$ 通信のラウンドであり、$\delta>0$ は局所関数の類似度を測り、$\mu$ は強凸定数であり、$\Delta$ はネットワークの直径であることを示す。 メッシュネットワーク上の低い通信複雑性は$\Omega\big(1/{\sqrt{\rho}} \cdot {\delta}/{\mu}\cdot\log (1/\varepsilon)\big)$, ここで$\rho$は、近隣ノード間の通信に使用されるゴシップ行列の(正規化された)固有ギャップである。 次に、いずれかのネットワーク(ログファクタまで)の下位境界に一致するアルゴリズムを提案する。 本研究ではロバストロジスティック回帰問題に対する提案アルゴリズムの有効性を評価する。

関連論文リスト

• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。 我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
  論文  参考訳（メタデータ） (2024-05-25T08:34:49Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。 このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。 シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
  論文  参考訳（メタデータ） (2023-05-25T22:27:42Z)
• 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)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• High-Dimensional Inference over Networks: Linear Convergence and Statistical Guarantees [20.701475313495884]
  エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。 分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
  論文  参考訳（メタデータ） (2022-01-21T01:26:08Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Maximizing Influence of Leaders in Social Networks [15.05158252504978]
  我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。 提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
  論文  参考訳（メタデータ） (2021-06-11T02:31:46Z)
• Impact of Community Structure on Consensus Machine Learning [0.17188280334580192]
  ブロックモデルから引き出されたネットワーク上でのコンセンサス機械学習について検討する。 私たちは、$tau_epsilon$が低い境界に達するような、コミュニティ構造の重要なレベルが存在することに気付きました。
  論文  参考訳（メタデータ） (2020-11-02T21:41:35Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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