acceptodds
Under review as a conference paper at ICLR 2027

PEACH: Personalized Negative Caching and Sampling for Unbiased Optimization of Extreme Multiclass Classification

Abstract

Extreme multiclass classification with the cross-entropy loss is computationally challenging because evaluating its normalization term requires summing over a huge number of classes. Approximating this term with a small subset of classes, as in sampled softmax, yields biased stochastic gradients that in general do not help stochastic optimization converge to a stationary point of the full objective. Hard-negative mining can reduce this approximation error, but does not remove the bias and incurs additional computational cost. Recent work removes the bias by reformulating cross-entropy minimization as an equivalent min-min problem, in which an auxiliary variable learns the normalization term and unbiased stochastic gradients can be computed efficiently. We find, however, that uniform sampling within this framework produces high-variance gradient estimates and slow convergence in practice. To address this limitation, we propose , an unbiased optimization method based on . PEACH maintains a small cache of hard negative classes for each example, evaluates their contributions exactly, and uses simple random sampling to estimate the sum over the remaining classes. Our theoretical analysis shows that this strategy preserves unbiasedness while substantially reducing the variance of stochastic gradients for min-min optimization. Across datasets with hundreds of thousands of classes, PEACH substantially accelerates optimization in wall-clock time compared with existing methods. At matched training loss, PEACH achieves up to speedup compared with biased and unbiased optimization methods, with the advantage becoming pronounced at larger scales.

Primary area:
optimization
Keywords:
extreme classification, stochastic optimization

Reviews

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

This paper addresses efficient cross-entropy optimization for extreme multiclass classification, where computing the full softmax normalization is prohibitively expensive. Existing negative sampling methods introduce biased gradients, while recent unbiased min-min optimization approaches suffer from high gradient variance and slow convergence. To address these limitations, the authors propose PEACH, which maintains a small, personalized cache of hard negatives for each training example. PEACH evaluates cached negatives exactly and uniformly samples the remaining classes, while dynamically updating the cache during training. The authors theoretically demonstrate that this strategy preserves unbiasedness while reducing gradient variance, enabling faster convergence. Extensive experiments validate the effectiveness of the proposed method.

Critical strengths
  • The paper clearly identifies the limitations of existing methods, including biased gradients in conventional negative sampling and high gradient variance in SCENT. Motivated by the observed concentration, stability, and example-specificity of hard negatives, the authors propose a well-justified caching strategy that reduces gradient variance while preserving unbiasedness.
  • The experimental evaluation is comprehensive, covering multiple large-scale classification datasets with hundreds of thousands of classes. The results show that PEACH achieves competitive or superior classification accuracy with improved optimization efficiency compared to existing methods, demonstrating a favorable trade-off between performance and training speed and validating the effectiveness of the proposed approach.
Critical weaknesses
  • The efficiency of hard-negative discovery is insufficiently justified. PEACH relies on uniform sampling to identify hard negatives, but provides no theoretical guarantee on how quickly important negatives can be discovered. This process may become inefficient as the number of classes grows significantly. Further theoretical analysis or empirical validation of the discovery efficiency would strengthen the proposed method.

  • The paper lacks a sensitivity analysis of the negative sampling budget. Investigating how different sampling budgets affect convergence speed and computational efficiency would provide a more comprehensive evaluation of the proposed method and further validate its effectiveness.

Questions for authors
  • PEACH relies on uniform sampling to discover hard negatives. How efficiently can the cache identify the most important negatives in extremely large label spaces? Can the authors provide theoretical or empirical evidence regarding the convergence of cache quality?
  • The paper does not systematically investigate the negative sampling budget. How does varying the sampling budget affect the convergence speed and computational efficiency of PEACH?
3 comments

We sincerely thank Reviewer Cq79 for the positive feedback and helpful suggestions. We appreciate the recognition that PEACH is well motivated by the observed structure of hard negatives, and that our experiments are comprehensive across large-scale datasets. We address each question below, and the new results are added to Appendix I of the revised paper.

Q1 PEACH relies on uniform sampling to discover hard negatives. How efficiently can the cache identify the most important negatives in extremely large label spaces? Can the authors provide theoretical or empirical evidence regarding the convergence of cache quality?

