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

The experimental evaluation, while sufficient, could include comparisons to more recent active learning methods

Thank you for the suggestion. We've compared against 8–10 standard baselines from scikit-activeml and DeepAL. Since our method builds on a cutting-plane training scheme, we adapted the baselines—sometimes with custom implementations—to ensure fair comparison (see Appendix H.3 for details). Because our method introduces a fundamentally novel setup unlike existing AL approaches, an exhaustive comparison is challenging given the vast literature. However, we’ll consider adding more recent deep AL methods in the baseline for the final version.

The practical implementation details for large-scale applications could be clarified further

We've detailed our implementation of sentimental classification task in Appendix H.1. We are happy to provide more details if there is anything unclear.

The limitations regarding very large networks and datasets are not fully addressed

Our proposed algorithm, still in its early stages, does face scalability challenges with the largest NN models. However, it evolves alongside advances in cutting-plane methods and LP solvers—both active research areas. Recent progress, such as improved cutting-plane techniques [8] and GPU-accelerated LP solvers [9, 10], can be directly applied to ReLU NN training based on the equivalence established in this work.

More importantly, our contribution goes beyond empirical gains. The theoretical insights enabled by this LP-NN connection are significant, especially given the much deeper understanding of LP systems compared to neural networks.

[8] An Asynchronous Proximal Bundle Method: https://link.springer.com/article/10.1007/s10107-024-02088-x; [9] CuClarabel: GPU Acceleration for a Conic Optimization Solver: https://arxiv.org/abs/2412.19027; [10] MPAX: Mathematical Programming in JAX:
https://arxiv.org/abs/2412.09734.

What factors limit the scale of data selection with your method, and what is the maximum scale achievable?

The main limitation in data selection is that more training data leads to more constraints in the LP formulation, increasing the problem size. While we explore pruning schemes to discard redundant constraints (Appendix F.4), scalability remains a challenge. We haven't tested the maximum scale—current experiments use only tens of points, as larger selections require longer solver runtimes. That said, the method remains executable, albeit slower with more data.

What is the computational cost when applying your method to deeper networks

The main computational bottleneck for deeper NNs still comes from solving a large LP since we will have more variables in the LP. So ideally, if we have a very efficient LP solver, there is no limit of our method. As shown in Theorem 4.2, our theory extends to arbitrarily deep NNs. Fortunately, we've seen recent effort in GPU-accelerated LP solvers as [9] and [10] mentioned above, which truly empower our method for large scale application.

Could your method be extended to work with pretrained models?

We've indeed done some experiments with pre-trained large LLMs, following exactly the reviewer's thoughts. Figure 4 shows the result of training a two-layer ReLU classifier on top of Phi-2's embeddings for sentiment classification task. Phi-2 is a 3B pretrained LLM model. Our result shows that when combining Phi-2's embeddings with our active learning scheme, we harness higher prediction accuracy and better query efficiency compared to other baselines.

If samples selected by your method were used to train deeper neural networks, would they be more effective than samples selected by existing methods?

Thank you for the question. We base our theoretical results on cutting-plane training as it offers a cleaner, more analyzable framework. In contrast, gradient-based methods rely heavily on heuristics, and understanding their dynamics (e.g., SGD with varying batch sizes or step sizes) remains limited, making rigorous analysis difficult.

In this revision, we strengthen our theory by showing that the learned model converges not only volumetrically in parameter space, but also in norm to the optimal decision boundary (see proof here). This supports the quality of our selected samples for downstream training. That said, empirically, we tested our selected samples on a deeper network for a quadratic regression task and found our method remained competitive with standard deep active learning baselines, even if the performance gap was smaller due to task simplicity (link). We plan to add further experiments on deeper models and more complex tasks in the final version.

Theorem 6.3, the main theoretical result in this work, is quite similar to the convergence analysis in (Louche & Ralaivola, 2015)

Dear reviewer, we first cite L&R’s work in Section 2 under “Cutting-Plane-Based Active Learning with Linear Models.” Our contribution goes well beyond theirs, which applies only to linear models. Theorem 6.3 resembles classic cutting-plane convergence results—standard in the literature (e.g., see pp. 9–10 in these notes)—but it's not specific to L&R but just a classic result. Our key novelty is extending this to the nonlinear two-layer NN $f^{\text{two-layer}}$, where $f^{\text{two-layer}}$, which is never obtained before.

Empirical evaluation does not convincingly address scalability

Our goal is to show the feasibility of training ReLU NNs via LPs (see abstract, Sections 1 & 3), enabling theoretical insights not possible with traditional methods. While not yet faster than gradient-based training, our method offers stronger query efficiency, consistently outperforming baselines with fewer queries (Figures 2–4). This makes it well-suited to query-limited settings.

Scalability challenges stem from:

• Constraint growth: We mitigate this via subsampling and iterative pruning (Appendix F.4).
• Solver overhead: Recent GPU-based LP solvers like CuClarabel [3] and MPAX [4] offer promising future improvements.

[3] CuClarabel: GPU Acceleration for a Conic Optimization Solver. https://arxiv.org/abs/2412.19027
[4] MPAX: Mathematical Programming in JAX. https://arxiv.org/abs/2412.09734

Concern over exponential growth in activation patterns

Thanks for raising this. The number of ReLU activation patterns does not scale exponentially in $n$; rather, it scales with the rank of the data (see Section 3 in [5]). We further reduce complexity using pruning strategies (Appendix F.4). Recent work [6] also proposes geometric-algebra-inspired sampling, although it doesn’t yet connect to LP-based training.

[5] Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks
https://arxiv.org/pdf/2002.10553; [6] Randomized Geometric Algebra Methods for Convex Neural Networks
https://arxiv.org/pdf/2406.02806.

