Pith. sign in

REVIEW 3 major objections 4 minor 48 references

Decentralised convex optimisation with probability-proportional-to-size quantization

T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read This paper proposes a probability-proportional-to-size (PPS) quantized gradient oracle and accelerated primal-dual methods, deriving large-deviation convergence guarantees for affine-constrained and decentralized stochastic convex…

desk verdict The PPS quantization idea is genuinely interesting, but Lemma 1's sub-Gaussian bound is wrong by a factor of e, and every subsequent theorem rides on it. read the letter →

arxiv 2501.18312 v1 pith:LZ4HVJZT submitted 2025-01-30 math.OC

Dmitrii Pasechniuk , Pavel Dvurechensky , César A. Uribe , Alexander Gasnikov This is my paper · ORCID
classification math.OC MSC 90C2590C1590C35
keywords probability-proportional-to-sizequantizationdistributedconvexoptimizationacceleratedgradientmethodquantizedoraclelargedeviationsprimal-dualalgorithmWassersteinbarycenter
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

The paper attacks the communication bottleneck of distributed optimization with a new way to quantize a vector before it is sent: split a mini-batched stochastic gradient into positive and negative parts, turn each part into a categorical distribution with probabilities proportional to component magnitudes, and sample a sparse zero-one vector from it. The resulting PPS oracle is unbiased, costs only 2 floats plus 2M log n bits per message, and has a second moment that shrinks as 1/M, making it competitive with near-optimal compressors and better than them when gradients live in a simplex. The paper's main claim is that this oracle is sub-Gaussian with a computable variance, and that this concentration property feeds accelerated primal and primal-dual algorithms for affine-constrained problems, giving epsilon,delta guarantees on both objective accuracy and constraint satisfaction. It then converts those results into a decentralized method and reports that the method matches optimal rates up to eO(1) factors while transmitting far fewer bits, with experiments on semi-discrete entropy-regularized Wasserstein barycenters.

What carries the argument

The PPS quantized gradient oracle: for a mini-batched stochastic gradient $G$, split it as $G=[G]_+ - [-G]_+$, draw $M$ indices from the categorical distribution with probabilities $P_G(k)=[G_k]_+/\|[G]_+\|_1$ and $M$ more from $P_{-G}$, and return $\frac{\|[G]_+\|_1}{M}\sum_i e_{k_i} - \frac{\|[-G]_+\|_1}{M}\sum_i e_{l_i}$. This object carries the whole argument because its unbiasedness gives correctness, its message format $2|\mathrm{float}|+2M\log_2 n$ gives the communication cost, and Lemma 1's sub-Gaussian bound gives the large-deviation estimates that Theorem 2 and Corollary 1 convert into $\epsilon,\delta$ rates. The algorithms additionally couple $r_t$ and $M_t$ iteration by iteration so quantization noise and stochastic noise enter the bounds on equal footing.

What would settle it

Set $v=(1/n,\dots,1/n)$, draw $k$ from the categorical distribution with probabilities $v_k$, and evaluate $E_k[\exp(\|e_k-v\|^2/\alpha)]$ with $\alpha=(1-1/n)/e$. For every $k$, $\|e_k-v\|^2=1-1/n$, so the expectation equals $\exp(e)>e$, contradicting the inequality the proof of Lemma 1 relies on. The same calculation with $k$ drawn uniformly, the sampling used in the proof, returns exactly $e$.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is that sampling gradient components with probability proportional to their magnitude yields a quantized estimate that is simultaneously unbiased, cheap to encode, and concentrated enough to drive accelerated primal-dual methods. The formal core is Lemma 1: for the PPS oracle, $E_{\xi,k,l}[\exp(\|\mathrm{PPS}(x,\xi,k,l)-\nabla f(x)\|^2/\sigma_{r,M}^2)] \le e$ with $\sigma_{r,M}^2=50(2(1-1/n)B^2/(eM)+\sigma_r^2)$, where $B$ bounds the $\ell^1$ norm of the oracle. From this sub-Gaussian inequality, Theorem 2 gives high-probability accuracy and constraint-violation bounds for affine-constrained problems; Theorems 3 and 4 show how to set the batch size $r_t$ and the sample count $M_t$ to minimize oracle calls and transmitted bits; and Corollary 1 turns the result into a decentralized algorithm whose communication complexity depends on graph parameters such as diameter and maximum degree. The paper claims these rates are optimal up to $\tilde O(1)$ factors and are the first to combine stochasticity, quantization, and primal-dual large-deviation guarantees.

