論文の概要: Distributed Sparse Feature Selection in Communication-Restricted
Networks
- arxiv url: http://arxiv.org/abs/2111.02802v1
- Date: Tue, 2 Nov 2021 05:02:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-06 05:10:20.155344
- Title: Distributed Sparse Feature Selection in Communication-Restricted
Networks
- Title(参考訳): 通信制限ネットワークにおける分散スパース特徴選択
- Authors: Hanie Barghi, Amir Najafi, and Seyed Abolfazl Motahari
- Abstract要約: 疎線形回帰と特徴選択のための新しい分散スキームを提案し,理論的に解析する。
データセット全体から因果次元を推定するために,ネットワーク内の情報共有をシンプルかつ効果的に行う手法を提案する。
- 参考スコア(独自算出の注目度): 6.9257380648471765
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper aims to propose and theoretically analyze a new distributed scheme
for sparse linear regression and feature selection. The primary goal is to
learn the few causal features of a high-dimensional dataset based on noisy
observations from an unknown sparse linear model. However, the presumed
training set which includes $n$ data samples in $\mathbb{R}^p$ is already
distributed over a large network with $N$ clients connected through extremely
low-bandwidth links. Also, we consider the asymptotic configuration of $1\ll
N\ll n\ll p$. In order to infer the causal dimensions from the whole dataset,
we propose a simple, yet effective method for information sharing in the
network. In this regard, we theoretically show that the true causal features
can be reliably recovered with negligible bandwidth usage of $O\left(N\log
p\right)$ across the network. This yields a significantly lower communication
cost in comparison with the trivial case of transmitting all the samples to a
single node (centralized scenario), which requires $O\left(np\right)$
transmissions. Even more sophisticated schemes such as ADMM still have a
communication complexity of $O\left(Np\right)$. Surprisingly, our sample
complexity bound is proved to be the same (up to a constant factor) as the
optimal centralized approach for a fixed performance measure in each node,
while that of a na\"{i}ve decentralized technique grows linearly with $N$.
Theoretical guarantees in this paper are based on the recent analytic framework
of debiased LASSO in Javanmard et al. (2019), and are supported by several
computer experiments performed on both synthetic and real-world datasets.
- Abstract(参考訳): 本稿では,疎線形回帰と特徴選択のための新しい分散スキームの提案と理論的解析を目的とする。
主な目的は、未知のスパース線形モデルからのノイズ観測に基づいて、高次元データセットのいくつかの因果的特徴を学ぶことである。
しかし、$\mathbb{R}^p$の$n$データサンプルを含む推定トレーニングセットは、非常に低帯域幅のリンクを介してN$クライアントが接続された大きなネットワーク上で既に分散されている。
また、1\ll N\ll n\ll p$ の漸近構成を考える。
データセット全体から因果次元を推定するために,ネットワークにおける情報共有のための単純かつ効果的な手法を提案する。
本稿では,ネットワーク全体にわたる$O\left(N\log p\right)$を無視して,真の因果的特徴を確実に回復できることを理論的に示す。
これにより、すべてのサンプルを単一のノード(中央化シナリオ)に送信する簡単なケースと比較して、通信コストが大幅に低減され、これには$o\left(np\right)$の送信が必要となる。
ADMMのようなさらに洗練されたスキームは、通信複雑性が$O\left(Np\right)$である。
意外なことに、我々のサンプルの複雑性境界は、各ノードにおける固定性能測定の最適集中的アプローチと同じ(定数係数まで)であることが証明され、na\"{i}ve 分散化技術は$N$で線形に成長する。
本論文の理論的保証は, Javanmard et al. (2019) における脱バイアスLASSOの最近の分析枠組みに基づいており, 合成および実世界のデータセット上で行われたいくつかの計算機実験によって支持されている。
関連論文リスト
- Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods [43.32546195968771]
本研究では,スムーズなアクティベーションを有するニューラルネットワークに対する勾配法におけるデータ依存収束と一般化挙動について検討する。
我々の結果は、よく確立されたRadecher複雑性に基づく境界の欠点を改善した。
XOR分布の分類において、NTK体制の結果に対して大きなステップサイズが大幅に改善されることが示されている。
論文 参考訳(メタデータ) (2024-10-13T21:49:29Z) - 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) - Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNs [42.551773746803946]
視覚タスクは局所性と翻訳不変性の特性によって特徴づけられる。
これらのタスクにおける畳み込みニューラルネットワーク(CNN)の優れた性能は、そのアーキテクチャに埋め込まれた局所性や重み付けの帰納的バイアスに起因する。
CNNにおけるこれらのバイアスの統計的利点を、局所連結ニューラルネットワーク(LCN)と完全連結ニューラルネットワーク(FCN)で定量化しようとする試みは、以下のカテゴリに分類される。
論文 参考訳(メタデータ) (2024-03-23T03:57:28Z) - Collaborative non-parametric two-sample testing [55.98760097296213]
目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。
グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。
提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
論文 参考訳(メタデータ) (2024-02-08T14:43:56Z) - On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks [13.2844023993979]
フェデレートラーニング(FL)は、ローカルデータを共有せずに複数のクライアントから機械学習モデルを協調的に作成するための分散パラダイムである。
本稿では,FedAvgが世界規模で世界規模で収束していることを示す。
論文 参考訳(メタデータ) (2023-10-09T07:56:56Z) - 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) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳(メタデータ) (2022-04-11T17:26:19Z) - High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees [20.701475313495884]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳(メタデータ) (2022-01-21T01:26:08Z) - Besov Function Approximation and Binary Classification on
Low-Dimensional Manifolds Using Convolutional Residual Networks [42.43493635899849]
畳み込み残余ネットワーク(ConvResNet)の理論的保証を関数近似および二項分類の統計的推定の観点から確立する。
その結果,ConvResNetsはデータセットの低次元構造に適応していることがわかった。
論文 参考訳(メタデータ) (2021-09-07T02:58:11Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - OSLNet: Deep Small-Sample Classification with an Orthogonal Softmax
Layer [77.90012156266324]
本稿では,ニューラルネットワークのサブスペースを見つけることを目的としている。
そこで本研究では,Orthogonal Softmax Layer (OSL) を提案する。
実験結果から,提案OSLは4つの小サンプルベンチマークデータセットとの比較に用いた手法よりも優れた性能を示した。
論文 参考訳(メタデータ) (2020-04-20T02:41:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。