Pith. sign in

REVIEW 41 references

Improved Stochastic Optimization of LogSumExp

T0 review · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read A rescaled SoftPlus family approximates LogSumExp with O(ρ) error, enabling stable stochastic optimization in entropic OT and KL-DRO.

arxiv 2509.24894 v4 pith:MERUPQBD submitted 2025-09-29 math.OC cs.LG

Egor Gladin , Alexey Kroshnin , Jia-Jie Zhu , Pavel Dvurechensky This is my paper
classification math.OCcs.LG
keywords optimizationdivergencelogsumexpstochasticapproximationdualgradientadvantages
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

Many machine learning objectives contain a LogSumExp: the log of a sum of exponentials. When that sum ranges over a large dataset, computing the gradient requires touching every term. Existing tricks that sample a small batch introduce a bias that only shrinks with batch size. This paper proposes instead to replace each exponential with a softened version, log(1 + e^x), scaled by a parameter ρ, and shows that the resulting objective is close to the original: the error is at most proportional to ρ, and it can be made arbitrarily small.

The approximation has a clean dual interpretation. The original LogSumExp is the Legendre transform of the KL divergence. If the KL term is swapped for a modified 'safe KL' divergence, whose density ratio is capped at 1/ρ, the dual becomes exactly the rescaled SoftPlus objective. The capped density also explains the name: the reweighting cannot blow up. However, the paper's 'divergence' label is not technically correct under the standard definition, because the generator does not vanish at equal measures.

The authors test the idea in two settings. In entropy-regularized optimal transport, the standard neural dual solver overflows in floating point when the regularization is small; the SoftPlus variant runs stably and continues to make progress. In distributionally robust optimization, the new gradient estimator outperforms the biased batch-softmax baseline when batches are small, though the advantage is less clear for very small penalty coefficients. The main practical message: a single scalar ρ trades approximation accuracy against smoothness, and intermediate values such as 10^-3 work best.

Extended reading notes

Core claim

The central assertion, from Section 2 and the abstract, is that F_ρ(φ;µ) = inf_α [α-1 + (1/ρ)∫ log(1+ρ e^{φ-α}) dµ] is an O(ρ)-accurate approximation of the log-partition F that preserves convexity and, for L-smooth inputs, has smoothness constant scaling linearly with L, enabling stochastic-gradient optimization with bias that does not depend on batch size. If true, the method provides a drop-in replacement for LogSumExp in large-scale OT and DRO.

Load-bearing premise

The practical advantage depends on the assumption that for a chosen ρ, the approximation is both within O(ρ) of the original objective and smooth enough for SGD to converge on the original objective within a reasonable epoch budget. The accuracy bounds in Proposition 2.4 require conditions on φ (upper boundedness in (iv), or the exponential condition in (iii)) that are not verified for the unbounded losses used in the experiments; the experiments simply set ρ=10^-3 and report good performance. If those conditions fail for a target loss, the approximation gap could be uncontrolled.

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.

Assumptions & free parameters 1 free parameters · 4 assumptions · 1 invented entities

The only free parameter is the approximation accuracy ρ, chosen by hand. The main axioms are the standard convex dual representation and technical smoothness/boundedness assumptions on the loss. The invented entity is the 'safe KL' functional, which is not an actual divergence.

free parameters (1)
  • ρ = 10^-3 in most experiments, 0.1 in UOT experiment
    Tunable approximation accuracy/smoothness trade-off; set by hand, not learned from data.
assumptions (4)
  • standard math Gibbs variational principle / convex dual representation for f-divergences
    Used to write F(φ;µ) = sup_ν [∫φ dν - D_KL(ν,µ)] and the analogous representation for Fρ in (5), citing Gibbs (1902) and Birrell et al. (2022).
  • standard math f_ρ is convex on [0,1/ρ] and its conjugate is f*_ρ(s) = (1/ρ) log(1+ρ e^s) - 1
    Direct calculation; used in Lemmas 2.2-2.3 to derive the rescaled SoftPlus objective.
  • domain assumption Assumption that the loss L(x,θ) is L-smooth and bounded below for smoothness preservation
    Needed for the smoothness constant bound in Prop C.2; in experiments, squared loss and CNN cross-entropy satisfy this in a loose sense.
  • domain assumption µ is a probability measure and e^φ is integrable
    The log-partition functional (1) is defined under this; used throughout the approximation theory.
