Sampled Estimators For Softmax Must Be Biased
Authors: Li-Chung Lin
Yaxu Liu
Chih-Jen Lin
Venue: NeurIPS 2025 poster ()
Keywords: Softmax
Negative Sampling
Extreme Classification
Primary area: general_machine_learning

Abstract: Models requiring probabilistic outputs are ubiquitous and used in fields such as natural language processing, contrastive learning, and recommendation systems. The standard method of designing such a model is to output unconstrained logits, which are normalized into probabilities with the softmax function. The normalization involves computing a summation across all classes, which becomes prohibitively expensive for problems with a large number of classes. An important strategy to reduce the cost is to sum over a sampled subset of classes in the softmax function, known as the sampled softmax. It was known that the sampled softmax is biased; the expectation taken over the sampled classes is not equal to the softmax function. Many works focused on reducing the bias by using a better way of sampling the subset. However, while sampled softmax is biased, it is unclear whether an unbiased function different from sampled softmax exists. In this paper, we show that all functions that only access a sampled subset of classes must be biased.
With this result, we prevent efforts in finding unbiased loss functions and validate that past efforts devoted to reducing bias are the best we can do.

Sampled Estimators For Softmax Must Be Biased
Li-Chung Lin National Taiwan University r08922141 @ntu. edu. tw
Yaxu Liu"
National Taiwan University d08944045éntu, edu.. tw Mohamed bin Zayed University of Artificial Intelligence yaxu www.miiuummiaacccco
Chih-Jen Lin
National Taiwan University
cj cjlin@csie ntu. edu. Mohamed bin Zayed University of Artificial Intelligence chihjen. lin@mbzuai. ac. ac.
Abstract
Models requiring probabilistic outputs are ubiquitous and used in fields such as nat- ural language processing, contrastive learning, and recommendation systems. The standard method of designing such model is to output unconstrained logits, which are normalized into probabilities with the softmax function. The normalization involves computing summation across all classes, which becomes prohibitively expensive for problems with a large number of classes. An important strategy sampled subset of classes in the softmax function,
reduce the cost is to sum known as the sampled softmax. was known that the sampled softmax is biased; the expectation taken over the sampled classes is not equal to the softmax function. Many works focused on reducing the bias by using a better way of sampling the subset. However, while sampled softmax is biased, it is unclear whether unbi- ased function different from sampled softmax exists. In this paper, we show that all functions that only access sampled subset of classes must be biased. With this result, we prevent efforts in finding unbiased loss functions and validate that past efforts devoted reducing bias the best do.
Introduction
Training losses based on the softmax function extensively used across various fields, e.g., natural language processing 12 13 [7 contrastive learning 4, and recommendation systems [6] 22]. The most common loss is to take the log of the softmax function, known the log-softmax or cross-entropy loss
L(O+.00 97
Dn = log Softmax(O*, 1T ....), 0,
In this loss, the softmax function gives the probability of class by
e0+
Softmax (ÿ* . ......... in.
est
En ed,
where j+ E IR. is the logit of the target class, 0f E RR for every < i S n are the logits of all negative classes, and there are + total classes. By summing this loss over all training data, we obtain the overall learning objective.
Work mainly done while visiting Mohamed bin Zayed University Artificial Intelligence.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

One typically employs gradient methods to train machine learning models. At each training step, the gradient of sog-softmax must be calculated, leading to the following partial derivatives"
log Softmax ......., Dn Softmax ........ ..... 0%
(2)
aÿ* +
and for every 1 S
log Softmax(ý" .......,,
mn) -Softmax((; ..... . 17
D141.... Bnn)
(3)
Both the loss and gradient computations inevitably rely on the softmax function. The denominator in (T) sums over logits for all negative classes, leading to a computational cost of ((n) for each calculation. This cost can become prohibitively expensive when training models on datasets with a large number of classes. A typical example involves recommendation systems, like [22], in which the size of ni can reach millions. In addition to the (n)) computational complexity of the denominator, evaluating (1) requires computing all logits, y When using large neural networks such as BERT [9. computing all n logits can become prohibitively expensive.
As shown in 22 intuitive idea to reduce the computation cost is sample a subset of k classes for loss calculation, and < n typically. An important scenario the stochastic gradient descent method, where each training step involves mini-batch of data, and within each batch only the sampled & classes are used to compute the stochastic gradient. That is, we use only & sampled classes in calculating 2 and (3), where widely used setting consider the following sampled softmax:
(4)
e + EJ= w(i;)e
where 1 classes (f1,..., ix) are randomly sampled from the n classes and w((i) ( is weighting term inversely proportional to the probability of sampling the i,th sampled class (2] In contrast, represents the full softmax, which involves all n + classes.
To ensure equivalence with training model using the full softmax, it is desirable for the sampled softmax to satisfy the condition of unbiasedness. Specifically, this condition is defined as follows:
Vøt 01 ................................ 0% E R, E [Stochastic Gradient]
Full Gradient.
When applying this condition implies that
VØ* 91 --.- Dn IR E
where EE [-] denotes the expectation over the sampled classes (ii,..., iz). If this condition does not hold, we consider that (4) biased with respect (I). The different gradients are potentially harmful to the optimization process and solutions. Unfortunately, previous works like [2] 3 have already demonstrated that 66) does not hold, highlighting the inherent bias of the sampled softmax. Moreover, experiments in [3 16 have demonstrated that bias degrades model performance in tasks such as multi-label classification and content recommendation.
The bias of sampled softmax leads us to wonder whether, beyond ) there could be other forms of approximation that are unbiased. In this paper, show that any general function with access subset of logits must be biased. Specifically, when & < n, let
S+ = :R* p++1 R}
denote the of all real-valued functions of 6: + real inputs, which covers all possible estimators operating on one positive logit and ls sampled negative logits. Then,
Vs E Sk. 3タ+ DT ......... D E R, s.t. E [(("* 10, .........
+
where it classes (i) .i....., i are randomly sampled from the n classes. In other words, there is no estimator 8 satisfying the unbiased condition for every possible set of n. logits when s has access to only à < n logits. By extending from the sampled softmax any general function s, this conclusion generalizes the finding of 3 and forms our main contribution. Our negative answer to the existence
"The detailed proof is given in Appendix A

---

Table 1: Notation
Notation
Description
7
Number of classes excluding the target
y E
R
Logit of the target class
V1 1...1
In E R
Logits of the remaining classes
Number of sampled classes Set of positive integers up to
(r] (1
S,
Set of permutations on [r]
g!
Number of combinations of r items chosen from q items
r r)
1 {a E R
0}
Set of positive real numbers Estimator taking l arguments The symmetrization of h3
hg : R +
fk
R
+ R
of unbiased approximations establishes theoretical boundary what is and is not achievable. Our result not only fills a notable gap in the literature but also sets clear limits for future research directions.
The remainder of this paper is organized as follows: In Section we summarize related works. In Section 3 we formally define the problem we aim to address and then state the main results of this work and our assumption. Section 4 starts with preliminaries in Section 4.1 that provide the necessary background and lemmas. followed by sketch of the proof in Section 4.2] The detailed proof is presented in Sections|4.3 and Appendix E Finally, Section[5joonluude the paper. The main notations used in this work are in Table and the appendix is available hhtps hailiin/paper/sooot sooferrs/oooio tmax_ biased/
7/www. csie. ntu. edu. /t/////////////eeee//e
Related Works
Prior efforts all implicitly assume that an unbiased solution does not exist without attempting to justify or challenge it. They can be roughly categorized into three directions.
Focusing on the sampled softmax (4) and attempting to minimize its bias. While 3 demon- strated that the inherent bias in the sampled softmax cannot be completely eliminated, they proposed a strategy to minimize this bias. Specifically, the closer the sampling distribution used for selecting (i1,.... (x)) approximates the full softmax, the less biased the sampled softmax becomes. To this end, [3] and its follow-up study [16] developed computationally efficient approximations for sam- pling. Additionally, numerous hard negative mining strategies have been widely adopted alongside the sampled softmax, such as those used in representation learning [21 20, 77. Hard negatives refer
to negative classes that produce large gradients when used in the sampled log-softmax loss:
llg
This setting effectively involves sampling negatives based their corresponding logits. Further- more, studies like [24] have argued that an effective hard negative mining method should be based on a good approximation of the full softmax distribution, consistent with the ideas proposed in [3].
addition to the aforementioned approach of selecting an appropriate sampling distribution, mentioned another idea: using larger sample size & to reduce bias. However, increasing k naturally leads to higher computational cost. To address this issue, subsequent works [19 23 introduced the concept of applying moving averages over multiple mini-batches of gradients, thereby approximating the effect a large sample size while maintaining low cost.
3
Exploring alternative functions that are computationally more efficient than the full softmax (I). Works in this category generally try to avoid sampling and explore a new loss with all logits their calculation. Well-known examples include hierarchical softmax [14] and spherical softmax [8). However, reported in [8), such alternative functions may perform worse than the

---

Since these methods do not involve sampling over the classes, we do not extend our discussion to them.
full softmax I.
Designing different learning problem with the same optimal solution. In L5 10 they transform the original optimization problem involving log-softmax term in the objective function into a new optimization problem. In the transformed problem, there is no log-softmax term in the objective function. They then show that for special types of models, the transformed problem has the same optimal solution as the original problem. The equivalence of the optimal solution is what they refer as "unbiased," which is unrelated to the problem of bias discussed in this paper. While these reformulation approaches are still under development, our negative answer to directly sampling softmax indicates that they are directions worth investigation.
By proving the non-existence of an unbiased solution, our work provides theoretical boundary and serves as meaningful complement to these studies.
3 Problem Definition and Main Result
Let (i1,...,44 is) E [m]* be random variables denoting a subset of k indices sampled from [n] =
[1....,n) without replacement. We wish to find an estimator s(g , ........, vT,)) such that
e0*
E [s(]* D1
(8)
e+ + Σ== e4i
where the expectation is over (d1.....
Our main results are Theorem 3.1 and Corollary 3.3
B&++1 + RR denote the set of all real-valued functions of k real inputs. Consider the setting where (i1...., in) sampled uniformly without replacement from {I....,n.) n.), and an estimator s E Sy is applied to one positive logit ğ and the sampled negative logits (U,,..... .,,)) Then
Theorem 3.1. Let < n and St = {s
Vs Sk, 3Ø* D1 ...., In E, S. E [$ D7, ......., + Softmax (ttt .01 ...... In
where E [-] is taken over the random choice of (1)....,4).
In this work, we focus on the existence of an unbiased estimator of the softmax function for two main reasons. First, during training, what matters most is the gradient of log-softmax, as model parameters are updated through gradient-based based optimization. Second, during inference, the output of interest softmax itself, which represents the predicted probability distribution over classes. In both situations, the exact value of the log-softmax not directly required. Regardless, with Theorem 3.1 that unbiased estimator of log-softmax does not exist in Appendix
we show
After we establish that Theorem 3.1 applies for uniform sampling, we next examine whether Theorem 3.1 still holds for other ways of sampling the k classes (fi...., i An example of non-uniform sampling is [3], where the samples are the union of the target class, in-batch negative samples, and samples based on BM25 [18. In In-batch negative samples refer to using the target classes of other instances in a mini-batch as the negative classes of the current instance.
While we want to consider sampling distributions that are as general as possible, we must be careful include impractical sampling distributions. Recall that the purpose of sampled estimator is to avoid computing all n logits; using the logits as part of the sampling process defeats the entire point of sampling. Consequently, make the following assumption.
Assumption 3.2. The sampling distribution is selected before computing the logits.
An example of violating Assumption 3.2 is to use distribution where the probability of sampling each class is proportional to the exponential of its logit ext In such case, it was proven [ that the sampled softmax is an unbiased estimator. However, constructing the distribution is equivalent to computing the softmax function for each class. Clearly, if we already have the softmax function, we
Note that 4 with w(i)) be also expressed by g Details in Appendix

---

would not need to compute sampled estimator. We obviously want to exclude such distributions from consideration.
In the previous example of 13], in-batch sampling and negative sampling are both selected before computing the logits, they satisfy Assumption 3.2 Similarly, find that most works sampled softmax satisfy Assumption For the minority of exceptions 3 [6].
we give brief discussion in
Appendix D
Given Assumption 3.2 and setting s(-) to 4 respect to the full softmax,
concluded that sampled softmax is biased with
+
edit
Σタ=1 w w(t))e
e
+ Em e
In the following sections, we further extend their conclusion to any general s(.) under Assumption 3.2
Corollary 3.3. Theorem 3. also holds if the indices (f....., .a.......,, ig) are sampled from any distribution
satisfying Assumption 3.2
The proof of Corollary 3.3 is given in Appendix E
In the following proof of 7 due simplification outlined in Section 4.2 we will work with
function ly IR + IR instead of : IRk+1 + I,, but they refer to the same problem of estimating the full softmax.
4
Main Proof
In this section, we prove Theorem 3.1 We begin with necessary preliminaries and lemmas, followed by a sketch that highlights the main ideas of the proof before presenting the complete derivation.
4.1 Preliminaries
This section introduces lemmas used in the proof of the main theorem. The proofs are provided in Appendix C
Definition 4.1. Let ha R R be function and S₃ be the set of permutations [k]. The symmetrization fú of h2 is defined by
F&) = Σ
1 k!
TES
The symmetrization is so named because it is symmetric in its arguments, stated as follows. Lemma 4.2. For every a E Sk.
xx) (.
Furthermore, the symmetrization has the same expectation under uniform sample, stated follows. Lemma 4.3. Let a (a1...., an)) B be n real numbers and (i1..... ix)) [n]* be random variables denoting is indices sampled uniformly from [n] without replacement. Then
E [a ate)) E [a, ... ...)..
where the expectation over (41,...,
4.2 Sketch of Proof for Theorem
The core idea of our proof is that unbiasedness imposes a strong requirement, demanding the estimator to generalize across arbitrary cases. To illustrate this, we constructed two of the simplest yet representative cases: one where all logits are identical and another where the logits are divided
5

---

into two groups, each with distinct value. It turns out that these two minimal cases alone have already revealed set of contradictory constraints. The proof is non-trivial, as involves identifying subtle examples that clearly demonstrate the inherent contradictions.
The proof of Theorem 3.1 proceeds by contradiction, shown below:
1.
We begin by reformulating the problem of estimating the full softmax into an equivalent problem of estimating:
F(a) 1+ +==10
where (01)...;0p)) an) E RR and R200 {a E a 0).
We hypothesize the existence of an unbiased estimator h2 R for F, which accepts arguments, and uses the symmetrization f& of hą, which has the same expectation, to simplify the
derivations.
We analyze the expectation of fk across various possible values of and derive a necessary equation for each vector a that fú must satisfy to be unbiased. These equations are derived using mathematical induction.
4. Finally, we complete our proof by demonstrating that it is impossible for fa to simultancously satisfy all equations, leading to a contradiction.
Specifically, for Step 3 above, check different of the form,
(bi,... bi, b2 b2)
where bj, by E R2 and m = .,..., k.
4.3 Proof of Theorem 3.1
Proof. First, note that
eØ+
Softmax(j" :91 ...,, 11)
eăt
Σ
1
Σ
e
+
follows that there is an unbiased estimator for the full softmax for every possible model output and only if there is an unbiased estimator for F
F(a)
(10)
1+ Σ
for every (az,....
R >0
We prove by contradiction, so we assume there is an unbiased estimator hg. That is, there exists an h2 such that for every
F(a)
[hx (ai...... aia))
(11)
where (d....., ix) E [n]]* are random variables denoting indices sampled uniformly from [n] without replacement.
Next, calculate the expectation in 11 in detail. For the selection of (f1,...,4k) ik), the number of all possible samples of indices
n! ke (n --)!
which is the number of combinations of k choices from items multiplied by the number of permutations on & items. Therefore, for every function G R - RR we have
(n k))! n!!
E [G(ai,..... ai,))
Σ (EC(n) dESk
Σ
G(zo(iy...,
(12)

---

where C(n, k; a) denotes the set of (x) choices of & elements from a.
Let JE be the symmetrization of hg. Then
F(a)= = E 0g ) = fx (a (i........
aiyy
(13)
[n2 k)!
E
n!
mEC(n,k;a) oES,
(n - k)!
Σ
E
[x(
(14)
n!
(EC(n,k;a) dESt
(n - k)hk!
fe( 2k)
n!
=EC(n,k.a)
Σ
(15)
mEC(n.k:a)
where 13 follows from Lemma 4.3 and 14
follows from Lemma 4.2
We claim that for every bj E 18 we have
1
fu ................................ b1) 1 + nd1
(16)
This is because fa is unbiased for every a, including for (bi..... bi), implying
F(a) = 1 1
(17)
E [fu air
(18)
Σ
Se(bi,...,b))
(19)
(EC(n,
=fu(b....... b1).
where 11 is the definition of F in 100 18 is from
13 and 19 is from 15
Similarly, suppose a
b1, b2) for some b1, b2 E Rso. Then we have
F(a) 1 (n 1)b, + bz
E (a ................................ aive)l
1 n2
12 (-11)
(*)
b
fecbi...... fa(bb....,,bi b1) +
k 1-1 fae (6,......, .1.
...,.
(20)
k)lk!
(n 1)!
(n k)!k!
(n 1)!
(n - k))(K - 1)! Ia (b,
b2)
n!
(n - 1)!k! nnb
n!
(21)
n k
+ k n
b1, b2).
nbi
The term (²=1) 20p is the number of ways of choosing counts of b, and the term the number of ways of choosing l counts of by and count of bz. Also, in 21 we use 16). Rearranging, have
(6-1) is
(n-1
a Io (n 1)by + b2
k 1
b, b2)
+ nbi
More generally, for each m S k, if we consider
(bI..... bi, b2...., b2).

---

we find that
1
1
n m
(3) g(o),
(m)
F(a) + (n mib1 + mb2
E ain
(22)
k j
j=D
where
و(ه) = fbi bi, b2,.... b2
j = O,...,k.
(23)
and the factor (x=z) ( is the number of ways of choosing k j counts of by and j counts of by The dependence of g on n, k; by and b2 are suppressed in the notation for brevity. We prove by strong induction on that
m
c(m,1) 1) + (n 1)b1 + lb2
g(m)
m O...., k.
(24)
where
c(m,1) 1)
(25)
ifm =
n n- m k-m
m-
m k - j
(m)
(m) c(j.t)
mm
n- m
km-m
j=l
otherwise.
Likewise, the dependence of e on n and k are suppressed in the notation for brevity. For the base case,
c(0,0) 0)
((0) (b1......... b1)
+ nb
1 nb
where we respectively use (23 (16 and
c(0,0) =
11
11
(26)
k:
k
for the derivation above.
For the induction step, we split the summation in 22
to single out g(m):
I
n
m
m
(m) +
n
m
mm)
g()).
(27)
k
k
=
Rearranging 22
we have
m-
n m
m
((m)
i 9(5))
(1-m) k
m
1 (n m)hi + mbz
h:
j=0
mm1
m
m
9(f).
(28)
1 + (n m)b1 + mb
j
For the first term in 28 by the definition in 25 we have
c(m, m)
(29)
k- m7
8

---

For the second term, assuming the induction hypothesis (4) is true for all j = o..... m7 1, we have
m
n2 m
m
g(i)
k - j
M
h kー
m
Σ
c(j,1)
(30)
1 + (n - -1)b1 + lb2
m k j
(m)
c(j,))
+ (n 1)b1 lb
n m
(m)
c(i.1)
k- (
(31)
(n - 1)61 + lb2
j=l (7)(0)
1+ (n 1)b1 + lbe
c(m,1) 1)
(32)
1 1)bı + lb2
1=0
In (30 g()) is substituted with the induction hypothesis 24
31
exchanges the order of summation By replacing values in (28) with
over and and c(m, 1) in (32) follows from the definition in
and 32 we have
n2 m
(m) j
((m)
g(5)
(n m)b, + mb2
m m
k-m m
1=0
c(m, m)
1 1 (n c(m,1 1)
1 1 m2 mb2
l)b1 + lb2
1=0
cmm 1)
(n 1)6, + lb2
10
Therefore, have finished proving (4 by induction.
Let
c²
max
le(.
Ju
Recalling that k < we have for all < k
c(j,))
(o(i)== =
Σ
+ (n 1)61 + lbb
1=0
j
lc(j,1)
(33)
1+ (n - 1)bb + lbz
1=0
c²
1 (n 1)bb + lb2
(34)
1+ (n- - k)b,
(j + 1)c
j=
(35)
1+ (n - k)bb
where 33 is due to triangle inequality, and (34p follows from the facts that b, by E l and k > 0.
since A is the number of samples. However, by the definition of g in 23) and (16).
g(k)= fa(be....,,
+ rab2

---

So we can use 135 to have
1 = -lg(k)]
(k: + 1)c*
<
1 + nb2
1 + (n k)bb
which is contradiction because if
2(k: + 1)c*
Y1 k
and
b2
then
(k: + 1)e
+ nbz
2
1 (n k3)b
To show that bn is well-defined, i.e., bj > O, we have
2(k: + 1)c²
61
n
(2(k - 1) maxjMsk (o(i,0)
n2 K
2(k + 1)lc(0, 0)
2(k + 1)
(36)
n - k
0,
where (3) follows from
26 The contradiction completes our proof.
Conclusions
This paper considered the problem of bias for methods that sample classes and examined the possibility of using a different function instead of the sampled softmax. Previous works have taken foundational assumption that such function cannot be found, treating this claim if it were true without justification. We proved, for the first time, that no function can be an unbiased estimator, which extends the conclusion in [3] that is only limited to the sampled softmax. Our result now serve as the theoretical premise for related studies. According to our result, future work should not aim find unbiased estimator. By providing proof of impossibility, work allows follow-up studies to focus on feasible solutions.
10

---

Acknowledgements
This work supported in part by National Science and Technology Council of Taiwan grant NSTCC-113-222-F-002 005-MY3, and in part by the Featured Area Research Center Program within the framework of the Higher Education Sprout Project by the Ministry of Education 11499000).). The authors thank the reviewers for their insightful and constructive comments.
References
[1] Yoshua Bengio and lean-Sébastien Senécal. Quick training of probabilistic neural nets by impor- tance sampling. In Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, pages 17-24, 2003.
[2] Yoshua Bengio and Jean-Sébasties Senecal. Adaptive importance sampling to accelerate training of a neural probabilistic language model. IEEE Transactions on Neural Networks, 19(4):713-722, 2008
[3] Guy Blanc and Steffen Rendle. Adaptive sampled softmax with kernel based sampling. In International Conference Machine Learning, pages 590-599, 2018.
[4] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple frame- work for contrastive learning of visual representations. Proceedings of the Thirty-Seventh International Conference on Machine Learning (ICMI), pages 1597-1607, 2020.
[5] Ching- Yao Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanie Jegelka. Debiased contrastive learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages
Ching-Yao
2020.
[6] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommenda- tions. In Proceedings of the 10th ACM Conference on Recommender Systems, pages 191-198, 2016.
[7] Kunal Dahiya, Nilesh Gupta, Deepak Saini, Akshay Soni, Yajun Wang, Kushal Dave, Jian Jiao, Gururaj K, Prasenjit Dey, Amit Singh, Deepesh Hada, Vidit Jain, Bhawna Paliwal, Anshul Mittal, Sonu Mehta, Ramachandran Ramjee, Sumeet Agarwal, Purushottam Kar, and Manik Varma. NGAME: negative mining-awe aware mini-batching for extreme classification. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining (WSDM), pages 258-266, 2023.
[8] Alexandre de Brébisson and Pascal Vincent. An exploration of softmax alternatives belonging to the spherical loss family. In International Conference on Learning Representations (ICLR), 2016.
[9] Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT, pages 4171 4186, 2019.
[10] Francois Fagan and Garud Iyengar. Unbiased scalable softmax optimization. 0bs//180300857 2018.
CoRR.
[11] Siddharth Gopal and Yiming Yang. Distributed training of large-scale logistic models. In Proceedings of the 30th International Conference on Machine Learning (ICML), pages 289- 297, 2013.
[12] Nilesh Gupta, Devvrit, Ankit Singh Rawat, Srinadh Bhojanapalli, Prateek Jain, and Inderjit S. Dhillon. Dual-eneoders for extreme multi-label classification. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR), 2024.
[13] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing (EMNLP), pages 6769-66666699 6781, 2020.

---

[14] Frederic Morin and Yoshua Bengio. Hierarchical probabilistic neural network language model. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statisties, pages 246-252 2005.
[15] Parameswaran Raman, Shin Matsushima, Xinhua Zhang, Hyokun Yun, and S. V. N. Vish- wanathan. DS-MLR: exploiting double separability for scaling up distributed multinomial logistic regression. CoRR, hess/660404406 2016.
[16] Ankit Singh Rawat, Jiecao Chen, Felix X. Yu, Ananda Theertha Suresh, and Sanjiv Kumar. Sampled softmax with random fourier features. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, pages 13834-13844, 2019.
[17] Nils Reimers and Iryna Gurevych. Sentence-BERT: Sentence embeddings using siamese BERT-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3980-3990 39900,999220000 2019.
[18] Stephen Robertson and Hugo Zaragoza. The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval, 3(4):333-389, 2009.
[19] Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: Theory and applications. In Proceedings of the Thirty-ninth International Conference on Machine Learning (ICML), pages 23292-23317, 2022.
[20] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. In Proceedings of the Ninth International Conference on Learning Representations (ICLR), 2021.
[21] Yang, Xinyang Yi, Derek Zhiyuan Cheng, Lichan Hong, Yang Li, Simon Xiaoming Wang, Taibai Xu, and Ed H. Chi. Mixed negative sampling for learning two-tower neural networks in recommendations. In Companion Proceedings of the Weh Conference (WWW), pages 441-447, 2020.
[22] Xinyang Yi, Ji Yang, Lichan Hong, Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Kumthekar, Zhe Zhao, Li Wei, and Ed Chi. Sampling-binn biis-correeee neural modeling for large corpus item recommendations. In Proceedings of the 13th ACM Conference Recommender Systems, page 269-277, 2019.
[23] Zhuoning Yuan, Dixian Zhu, Zi-Hao Qiu, Gang Li, Xuanhui Wang, and Tianbao Yang. LibAUC: deep learning library for x-risk optimization. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 5487-5499, 2023.
[24] Wenzheng Zhang and Karl Stratos. Understanding hard negatives in noise contrastive estimation. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACI-HIIT, pages 1090-1101, 2021.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction described our contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The scope of applicability and assumptions are formally stated in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

The proof of each lemma, theorem and corollary are formally written and referred to. The only assumption, Assumption 3.2 used in Corollary 3.3 is clearly stated.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA].
Justification:
There is experiment.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA].
Justification:
There is no experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.ccppulli/guuiii httppp//iiiicuiiccoo/ooeeeaaaaia CoodeSubeeiieeeeeeeeee ssi asiinnolle onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA].
Justification:
There is no experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA].
Justification: There is no experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA].
Justification:
There is no experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: There no human subjects or participants, no data, no model, no negative societal impact and no potential harm.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This is impossibility proof and not implementable as anything executable.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is impossibility proof and is not implementable anything executable.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: There is asset.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There is asset.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
There is no crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification:
There is no crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
The core method development only involved human brains.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
19

---

A Using Log-Softmax Loss During Training
The typical loss function for models based Softmax the log-softmax function
L 01 , Hn = log Softmax(O***
Dn ,..,,..,,,
x - log
Σ
U.
During training, we need to compute the gradient of L each step. In other words, we need to compute the partial derivatives. The partial derivative of log-softmax with respect to the target class is
0L 91 ..... ...9) Oijt
+
Di=l e
1 - Softmax (++, 00,00 01 ..... 8n
and the partial derivatives with respect to the negative classes j {l...., n2 are
aL(g DT ..... om
Ø0j
e + Σ e9,
Softmax Ūū 05.....07-11- ,9 ..
Therefore, computing the gradient of the loss function requires computing Softmax.
B Reducing to 8
Let o, E R denote the original logits for the ith negative class. Instead of using o, directly, we use
d1 = o, + -log(w()))
such that
8 0. +1)
w(() e
where Vi, wii) are constants. So we have
ev
s(g 0r, ...., 07v
cùt + Ej=1 c
eśt + 1 w(y)ee
which is the sampled softmax in the original logits o;
C Proof of Lemmas
C.1 Proof of Lemma 4.2
Proof.
[e(21...,,....
.... xk))
1
Σ
ha
he!
TESt
Σ
(37)
TEB
where 37
follows because the summation sums over the same set of summands.
20

---

C.2 Proof of Lemma 4.3
Proof. We first note that the number of all possible samples of indices is
n!
k
(n k)!
which is the number of combinations of choices from items multiplied by the number of permutations on k items. Let C(n, k; a) denote the set of (x) choices of k elements from a. Then
(n k)!
[fu aic))
Σ
E
n!!
(E;(n, oES,
(n k)!
Σ
E
Σ TES
he
#EC(n a;a) oES,
(n -n- k)!
Σ
Σ
ha (2(
(38)
n!
mEC(n,k;a) DESp
TES
(n - k)!
Σ
Σ
(T(R)
n!
=EC(n,k;a) 7E8
[hx (As).-.... 0ig
where
388 follows because the summation over sums over the same set of summands.
D Sampling Distributions Depending On All Logits
In this section, we show that and 16 not meet Assumption 3.2 by giving a brief overview of how they work.
Their methods depend on the following problem structure, Given input space X' and the input æ X, logits of class take the form
y: (f())), 0z))
where f: X Rd is the model, d is the embedding dimension and U, Rd is the embedding of class i. In other words, the probability of class is given by
el
Softmax (fi, ...... fi- 91+1 No+ 1)
Dn+I cd
(1))
Σ c(f(m),)))
In keeping with ( we let n denote the number of negative classes, so there are a total of n + classes. They proposed sampling distribution p that is efficient to compute and has a structure similar the softmax function. The probability p(1) of sampling class is given by
p(1) (d(f(z)), o(x,))
(39)
EØ
where o: Rdd R a feature map given by
(vv) = (2) Ua ... U2 UgUa).
21

---

Notably, the sampling distribution (39 does not satisfy Assumption 3.2 because (39 effectively involves computing the logits. Expanding out the terms of the inner product, have
d
(0([(a)), =
(a)
k=1
d
d
Σ {
3-1
k=1
(f(x), vi) (f()))
o4.
E Proof of Corollary 3.3
Proof. The proof is by contradiction. Assume there is an unbiased estimator h2 for F with sampling distribution p. That is,
Pr (11 = Ji....,44 . = jK) =
The expectation is given by
F(a) = E, (as.......... dir)l= (n k)! oeS,
(40)
Note that this is different from 12 in which have k choices from items first due the uniform sampling. Therefore, here we have Sn instead of Sy 12.. Further, the summation over a has n!
summands but there are only
11
n! [n k)!
k!
k-
choices of indices. Therefore, the summation counts each choice of indices (n k)) times, which is corrected by the first factor [n-
We first observe that F is symmetric in its arguments, i.e., for every permutation Sa.
F(a) 1+ ++ Oj 1+ En ar(1)
(r()))
(41)
By Assumption 3.2 is the same function regardless of the values of This property and (41 imply that, for every permutation 7 E Sn,
F(a) = F(ar(1)...., A7(n)) (n - k))l aES,
(42)
'Without Assumption 3.2 it is possible to have a different distribution for each a. See Appendix D for details.
22

---

Therefore,
F(a)
1
Σ
F(a)
n!
TES
1
1
x (a((o(r(1)) -.. (0((((())))))))
(43)
n!
k:)!
TES
JES
Σ
p(o(1), (((()...,..k(k)))) x
Σ
hy (.lorrr))......aa..... "
n!(n
k.!!
oESn
TES
p(o ... o(k)) x
hy ha.
(44)
n!(n -k)! aESn
TESS
(n k)! he(ar(1):..... (r(k))
(45)
n!(n -k]!
TES
1 hg(a-())....,a11))) (T(())
n! TES,
(n b)!
Σ Σ
(46)
n!
kia) DESt
where (43) follows from and follows because the summation over 7 sums over the same set of summands. From
44
45
E ploo(),.... = (n k:)! GES
because, as we mentioned earlier, each element counted (n- k:)! times. Finally, 446 is just 12 the expectation under the uniform distribution. This implies that h2 also an unbiased estimator under the uniform distribution. Such an fıg does not exist by Theorem 3.1 leading to a contradiction.
F Impossibility of an Unbiased Log-Softmax Estimator
In this section, we prove that an unbiased and differentiable log-softmax estimator E' does not exist. We prove by contradiction. Assume that
E
[e(ū 07, [5,]
log Softmax (i+ . ,....... kw))
Then
log Softmax(ğ" .......
E
[(00" "....... D7,)
Oÿ+
1
Σ
llit 9 (o())....... Fa(R))
n!
GES
a
Σ
l(j Bo(i)...... Bo(r))
n!!
O
SES
91, ........3 (155 (
E
(47)
Oi
So
Softmax($* (0+.0 07 ..... 07)
log Softmax($* 0T ...., f
Oÿ+
i
E
{( 0. ... 1
(48)
ag*
23

---

where the first equality follows from ( and the second equality follows from 447
The expression
Oi Ei"" Di....., Div -1 1
in (48 is therefore unbiased estimator for softmax, which contradicts Theorem 3.1
Note that the proof above assumes a differentiable estimator but the proof of Theorem 3.1 does not. Since we take the gradient of the loss estimator during training, we can reasonably assume that practical loss estimators are differentiable.
24


Reviews:
[{"review_id": "Hi6pqJgj9U", "reviewer": "Reviewer_Y1Xs", "summary": "In this work, the authors address a problem related to the use of the softmax function over a large number of classes. To handle the computational cost of the full softmax, practitioners often use a sampled softmax, which is known to be a biased estimator. This paper proves that any estimator that relies on a sampled subset of classes must be biased, under the assumption that the sampling distribution is independent of the logit values. The main contribution is a formal impossibility proof that confirms a widely held belief in the field, suggesting that research should continue to focus on bias reduction rather than elimination.", "questions": "1. The proof relies on constructing specific configurations of the logit values (e.g., all equal, or split into two groups). This is a valid and powerful proof technique. Have the authors considered alternative proof strategies, perhaps from information theory or functional analysis, that might offer a different perspective on why this unbiased estimation is impossible?\n\n2. The problem definition and proof are based on sampling k indices from n without replacement. Does the impossibility result also hold for sampling with replacement? It seems intuitively that it should, as this would be a less informative sample.", "limitations": "Yes, the authors have adequately addressed the limitations. They are very clear that their work is a theoretical impossibility proof and does not provide a new algorithm.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "#### Strengths\n\n1. The paper provides a solid and rigorous proof for a widely-held, but previously unproven, belief in the machine learning community. Formalizing this impossibility result is a valuable contribution that helps solidify the theoretical foundations of large-scale classification.\n\n2. The paper is well-written, and the proof is presented clearly. The logical flow is easy to follow, and the authors do a good job of setting up the problem and their assumptions. The technical quality of the mathematical argument is high.\n\n#### Weaknesses\n\n1. While the result is a useful formalization, it proves something that was already strongly suspected and implicitly assumed by most researchers in the area. Therefore, the work confirms the existing research direction (bias reduction) rather than opening up new ones. Its overall impact might be limited.\n\n2. The work is entirely theoretical. It does not offer new insights into the nature or magnitude of the bias for different estimators, nor does it provide any guidance for designing better-biased estimators. The lack of any empirical validation or practical takeaways makes the contribution feel incremental.", "was_revised": true, "final_justification": "This is a solid paper that rigorously proves something important: any estimator using a sampled subset of classes for a softmax function will be biased. This formalizes a belief many in the field already held, which is a valuable contribution.\n\nThe main drawback is that it doesn't really open up new research paths; it mostly just confirms that the current focus on reducing bias is the correct approach. Because the impact is more foundational than groundbreaking, the paper is seen as technically sound but a bit incremental. The good (a rigorous proof) just outweighs the bad (limited novelty).", "rebuttal": "> While the result is a useful formalization, it proves something that was already strongly suspected and implicitly assumed by most researchers in the area. Therefore, the work confirms the existing research direction (bias reduction) rather than opening up new ones. Its overall impact might be limited.\n> The work is entirely theoretical. It does not offer new insights into the nature or magnitude of the bias for different estimators, nor does it provide any guidance for designing better-biased estimators. The lack of any empirical validation or practical takeaways makes the contribution feel incremental.\n\nWe wholeheartedly agree with the reviewer's observation that our result formalizes an assumption widely held in the community. It is precisely the widespread relevance of our research question that makes our conclusion an important addition to the published literature. While the conclusion may have been strongly suspected, our goal was to rigorously prove it and settle the matter definitively. We believe resolving this foundational question helps solidify the basis for ongoing work in bias reduction.\n\n> The proof relies on constructing specific configurations of the logit values (e.g., all equal, or split into two groups). This is a valid and powerful proof technique. Have the authors considered alternative proof strategies, perhaps from information theory or functional analysis, that might offer a different perspective on why this unbiased estimation is impossible?\n\nRegarding alternative proof strategies, we did attempt several directions during the course of our work. However, the construction-based approach was the only one that led to a complete proof. We agree that alternative perspectives could offer valuable insight and worth exploring further in future work.\n\n> The problem definition and proof are based on sampling k indices from n without replacement. Does the impossibility result also hold for sampling with replacement? It seems intuitively that it should, as this would be a less informative sample.\n\nOur premise of sampling without replacement is based on the most common practice in real-world applications. We agree that extending the result to sampling with replacement is a natural next step and thank the reviewer for the suggestion."}, {"review_id": "K6JJnccbqs", "reviewer": "Reviewer_gnrp", "summary": "The authors consider the problem of approximating the softmax using sampling of its arguments. They prove theoretically that any sampling-based estimator that samples a fixed number of logits (and that is not allowed to depend on the logits) must necessarily be biased.", "questions": "- Does the analysis shed any light on the difficulty of *approximating* the softmax?  This would be useful for estimators that navigate a bias-variance tradeoff.\n- The analysis also doesn’t seem to rule out estimators that use a stochastic number of samples (e.g., based on a stopping rule), correct?  If it does, it would be great to point it out.", "limitations": "Not explicitly discussed; some of the points mentioned above could be mentioned.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The negative result provided by the paper is interesting, and supports / encourages the development of efficient biased estimators\n\nWeaknesses: \n- While the construction provided rules out unbiased estimates for the softmax, I don’t think it technically rules out unbiased estimates of, e.g., the log softmax (which is typically used in loss computation), which would be sufficient to obtain unbiased stochastic gradient estimates.  It would be great if the authors could comment on this.\n- Moreover, the theoretical analysis rules out *exactly* unbiased estimators, leaving open important questions of approximability (see below).", "was_revised": true, "final_justification": "I'd like to thank the authors for the clarification.  While the considered sampling scheme (and hence the implied hardness result) indeed is relevant for approximating the gradient as well (as discussed in Appendix A), the problem of approximating the log softmax itself (i.e., for computing the loss and not its gradient) is still relevant and not considered.  Nevertheless, while I still feel that the paper is somewhat limited, in my opinion it makes a relevant contribution to the literature and I have increased my score.", "rebuttal": "> While the construction provided rules out unbiased estimates for the softmax, I don’t think it technically rules out unbiased estimates of, e.g., the log softmax (which is typically used in loss computation), which would be sufficient to obtain unbiased stochastic gradient estimates. It would be great if the authors could comment on this.\n\nWe would like to clarify that we specifically addressed the gradient of log softmax in Appendix A. We showed that estimating the gradient of log softmax is precisely the same problem as estimating softmax. Therefore, we did rule out unbiased estimates for the log softmax as a loss.\n\n> Does the analysis shed any light on the difficulty of approximating the softmax? This would be useful for estimators that navigate a bias-variance tradeoff.\n\nWe agree that understanding approximability and bias-variance tradeoffs is important, and we are interested in pursuing this in future work. However, our focus in this paper was to resolve the question of exact unbiasedness, which remained open.\n\n> The analysis also doesn’t seem to rule out estimators that use a stochastic number of samples (e.g., based on a stopping rule), correct? If it does, it would be great to point it out.\n\nWe're not sure what was meant by estimators using a stochastic number of samples. If the suggestion refers to iterative schemes that incrementally sample more logits, then we think this is an interesting direction. Our analysis does not address such schemes, and we appreciate the suggestion as a potential future direction."}, {"review_id": "ixVBjN8Arq", "reviewer": "Reviewer_8WoT", "summary": "The paper provides a proof that no unbiased sampled estimator of the softmax function exists. The authors argue that this long suspected but never formally proven property could guide research into future softmax estimators.\n\nThe authors also give a thorough review of several related works which attempted to mitigate or avoid this bias.\n\nThe paper’s proof leverages a contradiction, showing that an estimator cannot exist which is unbiased in two cases: one where all logits are constant and one where all logits take on one of two values.", "questions": "Q1 What sorts of distributional assumptions on the logits would be required to construct an unbiased estimator for k << n?\n\nQ2 Given a fixed k << n, can one get close to an unbiased estimator?\n\nQ3 Does this property have implications for adaptive softmax estimators or softmax gradient estimators?", "limitations": "yes", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The provided proof is clear, formal, and relatively easy to follow. While the simplicity of the proof does not disqualify it from publication, it represents the sole output of the paper, meaning the bar for novelty and impact should be set high.\n\nUnfortunately, the applications of the proved result appear relatively limited. No scenarios come to mind in which one would expect a softmax estimator to be unbiased across the entire space of logit vectors.\n\nThough this analysis certainly helps to guide the conversation, it seems reasonable to expect further analysis from a publication of NeurIPS’ caliber (e.g., bounds on the bias based on k or distributional assumptions under which an unbiased estimator is possible).", "was_revised": true, "final_justification": "I still believe that the sole result of the paper lacks sufficient impact. The paper shows that if no restrictions are made on the distribution of logit vectors in a softmax, then an unbiased estimator cannot be created. The authors frame this lack of assumptions as a strength, but in reality it expands the family of allowed vectors to include adversarial examples which in turn makes the proof easier. Additionally, if we place no restrictions on the logit vectors, it seems unlikely one can expect to construct a useful estimator, much less an unbiased one.\n\nThis is why I strongly believe that in order to be published it is necessary for this paper to include further results bounding the bias of softmax estimators or provide a similar impossibility result for unbiased estimators given bounded logit distributions.\n\nAs a result, I have maintained my previous score.", "rebuttal": "> Unfortunately, the applications of the proved result appear relatively limited. No scenarios come to mind in which one would expect a softmax estimator to be unbiased across the entire space of logit vectors.\n\nWhile the result may align with intuition in hindsight, to our knowledge, no formal proof previously existed. Moreover, unlike softmax, there do exist unbiased estimators for other commonly used objectives (e.g., binary cross-entropy), which makes the softmax case non-obvious and worth settling formally.\n\n> Though this analysis certainly helps to guide the conversation, it seems reasonable to expect further analysis from a publication of NeurIPS’ caliber (e.g., bounds on the bias based on k or distributional assumptions under which an unbiased estimator is possible).\n\nWe agree that further analysis (e.g., bias bounds or conditions for approximability) would be valuable, but we chose to focus this work on conclusively resolving the exact unbiasedness question, which we view as a fundamental theoretical contribution.\n\n> What sorts of distributional assumptions on the logits would be required to construct an unbiased estimator for k << n?\n\nThere are trivial distributions (e.g., constant logits) under which an unbiased estimator could exist, but such cases are highly artificial and we are not aware of any that arise in practical settings.\n\n> Given a fixed k << n, can one get close to an unbiased estimator?\n\nWe did not study approximation quality or bias-variance tradeoffs, as our focus in this work was on establishing the impossibility of exact unbiasedness. We agree this is an important direction for future research.\n\n> Does this property have implications for adaptive softmax estimators or softmax gradient estimators?\n\nWe're not sure what is meant by \"adaptive softmax estimators,\" but if this refers to methods that adjust the sampling process based on observed data, then we have a discussion in Appendix D."}, {"review_id": "k5AkDj8cRZ", "reviewer": "Reviewer_Uj1A", "summary": "This paper proves that an unbiased estimator based on sampled indices for full softmax must be biased for general cases.", "questions": "- Line 122. Positive classes are not defined. Moreover, what if the positive classes of other instances are identical to the current instance? Are they still so-called negative?\n- Assumption 2.3 excludes adaptive sampling methods. The authors argue that this requires computing the full softmax. But is it possible to select sampling distribution after obtaining logits with a sampling approach rather than computing the full softmax?\n- Is it possible to quantify the bias?\n- How do existing techniques align with the paper's conclusion? Are there inspirations for new bias-reduction methods if we still adopt the biased estimator?\n- The sampled estimator is biased for general cases and the paper proves it by crafting counter-examples. What are the cases / conditions under which the estimator is unbiased?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strength**\n- The results in the manuscript are mathematically sound with rigorous and detailed proof presented. The assumptions are mild, practical and reasonable.\n- The conclusion is of interest to machine learning systems involving millions of possible classes to predict.\n\n**Weaknesses**\n- The results simply prevent investigations for finding unbiased estimators but do not provide any other deeper insights such as how to reduce the bias with the help of conclusions in the paper.", "was_revised": true, "final_justification": "I recommend borderline acceptance because this paper provides important conclusion for exact unbiasedness of sampled softmax estimators, but not a stronger acceptance level because the conclusion does not lead to any more significant insights on future designs of better estimators. My concerns have been addressed by the authors though. But the content and key take-aways do not seem to put this work certainly above the acceptance borderline.", "rebuttal": "> The results simply prevent investigations for finding unbiased estimators but do not provide any other deeper insights such as how to reduce the bias with the help of conclusions in the paper.\n\nWhile we agree that understanding and reducing bias is important, we chose to focus this paper specifically on the exact unbiased case as a first step.\n\n> Line 122. Positive classes are not defined.\n\nWe should've written \"target classes\" instead of \"positive classes\". We thank the reviewer for pointing out our error.\n\n> Moreover, what if the positive classes of other instances are identical to the current instance? Are they still so-called negative?\n\nThere are variants of in-batch sampling which do consider those classes as negative and there are variants which don't.\n\n> Assumption 2.3 excludes adaptive sampling methods. The authors argue that this requires computing the full softmax. But is it possible to select sampling distribution after obtaining logits with a sampling approach rather than computing the full softmax?\n\nIt is possible and it may be a very fruitful future direction. We gave a brief dicussion in Appendix D on previous works that take this approach to reduce the bias. However, we are not aware of adaptive sampling methods that can eliminate the bias completely.\n\n> Is it possible to quantify the bias?\n\nTo quantify the bias, we have to select a specific distribution of logits and estimator. Otherwise, any bias is possible. A trivial example is constant logits and using a constant function as estimator. An interesting future direction may be to empirically identify specific distributions and design estimators around them.\n\n> How do existing techniques align with the paper's conclusion? Are there inspirations for new bias-reduction methods if we still adopt the biased estimator?\n\nExisting techniques for softmax approximation are typically evaluated based on empirical performance, often without theoretical guarantees. Our result provides a formal justification for the use of biased estimators by showing that exact unbiasedness is unattainable, framing bias-reduction as a necessary tradeoff rather than a design flaw.\n\nAs noted earlier, adaptive sampling methods are not covered by our impossibility result and may offer promising avenues for bias reduction. We see this as an exciting direction for future work.\n\n> The sampled estimator is biased for general cases and the paper proves it by crafting counter-examples. What are the cases / conditions under which the estimator is unbiased?\n\nCiting our response to reviewer 8WoT: There are trivial distributions (e.g., constant logits) under which an unbiased estimator could exist, but such cases are highly artificial and we are not aware of any that arise in practical settings."}]

Author rebuttal:

Meta-review: This paper addresses a fundamental problem in large-scale classification: efficient approximation of the full softmax. 
It is well known that sampled softmax is biased. But it remains to be an open problem whether one can design an unbiased estimator of the full softmax. This work shows that ANY estimator that only accesses a sampled subset of classes is biased. This is a good validation on the many past works and therefore a very meaningful contribution to the community. 

There has been a healthy amount of discussions during the rebuttal period.
After the rebuttal all reviewers recognized the technical soundness of the work. 
The remaining concerns shared by reviewers are that the result is "not surprising" and therefore it does not "open up new research path". In particular the only reviewer who rated the paper below 4 states that the work "lacks sufficient impact". 

The machine learning community has long operated under the assumption that sampled softmax estimators are inherently biased, leading to a significant body of work on bias reduction. This paper provides the foundational result that this assumption is correct and that the pursuit of bias reduction is not just a practical choice but a theoretical necessity. Therefore the AC recommends that the paper to be accepted.

In the final version, in addition to incorporating the reviewers feedback, please  
* add key proof ideas and sketch in the main text.
* add the equivalence between estimating softmax vs. estimating the gradient in the main text.
Decision: Accept (poster)