Label Embedding via Low-Coherence Matrices
Authors: Jianxin Zhang
Clayton Scott
Venue: Accepted by TMLR ()

Abstract: Label embedding is a framework for multiclass classification problems where each label is represented by a distinct vector of some fixed dimension, and training involves matching model output to the vector representing the correct label. While label embedding has been successfully applied in extreme classification and zero-shot learning, and offers both computational and statistical advantages, its theoretical foundations remain poorly understood. This work presents an analysis of label embedding in the context of extreme multiclass classification, where the number of classes $C$ is very large. We present an excess risk bound that reveals a trade-off between computational and statistical efficiency, quantified via the coherence of the embedding matrix. We further show that under the Massart noise condition, the statistical penalty for label embedding vanishes with sufficiently low coherence. Our analysis supports an algorithm that is simple, scalable, and easily parallelizable, and experimental results demonstrate its effectiveness in large-scale applications.

Published in Transactions on Machine Learning Research (09/2025)
Label Embedding via Low-Coherence Matrices
Jianxin Zhang
Electrical Engineering and Computer Science University of Michigan
Ann Arbor, MI 48109
jianxinz@umich.en edu Clayton Scott
Electrical Engincering and Computer Science University of Michigan
Ann Arbor, MI 48109 clayscot@umich. edu
Reviewed on OpenReview:
Abstract
Label embedding is framework for multiclass classification problems where each label is rep- resented by distinet vector of some fixed dimension, and training involves matching model output to the vector representing the correct label. While label embedding has been success- fully applied in extreme classification and zero-shot learning, and offers both computational and statistical advantages, its theoretical foundations remain poorly understood. This work presents an analysis of label embedding in the context of extreme multiclass classification, where the number of classes is very large. We present an excess risk bound that reveals trade-off between computational and statistical efficiency, quantified via the coherence of the embedding matrix. We further show that under the Massart noise condition, the statistical penalty for label embedding vanishes with sufficiently low coherence. Our analysis supports an algorithm that is simple, scalable, and easily parallelizable, and experimental results demonstrate its superiority in large-scale applications.
1 Introduction
In classification, the goal to learn from feature-label pairs ((r,, vi)); classifier h - y that accurately maps feature vector æ in the feature space X to its label y in the label space D. For implementation purposes, labels typically represented using the one-hot encoding which, for C-class classification problem, represents the i-th class by the i-th standard basis vector in R.C
Unfortunately, the one-hot encoding of labels is limited in the context of eztreme classification, which refers to multiclass and multilabel classification problems involving thousands of classes or more (Wei et al. 2022). Extreme classification has emerged as an essential research area machine learning, owing to an increasing number of roal-world applications involving massive numbers of classes, such as image recognition (Zhoul et al. 2014), natural language processing (Le and Mikolov] 2014 Jernite et al.) 2017), and recommendation systems (Bhatia et al. 2015 Chang al. 2020). Classification methods based the one-hot encoding often struggle to scale effectively in these scenarios due to the high computational cost and memory requirements associated with handling large label spaces.
To overcome this challenge, the label embedding framework represents each label by a vector of fixed dimension, typically much lower than C, and learns a function that maps feature vector to the vector representing its label. At inference time, the label of a test data point is assigned match the nearest label representative in the embedding space. By employing lower-dimennsonall label space, label embedding overcomes the

---

Published in Transactions on Machine Learning Research (09/2025)
computational challenge posed by large label space. At the same time, there is growing need for efficient and scalable algorithms that can tackle extreme classification problems without compromising on performance
(Prabhu and Varma 2014 Prabhu et al.] 2018 Deng et al. 2018). Successful applications of label embedding
to extreme classification include Yu et al. ); Jain et al. (2019): Bhatia et al. 20 Guo et al. (2019);
Evron et al. 20188: Hsu el al.] (2009). Furthermore, Rodriguez et al. (2018) argues that label embedding can
accelerate the convergence rate and better capture latent relationships between categories.
Despite its widespread use, the theoretical basis of label embedding has not been thoroughly explored. This paper presents new excess risk bound that provides insight into how label embedding algorithms work, and then exploits this insight to identify a simple implementation of label embedding with excellent performance. Specifically, our bound establishes a trade-off between computational efficiency and classification accuracy, quantified in terms of the coherence of the label embedding matrix. Our theory applies to label-ombedding algorithms described by Algorithm [ including various types of embeddings: data- independent emboddings (Weston et al., 2002 Hsu et al., 2009), those anchored in auxiliary information (Akala et al. 2013), and embeddings co-trained with models (Weston et al. 2010). Furthermore, under the multiclass noise condition of Massart and Nédélec (2006), the statistical penalty associated with positive matrix coherence, which results from reducing the dimension of the label space, disappcars.
Mela-Algorithm is not our contribution, but rather a unification of several existing approaches. However, by selecting a label embedding matrix to optimize the tradeoff described by our bound, namely, by choosing a low-coherence embedding matrix, we present instantiations of this meta-algorithm that outperform competing approaches across several benchmark datasets.
2
Related work
While label embedding has also been successfully applied to zero-shot learning (Wang et al. 2019 Akata et al. 2013), we focus here on extreme classification, together with related theoretical contributions.
2.1 Extreme classification
Besides label embedding, existing methods for extreme multiclass classification can be grouped into three main categories: label hierarchy, one-vs-all methods, and other methods.
Label Embedding. LEML (Yu et al. 2014] leverages a low-rank assumption linear models and effectively constrains the output space of models to a low-dimensional space. SLEEC (Bhalia et al. 2015 is local embedding framework that preserves the distance between label vectors. Guo et al. (2019) point out that low-dimensional embodding- basod models could suffer from significant overfitting. Their thcorctical insights inspire a novel regularization technique to alleviate overfitting in such models. WLSTS (Evron el al.) 2018 is an extreme multiclass classification framework based on error correcting output coding, which embeds labels with codes induced by graphs. Hss et al. (2009) use column vectors from a matrix with the restricted isometry property (RIP) to represent labels. Their analysis is primarily tailored to multilabel classification. They deduce bounds for the conditional fz-error, which measures the squared 2-norm difference between the prediction and the label vector - a metric that is not a standard measure of classification error. In contrast, our work analyzes the standard classification error.
Label Hierarchy. Numerous methods such as Parabel (Prabhu et al., 2018). Bonsai (Khandagale et al., 2020), AttentionXML (You et al., 2019), lightXML (Jiang et al. (021), XR-Transformer (Zhang et al.) [202]). ), X-Transformer (Wei et al.) 2019), XR-Linear Yuu et al.) 2022), and ELIAS (Gupta et al., 2022) partition the label spaces into clusters. This is typically achieved by performing k-means clustering on the feature space. The training process involves training cluster-level model to assign a cluster to a feature vector, followed by training a label-level model to assign labels within the cluster.
One-vs-all methods. One-vs-all (OVA) algorithms address extreme classification problems with C' labels by modeling them as C independent binary classification problems. For each label, a classifier is trained to predict its presence. DiSMEC (Babbar and Schölkopf 2017) introduces a large-scale distributed framework train linear OVA models, albeit. at expensive computational cost. ProXMT. (Babbar and Schölkopf 2019
2

---

