Multiplicative Logit Adjustment Approximates Neural-Collapse-Aware Decision Boundary Adjustment

## Abstract

Abstract Real-world data distributions are often highly skewed. This has spurred a growing body of research on long-tailed recognition, aimed at addressing the imbalance in training classification models. Among the methods studied, multiplicative logit adjustment (MLA) stands out as a simple and effective method. What theoretical foundation explains the effectiveness of this heuristic method?
We provide a justification for the effectiveness of MLA with the following two-step process. First, we develop a theory that adjusts optimal decision boundaries by estimating feature spread on the basis of neural collapse. Second, we demonstrate that MLA approximates this optimal method. Additionally, through experiments on long-tailed datasets, we illustrate the practical usefulness of MLA under more realistic conditions. We also offer experimental insights to guide the tuning of MLA hyperparameters.

## 1 Introduction

Publicly available benchmark datasets commonly used to evaluate classification models, such as MNIST (Lecun et al., ) and CIFAR100 (Krizhevsky, ), usually have a balanced number of samples per class. In contrast to benchmark datasets, empirical evidence indicates that real-world data often follow an exponential distribution (Reed, ). This also holds for classification problems involving real-world data (Spain and Perona, ; Li et al., , ). Such distributions are commonly referred to as long-tailed data. In long-tailed data, a few classes (head classes) have a large number of samples, while most classes (tail classes) have only a limited number of samples. This imbalance poses a significant challenge in classification tasks, known as long-tailed recognition (LTR). LTR focuses on improving the accuracy of models trained on long-tailed data when evaluated on uniformly distributed data. In LTR, model predictions are often biased toward head classes. Since tail classes make up the majority, this bias significantly reduces the overall average accuracy across all classes (Zhang et al., ). To address this issue, LTR has been actively researched.

Various methods have been proposed for LTR. State-of-the-art methods (Ma et al., ; Long et al., ; Tian et al., ) are generally complex but often consist of combinations of simpler techniques, such as resampling (Drummond and Holte, ) and two-stage training (Kang et al., ). One straightforward method is logit adjustment (LA) (Menon et al., ; Kim and Kim, ). Among these techniques, post-hoc LA is a technique that adjusts the linear classifier on top of the feature map without additional training after the standard training process, offering both effectiveness and simplicity.
A prominent example of post-hoc LA is additive LA (ALA) (Menon et al., ), which is based on Fisher-consistent loss.
Another type of post-hoc LA is multiplicative LA (MLA) (Kim and Kim, ), which aims to adjust the decision boundaries on the basis of the differences in the feature spread across classes. Since MLA has also demonstrated significant empirical success, it raises the following question.

> Is there a theoretical foundation behind the effectiveness of MLA?

##### Contribution

We provide a theoretical guarantee that MLA achieves near-optimal decision boundary adjustments. Our contributions are summarized as follows.

- •
We derive a theoretical framework for adjusting decision boundaries optimally by leveraging feature spread estimates from neural collapse (NC) (Papyan et al., ) (Section 4.2).
- •
We demonstrate that MLA approximates the method based on the aforementioned theory (Section 4.3), clarifying under what conditions this approximation holds and how adjustments should be made.
- •
We experimentally validate that the approximation of MLA holds under realistic, non-ideal conditions where NC is not fully realized (Section 5).
- •
We provide empirical guidelines for hyperparameter-tuning of MLA (Section 5.4).

## 2 Related Work

##### Long-Tailed Recognition

LTR methods fall into three types: “Information Augmentation”, “Module Improvement”, and “Class Re-balancing” (Zhang et al., ). “Information Augmentation” aims to mitigate accuracy degradation by supplementing the limited information available for tail classes (Liu et al., ; Chu et al., ; Wang et al., ; Li et al., ; Wang et al., ). “Module Improvement” focuses on enhancing individual components of the network to boost overall performance. For example, Kang et al. () developed a two-stage training method that separates the training of feature maps and classifiers. Yang et al. () and Liu et al. () proposed methods to promote NC in feature maps. Recent approaches also use contrastive learning (Hadsell et al., ) (Ma et al., ; Tian et al., ; Li et al., ; Wang et al., ; Kang et al., ) and vision-language models such as CLIP (Radford et al., ) (Ma et al., ; Tian et al., ; Long et al., ). Despite these advancements, managing these methods can be challenging due to slow convergence (Liu et al., ) or complex models (Hasegawa and Sato, ). “Class Re-balancing” strategies adjust class imbalance to prevent accuracy degradation. Techniques in this category include resampling (Drummond and Holte, ; Li et al., ) and loss reweighting (Cui et al., ; Ma et al., ). However, reweighting is known to be ineffective for training overparameterized models (Byrd and Lipton, ; Zhai et al., ). LA is a simple yet effective method that falls under this category.

##### Logit Adjustment

LA modifies logit values by using the number of samples in each class, to bridge the distribution gap between the training and test data. LA methods fall into two categories: loss-function adjustments (Cao et al., ; Menon et al., ; Tang et al., ; Kini et al., ; Wang et al., ) and post-hoc LA methods that do not require additional training (Menon et al., ; Kim and Kim, ). The latter is particularly advantageous as it eliminates the need for retraining during hyperparameter tuning, thereby reducing both effort and time. Consequently, this paper delves deeper into post-hoc LA. Among post-hoc methods, there are two types depending on how the logits are adjusted: ALA (Menon et al., ) and MLA (Kim and Kim, ). ALA is grounded in a Fisher-consistent loss (Menon et al., ), providing some theoretical justification for its method. However, ALA assumes an infinite number of training samples, raising questions about its effectiveness with finite sample sizes. In contrast, MLA intuitively adjusts decision boundaries by using the size of each class cluster (Kim and Kim, ). MLA has empirically outperformed ALA in certain cases (Hasegawa and Sato, ).

##### Neural Collapse

NC is a term introduced by Papyan et al. () to describe four phenomena observed in the terminal phase of training classification models. These phenomena are as follows. Training feature vectors within each class converge to their respective class means (NC1); the class means of training feature vectors converge to form a simplex Equiangular Tight Frame (ETF) (Strohmer and Heath, ) (NC2); the class means of the training feature vectors align with the corresponding weight vectors of the linear classifier (NC3); and in prediction, the model outputs the class whose mean training feature vector is closest to the input feature vector in Euclidean distance (NC4).

NC is known to improve generalization accuracy and robustness (Papyan et al., ). Additionally, Galanti et al. () theoretically demonstrated that NC can occur even with test samples or samples from unseen classes. Various studies have explored the conditions under which NC arises (Rangamani and Banburski-Fahey, ; Han et al., ), and it is known that models trained using cross-entropy loss can also exhibit NC (Lu and Steinerberger, ; Ji et al., ). However, it has been observed that training with imbalanced data may hinder NC (Fang et al., ; Thrampoulidis et al., ; Dang et al., ). To address this problem, some methods have been proposed to promote NC even with imbalanced data (Yang et al., ; Liu et al., ). Yang et al. () introduced the ETF classifier, which fixes the linear classifier weights to form an ETF, thereby encouraging NC.

## 3 Preliminaries

We outline the notations used throughout this paper. For a comprehensive list, refer to the table in Appendix A. For any integer $i$, $[i]$ represents the set $\{1,\ldots,i\}$.
We use $\mathcal{X}\subset\mathbb{R}^{p}$ to denote the instance space and $\mathcal{Y}\equiv[K]$ to denote the label space. In a $K$-class classification problem, each sample $({\bm{x}},y)\in\mathcal{X}\times\mathcal{Y}$ is drawn from a distribution $P$. The training dataset, $\mathcal{S}\equiv\{({\bm{x}}_{i},y_{i})\mid{\bm{x}}_{i}\in\mathcal{X},y_{i}\in
\mathcal{Y}\}_{i=1}^{N}$, consists of independent and identically distributed (i.i.d.) samples drawn from $P$. Partitioning by class, we define $\mathcal{S}_{k}\equiv\{{\bm{x}}_{i}\mid({\bm{x}}_{i},y_{i})\in\mathcal{S},y_{i
}=k\}$ as the set of samples drawn from the class-conditional distribution $P_{k}$. Let $N\equiv|\mathcal{S}|$ be the total number of samples, and $n_{k}=|\mathcal{S}_{k}|$ be the number of samples in class $k$. Without loss of generality, we assume the classes are sorted in descending order of sample size, i.e., $n_{k}\geq n_{k+1}$ for all $k\in[K-1]$. The imbalance factor is defined by $\rho\equiv\frac{n_{1}}{n_{K}}=\frac{\max_{k}n_{k}}{\min_{k}n_{k}}$, which measures the degree of imbalance in the training dataset, where $\rho\gg 1$ holds in LTR scenarios. In contrast to the imbalanced training dataset, the test dataset used for evaluation has a uniform label distribution. Specifically, we denote $\tilde{\mathcal{S}}_{k}\sim P_{k}^{\tilde{n}_{k}}$ by the test dataset for class $k$, with $\tilde{n}_{k}$ samples. Then, it holds that $\tilde{n}_{k}=\tilde{n}_{k^{\prime}}$ for all $k,k^{\prime}\in\mathcal{Y}$.

Let ${\bm{f}}:\mathbb{R}^{p}\to\mathbb{R}^{d}$ be a feature map from the set $\mathcal{F}\subset\{{\bm{f}}^{\prime}:\mathbb{R}^{p}\to\mathbb{R}^{d}\}$. We focus on the input to the final layer of this feature map. Suppose the features are given by ${\bm{f}}({\bm{x}})={\bm{W}}^{1}{\bm{h}}({\bm{x}})$, where ${\bm{W}}^{1}\in\mathbb{R}^{d\times d_{1}}$ is a linear layer, and ${\bm{h}}\in\mathcal{H}:\mathbb{R}^{p}\to\mathbb{R}^{d_{1}}$ represents the output of the second-to-last layer of the feature map. For simplicity, we assume that ${\bm{h}}$ is bounded, meaning there exists a constant $B\geq 1$ such that $\sup_{{\bm{x}}\in\mathcal{X},{\bm{h}}\in\mathcal{H}}\|{\bm{h}}({\bm{x}})\|\leq
B$, where $\|\cdot\|$ denotes the Euclidean norm for vectors.

Let the expected value and mean of the features be denoted as ${\bm{\mu}}_{{\bm{f}}}(P_{k})\equiv\mathbb{E}_{{\bm{x}}\sim P_{k}}[{\bm{f}}({
\bm{x}})]$ and ${\bm{\mu}}_{{\bm{f}}}(\mathcal{S}_{k})\equiv\frac{1}{n_{k}}\sum_{{\bm{x}}\in
\mathcal{S}_{k}}{\bm{f}}({\bm{x}})$, respectively. When ${\bm{f}}$ is clear from the context, we abbreviate these to ${\bm{\mu}}(P_{k})$ and ${\bm{\mu}}(\mathcal{S}_{k})$.

These features are fed into a linear classifier ${\bm{W}}\in\mathbb{R}^{d\times K}$ and we obtain the logits ${\bm{g}}({\bm{x}})\equiv{\bm{W}}^{\top}{\bm{f}}({\bm{x}})$, where $\cdot^{\top}$ denotes the transpose of a matrix. The linear classifier weights can be expressed using column vectors ${\bm{w}}_{k}\in\mathbb{R}^{d}$, where ${\bm{W}}=[{\bm{w}}_{1},\ldots,{\bm{w}}_{K}]$. Thus, the logit for class $k$ can be written as $g_{k}({\bm{x}})\equiv{\bm{w}}_{k}^{\top}{\bm{f}}({\bm{x}})$. We assume that the weights of the linear classifier form an ETF. This assumption holds under NC and when we use an ETF classifier (Yang et al., ). This leads to the following equation:

$$ $\displaystyle{\bm{w}}_{k}^{\top}{\bm{w}}_{k^{\prime}}=\begin{cases}1&\text{if $k=k^{\prime}$,}\\ -\frac{1}{K-1}&\text{otherwise.}\end{cases}$ (1) $$

##### Logit Adjustment

MLA is a method that adjusts logits by scaling the norm of the linear classifier weights for each class (Kim and Kim, ). This is equivalent(^1^11Kim and Kim () adjusted logits to ${\allowbreak\left(\frac{n_{1}}{n_{k}}\right)^{\gamma_{\times}}}g_{k}({\bm{x}})$, while Menon et al. () adjusted them to $g_{k}({\bm{x}})-\gamma_{+}\log\frac{n_{k}}{\sum_{k^{\prime}}n_{k^{\prime}}}$. Note that both methods differ from the adjustment used in this paper only by a constant multiple or constant term. However, since this does not affect the ranking of logits across classes or the classification outcomes, we adopt the adjustments described in the main text of this paper.) in classification outcome to adjusting the logit for class $k$, $g_{k}({\bm{x}})$, by scaling it as ${n_{k}^{-\gamma_{\times}}}g_{k}({\bm{x}})$. Here, $\gamma_{\times}>0$ is a hyperparameter. Kim and Kim () used projected gradient descent to normalize the norm of the linear layer, $\|{\bm{w}}_{k}\|$, to 1. This normalization step is unnecessary in our setting because we use an ETF classifier and the weights remain fixed.
In contrast, ALA adjusts logits additively. This is equivalent1 to modifying the logit for class $k$, $g_{k}({\bm{x}})$, by subtracting $\gamma_{+}\log n_{k}$, where $\gamma_{+}>0$ is a hyperparameter.

## 4 Main analysis

MLA is a post-hoc adjustment method that increases the probability of classifying samples into tail classes by changing the angles of the decision boundaries (Kim and Kim, ). To derive the appropriate angles, it is necessary to estimate the sizes of the feature spread for each class. Galanti et al. () demonstrated that NC also occurs in test samples and provided a quantitative measure of feature spread. Following their approach, we verify the effectiveness of MLA theoretically through the lens of NC. In the following sections, we employ the ETF classifier (Yang et al., ) to encourage NC. This assumption can also be derived from the assumption that NC2 and NC3 hold. Using an ETF classifier also ensures that the weight vectors are normalized, as shown to be effective by Kim and Kim ().

First, in Section 4.1 we outline the assumptions and additional notations necessary to present our theory. Next, in Section 4.2, we demonstrate how to optimally adjust the decision boundaries from the perspective of NC. In Section 4.3, we indicate that MLA approximates this adjustment. Finally, Section 4.4 compares ALA and MLA in view of our theory.

### 4.1 Preliminaries: SVD and Rademacher Complexity

We consider the singular value decomposition of ${\bm{W}}^{1}$. When ${\bm{W}}^{1}$ has rank $r$, we can express it as ${\bm{W}}^{1}=\sum_{l=1}^{r}s_{l}\hat{\mathbf{}}l{\bm{v}}_{l}^{\top}$, where for each $l\in[r]$, $\hat{\mathbf{}}l\in\mathbb{R}^{d}$, ${\bm{v}}_{l}\in\mathbb{R}^{d_{1}}$, and $s_{l}\in\mathbb{R}_{>0}$. Moreover, for all $l\in[r]$, we have $\|{\bm{v}}_{l}\|=\|\hat{\mathbf{}}l\|=1$, and for $l\neq l^{\prime}\in[r]$, ${\bm{v}}_{l}^{\top}{\bm{v}}_{l^{\prime}}=\hat{\mathbf{}}l^{\top}\hat{\mathbf{}
}{l^{\prime}}=0$. Without loss of generality, we assume that $\forall l\in[r-1]$, $s_{l}\geq s_{l+1}$. In many deep neural networks, weight matrices can be replaced with low-rank representations while maintaining performance (Frankle and Carbin, ; Idelbayev and Carreira-Perpiñán, ; Kajitsuka and Sato, ). Thus, it is reasonable to consider $r\ll\min(d,d_{1})$ in practical situations.

We define the set $\mathcal{H}_{l}$ as:

$$ $\displaystyle\mathcal{H}_{l}\equiv\{({\bm{v}}_{l},{\bm{h}})\ |\ {\bm{f}}\in \mathcal{F},{\bm{f}}={\bm{W}}^{1}{\bm{h}},\ {\bm{v}}_{l}\text{ is the }l\text{ -th right singular vector of }{\bm{W}}^{1}\}.$ (2) $$

By using slightly rough notation, the Rademacher complexity and empirical Rademacher complexity of $\mathcal{H}_{l}$ are defined by:

