Pith. sign in

REVIEW 4 minor 17 references

An Elementary Proof of the Near Optimality of LogSumExp Smoothing

T0 review · 0 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read This paper proves that every convex, 1-smooth approximation of the coordinate-wise max in the infinity norm must differ from it by at least about 0.40726 ln d, so LogSumExp—the standard softmax—is near-optimal with at most a 1.23-fold gap.

desk verdict A clean elementary proof that improves the best lower bound for smoothing max from (1/8)ln d to about 0.40726 ln d and settles d=2,3 exactly; the proof holds up and the paper deserves refereeing. read the letter →

arxiv 2512.10825 v3 pith:53JAKY3X submitted 2025-12-11 math.ST cs.LGmath.OCstat.TH

Thabo Samakhoana , Benjamin Grimmer This is my paper
classification math.STcs.LGmath.OCstat.TH MSC 90C2526B25
keywords LogSumExpsoftmaxmaxfunctionsmoothinginfinitynormconvexlowerboundnonsmoothoptimizationmaximumeigenvalue
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

This paper asks how well any convex, 1-smooth function can approximate the coordinate-wise max in the infinity norm. Its central result is an elementary lower bound: every such smoothing must miss the max by at least γ(d), a quantity that grows like 0.40726 ln d; for overestimators, the corresponding gap is at least 0.8145 ln d. Since LogSumExp is an overestimator with gap exactly ln d, this pins the classical softmax as optimal up to a small constant factor, at most about 1.23. The paper also constructs exactly optimal smoothings for d=2 and d=3, showing LogSumExp is not exactly optimal in low dimensions. A reader should care because this gap controls the dimension dependence of accelerated nonsmooth optimization and of softmax-based attention mechanisms.

What carries the argument

The central object is the partition-sum lower bound γ(d)=max Σ(1−j_{ℓ−1}/j_ℓ)^2 over chains 1=j0<...<jk=d. The proof is elementary: symmetrize any candidate f by averaging over permutations, note all gradients lie in the probability simplex, write a convexity-smoothness inequality Q_{i,j}≥0 at the test points x^{(j)} (first j coordinates equal 1/j), telescope along the chain, take α→∞, and use permutation invariance plus boundedness of f(0) to force ∇f(αx^{(j)})→x^{(j)}. The asymptotic constant β≈0.28467 solves 2β ln β − β +1=0 and yields 2β(1−β)≈0.40726.

What would settle it

Find a convex, 1-smooth f with ||f−σmax||∞ < γ(d) for some d≥2—for example, run a high-accuracy convex optimization over candidate smoothings for d=4 and see whether the minimal deviation dips below γ(4)=9/16. Such a function would disprove Theorem 1.1.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: for every d≥2, the best possible deviation δ*(d) of a convex, 1-smooth (in the infinity norm) function from the max function is at least γ(d), where γ(d) is a maximization over chains of coordinate-block sizes. Asymptotically γ(d)∼0.40726 ln d, so any overestimating smoothing differs from the max by at least ∼0.8145 ln d; since LogSumExp overestimates by exactly ln d, it is optimal up to factor ln d/(0.8145 ln d)≈1.23. For d=2,3 the lower bound is achieved by explicit smoothings built from a quadratic regularizer on the simplex, giving exact constants (1−1/d)^2 and disproving exact optimality of LogSumExp in low dimensions. For d≥4, exact optimality

Load-bearing premise

The load-bearing step is that the limiting behavior of any good smoothing is captured by its values and gradients on the rays through the sparse test points x^{(j)}; if a better smoothing behaved differently off those rays, the γ(d) lower bound would not apply to it.

Editorial extensions