Published in Transactions on Machine Learning Research (09/2025)
Meta-Algoritae 1 Label Embeddingg.
1: Input: dataset D = {(),, embedding matrix G, multi-output regression algorithm A, the decoder function 3 from the embedding space to the label space.
2: Form the regression dataset D, = {(2,,9u))e gym)
Train regression model f with on Dr. Return: 3 o
mitigates the impact of data scarcity with adversarial perturbations. SLICE (Jain et al., 2019 accelerates
negative sampling based on generative model approximation. PD-Sparse (Yen et al.) 2016 and PPD-Sparse Yen et al. 2017a] propose optimization algorithms to exploit sparsity assumption on labels and feature
vectors.
Other methods. Beyond the above categories, DeepXML (Dahiya et al. 2021 ) uses negative sampling procodure that shortlists Ollog C") relevant labels during training and prediction. VM (Choromanska and Langford 2013) constructs trees with Olog C`) depth that have leaves with low label entropy. Based on the standard random forest training algorithm, FastXMM. (Prabhu and Varmal 2014) proposes to directly optimize the Discounted Cumulative Gain reduce the training cost. AnnexML (Tagami 2017) constructs k-nearest neighbor graph of the label vectors and attempts to reproduce the graph structure in lower-dimension feature space.
2.2 Excess risk bounds
Our thcoretical contributions are expressed as excess risk bounds, which quantify how the excess risk associated to a surrogate loss relates to the excess risk for the 0-1 loss. Excess risk bounds for classification were developed by Zhang 2004); Bartlett et al. 20066;; Steinwart (2007) and subsequently developed and extended by several authors.
Ramaswamy and Agarwal 20122) shows that one needs to minimize a convex surrogate loss defined on at least a C-1 dimension space to achieve consistency for the standard C-class classification problem, i.e., any convex surrogate loss function operating on dimension less than C - inevitably suffers an irreducible error. Complementing this, Avila Pires et al. (2013) validates the consistency of simplez encoding (Mroueh et al. 2012), a variant of label embedding in a C-1 dimensional space, and introduces an excess risk bound. Previous excess risk bounds have been developed for consistent loss functions. contrast, drawing from (Steinwart] 2007), we establish a novel excess risk bound for the label embedding framework, which admits irreducible error and is inherently inconsistent. This error diminishes as the coherence of the embedding matrix decreases and ultimately vanishes under Massart's noise condition (Massart and Nédélec 2006); leading to excess risk bound of the conventional form.
From a different perspective, Ramaswamy et al (2018) put forth a novel surrogate loss function for multiclass classification with an abstain option. This abstain option enables the classificr to opt-out from making predictions at certain cost. Remarkably, their proposed methods not only demonstrate consistency but also effectively reduce the multiclass problems [log C1 binary classification problems by encoding the classes with their binary representations. In particular, the region in X that causes the irreducible error in our excess risk bound is abstained from in Ramaswamy et al. (0018) to achieve lossless dimension reduction in the abstention setting.
3 Label embedding by low-coherence matrices
Let X' denote the feature space and y' = (1....,Cy C} denote the label space where C E N. Let (X,Y) be random variables in X' x y, and let be the probability measure that governs (X,Y). We use Px to denote the marginal distribution of on X.
We first introduce the definitions of matrix coherence in Section 3.1 followed by the notations and problem statement in Section 3.2 and then present the associated algorithm in Section 3.3 The excess risk bound and
3

---

Published in Transactions on Machine Learning Research (09/2025)
Table 1: Frequently used symbols in Section 3
Symbol Description
Symbol
Description
Embedding matrix
X'
Feature space
y
Label space
Probability mcasure on x y
Px
Marginal distribution of P on X
Loi
0-1 loss function
ga
Squared loss with embedding G RE,P
Risk of C under P
Bayes risk for L under P
7(x))
Class posterior probabilities
d(.)
Difference between top two posteriors
A
Coherence of G
g
Decoder from embedding to label
LG
(p = Lo1 (pC())
its interpretation are presented in Section 3.4
Finally, we introduce the condition for lossless label embodding Frequently used notations appear in Table I
in Section 3.5
3.1 Matrix coherence
Our theory relies on the notion of the coherence of a matrix A E C"xc, which is the maximum magnitude of the dot products between distinct columns.
Definition 1. Let {a be the columns of the matrix A e C where |aلl|2 = for all j. The coherence of A is X maxigw)scc a-)l-
If n 2 C, À is 0 when the columns of A are orthonormal. When < C, however, the coherence must be positive. Indeed, Welch (1974) showed that for A E Cax and S SC A2
C-n
MC--IJ
There are a number known constructions of low-coherence matrices when n C. A primary class of property [Johnson and Lindenstraus 1984 For example, Rademacher matrix has entries that are sampled i.i.d. from
examples is the random matrices with columns of unit norms that satisfy the Johnson--inndessree
uniform distribution on
J. With high probability, a Rademacher random matrix of shape C'
log C for some constant co (Achlioptas) 2001 While random matricos be easily obtained and have a low coherence in general, they require explicit storage (Nelson and Temlyakov practical problems by some carefully crafted deterministic matrices (Naidu 2011 and can be outperformed Numerous deterministic constructions of low-coherence matrices have been
achieves coherence X
et al. 2016 Liu and Jia 2020).
2011 Yu 2011 Li et al. 2012 Xu 2011: Naidu et al. 2016). In partieular, achieve À R C- with R: vC, which avoids explicit storage of the matrix and can achieve a lower coherence in practice. There are also algorithms that directly optimize matrices for a smaller coherence (Wei et al. 2020
proposed (Nelson and Temlyakov
Nelson and Temlyakov (2011) propose deterministic construction that
Abolghasemi et al. 2010
Obermeier and Martinez-Lorenzo
2017
et al. 2013 Lu et al. 2018).
3.2 Problem statement
To define the standard classification setting, denote the 0-1 loss Lai : x3 - + by Lo1(0))) = Ayze, where 1 is the indicator function. The risk of a classifier is BEL (N(X), Y)], and the goal of classification is to learn a classifier from training data whose risk is as close as possible to the Bayes risk minsem EiLo1 (h(X), where = (eeasurable h y).
We now describe an approach to classification based on label embedding, which represents labels vectors in < C dimensional complex space C". In particular, let G be x C matrix with unit norm columns, called the embedding matrir, having coherence G 1. The columns of G are denoted by 91, .u.92........ IC, and the column g, is used to embed the i-th label.
Given an embedding matrix G, the original C'-lass classification problem may be reduced to a multi-output regression problem, where the classification instance (x, y) translates to the regression instance (x. 9y). Given training data {(x,, })) for classification, we create training data {(r,, for regression, and apply any algorithm for multi-output regression to learn regression function X C".
4

---

Published in Transactions on Machine Learning Research (09/2025)
At test time, given test point 2, a label y is obtained by taking the nearest neighbor to f(x) among the columns of G. In particular, define the decoding function 8 C + y/ (p) min arg min - 9: gill2): where p represents the output of regression model. (Since the arg min is potentially set-valued, the min breaks tics in favor of the label with the smallest index.) Then the label assigned to x is (f((x))
(arg
Thus, label embedding gives rise to classifiers of the form 3 ff where f E F== fall measurable f -+ Fortunately, according the following result, no expressiveness is lost by considering classifiers of this form.
Proposition 2. Recall the decoding function 38 (p) minfarg mingeyllp gill2); the regression models F {all measurable J X +x } and the classification models H (all measurable h X' - }}. Then 8 oF H.
While the composition 8 o F preserves expressiveness, choosing low-dimensional embedding in conjunction with a convex surrogate can introduce irreducible crror (Ramaswamy and Agarwal 2012).
This and other results are proved in an appendix. follows that minser Ep Loi (36 (J(X)), Y)] is the Bayes risk for classification as defined earlier. This allows us to focus our attention on learning f X + C", Toward that end, we now formalize notions of loss and risk for the task of learning a multi-output function f for multiclass classification via label embedding.
Definition 3. A loss function for label embedding function L: C" yy+R. Given such loss function, define the C-risk of f with distribution P to be Re,p :F -R,, R, Re,P(f) Ep [4(f(X), Y)] and the L-Bayes risk to be Rg JEF Rc,
Using this notation, the target loss for learning with fixed embedding matrix G is the loss function I,C: C x x defined by T, y) == Loi (8C v). By Prop. [ the 7.G-risk of f is the usual classification risk of the associated classifier h = 8 f. and the La-Bayes risk is the Bayes risk of the original classification problem. The goal is to find a pair (f. G) that minimizes Rya (f), or in other words, a pair (f. that makes the excess targel risk Ry - Rie, as small as possible.
While the larget loss I defines the learning goal, it is not practical as training objective because of its discrete nature. Therefore, for learning purposes, Hsu et al. (2009); Akata et al. (2013) Yu et al. (2014) suggest a surrogate loss, namely, the squared distance between f(x) and Py- More precisely, for a given embedding matrix G, define n x + R as (p. := -1pp 1 This surrogate allows to learn f by applying existing multi-output regression algorithms as we describe next. Thus, the label embodding lcarning problem is to learn f with small surrogate excess risk. Our subsequent analysis will connect Rr,,, Ri to Ro - Rio,p.
3.3 Learning algorithms
Learning algorithms for classification via label embedding, as described thus far, can be summarized by a conceptually simple meta-algorithm, depicted in Meta-Algorithm | This meta-algorithm should not be
considered novel as its essential ingredients have been previously introduced Akata et al. (2013); Rodríguez/
et al. 20018). and several existing algorithms can be seen as instances (Hsu al.) 2009 Yu et al. 2014 Bhatia
et al.
2015 Evron et al. 2018 Akata al. 2013).
The meta-algorithm takes as input training dataset ((r,,))))= an embedding matrix G = [g), 92. ... ,c], and an algorithm A for multi-output regression. It forms the multi-output regression dataset {(x, Py. ) ) and applies A to produce a function f. The output the classifier g o s.
For example, the regression algorithm can be specified by selecting a model class Fo and a surrogate loss f and learning f by empirical risk minimization:
min SEFo
(f(a))
In our experiments we select Fo be a neural network with nodes in the output layer, and go be the squared error loss mentioned previously, the same surrogate analyzed in the next section.
5

---