A: Thank you for the question.

  • Discovery rate. In each epoch, every uncached class is sampled for a given example with probability m/Cm/C. Discovery is therefore slower for larger CC, and a larger mm helps (we use m=2Bm = 2B on TreeOfLife-200M).
  • Empirical evidence. Figure 3(c)(d) shows that the cache quality (Aiunc/AiA_i^{\text{unc}}/A_i) approaches that of the exact top-8 negatives on both Google Landmarks v2 and TreeOfLife-200M.
  • Future work. Since uniform sampling discovers hard negatives more slowly as the label space grows, designing more efficient discovery strategies, e.g., reusing logits already computed in a mini-batch or sharing candidate classes across similar examples, is an interesting direction for future work.

Q2 The paper does not systematically investigate the negative sampling budget. How does varying the sampling budget affect the convergence speed and computational efficiency of PEACH?

A: Thank you for the question. We vary the sampling budget m∈2048,4096,8192m \in \\{2048, 4096, 8192\\} on Google Landmarks v2 (Figure 8 in the revised paper; training loss below). PEACH is not sensitive to mm and a larger mm mainly speeds up early training, consistent with faster hard-negative discovery, at a slightly higher per-iteration cost.

Methodep10ep20ep30ep40ep50Time (h)
PEACH (mm=2048)0.79940.15240.04330.02990.01860.42
PEACH (mm=4096)0.76370.14020.03580.02460.01630.42
PEACH (mm=8192)0.63420.11520.03260.02310.01730.47

I appreciate the authors' thorough response and efforts to address my concerns. Their clarifications have resolved most of my questions, and I will therefore keep my original positive score.

Thank you for your positive feedback and for keeping your positive score.

Reviewer_thQQOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper addresses the problem of extreme multiclass classification, specifically the complexity of computing the normalization term of the cross-entropy loss function. To this end, the paper introduces PEACH - an SGD-based method that allows to obtain a low-variance unbiased estimate of the gradient of the cross-entropy loss while being more computationally efficient than state-of-the-art approaches.

The authors build on the work of Fagan & Iyengar (2018) and Wei et al. (2026b) that reformulates the cross-entropy objective as a minimization problem over an auxiliary variable, which then admits an unbiased stochastic estimator of the gradient. The novelty of PEACH lies in the way that the cross-entropy normalization term is computed: in addition to traditional uniform sampling of negative class labels, the method maintains a cache of negative class labels that have proven the "hardest" for this particular example in the past iterations.

The authors provide a theoretical analysis of PEACH, focusing on the lower variance of the stochastic estimate of the gradient compared to one obtained through uniform sampling. The paper includes a set of experiments that include both a comparison against SOTA methods and an ablation study.

Critical strengths

The core idea behind PEACH -- maintaining a negative-example cache -- is novel: no prior work, to my knowledge, has proposed an method that obtains an unbiased gradient estimate with a running cache. Both the theoretical and experimental results of the paper validate its benefits over the state of the art in terms of runtime / performance tradeoff on linear models.

Critical weaknesses

The paper considers training only linear models, and the experiments train a linear classifier head on frozen pre-trained features. An experiment training a deep neural network would be interesting to see.

Questions for authors
  • Would the method's advantages hold when training a non-linear model? (See Weaknesses).

  • In the Implementation paragraph of Section 6, as well as in the corresponding section of Appendix C, it is stated that sparse momentum SGD is used to preserve the computational benefit of negative class sampling. Same reasoning could be applied to BSGD and SCENT. Could the authors clarify if it was used only for PEACH, or for BSGD and SCENT as well? If only PEACH utilizes sparse momentum, the runtime advantage of the method could turn out to be overstated.

  • Although the experiments in the paper are convincing and in line with the theoretical results, the authors do not provide the code to reproduce the experiments. I would encourage the authors to do so.

1 comment

We sincerely thank Reviewer thQQ for the positive assessment and constructive suggestions. We are glad that the reviewer finds the idea of an unbiased gradient estimator with a per-example negative cache novel, and the theoretical and experimental results convincing. We address each question below, and the corresponding new results are added to Appendix I of the revised paper.

Q1 Would the method's advantages hold when training a non-linear model? (See Weaknesses).

A: Thank you for the suggestion. Yes, it still holds compared with the strongest baseline BSGD (KNN). We trained a ResNet-18 backbone end-to-end on Google Landmarks v2 and report the training loss in the table below. PEACH attains lower training loss with less time than BSGD (KNN) at every epoch. PEACH also reaches lower loss than other methods at the same wall-clock time (Figure 5 in the revised paper).