Load-bearing premise

The load-bearing premise is Lemma 1's claim that the PPS estimator's error has exponentially decaying tails with the stated variance; the proof derives that constant by averaging over indices uniformly even though the method samples them with probability proportional to component size, and for the vector whose components are all equal, the claimed exponential-moment inequality fails.

Editorial extensions

If this is right

  • One communicated message under PPS costs $2$ floats plus $2M\log_2 n$ index bits, so with small $M$ the per-round communication is logarithmic in the dimension rather than linear.
  • If Lemma 1 stands, the accelerated primal-dual method returns an $\epsilon$-accurate and $\epsilon/R$-feasible point with probability at least $1-\delta$, with an $\tilde O(\max\{\sqrt{LR^2/\epsilon},\sigma^2R^2/\epsilon^2,\sigma^2L^2/(\epsilon^2\|A\|_2^2)\})$ oracle-call count.
  • The variable-batch schemes of Theorems 3 and 4 let the user balance stochastic noise and quantization noise: more samples per iteration $r_t$ or more component samples $M_t$ reduce the variance terms in the rates, at known bit and arithmetic costs.
  • In the decentralized setting of Algorithm 3, each node transmits $\tilde O(B^2 d\log n\max\{...\})$ bits with dependence on the graph's diameter, maximum degree, and mixing constant, so denser networks and noisier oracles reduce communication.
  • For the Wasserstein barycenter application, the gradient of the entropy-regularized dual lies in the simplex, so PPS's second moment does not blow up with dimension; the experiments confirm that $M=1$ with modest batch sizes already tracks the unquantized baseline.

Reading between the lines

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

  • A corrected sub-Gaussian constant in Lemma 1 would alter only constants inside the $\tilde O(\cdot)$ rates, not the qualitative structure of Theorems 1-4, because every later bound depends on $\sigma_{r,M}$ polynomially.
  • The same large-deviation technology could be reused for non-Euclidean prox setups if the sub-Gaussian lemma is re-proved with a proper dimension-dependent constant; the paper notes its results are intended to generalize but works out the Euclidean case only.
  • For objectives whose gradients are simplex-valued, PPS should behave as a drop-in communication compressor for federated logistic regression and Sinkhorn-type optimal transport solvers, since its second moment is constant in dimension there; the paper tests only the Wasserstein barycenter case.
  • A natural stress test is to run the same primal-dual algorithm with uniform random sampling instead of size-proportional sampling; comparing the two under identical bit budgets would isolate what the PPS design itself contributes beyond cheap encoding.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The manuscript proposes a 'probability-proportional-to-size' (PPS) quantization scheme for distributed convex optimization: a vector is split into positive and negative parts, mapped to categorical distributions, and sampled M times to produce an unbiased sparse estimator. This estimator is inserted into accelerated primal and primal-dual methods. The central theoretical claim is Lemma 1, which asserts a sub-Gaussian bound for the PPS-estimated gradient with parameter sigma^2_{r,M} = 50(2(1-1/n)B^2/(eM) + sigma^2_r). From Lemma 1 the paper derives large-deviation convergence guarantees (Theorems 1-4, Corollary 1, Corollary 3), including communication-bit complexity bounds, and applies the method to decentralized Wasserstein-barycenter computation with numerical experiments.

