Pith. sign in

REVIEW 2 major objections 4 minor 55 references

RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read RATQ is a fixed-length quantizer that compresses gradients to about $d$ bits per update while keeping the optimal $1/\sqrt{T}$ stochastic-optimization error rate, matching the paper's precision lower bound up to an iterated-log factor.

desk verdict The almost-surely-bounded part of this paper is solid and worth reading; the mean-square-bounded part has a false key corollary (4.7) that undercuts the abstract's adaptive-gain claims. read the letter →

arxiv 1908.08200 v3 pith:NW5NYWAV submitted 2019-08-22 cs.LG cs.ITmath.ITmath.OCstat.ML

Prathamesh Mayekar , Himanshu Tyagi This is my paper · ORCID
classification cs.LGcs.ITmath.ITmath.OCstat.ML MSC 90C2594A34
keywords gradientquantizationstochasticconvexoptimizationfixed-lengthcodesHadamardtransformadaptiveuniformdistributedmeanestimationrate-distortioncommunication-efficientSGD
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

RATQ is a fixed-length quantizer that compresses noisy gradient estimates before they are used by projected subgradient descent. The paper's central claim is that with roughly $d$ bits per gradient, plus a negligible $O(\log\log\log\log^* d)$ overhead, RATQ attains the optimal $1/\sqrt{T}$ convergence rate for almost-surely bounded, convex stochastic optimization problems. An information-theoretic lower bound proved in the paper shows that any $r$-bit quantizer must suffer error at least $cDB\sqrt{d/\min\{d,r\}}/\sqrt{T}$, so RATQ's precision is optimal up to a tiny iterated-log factor. For oracles with only mean-square-bounded gradients, the paper adds an adaptive gain quantizer that needs $\log\log T$ bits for the gain, beating the $\log T$-bit requirement it proves for uniform gain quantizers. A sympathetic reader would take away that fixed-length, memoryless gradient compression can be almost as powerful as the best variable-length schemes.

What carries the argument

The load-bearing object is the Adaptive Tetra-iterated Uniform Quantizer (ATUQ) used inside RATQ on $s$-dimensional subvectors. ATUQ picks the smallest dynamic range $[-M_j,M_j]$ from a ladder with $M_j^2 = (3B^2/d)e^{*j} + (2B^2/d)\ln s$ (a tetration ladder), and then applies unbiased $k$-level coordinate-wise uniform quantization. The tetration spacing is not a technicality: it is what lets the encoder cover coordinates whose values can span an enormous range while using only $h \approx \log(1+\ln^*(d/3))$ possible ranges, so the precision overhead for communicating the chosen range stays tiny. Before this step, the randomized Hadamard rotation spreads the $\ell_2$ mass so that each rotated coordinate is subgaussian—its tails decay no slower than a Gaussian—with variance factor $B^2/d$; the subgaussian tails then make the per-coordinate mean-square error essentially constant. The second machinery is the Adaptive Geometric Uniform Quantizer (AGUQ) for the gain (the norm) in the mean-square-bounded case, whose dynamic ranges grow geometrically because gains need only satisfy a second-moment bound; this is what replaces the $\log T$-bit uniform gain with a $\log\log T$-bit adaptive gain. The paper also uses a random coordinate sampler (RCS) to reduce precision in the fixed-$r$ regime.

What would settle it

Run projected SGD on a smooth convex problem in dimension $d$ with almost surely bounded gradients for $T$ iterations and $r=d$ bits per gradient using RATQ; if the averaged gap does not stay at or below $C DB/\sqrt{T}$ for a constant $C$, Corollary 3.4 fails. To test the mean-square lower bound, use the one-dimensional heavy-tailed oracle constructed in the proof of Theorem 5.10 with a uniform gain quantizer of $r_g$ bits and check whether any protocol beats the $DB/T^{1/3}$ barrier; if a memoryless protocol with a fixed uniform gain quantizer achieves $1/\sqrt{T}$, Theorem 4.4 is false.

Watch

Extended reading notes

Core claim

