FIRAL: An Active Learning Algorithm for Multinomial Logistic Regression
Authors: Youguang Chen
George Biros
Venue: NeurIPS 2023 poster (2023)
Keywords: statistical learning
active learning
logistic regression
regret minimization

Abstract: We investigate theory and algorithms for pool-based active learning for multiclass classification using multinomial logistic regression.  Using finite sample analysis, we prove that the Fisher Information Ratio (FIR)  lower and upper bounds  the excess risk. Based on our theoretical analysis, we propose an active learning algorithm that  employs regret minimization to minimize the FIR. To verify our derived excess risk bounds, we conduct experiments on synthetic datasets. Furthermore, we compare FIRAL with five other methods and found that our scheme  outperforms them: it consistently produces the smallest classification error in the multiclass logistic regression setting, as demonstrated through experiments on MNIST, CIFAR-10, and 50-class ImageNet.

FIRAL: An Active Learning Algorithm for Multinomial Logistic Regression
Youguang Chen
George Biros
Oden Institute for Computational Engineering and Sciences The University of Texas Austin
Abstract
We investigate theory and algorithms for pool-based active learning for multiclass classification using multinomial logistic regression. Using finite sample analysis, we prove that the Fisher Information Ratio (FIR) lower and upper bounds the excess risk. Based on our theoretical analysis, we propose an active learning algorithm that employs regret minimization to minimize the FIR. verify our derived excess risk bounds, we conduct experiments on synthetic datasets. Furthermore, we compare FIRAL with five other methods and found that our scheme outperforms them: it consistently produces the smallest classification error in the multiclass logistic regression setting, as demonstrated through experiments on MNIST, CIFAR-I0, and 50-class ImageNet.
Introduction
Active learning is of interest in applications with large pools of unlabeled data for which labeling expensive. In pool active learning, we're given a set of unlabeled points U, an initial set of labeled points So. and a budget of new points our goal is to algorithmically select new points to label in order to minimize the log-likelihood error over the unlabeled points. Equivalently instead of selecting points directly, we seek to find probability density function that we can use to sample the b points. Informally (precise formulation in $ 2). let z denote a data point and p(z) denote the distribution density of unlabeled points. Let q(x) be the sampling distribution we will use to select the new points for labeling. We will choose (xx) in order to minimize the generalization error (or excess risk) of the classifier over p(x). Our theory is classifier specific: it assumes multinomial logistic regression with parameters 6. The expectations of the Hessian with respect of the classifier loss function over p(x) and q(x) distributions are denoted by H, and H., respectively. Using finite sample analysis, first result (Theorem in $ 3 is to show that the unlabeled data excess risk is bounded below and above by the Fisher information ratio Trace(H, -' -HH,), subject to the assumption of p being a propose and analyze a point selection algorithm based on regret minimization that allows us to bound the generalization error.
sub-Gaussian distribution. Our second result (Theorem 4 in 4
There is large body of work various active learning methods based uncertainty estimation (II 2 3). sample diversity 44 [5),, Bayesian inference 6 7 and many others ([)). Here just discuss the papers closest to scheme. Zhang and Oles M
claimed without proof that FIR is asymptotically proportional to the log-likelihood error of unlabeled data. Sourati et al. [T]] proved that FIR is an upper bound of the expected variance of the asymptotic distribution of the log- li-llikeihood error. Chaudhuri et al. [ proved con-asymptoiic results indicating that FIR is closely related to the expected logllikelihood error of Maximum Likelihood Estimation-based classifier in bounded domain. In this work, we use finite sample analysis to establish FIR-based bounds for the excess risk in the case of multinomial logistic regression with sub- Gaussian assumption for the point distributions.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Algoritmically finding points to minimize FIR is an NP-hard combinatorial optimization problem. There have been several approximate algorithms proposed for this problem. Hoi al. [2] studied the binary classification problem and approximated the FIR using submodular function and then used a greedy optimization algorithm. Chaudhuri et al. [11] proposed an algorithm that first solves a relaxed continuous convex optimization problem, followed by randomly sampling from the weights. Although they derived a performance guarantee for their approach, it needs a substantial number of samples to approach near-optimal performance solely through random sampling from the weights, and no numerical experiments results were provided using such approach. Ash et al. [K adopted a forward greedy algorithm to initially select excess of points and then utilized a backward greedy algorithm to remove surplus points. But such approach has no performance guarantee. Hence, there is still need for computationally efficient algorithms that can optimize FIR in multi-class classification context while providing provable guarantees.
Our proposed algorithm, FIRAL, offers a locally near-optimal performance guarantee in terms of selecting points to optimize FIR. In our algorithm we have two steps: first we solve continuous convex relaxation of the original problem in which we find selection weights for all points in U. Then given these weights, we select b points for labeling by a regret minimization approach. This two-step scheme is inspired by Allen-Zhu et al. [4] where similar approach was used selecting points for linear regression. Extending this approach to active learning for multinomial logistic regression has two main challenges. Firstly, we need to incorporate the information from previously selected points in each new round of active learning. Additionally, while the original approach selects features of individual points, in logistic regression, complicates the computation and derivation of theoretical performance guarantees. In Section A we present our approach in addressing these challenges.
need to select Fisher information matrix (H2), which
Our Contributions. In S B we prove that FIR is a lower and upper bound of the excess risk for multinomial logistic regression under sub-Gaussian assumptions. @ In 4 we detail our FIR Active Learning algorithm (FIRAL) and prove it selects points that lead to a bound to the excess risk. @ In $ we evaluate our analysis empirically synthetic and real world datasets: MNIST, CIFAR-10, and ImageNet using a subset of 50 classes. We compare FIRAL with several other methods for pool-based active learning.
2 Problem Formulation
We denote a labeled sample as pair (x. v), where E IRd is a data point, E (1,2, ,ct is its label, and e is the number of classes. Let @ E (e(x-))xd be the parameters of a c-class logistic regression classifier. Given v and 0, the likelihood of the label y is defined by
exp(0).x)
V E [c- (c-1) 1]
2)
I+Eice i exp(() x)
(I)
++ 1+ exp(0Ta) a)
=
We use the negative log- ligeliiel as the loss function: ((. (0) & - log x, 0). To simplify notation we define d = d(c - 1). We derive standard expressions for the gradient V e ((e-l)xd and Hessian ( (0) E æd in the Appendix B.1 (Proposition 23p. We assume there exists 0. such that p(ylæ) = pvy xr 0.). Then, given p(x)). the joint (z, y) distribution is given by
(p( u) - p(yl=,0.)p10 (xxx)
(2)
Then, the expected loss at 0 is defined by
(0) A E (e (0) = Empp(e) Eer
The excess risk of p(x) at 0 is defined as (p) (0) (O.). Note that (t) 2
Notation:
The inner product between two matrices is A B Trace(A B). For a matrix
A E mg let ||A] be the spectral norm of A, let vec( A) E mm be the vectorization of A by
stacking all rows together, i.e. vec(A) (AI,-- ... A AT)) where A, is i-th row of A. Given a
positive definite matrix A E IRdxd we define norm ||| || for I E Ed by || = vz T Az. For

---

integer h 2 1, we denote by I the b- identity matrix. For any point distribution p(z) we define Vp - Bx=p(=) [x:x: T] to be its covariance matrix, H (0) (() be the Hessian matrix of (0), define H. _ (..)
Active learning. Let U {-.) be the set of unlabeled points and So be the set of no initially labeled samples. In particular, we denote the set of points in S. as Xu- Let 0g be the solution of training classifier with So. i.e., do E arg migg 1 no ((..)) ((n.)()). We select a set of b points X C U, query their labels y p(y|z,,0) Vx X, and train a new classifier 6n n E(r,ies (() (f), where 5 is the set of So with new labeled points and n = no +
arg ming 1
Our goal is to optimize the selection of X so that we can minimize the excess risk on the original unlabeled set U, i.e. (0.)) (O.). In this context, we define two problems:
Problem Given X or equivalently q(x), can we bound - 1,,(0,))Lpp0)))"
Problem 2: Can we construct an efficient algorithm for finding X that minimizes Lp(0n) - (o)))
3 Excess Risk Bounds
In this section, we develop our theory to address Problem 1 Our plan is to endow p(x) and ((x) with certain properties Suu--Gausiiantty finite support) and derive FIR bounds for L0() Ly (0.). Let fn be the empirical risk minimizer (ERM) obtained from i.i.d. samples drawn from T.g (z. v):
On E arg min
n T Σ
1
(0),
E E [n], wi iid To (o(,, v)-
We assume that both p(z) and q(z) are sub-Gaussian distributions. Appendix A. gives brief review of definitions and basic properties of sub-Gaussian random variables (vector). We define the 2/2-norm of sub- Gaussian random variable x E IR as [|=]|e,, - inf(t > 0 E exp(22/t")) S 2}. For a sub-Gaussian random vector I E Rd || sup ==le, [uul22 S 1}. We formalize our assumption for p(z) and g(z) in Assumption
can derive 2 (proof can be found in Appendix D). We present the results for q (thus the subscript in the K constants); exactly the same results, with different constants hold for p.
I Based on this assumption,
some properties for the gradient and Hessian of ((x,)) (0) shown inm
Assumption 1. Let q(x) be a uub-Gaussian distribution for x E Reb we assume that V is positive definite. We assume that there exists r Z 1 such that for any 0 E (f.) = {6 :10 0. 122. I gr), (,) is positive definite, where || |12,,0 denotes the maximum row norm of a matrix.
Lemma 2. If Assumption Tholds for q(x), thenfor (x, v) Ty y):
(1) There exists Ko.g > S.s.. VV 1/2 1/2 S Ko.
(2) There exists K1.q > S.T. [H 1//2vcc ( (0=) S K1.q.
(3) There exists (r, > 0 s.l. for any 0 in the ball B, (0.) = (0 110 0.112000 Sr).
sup wEST
|| H. (0) ((.))
(1 H)) 1/2 ullv S (2n(T),
(5)
where Sh-1 is the unit sphere in TR, norm || lle, is the norm defined for sub-exponential random variable = E R by ||= = inf(t > 0 E exxp((=)/t) < 23.
Our main result of this section is Theorem Under the sample bound given by Eq. 6 we derive high probability bounds for the excess risk in Eq, 7 Details and the proof of Theorem can be found in Appendix C
Theorem 3. Suppose Assumption 7 Tholds for both p(x) and q(z). Let and > 0 be constants such that H, N oH, and I--1 V, (0,) hold. There exit constants C1, C2 and C3 > 0, such
that for any ê E (0, 1), whenever
2 max { Cidlog(ed//), Cror (oop(T+ vālogle/5))
(6)
3

---

where d a d(c - 1), we have with probability at least 1 - 6,
e H H.
n & ((,)) L x e -
H Hp
a²
n2
Here Hp = (0.) and H = (0.) and E is the expectation over {ur ~ plylkri, 0. 0,)) Furthermore,
C3VopV (d+ Vālogle/6))/n.
(8)
From Eq. 7.. we observe that FIR (Hg g pears in both the lower and upper bounds for R(Om). In other words, it is essential for controlling the ex- cess risk. To the right we show how the prefactors
H ap-
10
(ec 11/8²
1e + a 1)/a²
10
="-g-l and o² +--+ change as function of ax Con- stants Cj, C2 and C3 depend constants defined in Lemma 2 for both p(x) and g(x). Appendix D derive bounds for Kip and (r) in Proposi- tion 35 For a Gaussian design x (0, Vp). we derive bounds for p, Ko,p. Kipp and K2,p in Propo-
10
10
10
Figure 1: FIR prefactors in Eq.
sition 37
Bounded domain. If the domain of x is bounded, Chaudhuri et al. [I]] provided lower and upper bounds for the excess risk of p(x) (Lemma [TI.. Their conclusion is similar to ours, namely that FIR is crucial in controlling the excess risk of p(x). It is worth noting that when the domain bounded, both p(x)) and ((x)) are always Gabssaass,,n, Thus, our assumption is more general. For the sake of completeness,
provide detailed derivation of the excess risk bounds for p(x) in
Theorem when æ is bounded with Assumption 38
Active Learning via Minimizing Fisher Information Ratio
We now discuss the FIRAL algorithm that addresses Problem 2 We can use the theoretical analysis derived in the previous section to guide us for the point selection. Let p(x) be the empirical distribution on unlabeled pool U with [U| = and q the distribution for the n = no + b labeled points. Eq. 7 inspires us to select points to label such that we can minimize the FIR H. -1 Hp. where H, (..). H, (O.)). However, we cannot directly use this as 8, is unknown. Instead, we will use 9g. the solution by training the classifier with the initial labeled So That we will find q by minimizing (0,) (op))).
In we formalize
optimization objective in Eq. (3).. Solving Eq. 13) exactly is NP-hard Inspired by 14,, we approximate the solution in two steps: (1) we solve a continuous convex
optimization problem Eq. (14) ($ 4.2). (2) and use the results in regret minimization algorithm to select points by Eq.
In Algorithm
D we summarize the scheme.
We state theoretical guarantees for the algorithm in S 4.4 where prove that it achieves (1 + e)- approximation of the optimal objective value in Eq. 13 with sample complexity b (dd/c²) as stated in Theorem To Finally, we obtain the excess risk bound for unlabeled points U by accounting for the fact that we use Og instead of O, in the objective function. The overall result is summarized in the following theorem.
Theorem 4. Suppose that Assumption 7 holds. Let (0, 8 (0, 1), and b the number of points to label. Then with probability at least 1- 5. the computed by fitting a multinomial logistic regression classifier on the labeled points selected using FIRAL (Algorithm 7 with learning rate
7 =8V v/jee b > 2 + +1V d/e2, and n -oo satisfying Eq. 6 results in
(0.)) (0.)) (1+c) 2000 e On 1 OPT
(9)
a
Here OPT the minimal H, -1 Hp. attained by selecting the best b points from U: T. is the expectation over {y ~ p(ya r. ) and og and on are constants.
Such set can be generated by alternative method that only uses p(z) select points, e.g., K-means.

---

4.1 Optimization objective
First we define the precise expression for (06) HH, (80). We define the Fisher information matrix
Hax, 0) V ((a.v) (0). By Eq. (40 in Proposition 23 (Appendix B
find that for multinomial
logistic regression
22, 8) [diag(((x: 0)) h 0)h(2, 0)
(zr )
(10)
where @ represents the matrix Kronecker product, h(x, 0) is a (c - 1) didiennsiaa vector whose k-th component is (z, 0) = ply k|z, 0). In Eq. 10)
see that the Hessian of (xr,)) (0)
does not depend the class label y. Following previous definitions, Hp((b) L2 (8())
m Erey H(I, 0)) and (0)) V (0)) ExExOUX H(x, 0p). For notational simplicity
we also define
H(x) H(x, 00)
Σ
H(r',0))
(11)
x'E
E(:) - Σ [z)),
2, scalar.
(12)
(m(m)
Then minimizing (0,) (0)) is equivalent to
min f(=) (I())) - (I())) Hp(())-
(13)
=E(0.1) |=
We define 2, be the optimal solution of Eq. 13 and f- f(z)). ). In the following, with some abuse of notation, we will consider / being a function of either vector or positive semidefinite matrix ((E), depending on the context. Lemma 5 key properties of / when viewed as matrix function; we use them
to prove the optimality of FIRAL.
Lemma 5. f: (A E Ixd A 0} - R defined in Eq. 13 satisfies the following properties:
(1) convex: S(AA (1 A)B) AS(A) (1 (B) for all X E [0,1] and A, A E
(2) monotonically ion-increasin:: if A 3 B then f(A) 2 f(B),
(3) reciprocally linear: t then (tA)) f(A).
4.2 Relaxed problem
As a first step in solving Eq. 13
we relax the constraint E {0, 1] to 2 E [0, Then we obtain the following convex programming problem:
2o arg min f(E()))
(14)
||||==b
Since both the objective function and the constraint set are convex, conventional convex programming algorithm be used to solve Eq. (44. We choose to mirror descent algorithm in our implementation (outlined in the Appendix, Algorithm ( Since the integrality constraint is a subset of the relaxed constraint obtain the following result.
Proposition 6. f(2o) < fx.
In what follows, we use matrices E. and H())) (i [m]) defined by
E. ((0) and H ((x)) A Σ H(rr) 1/2 i [m].
(15)
4.3 Solving Sparsification problem via Regret Minimization
Goal of sparsification. Now we introduce our method of sparsifying 2o (optimal solution to Eq. T4h) into valid integer solution to Eq. (13). To do so, we use an online optimization algorithm in which we select one point at time in sequence until we have points. Notice that alternative techniques like thresholding zo could be used but it was unclear to us how to provide error estimates for such scheme. Instead, we use alternative scheme that we describe below.
5

---

Let 8s E [m] be the point index selected at step t E [b]. We can observe that if
Amin| Σ
L H
(i 2 for some > O, then EiED H ( E. By Lemma Item (3) and
Proposition obtain the following result.
Proposition 7. Given E (0, 1). we have
Amin Σ H (o..)) 2T
Σ H(ri)) LE
S ST
(16)
MEM
From Eq. (16).a larger value indicates that f is closer to f.. Therefore, our objective is to choose points in such way that Amin [tE(B) (s;))) maximized.
Lower bound minimum eigenvalue via Follow-The- Heeloo-Thh-Reguhaane Tew.-h--Reglarieet--eeeedddd (FTRL). We apply FTRL, which is popular method for online optimization [] to our problem because it can yield a lower bound for Amin EiE()) H(z,)) in our setting. FTRL takes b steps to finish. At each step t [b]. for fixed learning rate 17 O, we generate matrix A, defined by
1 I d
A
A. (vela
H H(+)))
1 2).
(17)
Here P1 is the unique constant such that Trace (A,) 1. Using Eq. 17 we can guarantee lower
bound for Amiu [EEte) H(a..)). which is formalized below:
Proposition 8. Given Ad, 1 E [b], defined by Eq. 17 and for all t
2
Amin E(C)))
1/2 Trace [A|/2-(A - (A,
(18)
"
Point selection via maximizing the lower bound in Eq. (88). Now we discuss our choice of point selection at each time step based on Eq. 18). Recall that our sparsification goal is to make
Amiin (- H ((,;)) large as possible. Since Eq. 18) provides lower bound for such minimum eigenvalue, we can choose i, E [m]] to maximize the lower bound, which is equivalent to choose
i arg min Tracee[(A) 1/2 + +):()))))+
(19)
iE(m)
Solving Eq. 19 directly can become computationally expensive when the dimension d, number of classes c, and the pool size are large. This is due to the fact that the matrix A, +n,H(z)) e x
(where d d(c 1)), requiring n eigendecompositions of d matrix to obtain the solution. Fortunately, we can reduce this complexity without losing accuracy. First, by Eq. (1O) and Eq. we have for any [m].
H(r,) = Σ
H(x (x) + [diag(h(z;,00) 00)) - h(r,, (o), 0o) (xxa))))
(20)
Xo
AV...V
AD
where V, V,A,V; is the eigendecomposition of diag(h(æ,, 0o)) h (o) 0n) Define matrix
Q A V V 1/2 then (x,)) D (Q.Q.) (zx=7) Substitute this into Eq. 15 we have new expression for transformed Fisher information matrix H(x:):
H H(x:) = (.)) D(E.) 1/2
(E.) (/2 -E,)-1/((Q) 8 &.) 8 8 (Q.)(Q
11.) D (21)
2D
AP.
Now define B, E Rdxd
s.t. B 1/2 1/2 = A,-
1/2 + D. By Eq. 21). we have A, A, 1HH(r,)) =
1/2 B-112 + nTP.P.T Applying Woodbury's matrix identity, we have B,
(A, 1/2 H(x))) BB/²² BBB PP pp B PP,
-
P B 1/2
(22)

