論文の概要: High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees
- arxiv url: http://arxiv.org/abs/2201.08507v1
- Date: Fri, 21 Jan 2022 01:26:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-24 20:05:27.699244
- Title: High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees
- Title（参考訳）: ネットワーク上の高次元推論:線形収束と統計的保証
- Authors: Ying Sun and Marie Maros and Gesualdo Scutari and Guang Cheng
- Abstract要約: エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
- 参考スコア（独自算出の注目度）: 20.701475313495884
- License: http://creativecommons.org/licenses/by/4.0/
- 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$はネットワーク接続を測定する。
計算コストは、データ分散にもかかわらず集中型投影勾配アルゴリズムのそれと一致するが、ネットワーク接続性が向上するにつれて通信ラウンドは減少する。
総じて,統計効率,ネットワーク接続性 \&トポロジー,高次元収束率の相関性について検討した。
関連論文リスト
- Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization [0.552480439325792]
パラメトリックな特徴を持つ不完全な情報を持つ分散最適化問題として$n$のエージェントを考える。
本稿では,各エージェントが未知パラメータの現在の信念を更新する分散近似アルゴリズムを提案する。
アルゴリズムの性能に影響を与える因子を定量的に解析し、決定変数の平均二乗誤差が$mathcalO(frac1nk)+mathcalOleft(frac1sqrtn (1-rho_w)right)frac1k1.5で有界であることを証明する。
論文 参考訳（メタデータ） (2024-04-21T14:18:49Z) - Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。