The central discovery is that a simple two-step recipe—randomly rotate the gradient by a Walsh–Hadamard matrix with random signs, then apply coordinate-wise uniform quantization with adaptively chosen dynamic ranges whose squares grow like a tetration $e, e^e, e^{e^e}, \dots$—makes every coordinate of the rotated vector subgaussian with variance factor $O(B^2/d)$, so a few dynamic ranges suffice to cover the whole $\ell_2$ ball with negligible distortion. With parameters set as in (7) and (9), the resulting quantizer RATQ is unbiased, has worst-case output norm $B\sqrt{(9+3\ln s)/(k-1)^2+1}$, and yields $\sup_{(f,O)\in\mathcal{O}_0} E(f,\pi QO) \le \sqrt{2}DB/\sqrt{T}$ using $r \le d(1+\Delta_1)+\Delta_2$ bits per gradient, where $\Delta_1 = \lceil\log(2+\sqrt{9+3\ln\Delta_2})\rceil$ and $\Delta_2=\lceil\log(1+\ln^*(d/3))\rceil$. Theorem 3.1 lower bounds any protocol by $cDB\sqrt{d/\min\{d,r\}}/\sqrt{T}$, so RATQ's rate is near-optimal; in the low-precision regime a random coordinate sampler reduces the bit count further at the same optimal rate up to an $O(\log\ln^* d)$ factor. In the mean-square-bounded case, the paper proves that any gain-shape quantizer with a uniform gain quantizer needs $\Omega(d+\log T)$ bits, while A-RATQ's adaptive geometric gain quantizer attains $3DB/\sqrt{T}$ with only $\log\log T$ bits for the gain. The same machinery also yields a fixed-length distributed mean-estimation code within $O(\log\log\log\log^* d)$ of the variable-length optimum, and a universal subgaussian quantizer within $O(\log\log\log\log^*\log(v/D))$ of the Gaussian rate-distortion function.

Load-bearing premise

The near-optimality claims are proved only for memoryless quantizers: the same quantizer is applied to each gradient, with no use of information from previous updates; if the quantizer is allowed memory, such as error feedback, the lower bounds no longer apply and fewer bits may suffice.

Editorial extensions

If this is right

  • For almost-surely bounded convex problems, distributed SGD can run at the optimal $1/\sqrt{T}$ rate with a fixed-length code of about $d$ bits per gradient, so the worst-case message length no longer grows with dimension the way it does for variable-length schemes.
  • The lower bound $E_0^*(T,r)\ge cDB\sqrt{d/\min\{d,r\}}/\sqrt{T}$ means any attempt to use fewer than $\Omega(d)$ bits per gradient while keeping the $1/\sqrt{T}$ rate is doomed; RATQ is within iterated-log factors of that floor.
  • For mean-square-bounded oracles, uniform gain quantization provably requires $\log T$ bits for $T$ iterations, whereas A-RATQ's adaptive gain needs only $\log\log T$ bits; with 32 bits the adaptive scheme supports astronomically many iterations.
  • RATQ gives a fixed-length protocol for distributed mean estimation whose total communication is within $O(\log\log\log\log^* d)$ of the optimal variable-length protocol.
  • The same ATUQ construction, without rotation, quantizes Gaussian and subgaussian vectors at a rate within $O(\log\log\log\log^*\log(v/D))$ of the Gaussian rate-distortion function, with constant per-dimension complexity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper leaves open whether stateful or error-feedback quantizers can beat the $d$-bit budget: because the lower bounds are proved only for memoryless quantizers, a stateful scheme that achieves $1/\sqrt{T}$ with fewer bits would not contradict this paper but would narrow the scope of its near-optimality claim.
  • The recipe 'rotate, then adapt the uniform grid to the tail of the transformed coordinates' is portable: for other constraint sets, such as $\ell_p$ balls or low-rank matrices, the same argument should construct a fixed-length quantizer once the tail behavior of the rotated coordinates is known.
  • The fixed-length property could make RATQ attractive in federated-learning settings where variable-length codes complicate batching and hardware protocols; testing this in an empirical benchmark is an extension beyond the paper.
  • The Gaussian rate-distortion corollary suggests that ATUQ-type dynamic-range ladders could be applied directly to neural-network weight or activation compression, where approximate subgaussianity often holds; this is an extrapolation, not a claim of the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. This paper studies distributed stochastic convex optimization in which each noisy gradient must be encoded with r bits. For oracles with almost surely bounded Euclidean norm, the authors prove a lower bound E*_0(T,r) ≥ cDB/√T · sqrt(d/min{d,r}) and propose RATQ, a fixed-length quantizer combining randomized Hadamard rotation and adaptive uniform quantization with tetration-spaced dynamic ranges; with parameters (7),(9) it gives sup E ≤ √2 DB/√T using r ≈ d(1+Δ1)+Δ2 bits. For mean-square-bounded oracles the authors propose a gain-shape variant A-RATQ, prove lower bounds for uniform gain quantizers, and claim A-RATQ achieves O(DB/√T) with an adaptive geometric gain quantizer. The paper also applies RATQ to distributed mean estimation and ATUQ to subgaussian/Gaussian rate distortion.

