論文の概要: Distributed Sparse Regression via Penalization
- arxiv url: http://arxiv.org/abs/2111.06530v1
- Date: Fri, 12 Nov 2021 01:51:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-15 14:13:02.656644
- Title: Distributed Sparse Regression via Penalization
- Title（参考訳）: ペナリゼーションによる分散スパース回帰
- Authors: Yao Ji, Gesualdo Scutari, Ying Sun, and Harsha Honnappa
- Abstract要約: エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
- 参考スコア（独自算出の注目度）: 6.6805526070045085
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study sparse linear regression over a network of agents, modeled as an
undirected graph (with no centralized node). The estimation problem is
formulated as the minimization of the sum of the local LASSO loss functions
plus a quadratic penalty of the consensus constraint -- the latter being
instrumental to obtain distributed solution methods. While penalty-based
consensus methods have been extensively studied in the optimization literature,
their statistical and computational guarantees in the high dimensional setting
remain unclear. This work provides an answer to this open problem. Our
contribution is two-fold. First, we establish statistical consistency of the
estimator: under a suitable choice of the penalty parameter, the optimal
solution of the penalized problem achieves near optimal minimax rate
$\mathcal{O}(s \log d/N)$ in $\ell_2$-loss, where $s$ is the sparsity value,
$d$ is the ambient dimension, and $N$ is the total sample size in the network
-- this matches centralized sample rates. Second, we show that the
proximal-gradient algorithm applied to the penalized problem, which naturally
leads to distributed implementations, converges linearly up to a tolerance of
the order of the centralized statistical error -- the rate scales as
$\mathcal{O}(d)$, revealing an unavoidable speed-accuracy dilemma.Numerical
results demonstrate the tightness of the derived sample rate and convergence
rate scalings.
- Abstract（参考訳）: エージェントのネットワーク上での疎線形回帰を非指向グラフ(集中ノードを持たない)としてモデル化する。
推定問題は、局所的なLASSO損失関数の和の最小化とコンセンサス制約の2次ペナルティとして定式化され、後者は分散解法を得るのに役立つ。
ペナルティに基づくコンセンサス法は最適化文献で広く研究されているが、高次元設定における統計的および計算的保証は未だ不明である。
この作品は、このオープンな問題に対する答えを提供する。
私たちの貢献は2倍です。
まず、ペナルティパラメータの適切な選択の下で、ペナルティ化された問題の最適解は、最適なミニマックスレート $\mathcal{O}(s \log d/N)$ in $\ell_2$-loss, ここで、$s$は空間値、$d$は周辺次元、$N$はネットワーク内の全サンプルサイズである。
第2に, 分散実装を自然に導くペナル化問題に適用した近似勾配アルゴリズムは, 集中統計誤差の順序の耐性に線形に収束し, 速度は$\mathcal{O}(d)$とスケールし, 避けられない速度精度ジレンマを示す。
関連論文リスト
- 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) - Improved Analysis of Score-based Generative Modeling: User-Friendly
Bounds under Minimal Smoothness Assumptions [9.953088581242845]
2次モーメントを持つ任意のデータ分布に対して,コンバージェンス保証と複雑性を提供する。
我々の結果は、対数共空性や機能的不等式を前提としない。
我々の理論解析は、異なる離散近似の比較を提供し、実際の離散化点の選択を導くかもしれない。
論文 参考訳（メタデータ） (2022-11-03T15:51:00Z) - Distributed Estimation and Inference for Semi-parametric Binary Response Models [8.309294338998539]
本稿では,分散コンピューティング環境下での半パラメトリック二値選択モデルの最大スコア推定について検討する。
直感的な分割・対数推定器は計算コストが高く、機械数に対する非正規制約によって制限される。
論文 参考訳（メタデータ） (2022-10-15T23:06:46Z) - High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees [20.701475313495884]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳（メタデータ） (2022-01-21T01:26:08Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - Distributionally Robust Optimization with Markovian Data [8.126833795693699]
本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。
本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
論文 参考訳（メタデータ） (2021-06-12T10:59:02Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。