Published in Transactions on Machine Learning Research (09/2025)
As remark, we have treated G as fixed imput to the meta-algorithm, but it can also be trained jointly with f. Our analysis is independent of model training, and thus applies to this case as well.
In the next section we present theory that supports selecting G with low coherence, which has not previously been examined in the label embedding literature.
3.4 Excess risk bound
We present an excess risk bound, which relates the excess surrogale risk to the excess larget risk. This bound justifies the use of the squared error surrogate, and also reveals a trade-off between the reduction in dimensionality (as reflected by X9) and the potential penalty in accuracy.
To state the bound, define the class posterior 77())
where n1(x)) Pr|x=x (1). Define d(x)) max; (x) maXigarg ny(m) (z(2), which is measure of "margin" at æ. We discuss this quantity further after the main result, which we now state.
Theorem 4. Consider an embedding matric G with unit norm columns 91, 92..... .9 and coherence G m Kaggs Recall R1 and Reo ,p represent risks as defined in Desonilion with R R and Rio, r being the corresponding Bayes risks. Then for all f E F,
{ 2x
RL Ria,p S
inf r> 22C 141G
1 X Px(d(X)<
4 12G
< Px(d(x)<<))Rps <R)( Rig,p)
V
(1 2072
4 4-21G
-Rjo,)
(r(1 + ((1+19)-0) - 2XG
As mentioned earlier, the goal of learning is to minimize the excess larget risk RL),p()) Rio,p Ra, The theorem shows that this goal can be achieved up to the first (irreducible) term by minimizing the excess surrogate risk Ryo,p(f) Rija The excess surrogate risk can be driven to zero by any consistent algorithm for multi-oulput. regression with squared error loss. We provide a formal definition of consistency and illustrate it with examples of both consistent and inconsistent loss functions in the appendix.
The quantity d(x)) can be viewed as mcasure of noise (inherent the joint distribution of (X,Y) at a point x. While max; (a))) represents the probability of the most likely label occurring, maxigarg max, (y) (x(r)) represents the probability of the second most likely label occurring. A large d(x) implies that arg max, m) (x) is, with high confidence, the correct prediction æ. In contrast, if d(z) is small, our confidence in predicting arg max, 1/: (1:) is reduced, as the second most likely label has similar probability of being correct.
As pointed out by Ramaswany and Agarwal 2012), any convex surrogate loss function operating a dimension less than C' - 1 inevitably suffers an irreducible error. In the present setting, this irreducible error is manifested in the first term, which depends on the coherence G of the embedding matrix. Given a classification problem with C' classes, a larger embedding dimension n will lead to a smaller coherence 21a
xo making d(x)= > 14x0 on a larger region in X' at the cost of increasing computational complexity. On 21
the other hand, by choosing a smaller n, d(x) < T+x0 on a larger region in X, increasing the first term in Theorem 4 This interpretation highlights the balance between the benefits of dimensionality reduction and the potential impact on prediction accuracy, as a function of the coherence of the embedding matrix, XO, and the noisiness measure, d(r).
3.5 Improvement under low noise
While Theorem f holds universally (for all distributions P), by considering a specific subset of distributions, we can derive a more conventional form of the excess risk bound. As a direct consequence of Theorem 4 under the multiclass extension of the Massart noise condition Massart and Nédélec (006),, which requires d(X) > with probability 1 for some e, the first and second terms in Theorem vanish. In this case, we
6

---

