Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes

This paper does not include much of the rich related literature around MIP formulations of neural networks (See [1]-[5] and all of their related references). For instance, the problem of training a ReLU neural network with 1 hidden layer to global optimality via polynomial complexity was addressed in [5]. Moreover, MIP/cutting planes/bisection search formulations of active learning for deep neural networks has also been well-studied (see [6]-[8]).

Furthermore, the numerical experiments focus primarily on synthetic experiments on the spiral data set & quadratic regression, giving some analysis on IMDB. Most importantly, these experiments all rely on small 2 or 3-layer ReLU, which limits analysis of the scaling of the algorithms to larger, more realistic neural networks.

[1] Anderson, Ross, et al. "Strong mixed-integer programming formulations for trained neural networks." Mathematical Programming 183.1 (2020): 3-39.

[2] Toro Icarte, Rodrigo, et al. "Training binarized neural networks using MIP and CP." Principles and Practice of Constraint Programming: 25th International Conference, CP 2019, Stamford, CT, USA, September 30–October 4, 2019, Proceedings 25. Springer International Publishing, 2019.

[3] Fischetti, Matteo, and Jason Jo. "Deep neural networks and mixed integer linear optimization." Constraints 23.3 (2018): 296-309.

[4] Bienstock, Daniel, Gonzalo Muñoz, and Sebastian Pokutta. "Principled deep neural network training through linear programming." Discrete Optimization 49 (2023): 100795.

[5] Arora, Raman, et al. "Understanding deep neural networks with rectified linear units." arXiv preprint arXiv:1611.01491 (2016).

[6] Sener, Ozan, and Silvio Savarese. "Active learning for convolutional neural networks: A core-set approach." arXiv preprint arXiv:1708.00489 (2017).

[7] Mahmood, Rafid, Sanja Fidler, and Marc T. Law. "Low-Budget Active Learning via Wasserstein Distance: An Integer Programming Approach." International Conference on Learning Representations.

[8] Ducoffe, Mélanie. Active learning and input space analysis for deep networks. Diss. COMUE Université Côte d'Azur (2015-2019), 2018.

There are several major weaknesses in the level of contribution of this paper, as well as in the empirical validation of the method. There are also various issues of clarity. Altogether that makes this paper problematic for acceptance.

1. Effectiveness of the proposed methodology: Since the paper of L and R (2005) active learning and in particular deep active learning has made quite a progress. The active learning problem itself is meant to tackle the scalability of data labeling.

a. Much of Deep AL today work son massive data sets, in batch mode querying. These doesn’t not exist in this paper’s empirical validation. Instead the authors show their case on a simple 2D spiral binary classification and regressions problem and on some 50K data set of text data. By all means this is not a convincing demonstration of solving the scalability issues that AL tackles. More data sets are needed, and it would be also desired to test again R and L, on the data sets they used, even just as an ablation study (which is missing here too.)

b. Multiclass extensions and batch mode querying are not touched here

c. The volumetric stopping criterion is also not even touched upon, in particular its dependence on the dimension of the hypothesis space. How would a user designate it?

d. Im missing some standard baselines for empirical comparison with active DL, such as Badge by J Ash et al, or Coreset by Sener et. al., other graph based Deep AL that uses graph built in the feature space and can address non-linearity as such (e.g. Diffusion-based Deep Active Learning Kushnir et. al.)

2. Contribution wise the convergence analysis is too similar to L and R (2005). It would be at least appropriate to address that Theorem 6.1 is similar to L and R. One should also address the initial work of Tong and Kohler (JMLR, 2002) on cutting planes type methodology in AL. Also the effectiveness of the proposed method inlight of the the work done so far on deep AL is marginal in my view, and is not proved in this paper on enough examples and in terms of addressing key factors on scalability of AL

3. Clarity:

a. the images, their label axes and their text fonts are reduced in size and sometime also not readable.

b. Image 1 doesn’t correspond to the notation in the paper

c. Statements such as line 93: “the size of parameters set reflects level of uncertainty” need to be made clear

d. It is confusing to address theta as input in the context of DL

e. Equation in line 163 definition is not clear: is it the space of all such diagonals matrix X? or the space of all vectors activated by the positive product?

f. What is the benchmark accuracy for the IMDB? lines are quite flat. How does it compare with the R & L (2005) performance?

4. The reader is redirected for many important details to the appendix, it disrupts the flow of the paper.

1. The method fundamentally lacks scalability due to its heavy reliance on CPU-based convex solvers and high computational complexity. The computational and memory requirements grow significantly with model size and data dimensionality, making it impractical for most real-world applications. This severely limits its practical utility in modern deep learning applications.

2. The method relies on a random sampling approach to collect ReLU activation patterns, which is not exhaustive and lacks theoretical guarantees for pattern coverage. This sampling process could miss important activation patterns, especially in high-dimensional data, potentially leading to suboptimal solutions. The paper does not provide sufficient analysis of how this limitation affects the model's performance and what patterns might be missed.

3. The method is extremely limited in its applicability, as it can only be used with neural networks using linear layers and ReLU activation functions. This restriction makes it incompatible with modern architectures such as transformers, convolutional neural networks, or networks using other activation functions, significantly limiting its practical impact in the field.

$\bullet$ The first issue is the applicability in real-world active learning with DNN. Many studies of active learning with DNN consider the CNN layer, ResNet architecture, transformer, etc in the image classification, natural langauge processing, and medical image analsys. The linear layers with ReLU activation is limited in the use of active learning.

$\bullet$ The second issue is the range of experiments in the compared alg., and datasets. The datasets are too small compared to other active learning studies (usually considering 5~10 datasets such as tiny image-net or CIFAR100). In the aspects of algorithms, recent algorithms such as BADGE, BAIT, LDM-based, etc. are not considered. Especially, the BADGE is based on the gradient. The comparison of BADGE and cutting-plane can reveal the advantages or disadvantages of two algorithms in the overall performance and fast convergence in the early steps w/wo gradients. It can highlight the proposed algorithm compared to gradient-based query algorithm.

$\bullet$ Furthermore, the effect of the depth of layers can be an interesting issue. The advanced issues are not thoroughly studied.

I have several concerns, especially towards the scalability of the approach.

1. My biggest fear is the method will not work well with larger scale neural networks. This is because neural networks, with moderate capacity, are universal approximaters. For example, with a small ResNet-18, the model can fit arbitrary set of labels for the CIFAR-10 dataset with perfect accuracy. This suggests that in most vision/language applications involving large scale neural networks, the activation pattern $D$ of the last layer can simply be the set of $diag(\{0, 1\}^n)$. In such a case, cutting algorithms are not effective in training neural networks, nor doing active learning.
2. The active learning experiments all have extremely small budgets. This is potentially because the active learning strategy in this paper is somewhat counterintuitive. The algorithm queries the most confident samples, and hope for the model to be misclassifying them. However, for any neural network trained with a moderate amount of labeled samples and with gradient-based approach, the most confident samples are almost always correctly classified. I suspect the reason existing algorithms (with gradient based training) underperform is because, under limited budget, it is very easy for neural networks to make mistakes. However, in almost all deep learning applications, the model is only effective with high accuracies, i.e., the model needs to learn about uncertain samples. I also wonder if the gain from the cutting plane active learning algorithm only comes from the gradient-free training, instead of the active learning strategy.
3. The paper primarily relies on the property of ReLU activation, which is not generalizable to modern transformer architectures, where training the model is definitely not a linear program.