Pith. sign in

REVIEW 3 major objections 4 minor 9 references

A single-loop stochastic algorithm, SCENT, minimizes entropic-risk objectives—log-sum-exp-type losses over enormous class sets—at the same O(1/√T) rate as plain SGD on smooth convex problems, by updating the dual variable through mirror des

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 05:11 UTC pith:M7LOECGM

load-bearing objection Genuinely useful SPMD algorithm and analysis for compositional entropic risk, but the main theorem's assumptions do not cover the paper's own deep-learning experiments. the 3 major comments →

arxiv 2602.02877 v2 pith:M7LOECGM submitted 2026-02-02 cs.LG

A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization

Xiyuan Wei , Linli Zhou , Bokun Wang , Chih-Jen Lin , Tianbao Yang This is my paper
classification cs.LG MSC 90C2590C15
keywords compositional entropic riskLog-E-Expstochastic proximal mirror descentBregman divergencedual optimizationextreme classificationpartial AUCdistributionally robust optimization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper claims that compositional entropic risk minimization—a loss family covering extreme classification, contrastive learning, partial AUC, and distributionally robust optimization—can be solved by a simple single-loop stochastic algorithm at the same O(1/√T) convergence rate as standard convex SGD. The obstacle it removes is the exponentially large smoothness constant that appears when the dual variable is updated by gradient descent. The proposed update, stochastic proximal mirror descent with a Bregman divergence induced by e^{-ν}, keeps iterates bounded, avoids numerical overflow, and controls the variance that breaks biased mini-batch methods. A sympathetic reader would take away a design principle: the geometry of the update should match the exponential form of the objective, and then the exponential constants can be tamed rather than endured.

Core claim

The paper's central claim is Theorem 3.6: under convexity and bounded scores, SCENT guarantees E[F_CERM(bar w_T) - F_CERM(w*)] ≤ (1/(2ηα√T))||w1 - w*||² + D_φ(ν*,ν0)/(αB√T) + αV/√T, i.e., an O(1/√T) convergence rate. This is achieved by solving the equivalent min-min dual problem min_{w,ν} (1/n)ΣE[e^{s_i(w;ζ)-ν_i} + ν_i] with a dual update of the form ν_{i,t} = argmin_ν e^{s_i(w_t;ζ)-ν} + ν + (1/α_t)D_φ(ν,ν_{i,t-1}), where φ(ν)=e^{-ν}. The mirror step has a closed form, ν_t = ν_{t-1} + log(1+α_t e^{s}) - log(1+α_t e^{ν_{t-1}}), which keeps ν in [c0,c1], avoids numerical overflow, and bounds the stochastic variance. The paper also shows that biased SGD is the α=∞ limit of this scheme and that

What carries the argument

The load-bearing object is the stochastic proximal mirror descent (SPMD) update on the dual variable, with Bregman divergence D_φ(ν,ν') = e^{-ν} - e^{-ν'} + e^{-ν'}(ν-ν') induced by φ(ν)=e^{-ν}. Because the stochastic objective Φ(w,ν;ζ)=e^{s(w;ζ)-ν}+ν is convex in ν and the mirror map matches its exponential curvature, the update admits a closed-form log-ratio expression that stays inside [c0,c1], avoids overflow, and yields a contractive variance bound. In the analysis, a virtual full-coordinate sequence arν_t makes the block-coordinate gradient estimator unbiased, and Lemma 3.5 bounds the resulting linearized regret in terms of the Bregman divergence and the variance δ²_t.

Load-bearing premise

The rate relies on each random score s_i(w;ζ) living inside a fixed interval [c0,c1] for every w and ζ; if scores grow without bound—as with unbounded linear logits or unconstrained deep features—the dual iterates may leave that interval, the variances can blow up, and the O(1/√T) guarantee no longer follows.

What would settle it