$$ $\displaystyle\mathfrak{R}_{n_{k}}(\mathcal{H}_{l})$ $\displaystyle\equiv\mathbb{E}_{\mathcal{S}^{\prime}_{k}\sim P_{k}^{n_{k}},\bm{ \sigma}}\left[\sup_{({\bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\frac{1}{n_{k}} \sum_{{\bm{x}}_{j}\in\mathcal{S}^{\prime}_{k}}\sigma_{j}{\bm{v}}_{l}^{\top}{ \bm{h}}({\bm{x}}_{j})\right],$ (3) $\displaystyle\hat{\mathfrak{R}}_{\mathcal{S}_{k}}(\mathcal{H}_{l})$ $\displaystyle\equiv\mathbb{E}_{\bm{\sigma}}\left[\sup_{({\bm{v}}_{l},{\bm{h}}) \in\mathcal{H}_{l}}\frac{1}{n_{k}}\sum_{{\bm{x}}_{j}\in\mathcal{S}_{k}}\sigma_ {j}{\bm{v}}_{l}^{\top}{\bm{h}}({\bm{x}}_{j})\right],$ (4) $$

where $\bm{\sigma}=[\sigma_{1},\ldots,\sigma_{n_{k}}]^{\top}$ represents the i.i.d. Rademacher random variables. In many cases, the Rademacher complexity scales as $\mathfrak{R}_{n_{k}}(\mathcal{H}_{l})\leq\sqrt{\frac{\mathcal{C}(\mathcal{H}_{
l},\mathcal{X})}{n_{k}}}$, where $\mathcal{C}(\mathcal{H}_{l},\mathcal{X})$ is some complexity measure independent of $n_{k}$ (Cao et al., ; Galanti et al., ). For instance, this holds for rectified linear unit (ReLU) neural networks; see Appendix B.2 for further details. We make this assumption in our settings.

### 4.2 Optimal Decision Boundary Adjustment from the Perspective of NC

Figure: Figure 1: Overview of Propositions 1 and 2. The angular bound probability $\Pi(\theta;k)$ represents the lower bound of the probability that the feature vector of ${\bm{x}}$ sampled from $P_{k}$ lies within the shaded region. Proposition 1 indicates that $\Pi(\theta;k)=1-\tilde{\mathcal{O}}\left(1/\sqrt{n_{k}}\right)$. Proposition 2 offers the optimal decision boundary by maximizing $\Pi(\theta_{k,k^{\prime}};k)+\Pi(\theta_{k^{\prime},k};k^{\prime})$ with respect to $\theta_{k,k^{\prime}}$ and $\theta_{k^{\prime},k}$.
Refer to caption: extracted/5897552/images/props.png

We indicate that the following result holds for general neural networks. For the proofs of the propositions presented in this section and for the case of ReLU neural networks, see Appendix B.

In NC, the training features converge to their respective class means (Papyan et al., ). It has also been demonstrated that test features are within a certain range from the class mean of training features, with this range depending on the sample size (Galanti et al., ). Following a similar approach, we can quantitatively measure the angular deviation between test features and the corresponding training class mean, as a function of the sample size.

To achieve this, we first define the angular bound probability $\Pi(\theta;k)$ as follows.

###### Definition 1 (Angular bound probability) .

The angular bound probability $\Pi(\theta;k)$ for class $k$ is the lower bound of the probability that the angle between ${\bm{f}}({\bm{x}})$ and ${\bm{\mu}}(\mathcal{S}_{k})$, for ${\bm{x}}\sim P_{k}$, is less than $\theta$. That is, we have that $\Pi(\theta;k)\leq\Pr_{{\bm{x}}\sim P_{k}}\allowbreak[\angle({\bm{f}}({\bm{x}})
,{\bm{\mu}}(\mathcal{S}_{k}))<\theta]$, where $\angle(\cdot,\cdot)$ is the angle between the two vectors.

The following proposition provides a quantitative measure of $\Pi(\theta;k)$:

###### Proposition 1 .

Suppose $n_{k}>2$. For ${\bm{f}}\in\mathcal{F}$, assume that for all ${\bm{x}}\in\mathcal{S}_{k}$, ${\bm{f}}({\bm{x}})={\bm{\mu}}(\mathcal{S}_{k})$ holds. Consider any $\theta$ that satisfies the following condition:

$$ $\displaystyle\frac{\pi}{2}\frac{r\|{\bm{W}}^{1}\|_{2}}{\sqrt{n_{k}}\|{\bm{\mu} }(\mathcal{S}_{k})\|}\allowbreak(4\sqrt{\mathcal{C}(\mathcal{H}_{l},\mathcal{X })}+4B+B\sqrt{2\log\frac{\sqrt{n_{k}}\|{\bm{\mu}}(\mathcal{S}_{k})\|}{\|{\bm{W }}^{1}\|_{2}}})<\theta<\frac{\pi}{2},$ (5) $$

where $\|\cdot\|_{2}$ denotes the spectral norm.
For such $\theta$, the following holds:

$$ $\displaystyle\Pi(\theta;k)=1-\frac{\pi}{2\theta}\frac{r\|{\bm{W}}^{1}\|_{2}}{ \sqrt{n_{k}}\|{\bm{\mu}}(\mathcal{S}_{k})\|}\left(4\sqrt{\mathcal{C}(\mathcal{ H}_{l},\mathcal{X})}+4B+1+B\sqrt{2\log\frac{2\theta\sqrt{n_{k}}\|{\bm{\mu}}( \mathcal{S}_{k})\|}{\pi\|{\bm{W}}^{1}\|_{2}}}\right).$ (6) $$

The overview of this proposition is illustrated in the left side of Figure 1.
When NC occurs, note that ${\bm{f}}({\bm{x}})={\bm{\mu}}(\mathcal{S}_{k})$ holds for all ${\bm{x}}\in\mathcal{S}_{k}$ by NC1 and ${\bm{w}}_{k}=\frac{{\bm{\mu}}(\mathcal{S}_{k})}{\|{\bm{\mu}}(\mathcal{S}_{k})\|}$ holds by NC3. Additionally, observe that the left-hand side of Eq. (5) and $1-\Pi(\theta;k)$ are $\tilde{\mathcal{O}}\allowbreak(\frac{1}{\sqrt{n_{k}}})$, where $\tilde{\mathcal{O}}$ denotes asymptotic notation ignoring logarithmic terms. From this proposition, we can quantitatively infer that as the sample size of a class increases, the features become more concentrated within a narrower region, with higher probability. This allows us to consider the optimal angle for the decision boundary.

Consider the optimal angle for the decision boundary between two classes, $k$ and $k^{\prime}$. Since we use an ETF classifier, the linear classifier weights forms an ETF structure, meaning the angle between ${\bm{w}}_{k}$ and ${\bm{w}}_{k^{\prime}}$ is $\psi\equiv\arccos\left(-\frac{1}{K-1}\right)$. Now, consider a decision boundary that forms an angle $\theta_{k,k^{\prime}}$ with ${\bm{w}}_{k}$. The angle between this boundary and ${\bm{w}}_{k^{\prime}}$ is $\theta_{k^{\prime},k}\equiv\psi-\theta_{k,k^{\prime}}$. Here, $0<\theta_{k,k^{\prime}},\theta_{k^{\prime},k}<\psi$.

In this setup, the probability that a sample ${\bm{x}}\sim P_{k}$ lies on the ${\bm{w}}_{k}$ side of the boundary is at least $\Pi(\theta_{k,k^{\prime}};k)$. Similarly, the probability that a sample ${\bm{x}}\sim P_{k^{\prime}}$ lies on the ${\bm{w}}_{k^{\prime}}$ side is at least $\Pi(\theta_{k^{\prime},k};k^{\prime})$. Therefore, the accuracy of classification between the two classes is at least $\frac{1}{2}\left(\Pi(\theta_{k,k^{\prime}};k)+\Pi(\theta_{k^{\prime},k};k^{
\prime})\right)$, which depends on the angle $\theta_{k,k^{\prime}}$ of the decision boundary. Thus, we seek the value of $\theta_{k,k^{\prime}}$ that maximizes this lower bound. The following proposition provides the solution to this problem.

###### Proposition 2 .

Suppose $n_{k},n_{k^{\prime}}>2$. For ${\bm{f}}\in\mathcal{F}$, assume that for both $\hat{k}\in\{k,k^{\prime}\}$, ${\bm{f}}({\bm{x}})={\bm{\mu}}(\mathcal{S}_{\hat{k}})$ holds for all ${\bm{x}}\in\mathcal{S}_{\hat{k}}$. Consider the following maximization problem:

$$ $\displaystyle\max_{\theta_{k,k^{\prime}},\theta_{k^{\prime},k}}{\Pi}(\theta_{k ,k^{\prime}};k)+{\Pi}(\theta_{k^{\prime},k};k^{\prime})\qquad\text{s.t. } \theta_{k,k^{\prime}},\theta_{k^{\prime},k}>0,\quad\theta_{k,k^{\prime}}+ \theta_{k^{\prime},k}=\psi.$ (7) $$

The unique solution $\theta_{k,k^{\prime}}^{*},\theta_{k^{\prime},k}^{*}$ within the range where $\theta_{k,k^{\prime}}$ and $\theta_{k^{\prime},k}$ satisfy Eq. (5) is given by:

$$ $\displaystyle\theta_{k,k^{\prime}}^{*}=\psi\frac{\|{\bm{\mu}}(\mathcal{S}_{k^{ \prime}})\|\sqrt{n_{k^{\prime}}}}{\|{\bm{\mu}}(\mathcal{S}_{k})\|\sqrt{n_{k}}+ \|{\bm{\mu}}(\mathcal{S}_{k^{\prime}})\|\sqrt{n_{k^{\prime}}}},\quad\theta_{k^ {\prime},k}^{*}=\psi\frac{\|{\bm{\mu}}(\mathcal{S}_{k})\|\sqrt{n_{k}}}{\|{\bm{ \mu}}(\mathcal{S}_{k})\|\sqrt{n_{k}}+\|{\bm{\mu}}(\mathcal{S}_{k^{\prime}})\| \sqrt{n_{k^{\prime}}}}.$ (8) $$

The overview of this proposition is illustrated in the right side of Figure 1.
When $n_{k}$ and $n_{k^{\prime}}$ are sufficiently large, Eq. (5) holds over a wide range of $0<\theta<\frac{\pi}{2}$. Moreover, as $K\to\infty$, $\psi=\arccos\left(-\frac{1}{K-1}\right)\to\frac{\pi}{2}$ and $\theta_{k,k^{\prime}}^{*},\theta_{k^{\prime},k}^{*}<\frac{\pi}{2}$ holds, making Eq. (8) meet the condition of Eq. (5) when $K$ is sufficiently large. In practice, for datasets with $100$ classes such as CIFAR100-LT, $\psi-\frac{\pi}{2}\sim 0.01$, meaning that $\theta_{k,k^{\prime}}^{*},\theta_{k^{\prime},k}^{*}<\frac{\pi}{2}$ is sufficiently valid.

This result can easily be extended to multi-class cases (refer to Proposition 3). In multi-class cases, it becomes an optimization problem of the angles $\theta_{k,k^{\prime}}$ for every pair of classes $k,k^{\prime}\neq k$ in $\mathcal{Y}$, defined as $\Theta\equiv\{\theta_{k,k^{\prime}}\mid k\neq k^{\prime}\in\mathcal{Y}\}$.

###### Proposition 3 .

Suppose $n_{k}>2$ for all $k\in\mathcal{Y}$. For ${\bm{f}}\in\mathcal{F}$, assume that for all $k\in\mathcal{Y}$, ${\bm{f}}({\bm{x}})={\bm{\mu}}(\mathcal{S}_{{k}})$ holds for all ${\bm{x}}\in\mathcal{S}_{{k}}$. Consider the following maximization problem:

$$ $\displaystyle\max_{\Theta}\sum_{k\in\mathcal{Y}}\sum_{k^{\prime}\neq k}\Pi( \theta_{k,k^{\prime}};k)+\Pi(\theta_{k^{\prime},k};k^{\prime})\quad\text{s.t. }\forall k,k^{\prime}\in\mathcal{Y},\theta_{k,k^{\prime}},\theta_{k^{\prime},k }>0\ \ \text{and}\ \ \theta_{k,k^{\prime}}+\theta_{k^{\prime},k}=\psi.$ (9) $$

The unique solution $\theta_{k,k^{\prime}}^{*}\in\Theta^{*}$ within the range where all $\theta_{k,k^{\prime}}^{*}\in\Theta^{*}$ satisfies Eq. (5) is given by:

$$ $\displaystyle\theta_{k,k^{\prime}}^{*}=\psi\frac{\|{\bm{\mu}}(\mathcal{S}_{k^{ \prime}})\|\sqrt{n_{k^{\prime}}}}{\|{\bm{\mu}}(\mathcal{S}_{k})\|\sqrt{n_{k}}+ \|{\bm{\mu}}(\mathcal{S}_{k^{\prime}})\|\sqrt{n_{k^{\prime}}}}.$ (10) $$

These theories suggest replacing the linear layer with a 1-vs-1 multi-class classifier with decision boundaries of $\Theta^{*}$. To generalize, we introduce a hyperparameter $\gamma_{\mathrm{1v1}}$, and define $\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}})=\psi\frac{\|{\bm{\mu}}(
\mathcal{S}_{k^{\prime}})\|{n_{k^{\prime}}}^{\gamma_{\mathrm{1v1}}}}{\|{\bm{
\mu}}(\mathcal{S}_{k})\|{n_{k}}^{\gamma_{\mathrm{1v1}}}+\|{\bm{\mu}}(\mathcal{
S}_{k^{\prime}})\|{n_{k^{\prime}}}^{\gamma_{\mathrm{1v1}}}}$, with $\Theta^{*}_{\gamma_{\mathrm{1v1}}}\equiv\{\theta_{k,k^{\prime}}^{*}(\gamma_{
\mathrm{1v1}})\mid k\neq k^{\prime}\in\mathcal{Y}\}$. Note that $\Theta^{*}_{\gamma_{\mathrm{1v1}}}=\Theta^{*}$ holds when $\gamma_{\mathrm{1v1}}=\frac{1}{2}$. We refer to the 1-vs-1 multi-class classifier that classifies based on this $\Theta^{*}_{\gamma_{\mathrm{1v1}}}$ as 1vs1adjuster.
See Appendix C for the specific algorithm of 1vs1adjuster.

###### Definition 1 (Angular bound probability) .

###### Proposition 1 .

###### Proposition 2 .

###### Proposition 3 .

### 4.3 MLA Approximates 1vs1adjuster

We consider how 1vs1adjuster can be approximated and replaced with an MLA-adjusted linear classifier.
MLA can be viewed as a technique that multiplicatively adjusts the cosine similarity between features and the linear layer weight vectors to increase the probability of classifying samples into tail classes. Although our theory in Section 4.2 aims to find the optimal decision boundaries between classes, it can be connected to MLA by considering the magnitude of logits under simple assumptions.

For the following discussion, we assume that $K$ is sufficiently large. Under this condition, it holds that $\psi=\arccos\left(-\frac{1}{K-1}\right)\to\frac{\pi}{2}$, allowing us to assume that $\cos(\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}})),\cos(\theta_{k^{\prime}
,k}^{*}(\gamma_{\mathrm{1v1}}))>0$.

Let the MLA factor, multiplicatively applied to the logits of class $k$, be denoted by $\kappa_{k}$. In other words, we consider the case in which the logit $g_{k}({\bm{x}})$ for class $k$ is adjusted to $\kappa_{k}g_{k}({\bm{x}})$. We present that when adjusting the decision boundaries on the basis of 1vs1adjuster, $\kappa_{k}\propto n_{k}^{-\gamma_{\mathrm{1v1}}}$ holds. Note that the ETF classifier ensures equal norms of the linear layer weight vectors across all classes. To adjust the decision boundaries to be equivalent to 1vs1adjuster by using MLA, we should adjust $\kappa_{k}$ such that the following holds for all $k\neq k^{\prime}\in\mathcal{Y}$:

$$ $\displaystyle\kappa_{k}\cos(\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}}))= \kappa_{k^{\prime}}\cos(\theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1}})).$ (11) $$

A problem arises here because there are only $K$ MLA factors, while they must satisfy $K(K-1)/2$ equations. Consequently, when $K>2$, there is typically no solution. However, by considering the following approximation, it is possible to obtain an approximate solution. First, note that as $K\to\infty$, it holds that $\psi\to\frac{\pi}{2}$. Letting $\epsilon=\frac{\pi}{2}-\psi$, and considering the continuity of $\cos$, we can approximate and solve Eq. (11) as follows:

$$ $\displaystyle\frac{\kappa_{k}}{\kappa_{k^{\prime}}}$ $\displaystyle=\tan(\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}}))\cos( \epsilon)-\sin(\epsilon)$ (12) $\displaystyle\sim\tan(\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}})).$ (13) $$

Now, let $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})\equiv\frac{\|{\bm{\mu}}(\mathcal{S}
_{k})\|n_{k}^{\gamma_{\mathrm{1v1}}}}{\|{\bm{\mu}}(\mathcal{S}_{k^{\prime}})\|
n_{k^{\prime}}^{\gamma_{\mathrm{1v1}}}}$, then we have:

$$ $\displaystyle\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}})=\psi\frac{\|{\bm {\mu}}(\mathcal{S}_{k^{\prime}})\|{n_{k^{\prime}}}^{\gamma_{\mathrm{1v1}}}}{\| {\bm{\mu}}(\mathcal{S}_{k})\|{n_{k}}^{\gamma_{\mathrm{1v1}}}+\|{\bm{\mu}}( \mathcal{S}_{k^{\prime}})\|{n_{k^{\prime}}}^{\gamma_{\mathrm{1v1}}}}=\psi\frac {1}{\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})+1}\sim\frac{\pi}{2}\frac{1}{ \tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})+1}.$ (14) $$

Next, for $0\leq\theta<1$, we approximate $\tan\left(\frac{\pi}{2}\theta\right)$ using the rational function $\phi(\theta)=\frac{\theta}{1-\theta}$. This approximation satisfies the following properties:

###### Lemma 1 .

$$ $\displaystyle\phi(0)$ $\displaystyle=\tan(0)=0,$ (15) $\displaystyle\phi\allowbreak(\frac{1}{2})$ $\displaystyle=\tan\allowbreak(\frac{\pi}{4})=1,$ (16) $\displaystyle\lim_{\theta\to 1-0}\phi(\theta)$ $\displaystyle=\lim_{\theta\to 1-0}\tan\allowbreak(\frac{\pi}{2}\theta)=+\infty.$ (17) $$

###### Lemma 2 .

Let $\theta\in[0,1)$. Then, the following holds:

