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