MethodEpoch 10 (Loss / Time)Epoch 20 (Loss / Time)Epoch 30 (Loss / Time)Epoch 40 (Loss / Time)Epoch 50 (Loss / Time)
BSGD (KNN)5.13 / 0.66 h3.30 / 1.32 h2.53 / 1.98 h2.22 / 2.64 h2.06 / 3.30 h
PEACH5.06 / 0.64 h2.96 / 1.28 h2.22 / 1.92 h2.08 / 2.56 h1.82 / 3.20 h

Q2 In the Implementation paragraph of Section 6, as well as in the corresponding section of Appendix C, it is stated that sparse momentum SGD is used to preserve the computational benefit of negative class sampling. Same reasoning could be applied to BSGD and SCENT. Could the authors clarify if it was used only for PEACH, or for BSGD and SCENT as well? If only PEACH utilizes sparse momentum, the runtime advantage of the method could turn out to be overstated.

A: Thank you for the careful question. Sparse momentum is used for all min-min methods, i.e., PEACH, SCENT (in-batch), and SCENT (uniform), so these methods are compared under the same optimizer. BSGD (in-batch) and BSGD (KNN) use standard momentum. To check whether the choice of optimizer affects the comparison, we train BSGD (in-batch), BSGD (KNN), and PEACH with and without sparse momentum on Google Landmarks v2 and TreeOfLife-10M, retuning the learning rate in each case (Appendix I.2 and Figure 6 of the revised paper). Training loss and total running time are shown below.

Sparse momentum barely changes the training loss or running time of PEACH and BSGD (KNN), and it only hurts BSGD (in-batch) on Google Landmarks v2. Hence, the runtime advantage of PEACH does not come from the optimizer; in our experimental setting, the computational benefit of sparse momentum is small.

Google Landmarks v2

Methodep10ep20ep30ep40ep50Time (h)
BSGD (in-batch) w/ sparse momentum1.361.040.790.640.640.28
BSGD (in-batch) w/o sparse momentum0.700.340.220.170.160.32
BSGD (KNN) w/ sparse momentum0.300.110.070.060.050.57
BSGD (KNN) w/o sparse momentum0.310.110.070.060.050.58
PEACH w/ sparse momentum0.760.140.040.020.020.42
PEACH w/o sparse momentum0.750.130.040.020.020.43

TreeOfLife-10M

Methodep10ep20ep30ep40ep50Time (h)
BSGD (in-batch) w/ sparse momentum5.935.174.914.784.760.14
BSGD (in-batch) w/o sparse momentum5.915.164.904.774.750.16
BSGD (KNN) w/ sparse momentum5.064.354.103.983.940.18
BSGD (KNN) w/o sparse momentum5.054.344.103.983.940.18
PEACH w/ sparse momentum5.434.143.743.583.510.19
PEACH w/o sparse momentum5.444.163.753.593.520.20

Q3 Although the experiments in the paper are convincing and in line with the theoretical results, the authors do not provide the code to reproduce the experiments. I would encourage the authors to do so.

A: Thank you for the suggestion. We are currently cleaning up our code and will release it together with scripts to reproduce all experiments.

Reviewer_DxhZOpenReview ↗
Rating
4(+2)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper targets extreme multi-class classification with a large number of classes. Optimization with full softmax can be expensive. On the other hand, the alternatives can be slow (uniform negative sampling) or biased (explicit hard negatives). The paper makes following observations (empirically verified on Google Landmarks v2 (GLv2)): (i) The negative partition is highly concentrated
(ii) Hard negatives stabilize early in the training (iii) Hard negatives are typically example specific.

It then builds on SCENT, which rewrites cross-entropy as a min-min problem with a per-example auxiliary variable such that sampled negatives give unbiased gradients. PEACH therefore keeps a cache of L = 8 hard negatives per example. Their contribution is computed exactly, and the remaining negatives are estimated by uniform sampling with a rescaling factor, which keeps the estimator unbiased given the cache. The cache is refreshed online with the top-L logits among cached and sampled classes.

The analysis gives the relative variance of the uniform estimator and of PEACH's estimator (Proposition 1 & 2), and a one-step descent bound that depends on variance (Theorem 3). Results are reported with on four datasets (161K - 796K classes, up to 209M examples) and with linear classifier. PEACH reaches lower training loss per unit of time than most baselines and gets slightly higher test accuracy at equal compute.