$$ $\displaystyle\phi(\theta)\leq$ $\displaystyle\tan\allowbreak(\frac{\pi}{2}\theta)<\frac{\pi}{2}\phi(\theta)$ $\displaystyle\qquad\allowbreak(0\leq\theta\leq\frac{1}{2}),$ (18) $\displaystyle\frac{2}{\pi}\phi(\theta)<$ $\displaystyle\tan\allowbreak(\frac{\pi}{2}\theta)<\phi(\theta)$ $\displaystyle\qquad\allowbreak(\frac{1}{2}<\theta<1).$ (19) $$

The proof of Lemma 1 is trivial and thus omitted. The proof of Lemma 2 can be found in Appendix B.3. These lemmas suggest that the approximation $\phi(\theta)=\frac{\theta}{1-\theta}$ for $\tan\left(\frac{\pi}{2}\theta\right)$ is particularly close when $\theta=\frac{1}{2}$ or $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})=1$, but it provides a global approximation. This is especially suitable for LTR settings, where $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})$ tends to deviate significantly from $1$.

Using these results, we further approximate Eq. (13) as:

$$ $\displaystyle\frac{\kappa_{k}}{\kappa_{k^{\prime}}}\sim\tan(\theta_{k,k^{ \prime}}^{*}(\gamma_{\mathrm{1v1}}))\sim\frac{\frac{2}{\pi}\theta_{k,k^{\prime }}^{*}(\gamma_{\mathrm{1v1}})}{1-\frac{2}{\pi}\theta_{k,k^{\prime}}^{*}(\gamma _{\mathrm{1v1}})}\sim\frac{1}{\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})}.$ (20) $$

Therefore, if we set $\kappa_{k}=\frac{\alpha}{\|{\bm{\mu}}(\mathcal{S}_{k})\|n_{k}^{\gamma_{\mathrm
{1v1}}}}$ for any $\alpha\in\mathbb{R}_{>0}$, we can approximately satisfy Proposition 3. This corresponds to performing MLA with $\gamma_{\times}=\gamma_{\mathrm{1v1}}$, under the assumption of feature normalization.

###### Lemma 1 .

###### Lemma 2 .

### 4.4 Discussion: Comparison of MLA with ALA

In Section 4.3, we demonstrate that MLA is grounded in the theoretical framework of decision boundary adjustment developed in Section 4.2.
We now turn our attention to ALA, presenting the issues that arise when applying the theory from Section 4.2 to ALA. This highlights the differences between MLA and ALA, and indicates the relative advantages of MLA.

ALA is inconsistent with the concept of optimal decision boundary adjustment as described in Proposition 3. This is because the decision boundaries adjusted by ALA changes depending on the norm of each feature, $\|{\bm{f}}({\bm{x}})\|$. For instance, let’s consider an instance ${\bm{x}}$ whose logit of class $k$ is represented as $g_{k}({\bm{x}})=\|{\bm{f}}({\bm{x}})\|\cos(\angle({\bm{f}}({\bm{x}}),{\bm{w}}_
{k}))$. The output of the classification label for ${\bm{x}}$ depends on the magnitude of $\|{\bm{f}}({\bm{x}})\|\cos(\angle({\bm{f}}({\bm{x}}),{\bm{w}}_{k}))-\gamma_{+}
\log n_{k}$ for each $k$. In other words, the classification result depends on both the angle $\angle({\bm{f}}({\bm{x}}),{\bm{w}}_{k})$ and the norm $\|{\bm{f}}({\bm{x}})\|$. This implies that the optimal decision boundaries during inference is effected by the norm of individual features. This dependency conflicts with Proposition 3, in which the optimal decision boundaries are independent of the norm of each feature.

On the other hand, suppose we assume that $\|{\bm{f}}({\bm{x}})\|$ is equal for all ${\bm{x}}\in\mathcal{X}$, ensuring that the angles of the decision boundaries remain constant for each sample. Following the same reasoning as in Section 4.3, we can also approximate 1vs1adjuster by ALA. However, compared to MLA, this approximation cannot hold globally when $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})$ varies significantly. This inconsistency with LTR settings, in which $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})$ can deviate considerably, makes ALA incompatible. See Appendix D for details.

These points are corroborated by the subsequent experimental results, which demonstrate the substantial differences between the properties of MLA and ALA.

## 5 Experiments

We experimentally demonstrate that MLA is an appropriate approximation of 1vs1adjuster from two perspectives. First, we outline the experimental setup in Section 5.1. Then, we demonstrate that MLA and 1vs1adjuster share similar decision boundaries in Section 5.2 and yield equivalent classification accuracy in Section 5.3. Finally, we present insights into MLA hyperparameters in Section 5.4, on the basis of experimental results.

### 5.1 Settings

Our experimental setup primarily follows Hasegawa and Sato (). We used CIFAR10, CIFAR100 (Krizhevsky, ), and ImageNet (Deng et al., ) as datasets. Following Cui et al. () and Liu et al. (), we created long-tailed versions of these datasets, namely CIFAR10-LT, CIFAR100-LT, and ImageNet-LT, with an imbalance ratio of $\rho=100$. To demonstrate that this method applies to general modal data, not just images, we also used the tabular dataset Helena (Guyon et al., ).

For the network architecture, we used ResNeXt50 (Xie et al., ) for ImageNet-LT and ResNet34 (He et al., ) for the other image datasets unless otherwise specified. For Helena, we used a multi-layer perceptron (MLP), following Kadra et al. (). We adopted the ETF classifier as the linear classifier to promote NC and fix the linear classifier weights. Thus, only the parameters of the feature map were trained. We used cross-entropy loss as the loss function and applied weight decay (Hanson and Pratt, ) and feature regularization as regularization techniques. Feature regularization was employed to promote NC (Hasegawa and Sato, ) and to prevent significant differences in the norms of the training features across classes, fulfilling the condition for MLA to approximate 1vs1adjuster. We tuned the hyperparameters $\gamma_{\mathrm{1v1}}$, $\gamma_{+}$, and $\gamma_{\times}$ using validation datasets. For further detailed experimental settings, refer to Appendix E.1.

We examined the behavior of MLA, ALA, and 1vs1adjuster when applied post-hoc to models trained on the training datasets. Specifically, we aimed to assess whether MLA provides an effective approximation of 1vs1adjuster in terms of decision boundary adjustment and classification accuracy. ALA, another post-hoc LA method, was included as a benchmark for comparison.

### 5.2 Decision Boundary Angles

We investigate how the decision boundary angles between classes are adjusted. Similar to the analysis in Sections 4.3 and 4.4, MLA and ALA can be interpreted as methods for adjusting the angles of the decision boundaries between classes. Let $\theta_{k,k^{\prime}}^{\times}$ and $\theta_{k,k^{\prime}}^{+}$ represent the angles of the decision boundaries between classes $k$ and $k^{\prime}$ derived from MLA and ALA, respectively.

For MLA, the following holds from Eq. (12):

$$ $\displaystyle\theta_{k,k^{\prime}}^{\times}=\arctan\allowbreak(\frac{ \allowbreak(\frac{{n_{k^{\prime}}}^{\gamma_{\times}}}{{n_{k}}^{\gamma_{\times} }}+\sin\allowbreak(\frac{\pi}{2}-\psi))}{\cos\allowbreak(\frac{\pi}{2}-\psi)}).$ (21) $$

For ALA, we assume that $\|{\bm{f}}({\bm{x}})\|$ is equal across all instances ${\bm{x}}$ and sufficiently large, denoted as $\|{\bm{f}}\|$. Then, from Eqs. (65) and (66), the following holds:

$$ $\displaystyle\theta_{k,k^{\prime}}^{+}=\frac{\psi}{2}-\arcsin\allowbreak(\frac {\gamma_{+}\log\frac{n_{k}}{n_{k^{\prime}}}}{2\|{\bm{f}}\|\sin\allowbreak( \frac{\psi}{2})}).$ (22) $$

We investigate the differences between these angles and $\theta_{k,k^{\prime}}^{*}$ used in 1vs1adjuster and demonstrate that MLA serves as a sufficient approximation of 1vs1adjuster. Figure 2 displays heatmaps comparing $\theta_{k,k^{\prime}}^{+}-\theta_{k,k^{\prime}}^{*}$ and $\theta_{k,k^{\prime}}^{\times}-\theta_{k,k^{\prime}}^{*}$ for CIFAR100-LT and CIFAR10-LT. Detailed experimental settings and results for other datasets are provided in Appendices E.1 and E.2, respectively. The heatmaps representing the difference between MLA and 1vs1adjuster are generally faint on datasets with a sufficient number of classes, such as CIFAR100-LT. This means that $\theta_{k,k^{\prime}}^{\times}-\theta_{k,k^{\prime}}^{*}$ is globally small across all $k,k^{\prime}\in\mathcal{Y}$. This is consistent with our theoretical predictions from Section 4.3, indicating that MLA is a sufficient approximation of 1vs1adjuster in large-class settings. The same phenomenon is observed for ImageNet-LT and Helena. Note that in these latter two datasets, this phenomenon occurs even though training accuracy is not sufficiently high and NC is not fully realized (see Table 1). This suggests that our theory holds under more relaxed conditions.

On CIFAR10-LT, which has fewer classes, the decision boundaries of both MLA and ALA differ significantly from those of 1vs1adjuster. This may be because the number of classes is so small that approximations such as $\psi\sim\frac{\pi}{2}$ are not valid. However, even in this case, MLA can still be regarded as an approximate method in that it achieves comparable test accuracy to 1vs1adjuster. See Section 5.3.

Figure: Figure 2: Heatmaps showing difference in angles of decision boundaries between each method and 1vs1adjuster. On the left is the result for CIFAR100-LT, and on the right is the result for CIFAR10-LT. The left side of each figure displays $\theta_{k,k^{\prime}}^{+}-\theta_{k,k^{\prime}}^{*}$, while the right side displays $\theta_{k,k^{\prime}}^{\times}-\theta_{k,k^{\prime}}^{*}$. Values that became NaN are shown in gray. In the case of CIFAR100-LT, the angle differences between MLA and 1vs1adjuster are generally small.
Refer to caption: extracted/5897552/images/theta_CIFAR100-LT.png

Figure: Figure 3: Average accuracy of each model trained on each dataset and adjusted by different methods. The error bars represent the mean and standard deviation across five trials with different seed values. 1v1 is short for 1vs1adjuster. MLA and 1vs1adjuster consistently achieve comparable accuracy.
Refer to caption: extracted/5897552/images/acc_set.png

### 5.3 Test Accuracy

We compare the test accuracy when each method is applied post-hoc to trained models.
Figure 3 displays the average test accuracy with error bars for each model trained on each dataset and adjusted by different methods.
The results on Helena and the detailed accuracy table can be found in Appendix E.3.
In all experiments, MLA can achieve high average accuracy comparable to 1vs1adjuster. Remarkably, this approximation holds even in cases where the assumptions mentioned in Section 4 do not hold, such as when the number of classes is small (CIFAR10-LT) or when training accuracy is low and NC has not sufficiently occurred (ImageNet-LT and Helena). In contrast, ALA achieves lower accuracy than 1vs1adjuster in some cases. ALA is based on Fisher consistency (Menon et al., ), assuming that the number of training samples is sufficiently large. While our theory also assumes a certain level of training sample size, it has been shown to work well even with more practical sample sizes. In addition, MLA and 1vs1adjuster achieve comparable accuracy to ALA even under unfavorable conditions, such as experiments on CIFAR10-LT and ImageNet-LT, where the assumptions of our theory do not strictly hold. These results demonstrate that MLA is a robust and practical method for improving test accuracy, even in real-world scenarios where ideal theoretical conditions are not met.

### 5.4 Hyperparameters

Table 1 summarizes the optimal values of MLA and 1vs1adjuster hyperparameters, $\gamma_{\times}^{*}$ and $\gamma_{\mathrm{1v1}}^{*}$, and the training accuracy for models trained on each training dataset.

On CIFAR10-LT, which has a small number of classes, the values of $\gamma_{\times}^{*}$ and $\gamma_{\mathrm{1v1}}^{*}$ are significantly different. This is probably because the approximation of 1vs1adjuster to MLA does not hold well when the number of classes is small.

From here on, we focus on cases in which the number of classes is sufficiently large. On CIFAR100-LT, where training accuracy has reached $100\%$, the optimal value is slightly higher than the theoretically derived value of 0.5. This suggests that when training reaches terminal phase and NC occurs, the feature spread can be bounded to a smaller order than $\tilde{\mathcal{O}}\allowbreak(\frac{1}{\sqrt{n_{k}}})$. For instance, recent research has aimed to bound generalization error to a smaller order than $\tilde{\mathcal{O}}\allowbreak(\frac{1}{\sqrt{n_{k}}})$ (Wei and Ma, ), and this may be related.

On Helena and ImageNet-LT, where training accuracy has not reached $100\%$, the optimal values can be smaller than 0.5. This is likely because the feature spread between classes does not differ as much compared to when NC sufficiently occurs. Even in such cases, MLA and 1vs1adjuster can achieve high test accuracy by adjusting hyperparameters (see Section 5.3 and Appendix E.3). These results are expected to be key insights when searching for the optimal hyperparameters for MLA.

**Table 1: Optimal hyperparameters and training accuracy for each model and dataset.**
| Dataset | Model | $\gamma_{\times}^{*}$ | $\gamma_{\mathrm{1v1}}^{*}$ | Training Accuracy (%) |
| --- | --- | --- | --- | --- |
| CIFAR100-LT | ResNet34 | $0.710\pm 0.037$ | $0.770\pm 0.060$ | 100.0 |
| CIFAR100-LT | ResNeXt50 | $0.770\pm 0.087$ | $1.010\pm 0.058$ | 100.0 |
| CIFAR10-LT | ResNet34 | $0.780\pm 0.518$ | $0.410\pm 0.120$ | 100.0 |
| ImageNet-LT | ResNeXt50 | $0.200\pm 0.000$ | $0.250\pm 0.000$ | 86.6 |
| Helena | MLP | $0.480\pm 0.093$ | $0.580\pm 0.060$ | 42.1 |

## 6 Conclusion

We provide a solid theoretical foundation for MLA, a simple heuristic method in LTR, and demonstrate its utility. First, on the basis of NC, we estimate the feature spread for each class and present a theory that derives the optimal method for adjusting the decision boundaries. Furthermore, we indicate that MLA is an approximation of this method and theoretically guarantees improvements in test accuracy. This provides clear insights into the conditions under which MLA is effective and how logits should be adjusted quantitatively. Additionally, through experiments, we demonstrate that the approximation holds under more relaxed conditions and that MLA exhibits practical usefulness by achieving accuracy comparable to or better than ALA.
This research forms a crucial foundation for future advancements in LTR and imbalanced learning methods.

One limitation of this study is the lack of a more in-depth theoretical analysis of ALA. While the current theory does not align with ALA, there may be approaches or assumptions that could guarantee its performance with a practical number of samples. Future research could explore this direction. Another potential avenue is the combination of MLA with other methods to develop more sophisticated methods and achieve state-of-the-art improvements in accuracy.

## Appendix A Acronym and Notation Table

Table 2 lists the acronyms referenced throughout this paper, and Tables 3, 4, and 5 provide a summary of the notations used in this paper.

**Table 2: Acronym table**
| Abbreviation | Definition |
| --- | --- |
| 1v1 | 1vs1adjuster |
| ALA | Additive logit adjustment [Menon et al., ] |
| ETF | Equiangular tight frame |
| i.i.d | Independent and identically distributed |
| LA | Logit adjustment |
| LTR | Long-tailed recognition |
| MLA | Multiplicative logit adjustment [Kim and Kim, ] |
| MLP | Multi-layer perceptron |
| NC | Neural collapse [Papyan et al., ] |
| ReLU | Rectified linear unit |

**Table 3: Notation table for operators and set**
| $\angle$ |  | The angle between the two vectors |
| --- | --- | --- |
| $\|\cdot\|$ |  | The Euclidean norm for vectors |
| $\|\cdot\|_{2}$, $\|\cdot\|_{F}$ |  | The spectral norm and Frobenius norm for matrices |
| $\tilde{\mathcal{O}}$ |  | The Landau notation, ignoring logarithmic terms |
| $\phi$ |  | The approximation function for $\tan$, i.e., $\phi(\theta)=\frac{\theta}{1-\theta}$ |
| $\operatorname{Avg}_{{\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}}h({\bm{x}},{<br>\bm{x}}^{\prime})$ |  | The average over pairs of different elements |
| $[i]$ |  | The set from $1$ to $i$, i.e., $\{1,\ldots,i\}$ |

**Table 4: Notation table for data**
| $\mathcal{X}$, $\mathcal{Y}$ |  | An instance space and a label space |
| --- | --- | --- |
| ${\bm{x}}$, $y$ |  | An instance and a label |
| $K$ |  | The number of classes, i.e., $|\mathcal{Y}|$ |
| $p$ |  | The instance dimension |
| $P$, $P_{k}$ |  | A sample distribution and a class-conditional distribution |
| $\mathcal{S}$, $\mathcal{S}_{k}$ |  | A training dataset and a class-specific training dataset |
| $\tilde{\mathcal{S}}_{k}$ |  | A class-specific test dataset |
| $N$, $n_{k}$ |  | The size of $\mathcal{S}$ and $\mathcal{S}_{k}$ |
| $\tilde{n}_{k}$ |  | The size of $\tilde{\mathcal{S}}_{k}$ |
| $\rho$ |  | An imbalance factor, $\rho\equiv\frac{n_{1}}{n_{K}}=\frac{\max_{k}n_{k}}{\min_{k}n_{k}}$ |
| $\bm{\sigma}$, $\sigma_{j}$ |  | Rademacher random variables |

