論文の概要: Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees
- arxiv url: http://arxiv.org/abs/2201.08507v2
- Date: Thu, 26 Dec 2024 17:00:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-30 17:21:02.839988
- Title: Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees
- Title（参考訳）: 勾配追従による分散スパース線形回帰--線形収束と統計的保証-
- Authors: Marie Maros, Gesualdo Scutari, Ying Sun, Guang Cheng,
- Abstract要約: エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
- 参考スコア（独自算出の注目度）: 23.256961881716595
- License:
- Abstract: We study sparse linear regression over a network of agents, modeled as an undirected graph and no server node. The estimation of the $s$-sparse parameter is formulated as a constrained LASSO problem wherein each agent owns a subset of the $N$ total observations. We analyze the convergence rate and statistical guarantees of a distributed projected gradient tracking-based algorithm under high-dimensional scaling, allowing the ambient dimension $d$ to grow with (and possibly exceed) the sample size $N$. Our theory shows that, under standard notions of restricted strong convexity and smoothness of the loss functions, suitable conditions on the network connectivity and algorithm tuning, the distributed algorithm converges globally at a {\it linear} rate to an estimate that is within the centralized {\it statistical precision} of the model, $O(s\log d/N)$. When $s\log d/N=o(1)$, a condition necessary for statistical consistency, an $\varepsilon$-optimal solution is attained after $\mathcal{O}(\kappa \log (1/\varepsilon))$ gradient computations and $O (\kappa/(1-\rho) \log (1/\varepsilon))$ communication rounds, where $\kappa$ is the restricted condition number of the loss function and $\rho$ measures the network connectivity. The computation cost matches that of the centralized projected gradient algorithm despite having data distributed; whereas the communication rounds reduce as the network connectivity improves. Overall, our study reveals interesting connections between statistical efficiency, network connectivity \& topology, and convergence rate in high dimensions.
- Abstract（参考訳）: エージェントのネットワーク上での疎線形回帰について検討し、非指向グラフとしてモデル化し、サーバノードを持たない。
s$-sparseパラメータの推定は制約付きLASSO問題として定式化され、各エージェントが$N$全観測のサブセットを所有する。
我々は,高次元スケーリング下での分散予測勾配追跡アルゴリズムの収束率と統計的保証を分析し,サンプルサイズ$N$で周囲次元$d$を成長させる(そしておそらく超える)。
我々の理論は、損失関数の厳密な凸性や滑らかさ、ネットワーク接続性やアルゴリズムチューニングの適切な条件といった標準的な概念の下で、分散アルゴリズムは、モデルの中心的な統計精度である$O(s\log d/N)$の範囲内にある推定値に、全世界的に収束することを示している。
統計的整合性に必要な条件である$s\log d/N=o(1)$が得られたとき、$\varepsilon$-optimal Solutionは、$\mathcal{O}(\kappa \log (1/\varepsilon))$グルーフ計算と$O(\kappa/(1-\rho) \log (1/\varepsilon)$通信ラウンドの後、$\kappa$は損失関数の制限条件数であり、$\rho$はネットワーク接続を測定する。
計算コストは、データが分散されているにもかかわらず、集中的に予測される勾配アルゴリズムと一致し、一方、通信ラウンドはネットワーク接続性が向上するにつれて減少する。
本研究は, 統計効率, ネットワーク接続, トポロジ, 高次元収束率の興味深い関係を明らかにする。
関連論文リスト
- Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。
このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。
次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。
i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。
その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
論文 参考訳（メタデータ） (2024-04-18T16:46:08Z) - Generalization and Stability of Interpolating Neural Networks with
Minimal Width [37.908159361149835]
補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。
トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。
m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
論文 参考訳（メタデータ） (2023-02-18T05:06:15Z) - 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) - On the Effective Number of Linear Regions in Shallow Univariate ReLU
Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。
我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
論文 参考訳（メタデータ） (2022-05-18T16:57:10Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳（メタデータ） (2022-02-08T12:58:14Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳（メタデータ） (2021-11-12T01:51:50Z) - Distributed Sparse Feature Selection in Communication-Restricted
Networks [6.9257380648471765]
疎線形回帰と特徴選択のための新しい分散スキームを提案し,理論的に解析する。
データセット全体から因果次元を推定するために,ネットワーク内の情報共有をシンプルかつ効果的に行う手法を提案する。
論文 参考訳（メタデータ） (2021-11-02T05:02:24Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。