I have considered the rebuttal and updated the score accordingly.

Critical strengths
  1. Evaluating the dominant terms exactly and sampling the rest can be seen as stratified sampling preserving unbiasedness. The variance formulas (Eqs. 15, 18) follow correctly from the finite-population identity, and the (Aunc/A)2(A^{unc}/A)^2 term is intuitive.
  2. Fig. 1 shows concentration, early stabilization and example-specificity on the GoogleLandmarks-v2 dataset. This aligns with the following proposal.
  3. Results are reported on four large scale datasets including TreeOfLife-10M, GoogleLandmarks-v2, Glint360k, and TreeOfLife-200M with upto 795K classes and 200M data points.
  4. PEACH yields 2 - 10x speedup (at same training loss) as compared to baselines.
  5. Hyperparameters (Table 8), per-method timing (Table 9), and the maximum learning rate (Table 7) are included for clarity.
Critical weaknesses
  1. The kNN graph is computed exactly and rebuilt every epoch (Appendix G1). At 796K classes this adds about 4.8 hours over in-batch (12.80 vs 8.00). An ANN-based KNN would change the wall-clock comparison significantly.
  2. All experiments use frozen features and a linear classifier. The introduction notes face and species recognition as crucial applications where features change during training and hard negatives may shift faster.
  3. The paper proves unbiasedness conditional on the cache and a one-step descent bound, but no convergence rate for PEACH.
  4. The time savings as compared to approximate softmax approaches are not significant (Table 9). What is the final accuracy comparison at the end of 50 epochs? BSGD (kNN) performs on par with PEACH on TreeOfLife-10M, GoogleLandmarksv2, and Glint360k but falls short on TreeOfLife-200M -- what happens if you give slightly more budget to BSGD (kNN)?
  5. Missing comparison with existing cache-based strategies such as [1].

Reference:

[1] https://proceedings.neurips.cc/paper_files/paper/2021/file/2175f8c5cd9604f6b1e576b252d4c86e-Paper.pdf

Questions for authors
  1. What is the exact definition of the 2 - 10x speedup (target loss, which baselines, which datasets)?
  2. How do SCENT-uniform and the other baselines do on TOL-200M with m = 2B negatives and the same 5-epoch warmup? How does kNN do with approximate nearest-neighbor search?
  3. Are the sparse-momentum optimizer and the shared sample set applied to all methods? Does the variance analysis still hold with a shared sample set?
  4. How do class-level caches, random caches, and an importance-sampling variant compare, in time as well as epochs?
  5. How does the method behave in the few-epoch regime, and with end-to-end training in which features change?
  6. What are the accuracy-versus-time curves, and the accuracy at convergence, for the main baselines?
  7. Classifiers and cache are initialized randomly -- is there any guarantee/bound on the hard negatives getting discovered?
6 comments

We sincerely thank Reviewer DxhZ for the thorough and insightful review, and for recognizing our variance analysis and large-scale evaluation. The detailed questions have helped us strengthen the paper, and we have added the corresponding experiments to Appendix I of the revised paper. We address each question below.

Q1: The kNN graph is computed exactly and rebuilt every epoch (Appendix G1). At 796K classes this adds about 4.8 hours over in-batch (12.80 vs 8.00). An ANN-based KNN would change the wall-clock comparison significantly.

A: Thank you for the suggestion! We would like to clarify the following points:

  • The extra time comes mainly from the large negative class set, not from building the KNN graph. Following [3], BSGD (KNN) uses 0.1C≈800.1C \approx 80K negatives per iteration on TreeOfLife-200M, where CC is the number of classes. Whereas in-batch methods use B=4096B =4096 negatives, where BB is the batch size. Building the exact KNN graph takes only about 0.5 h in total, i.e., roughly 10% of the 4.8 h gap (12.8 h vs. 8 h). An ANN-based KNN can save at most this portion, so it would not change the wall-clock comparison significantly in our experiments. For completeness, we run KNN with same negative sample size as PEACH, which yields much worse performance than using 0.1C0.1C (See our reply for Q7).
  • ANN-based baseline. For completeness, we implemented an ANN-based KNN baseline with 0.1C0.1C negatives (Implemention detail shown in Appendix I.4 of revised paper), and the results on TreeOfLife-200M are shown below. From the table we can see that PEACH remains both faster and better.
