acceptodds
Under review as a conference paper at ICLR 2027

Biased Stochastic Gradient for the Log-Softmax Loss

Abstract

The log-Softmax loss is widely used in machine learning, but computing its gradient can be expensive when the number of classes is large. Class sampling reduces this cost, but also raises the concern of bias: whether, after class sampling, the expectation of the stochastic gradient equals the full gradient. Such stochastic gradients have generally been suspected to be biased, but a formal proof has long been missing. Recently, Lin et al. (2025) made an important step toward resolving this question by proving that no estimator based on only a subset of class logits can estimate the full Softmax probability without bias. However, their result concerns Softmax estimation at the logit level only, rather than the gradients with respect to model parameters. Moreover, they only consider class sampling for a fixed training instance, whereas stochastic training involves both instance sampling and class sampling. These differences show that the unbiasedness question itself must be stated more carefully, including which stochastic gradient is considered and which sources of randomness are averaged over. Our first contribution is a proper definition of the unbiasedness of the stochastic gradient for the log-Softmax loss by taking the model, data, parameter values, sampling procedures, and the randomness over expectation into account. With the proposed definition, our second contribution is to formally prove that, for the log-Softmax loss, no universal estimator can ensure unbiased stochastic gradients under class sampling.

Primary area:
optimization
Keywords:
Log-Softmax, Negative Sampling, Extreme Classification, Stochastic Gradient Bias

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_7Gu2OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper theoretically proves that the stochastic gradients of log-softmax loss with class sub-sampling are biased. For the case of large-scale class categories in classification tasks, it is an efficient approach to draw a subset of classes to attend a softmax cross-entropy loss. Based on the theoretical result about softmax [Lin+25], the stochastic gradients w.r.t model parameters for the class-subset softmax loss on mini-batch sampling are proven to be biased, through detailed definition of gradient biasedness. The paper also discusses the extension to this theoretical consequence toward loss functions built upon log-sum-exp functions.

Critical strengths
  • In a large-scale classification scenario, class-subset sampling plays a pivotal role for efficient learning. Thus, biasedness of the stochastic gradients addressed in this paper is important for analyzing and further sophisticating optimizers.
Critical weaknesses
  • Theoretical novelty is limited. The main claim, Theorem 3.4, is straightforward (trivial) extension from [Lin+25]; biased loss gradients [Lin+25] convey biased parameter gradients in an obvious way.
  • It is hard to find novelty or theoretical effectiveness from Definitions 3.1-3.3, though the authors insist that ours may be the first to give a formal and complete definition in line 347. It sounds quite standard to me.
  • Most discussions are theoretically not surprising or less clear. Specifically, the weak points of the prior works [Lin+25, Bengio+08, Blanc+18] discussed in this paper are not clear, though the authors aggressively argue them.
Questions for authors
  • Please clarify theoretical novelty in comparison to the prior works such as [Lin+25] through clearly pointing out the issues in those works that this paper addresses.
1 comment

We thank the reviewer for the comments.

For W1

Theorem 3.4 does not follow directly from Lin et al. (2025). Their result concerns logits, while ours concerns model parameters. As explained in our response to Reviewer jTZ9 (Weakness 1), biased logit gradients do not necessarily imply biased parameter gradients.

For W2

Although unbiasedness is a standard concept, its precise definition matters for our existence question. In particular, the order of quantifiers determines whether we require one estimator to be unbiased for all settings or allow a different estimator for each setting. These are different theoretical claims. Please see our response to Reviewer jTZ9 (Weakness 2).

For W3

Our intention is not to question the correctness of previous results, but to clarify their scope.

In particular, both Lin et al. (2025) and Blanc and Rendle (2018, Theorem 2.1) study the unbiasedness condition for logits but not directly for parameter gradients. Bengio and Sénécal (2008) show that their proposed parameter-gradient estimator is biased, but do not establish the impossibility of universal unbiasedness or provide a formal definition for this existence question.

For more discussion on related works, please see our response to Reviewer GxEF (Weakness 1). We will revise our discussion on prior works.