Published in Transactions on Machine Learning Research (09/2025)
recover conventional excess risk bound, where R, Ri tends to 0 with Ryo, ((f) Rgo, We now formalize this.
Definition 5 (Multiclass Massart Noise Condition). The distribution P on X x y is said to satisfy the Multiclass Massart Noise Condition if and only if 3e > 0 such that (x(d(X) 2 c) =1
Corollary 6. Consider the same setup in Theorem and assume P satisfies the Multiclass Massart Noise eeainfd then for all E
Condition. If A E (0, 2-ess in
4 4- 21G
((1 XG) ess inf 2X (Rea Rew, p)
- - S
where essinf is the essential infimum of d, ess supfa R Px(d(X) <a) = 00.
For the special case where all labels are deterministic, we have essinf d(x) for all x, leading the simplified bound
Re (i,0) S 2 (1 2aya (Reo (() - Rig,
This obsorvation implics that for deterministic labels, any embodding matrix with coherence less than ensures consistency. Furthermore, smaller coherence means faster convergence.
4 Experiments
Table 2:
Summary of the dalasets used in the experiments. Nuain is the number of training data points, Nest the number test data points, the number features, and C the number of classes.
Dataset LSHTC1
Nuaai
Niest
D
C
83805
5000
328282
12046
DMOZ
335068
38340
561127
11879
ODP
975936
493014
493014
103361
In this section, we present an experimental evaluation of our proposed method, LOCOLE (LOw COherence Label Embedding), for extreme multiclass classification. LOCOLE is an instance Meta-Algorithm 1, as we explain below.
4.1 Experiment setup
We conduct experiments on three large-scale datasets, DMOZ [Partalas et al. 2015 LSHTC1 (Partalas et al. 2015), and ODP (Bennett and Nguyen 2009). which are extensively used for benchmarking extreme classification algorithms. The details of these datasets provided in Table 2 with DMOZ and LSHTCI
available from (Yen et al.] 2016 and ODP from (Medini et. al. 2019).
We apply LOCOLE where the multi-output regression algorithm is to train multilayer perceptron with n output layer nodes using the surrogate loss g² This is implemented using PyTorch, with 2-layer fully connected neural network used for the LSHTC1 and DMOZ datasets and a 4-layer fully connected neural network for the ODP dataset. The hyperparameters are tuned on a held-out dataset.
We experiment with the following types of embedding matrices:
Rademacher: entries sampled i.i.d. from a uniform distribution on Va - -
Gaussian: entries sampled i.i.d. from N/O, )) Columns are normalized to have unit norm.
C-Gaussian: the real and imaginary parts of each entry are sampled i.i.d. from N(0, 2.). Each
column is normalized to have unit
https::/ppoole.ccatt caail. htt.a//aa......eeea/aa/aaa//aaaa

---

Published in Transactions on Machine Learning Research (09/2025)
LaHTC1
DMOZ
ODP
0.45
0.25
0.15
0.15
Colserence
Coherence
Colsereeee
Gaussian
C-Gaussian
Rademacher
Nelson
Cross Entropy WLSTS
Squared Loss
Annex ML
Parabel
PD-Sparse
PPD-sparse
Figure These plots reveal an inverse correlation between embedding matrix coherence and classification accuracy across diffcrent datasets, with coherence the horizontal axis and accuracy the vertical. Non-LOCOLE methods are plotted as horizontal lines because they do not depend on the embedding dimensionality.
Nelson (Nelson and Temlyakov 2011]: :: a deterministic construction of low-cohcrence complex matrices which n must prime. If r an integer, > a prime number, and n" 2 C, then the coherence of the constructed matrix is most r-1
We choose in experiments.
vn
We compare LOCOLE against the following stato-of-tho-art methods:
PD-Sparsc
Yen et al.
2016): an efficient solver designed exploit the sparsity in extreme classifica-
lion.
PPD-Sparse Yen et al.
201 7al: a multi-process extension of PD-Sparse Yen et al. 2016
Parabel Prabhu et al.
2018
tree-based method which builds label-hicrarchy.
AnnexML Tagami 2017): :: a method which constructs a k-ncarest noighbor graph of the label vectors
and attempls to reproduce the graph structure from a lower-dimension feature space.
WLSTS (Evron et al. 2018:: method based on error correcting output coding which embeds labels by codes induced by graphs.
MLP (CE) Standard multilayer perceptron classifier with cross-entropy loss.
MLP (SE): Standard multilayer perceptron classifier with squared error loss.
For these methods,
the hyperparameters suggested by their papers accompanying code.
While there are numerous label embedding algorithms (Hsu et al. 2009 Yu et al. 2014 Bhatia et al. 2015 Evron et. al. 2018 Akata el al. 2013) which could be seen as specific subsets or instances of Meta-Algorithm our comparisons will not include all of them. The approach in AAkata et al. (2013) not tailored for extreme classification and requires auxiliary information construct the embedding matricos. On the other hand,
methods like Yu (2014): Bhatia al. (2015); Hsu et al. (2009) have been outperformed significantly by
the current sate-of-theeart algorithms shown in prior work Yeen et al. 2016 Bengio et. al. 2010
8

---

Distributed Published in Transactions on Machine Learning Research (09/2025)
Table 3: Accuracy on Various Datasets. RRM denotes Rademacher Random Matrices, GRM stands for Gaussian Random Matrices, and CGRM stands for Complex Gaussian Random Matrices. Methods without an embedding dimension ('-Dim') are LOCOLLOOE methods. We stop training when the training time reaches 50 hours and indicate this in the table.
LSHTC1
DMOZ
ODP
Method(-Diin
Ace.(Mean (
Method
Method(-Dime
Acc.(Mean
GRM 32
18.71 + 0.22%
GRM 32
38.66 0.18%
GRM 256
17.62 + 0.07%
GRM 64
24.64 = 0.23%
GRM 64
44.16 0.01%
GRM 512
19.35 0.04%
GRM-128
28.26 0.19%
GRM-128
46.76 0.05%
GRM-1024
20.77 0.03%
GRM-256
29.97 0.16%
GRM-256
47.58 0.12%
GRM-2045
21.81 = 0.07%
GRM-512
30.61 + 0.22%
GRM-512
47.92 + 0.07%
GRM-4096
22.20 + 0.04%
CGRM 32
24.77 = 0.31%
CGRM 32
44.11 + 0.04%
CGRM 256
19.39 = 0.07%
CGRM-64
28.42 + 0.22%
CGRM-64
46.78 + 0.07%
CGRM-512
20.74 0.08%
CGRM-128
29.97 + 0.21%
CGRM-125 128
47.51 0.09%
CGRM-1024
21.78 + 0.04%
CGRM-256
30.58 + 0.13%
CGRM 256
47.84 0.06%
CGRM
22.14 0.06%
CGRM 512
30.98 + 0.14%
CGRM 512
47.90
0.08%
CGRM 4096
RRM-32
18.66 0.20%
RRM-32
38.41 0.17%
RRM-256
RRM-64
24.77 + 0.17%
RRM-64
44.15 0.05%
RRM-512
19.36 0.04%
RRM-128
28.30 + 0.27%
RRM-128
46.60 +.04%%
RRM-1024
0.05%
RRM-256
30.06 0.21%
RRM-256
47.67 + 0.09%
RRM-2048
21.81 + 0.06%
RRM-512
30.66 + 0.22%
RRM-512
47.82 0.06%
RRM-4096
0.08%
Nelson- 113
29.66 = 0.12%
Nelson-113
47.57 + 0.06%
Nelson-331
0.06%
Nelson- 127
29.71 0.13%
Nelson-
47.71 0.04%
Nelson-509
20.86 0.09%
Nelson- 251
30.50 + 0.16%
Nelson 251
48.01 0.04%
Nelson-
21.91 = 0.06%
Nelson-500
31.08 0.15%
Nelson-508
48.02 0.06%
Nelson-2033
22.30 + 0.06%
MLP (CE)
26.30 = 0.36%
MLP (CE)
46.71 = 0.06%
MLP (CE)
13.99 = 0.11%
MT.P (SF)
28.03 + 0.17%
ML.P (SF)
38.38 + 0.14%
MLP (SE)
18.64 + 0.02%
Annex ML
29.06 + 0.35%
Annex ML
39.82 + 0.14%
Annex ML
21.61 + 0.04%
Parabel
22.24 + 0.00%
Parabel
38.56 + 0.00%
Parabel
17.09 + 0.00%
WLSTS
16.52 + 1.43%
WLSTS
13.60 1.49%
WLSTS
Train > 50 hrs
PDSparse
22.04 0.06%
PDSparse
39.76 0.03%
PDSparse
Train 50 hrs
PPDSparse
22.60 + 0.11%
PPDSparse
39.30 + 0.07%
PPDSparse
13.66 + 0.05%
Table 4: Accuracy and training time across methods.
See Section 4.3 for details.
Dataset
Metric
Single Node
PD-Sparse
LOCOLE
PPD-Sparse
LOCOLE
LSHTC1
Accuracy
22.04%
23.42%
22.60%
23.38%
Training Time
230s
55s
135s
14s
DMOZ
Accuracy
39.76%
41.09%
39.30%
40.57%
Training Time
820s
254s
656s
68s
ODP
Accuracy
N/A
15.11%
13.66%
15.06%
Training Time
50 hrs
2045s
668s
350s
While our theoretical framework is adaptable to any form of embedding, whether trained, fixed, or derived from auxiliary information, we focus on fixed emboddings in our empirical studies. This choice stems from the absence of standardized widely accepted methodology for jointly training the embedding function and the classifier. Although heuristic approaches exist, concerned that they may introduce confounding

---

Published in Transactions on Machine Learning Research (09/2025)
factors, complicating empirical interpretation. By centering on fixed embeddings, we ensure controlled evaluation, minimizing such confounding factors and emphasixing the role of coherence of the embeddings.
All neural network training is performed on a single NVIDIA A40 GPU with 48GB RAM. We explore different embedding dimensions and provide figures showing the relationship between the coherence of G and the accuracy. Full experimental details are presented in section in the appendix.
4.2 Experimental results
The experimental results in Table 3 highlight the superior performance of our proposed method across various datasets. In Table 3. the column Method (-Dim) denotes the method or embedding type along with its dimension, while the Acc. (Mean = Std) column presents the mean and standard deviation of accuracy over 5 randomized repetitions. Methods without embedding dimension (-Dim) are non-LOCOLE methods, which are unaffected by the embedding dimension. We highlight the best-performing method for each dataset. For each embedding method, there is a clear trend of increasing accuracy with larger embedding dimension. Ultimately, every embedding type outperforms all non-LOCOLE methods as the embedding dimension increases, with the Nelson embedding at dimension 509 achicving the highost accuracics across all datascts. We stop the training when the training time reaches 50 hours and indicate this in the lable.
We plot the accuracies as the coherence of the embedding matrix decreases in Figure ! for the LSHTCI, DMOZ, and ODP datasets. Alongside, we include several baselines for comparison. Figure I demonstrates negative correlation between the coherence of the embedding matrix and the accuracy, confirming our theoretical analysis. We include plots of coherence vs precision and recall in Section B of the appendix, along with low-dinensional projections of the embedding vectors.
4.3 Computational advantage
PD-Sparse (Yen et al. 2016) and PPD-Sparse Yen et al. 2017bp are among the most computationally efficient methods for training for extreme classification, to the best of our knowledge. PD-Sparse and PPD-Sparse both efficiently fit a linear model for classification with a multiclass hinge loss and elastic net regularization, which is regularization with both é, and f2 penalties. For comparison, we apply LOCOLE using the Rademacher embedding to elastic net-regularized (Zou and Hastie 2005) linear regression with go loss. To compare the computational efficiency, we set the embedding dimension to 360. In our distributed implementation (multi-output linear regression can be trivially parallelized by solving multiple scalar-output linear regressions), each node independently solves a subset of elastic net linear regressions with scalar output, effectively spreading out the computation. In Table 4 we compare LOCOLE with Rademacher embedding with PD-sparse and PPD-sparsc. LOCOLE clearly outperforms PD-sparse and PPD-sparse in both runtime and accuracy. We train the PD-Sparse method and Single-Nodk Node LOCOLE on Intel Xeon Gold 6154 processors, equipped with 36 cores and 180GB of memory. The distributed LOCOLE and the PPD-Sparse method also implemented in distributed fashion are trained across 10 CPU nodes, harnessing 360 cores and 1.8TB of memory in total.
5 Conclusion and future work
We provide theoretical analysis for label embodding mothods in the context of extreme multiclass classification. Our analysis confers a deeper understanding of the tradeoffs between dimensionality reduction and accuracy. We derive an excess risk bound that quantifies this tradeoff in terms of the coherence of the embedding matrix, and show that the statistical penalty for label embedding vanishes under the multiclass Massart condition. Through extensive experiments, we demonstrated that label embedding with low-coherence matrices outperforms existing techniques in both accuracy and runtime.
While our analysis focuses on excess risk, the reduction of classification to regression mcans that existing generalization error bounds (for multi-output regression with squared error loss) can be applied to analyze the generalization error in our context. For example, Reeve and Kabán (2020) show that the generalization
10

---

Published in Transactions on Machine Learning Research (09/2025)
error grows with the dimension of the output space. This suggests that smaller embedding dimension leads to tighter control of the generalization error.
Building on out theoretical framework, future work may consider extensions to multilabel classification, online learning, zero-shot learning, and learning with rejection.
6 Limitations
Lossless label embedding relies on Massart's noise condition. Although Massart's condition is well-recognized assumption in learning theory, it important to note that it remains a theoretical construct that cannot directly verified in most practical scenarios. This assumption facilitates thcoretical analysis but may not always reflect real-world data distributions.
11

---

Published in Transactions on Machine Learning Research (09/2025)
References
Abolghasemi, V., Ferdowsi, S., Makkiabadi, B., and Sanci, S. (2010). On optimization of the mcasurement matrix for compressive sensing, In 2010 18th Europenn Signal Processing Conference, pages 427 431.
Achlioptas, D. (2001). Database-friendly random projections. In Proceedings of the Twentieth ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems, PODS '01, page 274-20 281, New York, NY, USA. Association for Computing Machinery.
Akata, Z., Perronnin, F., Harchaoui, Z., and Schmid, C. (2013). Label-embedding for attribute-bascd classification. In Proceedings of the IEEE Conference on Computer Vision and Pullern Recognition (CVPR).
Babbar, R. and Schölkopf, B. (2017). DiSMEC: Distributed Sparse Machines for Extreme Multi-Tabel Classification. In Proceedings of the Tenth ACM International Comference on Web Search and Data Mining, WSDM '17, page 721 119, New York, NY, USA. Association for Computing Machinery.
Babbar, R. and Schölkopf, B. (2019). Data scarcity, robustness and extreme multi-label classification. Machine Learning, 108.
Bartlett, P. L.,, Jordan, M. L., and McAuliffe, J. D. (2006). Convexity, classification, and risk bounds. Journal of the American Statistical Association, (077)))1388-16
Bengio, S., Weston, J., and Grangier, D. (2010). Label embedding trees for large multi-class tasks. In Lafferty, J., Williams, C., Taylor, J., Zemel, R., and Culotta, A., editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc.
Bennett, P. N. and Nguyen, N. (2009). Refined experts: improving classification in large taxonomies, Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '09, page 11-18, New York, NY, USA. Association for Computing Machinery.
Bhatia, K., Jain, H., Kar, P., Varma, M., and Jain, P. (2015). Sparse Local Embeddings for Extreme Multi-label Classification. In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc.
Chang, W.-C., Yu, H.-F., Zhong, K., Yang, Y., and Dhillon, I. S. (2020). Taming pretrained transformers for extreme multi-label text classification. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 3163-3171
Choromanska, A. E. and Langford, J. (2015). Logarithmic Time Online Multiclass prediction. In Cortes, C.,, Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R.,, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc.
Dahiya, K., Saini, D., Mittal, A., Dave, K., Jain, H., Agarwal, S., and Varma, M. (2021). DeepXML: A deep extreme multi-Label lcarning framework applied to short text documents. In ACM International Conference on Web Search and Dala Mining.
Deng, H., Han, J., Zhao, Z., and Liu, H. (2018). Dual principal component pursuit: Improved analysis and efficient algorithms. In Advances in Neural Information Processing Systems, pages 1514-1524.
Evron, 1., Moroshko, E., and Crammer, K. (2018). Efficient Loss-Based Decoding Graphs for Extreme Classification. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa- Bianchi, N., and Garnett, R., editiors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc.
Guo, C., Mousavi, A., WU, X., Holtmann-Rice, D. N., Kale, S., Reddi, S., and Kumar, S. (2019). Breaking the Glass Ceiling for Embedding-Baate Based Classifiers for Large Output Spaces. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché- Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
12

---

Published in Transactions on Machine Learning Research (09/2025)
Gupta, N., Chen, P., Yu, H.-F.,, Hsich, C.-J., and Dhillon, I. (2022). ELIAS: End-to-Ena Learning to Index and Search in Large Output Spaces. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems, volume 35, pages 19798 19809. Curran Associates, Inc.
Hsu, D., Kakade, S. M., Langford, J., and Zhang, T. (2009). Multi-Label Prediction via Compressed Sensing. In Proceedings of the 22nd International Conference on Newral Information Processing Systems, NIPS'09, page 772-780, Red Hook, NY, USA. Curran Associates Inc.
Jain, H., Balasubramanian, V., Chunduri, B., and Varma, M. (2019). Slice: Scalable Linear Extreme Classifiers trained on 100 Million Labels for Related Searches. In WSDM '19, February 1 11-15, 2019, Melbourne, VIC, Australia. ACM. Best Paper Award at WSDM '19.
Jernite, Y., Choromanska, A., and Sontag, D. (2017). Simultancous Learning of Trees and Representations for Extreme Classification and Density Estimation. In Precup, D. and Teh, Y. W., editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning PMLR.
Research, pages
Jiang, T., Wang, D., Sun, L.., Yang, H., Zhao, 7., and Zhuang, F. (2021). LightXMT:: Transformer with Dynamic Negative Sampling for Perfo-mero Extreme Multi-label Text Classification. Proceedings of the AAAI Conference on Artificial Intelligence, 3599)7987777994.
Johnson, W. B. and Lindenstraus, J. (1984). Extensions of Lipschitz mappings into Hilbert space. Contempo- rory mathematics, 26:189-206:
Khandagale, S., Xiao, H., and Babbar, R. (2020). Bonsai: Diverse and Shallow Trees for Extreme Multi-Label Classification. Mach. Learn., 109(11):2099- 2119.
Le, Q. and Mikolov, T. (2014). Distributed represenlations of sentences and documents. In International conference on machine learning, pages 1188 1196. PMLR.
Li, G., Zhu, Z., Yang, D., Chang, L., and Bai, H. (2013). On projection matrix optimization for compressive sensing systems. IEEE Transactions on Signal Processing, 61(11):2887-289)
Li, S., Gao, F., Ge, G., and Zhang, S. (2012). Deterministic construction of compressed sensing matrices via algebraic curves. IEEE Transactions Information Theory, 58(8):5035-5)) -0415-5011.
Liu, X. and Jia, (2020). Deterministic construction of compressed sensing matrices via vector spaces over finite fields. IEEE Access, 8:203301 203308.
Lu, C., Li, H., and Lin, Z. (2018). Optimized projections for compressed sensing via direct mutual coherence minimization. Signal Processing, 151:45 55.
Massart, P. and Nédélec, E. (2006). Risk Bounds for Statistical Learning. The Annals of Stotistics, 34(5):2326- 2366.
Medini, T. K. R., Huang, Q., Wang, Y., Mohan, V., and Shrivastava, A. (2019). Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products. In Wallach, H., Larochelle, H., Beygelzimer, A., d' Alché-Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
Mroueh, Y., Poggio, T., Rosasco, L., and Slotine, J.-j. (2012). Multiclass learning with simplex coding, In Percira, F., Burges, C., Bottou, L., and Weinberger, K., editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc.
Naidu, R. R., Jampana, P., and Sastry, C. S. (2016). Deterministic compressed sensing matrices: Construction via euler squares and applications. IEEE Transactions on Signal Processing, 64(14):3566-36) 3375.
Nelson, and Temlyakov, V. (2011). On the size of incoherent systems. Journal of Approzimation Theory, 163(9))1238-1)) 1245.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Obermeier, R. and Martinez-Lorenzo, J. A. (2017). Sensing matrix design via mutual coherence minimization for electromagnetic compressive imaging applications. IEEE Tronsactions on Compulational Imaging, 3(2):217-22) 229.
Partalas, I., Kosmopoulos, A., Baskiotis, N., Articros, T., Paliouras, G., Gaussier, E., Androutsopoulos, I., Amini, M.-,, and Galinari, P. (2015). Lshte: benchmark for large-scale text, classification.
Prabhu, Y., Kag, A., Harsola, S., Agrawal, R., and Varma, M. (2018). Parabel: Partitioned Label Trees for Extreme Classification with Application to Dynamic Search Advertising. In ACM Indernational WWW Conference, pages 993 1002. International World Wide Web Conferences Steering Committee, International World Wide Web Conferences Steering Commiltee.
Prabhu, Y. and Varma, M. (2014). FastXML: A Fast, Accurate and Stable Tree-Classifee for Extreme Multi-Label Learning. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, page 263 272, New York, NY, USA. Association for Computing Machinery.
Ramaswamy, H. G. and Agarwal, S. (2012). Classification calibration dimension for general multiclass losses. In Pereira, F., Burges, C., Bottou, L., and Weinberger, K., editors, Advances in Newral Information Processing Systems, volume 25. Curran Associates, Inc.
Ramaswany, H. G., Tewari, A., and Agarwal, S. (2018). Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics, 12(1):530- 554.
Reeve, H. W. and Kabán, A. (2020). Optimistic bounds for multi-output prediction. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JML.R.org.
Rodríguez, P., Bautista, M. A., Gonzàlez, J., and Escalera, S. (2018). Beyond onc-hot encoding: Lower dimensional target embedding. Image and Vision Computing, 75:21-31.
Steinwart, I. (2007). How to compare different loss functions and their risks. Constructive Approzimalion, 26:225-22 -87.
Tagami, Y. (2017). AnnexML: Approximate Nearest Neighbor Search for Extreme Multi-Label Classification. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, page 455-464, New York, NY, USA. Association for Computing Machinery.
Tewari, A. and Bartlett, P. (2005). On the validity of pairwise surrogate losses in kernel methods. In Advances in Neural Information Processing Systems 18, pages 1217-1224.
Tewari, A. and Bartlett, P. L. (2007). On the consistency of multiclass classification methods. The Annals of Statistics, 35(1):605 636.
Wang, W., Zheng, V. W., Yu, H., and Miao, C. (2019). A survey of zero-shot learning: Settings, methods, and applications. ACM Trans. Intell. Syst. Technol, 10(2).
Wei, T., Mao, Z., Shi, J.-X, Li, Y.-F., and Zhang, M.-L. (2022). A survey on extreme multi-label learning.
Wei, T., Tu, W.WW., and Li, Y.FF. (2019). Learning for Tail Label Data: A Labcl-Speeific Feature Approach. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAI'19, page 3842 3848. AAAI Press.
Wei, Z., Zhang, J., Xu, Z., and Liu, Y. (2020). Measurement matrix optimization via mutual coherence minimization for compressively sensed signals reconstruction. Mathematical Problems in Engineering, 2020:7979606.
Welch, (1974). Lower bounds on the maxinum cross correlation of signals (corresp.). IEEE Transactions Information. Theory, 20(3):397-39)
14