If this is right

  • LogSumExp's ln d gap is at most about 1.23 times the best possible gap, so no alternative infinity-norm smoothing can improve the dimension dependence beyond a small constant.
  • Smoothing-based reductions for minimizing a finite maximum cannot beat Ω(√ln d) in dimension; dimension-independent accelerated rates are ruled out by this barrier.
  • For d=2 and d=3, the exact optimal gap is (1−1/d)^2, strictly below LogSumExp's 0.5 ln d, so the entropy-based softmax is not exactly optimal in low dimensions.
  • The same lower bound transfers to smoothing the maximum eigenvalue function under the spectral norm, via diagonal embeddings, with matching order ln d.
  • For d≥4, the paper's explicit quadratic smoothings are dominated by LogSumExp, and whether γ(d) is exactly tight remains an open question.

Reading between the lines

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

  • A natural next target is d=4: computing or bounding δ*(4) would show whether the exact-tightness phenomenon (γ(d)=(1−1/d)^2) ends at d=3. This is the paper's own open question, and a numerical search over simplex regularizers is the cheapest probe.
  • The lower bound's test points are sparse vectors with equal positive entries; if one could extend the chain construction to non-symmetric test sets, the constant 0.40726 might improve, potentially closing the gap to 0.5. That would require proving that some non-symmetric smoothing beats every symmetric one, since the paper shows symmetrization never hurts.
  • The dual reformulation in the appendix ties the smoothing gap to the range of a 1-strongly convex function on the simplex, and hence to the regret of prediction with expert advice; sharper regret tradeoffs would automatically translate into sharper smoothing lower bounds.
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

0 major / 4 minor

Summary. The paper studies the best possible uniform approximation of the coordinate-wise maximum function on R^d by convex functions that are 1-smooth with respect to the infinity norm. Its main result, Theorem 1.1, gives a lower bound delta*(d) >= gamma(d), where gamma(d) is a partition-sum quantity, and proves the asymptotic gamma(d) ~ 2 beta (1 - beta) ln d, with beta approx 0.28467 the root of 2 beta ln beta - beta + 1 = 0. Together with the LogSumExp upper bound 0.5 ln d, this shows that LogSumExp is optimal up to a constant factor of about 1.23. The proof is elementary: it symmetrizes the smoothing, uses the simplex constraint on gradients, applies a standard inequality for smooth convex functions on a finite family of test points, and then analyzes the resulting recurrence for gamma(d). The paper also proves exact optimality for d = 2 and d = 3 by explicit Nesterov-style smoothings, and it includes an appendix deriving the prior statistical lower bound for completeness.

Significance. This is a substantial contribution. It replaces the indirect game-theoretic and statistical lower bounds with a direct, self-contained argument, and it improves the known asymptotic lower bound by a factor of about 3.3 while narrowing the gap with LogSumExp to roughly 23%. The low-dimensional exact constructions are also valuable, and the paper is honest about the lack of tightness for d >= 4. The proof has no free parameters and does not fit constants to the desired conclusion; the bound is derived from first principles. If the result is correct, it confirms that LogSumExp is near-optimal among all convex 1-smooth approximations, not merely within a restricted family.

minor comments (4)
  1. [Section 1.1, Theorem 1.1] The display '2 beta (1 - beta) >= 0.40726' should read 'approx 0.40726' or '= 0.40726...', since the numerical value is an approximation obtained from the equation defining beta. The current inequality sign is technically true but misleading.
  2. [Section 2, asymptotic bounds for gamma(d)] The continuous-relaxation step in the upper bound asserts without derivation that phi = beta is the maximizer. A one-line derivative check and the identity 2 beta (1 - beta) ln beta + (1 - beta)^2 = 0, which follows from the defining equation of beta, would make this fully transparent. The lower-bound step also ends with 'collects and simplifies terms'; writing the final inequality explicitly would remove any doubt, since it is not immediate that the displayed expression remains >= -2(d-1)/d for all d >= 3.
  3. [Section 3, proof of Theorem 1.2] The centering shift by gamma(d) in the definition of f_d is essential for the claimed two-sided error. The sentence 'the largest deviation between f_d and sigma_max is ...' is correct only after this shift. It would help to state explicitly that the range of the quadratic distance h is c_d/2 (1 - 1/d), so that the centered gap is c_d/4 (1 - 1/d).
  4. [Section 2, equation (2.1)] The inequality (2.1) is a standard but non-obvious consequence of convexity and smoothness; the reader would benefit from a short statement of the underlying inequality, since [17, Theorem 5.8] packages both convexity and smoothness in one place.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is derived from first principles; existing bounds enter only as comparisons or background.