Run SCENT on a one-dimensional convex Log-E-Exp instance with s(w;ζ)=a·w·ζ, ζ uniform on [0,1], W=[-R,R] (so Assumption 3.2 holds), compute the empirical gap F_CERM(bar w_T)-F_CERM(w*) for T=10^2,...,10^6, and check the log-log slope; a slope significantly worse than -1/2 would contradict Theorem 3.6. A second check: drop the boundedness assumption by making W unbounded and observe whether the empirical gap stops decreasing, which would localize the load-bearing assumption.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If Theorem 3.6 is correct, convex CERM problems—including single-logit softmax losses over huge label sets—are solvable to ε-accuracy in O(1/ε²) stochastic iterations, the same order as SGD for smooth convex optimization.
  • The comparison in Section 4.3 implies the SPMD dual update has a convergence bound smaller than projected SGD by a factor of order 1/(|ν0-ν*| e^{ν*-c0}); for problems with large optimal dual ν*, that is exponentially better.
  • The lower bound in Appendix E shows the dependence on κ=E[e^{2s}]/(E[e^s])² is unavoidable for black-box dual algorithms, so the tuned SPMD rate O(κ/T) is near-optimal.
  • Recovering biased SGD as α=∞ and compositional SGD as α_t=γ'e^{-ν_t} means the unified analysis yields an improved O(1/ε²) complexity for compositional SGD on Log-E-Exp as a direct corollary.
  • Empirically, the same algorithm reports lower loss than six baselines on extreme classification and partial AUC benchmarks, and matches or exceeds them on CLIP training and distributionally robust optimization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: if the rate holds even outside the strict bounded-score assumption—for instance under weight decay or projection that keeps logits bounded—the same mirror geometry could be applied to any log-partition objective, such as energy-based models, tilted ERM, and listwise ranking losses.
  • Editorial inference: the closed-form dual update is a numerically stable 'soft normalization' that could replace temperature-scaled softmax in nonconvex deep networks; the paper's theory does not cover that nonconvex regime, so this is a testable extension.
  • Editorial inference: the SPMD/SGD comparison suggests that Euclidean updates are the wrong geometry for exponential-family objectives; a broader prediction is that Bregman divergences tied to the conjugate of the log-partition will systematically reduce variance in other stochastic fixed-point algorithms.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper introduces SCENT, a stochastic algorithm for compositional entropic risk minimization (CERM), based on the dual min-min formulation in Eq. (4). The dual variable is updated by a stochastic proximal mirror descent (SPMD) step with Bregman divergence induced by φ(ν)=e^{-ν}, which yields a closed-form update and avoids exponential overflow. For convex problems satisfying Assumption 3.2, Theorem 3.6 claims an O(1/√T) convergence rate for the primal CERM gap. The paper also studies the variance terms, compares SPMD with projected SGD for a fixed dual problem, proves a distribution-free lower bound in a restricted oracle model, and reports experiments on extreme classification, partial AUC, CLIP, and KL-regularized DRO.

Significance. If Theorem 3.6 is valid under its stated assumptions, the paper makes a useful contribution: it gives a single-loop stochastic algorithm with an O(1/√T) rate for convex Log-E-Exp/CERM objectives, a rate that existing compositional optimization analyses often fail to achieve. The closed-form SPMD update and the explicit recovery of BSGD and SCGD as special cases of the framework are elegant and likely to be useful. The variance analysis in Section 4 and the matching lower/upper bounds in Appendix E are also valuable. However, the central theorem is conditional on boundedness and convexity assumptions that are not satisfied by several of the paper's own motivating experiments, which is a substantive gap in the current submission.