---

Published in Transactions on Machine Learning Research (09/2025)
Weston, J., Bengio, S., and Usunier, N. (2010). Large scale image annotation: learning to rank with joint word-image embeddings. Machine Learning, (1)2211135
Weston, J., Chapelle, O., Elissceff, A., Schölkopf, B., and Vapnik, V. (2002). Kernel dependency estimation. In Proceedings of the 15th International Conference on Newral Information Processing Systems, NTPS'02, page 897-904, Cambridge, MA, USA. MIT Press.
Xu, Z. (2011). Deterministic sampling of sparse trigonometric polynomials. Journal of Complexity, 27 140.
Yen, 1. E., Huang, X., Dai, W., Ravikumar, P., Dhillon, I., and Xing, E. (2017a). PPDsparse: A Parallel Primal- Dual Sparse Method for Extreme Classification. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, page 545-553, New York, NY, USA. Association for Computing Machinery.
Yen, 1. E., Huang, X., Dai, W., Ravikumar, P., Dhillon, 1., and Xing, E. (2017b), PPDsparse: A Parallel Primal- Dual Sparse Method for Extreme Classification. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, page 545-553, New York, NY, USA. Association for Computing Machinery.
Yen, I. E.-H., Huang, X., Ravikumar, P., Zhong, K., and Dhillon, 1. (2016). PD-Sparse: A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel Classification. In Balcan, M. F. and Weinberger, K. Q., editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 3069-3077 3077, New York, New York, USA. PMLR.
You, R., Zhang, Z., Wang, Z., Dai, S., Mamitsuka, H., and Zhu, S. (2019). Attentionxml: Label tree-based attention-aware aware deep model for pereoperrfomecce extreme multi-label text classification. Advances in Neural Information Processing Systems, 32.
Yu, H.-F,, Jain, P., Kar, P., and Dhillon, 1. S. (2014). Large-scale multi-label learning with missing labels. In Proceedings of the 31st International Conference on International Conference on Machine Learning Volume 32, ICML'14 14, page 1-593-1-600 JMLR.org.
Yu, H.-F., Zhong, K., Zhang, J., Chang, W.-C., and Dhillon, S. (2022). PECOS: Prediction for enormous and correlated output spaces. Journal of Machine Learning Research.
Yu, N. Y. (2011). Deterministic compressed sensing matrices from multiplicative character sequences. In 2011 45th Annual Conference on Information Sciences and Systems, pages 1-5.
Zhang, J., Chang, W.-C,, Yu, H.-F., and Dhillon, 1. (2021). Fast Multi-Resolution Transformer Fine-tuning for Extreme Multi-label Text Classification. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances in Neural Information Processing Systems, volume 34, pages 7267 7280. Curran Associates, Inc.
Zhang, T. (2004). Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1) 32(1):56 (111::6685. 85.
Zhou, D.-X., Tang, J., and Yang, Y. (2014). Large scale multi-label learning with missing labels. Tn International Conference on Machine Learning, pages 593 601. PMLR.
Zou, H. and Hastie, T. (2005). Regularization and Variable Selection Via the Elastic Net. Journal of the Royal Statistical Society Series B: Statistical Methodology, 67(2))301 320.
Ávila Pires, B., Szepesvari, C., and Ghavamzadeh, M. (2013). Cost-sensitive multiclass classification risk bounds. In Dasgupta, S. and McAllester, D., editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Reseurch, pages 1391 1999,1 Atlanta, Georgia, USA. PMLR.
15