Applicability limited to ReLU networks

We've addressed a similar issue in our response to Point 2, but we’d like to re-emphasize the broader potential of connecting NN training to classical LP solving—both for advancing theory and enabling new algorithms. Our current work offers a preliminary demonstration of this:

• Theoretical advancement: We provide a convergence result that was previously unattainable due to the nonconvexity of NN training. Under our framework, the prediction function converges in norm to the optimal decision function (see our added proof here (anonymous link). In contrast, LP systems are well-understood thanks to centuries of study. Framing ReLU training as LP solving opens a promising new lens for analyzing deep NN properties.
• Algorithmic novelty: We show that cutting-plane methods can be applied to ReLU NN training—an approach not explored before. While we use a basic variant, there’s a rich and growing body of work on advanced cutting-plane methods (e.g., [7], published in Mathematical Programming, Jan 2025), which could be leveraged in future extensions.
• Solver development: GPU-supported LP solvers have only recently emerged, and represent an exciting and active area of ongoing research.

[7] An Asynchronous Proximal Bundle Method: https://link.springer.com/article/10.1007/s10107-024-02088-x

The paper does not address the volumetric stopping criterion in detail

Algorithm 1 gives the general cutting-plane training workflow. On its own, it lacks convergence guarantees, as random training samples may offer negligible volume reduction. The "volumetric stopping criterion" applies specifically to our active learning scheme, where shrinkage can be precisely measured. For general use, we rely on standard stopping rules like max iterations, data budget, or validation error.

Potential advantage over gradient-based methods

Our method, still in early stages, is slower than gradient-based training, so we focus on query efficiency—where we show stronger convergence guarantees and consistently outperform baselines with fewer queries (see Figures 2–4). This makes our approach ideal under a query budget. On runtime and scalability, our method evolves alongside advances in cutting-plane methods and LP solvers—both active research areas. As new breakthroughs emerge, they can be directly integrated to improve our training algorithm. Moreover, theoretical progress in these fields—arguably more likely than in learning theory—would naturally carry over to ReLU NN training through our established equivalence.

I am not able to draw solid conclusion that this method will surpass current SGD-based training of neural networks.

Thank you for raising this point. We do not claim that our method currently outperforms gradient-based training for deep NNs, especially as it remains in an early stage compared to mature gradient-based approaches.

Our key contribution is linking ReLU NNs to LPs, enabling convergence proofs previously thought infeasible due to non-convexity. Moreover. emerging GPU-based LP solvers like CuClarabel [1] and MPAX [2] offer promising avenues for scaling our approach.

[1] CuClarabel: GPU Acceleration for a Conic Optimization Solver https://arxiv.org/abs/2412.19027; [2] MPAX: Mathematical Programming in JAX https://arxiv.org/abs/2412.09734.

However, I am not sure about the evaluation criteria that solely relies on test accuracy versus SGD.

As noted, our primary goal is to demonstrate the feasibility of framing deep ReLU NN training as LP solving, which opens the door to theoretical insights previously out of reach—e.g., our convergence result—by leveraging centuries of progress in LP theory. That said, we also address empirical concerns.

The main computational burden stems from (1) the growing number of LP constraints, and (2) the cost of solving each LP:

• To manage constraint growth, we analyze LP structure evolution and propose an activation pattern subsampling and iterative filtering scheme (Appendix F.4) to prune redundant constraints.
• For solving LPs, recent GPU-enabled solvers like CuClarabel and MPAX offer promising directions to improve runtime and scalability.

Another issue is that momentum-based methods seem to be more popular, which might provide better performance.

Thank you for bring up this point. We don't involve different momentum-based methods into comparison since our main experiments are done for our active learning scheme, not for our training scheme. So in figure 2 and 3, we are mainly comparing against different active learning (or query selection in another word) baselines, not optimization algorithms. The only point we compare our training scheme to gradient-based method is in figure 4 (the right most figure), where we take SGD as a representative.

The key here is we do acknowledge our method in its current stage cannot beat SGD in deep NN training, but our theoretically-supported query acquisition strategy is already superior in terms of query efficiency. That's why most of our experiments are done for active learning. Though we are optimistic that, with the development of more advanced LP solvers, our method will be more and more practical in the near future.

The authors did not discuss the computational efficiency of their proposed method. We’ve discussed this in our reply to point 2.

Although convergence results are given, I am not sure how to understand the results.

Thank you for raising this point. In fact, a consequence of Theorem 6.3 is that the prediction function converges in norm to the optimal decision function. Please see our added proof here (anonymous link).

I think the paper would be greatly improved if the authors could show results regarding learning the correct function.

Thanks for the insightful suggestion! Yes we are able to make it, see above.

I think an interesting question is that whether this method could reduce the number of queries needed for active learning.

Yes. Despite the connection between training deep ReLU NN and solving LPs, our another contribution is the convergence result for query efficiency. Specifically, we theoretically prove that our proposed active learning strategy can exponentially shrink the parameter search space, this is (to our knowledge) the first theoretic guarantee for query efficiency among various active learning methods. Empirically, figure 2, 3, 4 all demonstrate that we can achieve better performance with fewer queried points.

Could the authors clarify on Algorithm 2?

We apologize for the confusion. Due to word limit, we include a detailed description here.

Could the authors comment of the computational aspect of their proposed method?

Our cutting-plane training scheme theoretically extends to arbitrarily deep neural networks with no upper limit on model size (Theorem 4.2). The active learning method exponentially shrinks the parameter search space, enabling analytical bounds on query complexity (Theorem 6.3). The main remaining concern is runtime, as noted in our responses to points 2 and 3, though promising progress is underway to address this.