MethodTraining timeFinal Training Loss (50th epoch)
PEACH9.8h0.44
BSGD (KNN)12.8h0.47
BSGD (ANN)12.4h0.48

Q2: All experiments use frozen features and a linear classifier. The introduction notes face and species recognition as crucial applications where features change during training and hard negatives may shift faster.

A: Thanks for the suggestion. We have conducted an end-to-end training (ResNet-18 as backbone) on Google-landmark v2, and report the training loss in the table below. From the results we can see that PEACH outperforms BSGD (KNN) and is the most efficient among all methods (please see Figure 5 in revised paper). We leave further investigation as a future direction.

MethodEpoch 10 (Loss / Time)Epoch 20 (Loss / Time)Epoch 30 (Loss / Time)Epoch 40 (Loss / Time)Epoch 50 (Loss / Time)
BSGD (KNN)5.13 / 0.66 h3.30 / 1.32 h2.53 / 1.98 h2.22 / 2.64 h2.06 / 3.30 h
PEACH5.06 / 0.64 h2.96 / 1.28 h2.22 / 1.92 h2.08 / 2.56 h1.82 / 3.20 h

Q3: The paper proves unbiasedness conditional on the cache and a one-step descent bound, but no convergence rate for PEACH.

A: Thank you for the question. Actualy, the convergence rate analysis follows the same as SCENT with the unbiasedness condition. In the worst case, it yields the same rate of O(1/T)O(1/\sqrt{T}) established in [2]. Our method introduces per sample caching to reduce variance while preserving unbiasness, thus the same proof techniques in [2] can be used to our analysis.

Q4. The time savings as compared to approximate softmax approaches are not significant (Table 9). What is the final accuracy comparison at the end of 50 epochs? BSGD (kNN) performs on par with PEACH on TreeOfLife-10M, GoogleLandmarksv2, and Glint360k but falls short on TreeOfLife-200M -- what happens if you give slightly more budget to BSGD (kNN)?

A: The testing accuracy of different methods at 50 epochs is reported in the table below. PEACH achieves accuracy close to Full Softmax across all four datasets with less training time and outperforms the other sampled baselines.

On TreeOfLife-200M, with 50 epcohs, BSGD (KNN) takes 12.8 h and has a testing accuracy of 84.66. In contrast, PEACH with 50 epochs takes less time (9.8h) and has a better testing accuracy of 84.89. Hence, giving BSGD (KNN) more budget would require giving PEACH even more budget for fair comparison. Hence, we omit this comparison.

MethodTreeOfLife-10MGoogle Landmarks v2Glint360KTreeOfLife-200M
Full Softmax47.51 (0.01)50.98 (0.00)99.95 (0.00)85.60 (0.00)
BSGD (KNN)45.80 (0.02)50.80 (0.01)99.93 (0.00)84.66 (0.04)
BSGD (in-batch)43.51 (0.03)49.62 (0.01)99.90 (0.00)77.47 (0.04)
SCENT (in-batch)43.53 (0.03)50.10 (0.03)99.90 (0.01)78.53 (0.03)
SCENT (uniform)45.20 (0.01)46.98 (0.01)99.89 (0.01)80.36 (0.04)
PEACH45.82 (0.01)50.82 (0.01)99.93 (0.00)84.89 (0.03)

Q5. Missing comparison with existing cache-based strategies such as [1].

A: We cite [1] in Section 2 and but did not compare with it since they address different problems from ours:

  • Different Problem setup. [1] trains two-tower retrieval models, while PEACH targets extreme multiclass classification with a trainable classification head.
  • Cache different things. [1] maintains a single table of document embeddings shared by all queries. PEACH maintains a small cache of class indices for each example.
  • Different cache update. [1] periodically re-embeds the oldest entries to limit staleness. PEACH recomputes the logits of cached classes with the current model and retains the top-LL classes among the cache and the sampled negatives.
  • No guarantee of Unbiasness. [1] does not guarantee an unbiased gradient for its sampled softmax objective, whereas the stochastic gradient of PEACH is unbiased for the min-min objective.

Q6. What is the exact definition of the 2 - 10x speedup (target loss, which baselines, which datasets)?

A: The speedup is measured as time-to-target-loss. For each of the other baselines, we take its final training loss after 50 epochs as the target loss, and divide its training time by the time PEACH needs to first reach that loss. For instance, if the final training CE of BSGD (in-batch) is 1.0 with 10 hours training time, while PEACH only takes 4 hours achieving the same loss 1.0, then we say it's a 2.5x speedup. We make it clear in the revision.

