Selective Mixup Fine-Tuning for Optimizing Non-Decomposable Objectives

We sincerely thank reviewer 4axA for their thoughtful questions and efforts to review our work. We provide our clarifications below to the concerns mentioned.

The authors use the first-order Taylor expansion on Eq. 5. I am curious about the performance if the second-order terms are involved, i.e., calculating the third term of Eq. 5. Also, the first-order gradient can be also approximated by f(x+ h) + f(x-h) -f(x) / 2h. Would it give better performance than the current one-sided approximation?

As long as we consider a first-order method similar to SGD, it is sufficient to consider the first-order term in eq (5). Further, considering any second-order terms will involve the calculation of Hessian to take advantage in optimization, calculation of that which is expensive for neural networks with large $W$.

We now explain the above in more detail. By considering the second-order term in eq (5), the definition of gains would slightly change, and the expected directional vector $V = \sum_{i,j}P_{Mix} (i, j) V_{ij}$ would slightly change accordingly. On the other hand, in the convergence analysis (Theorem 4.2), the expected directional vector affects the constant $c$, which is a lower bound of the cosine similarity of the expected directional vector and the true (normalized) gradient. If the cosine similarity is larger, then we have better convergence. Since maximizing the cosine similarity is equivalent to maximizing Gain, our method already aims to maximize the cosine similarity. This indicates that when we consider the second-ordered term in eq (5), to achieve better performance, we have to consider a second-order method using a Hessian of the loss function eq (2) instead of SGD. Therefore, as long as we consider a first-order method such as SGD, it is sufficient to consider the first-order term in eq (5).

Regarding the finite difference $(f(x + h) - f(x - h))/2h$, to the best of our knowledge, such an estimation is used for an estimation of gradients of the smoothed version of the objective function (e.g., [Agarwal el al., 2010]). Since we assume that the change (i.e., Gain) of the objective $\psi$ can be approximated as a linear function of the directional vector $V$, we do not see an advantage of considering the two sided-approximation. More precisely, we assume that the change $\Delta \psi(V) := \psi(\widetilde{C}[(W + \eta V)^T g]) - \psi(\widetilde{C}[W^T g])$ is approximately equal to a linear function of $V$, where $V$ is a directional vector and $\eta > 0$ is a learning rate. Since $\Delta \psi(V)$ is approximately linear in $V$, the two side approximation $\Delta \psi(V) - \Delta\psi(-V)$ is approximately equal to $2 \Delta \psi(V)$. Therefore, by considering two-sided approximation, we would only have an additional constant factor (2) in our argument. However, in a more generalized setting, where the assumption regarding the linear approximation does not hold, we might be able to improve our method (e.g. in terms of robustness) by utilizing a two-sided approximation. This would be an interesting extension.

Can authors provide some ablation studies on the hyper-parameters, such as the imbalanced ratio and the number of samples for feedback?

We request you look at Appendix K, where we have provided analysis on hyper-parameters. Here, we provide the ablation of the size of the validation set vs. the Mean Recall for the CIFAR-10 dataset with an imbalance ratio, $\rho_l=\rho_u=100$, where we observe robust performance of SelMix even when data is reduced to 10% of initial.

Table 2: Comparison of SelMix's performance for different sizes of the feedback set.

We show the ability of SelMix to boost performance in various imbalanced settings. We consider the CIFAR-10 dataset with an imbalance ratio, $\rho_l=\rho_u=50, 100, 200$ and show the results for optimizing Mean Recall and Min. Recall.

Table 2: Comparison of SelMix's performance on different imbalance factors (Setup as in Table 1).

Further in the Appendix, we compare the performance of different sampling policies for different values of scaling parameters (Fig. K.1). We also compare against different substitute mixups for the input, such as PuzzleMix and CutMix (Tab. K.5). We have provided results for different permutations of imbalance ratios for the labeled and unlabeled data such as $\rho_l = \rho_u = 100$ in Tab. 2(L) , $(\rho_l, \rho_u)= (100, 1)$ and $(\rho_l, \rho_u) = (100, \frac{1}{100})$ in Appendix Tab. H.1 We also compare the effectiveness of substituting cross-entropy loss with LA loss in FixMatch, which yields a better feature extractor, resulting in an overall boost in performance in Tab. K.4.