**Table 5: Notation table for models**
| ${\bm{f}}$, $\overline{{\bm{f}}}$ |  | A feature map and a ReLU neural feature map |
| --- | --- | --- |
| $\|{\bm{f}}\|$ |  | The value of $\|{\bm{f}}({\bm{x}})\|$, assuming that $\|{\bm{f}}({\bm{x}})\|$ is equal for all ${\bm{x}}\in\mathcal{X}$ |
| $\mathcal{F}$, $\overline{\mathcal{F}}$, $\overline{\mathcal{F}}^{M}$ |  | The set of feature maps, ReLU neural feature maps, and ReLU neural feature maps with constraints on $M$ |
| ${\bm{h}}$, $\overline{{\bm{h}}}$ |  | The output of the second-to-last layer of the feature map, and that of the ReLU neural feature map |
| ${\bm{g}}$, $g_{k}$ |  | A logit and the logit for class $k$ |
| ${\bm{W}}$, ${\bm{w}}_{k}$ |  | The weights of a linear classifier and its vector for class $k$ |
| ${\bm{W}}^{s}$ |  | The $s$-th linear layer from the end of the feature map |
| $r$ |  | The rank of ${\bm{W}}^{1}$ |
| $s_{l},\hat{\mathbf{}}l,{\bm{v}}_{l}$ |  | The $l$-th singular value, left singular vector, and right singular vector of ${\bm{W}}^{1}$, from its singular value decomposition |
| $\mathcal{H}$ |  | The set of ${\bm{h}}$ |
| $\mathcal{H}_{l}$, $\overline{\mathcal{H}}_{l}^{M}$ |  | The set of $({\bm{v}}_{l},{\bm{h}})$ for ${\bm{f}}\in\mathcal{F}$ and set of $({\bm{v}}_{l},\overline{{\bm{h}}})$ for $\overline{{\bm{f}}}\in\overline{\mathcal{F}}^{M}$ |
| $\mathfrak{R}_{n_{k}}(\mathcal{H}_{l})$, $\hat{\mathfrak{R}}_{\mathcal{S}_{k}}(\mathcal{H}_{l})$ |  | The Rademacher complexity and the empirical Rademacher complexity for $\mathcal{H}_{l}$ (see Section 4.1) |
| $\mathcal{C}$ |  | The complexity of the network and instance |
| $q$ |  | The depth of the feature map |
| $d$, $d_{1}$ |  | The dimension of ${\bm{f}}({\bm{x}})$ and the dimension of ${\bm{h}}({\bm{x}})$ |
| $B$ |  | The upper bound of ${\bm{h}}$, i.e., $\sup_{{\bm{x}}\in\mathcal{X},{\bm{h}}\in\mathcal{H}}\|{\bm{h}}({\bm{x}})\|\leq<br>B$ |
| $M$ |  | The upper bound of $\prod_{s=2}^{q}\|{\bm{W}}^{s}\|_{F}$ |
| ${\bm{\mu}}_{{\bm{f}}}(P),{\bm{\mu}}(P)$ |  | The expectation of ${\bm{f}}({\bm{x}})$ for ${\bm{x}}\sim P$ |
| ${\bm{\mu}}_{{\bm{f}}}(\mathcal{S}),{\bm{\mu}}(\mathcal{S})$ |  | The mean of ${\bm{f}}({\bm{x}})$ for ${\bm{x}}\in\mathcal{S}$ |
| $\overline{{\bm{\mu}}}(P),\overline{{\bm{\mu}}}(\mathcal{S})$ |  | Same as ${\bm{\mu}}_{\overline{{\bm{f}}}}(P)$ and ${\bm{\mu}}_{\overline{{\bm{f}}}}(\mathcal{S})$ |
| $\Pi(\theta;k)$, $\overline{\Pi}(\theta;k)$ |  | The angular bound probability for ${\bm{f}}$ and for $\overline{{\bm{f}}}$ (see Section 4.2). |
| $\gamma_{\mathrm{1v1}}$, $\gamma_{\times}$, $\gamma_{+}$ |  | Hyperparameters for 1vs1adjuster, MLA, and ALA |
| $\theta_{k,k^{\prime}},\theta_{k,k^{\prime}}^{*},\theta_{k,k^{\prime}}^{*}(<br>\gamma_{\mathrm{1v1}})$ |  | The angle of the decision boundary, the optimal angle, and the optimal angle adjusted by $\gamma_{\mathrm{1v1}}$ |
| $\theta_{k,k^{\prime}}^{\times},\theta_{k,k^{\prime}}^{+}$ |  | The angles of the decision boundaries derived from MLA and ALA |
| $\Theta,\Theta^{*}$, $\Theta^{*}_{\gamma_{\mathrm{1v1}}}$ |  | The set of $\theta_{k,k^{\prime}}$, $\theta_{k,k^{\prime}}^{*}$, and $\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}})$ |
| $\psi$ |  | The angle between the weight vectors of an ETF classifier, i.e., $\psi=\arccos\left(-\frac{1}{K-1}\right)$ |
| $\tau_{k,k^{\prime}}$ |  | The ratio $\frac{\|{\bm{\mu}}(\mathcal{S}_{k})\|n_{k}^{\gamma_{\mathrm{1v1}}}}{\|{\bm{\mu<br>}}(\mathcal{S}_{k^{\prime}})\|n_{k^{\prime}}^{\gamma_{\mathrm{1v1}}}}$ |
| ${\bm{m}}_{k,k^{\prime}}$ |  | The normal vector of the decision boundary between $k$ and $k^{\prime}$ |

## Appendix B Proof

Here, we present the detailed proofs and supplementary explanations for the theories proposed in this paper. Appendix B.1 contains the proofs for the propositions discussed in Section 4.2. Appendix B.2 provides specific examples of applying our theory to ReLU neural networks. Appendix B.3 includes the proof of the lemma presented in Section 4.3.

### B.1 Main Analysis

For all $k$ where $n_{k}>1$, the operation of averaging a pair of elements ${\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}$ is defined as follows:

$$ $\displaystyle\operatorname{Avg}_{{\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}} l({\bm{x}},{\bm{x}}^{\prime})\equiv\frac{1}{n_{k}(n_{k}-1)}\sum_{\begin{ subarray}{c}{\bm{x}}_{j_{1}}\in\mathcal{S}_{k}\\ {\bm{x}}_{j_{2}}\in\mathcal{S}_{k}\setminus\{{\bm{x}}_{j_{1}}\}\end{subarray}} l({\bm{x}}_{j_{1}},{\bm{x}}_{j_{2}}).$ (23) $$

First, we propose two lemmas required for the proof of the propositions in Section 4.2. Then, we prove the propositions using the lemmas.

###### Lemma 3 .

Suppose $n_{k}>2$. For any ${\bm{f}}\in\mathcal{F},\delta>0$, the following holds with a probability of at least $1-\delta$:

$$ $\displaystyle\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}}\allowbreak[\|{ \bm{f}}({\bm{x}})-{\bm{f}}({\bm{x}}^{\prime})\|]$ $\displaystyle-\|{\bm{W}}^{1}\|_{2}\sum_{l=1}^{r}\operatorname{Avg}_{{\bm{x}},{ \bm{x}}^{\prime}\in\mathcal{S}_{k}}\allowbreak|{\bm{v}}_{l}^{\top}({\bm{h}}({ \bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|$ $\displaystyle\qquad<\frac{r\|{\bm{W}}^{1}\|_{2}}{\sqrt{n_{k}}}\allowbreak(4 \sqrt{\mathcal{C}(\mathcal{H}_{l},\mathcal{X})}+4B+B\sqrt{2\log\frac{r}{\delta }}).$ (24) $$

###### Proof.

We derive this lemma following the proof of Theorem 3.3 in Mohri et al. [].
By the triangle inequality, the following holds:

$$ $\displaystyle\|{\bm{f}}({\bm{x}})-{\bm{f}}({\bm{x}}^{\prime})\|$ $\displaystyle=\allowbreak\|\sum_{l=1}^{r}s_{l}\hat{\mathbf{}}l{\bm{v}}_{l}^{ \top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))\|$ $\displaystyle\leq\sum_{l=1}^{r}s_{l}\|\hat{\mathbf{}}l\||{\bm{v}}_{l}^{\top}({ \bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|$ $\displaystyle\leq\allowbreak\|{\bm{W}}^{1}\|_{2}\sum_{l=1}^{r}|{\bm{v}}_{l}^{ \top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|.$ (25) $$

We use this inequality to bound $\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}}\allowbreak[\|{\bm{f}}({\bm{x
}})-{\bm{f}}({\bm{x}}^{\prime})\|]$. Then, for each $l\in[r]$, we calculate the probabilistic upper bound of $\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}}\allowbreak[|{\bm{v}}_{l}^{
\top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|]-\operatorname{Avg}_{{
\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}}\allowbreak|{\bm{v}}_{l}^{\top}({
\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|$ and apply the union bound to complete the proof.

Note that $\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}}\allowbreak[|{\bm{v}}_{l}^{
\top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|]=\mathbb{E}_{\mathcal{S
}_{k}\sim P_{k}^{n_{k}}}\allowbreak[\operatorname{Avg}_{{\bm{x}},{\bm{x}}^{
\prime}\in\mathcal{S}_{k}}\allowbreak|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{
\bm{h}}({\bm{x}}^{\prime}))|]$.
For $\mathcal{S}_{k}^{1},\mathcal{S}_{k}^{2}\sim P_{k}^{n_{k}}$, define $\Phi_{l}(\mathcal{S}_{k}^{1})$ as follows:

$$ $\displaystyle\Phi_{l}(\mathcal{S}_{k}^{1})=\sup_{({\bm{v}}_{l},{\bm{h}})\in \mathcal{H}_{l}}\allowbreak(\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}} \allowbreak[|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime} ))|]-\operatorname{Avg}_{{\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}^{1}} \allowbreak|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}) )|).$ (26) $$

Let $\mathcal{S}_{k}^{1},\mathcal{S}_{k}^{2}\sim P_{k}^{n_{k}}$ be datasets that differ only in the $j$-th sample ${\bm{x}}_{j}^{1},{\bm{x}}_{j}^{2}$, and define $\Phi_{l}(\mathcal{S}_{k}^{2})$ similarly as $\Phi_{l}(\mathcal{S}_{k}^{1})$. The difference between $\Phi_{l}(\mathcal{S}_{k}^{1})$ and $\Phi_{l}(\mathcal{S}_{k}^{2})$ can be upper-bounded as follows:

$$ $\displaystyle\Phi_{l}(\mathcal{S}_{k}^{1})-\Phi_{l}(\mathcal{S}_{k}^{2})$ $\displaystyle\leq\sup_{({\bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\Big{(} \operatorname{Avg}_{{\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}^{1}} \allowbreak|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|$ $\displaystyle\hskip 60.00009pt-\operatorname{Avg}_{{\bm{x}},{\bm{x}}^{\prime} \in\mathcal{S}_{k}^{2}}\allowbreak|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm {h}}({\bm{x}}^{\prime}))|\Big{)}$ $\displaystyle=\frac{1}{n_{k}(n_{k}-1)}\sum_{i\neq j}\sup_{({\bm{v}}_{l},{\bm{h }})\in\mathcal{H}_{l}}\allowbreak(|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}}_{j}^{ 1})-{\bm{h}}({\bm{x}}_{i}))|-|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}}_{j}^{2})-{ \bm{h}}({\bm{x}}_{i}))|)$ $\displaystyle\leq\frac{1}{n_{k}(n_{k}-1)}\sum_{i\neq j}\sup_{({\bm{v}}_{l},{ \bm{h}})\in\mathcal{H}_{l}}\allowbreak(|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}}_ {j}^{1})-{\bm{h}}({\bm{x}}_{j}^{2}))|)$ $\displaystyle\leq\frac{2}{n_{k}}\sup_{{\bm{x}}\in\mathcal{X},({\bm{v}}_{l},{ \bm{h}})\in\mathcal{H}_{l}}\|{\bm{h}}({\bm{x}})\|$ (27) $\displaystyle\leq\frac{2B}{n_{k}}.$ (28) $$

Therefore, using McDiarmid’s inequality, we can prove that for any $\delta>0$ the following holds with probability at least $1-\delta$:

$$ $\displaystyle\Phi_{l}(\mathcal{S}_{k})\leq\mathbb{E}_{\mathcal{S}_{k}} \allowbreak[\Phi_{l}(\mathcal{S}_{k})]+B\sqrt{\frac{2\log\frac{1}{\delta}}{n_{ k}}}.$ (29) $$

Note that for any ${\bm{f}}\in\mathcal{F}$, the following inequality holds:

$$ $\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}}\allowbreak[|{\bm{v}}_{l}^{ \top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|]-\operatorname{Avg}_{{ \bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}^{1}}\allowbreak|{\bm{v}}_{l}^{\top }({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|\leq\Phi_{l}(\mathcal{S}_{k}).$ $$

Using Eq. (25), we can derive the following:

$$ $\displaystyle\text{Left hand side of Eq.\,(\ref{eq:feature_bound1})}\leq\|{\bm {W}}^{1}\|_{2}\sum_{l=1}^{r}\Phi_{l}(\mathcal{S}_{k}).$ (30) $$

Thus, we aim to take a union bound of Eq. (29) over all $l$ to derive an upper bound.

Next, we bound $\mathbb{E}_{\mathcal{S}_{k}}\allowbreak[\Phi_{l}(\mathcal{S}_{k})]$:

$$ $\displaystyle\mathbb{E}_{\mathcal{S}_{k}}\allowbreak[\Phi_{l}(\mathcal{S}_{k})]$ $\displaystyle=\mathbb{E}_{\mathcal{S}_{k}}\left[\sup_{({\bm{v}}_{l},{\bm{h}}) \in\mathcal{H}_{l}}\big{(}\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}} \allowbreak[|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime} ))|]\right.$ $\displaystyle\hskip 80.00012pt\left.\vphantom{\sup_{({\bm{v}}_{l},{\bm{h}})\in \mathcal{H}_{l}}}\left.-\operatorname{Avg}_{{\bm{x}},{\bm{x}}^{\prime}\in \mathcal{S}_{k}}\allowbreak|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm{h}}({ \bm{x}}^{\prime}))|\right)\right]$ $\displaystyle\leq\mathbb{E}_{\mathcal{S}_{k},\hat{\mathcal{S}_{k}}}\left[\sup_ {({\bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\Big{(}\operatorname{Avg}_{{\bm{x}} ,{\bm{x}}^{\prime}\in\hat{\mathcal{S}_{k}}}\allowbreak|{\bm{v}}_{l}^{\top}({ \bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime}))|\right.$ $\displaystyle\hskip 90.00014pt\left.\vphantom{\sup_{({\bm{v}}_{l},{\bm{h}})\in \mathcal{H}_{l}}}-\operatorname{Avg}_{{\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S} _{k}}\allowbreak|{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{ \prime}))|\Big{)}\right]$ $\displaystyle=\mathbb{E}_{\mathcal{S}_{k},\hat{\mathcal{S}_{k}}}\left[\sup_{({ \bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\frac{1}{n_{k}(n_{k}-1)}\left( \allowbreak(\sum_{\begin{subarray}{c}\hat{{\bm{x}}}_{j}\in\hat{\mathcal{S}_{k} }\\ \hat{{\bm{x}}}_{j^{\prime}}\in\hat{\mathcal{S}_{k}}\setminus\{\hat{{\bm{x}}}_{ j}\}\end{subarray}}|{\bm{v}}_{l}^{\top}({\bm{h}}(\hat{{\bm{x}}}_{j})-{\bm{h}}( \hat{{\bm{x}}}_{j^{\prime}}))|)\right.\right.$ $\displaystyle\hskip 120.00018pt\left.\left.-\allowbreak(\sum_{\begin{subarray} {c}{\bm{x}}_{j}\in\mathcal{S}_{k}\\ {\bm{x}}_{j^{\prime}}\in\mathcal{S}_{k}\setminus\{{\bm{x}}_{j}\}\end{subarray} }|{\bm{v}}_{l}^{\top}({\bm{h}}({{\bm{x}}}_{j})-{\bm{h}}({{\bm{x}}}_{j^{\prime} }))|)\right)\right]$ $\displaystyle=\mathbb{E}_{\bm{\sigma},\mathcal{S}_{k},\hat{\mathcal{S}_{k}}} \left[\sup_{({\bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\frac{1}{n_{k}(n_{k}-1)} \left(\allowbreak(\sum_{\begin{subarray}{c}\hat{{\bm{x}}}_{j}\in\hat{\mathcal{ S}_{k}}\\ \hat{{\bm{x}}}_{j^{\prime}}\in\hat{\mathcal{S}_{k}}\setminus\{\hat{{\bm{x}}}_{ j}\}\end{subarray}}\sigma_{j}|{\bm{v}}_{l}^{\top}({\bm{h}}(\hat{{\bm{x}}}_{j}) -{\bm{h}}(\hat{{\bm{x}}}_{j^{\prime}}))|)\right.\right.$ $\displaystyle\hskip 120.00018pt\left.\left.-\allowbreak(\sum_{\begin{subarray} {c}{\bm{x}}_{j}\in\mathcal{S}_{k}\\ {\bm{x}}_{j^{\prime}}\in\mathcal{S}_{k}\setminus\{{\bm{x}}_{j}\}\end{subarray} }\sigma_{j}|{\bm{v}}_{l}^{\top}({\bm{h}}({{\bm{x}}}_{j})-{\bm{h}}({{\bm{x}}}_{ j^{\prime}}))|)\right)\right]$ $\displaystyle\leq 2\mathbb{E}_{\bm{\sigma},\mathcal{S}_{k}}\allowbreak[\sup_{( {\bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\frac{1}{n_{k}(n_{k}-1)}\sum_{\begin{ subarray}{c}{{\bm{x}}}_{j}\in{\mathcal{S}_{k}}\\ {{\bm{x}}}_{j^{\prime}}\in{\mathcal{S}_{k}}\setminus\{\hat{{\bm{x}}}_{j}\}\end {subarray}}\sigma_{j}|{\bm{v}}_{l}^{\top}({\bm{h}}({{\bm{x}}}_{j})-{\bm{h}}({{ \bm{x}}}_{j^{\prime}}))|]$ $\displaystyle=2\mathbb{E}_{\bm{\sigma},\mathcal{S}_{k}}\allowbreak[\sup_{({\bm {v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\frac{1}{n_{k}(n_{k}-1)}\sum_{\begin{ subarray}{c}{{\bm{x}}}_{j}\in{\mathcal{S}_{k}}\\ {{\bm{x}}}_{j^{\prime}}\in{\mathcal{S}_{k}}\end{subarray}}\sigma_{j}|{\bm{v}}_ {l}^{\top}({\bm{h}}({{\bm{x}}}_{j})-{\bm{h}}({{\bm{x}}}_{j^{\prime}}))|]$ $\displaystyle\leq\frac{2}{n_{k}-1}\mathbb{E}_{\mathcal{S}_{k}}\allowbreak[\sum _{{{\bm{x}}}_{j^{\prime}}\in{\mathcal{S}_{k}}}\mathbb{E}_{\bm{\sigma}} \allowbreak[\sup_{({\bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\frac{1}{n_{k}} \sum_{{{\bm{x}}}_{j}\in{\mathcal{S}_{k}}}\sigma_{j}|{\bm{v}}_{l}^{\top}({\bm{h }}({{\bm{x}}}_{j})-{\bm{h}}({{\bm{x}}}_{j^{\prime}}))|]]$ $\displaystyle\leq\frac{2}{n_{k}-1}\mathbb{E}_{\mathcal{S}_{k}}\allowbreak[\sum _{{{\bm{x}}}_{j^{\prime}}\in{\mathcal{S}_{k}}}\mathbb{E}_{\bm{\sigma}} \allowbreak[\sup_{({\bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\frac{1}{n_{k}} \sum_{{{\bm{x}}}_{j}\in{\mathcal{S}_{k}}}\sigma_{j}{\bm{v}}_{l}^{\top}({\bm{h} }({{\bm{x}}}_{j})-{\bm{h}}({{\bm{x}}}_{j^{\prime}}))]]$ (31) $\displaystyle\leq\frac{2n_{k}}{n_{k}-1}\mathbb{E}_{\bm{\sigma},\mathcal{S}_{k} }\allowbreak[\sup_{({\bm{v}}_{l},{\bm{h}})\in\mathcal{H}_{l}}\frac{1}{n_{k}} \sum_{{{\bm{x}}}_{j}\in{\mathcal{S}_{k}}}\sigma_{j}{\bm{v}}_{l}^{\top}{\bm{h}} ({{\bm{x}}}_{j})]$ $\displaystyle\quad+\frac{2}{n_{k}(n_{k}-1)}\mathbb{E}_{\mathcal{S}_{k}} \allowbreak[\sum_{{{\bm{x}}}_{j^{\prime}}\in{\mathcal{S}_{k}}}\sup_{({\bm{v}}_ {l},{\bm{h}})\in\mathcal{H}_{l}}|{\bm{v}}_{l}^{\top}{\bm{h}}({{\bm{x}}}_{j^{ \prime}})|]\mathbb{E}_{\bm{\sigma}}\allowbreak[\allowbreak|\sum_{j=1}^{n_{k}}- \sigma_{j}|]$ $\displaystyle\leq\frac{2}{n_{k}-1}\allowbreak(n_{k}{\mathfrak{R}}_{n_{k}} \allowbreak({\mathcal{H}}_{l})+B\mathbb{E}_{\bm{\sigma}}\allowbreak[ \allowbreak|\sum_{j=1}^{n_{k}}\sigma_{j}|]).\par$ (32) $$

The transformation in Eq. (31) is similar to that of Talagrand’s contraction lemma [Ledoux and Talagrand, ].

In addition, the following inequality holds:

$$ $\displaystyle\mathbb{E}_{\bm{\sigma}}\allowbreak[\allowbreak|\sum_{j=1}^{n_{k} }\sigma_{j}|]$ $\displaystyle=\sqrt{\mathbb{E}_{\bm{\sigma}}\allowbreak[\allowbreak|\sum_{j=1} ^{n_{k}}\sigma_{j}|]^{2}}$ $\displaystyle\leq\sqrt{\mathbb{E}_{\bm{\sigma}}\allowbreak[\allowbreak|\sum_{j =1}^{n_{k}}\sigma_{j}|^{2}]}$ $\displaystyle=\sqrt{\mathbb{E}_{\bm{\sigma}}\allowbreak[\sum_{j=1}^{n_{k}} \sigma_{j}^{2}+2\sum_{j\neq j^{\prime}}\sigma_{j}\sigma_{j^{\prime}}]}$ $\displaystyle=\sqrt{n_{k}}.$ (33) $$

From Eqs. (29), (32), and (33), it is proven that following holds with probability at least $1-\delta$,

$$ $\displaystyle\Phi_{l}(\mathcal{S}_{k})$ $\displaystyle\leq\frac{2n_{k}}{n_{k}-1}\allowbreak({\mathfrak{R}}_{n_{k}} \allowbreak({\mathcal{H}}_{l})+\frac{B}{\sqrt{n_{k}}})+\frac{B}{\sqrt{n_{k}}} \sqrt{2\log\frac{1}{\delta}}$ $\displaystyle\leq\frac{2n_{k}}{(n_{k}-1)\sqrt{n_{k}}}\allowbreak(\sqrt{ \mathcal{C}(\mathcal{H}_{l},\mathcal{X})}+B)+\frac{B}{\sqrt{n_{k}}}\sqrt{2\log \frac{1}{\delta}}$ $\displaystyle<\frac{1}{\sqrt{n_{k}}}\allowbreak(4\sqrt{\mathcal{C}(\mathcal{H} _{l},\mathcal{X})}+4B+B\sqrt{2\log\frac{1}{\delta}}).$ (34) $$

Substituting Eq. (34) into Eq. (30) and taking the union bound for all $l$ proves this lemma.

∎

###### Lemma 4 .

Suppose $n_{k}>2$. For ${\bm{f}}\in\mathcal{F}$, assume that for all ${\bm{x}}\in\mathcal{S}_{k}$, ${\bm{f}}({\bm{x}})={\bm{\mu}}(\mathcal{S}_{k})$ holds. For any $0<\delta,\delta^{\prime}<1$, define $\theta$ as follows:

$$ $\displaystyle\theta\equiv\frac{\pi}{2\delta^{\prime}}\frac{r\|{\bm{W}}^{1}\|_{ 2}}{\sqrt{n_{k}}\|{\bm{\mu}}(\mathcal{S}_{k})\|}\allowbreak(4\sqrt{\mathcal{C} (\mathcal{H}_{l},\mathcal{X})}+4B+B\sqrt{2\log\frac{r}{\delta}}).$ (35) $$

Assume that $\delta,\delta^{\prime}$ satisfy $\theta\leq\frac{\pi}{2}$. For ${\bm{x}}\sim P_{k}$, the probability that the angle between ${\bm{f}}({\bm{x}})$ and $\mu(\mathcal{S}_{k})$ is less than $\theta$ is at least $1-(\delta+\delta^{\prime})$.

###### Proof.

We bound $\mathbb{E}_{{\bm{x}}\sim P_{k},\mathcal{S}_{k}\sim P_{k}^{n_{k}}}\allowbreak[{
\|{\bm{f}}({\bm{x}})-{\bm{\mu}}(\mathcal{S}_{k})\|}]$ and apply Markov’s inequality. Expanding this,

$$ $\displaystyle\mathbb{E}_{{\bm{x}}\sim P_{k},\mathcal{S}_{k}\sim P_{k}^{n_{k}}} \allowbreak[{\|{\bm{f}}({\bm{x}})-{\bm{\mu}}(\mathcal{S}_{k})\|}]$ $\displaystyle=\frac{1}{n_{k}}\mathbb{E}_{{\bm{x}}\sim P_{k},\mathcal{S}_{k} \sim P_{k}^{n_{k}}}\allowbreak[{\allowbreak\|n_{k}{\bm{f}}({\bm{x}})-\sum_{{ \bm{x}}^{\prime}\in\mathcal{S}_{k}}{\bm{f}}({\bm{x}}^{\prime})\|}]$ $\displaystyle\leq\frac{1}{n_{k}}\mathbb{E}_{{\bm{x}}\sim P_{k},\mathcal{S}_{k} \sim P_{k}^{n_{k}}}\allowbreak[{\sum_{{\bm{x}}^{\prime}\in\mathcal{S}_{k}} \allowbreak\|{\bm{f}}({\bm{x}})-{\bm{f}}({\bm{x}}^{\prime})\|}]$ $\displaystyle=\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}}\allowbreak[ \allowbreak\|{\bm{f}}({\bm{x}})-{\bm{f}}({\bm{x}}^{\prime})\|].$ (36) $$

Using Markov’s inequality, for any $\delta^{\prime}>0$, with probability at least $1-\delta^{\prime}$,

$$ $\displaystyle\|{\bm{f}}({\bm{x}})-{\bm{\mu}}(\mathcal{S}_{k})\|$ $\displaystyle\leq\frac{1}{\delta^{\prime}}{\mathbb{E}_{{\bm{x}}\sim P_{k}, \mathcal{S}_{k}\sim P_{k}^{n_{k}}}\allowbreak[{\|{\bm{f}}({\bm{x}})-{\bm{\mu}} (\mathcal{S}_{k})\|}]}$ $\displaystyle=\frac{1}{\delta^{\prime}}{\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime} \sim P_{k}}\allowbreak[\allowbreak\|{\bm{f}}({\bm{x}})-{\bm{f}}({\bm{x}}^{ \prime})\|]}.$ (37) $$

Before applying Lemma 3 to this case, we demonstrate that the second term on the left-hand side of Eq. (24) is zero in this situation. When ${\bm{f}}({\bm{x}})={\bm{\mu}}(\mathcal{S}_{k})$ satisfies for all ${\bm{x}}\in\mathcal{S}_{k}$, ${\bm{f}}({\bm{x}})={\bm{f}}({\bm{x}}^{\prime})$ holds for all ${\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}$. Then, we have $\sum_{l=1}^{r}s_{l}\hat{\mathbf{}}l{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm
{h}}({\bm{x}}^{\prime}))=\bm{0}$.
Since $\hat{\mathbf{}}l$ are the left singular vectors of ${\bm{W}}^{1}$, they are linearly independent for different $l$. Therefore, for all $l\in[r]$ and for all ${\bm{x}},{\bm{x}}^{\prime}\in\mathcal{S}_{k}$,

$$ $\displaystyle{\bm{v}}_{l}^{\top}({\bm{h}}({\bm{x}})-{\bm{h}}({\bm{x}}^{\prime} ))=0.$ (38) $$

Then, we combine the equation Eqs. (37) and (38) with the result of Lemma 3 by union bound. For any $\delta,\delta^{\prime}>0$, with probability at least $1-(\delta+\delta^{\prime})$, the following holds:

$$ $\displaystyle\|{\bm{f}}({\bm{x}})-{\bm{\mu}}(\mathcal{S}_{k})\|$ $\displaystyle<\frac{1}{\delta^{\prime}}\frac{r\|{\bm{W}}^{1}\|_{2}}{\sqrt{n_{k }}}\allowbreak(4\sqrt{\mathcal{C}(\mathcal{H}_{l},\mathcal{X})}+4B+B\sqrt{2 \log\frac{r}{\delta}})$ $\displaystyle\equiv\frac{2}{\pi}\|{\bm{\mu}}(\mathcal{S}_{k})\|\theta.$ (39) $$

Since $1-(\delta+\delta^{\prime})$ is a lower bound for the probability, even restricting $\delta,\delta^{\prime}<1$ does not compromise the usefulness of the theorem.

The angle between ${\bm{f}}({\bm{x}})$ and ${\bm{\mu}}(\mathcal{S}_{k})$ can be expressed as $\arcsin\allowbreak(\frac{\|{\bm{f}}({\bm{x}})-{\bm{\mu}}(\mathcal{S}_{k})\|}{
\|{\bm{\mu}}(\mathcal{S}_{k})\|})$ when $\frac{\|{\bm{f}}({\bm{x}})-{\bm{\mu}}(\mathcal{S}_{k})\|}{\|{\bm{\mu}}(
\mathcal{S}_{k})\|}\leq 1$. Since $\arcsin(t)$ is strictly monotonically increasing for $0\leq t\leq 1$,
when we have $\theta\leq\frac{\pi}{2}$, the upper bound of the angle between ${\bm{f}}({\bm{x}})$ and ${\bm{\mu}}(\mathcal{S}_{k})$ can be written as $\arcsin\allowbreak(\frac{\|{\bm{f}}({\bm{x}})-{\bm{\mu}}(\mathcal{S}_{k})\|}{
\|{\bm{\mu}}(\mathcal{S}_{k})\|})<\arcsin{\allowbreak(\frac{2}{\pi}\theta)}\leq\theta$. This means that the upper bound of the angle between the features and the average training features of the class is less than $\theta$ with probability at least $1-(\delta+\delta^{\prime})$.

∎

See 1

###### Proof.

Consider the following $\delta,\delta^{\prime}>0$:

$$ $\displaystyle\delta$ $\displaystyle=\frac{\pi}{2\theta}\frac{r\|{\bm{W}}^{1}\|_{2}}{\sqrt{n_{k}}\|{ \bm{\mu}}(\mathcal{S}_{k})\|},$ (40) $\displaystyle\delta^{\prime}$ $\displaystyle=\frac{\pi}{2\theta}\frac{r\|{\bm{W}}^{1}\|_{2}}{\sqrt{n_{k}}\|{ \bm{\mu}}(\mathcal{S}_{k})\|}\allowbreak(4\sqrt{\mathcal{C}(\mathcal{H}_{l}, \mathcal{X})}+4B+B\sqrt{2\log\frac{2\theta\sqrt{n_{k}}\|{\bm{\mu}}(\mathcal{S} _{k})\|}{\pi\|{\bm{W}}^{1}\|_{2}}}).$ (41) $$

Given $B\geq 1$ and the condition on $\theta$,

$$ $\displaystyle\delta<\delta^{\prime}<\frac{\pi}{2\theta}\frac{r\|{\bm{W}}^{1}\| _{2}}{\sqrt{n_{k}}\|{\bm{\mu}}(\mathcal{S}_{k})\|}\allowbreak(4\sqrt{\mathcal{ C}(\mathcal{H}_{l},\mathcal{X})}+4B+B\sqrt{2\log\frac{\sqrt{n_{k}}\|{\bm{\mu}} (\mathcal{S}_{k})\|}{\|{\bm{W}}^{1}\|_{2}}})<1.$ (42) $$

Defining $\theta$ as above, we get $\theta=\frac{\pi}{2\delta^{\prime}}\frac{r\|{\bm{W}}^{1}\|_{2}}{\sqrt{n_{k}}\|
{\bm{\mu}}(\mathcal{S}_{k})\|}\allowbreak(4\sqrt{\mathcal{C}(\mathcal{H}_{l},
\mathcal{X})}+4B+B\sqrt{2\log\frac{r}{\delta}})$.
Therefore, by Lemma 4, the probability that the angle between ${\bm{f}}({\bm{x}})$ and ${\bm{\mu}}(\mathcal{S}_{k})$ is less than $\theta$ is at least

$$ $\displaystyle 1-(\delta+\delta^{\prime})=1-\frac{\pi}{2\theta}\frac{r\|{\bm{W} }^{1}\|_{2}}{\sqrt{n_{k}}\|{\bm{\mu}}(\mathcal{S}_{k})\|}\allowbreak(4\sqrt{ \mathcal{C}(\mathcal{H}_{l},\mathcal{X})}+4B+1+B\sqrt{2\log\frac{2\theta\sqrt{ n_{k}}\|{\bm{\mu}}(\mathcal{S}_{k})\|}{\pi\|{\bm{W}}^{1}\|_{2}}}).$ (43) $$

∎

See 2

###### Proof.

Noting that $\theta_{k^{\prime},k}=\psi-\theta_{k,k^{\prime}}$, we have:

$$ $\displaystyle\partialderivative{\theta_{k,k^{\prime}}}\allowbreak(\Pi(\theta_{ k,k^{\prime}};k)+\Pi(\theta_{k^{\prime},k};k^{\prime}))=\left. \partialderivative{\Pi(\theta;k)}{\theta}\right|_{\theta=\theta_{k,k^{\prime}} }-\left.\partialderivative{\Pi(\theta;k^{\prime})}{\theta}\right|_{\theta=\psi -\theta_{k^{\prime},k}}.$ (44) $$

Since $\theta_{k,k^{\prime}}^{*},\theta_{k^{\prime},k}^{*}>0$ and $\theta_{k,k^{\prime}}^{*}+\theta_{k^{\prime},k}^{*}=\psi$, with $\theta_{k,k^{\prime}}^{*}\|{\bm{\mu}}(\mathcal{S}_{k})\|\sqrt{n_{k}}=\theta_{k
^{\prime},k}^{*}\|{\bm{\mu}}(\mathcal{S}_{k^{\prime}})\|\sqrt{n_{k^{\prime}}}$, the following holds:

$$ $\displaystyle\left.\partialderivative{\Pi(\theta;k)}{\theta}\right|_{\theta= \theta_{k,k^{\prime}}^{*}}=\left.\partialderivative{\Pi(\theta;k^{\prime})}{ \theta}\right|_{\theta=\psi-\theta_{k^{\prime},k}^{*}}.$ (45) $$

Thus, we have $\partialderivative{\theta_{k,k^{\prime}}}\allowbreak(\Pi(\theta_{k,k^{\prime}}
;k)+\Pi(\theta_{k^{\prime},k};k^{\prime}))=0$ when $\theta_{k,k^{\prime}}=\theta_{k,k^{\prime}}^{*}$ and $\theta_{k^{\prime},k}=\theta_{k^{\prime},k}^{*}$.

Next, we prove that this is the only solution that gives the maximum value within the aforementioned range. We have:

$$ $\displaystyle\partialderivative[order=2]{\theta_{k,k^{\prime}}}\allowbreak(\Pi (\theta_{k,k^{\prime}};y)+\Pi(\theta_{y^{\prime}};y^{\prime}))= \partialderivative[order=2]{\Pi(\theta_{k,k^{\prime}};y)}{\theta_{k,k^{\prime} }}+\left.\partialderivative[order=2]{\Pi(\theta;y^{\prime})}{\theta}\right|_{ \theta=\psi-\theta_{k,k^{\prime}}}.$ (46) $$

Here, we define $\alpha_{k}\equiv\frac{\pi}{2}\frac{r\|{\bm{W}}^{1}\|_{2}}{\sqrt{n_{k}}\|{\bm{
\mu}}(\mathcal{S}_{k})\|},\beta\equiv 4\sqrt{\mathcal{C}(\mathcal{H}_{l},
\mathcal{X})}+4B+1$, and $\zeta_{k}(\theta_{k,k^{\prime}})=2\log\allowbreak(\frac{r\theta_{k,k^{\prime}}
}{\alpha_{k}})$. Note that $\partialderivative{\zeta_{k}(\theta_{k,k^{\prime}})}{\theta_{k,k^{\prime}}}=
\frac{2}{\theta_{k,k^{\prime}}}$. Then, the following holds:

$$ $\displaystyle\partialderivative[order=2]{\Pi(\theta_{k,k^{\prime}};k)}{\theta_ {k,k^{\prime}}}$ $\displaystyle=\partialderivative[order=2]{\theta_{k,k^{\prime}}}\allowbreak(1- \frac{\alpha_{k}}{\theta_{k,k^{\prime}}}\allowbreak(\beta+B\sqrt{\zeta_{k}( \theta_{k,k^{\prime}})}))$ $\displaystyle=\partialderivative{\theta_{k,k^{\prime}}}\allowbreak(\frac{ \alpha_{k}}{\theta_{k,k^{\prime}}^{2}}\allowbreak(\beta+B\allowbreak\zeta_{k}( \theta_{k,k^{\prime}})^{\frac{1}{2}})-\frac{B\alpha_{k}}{\theta_{k,k^{\prime}} ^{2}}\allowbreak\zeta_{k}(\theta_{k,k^{\prime}})^{-\frac{1}{2}})$ $\displaystyle=\partialderivative{\theta_{k,k^{\prime}}}\allowbreak(\frac{ \alpha_{k}}{\theta_{k,k^{\prime}}^{2}}\allowbreak(\beta+B\allowbreak\zeta_{k}( \theta_{k,k^{\prime}})^{\frac{1}{2}}-B\allowbreak\zeta_{k}(\theta_{k,k^{\prime }})^{-\frac{1}{2}}))$ $\displaystyle=-\frac{2\alpha_{k}}{\theta_{k,k^{\prime}}^{3}}\allowbreak(\beta+ B\allowbreak\zeta_{k}(\theta_{k,k^{\prime}})^{\frac{1}{2}}-B\allowbreak\zeta_{ k}(\theta_{k,k^{\prime}})^{-\frac{1}{2}})$ $\displaystyle\quad+\frac{\alpha_{k}}{\theta_{k,k^{\prime}}^{2}}\allowbreak( \frac{B}{\theta_{k,k^{\prime}}}\allowbreak\zeta_{k}(\theta_{k,k^{\prime}})^{- \frac{1}{2}}+\frac{B}{\theta_{k,k^{\prime}}}\allowbreak\zeta_{k}(\theta_{k,k^{ \prime}})^{-\frac{3}{2}})$ $\displaystyle=-\frac{\alpha_{k}}{\theta_{k,k^{\prime}}^{3}}\allowbreak(2\beta+ 2B\zeta_{k}(\theta_{k,k^{\prime}})^{\frac{1}{2}}-3B\zeta_{k}(\theta_{k,k^{ \prime}})^{-\frac{1}{2}}-B\zeta_{k}(\theta_{k,k^{\prime}})^{-\frac{3}{2}}).$ (47) $$

From the condition, there exists $\delta<1$ such that $\theta_{k,k^{\prime}}=\frac{\alpha_{k}}{\delta}$, implying $\frac{\theta_{k,k^{\prime}}}{\alpha_{k}}>1$. Since $\zeta_{k}(\theta_{k,k^{\prime}})>2\log 2>2$, we have

$$ $\displaystyle\partialderivative[order=2]{\Pi(\theta_{k,k^{\prime}};k)}{\theta_ {k,k^{\prime}}}$ $\displaystyle\leq-\frac{\alpha_{k}}{\theta_{k,k^{\prime}}^{3}}\allowbreak(2 \beta+2B\zeta_{k}(\theta_{k,k^{\prime}})^{\frac{1}{2}}-4B\zeta_{k}(\theta_{k,k ^{\prime}})^{-\frac{1}{2}})$ $\displaystyle=-\frac{2\alpha_{k}}{\theta_{k,k^{\prime}}^{3}}\allowbreak(\beta+ B\zeta_{k}(\theta_{k,k^{\prime}})^{-\frac{1}{2}}\allowbreak(\zeta_{k}(\theta_{ k,k^{\prime}})-2))$ $\displaystyle<0.$ (48) $$

Similarly, we can prove that $\left.\partialderivative[order=2]{\Pi(\theta;k^{\prime})}{\theta}\right|_{
\theta=\psi-\theta_{k,k^{\prime}}}<0$.

Therefore, Eq. (8) is the only solution that gives the maximum value within the range where $\theta_{k,k^{\prime}}$ and $\theta_{k^{\prime},k}$ satisfy Eq. (5).
∎

See 3

###### Proof.

The following holds, and the result follows trivially from Proposition 2.

$$ $\displaystyle\max_{\Theta}\sum_{k\in\mathcal{Y}}\sum_{k^{\prime}\neq k}\Pi( \theta_{k,k^{\prime}};k)+\Pi(\theta_{k^{\prime},k};k^{\prime})\leq\sum_{k\in \mathcal{Y}}\sum_{k^{\prime}\neq k}\max_{\theta_{k,k^{\prime}},\theta_{k^{ \prime},k}}\Pi(\theta_{k,k^{\prime}};k)+\Pi(\theta_{k^{\prime},k};k^{\prime}).$ (49) $$

∎

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Proof.

###### Proof.

###### Proof.

### B.2 Case of ReLU Neural Networks

In this section, we specifically demonstrate the values of $\mathcal{C}(\mathcal{H}_{l},\mathcal{X})$ and $B$ when the feature map is restricted to ReLU neural feature maps. This allows us to validate the assumption $\mathfrak{R}_{n_{k}}(\mathcal{H}_{l})\leq\sqrt{\frac{\mathcal{C}(\mathcal{H}_{
l},\mathcal{X})}{n_{k}}}$ posed in this paper and to illustrate the practicality of the proposed theory.

Let $\overline{\mathcal{F}}$ represent the set of ReLU neural feature map, and define a ReLU neural feature map as $\overline{{\bm{f}}}({\bm{x}})={\bm{W}}^{1}\max(\bm{0},{\bm{W}}^{2}\ldots\max(
\bm{0},{\bm{W}}^{q}{\bm{x}})\ldots)\in\overline{\mathcal{F}}$. Here, $q$ denotes the depth of the network, and the $\max$ operation is applied element-wise. We define the set $\overline{\mathcal{F}}^{M}$ as the set of ReLU neural feature map where the product of the Frobenius norms from the first layer to the second-to-last layer is bounded by $M$. That is,

$$ $\displaystyle\overline{\mathcal{F}}^{M}$ $\displaystyle=\left\{\overline{{\bm{f}}}^{\prime}:{\bm{x}}\mapsto{\bm{W}}^{1} \max(\bm{0},{\bm{W}}^{2}\ldots\max(\bm{0},{\bm{W}}^{q}{\bm{x}})\ldots)\in \overline{\mathcal{F}}\ |\ \prod_{s=2}^{q}\|{\bm{W}}^{s}\|_{F}\leq M\right\}.$ (50) $$

We focus on functions that belong to $\overline{\mathcal{F}}^{M}$. When discussing ReLU neural networks, we add an overline to distinguish them from the general case. For instance, $\overline{{\bm{h}}}$ refers to a function that returns the output of the second-to-last layer of a ReLU neural feature map. Similarly, $\overline{{\bm{\mu}}}(\mathcal{S}_{k})$ represents the average of the features $\overline{{\bm{f}}}({\bm{x}})$ for the dataset $\mathcal{S}_{k}$.

For such networks, we similarly define $\overline{\mathcal{H}}_{l}^{M}$, their Rademacher complexity, and empirical Rademacher complexity as follows:

$$ $\displaystyle\overline{\mathcal{H}}_{l}^{M}\equiv\{({\bm{v}}_{l},\overline{{ \bm{h}}})\ |\ \overline{{\bm{f}}}\in\overline{\mathcal{F}}^{M},\overline{{\bm{ f}}}={\bm{W}}^{1}\overline{{\bm{h}}},\ {\bm{v}}_{l}\text{ is the }l\text{-th right singular vector of }{\bm{W}}^{1}\},$ (51) $$

$$ $\displaystyle\mathfrak{R}_{n_{k}}\allowbreak(\overline{\mathcal{H}}_{l}^{M})$ $\displaystyle\equiv\mathbb{E}_{\mathcal{S}^{\prime}_{k}\sim P_{k}^{n_{k}},\bm{ \sigma}}\left[\sup_{\allowbreak({\bm{v}}_{l},\overline{{\bm{h}}})\in\overline{ \mathcal{H}}_{l}^{M}}\frac{1}{n_{k}}\sum_{{\bm{x}}_{j}\in\mathcal{S}^{\prime}_ {k}}\sigma_{j}{\bm{v}}_{l}^{\top}\overline{{\bm{h}}}({\bm{x}}_{j})\right],$ (52) $\displaystyle\hat{\mathfrak{R}}_{\mathcal{S}_{k}}\allowbreak(\overline{ \mathcal{H}}_{l}^{M})$ $\displaystyle\equiv\mathbb{E}_{\bm{\sigma}}\left[\sup_{\allowbreak({\bm{v}}_{l },\overline{{\bm{h}}})\in\overline{\mathcal{H}}_{l}^{M}}\frac{1}{n_{k}}\sum_{{ \bm{x}}_{j}\in\mathcal{S}_{k}}\sigma_{j}{\bm{v}}_{l}^{\top}\overline{{\bm{h}}} ({\bm{x}}_{j})\right].$ (53) $$

According to Golowich et al. [], the empirical Rademacher complexity for this family of functions is bounded by:

$$ $\displaystyle\hat{\mathfrak{R}}_{\mathcal{S}_{k}}\allowbreak(\overline{ \mathcal{H}}_{l}^{M})$ $\displaystyle=\mathbb{E}_{\bm{\sigma}}\allowbreak[\sup_{\allowbreak({\bm{v}}_{ l},\overline{{\bm{h}}})\in\overline{\mathcal{H}}_{l}^{M}}\frac{1}{n_{k}}\sum_{ {\bm{x}}_{j}\in\mathcal{S}_{k}}\sigma_{j}{\bm{v}}_{l}^{\top}\overline{{\bm{h}} }({\bm{x}}_{j})]$ $\displaystyle\leq\frac{1}{\sqrt{n_{k}}}\allowbreak(\sqrt{2q\log 2}+1)M\sup_{{ \bm{x}}\in\mathcal{X}}\|{\bm{x}}\|$ $\displaystyle\leq\frac{1}{\sqrt{n_{k}}}(1.5\sqrt{q}+1)M\sup_{{\bm{x}}\in \mathcal{X}}\|{\bm{x}}\|.$ (54) $$

Taking the expectation over $\mathcal{S}_{k}$, we can replace $\sqrt{\mathcal{C}(\mathcal{H}_{l},\mathcal{X})}=(1.5\sqrt{q}+1)M\sup_{{\bm{x}}
\in\mathcal{X}}\|{\bm{x}}\|$. Since $\mathcal{C}(\mathcal{H}_{l},\mathcal{X})$ does not depend on $n_{k}$, this confirms the assumption. We can also replace $B=M\sup_{{\bm{x}}\in\mathcal{X}}\|{\bm{x}}\|$ because $\sup_{{\bm{x}}\in\mathcal{X},{\bm{h}}\in\mathcal{H}}\|{\bm{h}}({\bm{x}})\|\leq
M
\sup_{{\bm{x}}\in\mathcal{X}}\|{\bm{x}}\|$.

In this case, Lemmas 3 and 4 can be rewritten as follows. Since these are simple substitutions, we omit the proofs.

###### Lemma 5 .

Suppose $n_{k}>2$. For any $\overline{{\bm{f}}}\in\overline{\mathcal{F}}^{M}$ and any $\delta>0$, the following holds with a probability at least $1-\delta$:

$$ $\displaystyle\mathbb{E}_{{\bm{x}},{\bm{x}}^{\prime}\sim P_{k}}\allowbreak[ \allowbreak\|\overline{{\bm{f}}}({\bm{x}})-\overline{{\bm{f}}}({\bm{x}}^{ \prime})\|]$ $\displaystyle-\|{\bm{W}}^{1}\|_{2}\sum_{l=1}^{r}\operatorname{Avg}_{{\bm{x}},{ \bm{x}}^{\prime}\in\mathcal{S}_{k}}\allowbreak|{\bm{v}}_{l}^{\top}\allowbreak( \overline{{\bm{h}}}({\bm{x}})-\overline{{\bm{h}}}({\bm{x}}^{\prime}))|$ $\displaystyle\qquad<\frac{r\|{\bm{W}}^{1}\|_{2}M\sup_{{\bm{x}}\in\mathcal{X}} \|{\bm{x}}\|}{\sqrt{n_{k}}}\allowbreak(6\sqrt{q}+8+\sqrt{2\log\frac{r}{\delta} }).$ (55) $$

###### Lemma 6 .

Suppose $n_{k}>2$. For $\overline{{\bm{f}}}\in\overline{\mathcal{F}}^{M}$, assume that for all ${\bm{x}}\in\mathcal{S}_{k}$, $\overline{{\bm{f}}}({\bm{x}})=\overline{{\bm{\mu}}}(\mathcal{S}_{k})$ holds. For any $0<\delta,\delta^{\prime}<1$, define $\theta$ as follows:

$$ $\displaystyle\theta\equiv\frac{\pi}{2\delta^{\prime}}\frac{r\|{\bm{W}}^{1}\|_{ 2}M\sup_{{\bm{x}}\in\mathcal{X}}\|{\bm{x}}\|}{\sqrt{n_{k}}\|\overline{{\bm{\mu }}}(\mathcal{S}_{k})\|}\allowbreak(6\sqrt{q}+8+\sqrt{2\log\frac{r}{\delta}}).$ (56) $$

Assume that $\delta,\delta^{\prime}$ satisfy $\theta\leq\frac{\pi}{2}$. For ${\bm{x}}\sim P_{k}$, the probability that the angle between $\overline{{\bm{f}}}({\bm{x}})$ and $\overline{{\bm{\mu}}}(\mathcal{S}_{k})$ is less than $\theta$ is at least $1-(\delta+\delta^{\prime})$.

We define the angular bound probability $\overline{\Pi}(\theta;k)$ for a ReLU neural network as in Section 4.2. Then, Proposition 1 can be rewritten as follows. The proof is omitted here as well.

###### Lemma 7 .

Suppose $n_{k}>2$. For $\overline{{\bm{f}}}\in\overline{\mathcal{F}}^{M}$, assume that for all ${\bm{x}}\in\mathcal{S}_{k}$, $\overline{{\bm{f}}}({\bm{x}})=\overline{{\bm{\mu}}}(\mathcal{S}_{k})$ holds.
Consider any $\theta$ satisfying the following conditions:

$$ $\displaystyle\frac{\pi r\|{\bm{W}}^{1}\|_{2}M\sup_{{\bm{x}}\in\mathcal{X}}\|{ \bm{x}}\|}{2\sqrt{n_{k}}\|\overline{{\bm{\mu}}}(\mathcal{S}_{k})\|}\allowbreak (6\sqrt{q}+8+\sqrt{2\log\allowbreak(\frac{\sqrt{n_{k}}\|\overline{{\bm{\mu}}}( \mathcal{S}_{k})\|}{\|{\bm{W}}^{1}\|_{2}})})<\theta<\frac{\pi}{2}.$ (57) $$

For such $\theta$, the following holds:

$$ $\displaystyle\overline{\Pi}(\theta;k)=1-\frac{\pi r\|{\bm{W}}^{1}\|_{2}}{2 \theta\sqrt{n_{k}}\|\overline{{\bm{\mu}}}(\mathcal{S}_{k})\|}\allowbreak(1+M \sup_{{\bm{x}}\in\mathcal{X}}\|{\bm{x}}\|\allowbreak(6\sqrt{q}+8+\sqrt{2\log \allowbreak(\frac{2\theta\sqrt{n_{k}}\|\overline{{\bm{\mu}}}(\mathcal{S}_{k}) \|}{\pi\|{\bm{W}}^{1}\|_{2}})})).$ (58) $$

Propositions 2 and 3 also hold similarly, ensuring the validity of 1vs1adjuster.

###### Lemma 5 .

###### Lemma 6 .

###### Lemma 7 .

### B.3 MLA Approximates 1vs1adjuster

In this section, we provide the proof of Lemma 2.
See 2

###### Proof.

When $\theta=0$, the result is trivial since $\phi(0)=\tan(0)=0$. For the remainder, we assume $\theta\in(0,1)$ unless otherwise stated.
Define $h(\theta)\equiv\frac{\tan\allowbreak(\frac{\pi}{2}\theta)}{\phi(\theta)}=\frac
{\tan\allowbreak(\frac{\pi}{2}\theta)(1-\theta)}{\theta}$.
Since $h(\theta)=\frac{1}{h(1-\theta)}$, proving the following will conclude the proof:

$$ $\displaystyle 1\leq h(\theta)<\frac{\pi}{2}\qquad\allowbreak(0<\theta\leq\frac {1}{2}).$ (59) $$

First, we demonstrate that $h(\theta)$ is monotonically non-increasing.

$$ $\displaystyle h^{\prime}(\theta)$ $\displaystyle=\frac{\theta\allowbreak(\frac{\pi}{2}\frac{1}{\cos^{2} \allowbreak(\frac{\pi}{2}\theta)}(1-\theta)-\tan\allowbreak(\frac{\pi}{2} \theta))-\tan\allowbreak(\frac{\pi}{2}\theta)(1-\theta)}{\theta^{2}}$ $\displaystyle=\frac{\frac{\pi}{2}\frac{\theta(1-\theta)}{\cos^{2}\allowbreak( \frac{\pi}{2}\theta)}-\tan\allowbreak(\frac{\pi}{2}\theta)}{\theta^{2}}.$ (60) $$

Now, define $l(\theta)\equiv\frac{\pi}{2}\frac{\theta(1-\theta)}{\cos^{2}\allowbreak(\frac{
\pi}{2}\theta)}-\tan\allowbreak(\frac{\pi}{2}\theta)$ for $\theta\in[0,1)$:

$$ $\displaystyle l^{\prime}(\theta)$ $\displaystyle=\frac{\pi}{2}\allowbreak(\frac{(-2\theta+1)\cos^{2}\allowbreak( \frac{\pi}{2}\theta)-\pi\theta(1-\theta)\sin(\frac{\pi}{2}\theta)\cos(\frac{ \pi}{2}\theta)}{\cos^{4}\allowbreak(\frac{\pi}{2}\theta)}-\frac{1}{\cos^{2} \allowbreak(\frac{\pi}{2}\theta)})$ $\displaystyle=-\frac{\pi}{2}\frac{2\theta\cos^{2}\allowbreak(\frac{\pi}{2} \theta)+\pi\theta(1-\theta)\sin(\frac{\pi}{2}\theta)\cos(\frac{\pi}{2}\theta)} {\cos^{4}\allowbreak(\frac{\pi}{2}\theta)}$ $\displaystyle\leq 0.\par$ (61) $$

Since $l(0)=0$, we have $l(\theta)\leq 0$ for $\theta\in[0,1)$. Therefore, from Eq. (60), $h^{\prime}(\theta)\leq 0$ for $\theta\in(0,1)$, indicating that $h(\theta)$ is monotonically non-increasing.

Since $h(\theta)=1$, to prove Eq. (59), we must indicate that $\lim_{\theta\to+0}h(\theta)=\frac{\pi}{2}$.
By applying l’Hôpital’s rule, this can be verified.

$$ $\displaystyle\lim_{\theta\to+0}h(\theta)$ $\displaystyle=\lim_{\theta\to+0}\frac{\tan\allowbreak(\frac{\pi}{2}\theta)(1- \theta)}{\theta}$ $\displaystyle=\lim_{\theta\to+0}-\tan\allowbreak(\frac{\pi}{2}\theta)+\frac{ \pi}{2}\frac{(1-\theta)}{\cos^{2}\allowbreak(\frac{\pi}{2}\theta)}$ $\displaystyle=\frac{\pi}{2}.$ (62) $$

Thus, Eq. (59) holds, completing the proof.

∎

###### Proof.

## Appendix C Algorithm of 1vs1adjuster

Algorithm 1 outlines the detailed steps of 1vs1adjuster, a 1-vs-1 multi-class classifier that performs classification based on the decision boundaries proposed in Proposition 3.
The derivation of the normal vector ${\bm{m}}_{k,k^{\prime}}\in\mathbb{R}^{d}$ for the decision boundary between $k$ and $k^{\prime}$ is as follows. Since ${\bm{m}}_{k,k^{\prime}}$ lies in the same plane as ${\bm{w}}_{k}$ and ${\bm{w}}_{k^{\prime}}$, and the angles with each are specified, it can be expressed using $\alpha,\beta\in\mathbb{R}$ as follows. Note that we assume $\|{\bm{m}}_{k,k^{\prime}}\|=1$ here.

$$ $\left\{\,\begin{aligned} {\bm{m}}_{k,k^{\prime}}&=\alpha{\bm{w}}_{k}+\beta{\bm {w}}_{k^{\prime}}\\ {\bm{m}}_{k,k^{\prime}}^{\top}{\bm{w}}_{k}&=\cos\allowbreak(\frac{\pi}{2}- \theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}}))\\ {\bm{m}}_{k,k^{\prime}}^{\top}{\bm{w}}_{k^{\prime}}&=\cos\allowbreak(\frac{\pi }{2}+\theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1}}))\end{aligned}\right.$ (63) $$

Solving this system of equations for $\alpha$ and $\beta$, we obtain the following:

$$ $\left\{\,\begin{aligned} \alpha&=\frac{\sin\theta_{k,k^{\prime}}^{*}(\gamma_{ \mathrm{1v1}})+\sin\theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1}})\cos\psi}{1 -\cos^{2}\psi}\\ \beta&=-\frac{\sin\theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1}})+\sin\theta_ {k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}})\cos\psi}{1-\cos^{2}\psi}\end{aligned }\right.$ (64) $$

Thus, the decision boundary can be defined as a plane passing through the origin with ${\bm{m}}_{k,k^{\prime}}$ as the normal vector. Note that Algorithm 1 simplifies this by using the normal vector multiplied by $1-\cos^{2}\psi$. Additionally, when $K$ is sufficiently large, ${\bm{m}}_{k,k^{\prime}}$ can be approximated as ${\bm{m}}_{k,k^{\prime}}\sim\sin\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}}
){\bm{w}}_{k}-\sin\theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1}}){\bm{w}}_{k^
{\prime}}$.