Reviewer_GxEFOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This work mainly focuses on stochastic gradients of the log-Softmax Loss under sampling methods. It establishes qualitative results that no universal estimator can unbiasedly estimate the full-softmax loss gradient across all models, datasets, and parameters. Its main results build on Lin et al. (2025) through a reduction, extending from probability estimation to model gradient estimation.

Critical strengths

The paper focuses on whether negative sampling preserves gradient unbiasedness in large-class scenarios, which is a significant question which is relevant to real-world applications such as information retrieval or recommender systems.

Critical weaknesses
  1. The paper relies heavily on Lin et al. (2025), while the related-work discussion almost solely focuses on distinguishing the present result from that paper. However, several other closely related studies [1–4] have also examined sampled-softmax. In particular, [1] already analyze gradient bias w.r.t. model parameters. The authors should compare their main contributions with these works beyond extending Lin et al.’s result. A broader discussion in Related Work would help establish the paper’s identity as an independent contribution.

  2. The theoretical results are qualitative, which do not quantify the unavoidable bias or characterize its dependence on the sampling protocols. As a result, their implications for practical sampling design remain unclear. Considering the widespread use of negative sampling in large-scale applications, the paper should provide a more detailed discussion on how its results can inform practical model design, which would improve the paper’s practical relevance.

[1] Rawat, Ankit Singh, et al. "Sampled softmax with random fourier features." Advances in Neural Information Processing Systems 32 (2019). [2] Rawat, Ankit Singh, et al. "Disentangling sampling and labeling bias for learning in large-output spaces." International conference on machine learning. PMLR, 2021. [3] Chen, Jin, et al. "Adaptive sampled softmax with inverted multi-index: Methods, theory and applications." arXiv preprint arXiv:2501.08563 (2025). [4] Pu, Yuanhao, et al. "Is Softmax Loss All You Need? A Principled Analysis of Softmax-family Loss." arXiv preprint arXiv:2601.22745 (2026).

Questions for authors

I have no questions regarding the correctness of the paper, but I would appreciate further discussions or analysis addressing the two listed points raised in Weakness.

1 comment

We thank the reviewer for pointing out these related works.

For W1

For the difference from Lin et al. (2025), please see our response to Reviewer jTZ9 (Weakness 1).

Rawat et al. (2019) and Chen et al. (2025) study the bias of specific sampled softmax estimators, providing bounds for the bias. However, these bounds do not rule out zero bias. Both works also cite Blanc and Rendle (2018, Theorem 2.1) to establish the existence of bias, but this theorem concerns gradients with respect to logits, not model parameters. As explained in our response to Reviewer jTZ9, biased logit gradients do not necessarily imply biased parameter gradients.

In contrast, we ask a different question: Does there exist an estimator that guarantees unbiased parameter gradients for all models, datasets, and parameter values?

In addition, Rawat et al. (2021) and Pu et al. (2026) focus more on the properties of loss functions and their approximations, rather than the unbiasedness of parameter-gradient estimators.

We will clarify these differences in the revision.

For W2

Our work focuses on whether a universally unbiased estimator exists, rather than how large the bias is.

Our result shows that no estimator within the considered class can guarantee unbiased parameter gradients in every setting. This complements previous work on measuring and reducing bias. Since unbiasedness cannot be guaranteed universally, understanding and controlling bias becomes even more important in practice.

We will clarify this implication in the revision.

Reviewer_jTZ9OpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies whether stochastic gradients for the log-Softmax loss can be unbiased when only a subset of classes is sampled. It first provides a formal definition of unbiasedness that accounts for the model, training data, parameter values, and both instance and class sampling. The main result shows that no estimator of the considered form can be universally unbiased. The proof reduces the problem to the impossibility of unbiased Softmax estimation established by Lin et al. (2025), using a model in which only one logit depends on a scalar parameter. The paper also extends the impossibility result to log-sum-exp objectives.

Critical strengths