Significance. If valid, the RATQ construction is a significant algorithmic contribution: it is a simple fixed-length scheme whose worst-case bit rate matches the d-bit lower bound up to iterated-logarithm factors, and the proof of Theorem 3.3 is detailed and self-contained. The mean-estimation and Gaussian rate-distortion applications are useful by-products, and the lower-bound framework using strong data processing and heavy-tailed constructions is of independent interest. The near-optimality claim is, however, restricted to memoryless quantizers (Remark 1), and the high-precision A-RATQ result is currently not correct as stated; with the parameter fix described below the core approach remains credible.

major comments (2)
  1. [§4.2, Eq. (17), Corollary 4.7] The claimed O(DB/√T) guarantee for A-RATQ does not follow from Theorem 4.6 and is in fact false with the stated parameters. With a_g=2 and log h_g = ceil(log(1 + (1/2) log T)), we have h_g - 1 ≈ (1/2) log_2 T, so the largest AGUQ dynamic range is M_{g,h_g-1} = B · 2^{(h_g-1)/2} ≈ B T^{1/4}. Lemma 4.5 and Theorem 4.6 then give β(Q) ≤ B^2/M_{g,h_g-1} = O(B/T^{1/4}), not O(B/√T). This is not merely a loose bound: taking a mean-square-bounded oracle whose gradient is 0 with probability 1-p and 2M_{g,h_g-1} e_1 with probability p = B^2/(4M_{g,h_g-1}^2) makes AGUQ overflow to 0 on the large-gradient sample, so the optimization error is Ω(DB/T^{1/4}). Thus the high-precision A-RATQ claim in Corollary 4.7 is unsupported as written. The theorem can be repaired by setting h_g ≈ log_2 T (or a_g ≈ 4) so that M_{g,h_g-1} ≈ B√T, at an additional gain-index cost of O(log log T), but the parameter choice (17) must be changed.
  2. [§3.1, Theorem 3.1] The proof of the precision-dependent lower bound is only a sketch. The key step I(V ∧ Q(Y)) ≤ 360δ^2 min{r,d} is quoted from [18, Proposition 2] without stating the exact hypotheses or verifying that the constructed coordinate distributions satisfy them, and the final maximization over δ is omitted. Since this lower bound is load-bearing for the paper's near-optimality claim, the authors should either supply a complete proof or give a precise statement of the strong data processing inequality being invoked and show how it applies to the oracle construction.
minor comments (4)
  1. [Abstract and Remark 1] The abstract and introduction should state prominently that the optimality claims are for memoryless quantizers; Remark 1 restricts the setting in this way, and without this qualification the phrase 'close to optimal' can be misread as applying to error-feedback or other memory-based schemes.
  2. [§3.1, proof of Theorem 3.1] There are apparent typos in the displayed equations: the factor Bδ√d should presumably be Bδ/√d, and the argument of the probability in the Hamming-distance step appears to be missing a factor of √d.
  3. [§5.1, proof of Lemma 5.7] The text says 'Setting m = 3v and m0 = 2v' but the statement of Lemma 5.7 and the preceding definitions use m0 = 2v ln s; the subsequent calculation uses ln s, so the displayed sentence is a typo.
  4. [§1 and Corollary 3.4] The notation for iterated logarithms is dense: log log log log* d appears in Remark 3 and log log ln* d in Corollary 3.8. A short table or explicit definitions of Δ1, Δ2, ln*, and log* would improve readability.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity: RATQ's guarantees follow from its stated assumptions; self-citations are contextual, and the Corollary 4.7 parameter-scaling issue is a non-circular arithmetic flaw.

full rationale