---

Published in Transactions on Machine Learning Research (09/2025)
A Proofs
In this section, we present the proofs of the results in the main paper.
A.1 Proof of proposition 2
Proof. This stems from the following facts: (i) for any given f E F, the function G o f is also measurable, i.e., 3 o F c H, (ii) for all h E H. the function f(x) Ih(x) ensures that 3 о f = h, and (ii) f(x) 9h(x) is measurable as it only attains finite number of values. So (ii) and (iii) imply H. 3 F.
A.2 Proof of the main theorem
Recall that (0(p = min arg min lp - gi 12)
Lemma 7. Vp E C", Vo E X, Cp,x(p) = max; 11(x)) - ()
Proof. Recall that - (p. = Loi (p), v) = 11 [mina min, alll- The result follows from the observation that (p)
(g( (I) and Ci,e,- = max; (z))).
Lemma 8, C2 is strictly convex and minimized at p Gn(z) = Eis (1)g))
Proof.
(p) = Prx--
((x)llp 9ill2
=
C
Σ
(x) (p- 9:.P - gi)
2
t=1
(p. - Ree
Σ
m(
1
Σ
(+)1l9911
2
1=1
(x)))
+
Σ
n (x)
2
2
1=1
So (2,+(p) is strictly convex and minimized Ph
De (=))9; Gn(x))
We'll use - to denote Gn((x) henceforward.
Lemma 9. Let V be normed space with norm l1-lly. Let u V + R be a strictly convex function. Let u be minimized at I with u(x*)= = O. Vo E V, Vo, > 0, if u(r) < = infz: =6 u(x), then || - llv do.
Proof. We first confirm the fact that VI E (0, 1) and E V - {0), ulx² + (q) < u(x" + g)-
u(x + (q) = u((1 - 1)x² + 11x" + 4))
< (1 - t))(x)))= + tu(x" + 4)
= tu(x" +9)
< u(x" + +)).
Assume the opposite: For some u E V, 5n > 0, u(x) < 8 = inf inf=:1l->" 1v u(z) and | x=1lv 2 dg. Then
8p (x x²)) 8,
- u(z)=((<² (x x²)) 2 u(x= +
| x lly
which results in contradiction.
16

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma 10. Fir x E X. vog > 0 E C", C2.x(p) < 200 1pp P < 60-
Proof. Applying Lemma with u C2 V V= C", I1-lly = 11-112: and x² = phr we have vp C", C2 <
inf, =nfss/s-p2]1== O2 lp Pz 212 8p- Furthermore,
inf =:I|a-p2 p
C2,r(0)
inf
= (8, 8) - Re (p .8) -
(Px Pa) Re(
mdg
2
2
inf
||s
Pz l
a:ll--p 160
1
2 %0
To facilitate our prools, we denote Ay.x= = 9h), 23 = Rielyas and A = mmaaax A9,al
Lemma 11. Vo E X, Vj, k E [C], Vp E C
1 (x) - (2; 21 V2 - 2XG
llp² pll2 1|p 9zl12 11p 9h 92l12-
Proof. We first consider the general case when p * Pz. Write p p + 80 where TT- and
6g = 1pp p2l12- Recall that pr Gn((x). Note the inequality immediately implies nx(x) > nz(x).
(1+ 1 (m) - (,(x)) 22
> 60
V2 2A
(1 (m)(() - 75(x)) 21 (m)(T) - (,(x)))) > 60 22G
= (1 (x) 77, (x)x)) 21 (x( - ()(x)) do /2 21G
21G
- (T)(TT) (1)))
VI XO (1 (v) - ())))) > V250
()))()(()) ()(x)) +
(A 2 )m(()) 220
(1)
V 22 itik
(1 (T) (x)) + Σ (AftE - 22 (z)) 6 2- 2199g
#j
Relp",
9k ,9k
9,) > 60l19; 9kll2
(2)
Relp", 9K 9,) > Re (de 9i - gk)
(3)
Relp"" + 6ov, 9k) Re(p" + 80v, g3)
llp - 13112 > |pp 9
(4)
Inequality follows the fact that Vi, 2 | S CC Inequality 2 follows from p = D (x)))g and
lgg gull2 /2 2 Inequality (3) is implied by the Cauchy-Schwarz inequality. In the last inequality the fact that ||اح||2 l1g 1.
17

---