major comments (3)
  1. [§3, Theorem 3.6 and Lemma 3.3] Theorem 3.6 is conditional on Assumption 3.2(ii), s_i(w;ζ)∈[c0,c1] for all w∈W, ζ, and on convexity of s_i. This assumption is not satisfied by the paper's own XC setup. Appendix A.1 explicitly takes W=R^d for the Log-E-Exp formulation. For the multi-class linear model in Eq. (2), s_i(w;ζ)=h(x_i)^T(w_ζ−w_yi) is unbounded above on R^d unless h(x_i)=0. The proof of Lemma 3.3 uses the boundedness of s_i to keep ν_i,t in [c0,c1] and to make the variance terms σ_t^2 and δ_t^2 finite; without boundedness those variance terms are not controlled, and the O(1/√T) bound does not follow. Algorithms 3–6 use unconstrained SGD/Adam updates for w with no projection, so the flagship XC experiments are not covered by Theorem 3.6. The paper should either impose and enforce a bounded primal domain (e.g., projection or weight clipping) and verify explicit c0,c1, or restrict the theorem to bounded convex ins
  2. [§5, Appendix F.2 (CLIP training)] Theorem 3.6 assumes that s_i(·;ζ) is convex for every ζ. In the CLIP/contrastive experiments (Appendix F.2), the score depends on a deep encoder h(x) and h(y), so s_i is nonconvex. Thus the central convergence guarantee does not apply to those experiments. The same caveat is stated in the theory, but the abstract and introduction present the CLIP experiments as part of the empirical demonstration of 'consistently outperforms existing baselines.' If nonconvex results are to remain, the paper needs either a nonconvex convergence analysis or an explicit statement that those experiments are heuristic extensions; the current framing overstates the theoretical coverage.
  3. [§5.1, §5.2, Table 1, Figure 7] The empirical claim that SCENT 'consistently outperforms existing baselines' is stronger than the reported data. In Table 1, on Abalone with τ=0.2, SCENT attains 13.664 (0.152), while SCGD attains 10.476 (0.043) and U-max 10.951 (0.065); SCENT is not the best method in that row. The CLIP results in Figure 7 are described in Appendix F.2 as 'similar or slightly better.' The claim of consistent superiority should be softened to match the evidence, and the paper should report the metrics used for the XC and pAUC comparisons rather than only loss curves.
minor comments (4)
  1. [Eq. (7) and Algorithm 1] There are minor notation inconsistencies: ν_t vs ν_i,t in the SPMD update, and the dependence of α_t on the previous ν iterate is not explicit in the algorithm box. Clarifying the exact step-size choice in the pseudocode would improve reproducibility.
  2. [Figures 2–7] Several figures are hard to read because the curves overlap and error bars are not clearly distinguishable; adding separate panels or a zoomed inset would help.
  3. [Theorem 3.6 statement] The constant V is defined only in the remark after the theorem; it would be clearer to define it before the display.
  4. [Appendix E] The lower-bound oracle model is restrictive: it assumes the algorithm can access only value/gradient oracle queries of the form Φ(ν;ζ). This is fine, but the paper should state explicitly that the lower bound applies to that oracle model and not to all possible algorithms for the original CERM problem.

Circularity Check

0 steps flagged

No significant circularity: the algorithm, its convergence bound, and the experiments are derived from stated assumptions and external benchmarks rather than from the target result.

full rationale

The paper's central claim, Theorem 3.6, is proved from Assumption 3.2 via self-contained lemmas (Lemmas 3.3–3.5 and their appendix proofs) that do not presuppose the target convergence bound. The dual reformulation (4) is an independent classical identity (Ben-Tal & Teboulle 1986), and the SPMD update (5)–(6) is derived by proximal mirror descent, not chosen to force the final rate. The variance terms σ_t^2 and δ_t^2 are defined from the stochastic estimators and bounded under Assumption 3.2, and the step-size choice α_t = α/√T is made before the regret bound is telescoped, not fitted to the final result. The paper's self-citations (e.g., to FastCLIP/NeuCLIP, Yuan et al., Zhu et al., Wang & Yang) provide context and baselines but are not load-bearing for Theorem 3.6; the proof is in the appendix and relies only on stated convexity and boundedness assumptions. The empirical comparisons are against external methods on public datasets. Although Assumption 3.2(ii) may not hold for the unbounded linear-model XC implementation or for nonconvex CLIP/DRO losses, that is a correctness/scope concern about assumption verification, not a circularity of the derivation chain. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no result is equivalent to its inputs by construction.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 0 invented entities

