Part 2 of the response
> Why are you starting with 3000 points for initialization? Isn’t that too much (e.g. for MNIST)? Does actual active learning start of with a random 3000 points? isn’t there too much redundancy in querying 3000 point on each query step?
In deep active learning, we believe a query batch size of around 3000 instances is generally accepted. For example, Sinha et al. [1] conduct experiments on CIFAR-10, CIFAR-100, Caltech-256, ImageNet, Cityscapes and BDD100K datasets. They use 10\% of the training set as initially labeled set and 5\% of the training dataset as the query batch size. Besides, many recent works [2][3] use a query batch size in the range of 2000 to 5000 instances in deep classification datasets, such as CIFAR-10, CIFAR-100, SVHN.
Referring to these works, we unify the query batch size in the classification datasets as 3000 instances in our experiment.
As these datasets have more than 60000 training instances (MNIST, CIFAR-10, CIFAR-100, SVHN, etc.). Given this, 3000 instances constitute less than 5\% of the training dataset.
> Why random performs better than other AL methods? E,g, Coreset in CIFAR-10?
The problem settings of Senar et al. [4] and our work are different. In our experiments, there are 50 distinct target networks to be learned. We follow the implementation of Tang and Huang [5] to adapt Coreset method to the multiple models setting. It solves the coreset problem based on the features extracted by the supernet. The selected instances may not be useful for other models, because the data representations are different. We believe this is the reason why Coreset is less effective than Random in our setting. We have supplemented more explanations of this phenomenon in the revised paper.
> What is $L^2$ in (1)? Is it the Lipschitz constant?
Yes, it is the Lipschitz constant of $f$. We state in an earlier paragraph that $f : \mathbb{R}\to \mathbb{R}$ is an $L$-Lipschitz function with $f(0) = 0$. This implies that $L$ is the Lipschitz constant of $f$. We have made this clearer in this revised paper.
> Can you please show me where your claim about a reduced sample complexity for $p=2$ is proven?
We prove Theorem 1.1. The proof is presented in the appendix A. As explained below Theorem 1.1, when the theorem is specialized to $p=2$ and to a single matrix, it implies a sampling complexity of $\tilde{O}(d/\epsilon^4)$. This is a factor of $d$ better than $\tilde{O}(d^2/\epsilon^4)$ in Gajjar et al. [6].
[1] Samarth Sinha,. Variational adversarial active learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5972–5981, 2019.
[2] Yonatan Geifman and Ran El-Yaniv. Deep active learning with a neural architecture
search. In Advances in Neural Information Processing Systems, pages 5974–5984, 2019.
[3] Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan,
Afshin Rostamizadeh, and Sanjiv Kumar. Batch active learning at scale. In Advances in
Neural Information Processing Systems, pages 11933–11944, 2021.
[4] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A
core-set approach. In Proceedings of the 6th International Conference on Learning Representations, 2018.
[5] Ying-Peng Tang and Sheng-Jun Huang. Active learning for multiple target models. In Advances in Neural Information Processing Systems, 2022.
[6]Aarshvi Gajjar, Christopher Musco, and Chinmay Hegde. Active learning for single neuron models
with lipschitz non-linearities. In Procedings of the 26th International Conference on Artificial
Intelligence and Statistics, pp. 4101–4113. PMLR, 2023.