Published in Transactions on Machine Learning Research (09/2025)
Now let == Pz. Let (1+19 (m
O. V2-2X²
1p gj 12 1|p- gk gxl12
-29 (P 1/ 93)
-2(1 - 33 (n (x) ()5x)) + Σ (A A 7z(
iFj
22 A (1) - n)(x)) 41 ()( (z))
22(1 (m (x) - 1/5 (2)))) DY (n (x) 7)(21))
-2(1 (1) (1(2)) 4Yt
Lemma 12. Vx E H, Vr
1 and Vp C", (2.r(p) <
21c
(1+19)--219)
C1,x()) <T.
4-2XG
C2.r (p) < (r-1)
11p-12l12 < (1419)-21 210
Proof. By Lemma 10
Fix x E X. Recall that
4-2
V2-2G
(p() = min (arg min lpp - 9:ll2]. We claim
1p- P-ll < (1+ AGr 22
max - ()) <r.
V2 12-X6 XG
(1-1 and max; (x) ()) 2 By Lemma 11 ||l g3amill
Assume 11p-Pa11
22-XG
||p - maxx m((x)) m(())
||, contradicting the definition of (p).. Hence, (p,r()) max; ((()) - (700 <r.
Now we're ready to prove Theorem
Proof of Theorem
Rlo -R / Cia(f(x))
=f CI,(((x)) 12:((022
c,,(((x)).
milla)er
We bound cach intogral individually.
By Lemma
12
Vz E X, Vr
22 T4x0, and Vp C"
(1+10)r-2*)
2r 2r = =C2x(p) 4 22G
(5)
Hence,
(p,) > 21G
= C2x(p) (1+ (1+19)C1,011) - 22
I+ G
4
21a
C1,((p) 5 1+ G 1+ G / (2,r
+
Note the last inequality actually holds for all p E C", that is, it holds when Cp, 1
22
Then,
18

---

Published in Transactions on Machine Learning Research (09/2025)
Jedleser (1x(((x))
1
21c
1+ A 1+ A V (1- (4-210)(2.(f((a))
1 A Px(d(X) + -
21C
C2x(f(x))
1
1 G Px(d(X)<r) - 2X
21c
Lucarer
C2nl (asl((/Canl((tt)
1+1G
Px.l
1 G +x)) 2X0
21C
| 1 / (2.x
(6)
1+
Px.2
21c
/ 2XC
/ (Px(d(()<()) Ree <R),, Rio, p)
1+ X +x)
<
1+ XG
In incquality we apply Holder's inequality.
When (p) (p) max; (xx) (g0 (x) 2 max; (1()) max max, (x(x) (x))) d(x). By (5)
if d(x) 2 r and C1,z (p) > O, then (2) (1+19)--19)) As CT,(()) E [0, 1]. d(x) 2 r and Ci (p) > 4-2
= (p) 222 (p) It is trivial that (2,z(p) 2 (1-19)x-119) (1,x(p) also holds when
1-2AC
1-210
(0+19))-210))
(p) = 0. Thus, Vo E X and Vp E C", d(x) 2r = (2) 2 4-2X0
C1. (p) = C1.(p) s
4-21G (11+10)-2207) (p) Therefore,
JI CL,( - /
4 2X
Jx:d(=)2r ((1 + 10)r 210)3 C2,((((x)
((1 19 / C2
4
4-2
(Re,r(f) - Ria,p).
([1+ (G)r 2XG)3
B Experiment details
In this section, we provide the details of our experiments.
B.1 Neural networks
In this section, we provide details on the architectures and hyperparameter choices for the neural networks used in our experiments. The architectures and hyperparameters are selected by trial-and-error on a heldout dataset.
B.1.1 LSHTC1
The proposed embedding strategy adopls 2-layer neural network architecture, employing a hidden layer of 4096 neurons with ReLU activation. The output of the neural network normalized to have a Euclidean norm of An Adamax optimizer with learning rate of 0.001 is utilized together with batch size of 128 for training. The model is trained for a total of 5 epochs. In order to effectively manage the learning rate, a scheduler is deployed, which scales down the learning rate by factor of 0.1 at the second epoch.
19

---

Published in Transactions on Machine Learning Research (09/2025)
Our cross-entropy baseline retains similar network architecture to the embedding strategy, with an adjustment in the output layer to reflect the number of classes. Here, the learning rate is 0.01 and the batch size is 128 for training. The model undergoes training for a total of 5 epochs, with a scheduler set to decrease the learning rate after the third epoch.
Finally, the squared loss baseline follows the architecture of our cross-entropy baseline, with the learning rate and batch size mirroring the parameters of the embedding strategy. As with the embedding strategy, the output is normalized. The model is trained for total of 5 epochs, and the learning rate is scheduled to decrease after the third epoch.
B.1.2 DMOZ
For the DM07 dataset, our proposed label embedding strategy employed a 2-layer neural network with hidden layer of 2500 neurons activated by the ReLU function. The output of the network is normalized to have a norm of 1. We trained the model using the Adamax optimizer with a learning rate of 0.001 and a batch size of 256. The model was trained for 5 epochs, and the learning rate was scheduled to decrease at the second and fourth epochs by a factor of 0.1.
For the coss-entropy loss baseline, we used the same network architecture with an adjustment in the output layer to match the number of classes. The learning rate was 0.01 and the batch size was 256. The model underwent training for total of 5 epochs, with the learning rate decrcasing after the third epoch determined by the scheduler.
Lastly, the squared loss baseline utilized the same architecture, learning rate, and batch size as the proposed label embedding strategy. Similarly, the model's output was normalized. The model was trained for epochs, with the learning rate scheduled to decrease after the third epoch.
B.1.3 ODP
For the ODP dataset, the experiments utilized a neural network model composed of layers. The size of the hidden layers progressively increased from 210 to 214, then decreased to 213, Each of these layers employed the ReLU activation function and was followed by batch normalization promote faster, more stable convergence. The final layer output size corresponded with the embedding dimension for the label embedding strategy and the number of classes for the cross-entropy and squared loss baselines.
In the label embedding framework, the output was normalized to yield norm of 1. This model was trained using the Adamax optimizer, a learning rale of 0.001, and a batch size of 2048. The training spanned 20 epochs, with a learning rate decrease scheduled after the 10th epoch by a factor of 0.1.
For the cross-entropy loss bascline, the same network architecture was preserved, with an adjustment to the penultimate layer, reduced by half, and the final output layer resized to match the number of classes. This slight modification in the penultimate layer GPU memory. Notably, the neural network output was normalized by dividing each output vector by its Euclidean norm before applying the softmax function, non-standard operation that significantly enhanced performance. This model was trained using a learning rate of 0.01 over 20 epochs, following a similar learning rate schedule.
necossary to accommodate the models within the 48GB
Finally, the squared loss baseline used the same architecture as the entsopy baseline and the same learning rate and batch size the label embedding model. Here, the output was also normalized. The model underwent training for 20 epochs, with learning rate decrease scheduled after the 10th epoch.
B.2
Elastic net
We aim to solve
min | - -1 + + + > F WeBDxn
(7)
where X E RD is the data matrix, the rows of Y Nxn are embedding vectors.
20

---

Published in Transactions on Machine Learning Research (09/2025)
The problem 7 can be broken down into independent real-output regression problems of the form |XW, - -yyl + W + +21lW,
min W
where W is the j-th column of W and Y, the j-th column of Y. Consequently, We can distribute the n real-output regression problems across multiple cores.
We develop regression variant of the Fully-Correcting
CookdCoorde Trank-Wolff (FC-BCFW) algorithm Yen et al., 2016) and use it to solve the real-oulput regression problems. As the solver operates iteratively, we set it to run for a predefined number of iterations, denoted as Niter- The chosen hyperparameters are outlined table 5
Datasct
A1
22
Niter
LSHTC1
0.1
1
20
DMOZ
0.01
0.01
20
ODP
0.01
0.1
40
Table 5: Hyperparameters for clastic net.
B.3
Practical issues
B.3.1 Choice of embedding dimension
In practical settings, the choice of the embedding dimension depends on available computational resources. Under fixed computational budget, our theory recommends opting for an embedding with minimal coherence. When the lype of embedding is fixed but compulational resources are flexible, we advise treating the embedding dimension as tunable parameter. Specifically, it is beneficial to incrementally increase n, perhaps exponentially, and observe the performance. This process should continue until the improvement in performance plateaus or the additional computational cost becomes prohibitively high.
B.3.2 Types embedding matrices
In our experiments, we used four types of embeddings. Random embeddings stand out for their simplicity and flexibility. They can be generated with a single line of code, and the embedding dimension can be any positive integer. However, their drawbacks inchude the need for explicit storage and potentially higher coherence compared to some deterministic matrices. On the other hand, deterministic matricos like those constructed using Nelson's method can achieve lower coherence, generally leading better performance. They do not require explicit storage, individual columns can be generated demand. The trade-off is that they Nelson's construction requires prime numbers for the embedding dimension).
complex to implement, and the options for embedding dimensions more limited (e.g.,
B.4 Used assets
We list the existing code used in our experiments.
PD-Sparse Yen et al.
(BSD-3-Clause
license).
PPD-Sparse
Yen et al.
2017a
Parabel PPrbbu et al.
2018):
AnnexML
http:///gthhhl.caaaaaaaa/aaa//ar Apache-2.0 2.0 license).
Tagami
2017
0-1-ov-file
WLSTS WLSTS(Evron Evron et al.
2018):
bttp://ghhaa.coooooommm/////tttp MIT Li-
cense).
21

---

Published in Transactions on Machine Learning Research (09/2025)
B.5 Visualization of Embeddings
20
(a) I-SNE plots of 2,048 Rademacher embedding tors in 128
(b) L-SNE plots of 2,048 Gaussian embedding vectors in 128
30
20-
25
30
(c) t-SNE plots of 2,048 complex Guassian embedding vectors in 128
(d) t-SNE plots of 2,048 Nelson's embedding vectors
in 1227
Figure 2: t-SNE plots illustrating the distribution of vectors from four embedding types.
To better understand the structural differences among various embedding lypes, we visualize 2,048 embedding vectors from each method using t-SNE, as shown in Figure The embeddings include Rademacher, Gaussian, complex Gaussian, and Nclson's 's construction. The random emboddings all exhibit roughly isotropic spreads the dow-dimensional projection. In contrast, the Nelson embeddings display more organized and geometrically constrained distribution.
22

---

Published in Transactions on Machine Learning Research (09/2025)
Macro Precision
Procision
Recall
0.4
Scure
Scure
Beere
0.4
Beare
Coherence
Coherence
Coherence
Coherenooe
Rademacher
Nelson
Figure Coherence vs metric score on LSHTC1 comparing Rademacher and Nelson embeddings across precision and recall (macro and micro).
B.6 Precision and recall
For set of C' classes, let TPc, FPc, FN, denote true positives, false positives, and false negatives for class Then
TP.
TP.
Precision,
Recalle
TP. + FP.'
TP. + FN.
Macro-averages compute the unweighted mean across classes,
1 Σ
1 0 Σ Recall
Macro-Precision
Precision,, Macro-Recall
while micro-averages pool counts across classes before computing,
Ee TP.
Σ TPc (TP (CT(T FN,) FN.)
Micro-Precision EE TT
Micro-Rocall
To assess whether the benefits of low coherence extend beyond classification accuracy, we include additional plots showing four other performance metries: macro-preeision, macro-recall, micro-precision, and micro-recall. Figure 3 shows how these metrics vary with the coherence of the embedding matrix for LSHTC1 using Rademacher and Nelson constructions. Consistent with the accuracy trends reported in the main paper, we observe clear inverse relationship between coherence and all measures. As coherence decreases, moving rirhtward along the reversed x-axis, all four scores consistently improve.
C Extended discussion
In this section, provide supplementary insights and theoretical context that extend the main exposition.
C.1 Consistent loss functions
Lot (X,Y) P with Y e (1.....Ky K} and function f X R For a surrogate Φ R.K x (1..... ...., K} +R define the risk Ro) B[)(J(X),Y)] We say Φ is (Fisher) consistent w.r.t. the 0-1 loss é if every minimiser f arg min, Rf) induces a Payes-optimg classifier (z(z) arg max; (x), i.e. inf, Ro(f) =f(f*)=inf, inf, Re(g) Re(g") (Zhang 2004 Tewari and Bartlett] 2007 Steinwart 2007 Canonical consistent surrogates include the mean-squared error @MSB(f. |c, - fl and the multinomial logistic (cross-entropy) exp(fx)
loss Olog(f. v) - log I. exp(fx) In contrast, margin- basod hinge variants such @hinge max
S3 f0) are known to be inconsistent in the multiclass setting Tewari and Bartlett. 2005).
23

---

Published in Transactions on Machine Learning Research (09/2025)
C.2 Nelson's construction
Let r 2 2 be natural number and p > r be prime number. Define index list := (#1,..., ar) where the ag's 's are integers in []. For each we define
F(a, u) = Σ
agu?
1=1
The n dimension embedding is constructed as
g" 1
exp Fla..)).....c exp
2T Fla.1)) n
2T F(a. ))
n
Given and r, each embedding vector is uniquely determined by a, yielding embedding capacity of n², The magnitude of the inner product between gd and gd is bounded by -= when + a' (Nelson and Temlyakov 2011
C.3
Dynamically growing label space
In scenarios with dynamically growing label spaces, random embedding matrices present significant challenges: new labels arrive, can simply sample their embeddings independently and identically distributed (i.i.d.). For deterministic constructions, the capacity depends on the construction algorithm of the embedding matrices. In Nelson's framework, the number of available low-coherence embeddings scales as n², allowing expansion to a polynomially large number of labels while maintaining desirable geometric properties. However, once the (n" 1) cap reached, the labels have be 'rehashod'.
24


Reviews:
[{"review_id": "GRn3x7XIMl", "reviewer": "Reviewer_FA3q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\nI thhink the current manuscript is relevant to the TMLR community since: \n- the paper presents a novel excess risk bound that links label embedding accuracy to matrix coherence.\n- It delivers rigorous mathematical backing to justify why low-coherence embeddings are useful.\n- and it shows that under Massart noise conditions, classification using label embedding becomes statistically consistent.\n- Their proposed Meta-Algorithm 1 is simple and modular, making it straightforward to plug into different model architectures and embedding strategies.\n- They conducted several experimental results (i.e, on three large-scale datasets) and some ablation analysis and validated that LOCOLE is efficient for the task of multiclass classification. \n\n### Weaknesses\n\n- One of the weaknesses of this study is the *fixed size of embedding*; besides suggesting generality, the experiments are restricted to fixed embeddings. This leaves out learned embeddings or embeddings using side-information, which are prevalent in practice.\n- Another one is the *Massart noise condition* that is a strong assumption and may not hold in real-world datasets, while it plays a critical role in justifying the *lossless embedding claims*.\n- The paper focuses solely on multiclass classification. While the authors mention extensions to multilabel or zero-shot settings but they are not demonstrated.\n-there is little discussion on practical limitations, such as handling imbalanced labels or noise in embeddings.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The current manuscript provides an analysis of label embedding in the context of extreme multiclass classification, where the number of labels can be very large. Label embedding replaces one-hot label vectors with dense vector representations, enabling scalable learning. To this end, the authors introduce  LOCOLE (Low COherence Label Embedding) that: i) derives an excess risk bound for label embedding using low-coherence matrices. ii)demonstrates that coherence (the maximum correlation between label vectors) directly influences classification performance. iii) they prove under the Massart noise condition that the statistical penalty of embedding vanishes if coherence is sufficiently low. iv) they also present LOCOLE, and empirically validate its performance across large-scale datasets such as LSHTC1, DMOZ, and ODP. Experimental results confirm the theory: classification accuracy improves as matrix coherence decreases.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have a few requests from the authors and would like to consider them, or at least provide discussion on these topics:\n\n### Suggestions on theoretical perspective:\n- can you please provide theoretical insight/discussion into extending the method to multi-label classification, a natural generalization?\n- Can you please  consider relax assumption and discuss more realistic noise models beyond the Massart condition or test its validity empirically?\n- \n\n### Suggestions on improving the  experimental setup \n- can you please incorporate learned embeddings (e.g., via deep co-training) to demonstrate generalizability beyond fixed low-coherence matrices?\n- can you please study how your proposed method handles class imbalance, noisy labels, or dynamically growing label spaces?\n- can you please provide deeper insight into how coherence relates to other performance metrics (e.g., precision, recall) and not just accuracy?\n- If it is possible, can you please visualize the embedding spaces (e.g., t-SNE plots of embeddings with varying coherence) this could help make abstract ideas more concrete.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YwxAXogtGo", "reviewer": "Reviewer_4dpB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strengths**\n\n- Classification with label embedding is an important problem in extreme classification and natural language processing.\n\n- The upper bound on the excess risk derived in this paper provides theoretical insights that can potentially guide the design of surrogate loss functions, embedding strategies, and learning algorithms.\n\n### **Weaknesses**\n- The paper's organization and presentation can be significantly improved; it is not easily accessible, even for a technically familiar audience. For example, the introduction of notations is scattered, the definition of matrix coherence is confusing, and it lacks proper motivation and interpretation. Additionally, the concept of \"consistency\" is not defined, and no examples of consistent or inconsistent loss functions are provided.\n\n- Proposition 2 can be misinterpreted. While it is correct that no expressiveness is lost by representing a classifier as a composition of a decoder and a measurable function, choosing an embedding dimensionality \\( n < C - 1 \\) under a convex surrogate loss introduces irreducible error, as discussed in Section 2.2. This subtle but important point should be clarified.\n\n- The experimental section is poorly presented. For instance, it is unclear whether Table 3 reports results only for LOCOLE. Summarizing the results of Table 3 in just one or two sentences is insufficient. Moreover, the reason why non-LOCOLE methods are plotted as horizontal lines is not explained. Are these methods unaffected by embedding dimensionality or coherence? This is a critical point, and the authors have sufficient space to elaborate on it. Finally, the tables and figures are minimally captioned and not self-contained.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies classification error under the dimensionality reduction of label embedding, with mean squared error (MSE) as the surrogate loss. This setting is particularly relevant for extreme classification, where the number of classes is large. An upper bound on the excess risk is provided in Theorem 4, which constitutes the paper's main contribution. The authors also propose an intuitive regression-based algorithm for classification under label embedding.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**To address the weaknesses outlined above, I suggest the following specific changes:**\n\n- Consolidate and clearly explain all notations in a single location, rather than introducing them gradually before Section 3.1 and again at the beginning of Section 3.2.\n- Define the notion of consistency and provide concrete examples of consistent and inconsistent surrogate losses.\n- Include a simple numerical example to illustrate how the embedding matrix is constructed and how class labels are mapped into the embedding space.\n- Add a clarifying note to Proposition 2 explaining why, despite preserving expressiveness, a low embedding dimensionality combined with a convex surrogate loss results in irreducible excess risk.\n- Revise the experimental section to improve clarity and completeness. In particular, clarify whether Table 3 reports only LOCOLE results, explain the behavior of non-LOCOLE baselines (e.g., why they appear as horizontal lines), and ensure that all tables and figures are sufficiently captioned and self-contained.", "broader_impact_concerns": "This paper is primarily theoretical and does not raise immediate societal or ethical concerns. However, given the relevance of label embeddings to large-scale classification tasks (e.g., in recommendation systems or language models), it is important to remain mindful of potential biases that can be introduced or amplified through embedding representations, particularly in applications involving sensitive or imbalanced label distributions.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eQjFWN1ByU", "reviewer": "Reviewer_d4j8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\nThe paper is well organized, and the problem setting is easy to follow. The theory is complemented by sufficient explanation and mathematical steps. The conclusion is intuitive and easy to follow. Both the excess risk bound of the general case and the improvement under low noise are well displayed clearly. The author compared the LOCOLE (LOw COherence Label Embeding) method with several state-of-the-art methods under the Meta-Algorithm 1 on several datasets and achieved significant performance improvement. \n\n\nWeaknesses\nAccording to the author, Meta-Algorithm 1 is not part of the contribution. Besides, the way to construct the low-coherence matrix. It is my understanding that the main contribution is the theoretical analysis to show the relationship between the excess risk and the embedding matrix coherence. If this is the case, can the author make such a part clearer in the introduction?\n\nThe author mainly conducts the experiments under the setting that matrix G is fixed. However, the author also claims that the proposed analysis also applies to the case where G is trained jointly with the f as well. I am wondering for the cases where G is trained jointly with the f, what would G look like, do they have a similar low-coherence property, or this is dataset dependent? From my understanding, deep neural networks are good at capturing some inherence relationships within the dataset.  For example, in some cases for image classification, some classes are more similar than others by definition (for example, dog vs cat, compared to dog vs grass) and show have higher coherence, under such cases, I am not sure whether imposing the low-coherence as a strong prior has some other implications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on label embedding, which is a framework for the multi-class classification problem, where each label is represented by a distinct vector. Instead of doing classification, the target is now not outputting the classification score directly, but regressing the label embedding so that it matches the correct label. This paper further focuses on the theoretical foundation of the label embedding setting in the extreme multiclass classification setting (the number of classes is very large). To this end, this paper presents an excess risk bound that shows the trade-off between computation and statistical efficiency. The core part of such a trade-off is the coherence of the embedding matrix, one can increase the embedding dimension to reduce such coherence but sacrifice the computational efficiency. Based on the theoretical findings, the author conduct experiments with a simple, scalable algorithm. They conduct experiments on several datasets to show the superiority of such an algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "So the previous section.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)