Figure: Algorithm 1 1vs1adjuster

## Appendix D Discussion: Approximation of ALA

Similar to the approximation of MLA in Section 4.3, we explore approximating ALA to 1vs1adjuster. ALA modifies the logits by adding a correction term, $-\gamma_{+}\log n_{k}$, where $\gamma_{+}>0$.

First, we assume that for any ${\bm{x}}\in\mathcal{X}$, the feature norm is constant, i.e., ${\bm{f}}({\bm{x}})=|{\bm{f}}|$. Similar to the MLA case, we denote the coefficient of the ALA by $\eta_{k}$. To adjust the decision boundaries in ALA such that it satisfies Proposition 3, $\eta_{k}$ must be set so that the following condition holds for all $k\neq k^{\prime}\in\mathcal{Y}$:

$$ $\displaystyle\quad\|{\bm{f}}\|\cos(\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1 v1}}))-\eta_{k}=\|{\bm{f}}\|\cos(\theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1 }}))-\eta_{k^{\prime}}$ $\displaystyle\Leftrightarrow\|{\bm{f}}\|\allowbreak(\cos(\theta_{k,k^{\prime}} ^{*}(\gamma_{\mathrm{1v1}}))-\cos(\theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v 1}})))=\eta_{k}-\eta_{k^{\prime}}.$ (65) $$