full rationale

The central result (Theorem 1.1) is self-contained. The proof of the lower bound δ*(d) ≥ γ(d) proceeds from standard convex-analysis inequalities: the p-norm smoothness/convexity inequality (2.1) quoted from Beck [17], the permutation-symmetrization Lemma 2.1, and the subgradient simplex Lemma 2.2. These are general facts about smooth convex functions; none of them assumes the LogSumExp upper bound or the desired lower bound. The quantity γ(d) is not fitted to match δ*(d); it is the maximum over all increasing integer sequences of a sum that arises naturally from the proof, and the asymptotic constant β is the maximizer of a continuous relaxation, not a data-fitting parameter. The LogSumExp function appears only as the upper-bound comparison after the lower bound is established, so the theorem is not circular. Proposition 1.2 is explicitly a reduction to the external online-learning lower bound of Cesa-Bianchi et al. [8] and the FTRL upper bound of Shalev-Shwartz [13]; it is presented as background/context, and the appendix proof is transparent about the reduction, so it is not a disguised use of the target result. The d=2 and d=3 optimality claims are verified by explicit construction with direct calculations of the smoothing gap, not by appealing to the lower bound being proved. The only self-citation, [10], appears in the related-work discussion of two-norm smoothing and is not load-bearing for any result in this paper. The open gap for d≥4 is explicitly acknowledged as a limitation and does not indicate circularity. Overall, no prediction is equivalent by construction to its inputs, and no load-bearing argument reduces to self-citation.

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

No free parameters are fitted: β is the unique root of 2βlnβ−β+1 in (0,1), forced by the continuous relaxation, and c_d is the exact optimum of a finite ratio maximization. The central proof relies on standard convex-analysis inequalities (co-coercivity, subgradient inequality, conjugate duality) and on the symmetrization lemma; no invented entities appear.

assumptions (4)
  • standard math Convex 1-smooth functions satisfy the co-coercivity inequality used in Eq. (2.1).
    Cites Beck [17, Thm 5.8]; standard convex analysis.
  • standard math Averaging a function over permutations preserves convexity and p-norm 1-smoothness.
    Used in Lemma 2.1; follows from ∥P∥_{p→p}=1 and convexity.
  • standard math Nesterov duality: f is 1-smooth in the infinity norm iff f* is 1-strongly convex in the one-norm.
    Used in Appendix A and in the d=2,3 constructions; cites Beck [17, Thm 5.26].
  • standard math Regret lower bound of Cesa-Bianchi et al. and the FTRL regret upper bound of Shalev-Shwartz.
    Used only for the auxiliary Proposition 1.2, not for the main Theorem 1.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Elementary Proof of the Near Optimality of LogSumExp Smoothing." pith.science (2026). https://pith.science/paper/53JAKY3X

@misc{pith2026251210825,
  author       = {Pith},
  title        = {Pith review of: An Elementary Proof of the Near Optimality of LogSumExp Smoothing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/53JAKY3X}},
  note         = {Machine review of arXiv:2512.10825}
}
abstract