The central claims rest on standard convex-analysis tools plus the domain assumptions listed. No new entities are introduced. The algorithm's step sizes are user-chosen hyperparameters and are not fitted to the target objective.

free parameters (3)
  • dual step-size scale alpha = tuned per experiment (e.g., e^10 to e^30 in XC; e^{-40} to e^{-5} in pAUC)
    Controls the SPMD step; enters all bounds as a constant multiplier and affects the final convergence constant.
  • primal step-size scale eta = implicit via learning-rate tables (lr values)
    In theory eta_t = eta * alpha_t; in practice the learning rate for w. Appears in the first term of the bound.
  • minibatch size B = 128 (XC), 64 (pAUC), 100 (DRO)
    Appears in the D_phi term of Theorem 3.6 and in the stochastic estimators.
axioms (4)
  • domain assumption s_i(.; zeta) is convex and differentiable, s_i(w; zeta) in [c0,c1], and E||nabla s_i(w_t, zeta)||^2 <= G^2
    Assumption 3.2; used in Lemma 3.3 and Theorems 3.6/B.7 to bound nu_t and the variance terms.
  • domain assumption E[z^2]/(E[z])^2 <= kappa and bounded stochastic gradient of F_CERM
    Assumption 4.1; used to control delta_t^2 and sigma_t^2 in Lemma 4.2.
  • domain assumption s(zeta) is sigma^2-subgaussian
    Assumption E.5; used for the matching upper bound in Theorem E.10.
  • standard math Classical dual/min-min identity log E[e^s] = min_nu E[e^{s-nu}] + nu
    Ben-Tal & Teboulle (1986); the problem is defined via this equivalence.

pith-pipeline@v1.3.0-alltime-deepseek · 41579 in / 14537 out tokens · 148971 ms · 2026-08-03T05:11:52.555538+00:00 · methodology

0 comments
read the original abstract

This paper studies optimization for a family of problems termed $\textbf{compositional entropic risk minimization}$, in which each data's loss is formulated as a Log-Expectation-Exponential (Log-E-Exp) function. The Log-E-Exp formulation serves as an abstraction of the Log-Sum-Exponential (LogSumExp) function when the explicit summation inside the logarithm is taken over a gigantic number of items and is therefore expensive to evaluate. While entropic risk objectives of this form arise in many machine learning problems, existing optimization algorithms suffer from several fundamental limitations including non-convergence, numerical instability, and slow convergence rates. To address these limitations, we propose a geometry-aware stochastic algorithm, termed $\textbf{SCENT}$, for the dual formulation of entropic risk minimization cast as a min--min optimization problem. The key to our design is a $\textbf{stochastic proximal mirror descent (SPMD)}$ update for the dual variable, equipped with a Bregman divergence induced by a negative exponential function that faithfully captures the geometry of the objective. Our main contributions are threefold: (i) we establish an $O(1/\sqrt{T})$ convergence rate of the proposed SCENT algorithm for convex problems; (ii) we theoretically characterize the advantages of SPMD over standard SGD update for optimizing the dual variable; and (iii) we demonstrate the empirical effectiveness of SCENT on extreme classification, partial AUC maximization, contrastive learning and distributionally robust optimization, where it consistently outperforms existing baselines. Code is available at https://github.com/Optimization-AI/SCENT.

Figures

Figures reproduced from arXiv: 2602.02877 by Bokun Wang, Chih-Jen Lin, Linli Zhou, Tianbao Yang, Xiyuan Wei.