The paper is largely self-contained and benchmarked against independent external results. The main upper bounds are proved directly: Theorem 3.3 computes alpha_0 and beta_0 for RATQ from Lemmas 5.1-5.9 (CUQ mean-square error, subgaussian tail bounds, and the Hadamard rotation lemma), and Theorem 4.6 combines those with Lemma 4.5 for the AGUQ gain quantizer. The parameters in (7), (9), (13), (16), and (18) are chosen from the problem data (B, d, s, T) and then substituted into derived bounds; no parameter is fitted to a target and renamed a prediction. The optimization-to-testing reductions in Theorems 3.1, 4.3, and 4.4 use Fano's inequality and the strong data processing inequality from [18], an external result, and are not derived from the paper's own quantizer bounds. Self-citations [1, 2, 43] appear only as contextual pointers to related information-constrained inference work and are not load-bearing in any proof. Remark 1 explicitly restricts the claim to memoryless quantizers; this is a scope limitation, not a circularity. The one substantive weakness I find is non-circular: with the parameters in (17), h_g is about 1 + (1/2) log_2 T, so M_{g,h_g-1} ~ B T^{1/4}, and Lemma 4.5 gives beta <= B^2/M_{g,h_g-1} ~ B/T^{1/4}; consequently the claimed 3DB/sqrt(T) bound in Corollary 4.7 does not follow from the stated substitution. This is a parameter-scaling/arithmetic error (a correct choice would be h_g ~ log_2 T, giving O(log log T) index bits), but it does not make any derivation equivalent to its inputs, so it does not raise the circularity score.

Assumptions & free parameters 9 free parameters · 6 assumptions · 0 invented entities

Everything needed for the central claims is either standard mathematics or explicitly stated domain assumptions. The algorithm's parameters (m, m0, h, s, k, ag, hg, kg, mu) are chosen analytically to optimize the derived bounds; none are fitted to data. The paper introduces no new physical or mathematical entities.

free parameters (9)
  • m (RATQ per-coordinate base range) = 3B^2/d
    Set in (7) so that each rotated coordinate has variance factor v = B^2/d, giving per-coordinate MSE O(v/(k-1)^2).
  • m0 (RATQ subvector tail offset) = 2B^2/d * ln s
    Set in (7) to control the union-bound tail term 2s e^{-M^2/(2v)} in Lemma 5.7.
  • h (number of dynamic ranges) = ceil(log(1+ln*(d/3)))
    Set in (7) so that M_{h-1} >= B, which makes RATQ unbiased on the a.s. bounded input.
  • s (subvector size, high precision) = log h
    Set in (9) to balance the d/s * log h overhead against the ln s term in the MSE.
  • k (CUQ levels) = ceil(2+sqrt(9+3 ln s))
    Set in (9) to make alpha0(Q) <= sqrt(2)B for the chosen s.
  • ag (AGUQ geometric growth rate) = 2
    Set in (17) and (18) so that the sum over geometric levels converges and the bias term B^2/M_{g,hg-1} is controlled.
  • hg (AGUQ number of ranges) = ceil(log(1 + 0.5 log T)) in the high-precision regime
    Set in (17) so that M_{g,hg-1} ~ B sqrt(T), making the bias O(B/sqrt(T)).
  • kg (AGUQ levels) = ceil(2 + 0.5 sqrt(log T + 1)) in the high-precision regime
    Set in (17) to balance gain MSE against the log T bit budget.
  • mu (RCS sampling fraction) = min{d, r/(3+ceil(log h))}/d
    Set in (12) and (18) so that the total number of bits used by the subsampled shape quantizer fits in r bits.
assumptions (6)
  • standard math Strong data processing inequality: I(V;Q(Y)) <= 360 delta^2 min{r,d} for an r-bit quantizer Q
    Used in the proof of Theorem 3.1 (Section 3.1) to upper-bound the mutual information between the hypothesis and the quantized oracle output; if this bound were false, the lower bound could be much weaker.
  • standard math Oracle complexity lower bound from [4] that E*_0(T,infinity) >= c0 DB/sqrt(T)
    Used as the base of Theorem 3.1 and as the benchmark for optimal convergence rate.
  • standard math Subgaussian tail and moment bounds (Lemma 5.6): P(|X|>x) <= 2 e^{-x^2/(2v)}, E[X^2] <= 4v, E[X^4] <= 32v^2
    Used repeatedly in Lemma 5.7, Lemma 5.8, and Appendix D for the rotated coordinates and Gaussian source.
  • domain assumption Convexity and bounded domain assumptions: f convex, domain diameter D, oracle unbiased with second moment bound (1)-(3)
    This is the stochastic optimization model of Section 2.1; all results are stated within this model.
  • domain assumption Shared public randomness for the randomized Hadamard matrix and RCS subsets
    The encoder and decoder use the same random rotation and subset; this is standard in the distributed mean estimation literature ([47]) and is required for the decoder to invert the rotation.
  • domain assumption Memoryless quantization at each step (Remark 1)
    The lower bound and the near-optimality claims apply only when the quantizer does not use information from previous updates; error feedback can circumvent this.