We consider the design of smoothings of the (coordinate-wise) max function in $\mathbb{R}^d$ in the infinity norm. The LogSumExp function $f(x)=\ln(\sum^d_i\exp(x_i))$ provides a classical smoothing, differing from the max function in value by at most $\ln(d)$. We provide an elementary construction of a lower bound, establishing that every overestimating smoothing of the max function must differ by at least $\sim 0.8145\ln(d)$. Hence, LogSumExp is optimal up to small constant factors. However, we provide strictly stronger smoothings showing the entropy-based LogSumExp approach is not exactly optimal. In small dimensions, we propose exactly optimal smoothings, attaining our lower bound.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 2 linked inside Pith

  1. [1]

    Smooth minimization of non-smooth functions.Math

    Yu Nesterov. Smooth minimization of non-smooth functions.Math. Program., 103(1):127–152, May 2005

    2005

  2. [2]

    André F. T. Martins and Ramón F. Astudillo. From softmax to sparsemax: a sparse model of attention and multi-label classification. InProceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48, ICML’16, page 1614–1623. JMLR.org, 2016

    2016

  3. [3]

    Kavosh Asadi and Michael L. Littman. An alternative softmax operator for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 243–252, 2017

    2017

  4. [4]

    Smoothing and first order methods: A unified framework.SIAM Journal on Optimization, 22:557–580, 2012

    Amir Beck and Marc Teboulle. Smoothing and first order methods: A unified framework.SIAM Journal on Optimization, 22:557–580, 2012

    2012

  5. [5]

    A method of solving a convex programming problem with convergence rateo(1/k2)

    Yurii Nesterov. A method of solving a convex programming problem with convergence rateo(1/k2). Soviet Mathematics Doklady, 27(2):372–376, 1983

    1983

  6. [6]

    Gomez, Łukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. InProceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 6000–6010, Red Hook, NY, USA, 2017

    2017

  7. [7]

    Optimal approxi- mation - smoothness tradeoffs for soft-max functions

    Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Manolis Zampetakis. Optimal approxi- mation - smoothness tradeoffs for soft-max functions. InProceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, 2020

    2020

  8. [8]

    Helmbold, Robert E

    Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice.J. ACM, 44(3):427–485, May 1997

    1997

Show all 17 references
  1. [9]

    Proximité et dualité dans un espace hilbertien.Bulletin de la Société Mathématique de France, 93:273–299, 1965

    Jean-Jacques Moreau. Proximité et dualité dans un espace hilbertien.Bulletin de la Société Mathématique de France, 93:273–299, 1965

    1965

  2. [10]

    The optimal smoothings of sublinear functions and convex cones.arXiv preprint arXiv:2508.06681, 2025

    Thabo Samakhoana and Benjamin Grimmer. The optimal smoothings of sublinear functions and convex cones.arXiv preprint arXiv:2508.06681, 2025. 10

    2025 arXiv

  3. [11]

    On lower complexity bounds for large-scale smooth convex optimization.Journal of Complexity, 31(1):1–14, 2015

    Cristóbal Guzmán and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization.Journal of Complexity, 31(1):1–14, 2015

    2015

  4. [12]

    The price of adaptivity in stochastic convex optimization.Mathematical Programming, Sep 2025

    Yair Carmon and Oliver Hinder. The price of adaptivity in stochastic convex optimization.Mathematical Programming, Sep 2025

    2025

  5. [13]

    Online learning and online convex optimization.Found

    Shai Shalev-Shwartz. Online learning and online convex optimization.Found. Trends Mach. Learn., 4(2):107–194, February 2012

    2012

  6. [14]

    A modern introduction to online learning.ArXiv, abs/1912.13213, 2019

    Francesco Orabona. A modern introduction to online learning.ArXiv, abs/1912.13213, 2019

    1912 arXiv

  7. [15]

    Accelerated first-order methods for hyperbolic programming.Math

    James Renegar. Accelerated first-order methods for hyperbolic programming.Math. Program., 173(1- 2):1–35, 2019

    2019

  8. [16]

    Radial duality part ii: applications and algorithms.Math

    Benjamin Grimmer. Radial duality part ii: applications and algorithms.Math. Program., 205(1–2):69–105, May 2023

    2023

  9. [17]

    Follow-the-Regularized-Leader

    Amir Beck.First-Order Methods in Optimization. SIAM-Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2017. A Proof of Proposition 1.2 – A Statistical Lower Bound Reduction Here, we take the dual perspective of designing a strongly convex functionh on the ...

    2017

Pith tools

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