Significance. If Lemma 1 were correct, the paper would be a valuable contribution: the PPS estimator would be communication-efficient, unbiased, and would have an attractive second-moment behavior on simplex-structured gradients, and the paper would provide the first accelerated distributed primal-dual method combining quantization, stochasticity, and large-deviation bounds. The manuscript also contains an application and reproducible-looking experiments. However, the proof of Lemma 1 contains a distribution mismatch and an invalid step from a mean bound to an exponential-moment bound, and the lemma is false as stated. Since all convergence and bit-complexity results depend on this lemma, the theoretical claims are not currently supported. The approach may be repairable by correcting the sub-Gaussian constant and supplying a genuine proof, but this is a substantial revision rather than a local fix.

major comments (3)
  1. [§2, Lemma 1] The proof reduces the problem to the condition E_k[exp(||v-e_k||^2/alpha)] <= e for k drawn from P_v(k)=v_k, but then computes E_k[||v-e_k||^2] as the uniform average (1/n) sum_k(...). These two distributions agree only when v is uniform. Under P_v one has E[||v-e_k||^2] = 1 - ||v||_2^2, not ||v||_2^2 - 2/n + 1. More importantly, a bound on the mean of ||v-e_k||^2/alpha does not imply the required bound on its exponential moment; the step 'we have (1-1/n)/alpha <= e, from where alpha=(1-1/n)/e' is a Jensen/quantifier error.
  2. [§2, Lemma 1, proof] Concrete counterexample: take v = (1/n,...,1/n). Then k is drawn uniformly and X = ||v-e_k||^2 = 1 - 1/n with probability one. Under the claimed alpha = (1-1/n)/e, E_k[exp(X/alpha)] = exp(e) = e^e > e, so the hypothesis used inside Lemma 1 fails. In fact alpha = 1 - 1/n would give the value e for this example, indicating the constant is off by a factor e. The tightness remark in the proof concerns only the mean, not the exponential moment, so it does not rescue the lemma.
  3. [§4–§5 and Appendix A] All downstream results inherit sigma^2_{r,M} from Lemma 1: Lemma 5 uses it in every large-deviation estimate, Theorems 1–4 use it in the epsilon(T,delta,...) formulas and in parameter choices such as M_t = 2(1-1/n)B^2/(e sigma^2 r_t), and Corollaries 1 and 3 use it in the communication-bit counts. Since Lemma 1 is not proven and is false with the stated constant, the convergence and complexity bounds as stated do not follow. This error is load-bearing, not a local typo.
minor comments (4)
  1. [§1, Notation] The definition 'Delta_n = {x >= 0 || sum_i x_i = 1}' should use ':' or '|' instead of the norm symbol '||' in the set-builder notation; as printed, the definition is unreadable.
  2. [§4.1] The sentence 'The following theorem is similar to Theorem 2' appears before Theorem 2 is stated; reorder or renumber the sections to avoid a forward reference.
  3. [§6.1] The symbol xi is used both for stochastic oracle noise and for the uniform reference distribution in Eq. (9) and the surrounding text; this collision makes the entropy-regularization term confusing and should be disambiguated.
  4. [§6.2, Figures 1–2] The axis labels and curve legends in the reproduced figures contain corrupted text (e.g., '1 o2', '10°'), which makes the experimental comparison difficult to read; the figures should be regenerated with clean labels.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the PPS estimator is analyzed in-paper, and prior-work citations are external tools; the Lemma 1 flaw is a soundness issue, not a circular reduction.

full rationale

The paper's central claim is that the PPS quantized gradient oracle (Eq. 1) is sub-Gaussian with parameter sigma^2_{r,M} (Lemma 1), and that plugging this oracle into accelerated primal/primal-dual templates yields large-deviation guarantees. Lemma 1 is not circular: it attempts a direct proof of the exponential-moment bound using a decomposition of the quantization error, Proposition 2.6.1 [43], and Lemma 3.1.3 [16]. The subsequent Theorems 1-4 and Corollary 1 invoke the concentration inequalities collected in Lemma 5, cited from [16] and [15]; these are external results whose assumptions do not include the PPS estimator, and the present paper's new contribution is showing PPS satisfies those assumptions. No parameter is fitted to a subset of data and then reported as a prediction; the choice Mt = 2(1-1/n)B^2/(e*sigma^2_rt) is a design rule, not a fitted claim. The self-citations to [16], [17], [23], and [27] are used as building blocks (dual-function lemmas, concentration inequalities, bound on R*) rather than as the source of the PPS sub-Gaussian property itself. The apparent flaw in Lemma 1 - deriving a bound on E_k[||v-e_k||^2] and using it as if it were an exponential-moment bound - is a mathematical soundness issue, not a circular reduction: the claimed inequality does not hold by construction, and it fails numerically for v=(1/n,...,1/n). Under the stated rules for circularity analysis, correctness and novelty concerns belong outside the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data. The assumptions are standard for accelerated stochastic convex optimization: smoothness, sub-Gaussian oracle noise, bounded L1 norm of gradient, Euclidean prox-function, and connected graph with positive algebraic connectivity. The proof of Lemma 1 (the sub-Gaussian bound for PPS) is the load-bearing step and contains an error.

