FIRAL: An Active Learning Algorithm for Multinomial Logistic Regression

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. The authors then propose an algorithm for active learning, based in FIR minimization, and prove a performance guarantee for it. Experimental results on simulated and real world datasets demonstrate well the performance of the proposed approach.

Strengths

1. The proposed algorithm stands on a solid mathematical background. 2. The experimental results demonstrate the performance benefits over competitive methods.

Weaknesses

1. The manuscript is very technical and not easy to read. 2. Comparison to competitive methods in terms of computation is missing.

Questions

1. Can the authors refer to the capabilities of their algorithm in terms of scale?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

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.

Strengths

The strengths of the paper are as follows: + This paper shows the relationship between expected excess risk and the fisher information ratio for the multinomial logistic regression model + This paper proposes an algorithm to maximize the fisher information ratio + The technical part of this paper is well-written and easy to follow

Weaknesses

The weaknesses of the paper are as follows: - unclear comparison with existing work and novelty: my main concern about the paper is the novelty compared with existing literature. - 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]. - 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. - 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. - 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. - 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.

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) - when the assumption on the Hessian $H_p$ and $H_q$ required by Theorem 3 is satisfied? How large is the constant $\sigma$? - 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)

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

There are still some limitations in the paper: - realizable assumption: the theoretical analysis is established on the realizable assumptions such that the data distribution follows the logistic regression model. - tightness of the excess risk: the tightness of the proposed theoretical bound is not discussed.

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.

Strengths

The equation and proof make sense. Good introduction on this part. Convinced theory.

Weaknesses

Not enough introduction on related work. The 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. No ablation study on hyperparameter, such as \eta.

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? What is the meaning of \theta_*? The optimal parameters to predict y? Could you compare with uncertainty-based active learning method, such as "Towards better uncertainty sampling: Active learning with multiple views for deep convolutional neural network"? Could you do experiments on the whole ImageNet data set, not just ImageNet-50?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The notation is not constant. For example, the subscripts of \theta_0 and \theta_n have different meaning. Some writing errors. Line 17 "we use the sample the b points". Line 20 "choose q in order minimize"... Please check them.

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).

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. The 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. In Figure 2, dashed constant-slope lines would help readability a lot. The main theoretical results are stated in an unnecessarily complex way, I believe. - 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. - 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.

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? - 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Yes

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.

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. 2. 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. 3. 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)$. 2. 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.

Questions

### Questions * 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? ### Typos and Edits * Line 17: “we use **the** sample the b points” -> “we use to sample these b points” * Line 25: “is bounded above and below **by** FIR”. Also, there should be a citation about FIR at that place. * Line 36: “sub-Guassian” * Line 38: NP-hard problem needs a citation there * Line 80: $V_p$ definition has a $q$, which should be $p$

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

See Weaknesses and Questions.

Convincing rebuttal, thank you for extra experiments

- **On the algorithm complexity**: This is maintained as a weakness of the current paper, but I am convinced that with sufficient effort in terms of selection of solvers we can keep this kinda tractable in the large-scale scenario. I am looking forward for future work applying this in large-scale. - **Experiment on pretrained frozen embeddings** and **experiment on imbalanced dataset**, thank you for providing these convincing experiments. I am raising the score to 7.

Update to review

I have read the comments made by the other reviewers, as well as the author's rebuttal. One concern I have is regarding the high complexity of the algorithm in terms of $\tilde{d}$, which is prohibitive for most practical senses. While I still recommend accepting the paper, I am waiting to read the post-rebuttal comments of the other reviewers and decide whether I should update the score from 7 to 6 in light of this issue.