invented entities (1)
  • Safe KL divergence D_ρ
    purpose: Provides the dual variational interpretation of the SoftPlus approximation; used as a penalty in regularized OT and DRO.
    It is a new mathematical construction defined in the paper. It does not satisfy the standard f-divergence condition f(1)=0, so it is not actually a divergence; it has no independent falsifiable handle outside the paper's own variational bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Stochastic Optimization of LogSumExp." pith.science (2026). https://pith.science/paper/MERUPQBD

@misc{pith2026250924894,
  author       = {Pith},
  title        = {Pith review of: Improved Stochastic Optimization of LogSumExp},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MERUPQBD}},
  note         = {Machine review of arXiv:2509.24894}
}
abstract

The LogSumExp function, dual to the Kullback-Leibler (KL) divergence, plays a central role in many important optimization problems, including entropy-regularized optimal transport (OT) and distributionally robust optimization (DRO). In practice, when the number of exponential terms inside the logarithm is large or infinite, optimization becomes challenging since computing the gradient requires differentiating every term. We propose a novel convexity- and smoothness-preserving approximation to LogSumExp that can be efficiently optimized using stochastic gradient methods. This approximation is rooted in a sound modification of the KL divergence in the dual, resulting in a new $f$-divergence called the Safe KL divergence. Our experiments and theoretical analysis of the LogSumExp-based stochastic optimization, arising in DRO and continuous OT, demonstrate the advantages of our approach over existing baselines.

Figures

Figures reproduced from arXiv: 2509.24894 by the authors.

