論文の概要: Fundamental limits of over-the-air optimization: Are analog schemes
optimal?
- arxiv url: http://arxiv.org/abs/2109.05222v2
- Date: Wed, 15 Sep 2021 06:38:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-17 13:46:29.946739
- Title: Fundamental limits of over-the-air optimization: Are analog schemes
optimal?
- Title（参考訳）: オーバー・ザ・エア最適化の基本限界:アナログスキームは最適か?
- Authors: Shubham K Jha, Prathamesh Mayekar, Himanshu Tyagi
- Abstract要約: その結果,SNR の低値に対して$sqrtd$ の係数で収束速度が低下することがわかった。
注目すべきは、$Amplitude$$Shift$$Keying$を使用し、ほぼすべてのSNRにおける最適収束率を達成する単純な量子化・変調スキームを示すことである。
- 参考スコア（独自算出の注目度）: 23.71982686172067
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider over-the-air convex optimization on a $d-$dimensional space where
coded gradients are sent over an additive Gaussian noise channel with variance
$\sigma^2$. The codewords satisfy an average power constraint $P$, resulting in
the signal-to-noise ratio (SNR) of $P/\sigma^2$. We derive bounds for the
convergence rates for over-the-air optimization. Our first result is a lower
bound for the convergence rate showing that any code must slowdown the
convergence rate by a factor of roughly $\sqrt{d/\log(1+\mathtt{SNR})}$. Next,
we consider a popular class of schemes called $analog$ $coding$, where a linear
function of the gradient is sent. We show that a simple scaled transmission
analog coding scheme results in a slowdown in convergence rate by a factor of
$\sqrt{d(1+1/\mathtt{SNR})}$. This matches the previous lower bound up to
constant factors for low SNR, making the scaled transmission scheme optimal at
low SNR. However, we show that this slowdown is necessary for any analog coding
scheme. In particular, a slowdown in convergence by a factor of $\sqrt{d}$ for
analog coding remains even when SNR tends to infinity. Remarkably, we present a
simple quantize-and-modulate scheme that uses $Amplitude$ $Shift$ $Keying$ and
almost attains the optimal convergence rate at all SNRs.
- Abstract（参考訳）: 符号付き勾配が分散$\sigma^2$の付加ガウス雑音チャネルに送られるような$d-$次元空間上での空対最適化を考える。
符号語は平均電力制約$P$を満たすため、信号対雑音比(SNR)は$P/\sigma^2$となる。
オーバー・ザ・エア最適化のための収束率の境界を導出する。
最初の結果は収束率の低い値であり、任意のコードが約$\sqrt{d/\log(1+\mathtt{SNR})}$で収束率を遅くしなければならないことを示す。
次に、勾配の線形関数が送られる$analog$$coding$と呼ばれる一般的なスキームのクラスを考える。
単純なスケールの伝達アナログ符号化方式は、$\sqrt{d(1+1/\mathtt{SNR})}$で収束速度を遅くすることを示した。
これは、前の下界を低いSNRの定数要素に一致させ、低いSNRでスケールされた送信方式を最適にする。
しかし,この遅延は任意のアナログ符号化方式に必要であることを示す。
特に、アナログ符号に対する$\sqrt{d}$の係数による収束の減速は、SNRが無限大の傾向にあるときでも残っている。
注目すべきは、$Amplitude$$Shift$$Keying$を使用し、ほぼすべてのSNRにおける最適収束率を達成する単純な量子化・変調スキームを示すことである。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。
我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
論文 参考訳（メタデータ） (2022-07-26T08:47:54Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳（メタデータ） (2020-09-30T04:44:45Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。