We thank the reviewer for their response and would like to respond to some of their concerns.
> "Still not very convinced about the significance of the work"
Both smoothed learning and multiclass classification with infinite labels are recent but well-established topics. Smoothed analysis originated in the analysis of one of best known problem in CS, viz. linear programming. In recent years, smoothed analysis has been extended to learning problems. Multiclass classification is one of the most fundamental ML problems. The significant of infinite labels is both theoretical and practical. Theoretically, it was the infinite labels setting that led to the recent complete characterization of multiclass learnability. From a practical point of view, infinite labels is a means to study what happens with extremely large label spaces. This is relevant to work in NLP (large vocabularies) and in extreme multiclass classification (e.g., recommender systems).
> "how much interest the setting … could attract from the NeurIPS community”
We note that there have been several NeurIPS papers regarding smoothed online learning, even dating back to 2011 [1-4]. There is also a long history of NeurIPS papers studying classification with extremely large label spaces. This line of work is known as ``Extreme Classification" [5-11]. Thus, we think studying the intersection of these two settings is natural and of interest to the NeurIPS community.
> "this setting is not a simple combination of smoothed online learning and multiclass classification with infinite labels”
We respectfully disagree with this criticism. Yes, the setting is simple — it combined smoothed online learning with multiclass classification with infinite labels. But the analysis is far from simple and our conclusions are far from obvious. We think that a simple setting with non-obvious analysis and conclusions should be of interest to NeurIPS. We think that the simplicity of the setting should not be a drawback of our contribution.
[1] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained,
and smoothed adversaries. Advances in neural information processing systems, 24, 2011.
[2] Nika Haghtalab. Foundation of Machine Learning, by the People, for the People. PhD thesis, Carnegie
Mellon University, 2018.
[3] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems, 33:9203–9215,379
2020.
[4] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as
easy as statistical learning. In Conference on Learning Theory, pages 1716–1786. PMLR, 2022
[5] K. Bhatia, H. Jain, P. Kar, M. Varma, and P. Jain, Sparse Local Embeddings for Extreme Multi-label Classification, in NeurIPS 2015.
[6] D. Hsu, S. Kakade, J. Langford, and T. Zhang, Multi-Label Prediction via Compressed Sensing, in NeurIPS 2009.
[7] Y. Chen, and H. Lin, Feature-aware Label Space Dimension Reduction for Multi-label Classification, in NeurIPS, 2012.
[8] M. Cisse, N. Usunier, T. Artieres, and P. Gallinari, Robust Bloom Filters for Large Multilabel Classification Tasks , in NIPS, 2013.
[9] I. Evron, E. Moroshko and K. Crammer, Efficient Loss-Based Decoding on Graphs for Extreme Classification in NeurIPS, 2018.
[10] R. You, S. Dai, Z. Zhang, H. Mamitsuka, and S. Zhu, AttentionXML: Extreme Multi-Label Text Classification with Multi-Label Attention Based Recurrent Neural Network, in NeurIPS 2019.
[11] S. Kharbanda, A. Banerjee, R. Schultheis and R. Babbar, CascadeXML : Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-Label Classification, in NeurIPS 2022.