Q7. How do SCENT-uniform and the other baselines do on TOL-200M with m = 2B negatives and the same 5-epoch warmup? How does kNN do with approximate nearest-neighbor search?

A: Thanks for your question.

  • Baselines with m=2Bm = 2B. We rerun SCENT (uniform) and BSGD (KNN) with m=2Bm = 2B on TreeOfLife-200M with the same negative set size as PEACH and report the training loss below. For in-batch methods, the negatives are the other labels in the mini-batch and hence cannot be manually changed. The results are shown below. From the results we can see that the final training loss of SCENT (uniform) is almost the same after doubling mm, and BSGD (KNN) with m=2Bm = 2B ends with a much higher loss compared to m=0.1Cm=0.1C used in the paper (0.75 vs. 0.47).
MethodNegative size mmep10ep20ep30ep40ep50Time (h)
SCENT (uniform)BB1.411.151.051.010.988.08
SCENT (uniform)2B2B1.391.151.031.000.988.20
BSGD (KNN)0.1C0.1C0.700.590.520.490.4712.80
BSGD (KNN)2B2B0.980.870.800.760.759.01
PEACH2B2B0.750.600.510.470.449.80
  • 5-epoch warmup. We apply the same 5-epoch learning rate warmup to SCENT (uniform) and BSGD (KNN) on TreeOfLife-200M and retune their learning rates. The performance is similar to that obtained without warmup and their maximum learning rates are the same as that in Table 7. The training loss is reported below:
Methodlr warmupmax lrep10ep20ep30ep40ep50
SCENT (uniform)✘0.011.411.151.051.010.99
SCENT (uniform)✔0.011.501.251.131.070.98
BSGD (KNN)✘0.10.700.590.520.490.47
BSGD (KNN)✔0.10.790.630.550.500.48
PEACH✔0.10.750.600.510.470.44
  • ANN-based KNN. Please see our response in Q1.

Q8. Are the sparse-momentum optimizer and the shared sample set applied to all methods? Does the variance analysis still hold with a shared sample set?

A: Thanks for your question.

Regarding the Sample set: The shared sample set is used by all methods that draw uniform negatives, including SCENT (uniform), PEACH, and the random padding in BSGD (KNN).

Regarding the momentum optimizer: The sparse-momentum optimizer is used in SCENT (in-batch), SCENT (uniform), and PEACH since we follow the codebase of SCENT. For other methods, we use the standard momentum update.

For completion, we compare the training loss of BSGD (in-batch), BSGD (KNN), and PEACH with and without sparse momentum optimizer on dataset Google Landmarks v2 and TreeOfLife-10M. The results are shown in the table below.

For BSGD (in-batch), using sparse momentum optimizer leads to worse performance, while for BSGD (KNN) and PEACH, training performance and running time remain nearly unchanged. In our experiment setting, the computational advantage of sparse momentum optimizer is not obvious.

Google Landmarks v2

Methodep10ep20ep30ep40ep50Time (h)
BSGD (in-batch) w/ sparse momentum1.361.040.790.640.640.28
BSGD (in-batch) w/o sparse momentum0.700.340.220.170.160.32
BSGD (KNN) w/ sparse momentum0.300.110.070.060.050.57
BSGD (KNN) w/o sparse momentum0.310.110.070.060.050.58
PEACH w/ sparse momentum0.760.140.040.020.020.42
PEACH w/o sparse momentum0.750.130.040.020.020.43

TreeOfLife-10M

Methodep10ep20ep30ep40ep50Time (h)
BSGD (in-batch) w/ sparse momentum5.935.174.914.784.760.14
BSGD (in-batch) w/o sparse momentum5.915.164.904.774.750.16
BSGD (KNN) w/ sparse momentum5.064.354.103.983.940.18
BSGD (KNN) w/o sparse momentum5.054.344.103.983.940.18
PEACH w/ sparse momentum5.434.143.743.583.510.19
PEACH w/o sparse momentum5.444.163.753.593.520.20

Regarding Variance analysis: Yes. All per-example results (unbiasedness, Props. 1–2, and Eq. (19)) remain unchanged. The only affected step is (54), the mini-batch variance would include cross-example covariance terms, since examples share the sampled classes. Theorem 3 still holds, and SCENT (uniform) uses the same shared sampling, so the comparison is unaffected.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.