---

Algorithm FIRAL(b, U. Sy. 0o)
Input: sample budget b, unlabeled pool U (el)) labeled set So, initial ERM 0g
Output: selected points X
1: X <- 0
2: Ze f- solution of Eq. Σ. Ei= 2x (x))
# continuous convex relaxation
3: V,A, <- eigendecompooition
( 0o)) h(r, 06) Vi E [m]]
4: P. < Σ 1/2 (I, @ )V,A vi [m]]
5: D defined in Eq. 21 A 1/2
v V B + (A, nD)ー
6: for = to b do
7: i solution Eq. X X {I++}
8: VAVT + cigendeccomposition of Σx=1 H(r,,) = 1 (D (D+PPPtPPP
9:
find 1++1 s.t. Eje(ā (V++1 + A1) =
10: A 1/2 V(r-nIg A)V 1/2 (A 1/2
+nD)
11:
end for
Now our point selection objective Eq. 19 is equivalent
+ 1/ P.B. /2P .P, B.P.
ie - arg max
(23)
kE mm
Since (I.-1 P B T PP)
((e-1)x(c-1), solving Eq. 23) is faster than solving Eq.
19
We
summarize FIRAL for selecting b points in Algorithm
Connection to regret minimization. Our algorithm is derived the solution of regret minimiza- tion problem in the adversarial linear bandits setting. We give a brief introduction in Appendix F3 Readers who are interested in this topic refer to Part VI of [77] In case the action matrix is
constrained to {A E Rdxd A 2 0, Trace(A) A) = 1} and is chosen by Eq. 17 the loss matrix is constrained to the set of the transformed Fisher information matrices [H (z, Jm and is chosen by
minimizing Eq. 23
Algorithm complexity. Our algorithm has two steps: convex relaxation (line 2 in Algorithm I
and sparsification (lines 3-11). Let Teigen(d] be the complexity of eigendecomposition of d-
dimensional symmetrie positive definite matrix. Given an unlabeled point pool U with m [0).
the complexity of solving the convex relaxation problem by mirror descent (Algorithm 2 is
(md log m Teigen (d) log m). where assume that the number of iterations is O(log m.)
cording to Theorem 42 Given sample budget b, the complexity of solving the sparsification problem
is O (T oTigen cigg + Teigen (c 1)mm).
4.4 Performance guarantee
We intend to lower bound Amin EEE(o) H(r.)) through lower bounding the right hand side of (T).
First, since our point selection algorithm selects point z; at each step maximize Traco| A//2
(A, 112 + (Ha)) we establish a lower bound for this term at each step, as demonstrated in Proposition g
Proposition 9. At each step t E [b), we have
1- 2 + nVd
Trace[A!! 1/2
(A, 1/2 ((:))
max [m] 7
(24)
The derivation is elaborated in Appendix F.4 We remark that there is similar lower bound derived for the optimal design setting in [E! (Lemma 3.2), where a rank-1 matrix ~, (is E [m]] and T E IRd) is selected at each step. In contrast, in our active learning setting, the selected matrix H H(z,,) possesses minimum rank of and can even be full-rank matrix, contingent upon

---

Dilation (f- increasing (%))
Translation (<: decreasing Tq)
n=33200
m=3200
1n I,
1,(0.)
10
1 H
Hg-- Hp
H H,
Figure 2: Synthetic experiments: excess risk of p(z) a function of the FIR (H2 -1 Hp) in dilation and translation tests.
the labeled points from prior rounds. The distinction between the characteristics of the matrices significantly complicates the derivation of such general lower bound.
By connecting the observations obtained in this section, we can show that our algorithm can achieve + of the optimal objective with sample size (ddee). We conclude our results in Theorem
Theorem 10. Given E 1), let nj 8V d/c, whenever b 2 320/e² + 16 ad/2 denote the instance index selected by Algorithm a step by is E [m]) then the algorithm is near-optimal:
I (Eee H(xr)) S (1 (1++6 f.. where the objective function defined in Eq. 133 and f. is its optimal value.
The excess risk upper bound for unlabeled points can be obtained using our algorithm in Theorem by combining Theorem 3 and Theorem 10 while considering the impact of using On as approximation for 0.. We present the proof in Appendix F66 Comparing Eq. 2 to Eq. 7 we observe a factor of 2(1 + e) degradation in the upper bound. The (1 - comes from our algorithm, while the 200 -term comes from the use of 6, instead of 0, This observation suggests that, given a total budget of points to label b we should consider rounds. At each round & we label a new batch size b/r points and we obtain a new estimate 8g that can be used to approximate 0,, The prefactor containing an will becomes ag and reduces 0g converges to 0.. The simplest solution would be to use r = but this can be computationally expensive. In tests, we this batched approach and choose b/r to be small multiple of c.
iterative approach consisting of active learning
5 Numerical Experiments
Synthetic datasets. We use synthetic datasets to demonstrate the excess risk bounds Eq. 7 derived in Theorem 3. We choose p(x)) ~ (O, Vp), where V 100L, and d 8. We explore different numbers of classes denoted by E (2. 3, 5, 8}. We define the ground truth parameter 0, in such way that the points generated from p(x) are nearly equally distributed across the e classes. In Fig (Appendix G.I we plot the first two coordinates of the points draw from p(x), where each point colored by its class id.
We conduct tests using two different types of g(x) based on operations applied to p(z): dilation and translation. For the dilation, (αx) NN(0, v/ Vp). where V/ Rt. We vary V/ within so that FIR (H, HH,) is in [0.2d, 10d]. where d = d(c - 1). For translation, g(x) ~ (T,,,, Vp). where = 1/V22,1/V200
0) and Tq E IR. We examine various To values that ensures H, -1 Hp E [d, 10d]. For each c (2, 5, 8), g(z) and n {1600, 3200). we i.idd draw n samples from (z) and obtain 6, defined by Eq. 4 using these samples. We estimate excess risk (O,) - (0.) by averaging the log-likelihodd error on 5 x 10 i...d. points sampled from p(r).
Fig. displays the excess risk plotted against FIR for both dilation tests (left two plots) and translation tests (right two plots). It is evident that FIR plays a crucial role in controlling the excess risk. In the case of dilation tests, observe an almost linear convergence rate with respect to FIR. In the translation tests, we observe a faster-than- linear convergence rate, which can be explained by examining the upper bound of Eq. (7). As FIR decreases, also decreases according to the right plot of Fig. 6) By Proposition
37 in scenario, we have K1,g < (100 + +T)) 3/4, In Appendix C
8

---

Random
K-Means
Entropy
Var Ratios
BAIT
FIRAL
Classifiction Accurccy (%6
100
MNIST
CIFAR-I0
90
ImageNet.55
90
80
90
75
70
70
10
Hio
160
10
20
40
100
240
440
100
200
400
700
1200
2200
Number of Labeled Samples
Number of Labeled Samples
Number of Labeled Samples
BAIT
FIRAL
Figure 3: Active learning results for MNIST (left), CIFAR-JO 10 (center) and ImageNet- 50 (right). Black dashed lines in the upper row plots are the classification accurucy using all points in U and their labels. The lower now shows 50 images that are selected in the first round of the active learning process for the ImageNet-S0 dataset.
it is stated that C3 O K1.q K2pp) As result, FIR decreases, both C3 and decrease, leading to a decrease in a (as indicated by Eq. (63) Referring to Fig. D the prefactor of the FIR term in the upper bound decreases convergence rate with respect to the FIR term in the case of translation. We perform similar on multivariate Laplace distribution and t-distribution, and the results consistent with our observations on Gaussian tests. Further details of synthetic experiments are given in Appendix G.1
decreases. Consequently, the upper bound of Eq. 7
indicates faster-than-linee
Real-world datasets. We demonstrate the effectiveness of our active learning algorithm using three real-world datasets: MNIST [8], CIFAR-10 10 [TI and ImageNet [20] In the case of ImageNet, we randomly choose 50 classes for experiments. First and then apply active learning to the feature space, that is, we do not use any label information in our pre-processing. For MNIST, we calculate the normalized Laplacian of the training data and use the spectral subspace of the 20 smallest eigenvalues. For CIFAR- 10 and ImageNet-50, we use contrastive learning SimCLR model [2T]: then we compute the normalized nearest-neighbor Laplacian and select the subspace of the 20 smallest eigenvalues; For ImageNet-50 we select the subspace of the 40 smallest eigenvalues. For each dataset, we initialize the labeled data So by randomly selecting one sample from each class. Further details about tuning hyperparameter 1) and data pre-prose pre-processing are given in Appendix G.2
unsupervised learning extract features
We compare our algorithm FIRAL with five methods: (1) Random selection, (2) K- K-means where b, (3) Entropy: select top-b points that minimize E.p(v c/a) logr(y = c/æ) (where is the class with the highest probability), (4) Var Ratios: select top-b points that minimize p(y = c/a) (where is the class with the highest probability). (5) BAIT [ solving the
objective as our method, select 2b points and then delete h points, both in greedy way. Random and K-means are non-deterministic, we run each test 20 times. The other methods are deterministic and the only randomness is related to Sp. We performed several runs varying So randomly and there is no significant variability in the results, so for clarity only present one representative run. We present the classification accuracy on U in the upper row of Fig. 3 We can observe that our method consistently outperforms other methods across all experiments. K-means, one of the most popular methods due to each simplicity significantly underperformed FIRAL. It is worth noting that the random selection method serves as a strong baseline in the experiments of ImageNet-50, where our method initially outperforms Random but shows only marginal improvement in later rounds. But random selection underperforms in CIFAR-10. 10. In the lower row of Fig. 3 we show the images selected in the first round on ImageNet-50 for BAIT and FIRAL. Images selected in other methods

---

and other datasets can be found in Appendix G.2 One way to qualitatively compare the two methods check the diversity of the samples: in the 50-sample example BAIT samples only 21/50 classes; AL samples 37/50 classes. This could explain the significant loss of performance of BAIT in the small sample size regime.
6
Conclusions
We presented FIRAL, a new algorithm designed for the pool-based active learning problem in the context of multinomial logistic regression. We provide the performance guarantee our algorithm by deriving excess risk bound for the unlabeled data. We validate the effectiveness of our analysis and algorithm using experiments on synthetic and real-world datasets. The algorithm scales linearly in the size of the pool and cubically on the dimensionality and number of classes due to the eigenvalue solves. The experiments show clear benefits, especially terms of robustness of performance across datasets, in the low-sample regime (a few examples per class).
One limitation of our algorithm the reliance of hyperparameter, 1), derived from the learning rate in the FTRL algorithm. There are large body of work in online optimization about the adaptive FTRL algorithm (e.g., (T6), which eliminates the need for such hyperparameter. In our future work, we will investigate the integration of adaptive FTRL and evaluate its impact on the overall performance of FIRAL. By exploring this avenue, we aim to enhance the flexibilityy and efficiency of our algorithm. Another parameter is the number of rounds to use in batch mode, but this we have just set to a small multiple of the number of classes. Other extensions include more complex classifiers and combination with semi-supervised learning techniques.
7
Acknowledgements
This material is based upon work supported by NSF award OAC 2204226; by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program, Mathematical Multifaceted Integrated Capability Centers (MMICCS) program, under award number DE-SCO023171; and by the U.S. National Institute on Aging under award number R21AG074276-01. Any opinions. findings, and conclusions or recommendations expressed herein are those of the authors and do not necessarily reflect the views of the DOE, NIH, and NSF. Computing time on the Texas Advanced Computing Centers Stampede system was provided by an allocation from TACC and the NSF.
References
[1] Ajay Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Multi-class active learning for image classification. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 2372-2379, 2009.
[2] Xin Li and Yuhong Guo. Adaptive active learning for image classification. In 2013 IEEE Conference Computer Vision and Pattern Recognition, pages 859-866, 2013.
[3] Burr Settles, Active learning literature survey. 2009.
[4] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint 17Xi:1708.00488) 2017.
[5] Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning. arXiv preprint
2019.
[6] Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International conference machine learning, pages 1 1183-1192. PMLR, 2017.
7 Robert Pinsler, Jonathan Gordon, Eric Nalisnick, and José Miguel Hermández- Bayesian batch active learning as sparse subset approximation. Advances neural information processing systems, 32, 2019.
10

---

[8] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po- Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. ACM computing surveys (CSUR). 54(9):1-40, 2021.
[9] Tong Zhang and F Oles. The value of unlabeled data for classification problems. In Proceedings of the Seventeenth International Conference on Machine Learning, Learning.(Langlee P., ed.), volume 20, page 0. Citeseer, 2000.
[10] Jamshid Sourati, Murat Akcakaya, Todd K Leen, Deniz Erdogmus, and Jennifer G Dy. Asymp- totic analysis objectives based on fisher information active learning. The Journal of Machine Learning Research, 18(1):1123 1163,116,111110 2017.
[11] Kamalika Chaudhuri. Sham M Kakade, Praneeth Netrapalli, and Sujay Sanghavi. Convergence rates of active learning for maximum likelihood estimation. Advances in Neural Information Processing Systems, 28, 2015.
[12] Steven CH Hoi, Rong Jin, Jianke Zhu, and Michael R Lyu. Batch mode active learning and its application to medical image classification. In Proceedings of the 23rd international conference on Machine learning, pages 417-424, 2006.
[13] Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34:8927-8939, 2021.
[14] Zeyuan Allen-Zhu Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal design of ex- periments via regret minimization. In International Conference on Machine Learning, pages 126- 135. PMLR, 2017.
[15] Michal Černy and Milan Hladík. Computational Optimization and Applications, 51(3):1397-1408 2012.
Two complexity results on c-optimality in experimental design.
[16] H Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. The Journal of Machine Learning Research, 1171):3 2017.
[17] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[18] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2916)114-114,, 2012.
[19] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (canadian institute for advanced research).
[20] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image datahase. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. leee, 2009.
[21] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Everest Hinton. A simple framework for contrastive learning of visual representations. 2020.
[22] Roman Vershynin. Introduction the non-asymptotic analysis of random matrices. 2010.
[23] Roman Vershynin. High-dimenssooal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[24] Dmitrii Ostrovskii and Francis Bach. Finite-sample analysis of m-estimators using self- concordance, 2018.
[25] Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17(one):1 - 6, 2012.
[26] Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex optimization, 2017.
[27] Francis Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4(none):384 414, 2010.
11

---

[28] Roy Frostig, Rong Ge, Sham M. Kakade, and Aaron Sidford. Competing with the empirical risk minimizer in a single pass, 2015.
[29] Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
[30] Axel Ruhe. Perturbation bounds for means of eigenvalues and invariant subspaces. BIT Numerical Mathematics, 1033):343-35,, 1970.
12


Reviews:
[{"review_id": "DyRPHuRRVw", "reviewer": "Reviewer_3UFt", "summary": "The authors present theory and algorithms for training multinomial logistic regression models in the pool-based active learning setting; how we should choose $b$ extra points to label from a pool of unlabeled ones, so that when we train a model including the newly acquired labeled points the excess risk of the classifier is minimized. The provide with novel asymptotic lower and upper bounds for the excess risk under sub-gaussian assumptions on the point distribution, and they show that excess risk is in $\\Theta$ of the Fisher Information Ratio between the proposal and point distributions. This justifies algorithms which select points based on the minimization of Fisher Information Ratio. They further devise an algorithm for $(1 + \\epsilon)$-optimal minimization of the Fisher Information Ratio objective. The algorithm depends on approximating the oracle predictive model $p(y|x, \\theta^*)$ by a pretrained classifier, a continuous convex relaxation of the NP-hard discrete problem of point selection, and a greedy regret minimization procedure for sparsifying the continuous solutions, while maintaining bounds for the optimality of the final solution. Finally, they perform extensive experimentation on synthetic and image classification benchmarks to demonstrate that 1) their bounds are numerically valid, 2) their method outperforms chosen baselines.", "questions": "### Questions\n*  On a more general note, active learning might prove itself more advantageous when unlabeled points U come from a different distribution than the actual distribution $p$ that we want to evaluate the excess risk under. Such example is the setting of training with class-imbalanced sets (or more generally datasets which have been collected under biased processes), which is a common issue with uncurated large-scale datasets collected in-the-wild. Changing the setting slightly, e.g. by assuming access to a small set S of curated class-balanced samples, might incur benchmarks that are even more favorable to using approaches like FIRAL. What are the authors thoughts about such baselines and problems?\n\n### Typos and Edits\n* Line 17: “we use **the** sample the b points” -> “we use to sample these b points”\n* Line 25: “is bounded above and below **by** FIR”. Also, there should be a citation about FIR at that place.\n* Line 36: “sub-Guassian”\n* Line 38: NP-hard problem needs a citation there\n* Line 80: $V_p$ definition has a $q$, which should be $p$", "limitations": "See Weaknesses and Questions.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1.  They provide asymptotic lower and upper bounds for the excess risk **under sub-gaussian assumptions** on the point distribution, and they show that excess risk is in $\\Theta$ of the Fisher Information Ratio between the proposal and point distributions. This weakens bounded domain assumptions found for similar bounds in the literature.\n2.  The employed sparsification methodology in the provided algorithm seems to be novel in the context of pool-based active learning, while maintaining the ability to have performance guarantees.\n3.  Numerical experiments are extensive and demonstrate that the algorithm outperforms the compared baselines. Even in the larger scale ImageNet-50 case, with pretrained feature extractors, their method provides with some benefits over random sampling.", "weaknesses": "1.   Portion of the effort and presentation goes into reducing the requirement of performing eigendecompositions of a $\\tilde{d} \\times \\tilde{d}$ matrix for each unlabeled point to performing eigendecompositions of $(c - 1) \\times (c - 1)$. However, there is still need to perform $b$ eigendecompositions of  $\\tilde{d} \\times \\tilde{d}$ matrices in order to use the FTRL algorithm. As a result, complexity is still $O(\\tilde{d}^3)$.\n2.   It seems that in more demanding cases (like ImageNet-50 presented in paper), there are diminishing returns from using an active learning setting like FIRAL over randomly sampling from unlabeled samples. This may discourage practitioners from implementing a pool-based active learning approach over random sampling from unlabeled samples, in order to avoid computational complexity issues and implementation overheads. This seems to be significant as the authors chose to further embed features extracted from pretrained networks with SimCLR to an even lower dimensional space using spectral embeddings. Evaluating the proposed algorithm under more practical considerations, it would be interesting to see the baseline of random sampling (and even K-means) from the unlabeled pool using instead the full $D$ dimensional extracted features from the pretrained network (in the cases of CIFAR10 and ImageNet-50); baselines which are certainly computationally possible to execute.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 3UFt for the review and comments!\n*  **On the algorithm complexity:**\nPlease see our general response.\n\n\n*  **Experiment on pretrained frozen embeddings:**\nWe compared various active learning methods on CIFAR-10 using frozen pretrained embeddings with a dimension of 512. The results of this comparison are presented in Figure 3, which is included in the rebuttal PDF. In the plot, it is evident that FIRAL outperforms the  methods up to the 200 labeled points budget. After this point, uncertainty-based methods, BAIT and FIRAL demonstrate comparable performance levels.\n\n\n*  **Experiment on imbalanced dataset:**\nThank you for pointing this to us, this is an excellent point. Indeed,  active learning helps a lot with imbalanced datasets.  We tested FIRAL on a class-imbalanced CIFAR-10 (Figure 2 in the rebuttal PDF). We observe that FIRAL and BAIT are not sensitive to class imbalance in the active pool and  significantly outperform the other methods."}, {"review_id": "qWLGJsNLDy", "reviewer": "Reviewer_C5TF", "summary": "This paper develops a pool-based active learning method for multinomial logistic regression, following a long line of work using the Fisher Information Ratio as a criterion for active set selection. The paper establishes FIR to tightly (within constants) characterize excess risk (Theorem 3), so that this can be used to select a set of points for active learning. This method is guaranteed pretty well (Theorem 4). ", "questions": "- The parameter settings for the real-world experiments are unclear right now (e.g. for \\eta); the included code has \\eta = 200, but is this ok for all datasets?\n- I'd like to see the results with multinomial logistic regression on pretrained frozen embeddings, i.e. \"linear probing.\" The theory here might actually reflect practice closely enough to make the results noteworthy. This type of approach would strengthen the paper a lot, and opportunities to do so with theory in non-toy settings are not so common.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "It's nice that the evaluations include strong baselines like BAIT; this is a valuable contribution because of the computational efficiency of the proposed method. \\tilde{d} is relatively small (hundreds) in useful regimes, where the proposed method would be quite efficient. I would not be entirely convinced that it performs better than BAIT without the empirical evaluations - but since they are present and look promising, this seems like a useful method. \n\nThe setting of multinomial logistic regression is at once specific enough to be useful here, and general enough to be interesting (could be any discrete label). So the extent to which theory meets practice here is uncommon and laudable - fantastic problem selection, and approach (with the FIR being the \"right\" quantity for other exponential families). ", "weaknesses": "The sparsification problem in (14) in Section 4.3 is where a lot of looseness in the theory creeps in; optimizing the eigenvalue for sparsification is a roundabout way of selecting points. I am a little puzzled by the relaxation of Section 4.3; the natural relaxation of the convex program (13) is a randomized rounding procedure optimizing over z \\in [0,1]^{m} , rather than optimizing over the positive orthant as in (14). I am also curious about the choice of FTRL for sparsification. It works well enough, but initially was quite confusing in the exposition.\n\nIn Figure 2, dashed constant-slope lines would help readability a lot. \n\nThe main theoretical results are stated in an unnecessarily complex way, I believe. \n- The complex dependence on \\alpha is not really necessary to fully write out in the theorem statements. Fig. 1 handles this well, but in order to interpret it in context, you should stress that n needs to be O(\\tilde{d}) for \\alpha to be low and the bounds to be tight. The complex interplay between these variables could overall use better explanation. \n- Theorem 4's use of the \\lesssim makes it difficult to interpret the (1+\\epsilon) prefactor on the right-hand side, and I had to rummage in the appendix and proofs to understand what the result is trying to express.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer C5TF for the review and comments!\n* **Relaxation problem:**\nThe reviewer is correct. The constraint on Equation (14) should be $z\\in[0,1]^m$. We are sorry for the confusion caused by the expression. We will fix it in the new version.\n\n* **Why use FTRL for sparsification problem?:**\nWe use FTRL because it allows to prove optimality of our algorithm.  Specifically, with FTRL we can establish a lower bound in Equation (18) for $\\lambda_{\\min}\\big(\\sum_{t\\in [b]}\\widetilde{\\bf H}(x_{i_t})\\big)$. Our goal in point selection consequently becomes the maximization of this lower bound, encapsulated by Equation (19), which is equivalently expressed in Equation (23). For the reason why Equation (18) is satisfied, we provided an explanation in Appendix F.3. The primary steps can be outlined as follows: (1) FTRL algorithm provides an upper bound (Equation (250)) for the  cumulative regret (defined in Equation (245)). (2) After applying Lemma 43, we can get the lower bound (Equation (254)) for the minimum eigenvalue of the summed loss matrices, i.e. ${\\lambda_{\\min}}\\big(\\sum_{t \\in [b]} {\\bf F_t}\\big)$. (3) Since this bound is satisfied for any symmetric semi-positive definite loss matrix with dimension $\\tilde{d}$, we can let loss matrix ${\\bf F_t}=\\widetilde{\\bf H}({x_{i_t}})$, thereby arriving at the obtained lower bound in Equation (18).\n\n* **Clarifying main theoretical results:**\nThanks for pointing them out. We will address them promptly by revising the content and discussion of Theorems 3 and 4 to ensure it becomes more concise and appropriately expressed.\n \n * **Selecting $\\eta$:**\n  Please see our general response. \n \n* **Experiment on pretrained frozen embeddings:**\nWe compared various active learning methods on CIFAR-10 using frozen pretrained embeddings with a dimension of 512. The results of this comparison are presented in Figure 3, in the rebuttal PDF.   In the plot, it is evident that FIRAL outperforms other methods  methods until 200 points are labeled. After this point, uncertainty-based methods, BAIT and FIRAL demonstrate comparable performance levels."}, {"review_id": "tyQDDXpzGk", "reviewer": "Reviewer_zZMa", "summary": "This paper proposes a novel active learning algorithm called FIRAL for pool-based active learning in multinomial logistic regression. The paper investigates the theory and algorithms for pool-based active learning and compares FIRAL to other active learning methods in terms of classification error. The authors use finite sample analysis to establish FIRAL-based bounds for the excess risk in the case of multinomial logistic regression with sub-Gaussian assumption for the point distributions. The experiments conducted on various datasets show that FIRAL outperforms other active learning algorithms in terms of classification error.", "questions": "In Line 67, the logistic regression classifier here is very simple, is it possible to apply this method on more complex classifiers, such as ResNet, Transformer, which need more data to train?\n\nWhat is the meaning of \\theta_*? The optimal parameters to predict y?\n\nCould you compare with uncertainty-based active learning method, such as \"Towards better uncertainty sampling: Active learning\nwith multiple views for deep convolutional neural network\"?\n\nCould you do experiments on the whole ImageNet data set, not just ImageNet-50?", "limitations": "The notation is not constant. For example, the subscripts of \\theta_0 and \\theta_n have different meaning.\n\nSome writing errors. Line 17 \"we use the sample the b points\". Line 20 \"choose q in order minimize\"... Please check them.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The equation and proof make sense. Good introduction on this part. \n\nConvinced theory.", "weaknesses": "Not enough introduction on related work.\n\nThe target task is logistic regression classifier. I think it is simple and has been researched for many years. If this method can be applied on more complex classifiers or segmentation, it would be better.\n\nNo ablation study on hyperparameter, such as \\eta.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer zZMa for the review and comments!\n\n* **Introduction on related work:**\nWe will add more discussion on related work in the new version.\n\n* **Classifier choice:**\nWe used the multinomial logistic regression classifier in order to be able to conduct the theoretical analysis. We believe our non-asymptotic analysis in Theorem 3 and our algorithm FIRAL can be extended to other Generalized Linear Models with the change of Fisher information matrix. We remark that we did use deep-learning based contrastive learning for feature extraction, on which we then apply our classifier. Comparison of our current methodologies  with a deep learning classifier that directly uses FIRAL would be interesting but also challenging, as it would be very hard to train a deep learning network with just a handful of examples. This comparison is important but beyond the scope of the paper. \n\n* **Selection Hyperparameter $\\eta$:**\nPlease see our general response to all reviews.\n\n* **Question regarding the definition of $\\theta_*$**\n In original submission we introduced $\\theta_*$ in lines 71--72:  we assume that the true distribution  $p(y|x)$ is given by the multinomial logistic regression with $\\theta_*$. \n\n* **Compare with uncertainty-based active learning methods**\nWe did compare uncertainty-based active learning methods such as \"entropy\" and \"Var Ratios\" in our paper (Figure 3 in the original submission). \"Var Ratios\"  is also referred as \"Confidence\" in some literature.\n\n* **Whole ImageNet dataset**\nUnfortunately, the $O(b \\tilde{d}^3)$ scaling of FIRAL's current implementation  makes it very expensive to apply the scheme to the entire ImageNet as it would require solving thousands of 40K-by-40K eigenvalue problems (if we use 40 features for each data point). However, we would like to emphasize that this is not a fundamental limitation of FIRAL. As we discussed in our common response, FIRAL can be significantly sped up. \n"}, {"review_id": "4BH4G85viD", "reviewer": "Reviewer_B8jR", "summary": "This paper studies active learning when the underlying data distribution follows the multinomial logistic model. This paper considers the pool-based setting and designs an algorithm to select the sample to query in a batch fashion. There are two main contributions: (1) The paper shows that the excess risk is lower and upper bounded by the Fisher Information Ratio. (2) propose an algorithm to select the samples to optimize the Fisher Information Ratio and thus minimize the expected risk. Theoretical analysis and experiments are conducted to validate the proposed approach.", "questions": "- could you highlight the main technical challenges and contributions of the paper beyond the existing work? (please refer to the first point of weaknesses for more details)\n- when the assumption on the Hessian $H_p$ and $H_q$ required by Theorem 3 is satisfied? How large is the constant $\\sigma$?\n- could you provide more discussion on the influence of the labeled dataset on the proposed method? (please refer to the third point of weaknesses for more details)", "limitations": "There are still some limitations in the paper:\n- realizable assumption: the theoretical analysis is established on the realizable assumptions such that the data distribution follows the logistic regression model. \n- tightness of the excess risk: the tightness of the proposed theoretical bound is not discussed.\n\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The strengths of the paper are as follows:\n+ This paper shows the relationship between expected excess risk and the fisher information ratio for the multinomial logistic regression model\n+ This paper proposes an algorithm to maximize the fisher information ratio\n+ The technical part of this paper is well-written and easy to follow", "weaknesses": "The weaknesses of the paper are as follows:\n\n- unclear comparison with existing work and novelty: my main concern about the paper is the novelty compared with existing literature. \n   -  comparison with [11]: as mentioned by the authors, the non-asymptotic relationship between the FIR and excess risk has been provided in [11] for the generalized linear model. However, I am a little bit confused by the claim in lines 43-44 that \"... the assumption that the loss function is strictly self-concordant (assumption 2 in [11]), which does not hold for the logistic regression case.\" Although the logistic regression loss is not strictly self-concordant, it is a general self-concordant function [27]. Based on the general self-concordance, it seems to me one can also bound the gap between the Hessians of two points as Assumption 2 in [11]. The authors also use the general self-concordant property (Proposition 31) to prove Theorem 3. I think it would be better if the authors could highlight that logistic loss is a general self-concordant function and highlight the novelty compared with [11].\n   - comparison with [14]: it seems to me the method used to optimize the FIR is largely established on [14]. Proposition 7 is similar to a combination of Eq (8) and Proposition 3.1 in [14]. Both papers use the regret analysis of FTRL to show the lower bound in Proposition 8.  I think the paper would have a more significant influence if the author could highlight the main challenge of applying the analysis of [14] to the logistic regression model.\n\n- about assumption in Theorem 3: Theorem 3 relies on the condition that $H_p(\\theta_*)\\leq H_q(\\theta_*)$. It is unclear to me how large this constant would be and how to verify the condition in practice since $\\theta_*$ is generally unknown.\n\n- about the labeled dataset: the algorithm requires a labeled dataset $S_0$ to estimate the unknown parameter $\\theta_*$. However, it is unclear to me how to obtain such a labeled dataset and when it is sufficient to obtain a good approximation of $\\theta_*$ for the following active learning. As shown in Theorem 4, the number of labeled data will affect the coefficient $\\alpha_0$ appearing in the exponential term that can be potentially large. I think it would be nice if the author could provide a more detailed discussion on the effect of the initial labeled data on the proposed algorithm.\n\n- about the constants in Theorem 4: since $\\alpha_0$ and $\\alpha_n$ are related to $n_0$ and $n$, I am not sure they are appropriate to be considered constants in the proposed bound. \n\n\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer B8jR for the review and comments!\n* **Novelty of Theorem 3 compared to [11]:**\n\t* Our primary contribution concerning Theorem 3 in comparison to the work presented in [11] is the generalization to sub-Gaussian distributions for the points. The proofs in [11] rely on an assumption of a bounded support for the points where we do not use this assumption.  We discussed this distinction in Lines 132--137 in our original submission. We remark that the bounded assumption is not explicitly stated in [11]. But it is required for the proofs in [11] to be valid. Specifically, item 5 of Assumption 1 in [11] assumed that  $\\nabla L(y|x, \\theta^*)$ is bounded by a constant $L_1$. For multinomial logistic regression, by the expression of the loss gradient in our paper (Equation (39)), we can infer that [11] assumes that the point $x$ is in a bounded domain. \n\t* Another contribution of our work on Theorem 3 in comparison to [11] is that we empirically demonstrate the excess risk bounds derived in Theorem 3 using synthetic datasets (as detailed in Section 5 and Appendix G.1).\n\t* Regarding the concern raised by the reviewer on Assumption 2 in [11] pertaining to multinomial logistic regression, we maintain our position that _Assumption 2 in [11] can not be deduced by the results in [27]_. Let us explain. Using the notation established in our paper, Assumption 2 of [11] asserts that there exits $L_4>0$ such that  $-L_4 \\lVert\\Delta\\rVert_2 {\\bf H}_p({\\theta^\\ast}) \\preceq {\\bf H}_p (\\theta) - {\\bf H}_p({\\theta^\\ast}) \\preceq L_4 \\lVert\\Delta\\rVert_2 {\\bf H}_p({\\theta^\\ast})$, where $\\Delta\\triangleq \\theta - \\theta^\\ast$.  We can interpret Equation (6) in Proposition 1 of [27] as implying $\\big(e^{-R\\lVert\\Delta\\rVert_2}-1\\big){\\bf H}_p({{\\theta}^{\\ast}}){\\preceq}{{{\\bf H}_p}(\\theta)-{{\\bf H}_p}({\\theta^\\ast})}{\\preceq}\\big(e^{R\\lVert\\Delta\\rVert_2}-1\\big){\\bf H}_p({\\theta^\\ast})$, where $R>0$ corresponds to the constant delineated in Proposition 1 of [27].  We can get the lower bound of Assumption 2 in [11] from this relation. But we can not deduce the upper bound of Assumption 2 in [11] since $e^{R\\lVert\\Delta\\rVert_2} - 1$ can not be upper bounded by $L_4 \\lVert\\Delta\\rVert_2$  for constant $L_4$.\n* **Novelty of FIRAL compared to [14]:**\nIn Lines 53 to 58 we discussed the two main challenges of applying the regret minimization approach in [14] for optimal design to our active learning setting for multinomial logistic regression. We appreciate the reviewer for raising this concern and agree on the need for a more detailed discussion on challenges and our contributions. Below are the main points:\n    - Algorithmically, there are technical details that are needed in extending the approach presented in [14] to formulate the point selection objective within our specific context. In [14], they work with a loss matrix that is essentially a rank-1 matrix $x x^\\top$ for some $x$ in $d$-dimension, resulting in a  straightforward point selection objective (as seen in Line 9 of Algorithm 1 in [14]). In contrast, the loss matrix in our scenario, denoted as $\\widetilde{{\\bf H}}(x_{i_t})$  (Equation (15)),  possesses a minimum rank of $c-1$ and can even be a full-rank matrix, contingent upon the labeled points from prior rounds. In order to manage the complexity associated with directly utilizing objective (19), we delve into the structure of the Fisher information matrix and employ algebraic techniques to establish an equivalent objective (23) that is more computationally efficient. We believe that our analysis is more technical compared to the  situation addressed in [14].\n    - Theoretically, the task that presents the most technical challenge compared to [14] when establishing the performance guarantee for our algorithm is _Proposition 9_.  The corresponding bound derived is Lemma 3.2 in [14].  The distinction between the characteristics of the loss matrices  significantly complicates the derivation of such a general bound in Proposition 9.  We have to use several algebraic tricks to obtain the  bound for the near-optimal performance guarantee (see Appendix F.4). In our opinion, our proof is not trivial,  which is perhaps corroborated by comparing the length of our proof with the proof of Lemma 3.2 in [14]. \n    - Empirically, we conduct active learning experiments on real-world datasets and demonstrate that our algorithm outperforms the compared baselines.\n* **Parameter $\\sigma$:**\nWe thank the reviewer for pointing this out. This is a typo in our manuscript, $\\sigma>1$ should be $\\sigma >0$ in Theorem 3 (also Theorem 32 for detailed version). We do not require $\\sigma>1$ in our proof. We apologize for the confusion caused by this typo. We will fix it in the new version. \n* **Influence of initial labeled dataset:**\nWe believe that the influence of the initial labeled dataset on the performance of active learning depends on the specific dataset in question. In our numerical experiments, using CIFAR-10 as an example, we randomly select one labeled point from each class to construct $S_0$. This approach ensures an equitable starting point for all methods, enabling a fair comparison. We agree that in practice, the selection of initial data points to label, absent any label information, can exert a significant impact on the initial performance of active learning, particularly when the budget for $|S_0|$ is severely restricted, say $1c$ or $2c$. There are several methods for selecting $S_0$: Random sampling, K-means clustering, or optimal experimental design [14]. In Table 1 of the rebuttal PDF, we compare the performance of these different sampling methods for $S_0$ for  $|S_0|=20$ and its effect to FIRAL. In Table 1, we observe that the effect of $S_0$ on the performance of FIRAL  is not significant (for this particular experiment). \n* **Constants in Theorem 4:** \nThanks for pointing this out. We will modify our expression regarding to these two constants in a more proper way."}, {"review_id": "4ma3QGNYgN", "reviewer": "Reviewer_PwwV", "summary": "The authors first prove that the excess risk of multinomial logistic regression with under subgaussian data distribution is lower and upper bounded by terms involving the ratio of the Fisher information of the unlabeled data and the Fisher information of the labeled data.\nThe authors then propose an algorithm for active learning, based in FIR minimization, and prove a performance guarantee for it.\nExperimental results on simulated and real world datasets demonstrate well the performance of the proposed approach.", "questions": "1. Can the authors refer to the capabilities of their algorithm in terms of scale?\n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithm stands on a solid mathematical background.\n2. The experimental results demonstrate the performance benefits over competitive methods.", "weaknesses": "1. The manuscript is very technical and not easy to read.\n2. Comparison to competitive methods in terms of computation is missing. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer PwwV for the review and comments!\n* **Not easy to read:**\nWe acknowledge that it might be hard to comprehend Section 4.3 for readers unfamiliar with regret minimization. We have tried explain the overal merit of our approach while leaving most technical details in Appendix. We are open to any suggestions that could enhance the readability of our paper.\n\n* **Comparison in computation:**\nWe interpret the question to refer the computational complexity of the algorithm. Our current implementation of FIRAL is much more expensive than random, k-means, and uncertainty-based methods. Its cost is comparable to BAIT. However, (1) we have not optimized some algorithmic details of FIRAL; and (2) FIRAL and BAIT significantly outperform the other methods. \n\n* **Scale capabilities:**\nPlease see our general response. "}]

Author rebuttal:
# General Response:
We thank the reviewers for their careful read of our paper, their comments, and  their suggestions. We have fixed all the typos mentioned in the reviews. We have submitted responses to individual researchers. We also submitted a PDF with additional results.

There were two issues that were raised by two reviewers: the complexity of the algorithm and the selection of the hyperparameter $\eta$. We address them below.

###  **Complexity of algorithm**
In our original submission, we stated the computational complexity of FIRAL at line 231.  Recall that $c$ is the number of classes, $d$ is the number of features per point, $\tilde{d}=d(c-1)$, $m$ is the number of unlabeled points in the pool, and $b$ is the number of points to select for labeling.  We use a dense-matrix SPD eigenvalue solver,  and  direct linear solver. These yield the complexity of FIRAL, as implemented now: $O(m c^3 + b \tilde{d}^3 + m \log m \tilde{d}^3).$  The $c^3$ term is due to Eq 23 (trace); the $b$-term is the SPD-eigenvalue solve in Alg 1, line 8 for  $\left(\sum_{s=1}^t \tilde{H}_s\right)$.  The $\log m$ comes from the $m$ linear solves (Alg 2, line 5, linear solve for $\Sigma$ and the trace) and $\log m$ expected iterations ($T$ in Alg 2, line 2).  

The performance of these steps can be significantly sped-up by (1) using matrix-free iterative solvers and (2) exploiting the structure of $H(x)$ (Eq 10, line 164). The storage of $H(x)$ is just $d+c$ if we only store ${\bf h}(x)$ and $x$. A matrix-free vector multiplication with $H(x)$ can be done in $\tilde{d}$ time using the structure of Eq 10. This structure can be exploited to accelerate computations with $\tilde{H}$ and $\Sigma^{-1}$. The trace calculations, eigenvalue solves, and linear solves can be done approximately using Krylov methods and randomized algorithms.

 For example, Eq 23 and Alg 2 trace calculations can be approximated using randomized trace estimation that requires approximate matrix-vector multiplications; and can be readily parallelized on multi-GPU architectures. The linear solve in Alg 2 can be done using the Conjugate Gradient method. The eigenvalues solve can be done using an iterative Lanczos solver. In this an approximation of $\nu_t$ could be in principle be computed in $O(b \tilde{d})$ cost. 
 
 We believe that by introducing fast algorithms and a more scalable high-performance implementation, the algorithm could scale to million of points and thousands of classes.  Our goal in this paper was simply to establish the theoretical correctness and optimality of FIRAL;  and to demonstrate its feasibility using modest-scale experiments. Scaling FIRAL to large datasets requires significant effort and merits a separate analysis. Such effort is beyond the scope of this paper. 

### **Selection of hyperparameter $\eta$:**
The selection of $\eta$ is done use a grid search and doesn't require labeling. (In our code this search is manual, but it can be automated.)  In our original submission, we discussed tuning $\eta$ in Appendix G.2 (Lines 1132 to 1134): we tested different values of $\eta$ to determine the one that maximizes $\lambda_{\min}\big(\sum_{t\in[b]}\widetilde{ \bf H}(x_{i_t})\big)$, as this is the main goal of our sparsification problem.

In the rebuttal PDF in Figure 4,  we report results of an ablation study on $\eta$ and included the results in Figure 4 of the newly submitted file: we plotted $\lambda_{\min}\big(\sum_{t\in[b]}\widetilde{ \bf H}(x_{i_t})\big)$ along with the accuracy under different values of $\eta$ in the first two rounds of the active learning tests on CIFAR-10. In our experiments, we explored different values of $\eta$ to determine the one that maximizes $\lambda_{\min}\big(\sum_{t\in[b]}\widetilde{ \bf H}(x_{i_t})\big)$, as this is the main goal of our sparsification problem (parameter tuning in Appendix G.2).  It is evident that $\lambda_{\min}\big(\sum_{t\in[b]}\widetilde{ \bf H}(x_{i_t})\big)$ serves as a valuable guide in selecting an appropriate $\eta$ that leads to good accuracy performance.


Meta-review: This paper introduces FIRAL, an algorithm with theoretical guarantees under weaker assumptions than prior work and convincing experimental results. Given the unanimous recommendation for acceptance from the four reviewers, I recommend acceptance.
Decision: Accept (poster)