論文の概要: Fundamental limits of over-the-air optimization: Are analog schemes optimal?

• arxiv url: http://arxiv.org/abs/2109.05222v1
• Date: Sat, 11 Sep 2021 08:50:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-17 13:19:30.257231
• Title: Fundamental limits of over-the-air optimization: Are analog schemes optimal?
• Title（参考訳）: オーバー・ザ・エア最適化の基本限界:アナログスキームは最適か?
• Authors: Shubham K Jha, Prathamesh Mayekar, Himanshu Tyagi
• Abstract要約: スケールされた伝送アナログ符号化方式は、sqrtd (1 + 1/SNR) の係数による収束速度の低下をもたらすことを示す。 注目すべきは、振幅シフト鍵を使い、ほぼ全ての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 + 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/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を満たすので、P/\sigma^2の信号対雑音比(SNR)が得られる。 オーバー・ザ・エア最適化のための収束率の境界を導出する。 最初の結果は収束率の低い値であり、任意のコードが約 \sqrt{d/log(1 + SNR)} の係数で収束率を遅くしなければならないことを示す。 次に、勾配の線形関数が送信されるアナログ符号化と呼ばれる一般的なスキームのクラスを考える。 単純なスケールの伝送アナログ符号化方式は, 収束速度を, \sqrt{d(1 + 1/SNR)} の係数で遅くすることを示した。 これは、前の下界を低いSNRの定数要素に一致させ、低いSNRでスケールされた送信方式を最適にする。 しかし,この遅延は任意のアナログ符号化方式に必要であることを示す。 特に、アナログ符号に対する \sqrt{d} の係数による収束の減速は、SNR が無限大の傾向にあるときでも残っている。 振幅シフトキーを用いた簡易量子化・変調スキームを提案し,全snrsの最適収束率をほぼ達成した。

関連論文リスト

• Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent [17.73720530889677]
  行列センシング問題の収束を早めるためのプレコンディショニング手法が提案されている。 本稿では,2因子パラメータを交互に更新するAPGDアルゴリズムを提案する。 理論的には、任意の乱数から始まる線形速度で APGD が準最適収束を達成することを証明している。
  論文  参考訳（メタデータ） (2025-02-01T15:44:39Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• 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)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。