We hope our response has clarified your concerns; please feel free to reach out to us if there are any other questions.

References

1. Agarwal, Alekh, Ofer Dekel, and Lin Xiao. "Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback." Colt. 2010.

What is the prior distribution on labels? How do you define this in practice ?

Prior distribution $\pi_i$ over labels $y=1...K$, represents the probabilities of obtaining a sample with a label $y=i$when sampled at random from a dataset before observing any specific data. We have obtained the prior distribution estimates, using the label statistics $y$ of the labeled training data present.

What is the unconstrained confusion matrix? It is never clearly defined in the paper, but is important to define the gain.

Thanks for the interesting question, it actually captures mathematical beauty of the proposed approximation. The unconstrained confusion matrix $\widetilde{C}$ is implicitly defined in the "Estimation of Gain Matrix" paragraph by $C_ {i} = \pi_ {i} softmax(\widetilde{C}_ {i})$, where $C_ {i}$ and $\widetilde{C}_ {i}$ are $i$-th row vectors of $C$ and $\widetilde{C}$, respectively. Although the matrix $\widetilde{C}$ is not uniquely determined since the softmax function is not one-to-one, the approximation (the first term of the RHS of eq (8)) is unique as the derivative of all these are unique. We explain this more in detail. In the approximation formula, we only need jacobian $\partial \psi/\partial \widetilde{C} = \frac{\partial \psi}{\partial {C}} \frac{\partial {C}}{\partial{\widetilde{C}}}$. We note that gradient of the softmax function can also be written as a function of the softmax function (i.e., $\frac{\partial \sigma_l}{\partial \xi_m} = \delta_{lm} \sigma_l(\xi) - \sigma_l(\xi) \sigma_m(\xi)$, where $\sigma_l(\xi) = softmax_l(\xi)$ for $\xi \in \mathbb{R}^K$, $1 \le l, m \le K$). Therefore, the first term of the RHS of eq (8) is uniquely determined even if $\widetilde{C}$ is not uniquely determined. We appreciate your suggestion and will clarify this in the final version.

We sincerely hope that our response has cleared the misunderstanding due to a type, which leads to an improved impression of our paper. Please feel free to contact us for further clarifications.

We thank the reviewer LrpR for their efforts in reviewing our work and providing us with very valuable feedback. We address the concerns raised by you as follows.

This discrepancy in the comparison may not provide a fair assessment of the true impact of SelMix. As can be seen in Table H.2 and H.1, FixMatch + LA shows already significant improvements over vanilla FixMatch. This makes it challenging to evaluate whether SelMix's improvements reported in the benchmarks are due to the approach or its combination with a more advanced baseline. A fair comparison would involve evaluating SelMix with vanilla FixMatch to better understand its relative performance,