Figure 1
Figure 1. fρ(t) for different values of ρ. It is easy to see that fρ(t) → f0(t) := tlog t + 1 − t as ρ → 0. Since f0 induces the standard KL-divergence, Dρ is its approximation with accuracy regulated by the parameter ρ. Using the variational representation, we define Fρ(φ; µ) := sup ν Z X φ(x) dν(x) − Dρ(ν, µ) : ν ∈ P(X ), Z X |φ(x)| dν(x) < ∞  . (5) (i.e., Fρ(·; µ) is the convex conjugate of Dρ(·, µ)). Note that the last … view at source ↗
Figure 2
Figure 2. Test-set eOT semi-dual objective vs. iteration for different regularization strengths [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Performance of ERM and two DRO approaches on MNIST with noisy labels. Left: ERM [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Densities of source and target distributions in the eOT experiment. [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: Left: convergence of kernel SGD applied to the dual objective (12) (blue and orange) and [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

41 extracted references · 8 linked inside Pith

  1. [1]

    Label noise types and their effects on deep learning

    G \"o rkem Algan and Ilkay Ulusoy. Label noise types and their effects on deep learning. arXiv preprint arXiv:2003.10471, 2020

    arXiv 2003

  2. [2]

    Methods of Information Geometry

    Shun-ichi Amari and Hiroshi Nagaoka. Methods of Information Geometry . American Mathematical Soc., 2000. ISBN 978-0-8218-4302-4

    2000

  3. [3]

    Robust solutions of optimization problems affected by uncertain probabilities

    Aharon Ben-Tal, Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59 0 (2): 0 341--357, February 2013. ISSN 0025-1909, 1526-5501. doi:10.1287/mnsc.1120.1641. URL http://pubsonline.informs.org/doi/abs/10.1287/mnsc.1120.1641

    arXiv 2013

  4. [4]

    Iterative bregman projections for regularized transportation problems

    Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyr \'e . Iterative bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37 0 (2): 0 A1111--A1138, 2015

    2015

  5. [5]

    Katsoulakis, Yannis Pantazis, and Luc Rey-Bellet

    Jeremiah Birrell, Paul Dupuis, Markos A. Katsoulakis, Yannis Pantazis, and Luc Rey-Bellet. (f,gamma)-divergences: Interpolating between f-divergences and integral probability metrics. Journal of Machine Learning Research, 23 0 (39): 0 1--70, 2022. URL http://jmlr.org/papers/v23/21-0100.html

    2022

  6. [6]

    Pattern recognition and machine learning, volume 4

    Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning, volume 4. Springer, 2006

    2006

  7. [7]

    Efficient bounds for the softmax function and applications to approximate inference in hybrid models

    Guillaume Bouchard. Efficient bounds for the softmax function and applications to approximate inference in hybrid models. In NIPS 2007 workshop for approximate Bayesian inference in continuous/hybrid systems, volume 6, 2007

    2007

  8. [8]

    Unbalanced optimal transport: Dynamic and Kantorovich formulation

    Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. Unbalanced optimal transport: Dynamic and Kantorovich formulation. arXiv:1508.05216 [math], February 2019. URL http://arxiv.org/abs/1508.05216. arXiv: 1508.05216

    arXiv 2019

Show all 41 references
  1. [9]

    Sinkhorn distances: Lightspeed computation of optimal transport

    Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013

    2013

  2. [10]

    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 0 (6): 0 141--142, 2012

    2012

  3. [11]

    Stochastic optimization for large-scale optimal transport

    Aude Genevay, Marco Cuturi, Gabriel Peyr\' e , and Francis Bach. Stochastic optimization for large-scale optimal transport. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp.\ 3440--3448. Curran ...

    2016

  4. [12]

    What every computer scientist should know about floating-point arithmetic

    David Goldberg. What every computer scientist should know about floating-point arithmetic. ACM computing surveys (CSUR), 23 0 (1): 0 5--48, 1991

    1991

  5. [13]

    Kullback- Leibler Divergence Constrained Distributionally Robust Optimization

    Zhaolin Hu and L Jeff Hong. Kullback- Leibler Divergence Constrained Distributionally Robust Optimization

  6. [14]

    On the translocation of masses

    Leonid Kantorovich. On the translocation of masses. (Doklady) Acad. Sci. URSS (N.S.), 37: 0 199--201, 1942

    1942

  7. [15]

    Fast yet simple natural-gradient descent for variational inference in complex models

    Mohammad Emtiyaz Khan and Didrik Nielsen. Fast yet simple natural-gradient descent for variational inference in complex models. In 2018 International Symposium on Information Theory and Its Applications (ISITA), pp.\ 31--35. IEEE, 2018

    2018

  8. [16]

    The Bayesian learning rule

    Mohammad Emtiyaz Khan and H vard Rue. The Bayesian learning rule. 0 (arXiv:2107.04562), June 2023

    2023 arXiv

  9. [17]

    A new optimal transport distance on the space of finite Radon measures

    Stanislav Kondratyev, L \'e onard Monsaingeon, and Dmitry Vorotnikov. A new optimal transport distance on the space of finite Radon measures. Advances in Differential Equations, 21 0 (11/12): 0 1117 -- 1164, 2016. doi:10.57262/ade/1476369298. URL https://doi.org/10.57262/ade/1...

    2016

  10. [18]

    Distributionally Robust Optimization

    Daniel Kuhn, Soroosh Shafiee, and Wolfram Wiesemann. Distributionally Robust Optimization . 0 (arXiv:2411.02549), November 2024. doi:10.48550/arXiv.2411.02549

    2024 doi arXiv

  11. [19]

    Large-scale methods for distributionally robust optimization

    Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances in neural information processing systems, 33: 0 8847--8860, 2020

    2020

  12. [20]

    Optimal entropy-transport problems and a new Hellinger – Kantorovich distance between positive measures

    Matthias Liero, Alexander Mielke, and Giuseppe Savaré. Optimal entropy-transport problems and a new Hellinger – Kantorovich distance between positive measures. Inventiones mathematicae, 211 0 (3): 0 969--1117, March 2018. ISSN 0020-9910, 1432-1297. doi:10.1007/s00222-017-0759-...

    2018 doi

  13. [21]

    Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations

    Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171 0 (1-2): 0 115--166, September 2018. ISSN 0025-5610, 1436-4646. doi:10.1...

    2018 doi

  14. [22]

    Guaranteed bounds on information-theoretic measures of univariate mixtures using piecewise log-sum-exp inequalities

    Frank Nielsen and Ke Sun. Guaranteed bounds on information-theoretic measures of univariate mixtures using piecewise log-sum-exp inequalities. Entropy, 18 0 (12): 0 442, 2016

    2016

  15. [23]

    Outlier-robust wasserstein dro

    Sloan Nietert, Ziv Goldfeld, and Soroosh Shafiee. Outlier-robust wasserstein dro. Advances in Neural Information Processing Systems, 36: 0 62792--62820, 2023

    2023

  16. [24]

    Sparse spatial autoregressions

    R Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33 0 (3): 0 291--297, 1997

    1997

  17. [25]

    On solving large-scale finite minimax problems using exponential smoothing

    EY Pee and Johannes O Royset. On solving large-scale finite minimax problems using exponential smoothing. Journal of optimization theory and applications, 148 0 (2): 0 390--421, 2011

    2011

  18. [26]

    Computational optimal transport: With applications to data science

    Gabriel Peyr\'e and Marco Cuturi. Computational optimal transport: With applications to data science. Foundations and Trends® in Machine Learning, 11 0 (5-6): 0 355--607, 2019. ISSN 1935-8237. doi:10.1561/2200000073. URL http://dx.doi.org/10.1561/2200000073. arXiv:1803.00567

    2019 arXiv

  19. [27]

    Information theory: From coding to learning

    Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge university press, 2025

    2025

  20. [28]

    Optimization of conditional value-at-risk

    R Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 2: 0 21--42, 2000

    2000

  21. [29]

    Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs , and Modeling

    Filippo Santambrogio. Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs , and Modeling . Springer International Publishing, 2015. ISBN 9783319208282. doi:10.1007/978-3-319-20828-2. URL http://dx.doi.org/10.1007/978-3-319-20828-2

    2015 doi

  22. [30]

    Certifying some distributional robustness with principled adversarial training

    Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv:1710.10571 [cs, stat], May 2020

    2020 arXiv

  23. [31]

    Statistical learning with conditional value at risk

    Tasuku Soma and Yuichi Yoshida. Statistical learning with conditional value at risk. arXiv preprint arXiv:2002.05826, 2020

    2002 arXiv

  24. [32]

    Demonstration-regularized RL

    Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Alexey Naumov, Pierre Perrault, Michal Valko, and Pierre Menard. Demonstration-regularized RL . In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id...

    2024

  25. [33]

    Michalis K. Titsias. One-vs-each approximation to softmax for scalable estimation of probabilities. Advances in Neural Information Processing Systems, 29, 2016

    2016

  26. [34]

    Optimal transport: old and new, volume 338

    C \'e dric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008

    2008

  27. [35]

    Graphical models, exponential families, and variational inference

    Martin J Wainwright, Michael I Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning , 1 0 (1--2): 0 1--305, 2008

    2008

  28. [36]

    Sinkhorn distributionally robust optimization

    Jie Wang, Rui Gao, and Yao Xie. Sinkhorn distributionally robust optimization. arXiv preprint arXiv:2109.11926, 2021

    2021 arXiv

  29. [37]

    Outlier-robust distributionally robust optimization via unbalanced optimal transport

    Zifan Wang, Yi Shen, Michael Zavlanos, and Karl H Johansson. Outlier-robust distributionally robust optimization via unbalanced optimal transport. Advances in Neural Information Processing Systems, 37: 0 52189--52214, 2024

    2024

  30. [38]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

  31. [39]

    @esa (Ref

    \@ifxundefined[1] #1\@undefined \@firstoftwo \@secondoftwo \@ifnum[1] #1 \@firstoftwo \@secondoftwo \@ifx[1] #1 \@firstoftwo \@secondoftwo [2] @ #1 \@temptokena #2 #1 @ \@temptokena \@ifclassloaded agu2001 natbib The agu2001 class already includes natbib coding, so you should ...

  32. [40]

    \@lbibitem[] @bibitem@first@sw\@secondoftwo \@lbibitem[#1]#2 \@extra@b@citeb \@ifundefined br@#2\@extra@b@citeb \@namedef br@#2 \@nameuse br@#2\@extra@b@citeb \@ifundefined b@#2\@extra@b@citeb @num @parse #2 @tmp #1 NAT@b@open@#2 NAT@b@shut@#2 \@ifnum @merge>\@ne @bibitem@firs...

  33. [41]

    @open @close @open @close and [1] URL: #1 \@ifundefined chapter * \@mkboth \@ifxundefined @sectionbib * \@mkboth * \@mkboth\@gobbletwo \@ifclassloaded amsart * \@ifclassloaded amsbook * \@ifxundefined @heading @heading NAT@ctr thebibliography [1] @ \@biblabel @NAT@ctr \@bibset...

Pith tools

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