For the left-hand side:

$$ $\displaystyle\cos(\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}}))-\cos( \theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1}}))$ $\displaystyle=-2\sin\allowbreak(\frac{\theta_{k,k^{\prime}}^{*}(\gamma_{ \mathrm{1v1}})+\theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1}})}{2})\sin \allowbreak(\frac{\theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}})-\theta_{k^{ \prime},k}^{*}(\gamma_{\mathrm{1v1}})}{2})$ $\displaystyle=-2\sin\allowbreak(\frac{\psi}{2})\sin\allowbreak(\frac{\psi}{2}- \theta_{k^{\prime},k}^{*}(\gamma_{\mathrm{1v1}}))$ $\displaystyle=-2\sin\allowbreak(\frac{\psi}{2})\sin\allowbreak(\theta_{k,k^{ \prime}}^{*}(\gamma_{\mathrm{1v1}})-\frac{\psi}{2})$ $\displaystyle=2\sin\allowbreak(\frac{\psi}{2})\sin\allowbreak(\frac{\psi}{2}- \theta_{k,k^{\prime}}^{*}(\gamma_{\mathrm{1v1}}))$ (66) $\displaystyle=2\sin\allowbreak(\frac{\psi}{2})\sin\allowbreak(\frac{\psi}{2} \allowbreak(1-\frac{2}{\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})+1})).$ $$

Let us denote the right-hand side as $g(\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}}))$. We set $\gamma_{+}^{*}>0$ so that it can be approximated near $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})=1$ by $2\gamma_{+}^{*}\log(\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}}))$. Specifically, we set $\gamma_{+}^{*}$ to satisfy:

$$ $\displaystyle g(1)$ $\displaystyle=0=-2\gamma_{+}^{*}\log(1),$ (67) $\displaystyle g^{\prime}(1)$ $\displaystyle=\frac{\psi}{2}\sin\allowbreak(\frac{\psi}{2})=2\gamma_{+}^{*}.$ (68) $$

The solution is $\gamma_{+}^{*}=\frac{\psi}{4}\sin(\frac{\psi}{2})$. Thus, when $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})\sim 1$:

$$ $\displaystyle\eta_{k}-\eta_{k^{\prime}}$ $\displaystyle\sim 2\gamma_{+}^{*}\log\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})$ $\displaystyle=\gamma_{+}^{*}\allowbreak(\log(\|{\bm{\mu}}(\mathcal{S}_{k})\|^{ 2}n_{k}^{\gamma_{\mathrm{1v1}}})-\log(\|{\bm{\mu}}(\mathcal{S}_{k^{\prime}})\| ^{2}n_{k^{\prime}}^{\gamma_{\mathrm{1v1}}}))$ $\displaystyle=\gamma_{+}^{*}\allowbreak(\gamma_{\mathrm{1v1}}\log n_{k}-\gamma _{\mathrm{1v1}}\log n_{k^{\prime}}+2(\log\|{\bm{\mu}}(\mathcal{S}_{k})\|-\log \|{\bm{\mu}}(\mathcal{S}_{k^{\prime}})\|))$ $\displaystyle=\gamma_{+}^{*}\gamma_{\mathrm{1v1}}\allowbreak(\log n_{k}-\log n _{k^{\prime}}).$ (69) $$

From this, we conclude that when $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})\sim 1$ and $\|{\bm{\mu}}(\mathcal{S}_{k})\|=\|{\bm{\mu}}(\mathcal{S}_{k^{\prime}})\|$ for all $k,k^{\prime}\in\mathcal{Y}$, the ALA results in the decision boundaries as 1vs1adjuster. However, under LTR settings, $\tau_{k,k^{\prime}}(\gamma_{\mathrm{1v1}})$ can vary significantly depending on $k$ and $k^{\prime}$, making this approximation less realistic in practice.

## Appendix E Experiments

In this section, we summarize the details of the experimental settings and results that are not fully covered in the main text. Appendix E.1 outlines the detailed experimental settings. Appendix E.2 provides supplementary results for the experiments in Section 5.2, while Appendix E.3 presents additional results for the experiments in Section 5.3 under different conditions.

### E.1 Settings

We describe the detailed training settings in this section. We mainly followed the hyperparameters used in Hasegawa and Sato []. First, we provide the details for experiments on image datasets, and then describe the experiments on tabular data, highlighting the differences.

#### E.1.1 Datasets

Following Cui et al. [] and Liu et al. [], we created long-tailed versions of image datasets.
For tuning the hyperparameters $\gamma_{\mathrm{1v1}},\gamma_{+},\gamma_{\times}$, we used validation datasets. Since CIFAR10 and CIFAR100 do not have validation datasets, we created validation datasets using a portion of the training datasets. Following Liu et al. [], we constructed the validation datasets by extracting only $20$ samples per class from the training datasets and using the remaining samples as the training datasets. For CIFAR100, we set $n_{1}$ to $480$, and for CIFAR10, we set it to $4980$. The imbalance factor $\rho$ was set to $100$. The classes within each dataset were divided into three groups—Many, Medium, and Few—on the basis of the number of training samples $n_{k}$. For CIFAR100-LT and ImageNet-LT, we categorized classes $k$ as Many if they had more than $1000$ training samples ($n_{k}>1000$), Medium if they had between $200$ and $1000$ training samples ($200\leq n_{k}\leq 1000$), and Few otherwise. For CIFAR10-LT, we classified classes as Many if they had more than $100$ samples, Medium if they had between $20$ and $100$ samples, and Few otherwise.

#### E.1.2 Evaluation Metrics

Unless otherwise specified, we used the following hyperparameters with ResNet. We chose stochastic gradient descent with $\text{momentum}=0.9$ as the optimizer and applied a cosine learning rate scheduler [Loshchilov and Hutter, ] to gradually decrease the learning rate from $0.01$ to 0 0. The batch size was set to $64$, and the number of training epochs was $320$. The loss function used was cross-entropy loss, and regularization included a weight decay of $0.005$ [Hanson and Pratt, ] and feature regularization of $0.01$ [Hasegawa and Sato, ]. Although we used an ETF classifier for the linear layer, we did not use Dot-Regression Loss [Yang et al., ], following Hasegawa and Sato []. The optimal $\gamma\in\{\gamma_{\mathrm{1v1}},\gamma_{+},\gamma_{\times}\}$ for LA and 1vs1adjuster were determined using cross-validation on validation datasets, exploring values from $\{0.00,0.05,\ldots,2.00\}$.

Next, we describe the experimental setup for ImageNet-LT. The learning rate was gradually decreased from $0.05$ to 0 0, with the number of training epochs set to $200$. Regularization involved a weight decay of $0.00024$ and a feature regularization of $0.00003$. All other settings were the same as those used for CIFAR100-LT.

For the experiments in Section 5.2, we used the optimal values of $\gamma_{\mathrm{1v1}},\gamma_{+},\gamma_{\times}$ determined by the validation data. For ALA, the value of $\|{\bm{f}}\|$ was calculated by averaging the norm of the class mean features for each class.

The accuracy reported in Section 5.3 represents the mean and standard deviation across five independent experiments, each using different random seeds. The values of $\gamma_{\mathrm{1v1}}$, $\gamma_{\times}$, and the training accuracy mentioned in Section 5.4 correspond to these experiments. All experiments were conducted on a single NVIDIA A100.

#### E.1.3 Tabular Data

Next, we describe the experiments conducted on tabular data. Since tabular data have characteristics that differ significantly from image data, we conducted these experiments to demonstrate that our results can generalize to other modalities beyond images. Apart from the settings described below, the procedure was identical to that used for image data. Following Hasegawa and Sato [], we used the Helena dataset with 100 classes. Since this dataset is not pre-split into validation and test sets, we randomly sampled 20 non-overlapping samples per class for validation and test sets respectively. The distribution of this dataset resembles a long-tailed distribution with $\rho\simeq 40$. For each class, those with more than 500 training samples were categorized as Many, those with $200\leq n_{k}\leq 500$ as Medium, and the rest as Few.

In line with Kadra et al. [], we trained a MLP with sufficient regularization. We used a 9-layer MLP with 512-dimensional hidden layers as the feature map. The model was trained for 400 epochs using AdamW [Loshchilov and Hutter, ]. Regularization methods included a $0.15$ dropout rate [Srivastava et al., ], $0.15$ weight decay, and $0.001$ feature regularization.

### E.2 Decision Boundary Angles

We present the results of the experiments from Section 5.2 conducted with different models and datasets. Figure 4 illustrates the differences in the angles of the decision boundaries of ResNeXt50 trained on CIFAR100-LT, while Figures 5 and 6 display the results for ImageNet-LT and Helena, respectively. In all cases, the decision boundaries adjusted by MLA and 1vs1adjuster tend to be more similar to each other than to those adjusted by ALA.

Figure: Figure 4: Heatmaps showing the difference in angles between the decision boundaries adjusted by each method and those adjusted by 1vs1adjuster of ResNeXt50 trained on CIFAR100-LT.
Refer to caption: extracted/5897552/images/theta_CIFAR100-LT_X.png