Thanks for pointing out this inconsistency due to a typo of w/; we have corrected typos in the revision. We want to clarify that all the methods we have compared in Table H.1 are methods which are trained from scratch and are not finetuning methods like the proposed SelMix (hence, w/ is not correct). Further, while comparing, we made sure that we were using the best baselines for proposed methods; for example, we used LA for DASO as their implementation as their implementation (https://github.com/ytaek-oh/daso) recommended it. Hence, to the best of our knowledge, we have provided fair comparisons.

Results with FixMatch

One potential work that uses a similar framework is CoSSL, which is a two-stage framework comprising a pre-training and a fine-tuning stage. For performing fair comparison with SelMix finetuning, we use the same pre-trained model for both for the results below. It can be observed that SelMix finetuning outperforms CoSSL fine-tuning by a large margin.

Dataset: CIFAR-10, IBR_L = 100, IBR_U = 100, N1=1500, M1=3000 (Table 1)

Dataset: CIFAR-10, IBR_L = 100, IBR_U = 1, N1=1500, M1=3000 (Table H.1)

Dataset: CIFAR-10, IBR_L = 100, IBR_U = 0.01, N1=1500, M1=3000 (Table H.1)

We sincerely thank reviewer misU for their constructive feedback on our work. We address your concerns as follows.

Literature review is not sufficient, and some sentences are over-claimed. Fine-tuning a pre-trained network for non-decomposable objectives and even non-differential objectives has been extensively developed recently. Please refer to a recent paper [1] and the references therein for more details. Particularly, the objective derived shares the same motivation as the natural evolution strategies [2] adopted in [1].

We thank the reviewer for pointing towards a concurrent paper [1], which also tries to fine-tune a model, but it operates in the scenario where the feedback is only accesssible through queries (black-box), whereas our work SelMix works in a scenario where model gradients are not-computable for certain objectives but can be approximated with gradients on other objectives (white-box). We have cited the papers in the additional related work section of our revision. Since the method proposed in [1] is based on a black-box optimization method proposed in [2], in [1] values of the objective $\psi$ can be observed only through function query, whereas we assume the objective $\psi$ and its gradients w.r.t the confusion matrix $C$ are approximately known. Since our method is a white-box optimization method, it can converge faster than black-box optimization methods such as [1]. Because we were not able to find convergence analysis in [1], we compare our result to a standard result [Agarwal et al, 2010] in the black-box optimization (bandit) literature. Corollary 4 in [Agarwal et al, 2010] suggests that the convergence rate of the black box optimization method is $O(d^2 K^2/\sqrt{t})$, while our convergence rate in Theorem 4.2 is given as $O(1/t)$, which indicates that our approach is less prone to larger values of $d$ and $K$, thus, our approach achieves better values of the objective compared to the black-box optimization approach [1].

"Some theorems are not formal and have overly strong assumptions. For instance, $z_k$ in Theorem 4.1 appears suddenly without intuitive explanation. There is no detailed explanation in the proof in the Appendix. “a reasonable directional vector for optimization” is not professional."

Thank you for your suggestion. We have improved our paper based on your comments (please refer to the submitted revision).

Although statements of Theorem 4.1 and 4.2 are formal, due to space constraint the statement of Theorem 4.3 is informal. The formal statement of Theorem 4.3 can be found in Section C.4.

The mean feature vector $z_i$ is defined in Theorem 4.1. We provide an intuitive explanation why this is necessary. Please note that $\psi$ is a function of the confusion matrix $C[h]$ of the classifier $h(x) = W^T g(x)$ (Sec. 3). By definition the $(i, j)$-entry of the confusion matrix $C[h]$ is given as

$$\mathbf{E}_ {x, y \sim D}[ 1 (y=i, \mathrm{argmax}_ {l} h(x)_ {l} = j) ]= P(y=i) \mathbf{E}_ {x \sim P(\cdot | y=i)}[ 1(\mathrm{argmax}_ {l} h(x)_ {l} = j) ]$$

Here, $P(\cdot | y = i)$ is the class conditional probability distribution. If we consider softmax instead of argmax, $C_ {ij}[h]$ is approximately given as

$$C_ {ij}[h] \approx P(y=i) \mathbf{E}_ {x \sim P(\cdot | y=i)}[ \mathrm{softmax}_ {l} h(x)].$$

Since we are interested in the change in the objective $\psi$ (Gain), by the above formula, we are interested in the change in the mean of the softmax of $h(x)$, where $x$ belongs to the class $i$. Because $h(x) = W^T g(x)$ is a linear classifier, the change in the mean of the softmax is related to the mean feature vector $z_i = \mathbf{E}_ x [g(x)]$, where $x$ belongs to the class $i$.

In Sec. 4.1, the words “a reasonable directional vector for optimization” appear twice. The first appearance follows the following inequality and “a reasonable directional vector for optimization.” is an intuitive explanation of this inequality for the vector $\widetilde{V}^{(t)}$. We have modified it to "a vector which has a sufficient component in the direction of gradient" for optimization.

$$\mathbf{E}[\widetilde{V}^{(t)}] \cdot \frac{\partial \psi(W^{(t)}) }{\partial W} > c\|\frac{\partial \psi(W^{(t)}) }{\partial W}\|.$$

Loss Proposed by ABC

ABC (Lee et al., 2021) considers the loss function of the following form for each example $(x, y)$ (Eq. 2). Here, for $i = 1, \dots, K$, $N_i$ is the number of samples in class $i$ (the class $K$ is the tail class).

$$L(F(x), y) = B (\frac{N_ {K}}{N_ {y}}) CE (F(x), y).$$

Here, for $p \in (0, 1)$, $B(p)$ is a Bernoulli Random Variable with $E[B(p)] = p$. We denote by $D$ the original long-tailed data distribution and by $D_ {B}$ the balanced data distribution so that we have the following for any (measurable) function $f$ on the data set:

$$E _ {(x, y) \sim D} [f(x, y)] = E_ { (x, y) \sim D_ {B}} [\pi_ {y} f(x, y)].$$

Here $\pi_i = P (y=i)$ is the class prior of the long-tailed distribution for class $i$.

In the definition of $L(F(x), y)$, by taking the expectation, we have the following:

$$E_ {(x, y) \sim D} [L(F(x), y)] = E_ {(x, y) \sim D_ {B}}[ \frac{N_ {K} \pi_ {y}}{N_ {y}} CE(F(x), y)].$$

Since we have approximately $\pi_ {y} \propto N_ {y}$, we see that

$$E_ {(x, y) \sim D} [L(F(x), y)] \approx const \times E_ {(x, y) \sim D_ {B}}[CE(F(x), y)].$$

Since under a balanced data distribution, accuracy coincides with the mean recall across classes and the CE loss is a surrogate loss for accuracy, we can regard the ABC loss as a surrogate loss of the mean recall.

We hope our response has clarified your concerns; please feel free to reach out to us if there are any other questions.

References

1. Agarwal, Alekh, Ofer Dekel, and Lin Xiao. "Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback." Colt. 2010.
2. Scarlett, Jonathan, Ilija Bogunovic, and Volkan Cevher. "Lower bounds on regret for noisy gaussian process bandit optimization." Conference on Learning Theory. PMLR, 2017.

We thank the reviewer iMBB for their reviews. We are delighted to know that you appreciate various aspects of our work. Thank you! We address some of the concerns raised by you as follows.

The fact that the proposed method requires only fine-tuning of a pre-trained model should result in a huge advantage in training time compared to existing methods, but this is not highlighted in the main results section of the paper.

We agree. Our method is a finetuning method, and in order to optimize for a performance objective, we do not have to train from scratch. We compare our method training time with CSST which needs to train the model from scratch for each objective. However, for this analysis, as CSST does not support the full list of objectives in the table; we use the closest surrogate object was used. The pretraining and training for SelMix and CSST was done on 4XA5000 (24gb) gpus.

Table 1. Time comparison for SelMix with CSSTDataset: CIFAR-10, $\rho_l$ = $\rho_u$ = 100, $N_1$=1500, $M_1$=3000

We will emphasize this more in the final version of the draft; thanks for your suggestion.

The description of SelMix in Algorithm 1 is a bit confusing. Algorithm 1 says the classifier h is updated, but in Section 4.1 it says the parameter W is updated. I’m assuming the former is a consequence of the latter. If this is the case, wouldn’t it be better to replace h with W in Algorithm 1?

Thank you for your suggestion. Yes, you are correct that parameter $W$ is the one which is primarily updated by the algorithm. However, in practice, a small amount of fine-tuning of the feature extractor also helps our case. Hence, we have named our algorithm SelMix as a fine-tuning technique and used $h$ in the algorithm (which contains $W$ as the primary part). We have discussed this in Appendix K of the draft.

Obfuscating the actual operation with the function SGD-Update() also makes it difficult to see the exact algorithm

We appreciate your suggestion. Due to space constraints, we had to abstract out the function. We have provided the full-length SelMix Algorithm in App. Alg. 2, which we will add to final version with increased page limit.