論文の概要: Differentially Quantized Gradient Methods

• arxiv url: http://arxiv.org/abs/2002.02508v4
• Date: Tue, 26 Apr 2022 20:45:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-03 10:10:36.617628
• Title: Differentially Quantized Gradient Methods
• Title（参考訳）: 微分量子化勾配法
• Authors: Chung-Yi Lin, Victoria Kostina, and Babak Hassibi
• Abstract要約: 微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。 あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
• 参考スコア（独自算出の注目度）: 53.3186247068836
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider the following distributed optimization scenario. A worker has access to training data that it uses to compute the gradients while a server decides when to stop iterative computation based on its target accuracy or delay constraints. The server receives all its information about the problem instance from the worker via a rate-limited noiseless communication channel. We introduce the principle we call Differential Quantization (DQ) that prescribes compensating the past quantization errors to direct the descent trajectory of a quantized algorithm towards that of its unquantized counterpart. Assuming that the objective function is smooth and strongly convex, we prove that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $\max\{\sigma_{\mathrm{GD}}, \rho_n 2^{-R}\}$, where $\sigma_{\mathrm{GD}}$ is the contraction factor of unquantized gradient descent (GD), $\rho_n \geq 1$ is the covering efficiency of the quantizer, and $R$ is the bitrate per problem dimension $n$. Thus at any $R\geq\log_2 \rho_n /\sigma_{\mathrm{GD}}$ bits, the contraction factor of DQ-GD is the same as that of unquantized GD, i.e., there is no loss due to quantization. We show that no algorithm within a certain class can converge faster than $\max\{\sigma_{\mathrm{GD}}, 2^{-R}\}$. Since quantizers exist with $\rho_n \to 1$ as $n \to \infty$ (Rogers, 1963), this means that DQ-GD is asymptotically optimal. The principle of differential quantization continues to apply to gradient methods with momentum such as Nesterov's accelerated gradient descent, and Polyak's heavy ball method. For these algorithms as well, if the rate is above a certain threshold, there is no loss in contraction factor obtained by the differentially quantized algorithm compared to its unquantized counterpart. Experimental results on least-squares problems validate our theoretical analysis.
• Abstract（参考訳）: 以下の分散最適化シナリオを考えてみよう。 ワーカーは勾配を計算するために使用するトレーニングデータにアクセスし、サーバは目標の精度や遅延制約に基づいて反復計算をいつ停止するかを決定する。 サーバは、レート制限されたノイズレス通信チャネルを介して、ワーカーから問題インスタンスに関するすべての情報を受信する。 本稿では,従来の量子化誤差を補正して,量子化アルゴリズムの降下軌道を非定量化アルゴリズムの軌道に向ける微分量子化(DQ)の原理を紹介する。 目的関数が滑らかで強い凸であると仮定すると、微分量子化勾配降下 (dq-gd) は、次の線型縮約係数 $max\{\sigma_{\mathrm{gd}}, \rho_n 2^{-r}\}$, ここで、$\sigma_{\mathrm{gd}}$ は非量子化勾配降下 (gd) の縮約係数、$\rho_n \geq 1$ は量子化器の被覆効率、$r$ は問題次元あたりのビットレート $n$ である。 したがって、任意の$R\geq\log_2 \rho_n /\sigma_{\mathrm{GD}}$ bits において、DQ-GD の収縮係数は非定量化 GD と同じであり、量子化による損失はない。 我々は、あるクラス内のアルゴリズムが$\max\{\sigma_{\mathrm{gd}}, 2^{-r}\}$よりも高速に収束できることを示す。 量子化器は$\rho_n \to 1$ as $n \to \infty$ (Rogers, 1963) として存在するので、DQ-GD は漸近的に最適である。 微分量子化の原理は、ネステロフの加速勾配降下やポリアクの重球法のような運動量を持つ勾配法に適用され続けている。 これらのアルゴリズムについても、レートが一定のしきい値を超える場合、差分量子化アルゴリズムによって得られる収縮係数が、その未定量化アルゴリズムと比較して失われることはない。 最小二乗問題に関する実験結果は、我々の理論解析を検証する。

関連論文リスト

• Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
  本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。 具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
  論文  参考訳（メタデータ） (2024-08-21T01:39:42Z)
• Quantum state tomography via non-convex Riemannian gradient descent [13.100184125419691]
  本研究では,kappa$のスケール依存性を改善する量子状態トモグラフィースキームを導出する。 この改良は、非多様体勾配(RGD)アルゴリズムの適用によるものである。 超高速収束とほぼ最適誤差境界の理論的結果は数値的な結果と相関する。
  論文  参考訳（メタデータ） (2022-10-10T14:19:23Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• Generalization Bounds for Gradient Methods via Discrete and Continuous Prior [8.76346911214414]
  次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。 また、あるSGDの変種に対する新しい境界を得ることもできる。
  論文  参考訳（メタデータ） (2022-05-27T07:23:01Z)
• Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
  我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。 繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。 要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
  論文  参考訳（メタデータ） (2021-12-29T14:47:56Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)

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

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