論文の概要: Order Optimal One-Shot Federated Learning for non-Convex Loss Functions
- arxiv url: http://arxiv.org/abs/2108.08677v1
- Date: Thu, 19 Aug 2021 13:38:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-20 20:35:39.136577
- Title: Order Optimal One-Shot Federated Learning for non-Convex Loss Functions
- Title（参考訳）: 非凸損失関数に対する次数最適単発フェデレート学習
- Authors: Arsalan Sharifnassab, Saber Salehkaleybar, S. Jamaloddin Golestani
- Abstract要約: 我々は、$m$マシンが存在し、それぞれが$n$未知の損失関数を観測するワンショット設定の問題を考える。
非凸損失関数(MRENC)のための分散学習アルゴリズムであるMulti-Resolution Estororを提案する。
MRE-NCは、合成誤差と実データとのバウンドという点で最適であることを示す。
- 参考スコア（独自算出の注目度）: 22.151396281190227
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of federated learning in a one-shot setting in which
there are $m$ machines, each observing $n$ samples function from an unknown
distribution on non-convex loss functions. Let $F:[-1,1]^d\to\mathbb{R}$ be the
expected loss function with respect to this unknown distribution. The goal is
to find an estimate of the minimizer of $F$. Based on its observations, each
machine generates a signal of bounded length $B$ and sends it to a server. The
sever collects signals of all machines and outputs an estimate of the minimizer
of $F$. We propose a distributed learning algorithm, called Multi-Resolution
Estimator for Non-Convex loss function (MRE-NC), whose expected error is
bounded by $\max\big(1/\sqrt{n}(mB)^{1/d}, 1/\sqrt{mn}\big)$, up to
polylogarithmic factors. We also provide a matching lower bound on the
performance of any algorithm, showing that MRE-NC is order optimal in terms of
$n$ and $m$. Experiments on synthetic and real data show the effectiveness of
MRE-NC in distributed learning of model's parameters for non-convex loss
functions.
- Abstract（参考訳）: 我々は,非凸損失関数上の未知分布から$m$のサンプル関数を観測し,それぞれが$m$のマシンを持つワンショット環境でのフェデレーション学習の問題を考察する。
F:[-1,1]^d\to\mathbb{R}$ をこの未知分布に対する期待損失関数とする。
目標は、最小値が$f$の見積もりを見つけることである。
その観察に基づいて、各マシンは有界長$b$の信号を生成し、それをサーバに送る。
severはすべてのマシンの信号を収集し、最小値である$f$の見積もりを出力する。
我々は,非凸損失関数(MRE-NC)に対する多解解推定アルゴリズムを提案し,予測誤差を$\max\big(1/\sqrt{n}(mB)^{1/d}, 1/\sqrt{mn}\big)$で有界化する。
また,MRE-NCが$n$と$m$という条件で最適であることを示す。
非凸損失関数に対するモデルパラメータの分散学習におけるMRE-NCの有効性を示す。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - A note on $L^1$-Convergence of the Empiric Minimizer for unbounded
functions with fast growth [0.0]
V : mathbbRd to mathbbR$ coercive に対して、経験的最小値の$L1$-distance の収束率について検討する。
一般に、高速な成長を持つ非有界函数に対しては、収束率は上述の$a_n n-1/q$で制限され、$q$は潜在確率変数の次元である。
論文 参考訳（メタデータ） (2023-03-08T08:46:13Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。
本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文 参考訳（メタデータ） (2022-05-28T05:13:45Z) - Private Convex Optimization via Exponential Mechanism [16.867534746193833]
我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。
また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
論文 参考訳（メタデータ） (2022-03-01T06:51:03Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。
我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。
我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文 参考訳（メタデータ） (2020-10-16T08:10:02Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。