Figure: Figure 5: Heatmaps showing the difference in angles between the decision boundaries adjusted by each method and those adjusted by 1vs1adjuster of ResNeXt50 trained on ImageNet-LT.
Refer to caption: extracted/5897552/images/theta_ImageNet-LT.png

Figure: Figure 6: Heatmaps showing the difference in angles between the decision boundaries adjusted by each method and those adjusted by 1vs1adjuster of MLP trained on Helena.
Refer to caption: extracted/5897552/images/theta_Helena.png

### E.3 Test Accuracy

Figure: Figure 7: Average accuracy of MLP trained on Helena and adjusted by different methods.
Refer to caption: extracted/5897552/images/acc_Helena_MLP.png

In this subsection, we first present the error bar plot for the average test accuracy on Helena, which is not shown in Section 5.3, followed by a detailed table of test accuracy of models adjusted by each method.

##### Error Bar

Figure 7 shows the average accuracy of models trained on Helena, adjusted by different methods. Notably, models trained on Helena, similar to those on ImageNet-LT, did not achieve a training accuracy of $100\%$, indicating that NC has not fully occurred (see Table 1). Despite this, the results show that MLA and 1vs1adjuster achieve comparable accuracy, consistent with the experiments on other image datasets.

##### Table

We compare the test accuracy when each method is applied post-hoc to trained models. We refer to the models only trained on the training data, without the application of any post-hoc adjustment methods, as Baseline.
We present two cases for each adjustment method: when the hyperparameter values are set according to the values derived from each theory (0.5 or 1.0), and when the parameters are tuned using validation data (best). The results for CIFAR100-LT and CIFAR10-LT are presented in Tables 6 and 7, respectively. Table 8 reports the accuracy of ResNeXt50 on CIFAR100-LT, while Tables 9 and 10 display the results of ImageNet-LT and Helena, respectively.

**Table 6: Accuracy of ResNet34 adjusted with each method on CIFAR100-LT.**
| Method | Many | Medium | Few | Average |
| --- | --- | --- | --- | --- |
| Baseline | $\mathbf{77.9_{\pm 0.3}}$ | $46.8_{\pm 1.0}$ | $15.3_{\pm 0.3}$ | $47.6_{\pm 0.5}$ |
| ALA ($\gamma_{+}=1.0$) | $72.3_{\pm 0.2}$ | $47.9_{\pm 1.1}$ | $28.3_{\pm 0.9}$ | $50.1_{\pm 0.4}$ |
| ALA (best) | $75.6_{\pm 0.9}$ | $49.2_{\pm 1.0}$ | $25.2_{\pm 2.2}$ | $50.7_{\pm 0.4}$ |
| 1v1 ($\gamma_{\mathrm{1v1}}=0.5$) | $76.4_{\pm 0.3}$ | $\mathbf{51.7_{\pm 0.9}}$ | $24.7_{\pm 0.7}$ | $51.7_{\pm 0.2}$ |
| 1v1 (best) | $74.2_{\pm 1.0}$ | $\mathbf{53.0_{\pm 0.9}}$ | $\mathbf{29.6_{\pm 1.1}}$ | $\mathbf{52.9_{\pm 0.3}}$ |
| MLA ($\gamma_{\times}=0.5$) | $75.6_{\pm 0.3}$ | $\mathbf{52.3_{\pm 0.8}}$ | $27.1_{\pm 0.7}$ | $52.4_{\pm 0.2}$ |
| MLA (best) | $73.2_{\pm 0.8}$ | $\mathbf{52.8_{\pm 0.9}}$ | $\mathbf{30.9_{\pm 1.1}}$ | $\mathbf{53.0_{\pm 0.3}}$ |

**Table 7: Accuracy of ResNet34 adjusted with each method on CIFAR10-LT.**
| Method | Many | Medium | Few | Average |
| --- | --- | --- | --- | --- |
| Baseline | $\mathbf{89.2_{\pm 1.5}}$ | $\mathbf{76.3_{\pm 2.5}}$ | $60.8_{\pm 4.6}$ | $76.8_{\pm 0.8}$ |
| ALA ($\gamma_{+}=1.0$) | $\mathbf{87.2_{\pm 2.5}}$ | $\mathbf{78.5_{\pm 2.9}}$ | $\mathbf{71.7_{\pm 3.9}}$ | $\mathbf{79.9_{\pm 1.0}}$ |
| ALA (best) | $\mathbf{87.7_{\pm 1.2}}$ | $\mathbf{78.2_{\pm 3.0}}$ | $\mathbf{70.5_{\pm 2.7}}$ | $\mathbf{79.7_{\pm 1.1}}$ |
| 1v1 ($\gamma_{\mathrm{1v1}}=0.5$) | $\mathbf{88.0_{\pm 2.2}}$ | $\mathbf{78.6_{\pm 2.7}}$ | $\mathbf{68.9_{\pm 4.2}}$ | $\mathbf{79.5_{\pm 0.8}}$ |
| 1v1 (best) | $\mathbf{87.9_{\pm 1.8}}$ | $\mathbf{79.3_{\pm 4.0}}$ | $\mathbf{69.0_{\pm 2.7}}$ | $\mathbf{79.6_{\pm 1.1}}$ |
| MLA ($\gamma_{\times}=0.5$) | $\mathbf{88.1_{\pm 2.2}}$ | $\mathbf{78.7_{\pm 2.7}}$ | $\mathbf{68.4_{\pm 4.3}}$ | $\mathbf{79.4_{\pm 0.8}}$ |
| MLA (best) | $\mathbf{88.0_{\pm 1.6}}$ | $\mathbf{79.2_{\pm 3.7}}$ | $\mathbf{68.8_{\pm 2.9}}$ | $\mathbf{79.6_{\pm 1.1}}$ |

**Table 8: Accuracy of ResNeXt50 adjusted with each method on Cifar100-LT.**
| Method | Many | Medium | Few | Average |
| --- | --- | --- | --- | --- |
| Baseline | $\mathbf{77.4_{\pm 0.3}}$ | $49.8_{\pm 0.5}$ | $18.2_{\pm 0.4}$ | $49.4_{\pm 0.3}$ |
| ALA ($\gamma_{+}=1.0$) | $73.3_{\pm 0.6}$ | $50.9_{\pm 0.5}$ | $31.0_{\pm 0.4}$ | $52.4_{\pm 0.3}$ |
| ALA (best) | $76.3_{\pm 0.3}$ | $51.9_{\pm 0.4}$ | $26.2_{\pm 0.4}$ | $52.2_{\pm 0.2}$ |
| 1v1 ($\gamma_{\mathrm{1v1}}=0.5$) | $75.6_{\pm 0.3}$ | $\mathbf{53.5_{\pm 0.5}}$ | $27.6_{\pm 0.7}$ | $53.0_{\pm 0.2}$ |
| 1v1 (best) | $70.5_{\pm 0.7}$ | $\mathbf{54.0_{\pm 1.2}}$ | $\mathbf{36.6_{\pm 0.9}}$ | $\mathbf{54.2_{\pm 0.3}}$ |
| MLA ($\gamma_{\times}=0.5$) | $74.5_{\pm 0.3}$ | $\mathbf{53.7_{\pm 0.8}}$ | $30.3_{\pm 0.7}$ | $53.5_{\pm 0.2}$ |
| MLA (best) | $72.9_{\pm 0.5}$ | $\mathbf{53.8_{\pm 1.1}}$ | $33.4_{\pm 0.6}$ | $\mathbf{54.0_{\pm 0.3}}$ |

**Table 9: Accuracy of ResNeXt50 adjusted with each method on ImageNet-LT.**
| Method | Many | Medium | Few | Average |
| --- | --- | --- | --- | --- |
| Baseline | $\mathbf{68.1_{\pm 0.2}}$ | $43.0_{\pm 0.2}$ | $17.0_{\pm 0.5}$ | $49.1_{\pm 0.2}$ |
| ALA ($\gamma_{+}=1.0$) | $65.3_{\pm 0.2}$ | $48.1_{\pm 0.1}$ | $31.2_{\pm 0.7}$ | $\mathbf{52.4_{\pm 0.1}}$ |
| ALA (best) | $63.1_{\pm 0.4}$ | $48.7_{\pm 0.2}$ | $36.7_{\pm 0.9}$ | $\mathbf{52.6_{\pm 0.2}}$ |
| 1v1 ($\gamma_{\mathrm{1v1}}=0.5$) | $48.7_{\pm 0.5}$ | $48.0_{\pm 0.4}$ | $48.4_{\pm 0.6}$ | $48.3_{\pm 0.2}$ |
| 1v1 (best) | $62.8_{\pm 0.4}$ | $\mathbf{49.3_{\pm 0.3}}$ | $34.7_{\pm 0.7}$ | $\mathbf{52.5_{\pm 0.2}}$ |
| MLA ($\gamma_{\times}=0.5$) | $38.9_{\pm 0.7}$ | $44.0_{\pm 0.3}$ | $\mathbf{52.3_{\pm 0.6}}$ | $43.2_{\pm 0.3}$ |
| MLA (best) | $62.4_{\pm 0.4}$ | $\mathbf{49.3_{\pm 0.2}}$ | $36.0_{\pm 0.5}$ | $\mathbf{52.6_{\pm 0.2}}$ |

**Table 10: Accuracy of MLP adjusted with each method on Helena.**
| Method | Many | Medium | Few | Average |
| --- | --- | --- | --- | --- |
| Baseline | $\mathbf{36.1_{\pm 1.3}}$ | $21.6_{\pm 0.6}$ | $17.4_{\pm 1.0}$ | $25.2_{\pm 0.3}$ |
| ALA ($\gamma_{+}=1.0$) | $\mathbf{34.7_{\pm 1.4}}$ | $26.5_{\pm 0.8}$ | $23.8_{\pm 0.3}$ | $28.4_{\pm 0.3}$ |
| ALA (best) | $31.2_{\pm 1.2}$ | $\mathbf{28.8_{\pm 0.6}}$ | $\mathbf{27.4_{\pm 0.3}}$ | $\mathbf{29.2_{\pm 0.4}}$ |
| 1v1 ($\gamma_{\mathrm{1v1}}=0.5$) | $32.9_{\pm 1.0}$ | $\mathbf{29.0_{\pm 1.0}}$ | $24.7_{\pm 0.8}$ | $\mathbf{28.9_{\pm 0.4}}$ |
| 1v1 (best) | $31.5_{\pm 1.2}$ | $\mathbf{29.8_{\pm 1.6}}$ | $25.6_{\pm 0.5}$ | $\mathbf{29.0_{\pm 0.4}}$ |
| MLA ($\gamma_{\times}=0.5$) | $31.1_{\pm 0.9}$ | $\mathbf{30.2_{\pm 1.0}}$ | $26.0_{\pm 0.6}$ | $\mathbf{29.1_{\pm 0.5}}$ |
| MLA (best) | $31.3_{\pm 1.7}$ | $\mathbf{29.8_{\pm 1.8}}$ | $25.8_{\pm 1.0}$ | $\mathbf{29.0_{\pm 0.3}}$ |

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please refer to the weakness section.
soundness: 3
strengths: - This paper presents a theory for optimally adjusting decision boundaries based on NC and links it to the MLA method, providing a strong theoretical explanation for MLA and adding depth to its empirical success.
- The authors conduct a series of experiments on long-tailed datasets to validate the theory and demonstrate the practical utility of MLA.
- The authors offer both theoretical and empirical comparisons between MLA and ALA, clarifying their differences and highlighting the advantages of MLA.
summary: This paper provides a theoretical foundation for the Multiplicative Logit Adjustment (MLA) method used in long-tailed recognition tasks. First, the authors develop a theory for optimally adjusting decision boundaries by leveraging feature spread estimates derived from neural collapse (NC). They then demonstrate that MLA effectively approximates this optimal adjustment method. Experiments conducted on various long-tailed datasets validate the practical applicability of this approximation, showing that MLA performs well under realistic conditions.
weaknesses: - The iNaturalist dataset is a widely used large-scale long-tailed dataset. Conducting experiments on this dataset would be beneficial to examine the behavior of MLA, ALA, and the 1vs1 adjuster in a larger-scale real-world context. Additionally, testing on CIFAR-LT with more extreme imbalance ratios would further evaluate the effectiveness of the proposed method.

- The theoretical framework relies on some strict assumptions that may not always hold in practice, such as the assumption of conditions under which NC occurs, which may not be valid in highly imbalanced real-world datasets. Similarly, the assumption that $\psi \rightarrow \pi/2$ does not hold when $K$ is small.
- There are some typos, such as on line 373, where "the optimal decision boundaries during inference is effected by" should be corrected to "the optimal decision boundaries during inference are affected by".

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: The paper mentions that "MLA has demonstrated significant empirical success," but it does not provide sufficient evidence to support this claim. Could more literature or experimental results be added to demonstrate the current advantages of MLA in long-tailed recognition?

The theoretical comparison between MLA and ALA is addressed in some aspects, but why is there no comparison with other advanced baselines in long-tailed recognition (such as the latest contrastive learning methods or distribution-balanced loss)?
soundness: 2
strengths: The framework that connects MLA with Neural Collapse is novel.  The assumptions and conditions are clearly stated, and the notation is consistent and well-defined.
summary: The paper aims to provide a theoretical justification for Multiplicative Logit Adjustment (MLA) in long-tailed recognition by linking it to Neural Collapse theory. The authors develop a theoretical framework for optimal decision boundary adjustment based on feature spread estimates from Neural Collapse and demonstrate that MLA approximates this optimal method.
weaknesses: 1. **Motivation**:
   The paper fails to establish a compelling motivation for the study. The claim that "MLA has demonstrated significant empirical success" is not sufficiently substantiated. There is no systematic analysis of the current strengths and challenges of MLA in long-tailed recognition.

2. **Theory-Practice Gap**:
   The connection between optimal decision boundary adjustment and actual performance improvements in long-tailed scenarios is weak. While the paper seems to demonstrate the effectiveness of MLA as a close approximation to the 1vs1adjuster from both theoretical and experimental perspectives, and contrasts it with Additive Logit Adjustment (ALA), it does not thoroughly analyze how MLA addresses the specific challenges of long-tailed learning from a theoretical standpoint. Additionally, there is no comparison with state-of-the-art long-tailed baselines or discussion on how MLA could be integrated with them. The experimental section focuses more on hyperparameter tuning for MLA rather than examining its impact on long-tailed learning.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Why did you primarily focus on ResNet models for the image analysis? Were there specific reasons for this choice over other architectures?
2. Why did you create imbalanced versions of balanced datasets instead of using inherently imbalanced datasets? For example, datasets that exhibit natural class imbalances could offer more realistic evaluations.
3. Although the paper focuses on post-hoc LA methods, did you compare the results with loss-function-based approaches? How does MLA's performance compare to other logit adjustment methods?
soundness: 3
strengths: * The problem of class imbalance is clearly motivated, and the investigation into MLA is a valuable contribution to this area of research.
* The mathematical framework is well-developed, offering a solid theoretical foundation for understanding the method.
* The analysis extends beyond image datasets to include other modalities, such as text, enhancing the paper's applicability.
* Extensive experiments are conducted, which reinforce the theoretical claims and provide a comprehensive evaluation of MLA’s performance.
summary: The paper addresses the problem of class imbalance in classification models and analyzes the effectiveness of the Multiplicative Logit Adjustment (MLA) method. The authors propose a theory on optimal decision boundaries based on neural collapse, demonstrating that MLA approximates these optimal boundaries. The paper is supported by experiments across various modalities, providing insights into MLA’s performance under different conditions.
weaknesses: * While the theoretical concepts are accurately communicated, the writing could be improved by breaking up overly long sentences to enhance readability (e.g., lines 098-104).
* The results in Tables 6-10 are intriguing, but more explanation is needed to clarify the implications of "Many," "Medium," and "Few" categories. Additionally, the reasons for the Baseline outperforming others in the "Many" category should be discussed in more depth.
* The descriptions for tables and figures are too brief, making it difficult for readers to grasp the full context of the results. Adding more detailed captions would help in understanding the findings.
* The paper contains numerous formal definitions and formulas, which can disrupt the reading flow, especially for readers who are not deeply familiar with this specific research area.

Meta-review: This paper studies the multiplicative logit adjustment (MLA) method proposed recently for the long-tail recognition (LTR) problem. The paper formally shows that MLA can be seen as an approximation of a theoretically-guided approach based on a neural collapse (NC) based adjusting of the optimal decision boundaries. The theoretical analysis also results in some practical benefits, such as better performance in more realistic LTR settings and hyperparameter tuning.

The paper received generally positive reviews from the reviewers. There were some concerns such as (1) lack of experiments on very large-scale LTR datasets such as iNaturalist (Reviewer Hejv), and (2) concerns about some of the theoretical assumptions (Reviewer Hejv), (3) motivation and theory-practice gap (Reviewer EiUb). There were some additional concerns that the experiments are not strongly demonstrating the effectiveness of MLA but are rather focused more on how it guides hyperparameter tuning

The authors provided a detailed response to these concerns. In the end, while two reviewers leaned towards acceptance with scores of 6, Reviewer EiUb remained a bit cautious with a borderline score of 5.

Considering the reviews, the author rebuttal, the discussion, and my own reading of the paper, my assessment is that the paper does offer a nice understanding/justification of MLA, along with some practical guidelines on how to use it effectively in realistic real-world LTR problems. I therefore recommend the paper for acceptance. At the same time, the authors should incorporate the reviewer feedback in the final version.

Decision: Accept (Poster)