Figure 1
Figure 1. Figure 1: Ratio between the error of SPMD and that of SGD when trained on Gaussian noise with different means and variances. SGD in a controlled synthetic data setting where s(ζ) ∼ N (µ, σ2 ). We vary µ, σ and compare the convergence error of SPMD and SGD in [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a): Cross-entropy loss curves of different methods on the training set (left) and validation set (right) of Glint360K. (b): Cross-entropy loss curves of different methods on the training set (left) and validation dataset (right) of TreeOfLife-10M. 0 20 40 Epoch 5 10 Val Loss BSGD ASGD ASGD (Softplus) U-max SOX SCENT 0 20 40 60 Epoch 0.900 0.925 0.950 0.975 Train Loss 0 20 40 60 Epoch 0.80 0.85 0.90 0.95 T… view at source ↗
Figure 3
Figure 3. Figure 3: Training loss curves of different methods for partial AUC maximization. (a): on the dataset CIFAR-10 with τ = 0.05 (left) and τ = 0.1. (b): on the dataset CIFAR-100 with τ = 0.05 (left) and τ = 0.1. also include results using the momentum optimizer for the model parameter w with similar results as discussed below. Results. We present the cross entropy loss value curves on the training data and validation d… view at source ↗
Figure 4
Figure 4. Figure 4: (a): cross-entropy loss of different methods on the training set (left) and validation dataset (right) of Glint360K, using SGD with momentum optimizer. (b): cross-entropy loss of different methods on the training set (left) and validation dataset (right) of TreeOfLife-10M, using SGD with momentum optimizer. 0 20 40 Epoch 5 10 Val Loss BSGD ASGD ASGD (Softplus) U-max SOX SCENT 0 20 40 60 Epoch 0.900 0.925 0… view at source ↗
Figure 5
Figure 5. Figure 5: Training loss curves of different methods using SGD with momentum optimizer for partial AUC maximization. (a): on the dataset CIFAR-10 with τ = 0.05 (left) and τ = 0.1. (b): on the dataset CIFAR-100 with τ = 0.05 (left) and τ = 0.1. Comparison between SGD and SPMD with fixed w. In [PITH_FULL_IMAGE:figures/full_fig_p030_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Error between νt and ν∗ when trained using different methods on Gaussian noise with different mean (top to bottom: µ = −1.0, −10.0) and standard deviation (left to right: σ = 0.1, 0.3, 1.0) F.2. CLIP Training We apply our method to image-text representation learning task, namely CLIP (Radford et al., 2021). Given a dataset of image-text pairs S = {(x1, y1), . . . ,(xn, yn)}, CLIP aims to train a model h (p… view at source ↗
Figure 7
Figure 7. Figure 7: Zero-shot evaluation performance of different methods trained on DFN-14M. Left: ImageNet-1K top1 accuracy. Middle: Retrieval recall. Right: Datacomp average performance. F.3. KL-Regularized Distributionally Robust Optimization We also consider KL-regularized distributionally robust optimization problem. Specifically, we consider linear regression task on a dataset S = {(x1, y1), . . . ,(xn, yn)}: min a∈Rd,… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 1 canonical work pages

  1. [1]

    The functionu7→ϕ(u) +ϕ(u−∆)is convex and its minimizer lies in[0,∆]

    =ϕ(u) +ϕ(u−∆). The functionu7→ϕ(u) +ϕ(u−∆)is convex and its minimizer lies in[0,∆]. Since∆≤1, applying Lemma E.2 gives ϕ(u) +ϕ(u−∆)≥ e−1 4 ∆2. Therefore, inf ν (F0(ν)−F 0(νε 0)) + (F1(ν)−F 1(νε 1)) ≥ e−1 4 ∆2.(40) Next, we show the total variation between P ε 0 , and P ε 1 is bounded. Because the two distributions differ only in the Bernoulli parameter, K...

    2000

  2. [2]

    doi: 10.4230/DagRep.8.7

    ISSN 2192-5283. doi: 10.4230/DagRep.8.7

    work page doi:10.4230/dagrep.8.7

  3. [7]

    information available

    URL https://proceedings.neurips. cc/paper_files/paper/2019/file/ 3eefceb8087e964f89c2d59e8a249915-Paper. pdf. Wang, M., Fang, E. X., and Liu, H. Stochastic composi- tional gradient descent: algorithms for minimizing com- positions of expected-value functions.Mathematical Pro- gramming, 161(1):419–449, 2017. Wang, T. and Isola, P. Understanding contrastive...

    Pith/arXiv arXiv 2019

  4. [8]

    TX t=1 αt(F(w t, νt)−F(w ∗, ν∗)) # ≤ 1 2η ∥w1 −w∥ 2 2 +D φ(ν∗, ν0) +E

    When w=w ∗, we have wt+1,w ∗ ∈ W, and thusr(wt+1) =r(w ∗) = 0. Rearranging the terms, we get ∇wΦ(wt, νt;ζ ′ t)⊤(wt −w ∗) ≤ 1 2ηt ∥w∗ −w t∥2 2 − 1 2ηt ∥w∗ −w t+1∥2 2 − 1 2ηt ∥wt+1 −w t∥2 2 +∇ wΦ(wt, νt;ζ ′ t)⊤(wt+1 −w t) ≤ 1 2ηt ∥w∗ −w t∥2 2 − 1 2ηt ∥w∗ −w t+1∥2 2 − 1 2ηt ∥wt+1 −w t∥2 2 + ηt 2 ∥∇wΦ(wt, νt;ζ ′ t)∥2 2 + 1 2ηt ∥wt+1 −w t∥2 2, where the last i...

  5. [62]

    Chen, T., Kornblith, S., Norouzi, M., and Hinton, G

    URL http://drops.dagstuhl.de/opus/ volltexte/2019/10173. Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual rep- resentations. InInternational conference on machine learning, pp. 1597–1607. PmLR, 2020. Chen, X., Fang, H., Lin, T.-Y ., Vedantam, R., Gupta, S., Doll´ar, P., and Zitnick, C. L. Microsoft...

    Pith/arXiv arXiv 2019

  6. [2019]

    cc/paper_files/paper/2019/file/ 97af07a14cacba681feacf3012730892-Paper

    URL https://proceedings.neurips. cc/paper_files/paper/2019/file/ 97af07a14cacba681feacf3012730892-Paper. pdf. Ben-Tal, A. and Teboulle, M. Expected utility, penalty functions, and duality in stochastic nonlinear program- ming.Management Science, 32(11):1445–1466, Novem- ber 1986. doi: 10.1287/mnsc.32.11.1445. URL https: //doi.org/10.1287/mnsc.32.11.1445. ...

    doi:10.1287/mnsc.32.11.1445 2019

  7. [2020]

    ISBN 3-030-39568-5

    edition, 2020. ISBN 3-030-39568-5. Levy, D., Carmon, Y ., Duchi, J. C., and Sidford, A. Large- scale methods for distributionally robust optimization. Advances in neural information processing systems, 33: 8847–8860, 2020. Li, T., Beirami, A., Sanjabi, M., and Smith, V . Tilted empir- ical risk minimization.arXiv preprint arXiv:2007.01162, 2020. Lin, L.-C...

    Pith/arXiv arXiv 2020

  8. [2025]

    Liu, B., Rosenfeld, E., Ravikumar, P., and Risteski, A

    URL https://openreview.net/forum? id=xtKNbPTnMA. Liu, B., Rosenfeld, E., Ravikumar, P., and Risteski, A. Ana- lyzing and improving the optimization landscape of noise- contrastive estimation.arXiv preprint arXiv:2110.11271, 2021. Loshchilov, I. and Hutter, F. Decoupled weight decay reg- ularization. InInternational Conference on Learning Representations, ...

    Pith/arXiv arXiv 2021

  9. [8856]

    Qiu, Z.-H., Hu, Q., Zhong, Y ., Zhang, L., and Yang, T

    URL https://openreview.net/forum? id=B0WYWvVA2r. Qiu, Z.-H., Hu, Q., Zhong, Y ., Zhang, L., and Yang, T. Large-scale stochastic optimization of ndcg surrogates for deep learning with provable convergence.arXiv preprint arXiv:2202.12183, 2022. Qiu, Z.-H., Hu, Q., Yuan, Z., Zhou, D., Zhang, L., and Yang, T. Not all semantics are created equal: Contrastive s...

    Pith/arXiv arXiv 2022