assumptions (5)
  • domain assumption f is convex and grad f is L-Lipschitz continuous.
    Assumed in Sections 3 and 4 for the primal and dual problems.
  • domain assumption Stochastic gradient oracle g satisfies E[g]=grad f, E[exp(||g-grad f||^2/sigma^2)]<=e, and ||g||_1<=B.
    Conditions 1-3 in Section 2.
  • domain assumption The conjugate f* is available and the stochastic approximation F* satisfies the stated smoothness and max-structure properties, giving unbiased primal restoration.
    Conditions 1-3 in Section 3.
  • domain assumption Euclidean prox-function d(x)=1/2||x||^2.
    Section 4.2, stated as a simplification.
  • domain assumption Network graph is connected, with Laplacian W having second eigenvalue lambda_2(W)>0.
    Section 5, standard distributed optimization setup.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Decentralised convex optimisation with probability-proportional-to-size quantization." pith.science (2026). https://pith.science/paper/LZ4HVJZT

@misc{pith2026250118312,
  author       = {Pith},
  title        = {Pith review of: Decentralised convex optimisation with probability-proportional-to-size quantization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LZ4HVJZT}},
  note         = {Machine review of arXiv:2501.18312}
}
read the original abstract

Communication is one of the bottlenecks of distributed optimisation and learning. To overcome this bottleneck, we propose a novel quantization method that transforms a vector into a sample of components' indices drawn from a categorical distribution with probabilities proportional to values at those components. Then, we propose a primal and a primal-dual accelerated stochastic gradient methods that use our proposed quantization, and derive their convergence rates in terms of probabilities of large deviations. We focus on affine-constrained convex optimisation and its application to decentralised distributed optimisation problems. To illustrate the work of our algorithm, we apply it to the decentralised computation of semi-discrete entropy regularized Wasserstein barycenters.

Figures

Figures reproduced from arXiv: 2501.18312 by the authors.