how reviews work

0 comments
Cite this review

Pith. "Pith review of RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization." pith.science (2026). https://pith.science/paper/NW5NYWAV

@misc{pith2026190808200,
  author       = {Pith},
  title        = {Pith review of: RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NW5NYWAV}},
  note         = {Machine review of arXiv:1908.08200}
}
read the original abstract

We present Rotated Adaptive Tetra-iterated Quantizer (RATQ), a fixed-length quantizer for gradients in first order stochastic optimization. RATQ is easy to implement and involves only a Hadamard transform computation and adaptive uniform quantization with appropriately chosen dynamic ranges. For noisy gradients with almost surely bounded Euclidean norms, we establish an information theoretic lower bound for optimization accuracy using finite precision gradients and show that RATQ almost attains this lower bound. For mean square bounded noisy gradients, we use a gain-shape quantizer which separately quantizes the Euclidean norm and uses RATQ to quantize the normalized unit norm vector. We establish lower bounds for performance of any optimization procedure and shape quantizer, when used with a uniform gain quantizer. Finally, we propose an adaptive quantizer for gain which when used with RATQ for shape quantizer outperforms uniform gain quantization and is, in fact, close to optimal. As a by-product, we show that our fixed-length quantizer RATQ has almost the same performance as the optimal variable-length quantizers for distributed mean estimation. Also, we obtain an efficient quantizer for Gaussian vectors which attains a rate very close to the Gaussian rate-distortion function and is, in fact, universal for subgaussian input vectors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 50 canonical work pages

  1. [1]

    Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction

    J. Acharya, C. L. Canonne, and H. Tyagi, “Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction,” arXiv:1812.11476, 2018

    work page Pith review arXiv 2018

  2. [2]

    Inference under Information Constraints II: Communic ation Constraints and Shared Randomness,

    ——, “Inference under Information Constraints II: Communic ation Constraints and Shared Randomness,” arXiv:1905.08302, 2019

    arXiv 1905

  3. [3]

    Distributed Learning with Sublinear Communication

    J. Acharya, C. De Sa, D. J. Foster, and K. Sridharan, “Dist ributed Learning with Sublinear Communication,” arXiv:1902.11259, 2019

    work page Pith review arXiv 1902

  4. [4]

    Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimi zation,

    A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwr ight, “Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimi zation,” IEEE Transactions on Information Theory, vol. 5, no. 58, pp. 3235–3249, 2012

    work page 2012

  5. [5]

    Information-theoretic lower bounds on the oracle complexity of convex optimizatio n,

    A. Agarwal, M. J. Wainwright, P. L. Bartlett, and P. K. Rav ikumar, “Information-theoretic lower bounds on the oracle complexity of convex optimizatio n,” Advances in Neural Informa- tion Processing Systems , pp. 1–9, 2009

    work page 2009

  6. [6]

    cpSGD: Communication- efficient and differentially-private distributed SGD,

    N. Agarwal, A. T. Suresh, F. X. X. Yu, S. Kumar, and B. McMah an, “cpSGD: Communication- efficient and differentially-private distributed SGD,” Advances in Neural Information Process- ing Systems , pp. 7564–7575, 2018

    work page 2018

  7. [7]

    Approximate nearest neighbor s and the fast johnson-lindenstrauss transform,

    N. Ailon and B. Chazelle, “Approximate nearest neighbor s and the fast johnson-lindenstrauss transform,” Proceedings of the ACM symposium on Theory of computing (STO C’06), pp. 557– 563, 2006

    work page 2006

  8. [8]

    On constrained randomized quantiz ation,

    E. Akyol and K. Rose, “On constrained randomized quantiz ation,” IEEE Transactions on Signal Processing, vol. 61, no. 13, pp. 3291–3302, July 2013

    work page 2013