The paper makes a reasonable distinction between estimating Softmax probabilities and estimating gradients with respect to model parameters. The main result is clearly stated, and the proof is easy to follow.

Critical weaknesses
  • My main concern is the very limited novelty and technical contribution. Theorem 3.4 follows almost immediately from Lin et al. (2025) by considering a single training instance and a model in which only the positive logit depends on a scalar parameter. Under this construction, unbiased stochastic gradient estimation reduces exactly to unbiased Softmax estimation. I find this reduction quite elementary. The extension to log-sum-exp follows essentially the same argument and adds little technical depth.

  • I am not convinced that the proposed definition of unbiasedness constitutes a substantial contribution. The definition is useful in making the relevant quantifiers and sources of randomness explicit, but it largely formalizes the standard unbiased-gradient condition for the setting considered here. Moreover, although the paper emphasizes the complexity introduced by jointly considering instance and class sampling, the main proof immediately reduces to a single training instance, making instance sampling irrelevant to the impossibility argument.

Questions for authors
  • Could the authors clarify what they consider the main technical novelty beyond Lin et al. (2025)? The proof of Theorem 3.4 seems to be a direct reduction to their existing impossibility result through a simple choice of model. Is there a more substantial difficulty or insight that I am missing?

  • What additional insight does Definition 3.3 provide beyond explicitly specifying the quantifiers and sources of randomness? In particular, given that the proof reduces immediately to a single training instance, I am not sure why jointly considering instance and class sampling is essential to the contribution.

2 comments

We thank the reviewer for the constructive comments. We agree that the reduction in Theorem 3.4 is simple. However, extending Lin et al. (2025) from logits to model parameters is not straightforward.

For W1 and Q1

Logit-level bias does not necessarily imply parameter-gradient bias.

Consider

\begin{pmatrix}\theta \\\\ \\theta\end{pmatrix}, \qquad L=\frac12(\hat y_1-1)^2+\frac12\hat y_2^2.$$ Suppose the true and expected estimated logit gradients are $$\boldsymbol g= \begin{pmatrix}\\hat y_1-1 \\\\ \\hat y_2 \end{pmatrix}, \qquad \mathbb E[\hat{\boldsymbol g}]= \begin{pmatrix}\\hat y_1 \\\\ \\hat y_2-1\end{pmatrix}.$$ The logit-gradient estimator is biased for every $\theta$, since $$E[\hat{\boldsymbol g}]-\boldsymbol g = \begin{pmatrix}1 \\\\ -1\end{pmatrix} \ne\boldsymbol 0.$$ However, the corresponding parameter-gradient estimator is unbiased: $$\mathbb E\left[ \frac{d\hat{\boldsymbol y}}{d\theta}^{\top} \hat{\boldsymbol g} \right] =2\theta-1 =\frac{dL}{d\theta}, \qquad \forall\theta\in\mathbb R.$$ Thus, bias in logit gradients does not necessarily imply bias in parameter gradients. Our main contribution is to establish an impossibility result for parameter gradients that is not established by Lin et al. (2025), rather than to develop a complicated reduction. **For W2 and Q2** Although unbiasedness is a standard concept, defining it precisely for an existence question requires care. For example, consider: - **Statement A:** $\exists s,\ \forall D,\mathcal M,\theta$, $s$ is unbiased. - **Statement B:** $\forall D,\mathcal M,\theta,\ \exists s$, $s$ is unbiased. Statement A requires a universal unbiased estimator, while Statement B allows a different estimator for each setting. **A implies B, but not conversely.** This illustrates why specifying the settings and quantifier order in Definition 3.3 is important: confusing them would change the theoretical claim. Our theorem covers both instance and class sampling, which allows us to formulate the result for stochastic training in practice. Since our theorem rules out universal unbiasedness, a single-instance counterexample is sufficient. This does not limit the generality of the result. We will clarify these points in the revision.

I thank the author for the response. I am not convinced of the novelty and technical contribution of the paper, and this concern is shared by other reviewers. I will maintain my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.