Figure 1
Figure 1. Convergence curves of Algorithm 3 and AGM for different network topology, [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Visualised approximate barycenters obtained by Algorithm 3 and comparison [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 39 canonical work pages

  1. [1]

    Barycenters in the wasserstein space

    Martial Agueh and Guillaume Carlier. Barycenters in the wasserstein space. SIAM Journal on Mathematical Analysis, 43(2):904–924, 2011

    work page 2011

  2. [2]

    Optimal gradient compression for distributed and federated learning

    AlyazeedAlbasyoni, MherSafaryan, LaurentCondat, andPeterRichtárik. Optimal gradient compression for distributed and federated learning. arXiv preprint arXiv:2010.03246, 2020

    arXiv 2010

  3. [3]

    The convergence of sparsified gradient methods

    Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31, 2018

    work page 2018

  4. [4]

    Eigenvalues of the laplacian of a graph.Linear and multilinear algebra, 18(2):141–145, 1985

    William N Anderson Jr and Thomas D Morley. Eigenvalues of the laplacian of a graph.Linear and multilinear algebra, 18(2):141–145, 1985

    work page 1985

  5. [5]

    Wasserstein gan

    Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein gan. arXiv:1701.07875, 2017

    arXiv 2017

  6. [6]

    Averaging Atmospheric Gas Concentration Data using Wasserstein Barycenters

    Mathieu Barré, Clément Giron, Matthieu Mazzolini, and Alexandre d’Aspremont. Averaging atmospheric gas concentration data using wasser- stein barycenters. arXiv:2010.02762, 2020

    work page Pith review arXiv 2010

  7. [7]

    Dis- tribution’s template estimate with wasserstein metrics.Bernoulli, 21(2): 740–759, 2015

    Emmanuel Boissard, Thibaut Le Gouic, Jean-Michel Loubes, et al. Dis- tribution’s template estimate with wasserstein metrics.Bernoulli, 21(2): 740–759, 2015

    work page 2015

  8. [8]

    An lp-based, strongly-polynomial 2-approximation algorithm for sparse wasserstein barycenters.Operational Research, pages 1–41, 2020

    Steffen Borgwardt. An lp-based, strongly-polynomial 2-approximation algorithm for sparse wasserstein barycenters.Operational Research, pages 1–41, 2020

    work page 2020

Show all 48 references
  1. [9]

    On the computational com- plexity of finding a sparse wasserstein barycenter.arXiv:1910.07568, 2019

    Steffen Borgwardt and Stephan Patterson. On the computational com- plexity of finding a sparse wasserstein barycenter.arXiv:1910.07568, 2019

    1910 arXiv

  2. [10]

    Primal heuristics for wasserstein barycenters

    Pierre-Yves Bouchet, Stefano Gualandi, and Louis-Martin Rousseau. Primal heuristics for wasserstein barycenters. InInternational Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 239–255. Springer, 2020. 24

    2020

  3. [11]

    On the ergodic convergence rates of a first-order primal–dual algorithm.Mathematical Programming, 159 (1):253–287, 2016

    Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of a first-order primal–dual algorithm.Mathematical Programming, 159 (1):253–287, 2016

    2016

  4. [12]

    Fair regression with wasserstein barycenters

    Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. arXiv:2006.07286, 2020

    2006 arXiv

  5. [13]

    Sinkhorn distances: Lightspeed computation of optimal transport

    Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors,Advances in Neural Information Processing Systems 26, pages 2292–2300. Curran Associates, Inc., 2013

    2013

  6. [14]

    The mnist database of handwritten digit images for machine learning research

    Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141–142, 2012

    2012

  7. [15]

    Stochastic first order methods in smooth convex optimization

    Olivier Devolder et al. Stochastic first order methods in smooth convex optimization. Technical report, CORE, 2011

    2011

  8. [16]

    Decentralized algorithms for wasserstein barycenters

    Darina Dvinskikh. Decentralized algorithms for wasserstein barycenters. Humboldt Universitaet zu Berlin (Germany), 2021

    2021

  9. [17]

    Decentralize and randomize: Faster algorithm for wasserstein barycenters.Advances in Neural Information Processing Systems, 31, 2018

    Pavel Dvurechenskii, Darina Dvinskikh, Alexander Gasnikov, Cesar Uribe, and Angelia Nedich. Decentralize and randomize: Faster algorithm for wasserstein barycenters.Advances in Neural Information Processing Systems, 31, 2018

    2018

  10. [18]

    Con- struction of non-asymptotic confidence sets in 2-Wasserstein space

    Johannes Ebert, Vladimir Spokoiny, and Alexandra Suvorikova. Con- struction of non-asymptotic confidence sets in 2-Wasserstein space. arXiv:1703.03658, 2017

    2017 arXiv

  11. [19]

    Algebraic connectivity of graphs.Czechoslovak mathe- matical journal, 23(2):298–305, 1973

    Miroslav Fiedler. Algebraic connectivity of graphs.Czechoslovak mathe- matical journal, 23(2):298–305, 1973

    1973

  12. [20]

    Universal method for stochastic composite optimization problems.Computational Mathe- matics and Mathematical Physics, 58:48–64, 2018

    Alexander Vladimirovich Gasnikov and Yu E Nesterov. Universal method for stochastic composite optimization problems.Computational Mathe- matics and Mathematical Physics, 58:48–64, 2018. 25

    2018

  13. [21]

    Efficient numerical methods for entropy- linear programming problems.Computational Mathematics and Mathe- matical Physics, 56:514–524, 2016

    Alexander Vladimirovich Gasnikov, EB Gasnikova, Yu E Nesterov, and Aleksey Vladimirovich Chernov. Efficient numerical methods for entropy- linear programming problems.Computational Mathematics and Mathe- matical Physics, 56:514–524, 2016

    2016

  14. [22]

    Stochas- tic optimization for large-scale optimal transport.Advances in neural information processing systems, 29, 2016

    Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochas- tic optimization for large-scale optimal transport.Advances in neural information processing systems, 29, 2016

    2016

  15. [23]

    Optimal decentralized distributed algorithms for stochastic convex optimization

    Eduard Gorbunov, Darina Dvinskikh, and Alexander Gasnikov. Optimal decentralized distributed algorithms for stochastic convex optimization. arXiv preprint arXiv:1911.07363, 2019

    1911 arXiv

  16. [24]

    Accelerated alternating minimization, accelerated Sinkhorn’s algorithm and accelerated Iterative Bregman Projections

    Sergey Guminov, Pavel Dvurechensky, Nazarii Tupitsa, and Alexan- der Gasnikov. Accelerated alternating minimization, accelerated Sinkhorn’s algorithm and accelerated Iterative Bregman Projections. arXiv:1906.03622, 2019

    1906 arXiv

  17. [25]

    Fast algorithms for compu- tational optimal transport and wasserstein barycenter

    Wenshuo Guo, Nhat Ho, and Michael Jordan. Fast algorithms for compu- tational optimal transport and wasserstein barycenter. InInternational Conference on Artificial Intelligence and Statistics, pages 2088–2097, 2020

    2020

  18. [26]

    Natural compression for distributed deep learning

    Samuel Horváth, Chen-Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. InMathematical and Scientific Machine Learning, pages 129–141. PMLR, 2022

    2022

  19. [27]

    Distributed optimization with quantization for computing wasserstein barycenters.arXiv preprint arXiv:2010.14325, 2020

    Roman Krawtschenko, César A Uribe, Alexander Gasnikov, and Pavel Dvurechensky. Distributed optimization with quantization for computing wasserstein barycenters.arXiv preprint arXiv:2010.14325, 2020

    2010 arXiv

  20. [28]

    Communication-efficient algorithms for decentralized and stochastic optimization.Mathematical Programming, 180(1):237–284, 2020

    Guanghui Lan, Soomin Lee, and Yi Zhou. Communication-efficient algorithms for decentralized and stochastic optimization.Mathematical Programming, 180(1):237–284, 2020

    2020

  21. [29]

    Acceleration for compressed gradient descent in distributed and federated optimization

    Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. arXiv preprint arXiv:2002.11364, 2020. 26

    2002 arXiv

  22. [30]

    Tianyi Lin, Nhat Ho, Marco Cuturi, and Michael I. Jordan. On the Complexity of Approximating Multimarginal Optimal Transport.arXiv e-prints, 2019. arXiv:1910.00152

    2019 arXiv

  23. [31]

    Eigenvalues, diameter, and mean distance in graphs

    Bojan Mohar. Eigenvalues, diameter, and mean distance in graphs. Graphs and combinatorics, 7(1):53–64, 1991

    1991

  24. [32]

    Springer Science & Business Media, 2013

    Yurii Nesterov.Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013

    2013

  25. [33]

    Panaretos and Yoav Zemel.An Invitation to Statistics in Wasserstein Space: Fréchet Means in the Wasserstein Space W2, pages 59–74

    Victor M. Panaretos and Yoav Zemel.An Invitation to Statistics in Wasserstein Space: Fréchet Means in the Wasserstein Space W2, pages 59–74. Springer International Publishing, Cham, 2020. ISBN 978-3-030- 38438-8. doi: 10.1007/978-3-030-38438-8_3

    2020 doi

  26. [34]

    The earth mover’s distance as a metric for image retrieval.International journal of computer vision, 40(2):99–121, 2000

    Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. The earth mover’s distance as a metric for image retrieval.International journal of computer vision, 40(2):99–121, 2000

    2000

  27. [35]

    Optimal algorithms for smooth and strongly convex distributed optimization in networks

    Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In international conference on machine learning, pages 3027–3036. PMLR, 2017

    2017

  28. [36]

    Optimal convergence rates for convex distributed optimization in networks

    Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, 20 (159):1–31, 2019

    2019

  29. [37]

    Barycenters of natural images con- strained wasserstein barycenters for image morphing

    Dror Simon and Aviad Aberdam. Barycenters of natural images con- strained wasserstein barycenters for image morphing. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7910–7919, 2020

    2020

  30. [38]

    Simou, D

    E. Simou, D. Thanou, and P. Frossard. node2coords: Graph represen- tation learning with Wasserstein barycenters.IEEE Transactions on Signal and Information Processing over Networks, 7:17–29, 2021. doi: 10.1109/TSIPN.2020.3041940

    2021

  31. [39]

    Stonyakin, Darina Dvinskikh, Pavel Dvurechensky, Alexey Kroshnin, Olesya Kuznetsova, Artem Agafonov, Alexander Gasnikov, 27 Alexander Tyurin, César A

    Fedor S. Stonyakin, Darina Dvinskikh, Pavel Dvurechensky, Alexey Kroshnin, Olesya Kuznetsova, Artem Agafonov, Alexander Gasnikov, 27 Alexander Tyurin, César A. Uribe, Dmitry Pasechnyuk, and Sergei Arta- monov. Gradient methods for problems with inexact model of the objec- tive...

    2019 arXiv

  32. [40]

    Stochastic saddle-point optimization for wasserstein barycenters.arXiv:2006.06763, 2020

    Daniil Tiapkin, Alexander Gasnikov, and Pavel Dvurechensky. Stochastic saddle-point optimization for wasserstein barycenters.arXiv:2006.06763, 2020

    2006 arXiv

  33. [41]

    Nazarii Tupitsa, Pavel Dvurechensky, Alexander Gasnikov, and César A. Uribe. Multimarginal optimal transport by accelerated alternating mini- mization. In2020 IEEE 59th Conference on Decision and Control (CDC),

  34. [42]

    A dual approach for optimal algorithms in distributed optimization over networks

    César A Uribe, Soomin Lee, Alexander Gasnikov, and Angelia Nedić. A dual approach for optimal algorithms in distributed optimization over networks. In2020 Information Theory and Applications Workshop (ITA), pages 1–37. IEEE, 2020

    2020

  35. [43]

    Cambridge university press, 2018

    Roman Vershynin.High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  36. [44]

    A fast proximal point method for computing exact wasserstein distance

    Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. A fast proximal point method for computing exact wasserstein distance. In Uncertainty in Artificial Intelligence, pages 433–453. PMLR, 2020

    2020

  37. [45]

    Accelerated primal-dual algorithms for distributed smooth convex optimization over networks

    Jinming Xu, Ye Tian, Ying Sun, and Gesualdo Scutari. Accelerated primal-dual algorithms for distributed smooth convex optimization over networks. In International Conference on Artificial Intelligence and Statistics, pages 2381–2391. PMLR, 2020. 28 Appendix A. Technical statem...

    2020

  38. [47]

    if rt = r ≥ 1, eO dj B2 log n ∥W ∥2m max n r σ2 i q B2∗ γε χ(W ), B2 ∗ ε2 χ(W ), m3λ2(W ) γ2ε2 χ(W ) o ,

  39. [48]

    if rt = max ( 1, 34γσ 2 i αt ε χ(W ) max ( 18C2, C3 + C4 √ m3λ2(W ) γB∗ 2)) , (A.1) eO dj B2 log n ∥W ∥2m max n 1 σ2 i q B2∗ γε χ(W ), B2 ∗ ε2 χ(W ), m3λ2(W ) γ2ε2 χ(W ) o bits in total. 31

  40. [2020]

    (accepted), arXiv:2004.02294

    2004 arXiv

Pith tools

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