Show all 55 references
  1. [9]

    QSGD: Communication-efficient SGD via gradient quantization and encoding,

    D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic , “QSGD: Communication-efficient SGD via gradient quantization and encoding,” Advances in Neural Information Processing Systems, pp. 1709–1720, 2017

    2017

  2. [10]

    Qsparse-l ocal-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations,

    D. Basu, D. Data, C. Karakus, and S. Diggavi, “Qsparse-l ocal-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations,” arXiv:1906.02367, 2019

    1906 arXiv

  3. [11]

    Boucheron, G

    S. Boucheron, G. Lugosi, and P. Massart, Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013

    2013

  4. [12]

    Communication lower bounds for statistical estimation problems via a distribut ed data processing inequality,

    M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. P. Woodr uff, “Communication lower bounds for statistical estimation problems via a distribut ed data processing inequality,” Pro- ceedings of ACM Symposium on the Theory of Computing (STOC’ 1 6), pp. 1011–1020, 2016

    2016

  5. [13]

    Convex optimization: Algorithms and compl exity,

    S. Bubeck, “Convex optimization: Algorithms and compl exity,” Foundations and Trends R© in Machine Learning, vol. 8, no. 3-4, pp. 231–357, 2015

    2015

  6. [14]

    T. M. Cover and J. A. Thomas, Elements of Information Theory. 2nd edition . John Wiley & Sons Inc., 2006

    2006

  7. [15]

    Capacity of the gaussian arb itrarily varying channel,

    I. Csiszár and P. Narayan, “Capacity of the gaussian arb itrarily varying channel,” IEEE Trans- actions on Information Theory , vol. 37, no. 1, pp. 18–26, 1991. 45

    1991

  8. [16]

    Taming the w ild: A unified analysis of Hogwild-style algorithms,

    C. M. De Sa, C. Zhang, K. Olukotun, and C. Ré, “Taming the w ild: A unified analysis of Hogwild-style algorithms,” Advances in Neural Information Processing Systems, pp. 2674–2682, 2015

    2015

  9. [17]

    Introductory lectures on stochastic opti mization,

    J. C. Duchi, “Introductory lectures on stochastic opti mization,” 2017, A vailable Online http://stanford.edu/~jduchi/PCMIConvex/Duchi16.pdf

    2017

  10. [18]

    Optimality guarantees for distributed statistical estimation,

    J. C. Duchi, M. I. Jordan, M. J. Wainwright, and Y. Zhang, “Optimality guarantees for distributed statistical estimation,” arXiv:1405.0782, 2014

    2014 arXiv

  11. [19]

    Covering spheres with spheres,

    I. Dumer, “Covering spheres with spheres,” Discrete & Computational Geometry , vol. 38, no. 4, pp. 665–679, Dec 2007

    2007

  12. [20]

    R. G. Gallager, Information theory and reliable communication . Springer, 1968, vol. 2

    1968

  13. [21]

    vqsgd: Vect or quantized stochastic gradient descent,

    V. Gandikota, R. K. Maity, and A. Mazumdar, “vqsgd: Vect or quantized stochastic gradient descent,” arXiv preprint arXiv:1911.07971 , 2019

    1911 arXiv

  14. [22]

    On Communication Cost o f Distributed Statistical Estima- tion and Dimensionality,

    A. Garg, T. Ma, and H. L. Nguyen, “On Communication Cost o f Distributed Statistical Estima- tion and Dimensionality,” Advances in Neural Information Processing Systems , pp. 2726–2734, 2014

    2014

  15. [23]

    Gersho and R

    A. Gersho and R. M. Gray, Vector quantization and signal compression . Springer Science & Business Media, 2012, vol. 159

    2012

  16. [24]

    Deep learning with limited numerical precision,

    S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayan an, “Deep learning with limited numerical precision,” Proceedings of the International Conference on Machine Learning (ICML’ 15), pp. 1737–1746, 2015

    2015

  17. [25]

    Dithered quantization via orthog onal transformations,

    R. Hadad and U. Erez, “Dithered quantization via orthog onal transformations,” IEEE Trans- actions on Signal Processing , vol. 64, pp. 5887–5900, 11 2016

    2016

  18. [26]

    Asymptotically dense spheric al codes. I. Wrapped spherical codes,

    J. Hamkins and K. Zeger, “Asymptotically dense spheric al codes. I. Wrapped spherical codes,” IEEE Transactions on Information Theory , vol. 43, no. 6, pp. 1774–1785, Nov 1997

    1997

  19. [27]

    Asymptotically dense spherical codes. II. Lamina ted spherical codes,

    ——, “Asymptotically dense spherical codes. II. Lamina ted spherical codes,” IEEE Transac- tions on Information Theory , vol. 43, no. 6, pp. 1786–1798, Nov 1997

    1997

  20. [28]

    Design and analysis of spherical codes,

    J. Hamkins, “Design and analysis of spherical codes,” Ph. D. Dissertation, UCSD , 1996

    1996

  21. [29]

    Gaussian source coding with sp herical codes,

    J. Hamkins and K. Zeger, “Gaussian source coding with sp herical codes,” IEEE Transactions on Information Theory , vol. 48, no. 11, pp. 2980–2989, 2002

    2002

  22. [30]

    Geometric Lower Boun ds for Distributed Parameter Estimation under Communication Constraints,

    Y. Han, A. Özgür, and T. Weissman, “Geometric Lower Boun ds for Distributed Parameter Estimation under Communication Constraints,” Proceedings of the International Conference on Computational Learning Theory (COLT’ 18) , vol. 75, pp. 3163–3188, 2018

    2018

  23. [31]

    K. J. Horadam, Hadamard matrices and their applications . Princeton university press, 2012

    2012

  24. [32]

    (Ban dit) Convex Optimization with Biased Noisy Gradient Oracles,

    X. Hu, L. Prashanth, A. György, and C. Szepesvári, “(Ban dit) Convex Optimization with Biased Noisy Gradient Oracles,” Proceedings of the International Conference on Artificial I n- telligence and Statistics (AISTATS’ 16) , pp. 819–828, 2016. 46

    2016

  25. [33]

    Gaussian arbitrarily varyin g channels,

    B. Hughes and P. Narayan, “Gaussian arbitrarily varyin g channels,” IEEE Transactions on Information Theory, vol. 33, no. 2, pp. 267–284, 1987

    1987

  26. [34]

    Error feedback fixes signsgd and other gradient compression schemes,

    S. P. Karimireddy, Q. Rebjock, S. U. Stich, and M. Jaggi, “Error feedback fixes signsgd and other gradient compression schemes,” arXiv:1901.09847, 2019

    1901 arXiv

  27. [35]

    On the role of mismatch in rate distortion theory,

    A. Lapidoth, “On the role of mismatch in rate distortion theory,” IEEE Transactions on Information Theory, vol. 43, no. 1, pp. 38–47, 1997

    1997

  28. [36]

    Low density codes achi eve the rate-distortion bound,

    E. Martinian and M. Wainwright, “Low density codes achi eve the rate-distortion bound,” Proc. IEEE Data Compression Conference , pp. 153–162, 2006

    2006

  29. [37]

    Information-based complexity of conv ex programming,

    A. Nemirovski, “Information-based complexity of conv ex programming,” 1995, A vailable Online http://www2.isye.gatech.edu/ne-mirovs/Lec_EMCO.pdf

    1995

  30. [38]

    Problem complexity an d method efficiency in optimiza- tion

    A. S. Nemirovsky and D. B. Yudin, “Problem complexity an d method efficiency in optimiza- tion.” Wiley series in Discrete Mathematics and Optimization , 1983

    1983

  31. [39]

    Introductory lectures on convex optimiz ation: A basic course,

    Y. Nesterov, “Introductory lectures on convex optimiz ation: A basic course,” Springer Science and Business Media , vol. 87, 2013

    2013

  32. [40]

    Rotated dispersed dither: A new technique for digital halftoning,

    V. Ostromoukhov, R. D. Hersch, and I. Amidror, “Rotated dispersed dither: A new technique for digital halftoning,” in Proceedings of the 21st Annual Conference on Computer Graph ics and Interactive Techniques , ser. SIGGRAPH ’94. New York, NY, USA: ACM, 1994, pp. 123–130

    1994

  33. [41]

    Nuqsgd: I mproved communication efficiency for data-parallel sgd via nonuniform quantization,

    A. Ramezani-Kebrya, F. Faghri, and D. M. Roy, “Nuqsgd: I mproved communication efficiency for data-parallel sgd via nonuniform quantization,” arXiv preprint arXiv:1908.06077 , 2019

    1908 arXiv

  34. [42]

    A stochastic approximation me thod,

    H. Robbins and S. Monro, “A stochastic approximation me thod,” The Annals of Mathematical Statistics, vol. 22, pp. 400–407, 1951

    1951

  35. [43]

    Extra samples can reduce t he communication for independence testing,

    K. Sahasranand and H. Tyagi, “Extra samples can reduce t he communication for independence testing,” Proc. International Symposium of Information Theory , pp. 2316–2320, 2018

    2018

  36. [44]

    Fundamental limits of online and distribut ed algorithms for statistical learning and estimation,

    O. Shamir, “Fundamental limits of online and distribut ed algorithms for statistical learning and estimation,” Advances in Neural Information Processing Systems , pp. 163–171, 2014

    2014

  37. [45]

    Low-density lattic e codes,

    N. Sommer, M. Feder, and O. Shalvi, “Low-density lattic e codes,” IEEE Transactions on Information Theory, vol. 54, no. 4, pp. 1561–1585, April 2008

    2008

  38. [46]

    Sparsified SGD with memory,

    S. U. Stich, J.-B. Cordonnier, and M. Jaggi, “Sparsified SGD with memory,” Advances in Neural Information Processing Systems , pp. 4447–4458, 2018

    2018

  39. [47]

    Distr ibuted mean estimation with limited communication,

    A. T. Suresh, F. X. Yu, S. Kumar, and H. B. McMahan, “Distr ibuted mean estimation with limited communication,” Proceedings of the International Conference on Machine Lea rning (ICML’ 17) , vol. 70, pp. 3329–3337, 2017

    2017

  40. [48]

    Atomo: Communication-efficient learning via atomic sparsification ,

    H. Wang, S. Sievert, S. Liu, Z. Charles, D. Papailiopoul os, and S. Wright, “Atomo: Communication-efficient learning via atomic sparsification ,” Advances in Neural Information Processing Systems, pp. 9850–9861, 2018. 47

    2018

  41. [49]

    Te rnGrad: Ternary gradi- ents to reduce communication in distributed deep learning,

    W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li, “Te rnGrad: Ternary gradi- ents to reduce communication in distributed deep learning, ” Advances in Neural Information Processing Systems, pp. 1509–1519, 2017

    2017

  42. [50]

    Open Problem: The Oracle Co mplexity of Convex Optimization with Limited Memory,

    B. Woodworth and N. Srebro, “Open Problem: The Oracle Co mplexity of Convex Optimization with Limited Memory,” arXiv:1907.00762, 2019

    1907 arXiv

  43. [51]

    Random packings and coverings of the unit n -sphere,

    A. D. Wyner, “Random packings and coverings of the unit n -sphere,” The Bell System Technical Journal, vol. 46, no. 9, pp. 2111–2118, 1967

    1967

  44. [52]

    Information-theoretic lower bo unds on Bayes risk in decentralized estimation,

    A. Xu and M. Raginsky, “Information-theoretic lower bo unds on Bayes risk in decentralized estimation,” IEEE Transactions on Information Theory , vol. 63, no. 3, pp. 1580–1600, 2017

    2017

  45. [53]

    Polar lattices: where arıkan meets forney,

    Y. Yan, C. Ling, and X. Wu, “Polar lattices: where arıkan meets forney,” Proc. IEEE Inter- national Symposium of Information Theory , pp. 1292–1296, 2013

    2013

  46. [54]

    I nformation-theoretic lower bounds for distributed statistical estimation with communicatio n constraints,

    Y. Zhang, J. Duchi, M. I. Jordan, and M. J. Wainwright, “I nformation-theoretic lower bounds for distributed statistical estimation with communicatio n constraints,” Advances in Neural Information Processing Systems , pp. 2328–2336, 2013

    2013

  47. [55]

    On universal quantization,

    J. Ziv, “On universal quantization,” IEEE Transactions on Information Theory , vol. 31, no. 3, pp. 344–347, 1985. 48

    1985

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.