Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Authors: Erica Zhang
Fangzhao Zhang
Mert Pilanci
Venue: ICML 2025 poster (2025)
Keywords: convex optimization
cutting plane method
active learning
Primary area: optimization->convex

Abstract: Active learning methods aim to improve sample complexity in machine learning. In this work, we investigate an active learning scheme via a novel gradient-free cutting-plane training method for ReLU networks of arbitrary depth and develop a convergence theory. 
We demonstrate, for the first time, that cutting-plane algorithms, traditionally used in linear models, can be extended to deep neural networks despite their nonconvexity and nonlinear decision boundaries. Moreover, this training method induces the first deep active learning scheme known to achieve convergence guarantees, revealing a geometric contraction rate of the feasible set. We exemplify the effectiveness of our proposed active learning method against popular deep active learning baselines via both synthetic data experiments and sentimental classification task on real datasets.

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Erica Zhang Fangzhao Zhang Mert Pilanci? 2
Abstract
are persistently seeking for alternative training schemes for large NN models, including zero-order and second-order algorithms.
Active learning methods aim to improve sample complexity in machine learning. In this work, we investigate an active learning scheme via a novel gradient-free cutting-plaan plane training method for ReLU networks of arbitrary depth and develop convergence theory. We demonstrate, for the first time, that cutting- plane algorithms, tradition- ally used linear models, can be extended to deep neural networks despite their nonconvex- ity and nonlinear decision boundaries. Moreover, this training method induces the first deep active learning scheme known achieve convergence guarantees, revealing a geometric contraction rate of the feasible set. We exemplify the effectiveness of our proposed active learning method against popular deep active learning baselines via both synthetic data experiments and sentimental classi- fication task on real datasets.
Cutting-plane method is a classic optimization algorithm and is known for its fast convergence rate. Research on gutting-plane type methods dates back to 1950s when Ralph Gomory (Gomory, 1958) first studied it for integer program- ming and mixed-integer programming problems. Since then, this method has also been heavily investigated for solving nonlinear problems. Different variations of cutting- method emerge, including but not limited to center of gravity cutting-plane method, maximum volume ellipsoid cutting- plane method, and analytic center cutting-plan method, which mainly differ in their center-finding strategies.
Historically, deep NN training and cutting -lanne methods have developed independently, each with its own audience. In this work, we bridge them for the first time by providing viable outting-plane-bee
deep NN training and active learning (AL) scheme. Our method finds optimal neural network weights and actively queries training points via a gradient-free cutting-plane approach. We show that the in- duced active learning scheme naturally inherits classic con- vergence guarantees of cutting butting-plane methods. We present synthetic and real data experiments to demonstrate the ef- fectiveness of our proposed methods.
1. Introduction
Large neural network (NN) models are now core to arti- ficial intelligence systems. After years of development, current large NN training is still dominated by gradient- based methods, which range from basic gradient descent method to more advanced online stochastic methods such as Adam (Kingma & Ba, 2017) and Adam (Loshchilov Hutter, 2019). Recent empirical effort has focused on cutting down storage requirement for such optimizers (see Griewank & Walther (2000); Zhao et al. (2024)); accel- erating convergence by adding momentum (see Xie et al. (2023)); designing better step size search algorithms (see Defazio & Mishchenko (2023)). Despite their popularity, gradient- methods suffer from sensitivity to hyper- parameters and slow convergence. Therefore, researchers
2. Notation
We denote the set of integers from to n as [n]. We use Bp {u E Rd ||ul|p 1} denote the unit fy-norm ball and .) to denote the dot product between two vectors. Given a hyperplane H. := {x : xTw = 0}, we use 7 (H-) to denote the positive (negative) half-space: -+(() == {x x" w 2 (z) We use notation (x) = max(z, 0). We take 1(x E S} as the 1/0-valued indicator function with respect to the set S, evaluated at æ.
Equal Contribution; Junior author listed first. Department of Management Science and Engineering, Stanford University 'Department of Electrical Engineering, Stanford University. Cor- respondence to: Erica Zhang wyy4232@stanford.com Zhang <zfzhao sdd
3. Preliminaries
Fangzhao
Classic cutting-plane method's usage in different opti- mization problems has been heavily studied. To better demonstrate the problem and offer more self-contained background, we start with describing basic cutting-plan method's 's workflow.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
original search space Pk
ineffective cut
effective cut
Ps
Pa
get certain cut point xz (k+1)
2(A
Pa+
vs.
Pott
(adapted from Boyd and Vandenberghe, 2018)
Figure Illustration of single iteration of general cutting-plane method (Boyd & Vandenberghe, 2007).
Cutting-Plann Method. Consider any minimization prob- lem with an objective function f(0), where the solution set, denoted as θ, is a convex set. Cutting-plane method typically assumes the existence of an oracle that, given any input fb. either confirms that fu E θ, thereby terminating with Og as a satisfactory solution, or returns a pair (or so- called "cut"" (z. 3) such that x" 0, S y while x > y for all 0 E O. If the cut is "good enough," " it allows for the elimination of large portion of the search space, enabling rapid progress toward the true solution set O
parameter space 0: = center(T"); (ii) queries the label ye for æ, from the unlabeled dataset D which has minimal pre- diction margin with respect to 0%: (iii) reduces the parameter space via a cutting plane in the case of mis-classification: T = T n (0 ye (zz, 8) > 0}. The algorithm terminates when set T is small enough or maximum iterations or data budget have been reached. This active learning scheme has strong convergence result inherited from classic cutting- plane method, which has been investigated in (Louche & Ralaivola, 2015).
The classic convergence results of the cutting-plane method are highly dependent on the quality of the cut in each iter- ation. For instance, if the center of gravity of the current volume removed, it guarantees a volume reduction of approximately 63%. Similar results hold for the analytic center and the center of the maximum volume ellipsoid. Fig- ure illustrates single step of the cutting-plane method, showing how a "good" cut near the center of the current volume induces a much larger volume reduction compared to a "bad" cut near the edge.
Cutting-PPane-Biie Based Active Learning with DNN Models (This Work). Although (Louche & Ralaivola, 2015) pri- marily focuses on the active learning setting, their method implicitly suggests a cutting-plane-based training work- flow for linear binary classifiers. To illustrate this, con- sider a set of training samples {(21, vi)...., (In yn Each pair (x., y:) induces a cut on the parameter space (0 y: x;) >> 0). The final center, i.e., 0, center( (0) y 2., > 0, i E [n]]], accounts for all such cuts and thus maintains the desired property (f; 0)) = y for all training samples. This choice makes 6g not only an optimal solution, but also a robust choice, as it remains stable under data perturbations.
Betting-Plane-Biiee Active Learning with Linear Mod- els (Louche & Ralaivola, 2015). Prior work (Louche & Ralaivola, 2015) has studied the use of cutting-plane method in the context of active learning with linear models for bi- nary classification tasks. The setup is the following. One is given set of unlabeled data D= = { ... J. The authors consider a linear binary classifier f(x; 0) := (8, .x) with prediction sign(f(x; 0)) for any input x. Define the set of model parameters that correctly classify our dataset as To. Starting at an initial set 7 which contains To as a subset, the goal is query training data point (and require its label) to reduce the size of 7 approach To as soon as possible (i.e., with as few data queried possible). The active learning framework developed by (Louche & Ralaivola, 2015) (Algorithm 3) starts with a localized convex set T The algorithm is presented with the set of all unlabeled data. At each step t, it performs the following steps: (i) computes the center of the current
By disentangling the model training process from the active learning query strategy described in (Louche & Ralaivola, 2015), we derive a gradient-free sutting-plane-based work- flow for training linear binary classifiers. However, this approach has several key limitations: (1) it is restricted to linear models, (2) it requires the data to be linearly sepa- rable to ensure existence of an optimal parameter set, and (3) it only supports binary classification tasks. Our current work addresses all three limitations by extending the cutting- plane method to train deep nonlinear neural networks for both classification and regression tasks, without requiring linear separability of the data. Similar to the linear binary classification case, our vanilla training scheme lacks desir- able convergence guarantees, as the cuts may occur at the edge of the parameter set. To overcome this, we focus on
saating-plane-basse
2

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
seetiin-plane-basee active learning scheme that enables cuts to be near the center of the parameter set. We provide convergence result for this approach which, to the best of our knowledge, is the first convergence guarantee for active learning algorithms applied to deep neural networks.
Note that originally, we want (0, 0 be satisfied for our sign prediction. However, the set {0) (0, .x) > 0} is not compact and is thus not compliant with forms of standard linear programs. This may raise technical issues. We observe that our training data is finite, and thus we can always scale 0 to achieve y: (0, xz) 2 c for any positive constant e once y:(0, zi) > holds, and y: mi) 2 c for > also guarantees y: (8, > 0. We pick c 1 in
Outline. The paper is organized as follows: in Section 4, we adapt the cutring-plane method for nonlinear model training by transforming the nonlinear training process into a linear programming problem. Section 5 introduces the training algorithm
(I). With a two-layer ReLU model, we obtain the following problem:
general gradient-free outting-plane-ban for deep NNs. In Section 6, we explore the induced cutting- plane active learning framework and prove its convergence. Section 7 demonstrates the practical effectiveness of our proposed training and active learning methods through var- ious experiments. Finally, limitations and conclusions are discussed in Section 8.
find
W1, W₂ 36 (c. W1) W2
(2)
S.L.
Vi.
Before showing that solving (2) is indeed equivalent to solving a linear program, we first introduce the core concept of activation patterns which we will draw on heavily later. For data matrix X E Raad and any arbitrary vector u E IRd, we consider the set of diagonal matrices
4. Key Observation: Training ReLU NNs for Binary Classification is Linear Programming
D = {diag( 1 (Xu 2 0])}.
We denote the carnality of set D as P, i.e., P= |D] Thus (D; E D, E [P]} iterates over all possible activation patterns of ReLU function induced by data matrix X. See Definition C.1 for more details. With this concept, we can reframe the training of two-layer ReLU model for binary classification as the following linear program:
The cutting-plane active learning scheme proposed by (Louche & Ralaivola, 2015) (summarized in Section 3) is designed for linear models like fx = (0,z). æ². Extend- ing this method to nonlinear models, such as a two-layer ReLU network f(;; 8) = (x T +1)+ W22 with W1 E Rdxx and W2 E Th presents additional challenges. Specifically, for a mis-predicted data pair (Ia, y4). determining how to cut the parameter space for (W1, W2) is far more complex (and nonlinear), whereas in the linear case, the cut is simply ya( (0, .xx) > 0.
Theorem 4.1. When m 2 2P, Problem (2) is equivalent to
find
Ue ul
P Σ D;X -u)) 21,
s.1.
y
(3)
To break this bottleneck and extend the cutting-plane-basee based learning method to nonlinear models, we observe that train- ing ReLU network for binary classification can be for- mulated a linear programming problem. This insight is crucial for extending the learning scheme in (Louche & Ralaivola, 2015) to more complex models. We now develop our core idea of reframing binary classification with ReLU models as linear programs. For clarity, we present our re- sults in two thcorems: one for two-layer ReLU networks and another for ReLU networks of arbitrary depth. We focus on the two-layer case in the main paper for detailed discus- sion, deferring the more abstract general case Appendix F.2. Since the general case is an extension of the two-layer model, focusing on the two-layer case should be enough to provide a clear understanding of the core concepts.
(2D; - 1)Xu, 2 0,
(2D; - 1) 20.
Proof. See Appendix F.I.
The equivalence in Theorem 4.1 holds in the sense that, which we prove rigorously in Appendix F.I, whenever there is solution Wi, W₂ to Problem (2), there is always solution [u, ut} to problem (3) and vice versa. Moreover, when an optimal solution {ut, uf*) } to problem (3) has been found, we can explicitly create an optimal solution {WI. WT} to Problem (2) from value of (ut, uf }. see Appendix F. for details. Thereafter, for any test point ã, our sign prediction simply (ign((W**)+ WW),, which will have the same value as sign(L, (5" uz) )+ (ff"(()))
We start with writing the linear program corresponding to the linear model for binary classification tasks as below,
We emphasize that our reframing of training ReLU neural network for binary classification as linear program does not crase the nonlinear nature of the ReLU activation. Instead, this approach works because the ReLU activation patterns
find
0
(1)
s.t.
(:(0.z)) 21 Vi.
3

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
for a given training dataset are finite. By looping through these activation patterns, we can explicitly enumerate them. At test time, the ReLU nonlinearity is preserved, as our prediction Zign(E, (2" u;)+ (2Tu;)+ - (a" +)) depends on the sign of u2 and J u4, ensuring that the expressiveness of the nonlinearity remains intact. A careful reader might note that the number of patterns P increases with the size of the training data, meaning the number of variables in Prob- lem (3) may also grow. Additionally, finding all activation patterns poses a challenge. In Section 7, we demonstrate that subsampling a set of non-duplicate activation patterns performs well in practice. For further grounding, Appendix F.4 outlines an iterative hyperplane filtering method that guarantees the identification of all activation patterns with a reasonable complexity bound.
where cs E [1, and
P:
Ton-1"a (0(1)) =
Σ D (T(-)D)(()))))
(D((i))))
(D(i-1))
J:=1
-T ((-11).(()(t (D(6-1))
visn-1
(0 (D(I)
= Σ
D X
Inja-insh
f1
2cn- 1
Proof. See Appendix F.2.
5. Training Deep Neural Networks via Cutting-Plane Method
Now, let us consider ReLU network with hidden layers for binary classification task
Algorithm Training NN with Cutting- Plane Method
find W1, W2. ... Wn+1 s.t. y (... ((XW))+W2) ... )+ W 2 1.
Input: Ev. Tu.Tma
Initialization: To + B2, t + 0 repeat
(4) We extend the activation patterns involved in Theorem
0 + center(T*)
Get new training data (Znes Vay) if you f 0*) < 0 then
4.1 to (n + 1)-layer neural networks. Let W1 E Rdxmi W2 E Rm W3 E R= Wn E Pm Xmm, Wn+1 E R= Define ma := d and the ac- tivation pattern in i-th layer as
T < T (ecu(((m))))
1+t+1
end if until vol(T') S E, or tt 2 Tmax return 8:
D(i) = -ddia((L(( ((x.((((X)))))))) 03 ... 2 03)
0j E 1 j U R
With the linear program reframing of training deep ReLU models in place, we now formally introduce our cutting- plane-based NN training scheme for binary classification. We begin with feasible set of variables in our linear pro- gram (5) that contains the optimal solution. For each train- ing sample (z,, y:). we add the corresponding constraints as cuts. At each iteration, we select the center of the current parameter set, stopping when either the validation loss sta- bilizes or after fixed number of iterations, similar to the stopping criteria in traddent-based training of large models.
We denote the cardinality of set D(1) as i..., P, (D()
Thus (D.)) ( E D(0, E [P.] iterates over all possible
activation patterns at the i-th hidden layer. We then reframe Problem (4) as below:
Theorem 4.2. When m, 2 1122, for each i E [n], Prob- lem (4) is equivalent to
We present our cutting-plane- blane NN training algorithm here in main text. For generalizations, such as (i) relax- ing the data distribution to remove the linear separability requirement (Appendix 1) and (ii) extending from classi- fication to regression tasks (Appendix E.2), we refer readers to Appendix E. We emphasize that both the relaxed data con- straint and the ability to handle regression tasks are unique to our method and have not been achieved in prior work.
find
U On
injn-1ja-2-..1
D mn) jn
(
s.t.
y
- -Tin-1) (D( 21
(2D
T) T) (1-1)(n-))---(- (1)) 0,2 0 Algorithm 1 presents the general workflow of how we train deep NNs with gradient-frr nutting-plane method, (5) which simply adds a cut corresponding to each training data
J:
(2
I)Xu, Ca Cann-1nn
Jain-1n.fj 2 0,
J
4

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
(Ino Mh:)) in each iteration. When the stopping criterion is satisfied, center of current parameter set T is returned. Here we start with the parameter space the unit 2-norm ball, which is guaranteed to contain optimal parameters due to scale invariance.
in this section the algorithm specifically for binary clas- sification and with respect two-layer ReLU NNs. We emphasize that the algorithm can be easily adapted to the case of multi-class classification and regression tasks, per discussion in Appendix E.2, and for deeper NNs following our reformulation in Theorem 4.2.
After we get the final 0', for any test point T. we can directly compute our sign prediction with 6% For example, for two-layer ReLU model, 0% will be of form {ul, u/ J. our final sign prediction would simply be sign (x( (z ++)++) For deeper models, the prediction is bit more complex and is given in equation (16) in Appendix F.2. Notably, the computation of final sign prediction from value of 0. always takes a single step, just as one forward pass of original NN model formulation. Moreover, one can also restore optimal NN weights from final 0% see Appendix F.1 for two-layer case reconstruction of optimal NN parameters and Appendix F.2 for general case.
Recall the problem formulation for cutting-plamn training with two-layer ReLU NN for binary classification (Equation (3)). Given training dataset (X, y). we use XD and yo to denote the slices of X and y at indices D. Moreover, we succinetly denote the prediction function as:
fowo-layer (X:0) = Σ E(DX))ouf -us) us)
i=1
X5 -X 0, 1 -X3
(6)
where 0 = (u1, ui,..., up Up) with u, ut R and X is shorthand notation for (D,X)p. For the further brevity of notation, we denote the ReLU constraints in Equation (3), i.e. ((2D: - ))) un 2 0 and ((2D; - I, Ix)x) u¹ 2 0, as C(D) and CM()). We use the analytic center (Definition 6. 1 below), which is known to be easily computable and has good convergence properties, as our "center" function. Then with Theorem 4.1, cutting-plann paattr---paae-eeeeeee based active learning methods for deep NNs become well applicable.
Two key functions in our proposed training scheme are the "center" and the "cut" function, which we detail below:
Center. The "center" function calculates the center of the convex set T There are a couple of notions of centers, such as center of gravity (CG), center of maximum volume ellipsoid (MVE). Chebyshev's cen- ter, and analytic center (Boyd & Vandenberghe, 2004). Among these, the analytic center is the easiest to com- pute and is empirically known to be effective (Goffin et al., 1997; Atlason et al., 2008). This is the notion of center that we implement. See Appendix H.1 for details.
Definition 6.1 (Analytic Center). The analytic center of polyhedron p = {=laς : S b,, = I,.., m) is given by
m
AC(P) := arg min
>
log(b, - of 2)
Cut. The "cut" function determines the cutting planes we get from specific training data (I Dn.)- For two- layer model, the "cut" function would return the con- straint set (yn, (E: Din, = (u: u()) 2 1, (2Din, 1)=H 4i 2 0, (2D in, 1)=T, uf 2 0}. For deeper NNs, the "cut" function would return constraints listed in Problem (5).
We are now ready to present the cutting-plane- learning algorithms for deep NNs. For breadth of discussion, we present three versions of the active learning algorithms, each corresponding to the following setups:
active
1. Cutting-plan active learning with query synthesis (Al- gorithm 2). The cutting-plane oracle has access to query synthesis, ensuring that the cut remains active until the optimal classifier(s) is(are) encountered, at which point the algorithm terminates.
Unlike gradient- based neural network training, which takes gradient descent step for each queried data point, our method applies a cutting-plant planne cut for every data point en- countered. Furthermore, our training scheme guarantees correct classification for all previously encountered data points, a property not ensured by gradient-based methods
Cutting-plane active learning with limited queries (Al- gorithm 4). The cutting-plane oracle operates with limited queries, performing cut only when the cur- rent center misclassifies the data pair provided by the oracle.
6. Cutting-Pland Plane-Based Active Learning and Convergence Guarantees
3. Cutting-plane active learning with inexact cuts (Algo- rithm 5). The cutting-plane oracle also operates with limited queries, but in this case, the algorithm performs a cut regardless of whether the current center misclas- sifies the data pair provided by the oracle.
6.1. Cutting-Plane Localization for Active Learning
Our proposed cutting-plane- blane- active learning algorithm adapts and extends the generic trainings framework dis- cussed in Section 5. For the sake of simplicity, we present
5

---

Active Learning of Deep Neural Networks via Stradient-Free Cutting Planes
cutting-plane NN (ours)
cutting plane ithree-leyen
Entregy Sampling
Greedy X
abc
Train data
Test data
1,0
Queried data
033
Least Confidence
cuiting plane (Lineat)
Random Sampling
BALD Drapout
0.5
-1.0
1.5 -1.0
02.5
0.0
0.5
1.0
Figure 2. Decision boundaries for binary classification on the spiral dataset for the cutting-plane AL method using two-layer ReLU neural network, alongside various deep AL baselines. For compactness, we also include the decision boundaries for the cutting-plane AL method with three-layer ReLU network in the collage to demonstrate its feasibility. For fairness of comparison, two-layer ReLU network structure and embedding size of 623 for all methods. We enforce the same hyperparameters for all deep AL baselines and select the best performing number of training epochs 2000 and learning rate at 0.001 ensure optimal performance. See Appendix H.3 for details.
the same
For brevity, we present the algorithm for the first setup here (Algorithm 2), using Dos for query synthesis, and defer the rest to Appendix D.
which includes regularization, can improve the cutting-plane method's performance in certain tasks (see Appendix H.2).
6.2. Convergence Guarantees
Algorithm 2 Cutting-plane AL for Binary Classification with Query Synthesis
We give theoretical examination the convergence prop- erties of Algorithm 2 with respect to the center of gravity (CG). Analysis of Algorithm with center of maximum vol- ume ellipsoid (MVE) and Algorithm 5 for inexact cuts deferred to Appendix G.3 and G.4. We note that the analysis of MVE closely parallels that of CG. For both centers, we measure the convergence speed with respect to the volume of the localization set T and judge the progress in itcration by the fractional decrease in volume: vol(T*+1)) (/vo('T)) To start, we give the definition of the center of gravity.
1: T <- B2
2:
3: DAL +
4: repeat
5: 0 (Tt)
6: for in (1, -1 do
7: (Fnes Vna) ) QUERY
8:
if yu, praottgee (x,,, 0.) < 0 then
9:
DAI. ADD(DAL, (Zm,, 3m)))
10:
T - T n {0 Une puo-lager (Tni 0) M
0, C.C((m)), L --++1
Definition 6.2 (Center of Gravity (Boyd & Vandenberghe, 2004)). For given convex body (i.e. compact convex set with non-empty interior) C' C IRd, the centroid, center of gravity (CG) of C, denoted 0g (C")", is given by
11:
end if
13:
end for
14:
until |'xull 2 Tbudget
15:
return 0
1
(c(C) vol(C") J
vdæ.
function Query(0,s)
2: (a, u) <- arg (e s two layer (Nin 0)
Our analysis of the center of gravity relies on Propo- sition C.4 from (Grünbaum, 1960). which ensures that cutting a convex body through its centroid eliminates fixed portion of the feasible set. Recursively applying this proposition yields the volume inequality: vol(T,) S (1 - 1/e1/e) 1/e) vol s vvll)))
3: return (x, y)
4: end function
Notably, Ergen & Pilanci (2021b) shows that two- and three- layer ReLU networks can be reformulated as exact convex programs, allowing a final convex solver to be applied to Al- gorithm 2 after the active learning loop. This reformulation,
Our proposed soating-plane--ee based active learning method (Algorithms and 4) modifies the splitting in Proposition
6

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Cutting Plane NK (Durs)
Cutting-Ptaee (Linear)
Bandom Sampling
Encropy Sampling
Train
Loo
Least Confidence
Greedy
Test
Oowen
Creedy
True yoxx
Prediction
x Test Data
Queried Points
Entrapy
Rancom Sampling
spc
Conficence
cutting Jouns)
Figure 3. Left: Predictions for the quadratic regression task using the cutting-plane AL method with two-layer ReLU network, alongside representative deep AI. baselines. Full results are deferred Appendix H.5. The linear cutting-plane AL method becomes infeasible after the fourth query, as expected (see Appendix D for further explanation), so its prediction is based on 4 queries, while others use all 20. Right: Logarithm mean test/train RMSE across seeds (0 (0-4) versus the number queries for the two-layer cutting-plann AL baselines. The linear cutting-plan method is excluded for this comparison due to infeasibility.
C.4 by replacing the weight vector with mapping of the pa- rameter to the feature space via the function fiwo-layer, which depends on the point In, returned by the oracle each step, along with the associated linear constraints C((ne)) and ((((n))). Since yowe-layer is linear in 0 (as in Equation (17)), the set {0 Y/m ftwo-layer (Zn, 0) 2 0} forms half-space in the parameter space. Therefore, {0) yo. (x, 0) 2 0, 0,C((m)), (((m))) defines a convex polyhedron. This represents a non non-trivial modifi- cation the results in Proposition C.4.
satisfies the following inequality:
vol(TT) < <11-2) vol(T).
Proof. See Appendix G.1.
An immediate consequence the progressive volumetric shrinkage of the parameter space in Theorem 6.3 is the con- vergence of the prediction function fg ptwo-layer to the optimal decision function fgr etwo-layer
Theorem 6.3 (Convergence with Center of Gravity). Let T C ddd be a convex body and let 0G denote its center of gravity. The polyhedron given in Algorithm 2 and Algorithm 4 (assuming that the cut is active), i.e.
Corollary 6.4 (Prediction Convergence of Two-Layer Net-
work). Let T C R2PP be an initial convex parame- ter domain containing the optimal parameter 0", and let [T be the sequence of convex bodies generated by repeated cuts centered at the center of gravity of the current set, in Theorem 6.3. Assume that each cut is active and the associated constraints are valid. Then for any fixed data matrix X E Ruxd the corresponding prediction functions converge:
Tn {0: ya ftwo-layer (I,: 0, 0,C((()),
where coupling (In, Vn) the data point returned by the outting-plane oracle after receiving queried point tc. parti- tions the convex body T into two subsets:
[I I (X) -
ptwo-layer (X)ll2 +0 as k + 00,
Ti = {0 E T::00 :3 ftwo-layer (zn; 0) C,,((n))
where ((K) (K) denotes the center of gravity iteration k.
To = (0 E T Un powo-layer (zn: -OV-C((m))
C(((f)))
Proof. See Appendix G.2.
where denotes the complement of given set. Then Ti
7

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
lest Accurecy
Test Accuracy
Test Accurocy
cutting plane training
SGD (1-1e11)
00-
005
SGD (ea)e-22
07-
(lmiee33
06-
0.70
04-
0/5-
two layer NN (ours)
01-
active sampling (ours)
0.54
linear model
random sampling
09
0M5
19
7
12
TaN
Query Points
Query Points
Query Points
moving average
Figure 4. Sentimental analysis on IMDB movie review dataset with two-layer ReLU model. We take Phi-2 embeddings as training features and compare with various baselines. The result shows that the introduction of non-lincarigg improves upon lincar model performance; our active sampling scheme effectively identifies valuable training points compared random sampling; and our cutting- plane training scheme is more effective than SGD in this setting. See Section 7.2 for details. Linear and our reframed two-layer models are initialized to predict zero while two-layer NN trained with SGD has random weight initialization, thus starting from non-zero prediction. Solid lines are running averages of dotted lines.
7. Experiments
baselines with fewer queries.
We validate our proposed training and active learning meth- ods through extensive experiments, comparing them with various popular baselines from scikit-are -act veml (Kot- tke et al., 2021) and DeepAL (Huang, 2021). Synthetic data experiments are presented in Section 7.1, and real data experiments are presented in Section 7.2. An overview of each baseline is given in Appendix H.3. For implementation details and additional results, refer to Appendix H.
Quadratic Regression. We evaluate method (Al- gorithm 6) on a simple quadratic regression task, com- paring it against the same seven baselines from the spi- ral task and two additional regression AL methods from seikit-acts iveml: GreedyT (greedy sampling in tar- get space) and kldiv (KL divergence maximization). Using 100 noise-free data points from y = x², we perform a 4:1 train-test split with query budget of 20 points. The numer- ical results are presented in Appendix H.5 (Table 5). The left of Figure 3 visualizes our method's 's final predictions against select baselines. Our cutting-plane AL. achieves the lowest train/test RMSE of 0.01/0.01, reducing errors by over 80%/75% compared to the next best baseline. This strong performance consistent across random seeds, as shown in the error-bar plots (right of Figure 3), where our method converges faster to the optimal solution with fewer queries.
7.1. Synthetic Data Experiments
In this section, we present small scale numerical experi- ments to verify the performance of our algorithm on both classification and regression tasks.
Binary Classification on Synthetic Spiral. We use syn- thetic dataset of two intertwined spirals with positive and negative labels (details in Appendix H.4), which contains 100 data points with a 4:1 train-test split. We compare the train and test accuracy of our cutting outting-plane AL (Algorithm 4) to popular deep AL baselines, all evaluated with query budget of 20 points (25% of the train data). Our method achieved perfect accuracy on both sets, outperforming all baselines. Notably, in the 3-layer case, our cutting- plane AL achieved train/test accuracies of 0.71/0.60 while using only 57 and 34 neurons per layer, respectively, compared to 623 neurons in the two-layer version. See Table in Appendix H.4 for numerical results. The decision boundary plot in Figure 2 shows the 3-layer model capturing the spiral's 's rough shape with smaller embeddings, while the two-layer model precisely traces the spiral. The strong performance of our method is consistent across random seeds, as shown in the error-bar plot in Appendix H.4 (Figure 15), where our approach converges to the optimal classifier faster than
7.2. Sentimental Classification for Real Datasets Using LLM Embeddings
To demonstrate the real-world applicability of our method, we combine the Microsoft Phi-2 model (Javaheripi et al., 2023) with our two-layer ReLU binary classifier for senti- mental classification on the IMDB (Maas et al., 201 movie review dataset. This dataset contains 50k online reviews labeled as positive or negative. Example training data can be found in Appendix H.6. Our active learning algorithm, paired with the tutting-plane training scheme, is tested on this task. For the experiment, we extract Phi-2's final-layer embeddings (size d = 2560) as feature vectors for training and testing and sample P 500 activation patterns to man- age the high-dimensiioal feature space (details in Appendix H.
8

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Figure 4 presents our results compared to various baselines. The leftmost plot shows that our two-layer ReLU model achieves higher accuracy within the same query budget compared to the linear model from (Louche & Ralaivola, 2015), highlighting the advantage of a nonlinear model. The middle plot compares our active learning method to random sampling, both using the two-layer ReLU model. As expected, our active sampling scheme identifies critical data points, enabling better performance within the same query budget. The rightmost plot compares our cutting-plane- based NN training with stochastic gradient descent (SGD). Unlike SGD, which requires batched data and struggles with as few as 15 query points, our satting-plane training achieves higher accuracy with this minimal training budget, demonstrating its efficiency.
Acknowledgement
M.P. acknowledges support in part by National Science Foundation (NSF) under Grant DMS-2134248, in part by the NSF CAREER Award under Grant CCF-2236829; in part by the U.S. Army Research Office Early Career Award under Grant W91 INF-21-1-0242 in part by the Office of Naval Research under Grant 180014-24-1-216- E.Z. and F.Z. acknowledge support from the Stanford Graduate Fel- lowship (SGF) for Sciences and Engineering.
In addition, the authors would like to thank Maximilian Schaller from the Department of Electrical Engineering at Stanford University for their valuable contributions to the early development of the codes used in this paper.
References
8. Conclusion and Limitation
Abe, N. and Mamitsuka, H. Query learning strategies using boosting and bagging. In Proceedings of the Fifteenth International Conference on Machine Learning (ICML), pp. 1-9. Citeseer, 1998.
In this work, we introduce novel cutting-plane-bet method for deep neural network training. We also ex- plore an active learning scheme built on our proposed training framework. The implementation of our cutting- plane active learning (CPAL) method is made available at https://gttuu..com/pp compplaaniilaaalpaa. Despite its novelty, our current implementation has several key limitations that hin- der its competitiveness with large-scale models trained using gradient-based methods: (1) our hyperplane subsampling process is not exhaustive; (2) our implementation relies on CPU-based convex program solver and inefficient for large-scale problems with many variables; (3) our approach has so far been applied only to classification and regression tasks. Nevertheless, our theoretic work shows valid way to extend cutting- -laane method from prior linear-model -bsse binary classifier to NN-based classifier and regressor, and our active learning method persists fast geometric conver- gence rate.
Atlason, J., Epelman, M. A., and Henderson, S. G. Optimiz- ing call center staffing using simulation and analytic cen- ter cutting-plane methods. Manage. Sci., 54(2)2255-39, feb 2008. ISSN 0025-1909. doi: 10.1287/mmsc.J. 0774. URL https: http//do....rgg / 10. 1070.0774
Balas, E., Ceria, S., and Cornuéjos, G. A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Program., 58(1-3):295-322 January 1993. ISSN 0025- 5610.
Boyd, S. and Vandenberghe, L. Localization and cutting- plane methods. From Stanford EE 364b lecture notes, 386, 2007.
Due space constraints, the prior work section is de- ferred to Appendix A and detailed conclusion section is deferred to Appendix B.
Boyd, S. P. and Vandenberghe, L. Convex optimization. Cambridge university press, 2004.
Chen, T. and Chen, H. Approximations of continuous func- tionals by neural networks with application to dynamic systems. IEEE Transactions on Neural Networks, 4(6): 110-918, 1993. doi: 10. 10.1109772.286886
Impact Statement
This work introduces cutting-plane-hie framework for training deep neural networks, offering the first deep active learning method with convergence guarantees. It enhances efficiency and reliability in neural network training, with domains like
Chui, K. and Li, X. Approximation by ridge functions and neural networks with one hidden layer. Journal of Approximation Theory, 70(2):131-14) 1992.
potential applications in resource-constraing healthcare and environmental modeling. While the method carries minimal ethical risks, future work should consider fairness constraints to address unintended biases.
Costarelli, D., Spigler, R., et al. Constructive approximation by superposition of sigmoidal functions. Anal. Theory Appl, 19(2):19-1196, 2013.
Cotter, N. The stonewweiesstrass theorem and its applica- tion to neural networks. IEEE Transactions on Neural Networks, 1(4):290-295, 1990. doi: 10.1109/72.8026.
9

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Cybenko, G. Approximation by superpositions of sig- moidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Griewank, A. and Walther, A. Algorithm 799: revolve: an implementation of checkpointing for the reverse ad- joint mode of computational differentiation. ACM Trans- actions on Mathematical Software (TOMS), 26(1):19-45, 2000.
Defazio, A. and Mishchenko, K. Learning-rate-Fnnn learning by d-adaptation, 2023. URL https: hww.t:ttts///attet http:////axxvvooo// orrg/ 222/2231100777
Grünbaum, B. Partitions of maass-istributtinss and of convex bodies by hyperplanes. Journal of Mathematical Analy- sis and Applications, 10(4):125--1261, 1960. Received January 22, 1960. This research United States Air Force through the Air Force Office of Scientific Research of the Air Research and Development Command, under contract No. AF49(638)-253.
Diamond, S. and Boyd, S. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
supported by the
Elreedy, D., Atiya, A. F., and Shaheen, S. I. A novel active learning regression framework for balancing the exploration-explloittion trade-off. In Proceedingy of the 28th International Joint Conference on Artificial Intelli- gence, pp. 651 651-657, 2019.
Hornik, K. Approximation capabilities of multilayer feed- forward networks. Neural networks, 4(2):251-255 1991.
Huang, K.-H. Deepal: Deep active learning in python, 2021.
Ergen, T. and Pilanci, M. Implicit convex regularizers of cnn architectures: Convex optimization of two- and three- layer networks in polynomial time. 2021a.
ichi Funahashi, K. On the approximate realization of continuous mappings by neural networks. Neural Networks, 2:183-192. 1989. URL https: attps::/app.. /api. semanticscholar.co ott.rr/cccccccl.ooooooooorraaaaa 1020310,
Ergen, T. and Pilanci, M. Revealing the structure of deep neural networks via convex duality. 2021b.
Javaheripi, M., Bubeck, S., Abdin, M., Aneja, J., Mendes, C. C. T., Weizhu Chen, A. D. G., Eldan, R., Gopi, S., Gunasekar, S., Kauffmann, P., Lee, Y. T., Li, Y., Nguyen, A., de Rosa, G., Saarikivi, O., Salim, A., Shah, S., San- tacroce, M., Behl, H. S., Kalai, A. T., Wang, X., Ward, R., Witte, P., Zhang, C., and Zhang, Y. Microsoft research blog, 2023.
Franc, V., Sonnenburg, S., and Werner, T. Cutting-plame methods in machine learning. 2011.
Gal, Y., Islam, R., and Ghahramani, Z. Deep bayesian active learning with image data, 2017a.
Gal, Y., Islam, R., and Ghahramani, Deep bayesian active learning with image data, 2017b. URL https: //arxiv. org/ abs / 1703. 02910.
Jiang, H., Lee, Y. T., Song. Z., and wai Wong, S. C. An improved cutting plane method for convex optimization, convex-coneave games and its applications, 2020. URL attps://arxine org/ abs www.aaaa..0 22044. 04250.
Gallant and White. There exists a neural network that does not make avoidable mistakes. In IEEE 1988 International Conference on Neural Networks, pp. 657-664 vol.1, 1988. doi: 10.1109/ICNN.IT 1988.23903.
Karzand, M. and Nowak, R. D. Maximin active learning in overparameterizee model classes. IEEE Journal on Se- lected Areas in Information Theory, 1(1):167-177, 2020.
Kelley, E. The cutting-plane method for solv- ing convex programs. Journal of The Sociery for Industrial and Applied Mathematics, 8:703-712, 1960. URL https: httpa/.saatttsccchll..tttt
Goffin, J.-I.,, Marcotte, P., and Zhu, D. An analytic center cutting plane method for pseudomonotone variational inequalities. Operations Research Let- ters, 20(1):1-6, 1997. ISSN 0167-6377. doi:
URL https: wtwp://wwwww//c/ http://wwwwwcciceeeeeeeeeee com/ aecience/atticle/pi///n/
Kingma, D. and Ba, J. Adam: A method for stochastic op- timization, 2017. URL https: http:///xxxvv.rvoo aba/ 1412.698U
Gomory, E. An algorithm for integer solu- tions linear programs. 1958. URL https: //api. www.aaaaisccoll..roo.ooooo 116324171.
Kottke, D., Herde, M., Minh, T. P., Benz, A., Mergard, P., Roghman, A., Sandrock, C., and Sick, B. scikit- activeml: A Library and Toolbox for Active Learn- ing Algorithms. Preprints, 2021. doi: 10.20944/ preprins202103.0094.. URL com/sciki titssiikitaatieeen homm//scc secckiitaccte
Goulart, P. J. and Chen, Y. Clarabel: An anterior-point solver for conic programs with quadratic objectives, 2024.
10

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Lee, Y. T., Sidford, A., and wai Wong, C. A faster cutting plane method and its implications for combinatorial and convex optimization, 2015. URL https: //rxiv. org/abs/ / 1508. 04874.
Parshakova, T., Zhang, E, and Boyd, S. Implementation of an oracle-structured bundle method for distributed op- timization, 2023. URL https: /ttp/vaxivvvv/// /bs/ 2211. 01418.
Leshno, M., Lin, V. Y., Pinkus, A., and Schocken, S. Original contribution: Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Netw., 6(6): 861-867, jun 1993. ISSN 0893-6080. doi: 10.1016/ 508993-6088000)88131-- URL https:tt////mm //ts:.///ooooo/// org/ 10. 10.1016/S0893- 6080 (05) 80131-5.
Pilanci, M. and Ergen, T. Neural networks are convex regularizers: Exact polynomial-ting convex optimization formulations for two-layer networks, 2020.
Pinkus, A. Approximation theory of the mlp model in neural
networks. Acta numerica, 8:143-195, 1999.
Settles, B. Active learning literature survey, 2009. URL cww.coo//////o//oo wwtpppb/s/ttees....seee settles... activelearning pdf.
Lewis, D. D. and Gale, W. A. A sequential algorithm for training text classifiers. In SIGIR, pp. 3-12, 1994a.
Seung, H., Opper. M., and Sompolinsky, H. Query by com- mittee. In ACM Workshop Computational Learning Theory, pp. 287-294, 1992.
Lewis, D. D. and Gale, W. A. A sequential algorithm for training text classifiers, 1994b. URL https:: /arxiv. org/ org/abs/ cttp//mpplggggg 9407020.
Shen, Z., Yang, H., and Zhang, S. Optimal approxi- mation rate of relu networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-135, January 2022. ISSN 0021-7824. doi: 10. 1.10066j.matur:2221.00 org/10. matpur. 2022. 009.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step, 2023. URL https: //arxiv. org/
URL http: / doi.
20050.
Loshchilov, I. and Hutter, F. Decoupled weight decay regu- larization, 2019. URL https:://// / /aaxxaxxvvvv.///////aa abs/
Stanley, R. P. et al. An introduction to hyperplane arrange- ments. Geometric combinatorics, 13(389-496):24, 2004.
1711.05101.
Viehmann, et al. skorch: A scikit-learn compatible neural network library that wraps pytorch. https: /ttp//ggtttbbbbb com/ Seon/skorch-dev swtrchk..chhh 2019. Version 0.10.0.
Louche, U. and Ralaivola, L. From cutting planes algo- rithms to compression schemes and active learning. In 2015 International Joint Conference on Neural Networks (LJCNN), pp. 1-8. IEEE, 2015.
Woodward, M. and Finn, C. Active one-shot learning, 2017. URL https:tt/////. /ttpvv.iiivv////i////aa////aaavv .rg.ivoorrrraooo /arg//abi absg///b//// awtpaa//..../////./ 170.. 06559.
Maas, A. L., Daly, R. E., Pham, P. T., Huang, D., Ng. A. Y., and Potts, C. Learning word vectors for sen- timent analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguis- tics: Human Language Technologies, pp. 142-150, Port- land, Oregon, USA, June 2011. Association for Com- putational Linguistics. URL http: htttp://ww... wtw.:/wwwwww....... org/ aaap/nthoolloggg /P11-11111 1111--1055 101..
Wu, D., Lin, C.-T., and Huang. J. Active learning for re- gression using greedy sampling. Information Sciences, pp. 90-105, 2019.
Xie, X., Zhou, P., Li, H., Lin, Z., and Yan, S. Adan: Adap- tive nesterov momentum algorithm for faster optimiz- ing deep models, 2023. URL https: http///xxivv.rr////// abs/ 2208. 06677.
Zhang, F. and Pilanci, M. Analyzing neural network-based generative diffusion models through convex optimiza- tion, 2024. URL https:tt//// /tttpp://arxiii //tp//aavvvv////////////////.av/ org/ 01965.
Mhaskar, H. and Micchelli, C. Approximation by superpo- sition of sigmoidal and radial basis functions. Advances in Applied Mathematics ADVAN APPL MATH, 13:350- 373, 09 1992. doi: 10.1016/0196 (00006601996888889299000001 8858(92)90016-PP
Zhao, J., Zhang, Z., Chen, B., Wang, Z., Anandkumar, A., and Tian, Y. Galore: Memory-efficient Ilm training by gradient low-rank projection, 2024. URL https: htt///aabb2233.33353 03507.
MOSEK ApS. MOSEK Optimizer for Python Version 10.0.0, 2024. URL https:/ cense file attached: misek.lic.
com/ Li-
/
Mussmann, S., Reisler, J., Tsai, D., Mousavi, E., O'Brien, S., and Goldszmidt, M. Active learning with expected error reduction, 2022. URL https:://// //arxiivvoorr abs abss/2111 09283.
Zhu, Y. and Nowak, R. Active learning with neural net- works: Insights from nonparametric statistics. Advances in Neural Information Processing Systems, 35:142 155, 2022.

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
A. Prior Work
We emphasize the novelty of our work as the first to introduce both cutting-plane-bee training schemes and cutting-plane- based active learning methods to deep neural network models. To the best of our knowledge, this work also provides the first convergence guarantees among existing active learning methods for nonlinear neural networks. As discussed in Section 3, the most closely related work is (Louche & Ralaivola, 2015), which also integrates the concepts of cutting-pla -lanne methods, active learning, and machine learning for binary classification tasks. We are not aware of any other studies that closely align with our approach. However, we review additional works that, while less directly connected, share some overlap with our research in key areas.
Cutting-Plane Method. Cutting-plane methods are first introduced by (Gomory, 1958) for linear programming. Though being considered ineffective after it was first introduced, it has been later shown by (Balas et al., 1993) to be empirically useful when combined with branch-and-bound methods. Cutting-plane method is now heavily used in different commercial solvers. Commonly employed cutting planes for solving convex programs are tightly connected to gradient information, which is also the underline logic for well-known Kelley's 's cutting plann method (Kelley, 1960). Specifically, consider any minimization problem with objective ʃ(0) whose solution set, we denote as θ is a convex set. Gradient-basse based outting-plane method usually assumes the existence of an oracle such that given any input 0g. it either accepts 0g E θ and thus terminates with satisfactory solution 0n being found or it returns a pair (ar,)) such that x²'0g S y while 2T 7 > y for any 0 E O, i.e., we receive cutting plane that cuts between the current input dg and the desired solution set O. Such cut is given by subgradient of f at query point fg. Consider any subgradient, g E (f()), we have the inequality S(0) 2 [00) + g" (0- On), which then raises the cut n² (0- 0o) I 0 for minimization problem. Recent development of outting-plane methods involves those designed for convex- concave games (Jiang et al., 2020), combinatorial optimization (Lee et al., 2015), and also application to traditional machine learning tasks such as regularized risk minimization, multiple kernel learning, and MAP inference in graphical models (Franc et al., 2011).
Active Learning. With the fast growth of current model sizes, a large amounts of data is need for training an effective deep networks. Compared to just feeding the model with set of randomly-selected training samples, how to select the most informative data for each training iteration becomes a critical question, especially in neural models (Zhu & Nowak, 2022; Karzand& & Nowak, 2020). Efficient data sampling is thus increasingly important, especially for current RL-based language model training schemes. With the increasing power of current pretrained models, researchers observed that since most of simple questions can be addressed correctly by the model already, these questions are less important for further boosting the language models' capacity. Therefore, actively selecting questions that LLM cannot address correctly is key to current LLM training (Lightman et al.. 2023). Based on different learning settings, active learning strategies can be divided into: drased selective sampling used when the data is generated continuously (Woodward & Finn, 2017); pool-based sampling used when a pool of unlabeled data is presented (Gal et al., 2017b); query synthesis methods used when new samples can be generated for labeling. Based on different information measuring schemes, active learning algorithms can be further divided into uncertainty sampling (Lewis& & Gale, 1994b) which selects data samples to reduce prediction uncertainty, query-by-comme commiitee sampling which involves multiple models for data selection, -ieeritt-wwiihhed method which selects the most diverse data sample, and expected error reduction method (Mussmann et al., 2022) which selects samples to best reduce models' expected prediction error.
Convex NN. We note that the idea of introducing hyperplane arrangements to derive equivalent problem formulation for deep NN training task has also been investigated in prior convexification of neural network research. For example, (Ergen & Pilanci, 2021b) has exploited this technique to derive convex program which is equivalent to two-layer ReI.U model training task. More developments involving (Ergen & Pilanci, 2021a) which derives convex programs equivalent to training three-layer CNNs and (Zhang& & Pilanci, 2024) which derives convex programs for diffusion models. However, those work neither derive linear programs as considered in our case, nor did they connect such reframed problems to active learning platform. On the contrast, they mainly focus on solving NN training problem by solving the equivalent convex program (directly) they have derived via convex program solver such CVXPY (Diamond & Boyd, 2016).
B. Conclusion and Limitations
In this work, we introduce a novel cutting-plane plane- based method for deep neural network training, which, for the first time, enables the application of this approach to nonlinear models. Additionally, our new training scheme removes previous
12

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
restrictions on the training data distribution and extends the method beyond binary classification to general regression tasks. We also explore an active learning scheme built on our proposed training framework, which inherits convergence guarnntees from classic cutting-plane methods. Through both synthetic and real data experiments, we demonstrate the practicality and effectiveness of our training and active learning methods. In summary, our work introduces novel, gradient-free approach to neural network training, demonstrating for the first time the feasibility of applying the cutring-plane method to neural networks, while also offering the first deep active learning method with convergence guarantees.
Despite its novelty, our current implementation has several key limitations that hinder its competitiveness with large-scale models trained using gradient-based methods. First, although we employ subsampling of activation patterns and propose an iterative filtering scheme (see Appendix F.4), the subsampling process is not exhaustive, which impacts model performance, especially with high-dimensional data. Refining the activation pattern sampling strategy could significantly improve results, Second, we rely on analytic center retrieval during training, which we solve using CVXPY. However, this solution is CPU-bound and becomes inefficient for large-scale problems with many variables. Developing a center-finding algorithm that leverages GPU parallelism is crucial to unlocking the full potential of our training method. Finally, while current large language model (LLM) training often involves cross-entropy loss, our approach has so far been applied only to classification and regression tasks, Extending our method to handle more diverse loss functions presents an exciting avenue for future research.
C. Key Definitions and Deferred Theorems
C.1. Key Definition
A notion central to the linear programming reformulation which enables the feasibility of our proposed cutting-plane based AL method is the notion of hyperplane urrangement. has been briefly introduced in Section 4. We now give a formal definition.
Definition C.1 (Hyperplane Arrangement). A hyperplane arrangement for a dataset X E Raxd, where X contains x; in its rows, is defined as the collection of sign patterns generated by the hyperplanes. Let A denote the set of all possible hyperplane arrangement patterns:
A = (X E R
(8)
where the sign function is applied elementwise to the product Xw.
The number of distinct sign patterns in A is finite, i.e., |-|| < cc. We define a subset S A, representing the collection of sets corresponding the positive signs in each element of A:
S = (U A).
(9)
The cardinality of S, denoted by P, represents the number of regions in the partition of Ed created by hyperplanes passing through the origin and orthogonal to the rows of X, or more birefly, P is the number of regions formed by the hyperplane arrangement.
As the readers may see in the definition, P, the number of regions formed by the hyperplane arrangement, increases with both the dimension and the size of the dataset X. To reduce computational costs of our cutting-plane AL algorithm, as we will discuss in Appendix H.I, we sample the number of regions in the partition instead of using the entire S.
In addition to center of gravity (Definition 6.2) and analytic center (Definition 6.1), another widely-used notion for center is the center of maximum volume inscribed ellipsoid (MVE), which we also referenced in the main text. We hereby give its definition (Boyd& & Vandenberghe, 2004).
Definition C.2 (Maximum volume inscribed cllipsoid (MVE)). Given a convex body C R2d the maximum volume inscribed ellipsoid inside C' is found by solving the below optimization problem:
maximize log det B
subject to sup 1e(e(u)) S0
(10)
||
13

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
where we have parametrized the ellipsoid as the image of the unit ball under an affine transformation:
E(U) == (Bu c: ||u|| - 1}
with c E Id and B E 4. The optimal value of the variable u in the convex program in 10 gives the center of the maximum volume inscribed ellipsoid of the convex body C, which affine invariant. We denote it as (C), or Ow as abbreviation.
metric important to our evaluation for the regression prediction in Section is the notion root mean square error, or RMSE.
Definition C.3 (Root Mean Square Error). The root mean square error (RMSE) is a metric used to measure the difference between predicted values and the actual values in regression model. For set of predicted values S and true values yr. the RMSE is given by:
1
RMSE
U1 y1)
where n is the total number of data points, is is the predicted value, and Y4 is the actual value. RMSE provides an estimate of the standard deviation of the prediction errors (residuals), giving an overall measure of the model's accuracy.
C.2. Key Theorems
Key Theorems in Section 6.2. We present the cornerstone theorem to our results in Section 6.2 given by (Grünbaum, 1960) on the bounds relating convex body partitioning.
Proposition C.4 (Grünbaum's 's Inequality). Let T Rd be convex body (i.e. compact convex set) and let lg denote its center of gravity. Let H far Rd w 0c) = 0} be arbitrary hyperplane passing through 0g. This plane divides the convex body T in the two subsets:
T = {0 T w 0 2 wT TTaah
T2 = 10 E TT: w² 0 < w" 0c).
Then the following relations for 22
(T)) < (1 9/ S 11/e)rol(T))
(I))
Proof. See proof of Theorem 2 in (Grünbaum, 1960).
D. Deferred Algorithms
D.1. More on Cutting-Plane AL for Binary Classification
1.1.1. LINEAR MODEL.
Algorithm describes the original nutting-plane-basee learning algorithm proposed by (Louche & Ralaivola, 2015). This algorithm, despite having pioneered in bridging the classic cutting-plas plann optimization algorithm with active learning for the first time, remains limited to linear decision boundary classification and can only be applied to shallow machine learning models. We have demonstrated its inability to handle nonlinear decision boundaries and simple regression tasks in Section where the linearity of the final decision boundary and prediction returned by the cutting-plane AL algorithm is evident. Nevertheless, Algorithm 3 establishes crucial foundation for the development of our proposed cutting -lanne active learning algorithms (Algorithm 2, 5, 4, and 6).
D.1.2. NN MODEL WITH LIMITED QUERIES
We begin with Algorithm 4, which summarizes our proposed cutting-plas plane active learning algorithm under the second setup discussed in Section 6.1. In this case, the cutting-pla plane oracle has access to limited queries provided by the user and, in
14

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Algorithm 3 Generic (Linear) Cutting-Plaan Peainn AL
1: T - B2
2: t 2+0
3: repeat
4:
f center))(TT)
5: Ine Yn. + QUERY D)
6: if Un, (0' Fnd) < 0 then
7:
T 4 T n ff= Vnu (n.) 2 0}
8:
L 1+1+1
9:
end if
10:
until T' is small enough
11:
return 0%
1: function Query(T, (T, D)
2: Sample M points $ SM from T
3: g M Σi= 8k
4: x arg mi xg,
5: y get label from an expert
6: return y y
7: end function
contrast to its query synthesis alternative (Algorithm 2), only makes the cut if the queried center mis-classifies the returned data point from the oracle. Hence, the convergence speed associated with Algorithm hinges on how often the algorithm queries center which incorrectly classifies the returned queried points before it reaches the optimal classifier. Therefore, the performance of this algorithm in terms of convergence speed depends not only on the geometry of the parameter version space but also on the effectiveness of the Query function to identify points from the limited dataset which gives the most informative evaluation of the queried center.
While Algorithm 4 still maintains similar rate and convergence guarantees as Algorithm 2, to optimize the empirical performance of Algorithm 4 (see discussions in Section 6.2), we therefore modify the Query function to query twice, once for minimal margin and once for maximal margin, maximize the chances of the oracle returned points in correctly identifying mis-classification of the queried center. This modification greatly aids the performance of Algorithm 4, allowing the algorithm to make effective classification given very limited data. This is demonstrated in our experiment results in Section 7.
D.1.3. NN MODEL WITH INEXACT CUT
Algorithm summarizes our proposed cutting-plant plane active learning algorithm under the third setup metioned Section 6.1. Under this scenario, the cutting-plan oracle has access limited queries. However, contrast to Algorithm 4, this cutting-plane AL algorithm always performs the cut regardless of whether the queried center mis-classifies the data point returned by the oracle. This is an interesting extension to consider. On the one hand, it can possibly speed up Algorithm 4 in making a decision boundary as the cut is effective in every iteration. On the other hand, however, the algorithm's 's lack of discern for the correctness of the queried candidate presents a non-trivial challenge to evaluate its convergence rate and whether it still maintains convergence guarantees. It turns out that we can still ensure convergence the case of Algorithm 5, and the convergence rate can be quantified by measuring the "inexactness" of the cut in relation to a cut which directly passes through the queried center. We refer the readers to detailed discussion on this matter Appendix G.3. We would also like to emphasize that Algorithm 2, 5, and 4, although written for binary classification, can be casily extended to multi-class by using, for instance, the "'onevverus--ll strategy. See Appendix E.2 for details.
While it may be intuitive for the optimal performance of the cutting-plane AL algorithms to translate from binary classification to the multi-class case, it is not entirely evident for us to expect similar performance of the algorithms for regression tasks, where the number of classes K + cc. What is surprising is that our cutting- plane AL still maintains its optimal performance on regression tasks, as evidenced by the synthetic toy example using quadratic regression in Section 7. Nevertheless, one can argue that the result not so surprising after all as it to be expected in theory due to intuition explained in Appendix E.2.
15

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Algorithm 4 Cutting-plane AL for Binary Classification with Limited Queries
1: T - B2
2: f 3-D) 0
3: DAL 6
repeat
5: 0% f +-center(T) (T))
6: s (1, -1 do
7: (Imi Mo.) QUERY(T', : D DAL.:
8:
if Une fronndyy (I (.)) < O then
9:
DAI ADD DAL., (Tru you))
10:
T + T {0: Un fumoriagrr (xn C(C(
11:
f 1+t+1
12:
end if
13:
end for
until (D
2 Phudges
15:
return 02
1: function Query(0,s)
2: (x, 3) arg (ww. of ( 0)
3: return (x, y)
4: end function
D.2. More on Cutting-Plane AL for Regression
D.2.1. NN MODEL WITH LIMITED QUERIES
To generalize our classification cutting-plane AL algorithm regression tasks, we need to make some adaptations the cutting criterion and how the cuts being made. As the main body of the algorithm is the same across different setups (e.g. query synthesis, limited query, and inexact cuts) except for minor changes the reader and 5, we only present the cutting-plant AL algorithm for regression under limited query. Algorithm 6 summarizes our proposed algorithm for training regression models via cutting-plane active learning. Here >> 0 is a threshold value for the L2 Lo-norm error chosen by the user. Observe that the new L2-non -nonomm cut of step
see in Algorithm 2,
T++1 T n I1yre
flwo-layer (In, 0)1l C(mm))
consists simply two linear cuts:
S Un,
ptwo-layer layer (Inn 0 <
We can hence still ensure that the version space remains convex after each cut.
D.2.2. LINEAR MODEL
Following the adaptation of our cutting-plane AL from classification to regression tasks, we similarly attempt to adapt the original linear outting-plane AL (Algorithm 3) for regression. Algorithm 7 introduces an e >> 0 threshold to account for the L2-norm error between the predicted value and the actual target. This threshold controls both when a cut is made and the size of the cut. We applied this version of the algorithm (Algorithm 7) in the quadratic regression experiment detailed in Section 7. However, for nonlinear regression such as quadratic regression- approach will necessarily fail. The prediction model (0, in Algorithm 7 linear, whereas the underlying data distribution follows nonlinear relationship. ie.. y = 2 As result, once the query budget starts accumulating nonlinearly distributed data points, no linear predictor can satisfy the regression task's requirements for small values of e.
In particular, after a certain number of iterations f, the cut
T n {0: I| 10, 1212 5e}
will eliminate the entire version space (i.e., 7++ = 9). This occurs because the error between the linear prediction and the nonlinear true values (c.g., y = z²) cannot be reduced sufficiently, disqualifying all linear predictors. This is precisely what we observed in our quadratic regression example in Section After four queries, the algorithm reported infeasibility in
16

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Algorithm 5 Cutting-plane AL for Binary Classification with Inexact Cutting
1: T t B2
2: t 1+0
3: DAL +-
4: repeat
5: 0% c
6: s in (1, -1] do
7:
(Eme yn.) 6- QUERY D DAL: s)
8:
DAL. AD.(DAL.: ( Yys, ))
T + T n {0: Vn. f fuwo-layer
9:
10:
t 1+t+1
11: end for
until [DAL.] 2 Mbudget
return 0%
1: function Query(U,s)
2: (z,y) y) < arg De 8f srwwllayer (Inz 8)
3: return (zc, y)
4: end function
solving for the version space center, as the remaining version space had been reduced to an empty set. This infeasibility is a direct consequence of the mismatch between the linear model's capacity and the data's 's nonlinear nature.
Algorithm 7 Linear Cutting-Plann AL for Regression
1:
T + B2
2: 4
3: DAL. 4-0
4: repeat
5:
0e + center(T"))
6:
Ine Mn, +- QTE ,D)
7:
if Ill (0c, Ins) 1|2 > then
8:
T t T n {0: I1ym. (8, xn.) 1a2 $ c}
9:
1+++1
10:
end if
11:
until [Dar_
Thndge
return 0'
1:
function Query(T, D)
2:
Sample M points $1...., 8M from T
3: <
Σイ=1>h 8t
4: arg mill,ee nx)
5: y get label from expert
6: return x.
7:
end function
D.3. Minimal Margin Query Strategy
Here we note that in our main algorithm 2, we always query points with highest prediction confidence by setting
(a, v)
arg min of fww.layyr (zn.: 8).
Dgs
However, we indeed allow more custom implementation of query selection. For example, an alternative approach is to select data with minimal prediction margin, i.e.
(xr, v) + arg min I ; 0)].
17

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Algorithm 6 Cutting-plane AL for Regression with Limited Queries
1: T - B2
2: f 4-D) 0
3: DAL 6
4: repeat
5: 0% f +-center(1 T
6: s (1, 1 do
7: (Imi Mo.) QUERY(T', D DAL.;
8:
if Un. fron (I 02)112 2 then
9:
DAI (DD.(DAL. (Tmu Yus))
10:
T + T n {0: ll - prwwrlayer (Ine 0)1
11:
f 1+t+1
12:
end if
13:
end for
until A
2 Phodges
15:
return 02
1: function Query(0,s)
2: (x, v) arg (mnn of layel (Xne
3: return (x, y)
4: end function
We experiment with this query strategy in our real dataset experiments.
E. Key Generalization to Cutting-Plane AL
In this section, discuss two important generalizations of our cutting-plane AL method: (i). the relaxation in data distribution requirement and (ii). the extension from classification to regression.
E.1. Relaxed Data Distribution Requirement
For linear classifier f(x;0) = 0, the training data expected be linearly separable for an optimal 0* to exist. However, this constraint on training data distribution is too restrictive in real scenarios. With ReLU model, due to its uniform approximation capacity, the training data is not required to be linearly separable as long as there is continuous function h such that sign(/(<r) thus we can totally remove the prerequisite on training data. For sake of completeness, we provide a version of uniform approximation capacity of ReLU below, with an extended discussion about a sample compression perspective of our cutting- plane based model training scheme thereafter. Given the fact that two-layer model has weaker approximation capacity compared deeper models, here consider only two-layer model without loss of generality. Uniform approximation capacity of single hidden layer NN has been heavily studied (Chen & Chen, 1993; Chui & Li, 1992: Costarelli et al., 2013; Cotter, 1990; Cybenko, 1989; ichi Funahashi, 1989; Gallant & White, 1988; Hornik, 1991; Mhaskar & Micchelli, 1992: Leshno et al., 1993; Pinkus, 1999), here we present the version of ReLU network which we find most explicit and close to our setting.
for all (I, y) pairs. Due to the discrete nature of sampled data points, this is always satisfiable,
Theorem E. (Theorem 1.1 in (Shen et al., 2022)) For any continuous functiinn f E C((O, 1) there exists a two-layer ReLU network o = (xW, + b,)+ W, + b2 such that
Il *1L= E O (Venna (mm -))1/))
where w.(:) is the modulus of continuity of f-
The above result can be extended any f C([-R. R) see Theorem 2.5 in (Shen al., 2022) for discussion. Therefore, for any fixed dimension d, as we increase number of hidden neurons, we are guaranteed to approximate ʃ a.e. (under proper condition on w Thus the assumption on training data can be relaxed to existence of some {W1, b, W2, b2) such that sign()(=)) = y. which happens almost surely. A minor discrepancy here that the á being considered in above Theorem incorporates the bias terms b,, by while our Theorem 4.1 considers two-layer NN of form (xW1) + W2. We note here that (xWi) + W2 essentially the same as the one with layer-wise bias. To see this, we can append the data x by a 1-value entry
18

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
accommodate for b1- After this modification, we can always separate neuron of form (XW1)) W26 set 1 and zeros elsewhere, and W2: would then accommodate for bias 82- Therefore, our relaxed requirement training data still persists. For deeper ReLU NNs, similar uniform approximation capability has been established priorly and furthermore the general NN form we considered in Theorem 4.2 incorporates the form with layer-wise bias and thus we still have such relaxation on training data distribution, see Appendix F.3 for more explanation.
E.2. From Classification to Regression
Algorithm/ 2 shows how we train deep NN for binary classification task with cutting-plan method. Nevertheless, it can be easily extended to multi-class using, for instance, the so-called "one-versus-all classification strategy. To illustrate, to extend the binary classifier to handle K classes under this approach, we decompose the multi-class problem into K binary subproblems. Specifically, for each class Cx. we define a binary classification task as:
Classify between C2 and UC
where we classify Cs against all other classes combined as a single class. This creates binary classification problems, each corresponding to distinguishing one class from the rest.
In fact, cutting-plane AL can be even applied to the case of regression, where the number of classes K + co. The core intuition behind this is still the uniform approximation capability of nonlinear ReLU model. Given any training data x with its label we want a model fa; 0) to be able to predict y exactly. Here the data label is no longer limited to plus or minus one and can be any continuous real number. For linear model f(x; 0) = xTe f considered in (Louche & Ralaivola, 2015), train such a predictor is almost impossible since it is highly unlikely there exists such a for real dataset. However, with our ReLU model, we are guaranteed there is a set of NN weights that would serve as desired predictor due to its uniform approximation capacity.
Therefore, for regression task, the training algorithm will be exactly the same Algorithm 3 instead that the original classification cut unchanged. A minor discrepancy here is that though theoretically sounding, the strict inequality f(Inii 0) = yn, may raise numerical issues in practical implementation. Thus, we always include a trust region as yo. é S f (Inn; 0) S yo. + with some small for our experiments. See Algorithm for our implementation details.
0) 21 1 will be replaced with [ 0) Dn,- All other activation pattern constraints are leaved
F. Deferred Proofs and Extensions in Section 4
F.1. Proof of Theorem 4.1
We prove the equivalence in two directions, we first show that if there exists W1, W2 to y O ((XW1)+W2) 2 1, then can find solution {u,, 2{} to Problem (3); we then show that when there is solution (u,, ut} to Problem (3) and the number of hidden neurons m 2 2P, then there exists Wi, W2 such that y @ ((XW1)+ W2) 2 1. We last show that given solution fu,, wf} to Problem (3), after finding correspondent W1, W2, the prediction for any input can be simply computed by > (iu;) (zu()+. We now start with our first part and assume the existence of W,, W2 to y O ((XW)) W2) 2 1, i...
m y 0
(XW1,) W23 21,
j=1
from which we can derive
Σ DWXWW 21,
(12)
where D = diag( (1 > 0}) E Raxn, Now consider set of pairs of {uz, u²} given by u Wi, 22, n/f = for
j E [j] W25 2 0} and uy = 0, u/y = - WWy forj Wil < 0}. We thus have by (12)
m
y C
D X(u, v/)) 2 1, (2D) I)Xu, 20 (2D) nxx,, 2 0.
1=1
19

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
The only discrepancy between our of (uy, (1y) pairs and desired solution to Problem (3) is match Dj's in equation (12) to D in Problem (3). This achieved by observing that whenever we have D2 Dj = (aa,) for some a. E [m]] we can merge them as
Dy - u'a) + Dbb - r/H)) D(a,)) ((Uua + ub) (1/2 + u/))) D(a,b) X ((uotb w/tb0;
with (a+b) 1)x and (2D 1)X uatb patterns {D)lj [m]}. We guaranteed to get
0 still hold. We can keep this merging for all activation
y ④
Dj -ijū((jj@)) - 7/) 2 1,0, - X) 2 0, (2 T)x 0
[mm] different. Note since our Diili [P]} in Problem (3) loop over all possible activation patterns corresponding X, is always the case that m - and Dj D; for some i [P]. Thus we get solution {u,, u/} to Problem (3) by setting 14 = ūg, v/ iiyy when D; = Dr for some E [m]. Otherwise we simply set u4 = ' = 0. This completes our proof of the first direction, we now turn to prove the second direction and assume that there is solution fu, uf} to Problem (3) as well as the number of hidden neurons m 2P. We aim show that there exists W1, W2 such that y @ ((XW))+ W2) 2 1. Since we have
where all D E
P Σ
O
DiX(u, - -4) 1, - I)Xu, 2 2,D2,, 1)X14 2 0,
we are able to derive the below inequality by setting = 4j = 1 for E [P] and 2/ uk_ = - [P+1,2P]
2P
y O Σ (xu))+a; 2 1.
Therefore, consider Wi Raxm defined by Wij = Vy for j E (2P) and Wij 0 for any j 2P, W2 R defined by W2i aj for E [2P] and W2j 0 for any j > 2P. Then achieve
2P
y @ (2xW - y > 2x
as desired. Lastly, once a solution {u,, u4} to Problem (3) is given, we can find corresponding W1, W2 according to our analysis of second direction above. Then for any input ž, the prediction given by (iW1)+ W2 is simply Σ (Zu:)+ (zu()+.
E.2. Proof of Theorem 4.2
Similar proof of Theorem 1.1, carry out the proof in two directions. We prove first that if there exists solution to Problem (4), then there is also solution to Problem (5). We then show that whenever there exists solution to Problem (5), there is also solution to Problem (4). Concerned with that the notation complexity of (n + 1)-layer NN might introduce difficulty to follow the proof, we start with showing three-layer case as concrete example, we then move on to (n+ 1)-layer proof which is more arbitrary.
Proof for three-layer. The three-layer ReLU model being considered is of the form (XW1), W3. The corresponding
20

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
linear program is given by
find
Uijs ukys Vig. o/y
P2
P
Pi
Σ 2)
Σ
D.D (uus - u/j) - Σ 1 ((1y-1(6)) b//)) 2 1,
s.t. 0
1=1
i=1
(2D (1)
N) 2 0, (2D - -() 2 0, (2D - -1)X 2 0, (2D, - -1)Xi's 2 0,
P7
(2D 1)
Σ 1 ((us - n4()) 2 0, (2D, -
Σ
X(vi) D x - v//)) 20 0,
which is a rewrite of (5) with n = 2. Firstly, assume there exists solution { 22, Wz} to the problem y o
(2)))+ W3 2 1. We want to show there exists {ui, uhy, Vig b/y} solves the above problem. Note that by y @ (XXW)) Ws 2 1, we get
mi Σ
y O
(XW1)) Wei
W3 2
Let K2 denote Lign(WWi,) i., (2K, - 1) 2 0, we can write
y 0
Σ
K K,XW
Wa 21 1.
Expand on the outer layer neurons, we get
172/
O
Σ
K;XWi, W265
Waj 2 1.
Construct Cjj W2,W2i whenever W2i 2 0 and 0 otherwise, di ----We WW Wir whenever Way 0 and 0 otherwise, can write mgg
mi
K;X (ci - (1) Waj 1,(2, Xoy (2K: 1)x6 2 0.
y
Denote sign
E K2X (cij-
4) as K,² we thus have
mg
mi
(2)
Σ
KiX(eu- -4,) Waj 11
y
with (2K; 1)x 2 0, (2K, - nxd, 2 0, (2K
- n Ty K2X(ce (3)) 2 0. We construct {dij, d'y, eij. ebpy
by setting d, = Gy Waj, dyy = cy W3j when Waj 2 0 and 0 otherwise, setting Gij = -ca -ayWaaj Shjseely e'e = - c, Waj when Wa < 0 and 0 otherwise, and we will arrive at
KP (2)
KiX - d2y) Σ Σ
K2X(ee - -66) 21,
V 2
1=1
1=1
where
(2K; (2K:-1)X0 (2X:-1 2 0, (2K; - 1)Xd, 20, (2K; - 1]Xei 2 0, (2K, - 1)Xe's 20
m1
my
(2K - 1) Σ K2X d,y) 2 0, (2x 1) Σ K2X(ei 41) 20,
which is already of form we want. We are left with matching m. with P; for i E [1 and matching DJ to (2) D(") to Ke, (uig uly, Vig. ('g) to (dij, d'y, Ctj, d We achieve this by observing that whenever there is duplicate K k(²) (2
21

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
we can merge the corresponding terms as
K
(2)
mi
K2X (dij - dirr) Σ KiX(e - -dte)) + (2)
m1
XiX(dis; - -d12) - -
KeX(e - -c(p))
i=1
m1
((2))
Σ
K2X ((de) + dijz)) - -(dij + +(jze))
Σ KiX (leys + +eitz) - -(éi + t((za))
(i1d5)
mi K2X ((X(di(i+5a) - di(istse))
m2
-1(2) (i1d2)
Σ 1=1
((X((1()45)) - (h61t22))
where K
p digi+t)) := -dis + ddija oi ((1+)))) = d'ig. + dajs (1(1+t2)) = Eij: + Cijze ((1+52)) = -gg +efe
(2)
We have as constraints
(2K (iida) 1)
K2 (dd(iii)))))) - diGitsal) Σ
2 00
(2 (1ida) 1)
K;X(er(itja) (it
2 0,
(2K, T)X ()xd 2 0, (2K, - (x
2 0,
(2K; T)xe 2 0, (2K; T)X ((1+)2))) 2
Keep such merging until all k are different, we arrive at
mi
K2X (dis - -kyy Σ
m
KiX - -E6) 21.
y
with
(2K; - xd 2 0, (2K; - 1)xd( 2 0, (2K; - 1). 2 0, O2K, - 11)xe' 20,
(2k)) (2) - 1)
Σ x(x / 2 (2K 1)
Σ K - {ss
20,
where m2 S P2, K E (D(2)) and k all different. We now proceed to match K; and D. Consider Em K2X(d.g
d.). if K. Kg for some U, q, we can merge them as
(do d.y)) + K2 KgX(du) - dug) = K(v.g) X (d(wta)) dottrz)
where K(v,g) = Kr, (ot == Juj + day Tayd(otoss = dug + d'oooss The constraints are (2K (v.9) - T)xd 2 0, (2Kr.g T)Xe(u+0)s 2 0, and we still have
(2K(0)-1) (2) 11)
Σ
K;X(de) - diz))
dusenr) 2 0.
VElmul.ate.i44
Continue such merging and also for {Cij, dy we finally arrive at
mg
m (d, ر,ي Σ R.x - 2
(2)
y
m=l
with
(2R; - x) 2 (2R; nxxă, 2 0, (2K; - T)Xes 2 20 n)xe's 20,
(2 - 1)
Σ xā, - = 2 0, (2R - 1)
Σ
kix(es - {E6) 20.
22

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Now, for any D $ {K* we set all Uij = V/j = Vij = f/y = 0. For D.3)) = Kz. y for any D.") & {K}, we set all
Mij = un =1- = J/jj = O. For D = R 3 D = RR, we set Uaj = =d 1// = dezg, Uej = Eeg, 1/y = Egz. Then we get exactly
Pi
(1) X(ei) X - -06)) -2.1)) 1,
O
Σ 1=1
2)
Σ
D. X(uy (n/)) Σ
D
i=1
and
(2D (1) - uij 2 (2D. ()) T)Xid 2 0, (2D( 1) 2 (2D 1)x 20, 0,
P7
(2D 1)
Σ
DJ X(us - -v/g) - 20, 1) D. D..Tx(1s - -bb) 20,
which completes the proof of our first direction. We now turn on to prove the second direction, assume there exists Wej, u Vig. V'y such that
P2
Pi
Pi Σ
11) D. X(eis - - 21,
O
Σ
D
Σ
D
0 X(us
i=1
with
(2 (2) - uig 2 0, (2D)1)) T)x 2 0, (2D1()) 1)) 2 2, -1)xoly 2 0,
(2D 1)
Σ
Pi
(ux
- uky)) 2 0, (2(2)))) - 1)
Σ DiX - -06) 2 0.
P1
i=1
We want to show that there exists W1, W2, W3 such that
y o (1XW))
We are able to derive
P2
P
D&X (ui (mn))
Σ
P (
(iX v(5) ) 21, )
y
and furthermore
Ps
P
P
Σ
X [uug)+ - -1116)+
Σ (Xug)+ ((xr)) 21.
yo 2
We thus construct (Magj anj } by setting Mej uij, Oij = 1 for i [Pi], Kij u/ii ai = -1 1 for [P] + 1.2P]
We similarly construct (klg: a with (ue J. we thus get
Ps
2P
2P
y O
Σ
Σ
X (Kkis)
-
Σ ( (kkg))+dk
21. 1.
+
We construct {uj} by setting uj- 1 for j E [Pa] and uj -1 for j E [P + 1,273) We construct also {Rej, ānj) such
that Riz- = Kej, āij au for i E [2Pr],j E [P2], Ray = K())rr)) :3); ãis = d()r)s) fori [2P]].j E [P2 + 1,2P),, we thus get
2P
2P
Σ
Σ
(Xx))+
uj
21
+
Therefore, we arrive at O (_ W2) W3 2 1 by focusing on j < 2P, i < Pp. i.e., setting parameters with
(i.j) indices exceeding these thresholds to be all zero. We then set W1: = Rab for a = L2n + 1, = (i - 1)%2P; + 1, Way = ((1-1)82P.41 for E [(j - 1) 2P, + 1.j 2P:) and O otherwise, Waj Uj-
23

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Proof for n + 1-layer. We now provide proof for ReLU model of arbitrary depth. The logic follows the three-layer case proof above, despite the notation now represents + 1-layer model for arbitrary n. We first assume that there exists WI, W2,- ... Wn that satisfies problem (4). We want to show that there exists jaan) which satisfies problem (5). We first span the inner most neuron to get
y O
Σ (XW16 W
W3
W4
Ws ....
Wn+1 2 1.
Denote (ign(XW(1) as k i... (2K - 11. 2 0. We can then rewrite the above inequality as
y +
Σ
K XW1, W2n1
W
W4
W6 ...
Wn+1 21. 1.
+
+
+
We then expand the second last inner layer
(
Σ
Σ
( XW1, W2inig
Wsia
Wa
W3 ...
Wa+1 2 1.
+
We construct {b (0()) } such that b W1,, W2 when W2 2 0 and 0 otherwise, (( W W2iri < 0 and 0 otherwise. Therefore we get
W16, W25n when
5162
((
O 1...
Σ
Σ
m1
1122
(1)
5182)
W3i2
W4
W....
Wn+1 2 1,
with constraints (2K (1) - 1)x6
2 0, (2K [1] -1ix 2 0. Let k22) denote sign
(>
m K (1) x - -b )), i.e.
(2K?2) 12 r)
mi ((')
x(b
{(1)) )) 2 0, we thus have
1122
m
K (2)
Σ
K
(1) X
(10)
Weis
W4
Wo...
Wn+1 2
11=1
+ +
with constraints
m1 K( x((()) - b((1te) 20. 0. Σ
(2K
-IXb 11
2 0, (2K 1)xx(1 116
2 0, (2K - I)
Expand one more hidden layer
ma
m2
mi
Σ
Σ
(222)
Σ
k(())
X
(1()) f112
W Wsisis
Waig
W5...
Wa+1 2 1.
i
1==1
11=1
11=1
+
Construct {6 (igggis o (11))
(1I)
igrgis J by setting
6
(II)
1140 Waizes and (((11) b((l)) Waighs when Waitks 2 0 and 0 otherwise.
fif2ds
6112
Construct ( indgig) } by setting
((2))
(12)
(1 Waints and (2(2))
_1((2) W Wiggis when W sizts < 0 and 0
otherwise. Let K. (3)
denotes sign( /
m2
(2)
-m= K ((1))) ((ll Wiinss) Thus we have
mi
(1)
=1
mg
mg
m
y
is
(3)
K
12
(2)
k
X
(1)) (((1))
irizés)
11=1
-1
(2)
X
(2)
- -b((ee)
Waes
Ws ...
Wn+1 2 1,
b,
24

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
with constraints
(2K
T)xb
(1))
2 0, (2K. x)
2
i1
F1i2is
(2K 11
1)xb,
(12)
2 0, (2K 1)
2 0.
116210
(2k (2) 1)
Σ
m
K
X
1
)
2 0, (2K (2)
-1)
Σ
m
k X
(12)
- -b((2))
E1128s) ))
20,
1122is
11=
m2g
))
(2K (3)
I)
Σ
K
(2)
K 1 X
(11)
(2)
K x
i112is
(122)
2 0.
1==1
For cleanness, we introduce the following notation, for any e E (1, 2) and 2 2 n - 1,
m2
(0 T
k/!0² (Tee ((==-))(-)))-(0(06-1
hhu pn 1=1| (k(o-1)) ((n-1)(n-2) 2)- (0-))-))))))))
oo 1c 2 1=2 (K(1-1)))
When s= 1,
T Cn-16a----aa
())-)-2))--11111 (K(1))= = Σ
(:(1) 11
x
1 1-111
(en- (aa--inn-- (n-2))))))
inin 111
1=1
Proceed with the above splitting, under the newly defined notation, we will get
(n) in
(I(1-)))
-T," -2
(K 21
y
with constraints
(2K!
T)T n- (n=1)(n2))..)))
(K(6-11) 2 0,42 S 8 8 1,
(2K!!) b1 1)Xb (0--16m----01 2 0, (2X 1|Xb ( (cm-1en-2 2c)
2
',
in 1
Note we already have the form of (5) by combine -11---1--1
(())))))))))))) } and {b (o 10-0011n - 2)) into (b (n 10,- 101-2"001)) (nta-1nt
}. the
only thing left is to match { {x)*)} with (D("),, we do this by recursion. Consider any layer I, assume all (K(*), ), S I can be matched with {D()),, n < l. Now we consider the (1 + 1)-th layer. Note that all K (!-1)) E (D(+t) for any it+1 E [m=+1]. If there is duplicate neuron activation patterns, i.e., K_ k((+1) K
(1+1) for some 4 b, b, E [m++]]. Then we merge all lower-level neurons corresponding to ((((+1) and K. k-(++1) by summing up the corresponding (with respect to i1,12, ,,,,,.,;; i indices) vectors. Both the layer output and ReLU sign constraints will be preserved for all layers up to (I+ 1)-th layer, and we thus get, after the merging, a new set of {K(++)) and (b} that matches the problem (5) up to layer (1+ 1), where we just set all parameters be zero for any Ji+1 E [P++1] such that Djys & (K(41)). Now, only need to (6-116-----) terms, consider without
verify that the last inner layer's neuron can be matched. By the symmetry between b 1n loss of generality the neuron
mi
k Xb (cn 1=1[(s- 2 [-1]-
(13)
1-
1=
which we want to match with
P.
Σ
D X Xul
-| ji
(14)
1"11
=1=1
Note by construction know K."h (D(1) for any i E [m1]. If there is any duplicate neurons K:!)) K(D (1) for
some A d, d E [mi]. We denote ((0) K(D) K Let f:1-..1
b11-.11 - + b [6
111...1
Then we merge k!!)) and K. by replacing them with only one copy of K k(2)
(c.d) and set the corresponding vector to be
- Continue this process until there is no duplicate neurons in the last inner layer. We are guaranteed to get a set of (K( and corresponding (b!l.--1 (b i such that K-(1) belong to (D(1) and are all different. Now assume
25

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
all outer layers have already been merged by the scheme of summing up corresponding b vectors mentioned above. Using {ms, k(s), b} represent the new set of parameters. Then is [mm]] with ri, I P.. The expressions (13) and (14) can be
!!!! matched by setting / jjad-11-jj = 6 1- 1 for i,) pairs satisfying D) = R and setting to zero if ( Ja &f [R(
This completes our first direction proof.
We now assume that there exists (" rh weights W1, W2,,.- Wn+1 satisfying (4). Since our jahh- satisfies all plane arrangement constraints in (5), we thus have, based on the inner most layer's activation pattern constraint and splits (MnInni-. 1""0h } into u tn 2n101
( I which satisfies problem (5), our goal is to find (n 1)-layer NN
(on=1]en-10n-22 U 10-111n2-0
(en 2/0 210--10 16
3nJa-1"'11
u Inin-1"'Jh
Pn-1
D m)
D (n-1)
Σ
(Xu (Xugam)))+ - (Xu (Xud.
(l...1 in (omnis)
y
jn
in 1
51m1
Pa
(X (Ku3..) Jannii )+ - (X fnennt) )) 21.
D 1)
jn-1=1
==
Thus we can find some "jiji E Rd ((1) 5(2)
((a) E {-1,,1 13 such that
31
Pa
(n)
(
(D - T, (n (D(n-1)))
Jn
Jn 11
2P
2P
2P
2P:
2P
Σ
Σ
Σ
(X Us in s+
(15)
jn 1=
fn-1=1
jn-2=1
J==1
n==1
s/2
..... s/mm2)
s(m-1)
s(())
Though the process of finding {Vim.h / has been outlined in three-layer case proof above and can be extended to (n + 1)-layer case, we present here an outline of finding such "ijnin--''' 5500 for five-layer NN for demonstration. For
n = 5, we have the following
Pr
P2
P
Σ
Σ
(Xa
Jainini) - (Xa" 1111
II
ietnnasi )+
Σ
(Xa
jndassi )+ (Xa 112 juiseen )+
1==1
1==1
j==1
+
Ps
X 121
juishan )+ (X 121
isiainn )+
Σ
(Xa 122
Jahaian )+ (Xa 122
122 sanaeent
P3
P 212
(X 211
Suiaiin (Xa
satatasi+
(X
Jahiiin) (Xa 212
ishaian) )+
12
j1=1
Σ X 221
)4ssian (x 221 jasahnn )+
(X 222
Juhian (Xa 222 saiatait
Let Uill
( U {a" 1111
122 jajajan } and similarly construct Vajaaaan J4jajaj1 jafajaji
11
121
211
212
221 222
Let sill 5112 5121 S122 s211, 5212 ; 5921, 5222 to be 1 for fi E [P] and to be for J1
" "ataiani"
hn ; "1 in in ;
26

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
[P] + 1, Thus, the above expression is equivalent
P4
Pg
2P
2n
Σ
(X 111
S111
Σ
(X 112 112
S412
3438fadi
J433fadh
Jam1
J2
51
Pg
2/
2
(X 121
juzaiah S121
(X (X 122
S122
Jusiiah
P3
P2
2h
2h 212
(X 211
S 535
Σ
(x
Jaistahi S312
Jaisdahi
1==1
J==1
f==1
1==
2P
2B
(X 221 221
Jusajah S222
(X 222
Jusaihh S222
S22
Let 0 11 Jadatadh Jaistah
J
[1i1
"Jasihh and $11
511 Let St = 1 for j2 E [Pa] and 52 -1 1 for j2 E [P2 + 1, 1P). 521
Similarly construct 212
112 512 21
S21 22 822 S32 Thus the above expression is equivalent to
ji j2 Junhjj in jainieji
21%
2h
21% Σ
2n
(X jataaa
S11
211
S
(X
Jussian )+
512 51
212 S
14
ja
jo
d2
+
P'
254
2B
2/
28
X 21
521
221
Σ
Σ
(X
522
222
Jadadasi
J2
Jadajash
j2
ja
Ja
j2
2 juisish U {v32 Jujaish J. Let Sy. = 311
(2)
Let o) Dj2
juinin =
{wll
jnjsizh U {u)2
juisinh }. 2 jasnn =
S = 51
521 Let
, 5(2)
S Let further 5(1) 3a to take value 1 for ja E [P'] and take value - 1 for ja E [P + 1, 1.2P3.
12 Therefore the above expression equivalent to
P
2P Σ
201
(X 1
((L)
((1)
(1)
52
js
14=1
+
+
2
(X
4 f
(2)
(2))
(2)
J2
29
We once again repeat the above procedure for the outer most layer and we arrive
(1) Junnnnn
Σ
Σ (X
)
(())
((1)
S/a5
ja
f==1
where S% for ja E [Pa] and -1 otherwise. This completes our construction of (1 1-- 5(00 for = 5. Now, we are left with matching the following two expressions
2P
2P -1
2P 2
21
Σ
Σ
)+
5
5(n-2)
s(x-1)
(())
in
jn
==
fn-1=1
jn -==2=1
===1
27

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
and
ma
Mn-1
2
m2
Σ
Σ
Σ
Σ
(XW kWWi)+W2ss
Waistz ... W W(m-1))n----
W Wninin-
Fn
fn-2=1
This can be done by setting all weights corresponding to indices {ún > 2P hn-1 4PmP .4k > II 2Pp) to be all zeros, then for the outer most layer, we set W W(n+1)i, = = for 2 S k S n, we set Wkinin-1 = s(k-1) ((8-1-111%2PP-11
for 1-1 E [(i 1) 2P + 1, 11 and 0 otherwise. For the inner most layer, set Win, Ujntn-inch with
jn L(i 1p + +1,
Jn = L((01 - 1 +1,
Jn-2 2 = L(((01 -
+1,
j2 = (11--))9110 +1,
J1 ((..,)) 2P, +1.
Given any test point ă E gd, the final prediction can be computed by
Pn
T T (D(u-t))) - - -(T:-- (D(m-1))
1 =
(16)
m1
where
P.
T T(n-!)- (1) (D(1))
Σ
((n-1)_.((()-- (D(())))())))) - - ((-1)))-()(-1))) (D(i
Te "
1
Pi
((=-1)(n2))--11) 1
(D())
2 a lon- )) Inin-i-11))
(i"
201-1-001 Injn-1nf1
21
E33 Explanation of Bias Term for General Case
To show that the n-layer NN of form ((--- (XW1)+ W2) W3.. W W,n+)),W, preserves the same approximation capacity as the biased version ((... ((XW1 + b,b + b2) W3 + by...) )) Wn- bn-1)+ W,, + ò,, we show that the biased when the constraint on number of hidden neurons is mild. First note that we can always append the data matrix X with column of ones to incorporate the inner most bias by. Then for each outer layer, we can always have an inner neuron to be a pure bias neuron with value one. Then the corresponding outer neuron weight would serve as an outer layer bias.
version is incorporated in the form ((-- ((XW) W2) ....) W....) wn-1)+W.
F.4. Activation Pattern Subsampling and Iterative Filtering.
Here we detail more about our hyperplane selection scheme. Take two-layer ReL.U model for example, in order to find the activation pattern corresponding to the hidden layer, one needs to exhaust the set (diag(1 2 0})} for all E Id In our experiments, we adopt a heuristic subsampling procedure, i.e., we usually set moderate number of hidden neurons mi. and we sample set of Gaussian random vectors {u,, u2, Un, with some random nı > mi. Then we take the set (diag(1 (Xu, ) E [mı]). If [diag( 1 (Xu; 2 O)) E [mı]}] mi, take subset of m, activation patterns there, if not, we increase nı and redo all prior steps until we hit some satisfactory n1. This heuristic method always works well in our experiments, see Appendix H.1 for more about our implementation details.
A more rigorous way which exhausts all possible activation patterns can be done via an iterative filtering procedure. We demonstrate here for a toy example. Consider still two-layer model as before, when we are given a data set X of size n, a loose upper bound on [D] is given by 2n, i.e., each piece of data can take either positive and negative values and they are all
28

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
independent. Thus one can find all possible D is by solving
2
find
Σ
Jull 12
s.t. (2D;
I)xx; 0,114,12
where Dj's loop over all 2" possibilities. Then the D,'s correspond to non-zero u, 's in the solution are feasible plane arrangements. However, this method induces 2 x variables. A more economic way to find all feasible arrangements to do an iterative filtering with each newly added data. When there is only one non-zero data point X1, there always exists U U2 vectors such that Xf un > 0 and Xf u2 0. Thus D {[1] [0]} represent all possible sign patterns for this single training data. After the second data point has been added, we know
{ {0000 9
11111
00
0
0
D2 S
1
0
0
0
1
0
Therefore, an upper bound on cardinality of D2 given by 2 4. However, this upper bound might be pessimistic, for example, if X1 = X2, then we would expect
: -
D2 = {b
1010
1 1
(b
0
0
0 0
0 0}
1
0
Since Xf'u X u for any u, they will always have the same sign pattern. Things get more complicated with more data points, say for data points X2, .X,, it is possible that sign pattern of X,, u can be determined by sign patterns of XF u. Xy u.... X x 1 when there linear dependency between the data points, which happens more often with larger set of training data. Thus the true cardinality of D, might be far smaller than 2", Indeed, one can show that, with denoting rank of the training data matrix consisting of the first data points (Pilanci & Ergen, 2020; Stanley et al., 2004),
c (dn=-1))
Dr.l S 2r
which can be much smaller than our pessimistic bound 2" especially when training data has small rank. To stay close to the optimal cardinality and avoid solving an optimization problem with 2" + d number of variables, what one can do is to find the feasible plane arrangements iteratively at the time when each single data point added. The underline logic is that plane arrangement patterns which are infeasible to X[1:-1] will also be infeasible to Xpa)-- Therefore, assume one has already found the optimal sign patterns D.-1 for the first t training samples which has cardinality Ct-1, when X₃ arrives, one needs to solve the following auxiliary problem
2c
find
||ull
D P(t-i) 1)i
0
01
2
-1
Xu, 2 0, .--1l
0
1ji-1
0
1 -1) Xu; 2 0,i (a-1 + I, 20--1]
2
|| la
1,
which has only (2 c--1) d number of variables and can be far fewer than 2 d. This scheme also be done lazily each fixed T iterations, one just add all {0, 1)- -ppaternss for the last T data points.
G. Deferred Proofs and Extensions in Section 6
G.1. Deferred Proof of Theorem 6.3
Proof. Notice that the polyhedron cut is simply three consecutive cuts with three hyperplanes:
Hi : {0: yn powo-layer (n.T; 0) = =0]:
29

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
H2 {0= (2D; Dn 0):
H3 {60: (2D; 1 0),
where 8 (0") denotes the reduced θ (u/, u1, ...., 2/ Up) vector containing only the odd (even) indices. Since the cuts imposed by the linear inequality constraints C, and C2 via hyper-planes H2, H3 only reduce the remaining set T, examining the volume remained after just the cut via 7/1 suffices for the convergence analysis as it bounds vol( from above.
Assuming the cut is active, it follows that 8G misclassifies (Zn, Vn.). so Yn 0g is in the interior of T2. By Proposition C.4, it follows that
flwo-layer (Zpi 0) < 0. Thus, the cut is deep and
(T n h1+h vol(TnHE S (1 (01-1/e)vool 1/e)
where Hg is any hyperplane that goes through 0g which is parallel to H11 Therefore, at each step t where the cut is active, at least volume of magnitude voo( is cut away. The volume of T after i iterations is bounded by:
vol(T') < (1 1/e)* vo)(
Then as f + oo, (1 - 1/e)* + 0, it follows that vT" converges to zero and the feasible region shrinks to point(s).
Notice that since T is convex body and { is a nested decreasing sequence of convex set with 7 C TT', by the finite intersection property. the intersection of all T sets is non-empty and contains the optimal solution f*:
T {0"}.
remains to justify that what the intersection contains is indeed the optimal solution. To see this, observe that the problem that Algorithm 4 simply a feasibility problem. Since every time the convex set shrinks by intersecting with the constraint set containing feasibility criteria given each new acquired data point (Im,, Vn.), i...
(0
T U/. ftwo-lhyer (a,, 0) > 0, C(())) C' ((n))),
the set shrinks to a finer set that satisfies increasingly more constraints posed by additional acquired data points. This monotonic improvement with the shrinking feasible region implies that the sequence of classifiers 0' converges to the set of optimal classifiers {0*}.
G.2. Deferred Proof of Corollary 6.4
Proof. We show that the volumetric shrinkage in Theorem 6.3 implics convergence of the prediction function plwo-laye layer lokk)
to
the optimal decision function fg" elwo-layer
Let X E gaxd be fixed data matrix. The two-layer ReLU network prediction function can be expressed
I two-layer (X)= = Σ DeX(ul 1 u.),
(17)
where = (u', u1,..., u/y, up) E PR2 is the parameter vector, and each u,, uf E Rd. Define wy : uf - Uy and similarly w/ = u/" ui where 8* denotes the limiting parameter.
Let ((h) E (T()) denote the center of gravity of the parameter set at iteration k. We aim to show:
|| elwo-layer (X)
fg. (exxolaae(((X)) - 0 +
Decomposition of prediction difference.
Expanding the difference between predictions:
fl for (X))l2
Σ
D (k) Xw
(K)
2
P
P (M) -w,)+ + Σ (D( - D2)
x
X(w
P |1(D{*) D7)Xwil12.
| (k) X X(w; (k)
w
30

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Here ( and D are diagonal matrices in {0, 1 encoding the ReLU activation pattern of the i-th unit.
Bounding the first term. Since ( is diagonal with operator norm 1, we have:
D X(w: w S || [|w!
w 22
and summing over i:
Σ
D (k) X(w wflle S |X _ Ioo
w 112-
By Schwarz:
1/2
Σ
1o (k) - wlll2 I vP.
Σ (1)))) - wu:12
Bounding the second term. The activation pattern 1 determined by the sign of Xu (R) Over the finite dataset X, there are only finitely many sign patterns:
H { (sign(Xw) w w R²), |7| xc.
(18)
Thus, D; is piecewise constant with respect to w,, and therefore locally constant almost everywhere. Since w - w.,, we conclude that for sufficiently large k; have D. D implying
[1D!! X = 0.
Conclusion. Combining the bounds, we have:
1/2
P we
Il (X) - fo- (X)]l S |X vP.
mml
(K)
112
+ o(1),
where the (1) term accounts for the vanishing contribution from activation pattern differences.
Finally, since the volumetric convergence guarantees ((k) + 0", and hence (k) + wf,, it follows that
||
tww-layer (X) - - Ltwo-layer (X) + O.
g())
G.3. Extension to Algorithm 4: The Case of Inexact Cuts and Convergence
In this section, we discuss convergence results of Algorithm 5 under the third setup described in Section 6.1.
Note that the cut made by both Algorithm and Algorithm 2 are exact in the sense that cuts are only made when the computed center mis-classifies the data points returned by the oracle and is therefore always discarded via the cutting hyperplanes. Algorithm 5, on the other hand, implements inexact cut: cuts are always made regardless of whether the queried center mis-classifies. Nice convergence rate similar to that of Theorem 6.3 can still be guaranteed, as we shall see in the following theorem. as long as the cut made within a certain neighborhood of the centroid each step.
First, let quantify the inexactness of the cut. At each iteration, given cutting hyperplane H. of normal vector which passes through the origin by design, and the computed center 0, the Euclidean distance between 0 and the hyperplane is given by
||0||a| cos())),
(19)
31

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
where
8.
arccos(
(20)
|0 all2
is the angle between & and the normal vector For simple notation, let denote the angle between @ and the cutting plane Ha as B. Then
π 2 a.
3
(21)
Next, we introduce an important extension to Proposition C.4 given in (Louche & Ralaivola, 2015).
Proposition G.1 (Generalized Partition of Convex bodies). Let T S Id be convex body. Let H. be hyperplane of normal vector a. We define the positive (negative) halfspace T (resp. T-) of with respect to Ha as
T T (a, 0) 2 0}
T = =n(OER''' (a.0) < 0}
The following holds true: 0c + Aa E T then
vol(T+)/vol(1) 2 2 - A)a,
where
vol Vol(T)
A = Y
Rd Rd
with X R an arbitrary real such that S 1, Oa a constant depending only on d, the radius of the (d - 1) dimensiooal
ball B2 of volume vol(B2) := vol(T {0 Rd (a, 8) -}} and
H = max 6" a (resp. Hy- == min bTa).
SET+
BET
Proof. See Proof of Theorem 2 in (Louche & Ralaivola, 2015).
Note that by symmetry of partitioned convex body with respect the centroid (an application of Proposition C.4), one can similarly establish bound in the case that
Og + Aa ET=
where A is defined in Proposition G.I. Then
2 E (1- A)d.
(22)
Proposition G. generalizes Grünbaum's 's inequality Proposition C.4 by allowing a cut that is of distance (greater than or equal to) A along the direction of the normal vector a from the actual center of gravity. To apply Proposition G.I, we need establish an equivalence relation between our quantifiation of the inexactness through the Euclidean distance h (or angle and or 3) with A.
We are now ready to bound the volume reduction factor for inexact cuts with respect to the center gravity in Algorithm 5. Theorem G.2 (Convergence with Inexact Cuts of Center of Gravity). Let T C RR be convex body and let Og denote its center of gravity. Given oracle returned data point (Ins Vn), define hyperplane
H₂g {0 E Rdd
Yn gawo-layer (In; 0) 0),
where
0 yn
[xt]
2 x [f
32

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
its associaled normal vector. Then Ha divides T into positive half-space T+ and a negative half-space T
T T e R (a. 0) 2 0} T = Tn (a,0) < 0),
and h : [0 Tallz
is the Euclidean distance between 0G and Ha. The inexact polyhedron cut given in Algorithm 5 partitions the convex body T into subsets:
Ti (0 T ((
To = 10 E :ETTTTT or ((())))
where denotes the complement of given set. The following holds:
vol(TT) (1 -1--6 10--e-1 e- (1-
with
HT h > 0, (T)ol(T)H
À =
where Og is constant depending only on d, R. is the radius of the (d 1)-dimensional ball Bg of volume vol(B.) == vol(T n Ha) and
H max @Ta (resp. Hy- == min aTa). BET
SET+
Proof. Observe that at each iteration if 0g mis-classifies the oracle returned data point (I,, Bn). then have the same analysis as in Theorem 6.3. In such case, have guaranteed accelerated cuts with strietly better volume reduction rate bound than in the case when cuts are made exactly through the centroid. This is because in this case the centroid is contained in the interior of the eliminated region. On the other hand, when the cut is made such that the centroid is contained in the interior of the positive half-space, we cut away smaller volume than when we make the cut through the centroid. Therefore, to obtain a lower bound on the volume reduction rate for Algorithm 5, suffices to examine only the latter case, i.c. when AG is contained in interior of the positive half-space.
Suppose that 0g T Ha. Define real number A to be such that
10 a|
hhhh hh:
|
then since 0G ha Ha, it follows that
0G + Aa T-
By Proposition G.1 and symmetry, it follows that
(a((T)/vol(? 2 21- 2)d,
where
A A(O. vol (T) Rd HH
a real such that À I 1, Oa is a constant depending only on d, R is the radius the (d - 1) dimenssonal ball B3 of volume vol(B2) == vol(T Ha) and
HT max 0 (resp. HT = min 0T a).
SET+
OET
Since
= Xea vol vol(T) HT+
< -h,
R
33

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
equivalently
R HT (avol(T)H7)
0<
it follows that
vol(T e- vo)
= '1 x) vol
or equivalently
vol(T+) (1 (1- vol)))
where
R HT (
i=
Since
Ti TT (7 ET+
have that
vol(TT) S vol(T*) e1--- vol
To justify that the derived ratio vol()))/vo((7) is valid, i.e. vol(Ti)/vol(T) E [0, 1], it suffices to show that e e1 2)d
[0, 1], or < X < 1.
Define coefficient
cHH, .d) = = vol (T)
R²
Since by definition H1 > 0, Hy < 0, with Od, vol Rd > 0, it follows that c(Ha, T, d) < O.
Since Ā = -cHHa T, .d)- and 0, we have that Ā > Next, to see λ s 1, observe that since we have
Ac(Ha, T. -h,
follows that
cHa, T,d) < -h 5 -> -
where we have used the fact that 0 < A S 1. follows that
A= -c T, h1 < h - 1.
Hence, < A < 1. Then by Theorem 6.3, the volume reduction ratio 1 - e ' >> 1-e offers strict upper
bound for each iteration of Algorithm 5, regardless of whether the centroid 0 is contained in the positive half-space the negative half-space.
Given Theorem G.2, at each step t in Algorithm 5, at least a volume of magnitude e e1 vol is cut away. The volume of T after t iterations is bounded by:
vol(T') <1- e- 2)dye vol(T").
Since Ā 1, we have 1 11-e- Ājd < 1. So converges zero as t + co, and the feasible region shrinks the optimal point(s), as in Theorem 6.3.
xo, (1- - R)det + It follows that vol
Theorem G.2 allows us to quantify the volume reduction rate function of the inexactness of cuts through the Euclidean distance between the centroid and the cutting hyperplane, which is monitored by the query sampling method. In particular, in the case of inexact cuts in Algorithm with minimal margin query sampling scheme, the volume reduction rate converges asymptotically in the number of training data supplied to the cutting stated in the following corollary.
autting-plane plane oracle to the rate in Proposition C.4. This result
34

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Corollary G.3 (Asymptotic Convergence of Inexact Cuts with Center of Gravity). Assume that data points Iy 's are uniformly distributed across input space. Let the number of training data supplied the cutting-pane oracle in Algorithm 5 goes to infinity, i.e. [D] oo. Then the volume of T after iterations with the polyhedron cut in Algorithm 5 under minimal margin query sampling method converges asymptotically to bound
vol( < (1- (1=))><(()
Proof. Let us begin with analyzing single iteration with convex body T C Rd and its centroid 0c. Notice that as [D] increases, data points 's become more densely distributed across the input space. So for any > O, there exists a sufficiently large N such that for all [D] > N, there exists at least one data point x; E D, for which ftwo-layerxxe 0c) =
[x] z I3 == 0gl < E. As [D] + oc, e can be made arbitrarily small, implying that
arg min ftwo-layer (zy; 0&)l +
2,ED;
This suggests that the Euclidean distance between 0g and the oracle returned cutting plane Ha diminishes to |D] cc.
By Theorem G.2, given inexact polyhedron in Algorithm 5 distance h away from the centroid, the volume of the remaining set is upper bounded by the following:
vol(TT) s (1-c --)-p 2) vol()),
where Ā -c(Ha, T,d)- and
(T)
c(Hor T, .d) = Oa Rd
Then to show that ratio (1 e 2)a) 1 equivalently
0, as h - 0, it suffices to show that the coefficient term -c(Ha, d. = lc(Ha. T. dd) is lower bounded by constant M so that its inverse is upper bounded. This is easy to show. First observe that dimension dependent constant O₂ and vol(T) is fixed and finite regardless of the cutting plane Ha. Because convex body T is by definition closed, variables R, Hy- are bounded from above. By the same reasoning. H bounded from below and away from O, for if Hy 0, it follows that vol(T*) = 0, suggesting the termination and convergence of the algorithm to the optimal solution(s). Hence, there exists a constant Mmin such that
min |c(Ha, Td)) 2 Mmin- Hay
It follows that
0 0 lim A = lim -c(Ha. d, lim M M- = 0. h-+0
h-
80
So as [D] + oo, we have that h + 0, which results in Ả + O. Therefore, the volume of after iterations in Algorithm
follows:
lim vol(T') < Po
lim (1-e - vo (1 e- vol(T)).
G.4. Convergence w.r.t Center of the Maximum Volume Ellipsoid
Recall the definition for the center of MVE in Definition C.2. We will now show that similar convergence rate that of the center of gravity can be achieved under center of MVE as well.
Theorem G.4 (Convergence with Center of MVE). Let T Rdd be convex body and let 0M denote its center of the maximum volume inscribed ellipsoid. The polyhedron cut given in Algorithm 4 (assuming that the cut is active) and Algorithm 2, i.e.
Tn Yo. gtwo-layer (I,: 2 (,C((a))
where coupling (In, Und is the data point returned by the cutting ppann oracle after receiving queried point 0 partitions the convex body T into two subsets as Theorem 6.3. Then Ti satisfies the following inequality:
vol(Tz) < <(1
Z) - vol.
1
35

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Proof. The proof follows similarly the proof to Theorem 6.3. For the MVE cutting-plane method, the bound the volume reduction factor is given by:
vol( (T)(
1 d'
31
where &t denotes the iteration (Boyd & Vandenberghe, 2004). Since (xx ()) is linear in and by the design of the algorithm, the center M is always contained in the interior of the discarded set (or equivalently, the cut deep), proof for the bound (1 - 2) vol(T) follows similarly as the proof of Theorem 6.3.
Accelerated Cutting Theorem in (Louche & Ralaivola, 2015): for any convex body K R and any hyperplane W. cg(K)E K+ then
V(K+) 2 e V(K).
Here in our case, we consider P, P= 1. Assume the ReLU gate is activated, we harness the following constraints
x² (w1 w2) 2 0, x" w1 0, x² w2 0.
H. Experiments Supplementals
H.1. Implementation Details
In this section, we provide an overview of the implementation details. For specific aspects, such as baseline implementation and the cutting-plane AL method for regression, we direct readers to the corresponding sections in Appendix H.
In our experiments, we follow exactly the same algorithm workflow as in Algorithm for our model training and Algorithm 4 for active learning with limited queries, which is the version used conducting all of our experiments in Section 7. In the training of Algorithm 4, we implement the "center" function for analytic center retrieval due to its simple computation formula (see Definition 6.1) Since the center retrieval problem is of convex minimization form, we solve it with CVXPY (Diamond & Boyd, 2016) and default to MOSEK (MOSEK ApS, 2024) as our solver. In our experiments, MOSEK is able to handle encountered convex optimization programs, given that they are feasible. We involve all training data cuts while we note that some cut dropping method may help alleviate computation overhead. i.e., one may keep the last several cuts only, see Section 2.5 in (Parshakova al., 2023) a discussion on constraint dropping. For activation pattern generation, for two-layer model experiment, say we want m patterns, we always generate a of standard Gaussian vectors fu,, ė [n]] for some > m, compute the induced pattern set {D, diag( (Xx, 0})}, and take non-duplicate patterns out of it. Furthermore, in our implementation of Algorithm 4, we included few additional checks for computational efficiency, like skipping the centering step when cut has been performed before, or book-keeping of discarded data points that should not be re-considered immediately. For IMDB experiments, we randomly pick 50 training data points and 20 test data points for case of computation, and we use minimal margin query strategy described in Appendix D.3. Through all our data experiments, random seed is fixed be 0 except for error bar plots, where we always take random seeds (0, 1, 2, 4).
H.2. Final Solve Regularization Cutting-plane AL
In this section, we discuss an optional feature to our cutting-plan AL method via the two-or-thred layer ReLU network: the inclusion of a final convex solve which solves for the optimal parameter of the equivalent convex program to the two-or-three layer ReLU network using the data acquired by the AL thus far.
Convexifying Two-layer ReLU Network. To introduce this final convex solve, we first briefly overview the work of (Pilanci & Ergen, 2020). We will focus the two-layer ReLU network case, the case for three-layer be easily extended by referencing the exact convex reformulation of the three-layer ReLU network given in the paper by (Ergen & Pilanci, 2021b).
(Pilanci & Ergen, 2020) first introduced a finite dimensional, polynomial-size convex program that globally solves the training problem for two-layer fully connected ReLU networks. The convexification of ReLU networks can be summarized into a two-step strategy:
36

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
1. Project original feature higher dimensions using convolutional hyperplane arrangements.
2. Convexify using convex regularizers, such as convex variable selection models.
First, as per Step 1), we briefly recall and define a notion of hyperplane arrangements for the neural network in Definition C.I and we can rewrite the ReLU constraint using the partitioned regions by the hyperplanes:
(2D(S) I x 2 0
(23)
Next, per Step 2), we define the primal problem and give its exact unite-dimensional convex formulation. Given data matrix X IRaxd we consider a two-layer network ((X;0) Rund + R with m neurons:
f(x:0) Σ (Xws))aaj
(24)
where wy E ERd, Oj E IR are weights for hidden and output layers respectively, and 0 = {wj, oz) Supplied additionally with label vector y E R" and a regularization parameter >> 0, the primal problem of the 2-layer fully connected ReLU network is the following:
p=:= := min
[I((x;0) v12
(1wy az).
(25)
(
2
The above non-convex objective is transformed into equivalent convex program. For detailed derivation, please refer to (Pilanci & Ergen, 2020). We will give an overview of the key steps here. First, re-represent the above optimization problem as an equivalent & penalized minimization.
1 2
min
min [o
(|((x)))
- -
> Jayl-
(26)
Using strong duality, the exact semi-infinite convex program to objective 25 obtained:
p"
max vERT s.t. jo" (Xw) Is
0 +
(27)
Under certain regularity conditions in (Pilanci Ergen, 2020), the equivalent miite-dimensional convex formulation the following:
P D(S.) - -w) -.)-v11
D²
min oo ER
Σ
fu 1P
(28)
+ 31
[ 1 + [14(
1=1
subject to the constraints that
(2D(S)) I,) 2 0, - 2 0, Vi.
Here, is a regularization parameter, and we denote {u, ud [e as the solution objective 28.
To that the convex program outlined in 28 is indeed exact reformulation of the two-layer ReLU network, convex solve the spiral dataset and the quadratic regression dataset in Section 7 and compare it with standard stochastic gradient descent technique. We also note here that for the sake of brevity, we will be referring to the solving of the exact convex program with respect to the two-or-three layer ReLU networks interchangeably as "convex solve" or "final solve".
the
First, using the same spiral dataset of randomly selected 80 points from 100 points Spiral (k1 = 13, kg = 0.5, Natape = 50) (detailed in Appendix H.4) and 0.001, the convex solve achieves an objective value of 0.0008, while stochastic
37

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
1.0
0.0
-0.5
-1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
Figure Decision boundary made by conves solve (lefi) and stochastic gradient descent (right) on the Spiral Dataset of Piatage 30.
1.0
0.5
-0.5
-1.0
1.0
0.5
0.5
1.0
1.0
-0.5
1.0
Figure 6. Decision boundary made by convex solve (left) and stochastic gradient descent (right) on the Spiral Dataset (ldope 100.
gradient descent levels out at an objective value greater than 0.001. The final decision boundary on the spiral using the convex solve (left) and SGD (right) is shown in Figure 5, where we have used marker "x" to indicate the train points passed into each solver and triangle marker indicate test points. While both methods capture the spiral perfectly in this case, the advantage of the convex solve becomes more evident given more complex (e.g. in terms of shape) data. This is demonstrated in Figure 6, where have used spiral dataset of randomly selected 80 points from 100 points Spiral (k1 13, 422 0.5, Rehape 100). Similar results hold for the regression case. The convex solve for the two-layer ReLU network returns objective value of 4.142 10-5, This aligns with the result of Figure 7 as the final prediction of the convex solves aligns perfectly with the actual quadratic function.
Integration of the Final Convex Solve. Now we talk about how we can incorporate the convex program in 28 into our cutting-plan AL method to potentially aid its performance. We first provide some justifications.
Duvinite Beepodan oowrs Belli
355
Figure 7. Prediction made by convex solve (red) and stochastic gradient descent (syan) the regression dataset.
38

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
As have mentioned in Section 6, since the prediction function
Σ D(S.) - u:) ftwo-layer (X;0) -Xt -X- - X X²
linear in 0 (u), U1...., u/ up) with ue u', F' along with the ReLU cuts, we preserve the convexity of the parameter space after each cut. And hence, the final solve becomes well applicable. To introduce this step. we use the short-hand notations in Section 6 and also, for the sake of brevity, we denote the exact convex objective in Equation 28 as the following:
(D; = min 1
Σ
(D(:)) - u,) -1pl- vol2
2
(29)
+ B
(1|uell2 + [|u/]l2)),
where XD and yo are the slices of X and y at indices D.
Algorithm shows how the final convex solve incorporated into our sutting-plane AL method via the two-layer ReLU network with limited queries. Other variations such as query synthesis (Algorithm 2), inexact cuts (Algorithm 5), as well as regression (Algorithm 6) can be adapted in the same way. In Algorithm 8, SOLVE () is convex solve that solves the exact convex formulation in Equation 28 with all the selected training data pairs (æ,, y:) | E DAI from the active learning loop. In our implementation, we use CVXPY and default to solver CLARABEL (Goulart & Chen, 2024).
Algorithm Cutting-plane plane AI. for Binary Classification with Lim-
ited Queries using Final Solve
1: T +- 18
2: f x-00 0
3: DAI. 6-
4: repeat
5: 0f < center(T")
6: for in (1, 1 do
7: (Ine Unc) t QT D DAL: 8)
8:
if Yiu playee (Ene: 0²) < 0 then
9:
DAL ADD(DAL, (2n,; mn.))
10:
T
T n (0
ynz (Zn M1
C.C(m.)).C(((m)) L 1-1+1
Upon examining Algorithm 8 and the objec- tive function of the equivalent convex pro- gram (Dbi 06, .3) in 28, a key difference is the introduction of regularization term, i.c. s( (11u, 12 + 2 In more complex tasks, the inclusion of the final convex solve, and thus additional regularization, tends to aid the cutting-plate AL method in achieving faster convergence in the number of queries. This is the case, for example, for the spiral dataset in our experiment (see Appendix H.4). However, for simpler tasks, such as the quadratic regression prediction, adding regularization could slow down the convergence (see Appendix H.5). Therefore, in our experiments, we emphasize that we have used the best cutting-plan plaane AL method, chosen from the version with or without the final convex solve. This is explicitly noted in the supplementary sections, namely Appendix H.4 for the spiral experiment and Appendix H.5 for the quadratic regression task. We also remark that due to the limitation in theory the convexification of neural networks, such convex solve is only viable up to three-layer ReLU network.
11:
12:
end if
13:
end for
14:
until [Daul 2 Baddae
0f SOLVE( S (DAi 0. ('DD))
16: return
H.3. Active Learning Baselines
In this section, we introduce the various baselines used in the spiral task and the quadratic regression task in Section 7. We also elaborate on the implementation details of each baseline discussed.
In addition to random sampling, which serves as a baseline for all other AL methods, and the linear cutting- -laane AL method (Algorithm for classification and Algorithm for regression). which provides a baseline for our cutting nutting-plane NN algorithm (Algorithm 4), demonstrating our extension from linear to nonlinear decision boundaries in the cutting-plane
39

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
AL framework, we also survey popular AL algorithms from the scikit-acte iveml library (Kottke al., 2021) and the DeepAL package (Huang, 2021).
We first introduce the baselines we implemented from the DeepAL package.
Entropy Sampling (Settles, 2009). This technique selects samples for labeling based on the entropy of the predicted class probabilities. Recall that the entropy for a sample æ with predicted class probabilities p(y) x)) is given by:
Hyla:) = Σ p(u c/ar) log p(y = c(z)
Higher entropy indicates greater uncertainty, making such samples good candidates for active learning.
Bayesian Active Learning Disagreement (BALD) with Dropout (Gal et al., 2017a). BALD aims to choose samples that maximize the mutual information Ily 0/xr, Dirain] between predictions y and model parameters 8, given sample and training data Dtraine Mathematically, this is expressed as:
my. f/ Dtrain] = Hly x, Dtrasn] - Ep(( Derass)) H [y| 20 0]]
BALD with dropout extends this approach by using dropout during inference approximate Bayesian uncertainty, allowing for efficient estimation of uncertainty in deep learning models through Monte Carlo dropout.
Least Confidence (Lewis & Gale, 1994a). This strategy selects the samples where the model is least confident in its most likely prediction. For given sample is measured by the confidence of the predicted class D, follows:
LC(x) = max ply = c/z)
Samples with lower confidence values are considered more uncertain and thus more informative for labeling.
Next, we introduce the baselines surveyed from sci kit-aactiieet
Query by Committee (QBC) (Seung et al., 1992). The Senyy-y--oommitee strategy ensemble of estimators (a "committee") to identify samples on which there is disagreement. The committee members vote on the label of each sample, and the sample with the highest disagreement is selected for labeling. This disagreement is often quantified using measures like vote entropy:
H Hvote (x) --E
Σ Vi
Ue log
C
C
where v. is the number of votes for class and C is the total number of committee members. This strategy focuses on reducing uncertainty by selecting instances where committee members are in conflict.
Greedy Sampling on the Feature Space (GreedyX) (Wu et al., 2019). GreedyX implements greedy sampling on the feature space, aiming to select samples that increase the diversity of the feature space the most. The method iteratively selects samples that maximize the distance between the newly selected sample and the previously chosen ones, ensuring that the selected subset of samples represents diverse regions of the feature space. This is often formulated as:
max min | - 1251
D.ED
where D is the set of all data points and Q is the set of already selected query points.
Greedy Sampling on the Target Space (GreedyT) (Wu et al., 2019). This query strategy initially selects samples to maximize diversity in the feature space and then shifts to maximize diversity in both the feature and target spaces. Alternatively, it can focus solely on the target space (denoted as GSy). This approach attempts to increase the representativeness of the selected samples in terms of both input features and target values. The optimization can be formulated as:
max min ||. - ==,
and/or max min 11 - y1 M.D
R =
where is the set of all data points and Q is the set of already selected query points, applied either to the feature space, the target space, or both.
40

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
KL Divergence Maximization (Kidiv) (Elreedy al., 2019). This strategy selects samples that maximize the expected Kullhack-Leiblee (KI.) divergence between the predicted and true distributions of the target values. In this method, it is assumed that the target probabilities for different samples are independent. The KL divergence is measure of how one probability distribution diverges from a second, reference distribution, and is given by:
P(a,)
DKL (P Q) - P(a.) log ((x,)
where P is the true distribution and Q is the predicted distribution. This method balances exploration and exploitation by focusing on the areas where the current model's uncertainty is greatest.
We used Juery-By-Commet regression experiment, and used Greedy Sampling on the Target and KI. Divergence Maximization only for the regression task. As the readers may see in the descriptions provided above, both KL Divergence Maximization and Greedy Sampling on the Target Space are primarily suited for regression tasks due to the way they handle target distributions and diversity in the target space, which are more relevant in regression scenarios where the output values are continuous. Therefore, we have only included them for the regression task to offer a more robust comparison to our AL method.
and Greedy Sampling on the Feature Space for both the spiral experiment and the quadratic
We now discuss the implementation details for each of the aforementioned baselines. We implement random sampling and all DeepAL baselines using the DeepAL pipeline, while the scikit seikittactiin iveml baselines are imple- mented within their respective framework. We note that the original DeepAL framework given by (Huang, 2021) only implements active learn- ing for classification tasks. Thus, we modified the pipeline to allow AL methods surveyed from DeepAL to also be able to handle regression tasks. Since the modifications are minor, such as changing the loss criterion from cross-entropy to root mean square error loss, but not structural, we omit this distinction here and refer the readers to our submitted codes for details. Algorithm 9 outlines the general workflow of deep active learning baseline. Here, Dt and Dy refer to the set of labeled and unlabeled training data respectively, and nimi is the number of initial data to be randomly selected and labeled before the active learning loop.
Algorithm 9 Deep Active Learning Baseline
1: Dr < SAMPLE(D,, Mhmii)
2: Du + D Dr
3: 80 TRAIN(D,))
4: +
5: repeat
6:
Ev + EMBEDDINGS (Du 09)
7:
{Ina: Un, J + QUERY(EU:. Du)
8:
DI < ADD(D (Fn;; Mn. })
9:
DU + DU /. 3n
10:
aC+1, + TRAIN(Dr.)
11:
++t +++
12:
until |D2| Tbbdgee
13:
return 0¹
remains for us to discuss implementation details for scikit-acii aceil baselines. It is noteworthy that the default seikit-act i veeml active learning method for both classification and regression is implemented using own classifiers or regressors, such the mixture model classifiers for classification and the normal inverse Chi kemnel regressor, instead of trained using customizable deep neural nets, in the case of DeepAL. For the sake of breadth in surveying popular active learning baselines, we use the Python package skorch, scikit-learn compatible wrapper for PyTorch models (Viehmann et al., 2019), to integrate custom neural networks with a used popular sc k iittitaac -ttttctiiiii.... i veml active learning methods trained with its default regressor, the normal inverse Chi kernel regressor, for the regression tasks. In the classification case, we enforce the same ReLU architecture on all baselines for fairness. And in the regression case, to ensure the optimal performance of the sci waikit-acc veml baselines for the robustness of comparison, we use the so-called "bagging regressor" in seikit-acti ivell, which is an ensemble method that fits multiple base regressors (in our case, 4) on random subsets of the original dataset using bootstrapping (i.e., sampling with replacement) to update the base normal inverse Chi kernel regressor. This method is known to improve query learning strategies by reducing variance and improving robustness, ensuring that the baselines perform optimally (Abe & Mamitsuka, 1998).
classifiers for the classification tasks. and
Further further implementation details, such as how we implement the QBC method in the classification case using Skorch by creating an ensemble of 5 classifiers using the exact same ReL.U architecture with parameters in Table 2 but with different

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
random state of 0-4 respectively, and additional details on the specific implementation, please refer our submitted codes.
Finally, we would like to again emphasize that towards a fair and robust comparison, we select the best performing number of epochs (for a discussion on this, refer to Appendix H.4) and learning rate for AL baselines using deep neural networks and use enhancements such as bagging regressors for the srikit-actan iveml baselines trained on its default regressors.
H.4. Synthetic Spiral Experiment
In this section, we provide additional implementation details and supplementary results on the synthetic spiral binary classification experiment in Section 7.1.
Data Generation. We generate the two intertwined spiral used in Section 7 according to the following: the coordinates (#1,22) Ø2) for the i-th data point of the spiral with label y are generated as
21
F coo(()2
An
12,
22
rsin(d An
+ 12 r= Kis
ka-
Ø iT,
where .i,... ks are positive coefficients. In the implementation, index is normalized to lie within the range from 0 to Nishape - 1, where Rshape controls the shape of the spiral, so that the shape is independent of the total number of data points generated. The bigger Nsstpe is, the more complex the spiral (see for instance the spirals in Figure 5 versus Figure 6). In our experiment, we use the spiral dataset with k 13, k2 0.5, Rishape 50.
AL Implementation Details. To implement the butting-plane AL method, use 1000 simulations to randomly sample the number of partitions in the hyperplane arrangements (Definition C.1). This determines the embedding size (or the number of neurons). Table summarizes the statistics with respect to each seed. In our implementation of the deep AL baselines, we adjust the embedding size accordingly when using a different seed to ensure fair comparisons.
Sced
3
Neurons
623
607
605
579
627
Table 1. Number of neurons for each seed (0-4) sampled using 1000 simulations for the spiral dataset.
For all deep active learning baselines used in the Spiral case, we have set the hyper- parameters to be according to Table 2. We empirically selected learning rate 0.001 from the choices 10.1, 0.01, 0.001} } as it tends to give the best result among the three for all baselines in both the classification and regression tasks. We also choose the number of epochs to be 2000 as it also gives the best result among choices (20, 200, 2000} and show significant improvement from both 20 and 200.
Epochs
Learning Rate
Train Batch Size
Test Batch Size
Momcntum
Woight Docay
2000
0.001
16
10
0.9
0.003
Table 2. Hypar-parameters of deep AL baselines' training networks with the Stochastic Gradient Descent (SGD) optimizer
In fact, the performance of the deep AL baselines hinges much on the number of epochs in the train step (see Algorithm 9. Even when the AL method gains access the full data, if the number of epochs is small, we would still not obtain satisfactory classification result. In the following, we explore the effect of number of epochs classification accuracy for the baselines. We fix seed = 0 and use the same spiral data generation used in Section 7.1 with a 4:1 train/test split along with a budget of 20 queried points. Figure 8 to Figure 13 show the classification boundary with varying epochs = 20, 200, and 2000.
For most baselines, we observe a significant improvement in the decision boundary between 200 and 2000 epochs. To ensure robust comparison across methods, we set the number of epochs 2000. This mini experiment also underscores the inefficiency of gradient-basse based training, as the accuracy rate heavily depends the number of training epochs, highlighting the need for large number of iterations to achieve satisfactory results.
Experiment Results. We now give the deferred supplementary experiment results in Section 7.1. To start, per discussion in Appendix H.2, we would like to discuss the inclusion of regularization through the final convex solve of the equivalent convex program of the two-layer ReL.U networks.
42

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
bronendumpping kg
Gurfedoms
10
1/
2 00
-10
-15
-55
-35
-38
-25
(a) epoch = 20
(b) epoch = 200
(c) epoch = -2000
Figure 8. Entropy Sampling (20 Queries)
Sandondamstig
Randondampping
34
Ber Oaice
0.
-10
1.0
-15
-38
1.0
335
-38
3.0
(a) epuch = 20
(b) epoch = 200
(c) epoch 2000
Figure 9. Random Sampling (20 Queries)
IewtCaricerce
Tax
10-
38
255
10
(a) epoch 20
(b) epoch 200
(c) epoch -2000
Figure 10. Least Confidence (20 Queries)
43

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
S'LDOroppot
Ours Quriec Dara
Tra Diee
Mit 243
Qatree Detts
12
-10-
-1.0
-15
-18
-25
(a) epoch 20
(b) epoch 200
(c) epach =2000
Figure 11. BALD with Dropout (20 Queries)
1.
graedy
groetyx
greddy
2
-10
1.8
-30
-15
(a) epoch-
(b) epoch 200
(c) epoch -2000
Figure 12, GreedyX Queries)
cb
db-
Quered Dat
3 33
-10
24
-33
-55
05
-1.
25
(a) epoch 20
(b) epach 200
(c) epoch = 2000
Figure QBC (20 Queries)
44

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Figure 14 shows the final decision boundary with (left) and without (right) the convex solve with the same data and setup in the spiral experiment in Section 7.1. We abbreviate "after final solve" AFS and "before final solve" as BFS. It is evident that the inclusion of regularization improves the performance of our cutting-plane active learning method, increasing the accuracy rate on train/test set from 0.84/0.60 to 1.00/1.00. This is therefore the method we use for our outting-plame AI. algorithm. We will see that regularization with the final convex solve does not always speed up the convergence of our cutting-plane plann AL method in the number of queries. tends to work less optimally when used on relatively simple dataset, as we will see in Appendix H.5.
AFS AFS-CVX
BFS-CVX
2.5
1.5
Train Data
Thai Data
Test Data
Text Data Querleed Data
Quarled Data
1.0
1.0
0.0
1.5
1.0
0.5
1.0
1.0
0.5
(a) AFS
(b) BFS
Figure 14, Decision boundary of cutting-plane AL via the two-layer ReLU network with (left) and without (right) final convex solve.
Table 3 presents the train and test accuracies on the binary spiral dataset. This corroborates the decision boundaries shown in Figure 2. Finally, to demonstrate the consistency of optimal performance of our proposed method and to highlight its fast
Method
Train Accuracy
Test Accuracy
Cutting-plane (ours)
1.00
Linear Cutting plane
0.50
0,50
Random Sampling
0.73
0.70
Entropy Sampling
0,76
0.70
BALD with Dropout
0.71
0.65
Least Confidence Sampling
0.64
0.55
Greedy Sampling (GreedyX)
0.59
0.60
Query By Commitlee (ybc)
Table and test nocuracies binary classification Spiral (R) 12, Avg m 0.5, Vstuge 50) dataset for cutting plane the 2-layer ReL.U and various deep AI. baselines using seed 0.
convergence, we plot the mean train/test accuracy rates against the number of queries for our method and the baselines with bar generated by running experiments on seeds 0-4, Figure 15 demonstrates the result.
H.S. Quadratic Regression Experiment
Data Generation and AL Implementation Details. We generate the experiment dataset in this section simply according to the quadratic equation y x² without adding any noise. Since the dimension of the regression dataset goes down from d = 3 in the spiral dataset (with the third dimension acting bias for the ReI.U networks) to d = 2 in the regression dataset, we increase the number of simulations to 2000 to randomly sample partitions for hyperplane arrangements to maintain an adequate embedding size. As in the spiral task, Table summarizes the number neurons sampled with respect to each seed. Once again, in our implementation of the deep AL baselines, we adjust the embedding size accordingly when using different seed to ensure fair comparisons. As in the spiral experiment, we set the syper-parametes for all deep active
45

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Test Accuracy Mean versus Number of Queries Binary Spiral
greedyX
EntropySamping
RandomSamgglig
LeastConfidence
0,9
BALDDropout
abc
Outting
Text Acturacy
0.8
0.3
Number Queries
(a) Test
Accuracy
Binary
1.0
greedyX EntrapySamping
NandomSandting
LeastEanfidence
BAI DDropott
Outting Plane tours)
Meturary
0.7
0.5
0.4
10
20
40
50
Number of Queries
(b) Train
Pigure 15. Mean test and train accuracy rale across seeds (0 versas the number of queries for the 2. layer cutting plane Al. and various buselines.
46

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Seed
3
159
Table 4. Number of nourous each seed (0-4) sampled using 2000 simulations for quadratic regression datasct.
(a) AFS
(b) BFS
Figure 16, Prediction quadratic regression with cutting-planc two-layer ReLU network (left) and without (right) convex solve.
learning baselines according to Table 2. In the quadratic regression task, we similarly observe improved performance in deep AI. baselines with higher number training epochs and lower learning rate of 10-3, ensuring that the baselines provide robust comparison. For baselines from scikit act iveml, we use the bagging regressor along with the default regressor to enhance their performance (see Appendix H.3). For cutting-plan AL method (Algorithm 6) and the linear cutting-plane AL method (Algorithm 7), we choose the threshold value
10-3
Experiment Results. We now present the deferred experiment results the quadratic regression experiment. To start, discuss the performance of our cutting-plas plane AL method with and without convex solve. While using the full 80 training data, the stand-alone convex solve achieves perfect prediction of quadratic regression (see Figure 7), Figure 16 shows that including the regularization in our cutting-plame AL method with query budget of 20 leads to slightly suboptimal predictions compared to the non-regularized version. This could be because of the reduced complexity in the quadratic regression task, where the relationship between the features and the target simple and well-behaved and the model is less likely to overfit. Therefore, the incorporation of regularization could slow down the parameter updates, leading to slower convergence.
Method
Train RMSE
Test RMSE
Cutting-plane (ours)
0.0100
Linear Cutting plane (infeassibee
0.7342
0.7184
Random Sampling
Entropy Sampling
0.0599
0.0529
BALD with Dropout
0.0568
0.0408
Least Confidence Sampling
0.0599
0.0529
Greedy Sampling (GreedyX)
0.0745
0.0447
Query By Commillee (yhc)
K1. Divergence Maximization (kldiv)
0.1356
0
Greedy Sampling Target (GreedyT) T)
0.3296
Table Train and test RMSF. for the quadratic regression task (y )²) using the cutting- AI, with a 2-layer ReI.U neumal network and various deep AI. buselines with
=.
The trend plot in Figure 17 clearly illustrates the faster convergence of our cutting-plane AL method without regularization (BFS), compared to the regularized version (AFS), and significantly outpacing all other baselines. Therefore, for the quadratic regression task, we use the outting-plane AL method without final solve (BFS). Nevertheless, it is noteworthy that both AFS and BFS cutting-plane AL method significantly outperforms all baselines and converging to the optimal prediction considerably faster rate.
47

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Lag-IMMSE versus Queries Quadratic Regressio
10
THE RMSSE
gready
Samplig
anstiartidance SALDOhapou:
(645) (BP5)
Queree
(a) Test
Log
Regression
20-2
preatsx
gready
Sampligg
Cuiting Hane (APs)
Cutting Jane (072)
Number of Queres
(b) Train
queries 2-layer cutting plane augmented emoor har plot right of Figure with additional distinguishment between the AFS and BFS cutting plane AL method.
Figure 17. Logarithm
(0-4)
haselines.
Now we present the deferred results for the quadratic regression experiment in Section 7.1. Table 5 documents the train and test RMSE for our proposed cutting-plane AL against various deep AL baselines. In addition, Figure 18 presents the corresponding prediction made by our proposed method and the complete set of surveyed baselines.
H.6 IMDB Data Examples
48

---

Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Cutting Plane
Cutting (Liwar)]
Randam Sampling
Entrocy Sampling
30
64
Least Confidence
Groudy X
Groedy Target
obc
kiohe
G4
60
40
10
15
True yex?
Prediction
X Test Data
Querled Points
Figure 18. Predictions various AL algorithms quadratic regression using cutting-plane AL with two-layer RcLU neural network and deep baselines (complete).
Examples
Content
Label
"If you like original gut wrenching laughter you will like this movie. If you are young or old then you will love this movie, hell even ..."
Review
positive
"An American Werewolf in London had some funny parts, but this negative one isn't so good. The computer werewolves are just awful..."
Review 2
Ardh Satya" is one of the finest film ever made Indian Cinema. Directed the great director Govind Nihalani..."
Review
positive
Table 6, Examples of IMDB movie reviews
49


Reviews:
[{"review_id": "rTZjHfV8wm", "reviewer": "Reviewer_EEZV", "summary": "This paper provides a very interesting results for training ReLu neural networks. The authors show that training a binary classification problem using ReLu neural networks is essentially solving a linear program (LP), and therefore in the context of active learning, adding a new data point in the training set is equivalent to adding new linear constraints in the proposed LP. The authors also show that they can add linear constraints in a way that the volume of the feasible space is decreasing by $1-\\frac{1}{e}$ for each query, and compare test accuracy on several datasets among linear models and ReLu network trained by SGD.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I am not able to draw solid conclusion that this method will surpass current SGD-based\ntraining of neural networks.\n\nThank 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.\n\nOur 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.\n\n[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.\n\n> However, I am not sure about the evaluation criteria that solely relies on test accuracy versus SGD. \n\nAs 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.\n\nThe main computational burden stems from (1) the growing number of LP constraints, and (2) the cost of solving each LP:\n\n- 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.\n- For solving LPs, recent GPU-enabled solvers like CuClarabel and MPAX offer promising directions to improve runtime and scalability.\n\n> Another issue is that momentum-based methods seem to be more popular, which might provide better performance.\n\nThank 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.\n\nThe 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.\n\n> The authors did not discuss the computational efficiency of their proposed method.\n We’ve discussed this in our reply to point 2.\n\n> Although convergence results are given, I am not sure how to understand the results. \n\nThank 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)](https://drive.google.com/file/d/1K57njXjyj4Ea846PEh4qBkS4_wwsyGfW/view?usp=sharing).\n\n> I think the paper would be greatly improved if the authors could show results regarding learning the correct function.\n\nThanks for the insightful suggestion! Yes we are able to make it, see above.\n\n> I think an interesting question is that whether this method could reduce the number of queries needed for active learning.\n\nYes. 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.\n\n> Could the authors clarify on Algorithm 2?\n\nWe apologize for the confusion. Due to word limit, we include a detailed description [here](https://drive.google.com/file/d/10Co8zLhbtlI9qqgI1AWUODN_4utD8C7m/view?usp=sharing).\n\n> Could the authors comment of the computational aspect of their proposed method?\n\nOur 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.", "claims_and_evidence": "I am good with the theoretical claims. However, given the numerical tests conducted, I am not able to draw solid conclusion that this method will surpass current SGD-based training of neural networks.", "methods_and_evaluation_criteria": "I think the benchmark datasets are wide enough, from my perspective. However, I am not sure about the evaluation criteria that solely relies on test accuracy versus SGD. Since the number of variables grow fast as neurons increase, it seems like the runtime for LP would increase by a lot. Another issue is that momentum-based methods seem to be more popular, which might provide better performance.", "theoretical_claims": "No, I do not check the correctness of the proofs.", "experimental_designs_or_analyses": "Please see my comments for the session \"Methods And Evaluation Criteria\".", "relation_to_broader_scientific_literature": "I believe that this paper provides a very interesting perspective that could potentially connect the field of (Mixed-Integer) linear optimization with the well-developed field of neural network. For a long time people believe that only continuous optimization techniques would be great for NN training, but it might be the case that MILP would play a role as well.", "essential_references_not_discussed": "I did not find any essential references not discussed.", "other_strengths_and_weaknesses": "Strengths: \n1. The authors developed the connection of modeling the training of NN with LPs, which is a novel topic in the field of Machine Learning.\n2. The authors further provides theoretical results on the convergence of their proposed LP-based method for binary classification for active learning \n3. The paper is written in a very clear way.\n\nWeaknesses:\n1. Although convergence results are given, I am not sure how to understand the results. As the volume decreasing exponentially might not imply that the algorithm is capturing the correct hidden function, and therefore increasing the test accuracy\n2. The authors did not discuss the computational efficiency of their proposed method, which might be a big problem when it comes to large scale NN models", "other_comments_or_suggestions": "I think the paper would be greatly improved if the authors could show results regarding learning the correct function, which should not be too hard given the rich literature regarding MLPs. For example, the well-known Universal approximation theorem.\n\nMoreover, I think an interesting question is that whether this method could reduce the number of queries needed for active learning - it would be very exciting to learn about this if this is true.", "questions_for_authors": "1. I found that Algorithm 2 in the paper could be confusing. Could the authors clarify on what those variables mean?\n2. Could the authors explain how to interpret the convergence results? For example, if the underlying decision boundary of the true decision boundary is given by $f(x)$, can the LP-based NN training models approximate such function?\n3. It is connected to the above problem. If the results are unknown for a general $f(x)$, is that possible to show that for some certain class of functions, the decision boundary could be learned?\n4. Could the authors comment of the computational aspect of their proposed method? For example, on the runtime, maximum number of neurons allowed, and the average queries needed?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "odUOzhXnVh", "reviewer": "Reviewer_eDnf", "summary": "This paper proposes a novel method for training ReLU deep neural networks and selecting data queries within an active learning framework. Extending previous work on cutting plane algorithms to multi-layer ReLU networks, the authors formulate network training as a linear programming problem, decomposing the task of data fitting into a series of linear programs that can be solved efficiently. Additionally, the paper introduces a new active learning strategy that prioritizes querying the most confident samples to effectively identify misclassified instances and substantially reduce the parameter space. The proposed framework is validated through experiments on multiple synthetic datasets, demonstrating its efficacy.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Theorem 6.3, the main theoretical result in this work, is quite similar to the convergence analysis in (Louche & Ralaivola, 2015)\n\nDear 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](https://stanford.edu/class/ee364b/lectures/localization_methods_notes.pdf))—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.\n\n> Empirical evaluation does not convincingly address scalability\n\nOur 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.\n\nScalability challenges stem from:\n- Constraint growth: We mitigate this via subsampling and iterative pruning (Appendix F.4).\n- Solver overhead: Recent GPU-based LP solvers like CuClarabel [3] and MPAX [4] offer promising future improvements.\n\n[3] CuClarabel: *GPU Acceleration for a Conic Optimization Solver*. https://arxiv.org/abs/2412.19027  \n[4] MPAX: *Mathematical Programming in JAX*. https://arxiv.org/abs/2412.09734\n\n> Concern over exponential growth in activation patterns\n\nThanks 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.\n\n[5] *Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks*  \nhttps://arxiv.org/pdf/2002.10553; [6] *Randomized Geometric Algebra Methods for Convex Neural Networks*  \nhttps://arxiv.org/pdf/2406.02806.\n\n> Applicability limited to ReLU networks\n\nWe'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:\n- 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)](https://drive.google.com/file/d/1K57njXjyj4Ea846PEh4qBkS4_wwsyGfW/view?usp=sharing). 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.\n- 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.\n- Solver development: GPU-supported LP solvers have only recently emerged, and represent an exciting and active area of ongoing research.\n\n[7] *An Asynchronous Proximal Bundle Method*: https://link.springer.com/article/10.1007/s10107-024-02088-x\n\n> The paper does not address the volumetric stopping criterion in detail\n\nAlgorithm 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.\n\n> Potential advantage over gradient-based methods\n\nOur 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes. The paper introduces a novel approach to neural network training from cutting-plane algorithms.", "theoretical_claims": "Theorem 6.3, the main theoretical result in this work, is quite similar to the convergence analysis in (Louche & Ralaivola, 2015). It would be appropriate to mention this prior work in the theory section.", "experimental_designs_or_analyses": "Much of today's Deep Active Learning research focuses on large-scale datasets using batch-mode querying, aspects not addressed by the experiments in this paper. Instead, the authors evaluate their method primarily on simple tasks like a simple 2D spiral binary classification and a regression problem. Consequently, this empirical evaluation does not convincingly demonstrate how the proposed method addresses the scalability challenges typically targeted by active learning.", "relation_to_broader_scientific_literature": "The problem of applying convex optimization methods for neural network training is relevant, and the theoretical contributions appear sound. The proposed method effectively addresses common challenges inherent in gradient-based methods, such as hyperparameter sensitivity and slow convergence, while achieving competitive performance.\n\nThe experimental results demonstrate promising outcomes in both classification and regression tasks on smaller-scale datasets, suggesting potential suitability for specific practical scenarios.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "1. I have a concern that the method may not work well with larger-scale neural networks. The size of the activation pattern $D$ can be exponential in $n$.  \n \n\n2. The proposed method has significant limitations in terms of applicability, as it exclusively supports neural networks composed of linear layers with ReLU activation functions. This constraint renders it incompatible with modern architectures, including transformers, convolutional neural networks, and models utilizing alternative activation functions. Consequently, this severely restricts the practical impact and broader relevance of the method within the current deep learning landscape.", "other_comments_or_suggestions": "1. The paper does not address the volumetric stopping criterion in detail, particularly regarding its dependence on the dimensionality of the hypothesis space. It remains unclear how a user would practically specify or adjust this criterion.\n2. One potential advantage of the proposed cutting-plane method could be reduced computational cost compared to gradient-based methods. However, this aspect hasn't been sufficiently discussed or analyzed. Providing empirical runtime comparisons between the cutting-plane approach and gradient-based algorithms on the tested datasets would help to quantitatively highlight any computational benefits. Such an analysis would significantly strengthen the evaluation by clarifying whether the proposed approach offers practical efficiency improvements.", "questions_for_authors": "See ``Other Comments Or Suggestions''.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pbUA4QXLl0", "reviewer": "Reviewer_jFZZ", "summary": "This paper introduces a novel theoretical framework that extends cutting-plane optimization methods to active learning for deep neural networks. The authors bridge two previously separate domains: deep neural network training and cutting-plane optimization techniques. The primary contribution is showing that cutting-plane algorithms, traditionally limited to linear models, can effectively train neural networks despite their non-convexity and nonlinear decision boundaries. A key theoretical result is the geometric contraction rate guarantee of the feasible set, providing strong convergence properties. Through experiments on both synthetic data and standard benchmarks, the authors demonstrate that their approach achieves competitive performance against established active learning baselines while maintaining theoretical guarantees that most current methods lack. This represents an important step toward principled active learning methods for deep neural networks with provable properties.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The experimental evaluation, while sufficient, could include comparisons to more recent active learning methods\n\nThank 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.\n\n> The practical implementation details for large-scale applications could be clarified further\n\nWe've detailed our implementation of sentimental classification task in Appendix H.1. We are happy to provide more details if there is anything unclear.\n\n> The limitations regarding very large networks and datasets are not fully addressed\n\nOur 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.\n\nMore 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.\n\n[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:  \nhttps://arxiv.org/abs/2412.09734. \n\n> What factors limit the scale of data selection with your method, and what is the maximum scale achievable?\n\nThe 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.\n\n> What is the computational cost when applying your method to deeper networks\n\nThe 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.\n\n> Could your method be extended to work with pretrained models?\n\nWe'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.\n\n> If samples selected by your method were used to train deeper neural networks, would they be more effective than samples selected by existing methods?\n\nThank 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.\n\nIn 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](https://drive.google.com/file/d/1K57njXjyj4Ea846PEh4qBkS4_wwsyGfW/view?usp=sharing)). 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](https://drive.google.com/file/d/1tR3e8n2Lc-JzmGozrzB7ZHU9RsTB-kf4/view?usp=sharing)). We plan to add further experiments on deeper models and more complex tasks in the final version.", "claims_and_evidence": "The claims in this paper are well-supported through rigorous theoretical analysis and empirical demonstrations. The authors clearly establish their theoretical framework and provide thorough proofs for their convergence guarantees, which is particularly valuable in the typically heuristic-driven field of deep active learning.", "methods_and_evaluation_criteria": "The proposed method represents a creative and theoretically sound approach to the active learning problem. By adapting classical cutting-plane methods to the neural network setting, the authors provide a fresh perspective that addresses limitations of previous approaches.\n\nThe evaluation methodology is appropriate and well-executed, using standard benchmark datasets and metrics. The authors effectively demonstrate their method's performance through clear visualizations and comparisons against relevant baselines. Their approach of evaluating on both synthetic data (to verify theoretical properties) and standard benchmarks (to demonstrate practical utility) provides a comprehensive assessment of the method's capabilities.", "theoretical_claims": "No problems.", "experimental_designs_or_analyses": "The experimental design is sound and effectively demonstrates the method's practical utility. The visualizations are particularly strong, providing clear intuition about how the algorithm operates. The experiments validate the theoretical properties while showing competitive performance on standard tasks.\n\nWhile the baseline comparisons are somewhat limited and focused on simpler approaches, they adequately demonstrate the method's effectiveness relative to established techniques. Given the theoretical focus of the paper, the experimental validation strikes an appropriate balance between demonstrating theoretical properties and practical utility.", "relation_to_broader_scientific_literature": "This work makes a valuable contribution by bringing together two previously separate research areas: cutting-plane optimization and deep active learning. It builds upon classical optimization techniques while addressing modern deep learning challenges.\n\nThe approach offers promising avenues for extension to other sample selection problems beyond active learning, potentially impacting other areas where principled sample selection is critical. The theoretical guarantees provided by this approach distinguish it from many existing methods in the field.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "**Strengths:**\n- The paper makes a novel connection between classical optimization techniques and modern deep learning\n- The theoretical analysis is rigorous and provides valuable insights into the method's performance\n- The visualizations are clear and intuitive, effectively communicating the algorithm's operation\n\n**Weaknesses:**\n- The experimental evaluation, while sufficient, could include comparisons to more recent active learning methods\n- The practical implementation details for large-scale applications could be clarified further\n- The limitations regarding very large networks and datasets are not fully addressed", "other_comments_or_suggestions": "See Questions.", "questions_for_authors": "1. What factors limit the scale of data selection with your method, and what is the maximum scale achievable? Understanding these constraints would help clarify the method's practical applicability.\n\n2. What is the computational cost when applying your method to deeper networks, and approximately how many neural network layers can your approach effectively handle while maintaining its theoretical guarantees? This would help readers understand the scalability of your approach.\n\n3. Current active learning approaches often leverage pretrained models (e.g., ActiveFT). Could your method be extended to work with pretrained models, perhaps by training only a linear classifier layer or a shallow two-layer network with ReLU? Some simple experimental validation would be valuable.\n\n4. If samples selected by your method were used to train deeper neural networks, would they be more effective than samples selected by existing methods? This comparison would help establish broader applicability beyond the theoretical context.\n\nI should note that while I'm not specialized in theoretical machine learning research, the paper appears well-executed and makes a valuable contribution. I have a positive impression overall, though I believe addressing the real-world applications and scalability questions would further strengthen the work.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel active learning approach for ReLU neural networks that leverages cutting plane methods and operates in a gradient-free manner. The method is enabled by reformulating ReLU training as a linear program, which offers a new perspective on ReLU active learning. The authors also develop convergence guarantees for the proposed active learning approach. Most reviewers acknowledged the novelty of the algorithm and the significance of the theoretical results. 

The main concern raised by reviewers is on the scalability of the proposed method, due to the number of constraints in its LP formulation. The authors acknowledge this issue and develop pruning techniques to remove redundant constraints. Scalability issues could also be partially mitigated through the parallel development of GPU-accelerated LP solvers. While the scalability issue should not be overlooked, it is important to recognize that this submission presents the first algorithm to connect ReLU active learning with linear program, opening avenues for future work in this direction.
Decision: Accept (poster)