Annealed Multiple Choice Learning: Overcoming limitations of Winner-takes-all with annealing
Authors: David Perera
Victor Letzelter
Theo Mariotte
Adrien Cortes
Mickael Chen
Slim Essid
Gaël Richard
Venue: NeurIPS 2024 poster (2024)
Keywords: multiple choice learning
winner-takes-all
deterministic annealing
uncertainty quantification
Primary area: probabilistic_methods
TL;DR: We introduce Annealed Multiple Choice Learning (aMCL) which combines deterministic annealing with MCL.

Abstract: We introduce Annealed Multiple Choice Learning (aMCL) which combines simulated annealing with MCL. MCL is a learning framework handling ambiguous tasks by predicting a small set of plausible hypotheses. These hypotheses are trained using the Winner-takes-all (WTA) scheme, which promotes the diversity of the predictions. However, this scheme may converge toward an arbitrarily suboptimal local minimum, due to the greedy nature of WTA. We overcome this limitation using annealing, which enhances the exploration of the hypothesis space during training. We leverage insights from statistical physics and information theory to provide a detailed description of the model training trajectory. Additionally, we validate our algorithm by extensive experiments on synthetic datasets, on the standard UCI benchmark, and on speech separation.

Annealed Multiple Choice Learning: Overcoming limitations of Winner-takes-all with annealing
David Perera"
Victor Letzelter" 12
david. pww.raa@taeeoonppriiss..
victor www.eelterrttelcccoe.aaaa
Théo Mariotte
Adrien Cortés
Mickael Chen
Slim Essid
Gaël Richard
LTCI, Télécom Paris, Institut Polytechnique de Paris 2 Valeo.ai
Sorbonne Université
Abstract
We introduce Annealed Multiple Choice Learning (aMCL) which combines simu- lated annealing with MCL. MCL is learning framework handling ambiguous tasks by predicting small set of plausible hypotheses. These hypotheses are trained using the Winner-takes-all (WTA) scheme, which promotes the diversity of the predictions. However, this scheme may converge toward arbitrarily suboptimal local minimum, due to the greedy nature of WTA. We overcome this limitation using annealing, which enhances the exploration of the hypothesis space during training. We leverage insights from statistical physics and information theory provide detailed description of the model training trajectory. Additionally, we validate our algorithm by extensive experiments on synthetic datasets, on the standard UCI benchmark, and on speech separation.
Introduction
Ambiguous prediction tasks arise deep learning when the target y is ill-defined from the input Predicting y directly from can be challenging due to the partial predictability of from the information contained x. Multiple Choice Learning (MCL) [25, 41] addresses these challenges by providing small set of plausible hypotheses, each representing different possible outcome given the input. MCL learns these hypotheses using a competitive training scheme that promotes the specialization of the hypotheses in distinct regions of the output space }. The framework iteratively partitions y into a Voronoi tesselation and guides each hypothesis toward the barycenter of its and conditional variant of the popular K-means algorithm [45]. Like K-means, MCL is sensitive to initialization, subject to hypothesis collapse [49], and more generally may converge toward arbitrarily suboptimal hypothesis configurations [63]. While there is substantial body of literature addressing the limitations of K-means [3, 20, 58], relatively little has been done address these challenges in the context of MCL [63, 49, 54]. The core issue of MCL lies with its greedy gradient-based update of the hypotheses. This greediness precludes the exploration of the hypothesis space. preventing MCL from optimally capturing the ambiguity of We propose to incorporate annealing into this gradient descent update in order improve the robustness of MCL.
respective Voronoi cell [63]. This mechanism makes MCL akin gradient-descent-bane
Simulated annealing, inspired by the gradual cooling metals, was originally introduced for statistical mechanics applications [28, 52] and was later applied to combinatorial problems [35]. It is
'Equal Contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

random exploration process concurrent to the popular stochastic gradient descent, with significant difference: gradient descent always tries to improve performance while annealing also accepts to temporarily degrade it for the sake of exploration. The range of this exploration is controlled by temperature parameter: with a high temperature, annealing explores wide regions of the search space; when the temperature decreases, the exploration becomes narrow, and the system is able to refine its performance, This strategy has been shown to converge to an optimal state, provided that the cooling sufficiently slow [26].
Deterministic annealing [62] is variant of simulated annealing. In simulated annealing, exploration relies on a sequence of random moves across the search space, whereas deterministic annealing seeks greater efficiency by replacing this random process with the exact minimization of a deterministic functional, namely the free energy of the system. It has been shown that deterministic annealing can be efficiently applied to clustering [61, 62]. this article, we show that can be further adapted to the conditional and gradient-bare based setting of MCL. The resulting algorithm, which we name aMCL for annealed MCL., addresses the main issues of MCL, and achieves strong performance in practical settings while being straightforward to implement and amenable to analysis. Specifically, we make the following contributions.
We introduce Annealed Multiple Choice Learning (aMCL), a novel algorithm that incorporates annealing into the multiple choice learning framework (Section 3).
We propase a theoretical analysis of aMCL, to understand its advantages in comparison to vanilla MCL. We characterize the training trajectory of the model, by establishing an analogy with statistical physics and information theory (Section 4).
We provide extensive experimental validation, by applying this method i) to illustrative synthetic examples; ii) to a standard distribution estimation benchmark (UCI datasets); and also iii) to the challenging audio task of speech separation (Section 5). The accompanying code is made available.
2 Related Work
Multiple choice learning. MCL has been successfully applied to various machine learning tasks, typically using multi-head neural networks, with each head providing a prediction [40, 22, 42). Several works observed the phenomenon of hypothesis collapse [8, 19, 33, 40, 67, 63], where some hypotheses are left unused during training. Various solutions have been proposed to tackle collapse [63, 49, 54]. Notably, [63] introduces Relaxed-We -TTA, which updates non-winning hypotheses with gradient scaled by a small constant E. However, this small gradient biases the hypotheses toward the global barycenter of the target distribution, which can be shown be suboptimal [14].
Simulated and deterministic annealing. Deterministic annealing is a variant of simulated annealing [28, 52, 35]. Rose et al. extensively investigated its properties, particularly in relation to statistical physics and clustering [61, 62, 59, 60]. We are, to the best of our knowledge, the first to combine this technique with Winner-takes-dl aal training in conditional setting.
Information theory and quantization. Quantization [64] consists of discretizing continuous variables over a finite set of symbols. The rate-distortion theory studies the minimal number of bits necessary to encode information at given level of quantization error [5, 2, 4J. Recently, relation has been established between optimal quantization of conditional distributions [14] and multiple choice learning [63, 42, 43]. In this paper, we propose to integrate annealing for conditional quantization.
3 Annealed Multiple Choice Learning
3.1 Wanner-takes-all loss and its limitations
Let X' and y denote subsets of Euclidean vector spaces. We are interested in so-called ambiguous tasks, i.e., for any given input & E X. there may be several plausible outputs E ). Formally, let p(a, y) denote a joint distribution on Y. Multiple Choice Learning (MCL) [25, 41] was proposed to train neural networks in this setting, and has proven its effectiveness in a wide range of machine vision [40], natural language [22] and signal processing tasks [42].

---

MCL consists in training several predictors fn) E F(*, typically a multi-head neural network derived from common backbone, such that for each imput E X. the predic- tions (z). Jn (x)) provide an efficient quantization of the conditional distribution p(y x)
[63, 42, 43]. This goal is achieved by minimizing the distortion
/ min e ev, fx())) p(z, y)drdy, Jxxy kE]1.n]
D(f)
(I)
where e y²a 7 is an underlying loss function, for instance, the squared Euclidean distance E(g. lly 0ll Eq. (I) can be seen as generalization of the conditional distortion [56].
More specifically, MCL training is an iterative procedure optimizing (1) by alternating the two following steps.
1. Assign each y to the closest hypothesis (xx build the Voronoi cells:
(a(x) E y VI [1. Ely, fa(z)) S Ely, fi(z)))
(2)
2. Minimize the distortion within each cell by taking a gradient step on the WTA loss:
/ 1 X K=
(
WTA ( -
((u(()) x)dyy p(x)dxx
The prediction models can be paired with scoring models (71.-.. (.1:-... 7n) F(X, [0, 1J"). which trained to estimate the Voronoi regions' probability mass using the scoring loss [42]
Cecoring (7) A
BCE (1 E (x(x)), p(x, y)drdy
where BCE(P, 9) _ -plog(4) - (1 p) log(1 - 9). In practice, the two losses (3) and (4) are opti- mized in a compound objective L = LWTA + _scoring, A probabilistic interpretation of such trained predictors has been developed [63, 42). shows that the predictions and scores be interpreted as a mixture model approximating the conditional density p(u x) by Σx The ( (v).
It has been shown that WTA is sensitive to initialization [54], and often leads to suboptimal hypothesis positions, similarly to K-means. Indeed, WTA a greedy procedure that updates only the best hypotheses: if one hypothesis falls outside the support of the data density p(- æ)) it may be isolated from its competitors at initialization, and remain so across training (the collapse issue).
Our method improves the WTA training scheme by addressing the inherent greediness of gradient descent and introducing variability in the exploration of the hypothesis space through deterministic annealing. Figure illustrates the limitations of the aforementioned algorithms and the comparative advantage of aMCL.
3.2 Combining deterministic annealing with Multiple Choice Learning
We introduce aMCL, which combines MCL and anncaling. Let t + T(t) denote a temperature schedule decreasing with the training step and vanishing the end of the training. Similarly to MCL. aMCL. alternates between an assignation and minimization step, as follows:
1. Softly assign each to all fx(x)) using the softmin operator (or Boltzman distribution 4r()):
e(f((o)))))
((f(()).))
4rce (fk x. v. A
exp
T(t) (--T())
Zz.y A
exp
(5)
Zu.y
T(t)
2. Minimize the distortion within each soft cell by taking gradient step on the aWTA loss:
CITTA
T
(
(Uua()) w,,)p(,,, y)dady,
(6)
XXX k=
where (T is kept constant (i.e., the shop_gradient operator is applied).

---

MCL
Relaxed WTA
Annealed MCL
Figure I: Overcoming limitations of Winner-Takes-AA training with annealing. Illustrations of the test-time predictions Mixture of three Gaussians (green points) with 49 hypotheses. Shaded blue circles represent the hypothesis predictions, with intensity corresponding to the predicted scores. (Left) Predictions of MCL proposed in [41, 42]. (Middle) Predictions of Relaxed WTA [63] with & = 0.1. (Right) Annealed MCL with initial temperature To = 0.6. Each model was trained with the same backbone (a three-layer MLP).. We that WTA leaves out some hypotheses, achieving a higher quantization error than aMCL. Moreover, we see that Relaxed-W WTA is biased toward the barycenter of the distribution, in contrast with aMCL.
Therefore, the lowest level, aMCL simply consists of replacing the min operator from (2) by softmin. aMCL introduces the temperature schedule by the literature on simulated annealing [26], is crucial to ensure that temperature decreases slowly enough to benefit from the advantages of annealing. In practice, we experimented with both linear and exponential schedulers (see also Section 5).
additional hyperparameter. As highlighted
On a higher level, we can interpret the objective of aMCL as a smoothed version of the MCL objective. Smoothing with high temperature simplifies the optimization problem (6), making the loss landscape easier to navigate: we can conjecture from this analysis that aMCL. will find global minimum at high temperature, and we can expect it to stay optimal as long as the temperature decreases slowly enough [9]. We can also see aMCL as input-dependent version of deterministic annealing [61, 62]. In this view, a high temperature encourages the exploration of the hypothesis space and mitigates the greediness of the gradient descent update (3). Moreover, following [26], we can posit that there exists an optimal temperature schedule striking a balance between exploration and optimization. Yet another interpretation is that aMCL constitutes
[63], as Qr [fx x, y) depends both on the distance between the hypothesis f& fx(zz) and the target y. and the training step These interpretations shed light the inner workings of aMCL. However, the complete training dynamic of the algorithm appears when we analyze aMCL through the lens of information theory and statistical physics, which is the purpose of the next section.
adaptative extension of Relaxed-MC
Theoretical analysis
In this Section, we theoretically investigate the properties of our algorithm. Specifically, we de- tail its training dynamic in Section 4.1. In Section 4.2, explore how this dynamic relates to the rate-distortion curve. This relationship allows us to study in Section 4.3 the phenomenon of phase fransition, where hypotheses merge and split into sub-groups depending the temperature. Throughout this Section, we will focus on the squared Euclidean distance {(g y) = ly - 0112.
4.1 Soft assignation and entropy constraints
Minimizing (1) is NP-hard [1, 10, 48). Unsurprisingly, MCL can get trapped in local minima during training. this Section, we discuss why the aMCL training scheme in Section 3.2 more resilient to this pitfall. The first step toward our analysis is to observe that the stop_ goo__gnndnettt operator used in (6) of the aMCL update effectively turns the algorithm into an alternating optimization the soft distortion
Dlg.f) I
m
e(fa(z) v) qffelz v) p(z, y)dzdy,
JXXY

---

where the variables and f are treated as independent, procedure similar to Expectation Maximiza- tion [12]. This observation captured by Proposition I, where == , denotes the set of functions from X' to )mh A, the set of all distributions on items conditioned by points on X' x y/ (m) = -E==1 T log vy the entropy of a discrete distribution π, Hr = H ((r) the entropy the Boltzmann distribution at temperature T, and X the learning rate of the gradient descent at step t. Proposition (Entropy-constrainge alternated minimization). The assignation (5) and optimization (6) steps of aMCL correspond to an entropy-constrainee block coordinate descent on the soft distortion.
9 argmin D) f&t t fa- - D(. Ak [1,n].
(8)
geA.
2
This is a corollary of Proposition 2, which provides additional insights on the training dynamics of aMCL.
Proposition 2 (aMCL training dynamic), See Proposition 5 in Appendix. The following statements
are true for all T > 0, f E F, strictly positive E An, x E X and y E E..
exp ( (-(((((())))) (T) (T([x(2,)) E exp (-((f((()))) /T)
(i) argmin ((g, f) qr, gEA, H(
Wk E [1,n]
f1(x) = Jy af u)p(y x)dy
(ii) argminze>D(1,1 8
Vk E [1,n]
Sy a(h xz, s)p(y x)dy
(iit) V P(a,)) - SW), 7 = (0 v)y xddyy.
vk E [1,n]
Part (i) states that the softmin operator is the solution of the entropy autroy--constrained constrained minimization the soft distortion. Part (ti) states that necessary condition for minimizing the soft distortion is that each fk is a soft barycenter of the assignation distribution for each temperature T. Part (iii) states that each gradient update moves fs toward this soft barycenter f", and that the update speed depends on the probability mass 7 of the points softly assigned to fs. Together, they describe the training dynamics of aMCL. Note that T O, qr converges to one-hot vector, and the soft barycenter in (di) becomes a hard barycenter. This is consistent with the necessary optimal condition for MCL, fi (z) Ey-p(u)a) [Y | (x)), proved by Rupperecht et al. [63].
4.2 Rate-distortion curve
We have established in Section 4.1 that the aMCL training scheme is equivalent to an entropy- constrained alternating optimization of the soft-distortion (7), with each hypothesis fa moving toward a soft barycenter. In this Section, we describe the impact of temperature cooling on this training dynamic.
First, observe that when the temperature is high, the Boltzmann distribution er becomes uniform. Therefore, the soft Voronoi cells merge into single cell V the hypotheses fa converge toward the barycenter of y, and they all fuse into a single hypothesis:
(9) Remarkably, this phenomenon occurs even finite temperatures (see Appendix, Proposition 9). As the temperature decreases, a phenomenon of bifurcation occurs [61, 59]. During this process, the hypotheses iteratively split into sub- sub-groups, as shown Figure 4. The virtual number of hypotheses [60] for each x at given distortion level is captured by the conditional rate- distoritootion function
(x) = E(x,Y) [Y X = x]. Ak E [1,n].
R₂ (D*) A min gE FEF D.(g.f)ED*
(Ý;
(10)
In Eq. (10), Y ~ p(y | x) follows the target distribution, the hypothesis position Y ~ (fr x)) follows a distribution over y with qffx x) = fy q(fx æ, v)p( æ)dr, (Ý;; information, and (g. f) Jy Σg ((fa(z) U)((fe v))((( x)dy is the distortion for input
Y) ) is their mutual
The rate-distortion function R, (D*) has the following key properties.
5

---

Dist-Distottion Curve
Distortion daring training
Shsmnon Lower Bound
73 (upper bound)
of
Distortion
Rate R
MCC
aMCL
10
10
10"
10"
Distortion
Temperature
Figure 3: Regimes in the distortion (1) vs. tem- perature training curve on the setup of Figure At first, the hypotheses converge to the conditional mean. It is followed by plateau phase where per- formance stagnates. Transition begins at Th: the hypotheses migrate toward the barycenter of each Gaussian. Then, they split and we observe last phase transition. For reference, 2a the critical temperature for a Gaussian with variance o².
Figure 2: Illustration of the training trajec- tory in the Rate-Distortion curve. Training trajectories of MCL (blue) and aMCL (red) in the case of single Gaussian. The optimal reachable distortion ('+') is the distortion D satisfying R(D)) logz(1) (n) (See Section 4.2).
Proposition 3 (Rate-distortion properties). See Proposition 7 in Appendix.
For each x E X, let Dmax (31) denote the optimal conditional distortion when using single hypothesis, we have the following results.
(i) For each T O, minimizing the free energy
= D (QT)),
(11)
over all hypotheses positions I F(X,3") comes down to solving the optimization problem that defines (10) for each X.
(ii) R₂ is a non-increasing, convex and continuous function of D*. (D(D") for when it
D* 2 Dmaxx and for each x the slope can be interpreted as R (D") is differentiable.
(iii) For each x, R2(D") is bounded below by the Shannon Lower Bound (SLB)
Rz(D*) 2 SLB(D") & H(Y) - H(D*)
(12)
where Y ~ ply x:) and H(D*) is the entropy of a Gaussian with variance D*
Part (i) establishes that the rate-distortion function is tightly linked with our problem. Provided that the hypotheses fa perfectly optimize the soft distortion (7) at any temperature level, the hypothesis configuration / will follow the optimal parametric curve (D*, R,*)))) ) for each x E X. Part (ii) describes the shape of the parametric curve (D', R2 (D*)). The Shannon Lower Bound described in part (iiz) is lower bound on the virtual number of hypotheses reached by aMCI.
The rate-distortion curve effectively describes the training trajectory of our algorithm, with the deterministic annealing procedure consisting of ascending along this curve [61, 59]. Interestingly. there of critical temperatures at which the hypotheses suddenly split, increasing the number of sub-groups they form. By analogy with statistical physics, the behavior at these points has been coined phase transitions [23]. An illustration of the trajectory MCL and aMCL the rate- distorttooionn space is shown in Figure 2. We see that MCL evolves along a constant rate R = log, (n) (in bits) following (a). In contrast, aMCL initially reaches the critical state at D* = D following (b). After the transition, the trajectory of aMCL returns to the maximal rate following (c). We expect the optimization a lower rate be simpler and this training trajectory to provide a better initialization for the set of hypotheses compared to the vanilla MCL.

---

4.3 Phase transitions
During training, as the temperature decreases, the hypotheses f undergo sequence of phase transitions at specific critical temperatures. The right tool to exhibit these critical temperatures is the Hessian of the free energy f # (f.qr). Transitions occur when the minimum of 9 is no longer stable, and it can be shown [61] that this relates to the eigenvalues of the following block-diagonal covariance matrix:
CLL.(I (n()) v))(()) v) a(v x)py) x)dy,
(13)
where Qly I 2k. denotes the posterior probability of assigning point y to the hypothesis calculated using Bayes's rule [60]. At high temperatures, all hypotheses merge into the conditional barycenter of the distribution (9). In this setting, all the matrices Ck, are equal to the data covariance
matrix C(x) A Cov(x.Y)=ple Y))p(.))) Y X = z/. & has a unique minimizer, and the stability of this global optimum is conditioned temperature To is defined as the first temperature for which the Hessian of $ is no longer positive definite.
the strict positivity of the Hessian of P. The first critical
This temperature is connected to D the vanishing point of the rate-distortion function Rs (D*). which also corresponds the optimal I-hypothesis distortion [4]. Indeed, R,(D") measures the virtual number of hypotheses, so that the first splitting of the hypotheses from a single point to several groups will coincide with the moment when R. (D*) > O. We summarize these observations in the following Proposition 4, which is illustrated in Figure 3.
Proposition 4 (First critical temperature). See Definition I, Propositions 6 (ii) and 8 in Appendix. Let Amax() (-) denole the maximum eigenvalue of matrix, (T) - (xTr: ) D (T) a fer Dgrr f), and Dunax - SZex Dmmxpp(x)) p())dx. Then the two following properties hold.
(i) D and D' are non non-decreasing functions of T and admit generalized inverses (with the convention g (3) [a g(a) 2 33 for the generalized inverse of a function g)-
(ii) The conditional (resp. non-conditional) first critical temperature (x) (resp. Tğ satisfy
(z) _ (D:) (D = -2Amax(C(x))
(14)
Te a (D*)~1 (D max) S 2 sup Amax (C(x))
(15)
=EX'
T(t)
T(t)
T(t))
T(G)
0.6
0.9
Figure 4: Conditional phase transitions with 4 < l2 < 13 < 44- Results for a conditional
version of the dataset in Figure 1, where the Gaussian moves linearly and increases with the input E [0. 1]. aMCL was trained during 1000 epochs, using a linear scheduler with To 1.0, and using 49 hypotheses. Each subplot group corresponds the predictions of the model a given temperature, evaluated at different values. At temperature T(t1), the hypotheses are at the barycenter. As temperature decreases they undergo a first phase transition (at temperature T(t2) for x 0.9 and T(ta) for x = 0.6), moving toward each Gaussian's 's barycenter, followed by second phase transition T(ta). We see that earlier splits the cooling schedule correspond to conditional distributions with higher variances.
7

---

After the first transition, an interesting phenomenon occurs for some distributions p(z, y). Instead of splitting all directions, the hypotheses fF continue form small number of subgroups. The hypotheses JK may undergo many phase transitions before they all split apart from each other: this is illustrated in Figure Generally, this recursive splitting reaches an end: under mild conditions [36], there is critical temperature below which the hypotheses all separate from each other. This defines the last critical temperature T Remarkably, T is associated with the Shannon Lower Bound: the temperature at which Rt (D*) hits the lower bound SLB(D*) corresponds to the moment when the hypotheses f& completely separate from each other (see Theorem and 3 in [59]).
Experimental validation
In this Section, we experimentally investigate the advantage of our algorithm in practical settings. Specifically, evaluate it on the standard UCI benchmark in Section 5.1, and we apply it to the challenging task of speech separation in Section 5.2.
5.1 UCI datasets
5.1.1 Setup
General setup. We followed the experimental protocol described by [29] for the UCI benchmark [15]. Specifically, we used the official train-test splits, with 20 folds except for the Protein dataset, which is split into 5 folds, and the Year dataset, which uses single fold.
Baselines. our result tables, we also include data from three baseline methods detailed in Table 1 of Lakshminarayanan et al.'s paper [38] ('Deep Ensembles'), which serves as reference. These baselines include Probabilistic Back Propagation [29] (denoted 'PBP'), and Monte Carlo Dropout [21] (denoted 'MC-dropout', As additional baselines, we include the standard score-based MCL (e.g., [42]). We also include the Relaxed-MCL variant [63] with E = 0.1. The impact of s discussed in Appendix D.2. Our method (aMCL), was trained with exponential scheduler of the form T(t) Top', with p = 0.95 and To = 0.5. Comparison with a linear scheduler also provided in Appendix D. Both aMCL and Relaxed-MCC were trained for 1,000 epochs. Each MCL system was trained with n hypotheses.
Metrics. We computed the following metrics on the UCI datasets. Let d denote the squared Euclidean distance: d(G,, y:) 1y - 12, and N the number of samples each dataset. The RMSE (4) is defined as RMSE / */ E, d(Ots vi). where ÿ denotes the estimated conditional mean. The latter was computed with Σk= Th (x for the MCL variants. The results of this experiment are summed up in Table (Distortion), and also in Table 2 (RMSE). Rows are ordered by dataset size N, with the intensity of the grey color proportional N (excluding the Year dataset).
5.1.2 Results
Table 1: Results on UCI regression benchmark datasets comparing Distortion. Experimental
setup is described in Section 1. Relaxed-WTA WTA results were computed with 0.1 which strikes a good tradeoff between RMSE and Distortion (see Table 5 in Appendix). The rows are ordered by dataset size N. Best results in bold, second bests underlined.
Distortion ())
Datasets
Relaxed-WTA (a = 0.1)
MCL
aMCL
N
Year
9,09 NA
4.82 1
4.46 NA
515345
Protein
1.67 + 0.16
0.80
0.77 0.03
45730
Naval
4.21e-7 + 2.36e-7
1.84e-6
2.42e-6
5.37e-7 3.83e-7
11934
Power
2.95 1 0.91
2.31
0.64
9568
Kin8nm
9.32e-4 7.97e-5
1.00e-3 1.47e-4
6.81e-4
8.14e-5
8192
Wine
0.06 + 0.02
0.02
0.03 0.01
1599
Concrete
6.91 + 2.81
5.13 1.23
5.71 1.72
1030
Energy
0.30 +: 0.12
1.25 1.25
0.28 0.09
768
Boston
3.32 + 2.84
2.14 0.49
2.69 1.39
506
Yacht
1.34 + 0.93
3.09 2.41
1.15 0.97
308

---

Table Results on UCI regression benchmark datasets comparing RMSE. Best results are in corresponds to reported results from [38].
bold, second bests are underlined.
RMSE (1)
Datasets
PBP
MC Dropout'
Deep Ensembles*
Relased-WTA TA (2 0.1)
MCL
aMCL
NV
Year
8888 : NA
8.83 NA
8.89 NA
8.97 1 NA
9.09 F NA
9.08 NA
515345
Protein
4,73 = 0.01
4.36 + 0.04
4.71 + 0.06
4.38 0.02
4,39
4,25 + 0.02
45730
Naval
2.08e-3
4.04e-4
Power
4.12 = 0.03
4,02 + 0.18
4.11 0.17
4,02 0.18
4,18 0.16
4.08 0 0.20
9568
Kinšnm
0.10 + 0.00
0.10 + 0.00
0.09 0.00
0.08 0.00
0.10 001
0.08 0.00
8192
Wine
= 0.01
+ 0.04
0.64 2
0.63 0.04
0.63 063=0.04
0.63 0.04
1599
Conerete
5.67 = 0.09
5.23 + 0.53
603 + 0.58
5.28 0.58
6,02 = 0.65
5.47 + 0.67
1030
Energy
Boston
3,01 +: 0.18
2.97 0.85
3.28 1,00
2.85 0.72
3,54 1.16
3,05 0 0.91
506
Yacht
1,02 = 0.05
L11 0.38
1.58 0.48
2.52 1.04
3.28 1.39
162 1022:..55 0.53
308
Comparison of aMCL and MCL. We can observe that aMCL performs comparably or outperforms vamilla MCL in most settings. especially for large dataset sizes, both in terms of distortion and RMSE. This outcome supports the claims made in the paper and is especially promising, given that the temperature scheduler was not specificallyy optimized for each dataset.
Comparison aMCL and standard UCI baselines. We observe that aMCL, performs on par with, and in some cases exceeds, standard baselines the RMSE metric. This is noteworthy, aMCL not explicitly optimized for RMSE during training its primary focus on quantization. While perfect quantization would naturally result optimal RMSE, achieving low RMSE is not the main objective of aMCL. For example, the RMSE performance of MCL is slightly worse across most datasets in those experiments.
Comparison with Relaxed-MCL. Finally, we compare aMCL and Relaxed-MCL, since aMCL can adaptative version of Relaxed-MCL. Our results indicate that aMCL generally
be interpreted outperforms Relaxed-Me MCLL in terms of distortion across nearly all datasets. However, we also observe that Relaxed-MCII demonstrates strong performance in terms of RMSE. We attribute these findings to the bias of Relaxed-MCL toward the conditional barycenter of the target distribution, which seems to improve RMSE the expense of increased distortion. This trade-off arises because RMSE evaluates the accuracy of the barycenter estimation, while distortion measures the quantization performance. The trade-off between distortion and RMSE be adjusted by uning the value of e. Further analysis of this parameter presented in Appendix D.1, where we show that aMCL. strikes good balance between these two metries.
These results strongly support the use of aMCL as a quantization algorithm in practical settings. To further evaluate its effectiveness, we also apply aMCL to more challenging task, namely speech separation.
5.2 Application to speech separation
Speech separation consists of isolating each speaker's signal from mixture in which they are simultaneously active. This task is of major interest for automatic speech processing applications [50, 44, 71]. these experiments, we explore the application of MCL and the proposed aMCL to the task of speech separation. An extensive description of the experiments is proposed in Appendix E.2.
5.2.1 Experimental settinn
General purpose. Speech separation consists in obtaining the source signals y1 V1.... Um E RR from a mixture x = >x=1 Hence, the task is to provide estimates 91..... Dm of the isolated speech tracks from the mixture x.
Dataset. Source separation experiments are conducted on the Wall Street Journal dataset [30] (WSJO-mix), standard benchmark for speech separation. We focus the 2- and 3- speaker mixture scenarios, with each scenario including 20,000 training, 5,000 validation, and 3,000 testing mixtures.
Model architecture. The source separation task is solved using the Dual-Path Recurrent Neural Network (DPRNN) architecture [46]. DPRNN has been extensively used speech separation, as strikes good balance between performance and number of trainable parameters [73, 65].

---

Separation metrics. We use the Scale-Invarian Signal Signal-to-Distoree Distortior Ratio (SI-SDR) to measure the separation quality [70, 39]. There an ambiguity finding the best assignment between predicted and active sources. The PIT SI-SDR loss [37] initially addresses this issue. We propose to use MCL. and our new variant aMCL. to perform this matching (See Appendix E).
5.2.2 Results
Comparing PIT, MCL, Relaxed-WTA and
Table 3: 2- and 3- speaker source separation with PIT (topline). MCL, aMCL and Relaxed- WTA (E = 0.05). PIT SI-SDR metric (f) on the WSJO-mix eval set. Results over three training seeds, with mean and standard deviation reported.
aMCL. Table 3 presents the source separation results in the 2- and 3-speaker scenarios. First, aMCL demonstrates performance equivalent to or better than MCL.. Both methods can be used for the separation task. However, we observed that MCL is subject to hypothesis collapse for some training seeds, while aMCL is more robust to initialization. This translates into a lower inter- seed standard deviation for aMCL. Second, we observe the advantage of aMCL over Relaxed- WTA, which is consistent with our previous anal- ysis of the barycenter bias of this method. Third, aMCL. performs equivalently to PIT in both sce-
Method
2 speakers
3 speakers
PIT
16.88 + 0.10
10.01 + 0.04
MCL Relaxed-WTA
16.30 + 0.59
10.06 + 0.21
16.70 + 0.08
9.43 + 0.21
aMCL
16.85 + 0.13
10.00 + 0.21
narios. Note that by using MCL or aMCL., the number of predictions n could exceed the number of sources m. This could leveraged to improve the separation metries (cf. Appendix E.3.2). Finally, aMCL improves the algorithmic complexity of PIT from ((m²) to O(m)) (cf. Appendix E.3.1). These results make aMCL stand as a good alternative to PIT.
Observing phase transition. When the metric is the Euclidean distance, the theoretical analysis of Section 4.3 and the synthetic experiments (see Figure 3) have highlighted a phenomenon of phase transition for aMCL. Here, we analyze the validation loss trajectory as a function of the temperature for different initial temperatures, and using an exponential scheduler. The curves with the two higher initial temperatures in Figure 8 exhibit a plateau until given temperature. After this critical point, the loss decreases. Although the SI-SDR is -un-uucideea,, this behavior resembles that observed for the Euclidean metric. This is detailed in Section E.3.3 of the Appendix.
6 Conclusion
This article introduces aMCL, novel training method that combines deterministic annealing and the Winner-Takes-all training scheme to address two key issues of MCL: hypothesis collapse and convergence toward suboptimal local minimum of its quantization objective. We provide a detailed analysis of aMCL's training dynamics. Moreover, drawing on statistical physics and information theory, we provide insights into the trajectory of the aMCL predictions during training. In particular, we exhibit a phase transition phenomenon and establish its connection to the rate-distortion curve. We validate our analysis with experiments on synthetic data, on the UCI datasets, and speech separation task. This demonstrates that aMCL is a theoretically grounded alternative to MCL in diverse settings. Future work includes detailed analysis of the temperature schedule's impact, the derivation of performance bounds, a thorough examination of our algorithm's convergence, particularly at finite temperature, as well an evaluation of its generalization capabilities on out-of- distribution samples.
Limitations. First, aMCL introduces temperature schedule: this is challenging hyperparameter tightly linked to the optimizer and its learning rate. The derivation of optimal schedules left to future work. Second, annealing requires slow temperature schedule to maintain model performance. This potentially leads to longer training times.
Broaden impact. This paper introduces research aimed at progressing the field of Machine Learning. While our work has numerous potential societal implications, we believe there are no specific consequences that need to be emphasized in this paper.
10

---

7 Acknowledgments
This work was funded by the French Association for Technological Research (ANRT CIFRE contract 0022-18544 and Hi! PARIS through their PhD in AI funding programs, and was performed using HPC resources from GENCI-IDRIS (Grant 2021-AD01 101 10164))R)) We are grateful the reviewers for their insightful comments.
References
[1] Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. Np-hardness of euclidean sum-of-squares clustering. Machine learning, 2009, 4, 15
[2] Suguru Arimoto. An algorithm for computing the capacity of arbitrary discrete memoryless channels. IEEE Transactions on Information Theory, 1972. 2
[3] David Arthur, Sergei Vassilvitskii, et al. k-means++: The advantages of careful seeding. In Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2007.
[4] Toby Berger. Rate-distortion theory. Wiley Encyclopedia of Telecommunicattonss, 2003. 2, 7, 20
[5] Richard Blahut. Computation of channel capacity and rate-distortion functions. IEEE Transac- tions on Information Theory, 1972.
[6] Richard Blahut. Principles and practice of information theory. Addison- Wesley Longman Publishing Co., Inc., 1987. 20
[7] David P Bourne and Steven M Roper. Centroidal power diagrams, lloyd's algorithm, and applications to optimal location problems. SIAM Journal on Numerical Analysis, 2015. 15
[8] Mike Brodie, Chris Tensmeyer, Wes Ackerman, and Tony Martinez. Alpha model domination in multiple choice learning. In IEEE International Conference on Machine Learning and Applications, ICMLA, 2018.
[9] Imre Csiszár. On the computation of rate-distortion functions (corresp.). IEEE Transactions on Information Theory, 1974.
[10] Sanjoy Dasgupta. The hardness of k-means clustering. 2008.
[11] Davisson. Rate distortion theory: A mathematical basis for data compression. IEEE Transactions Communications, 1972. 20
[12] Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, 1977. 5
[13] Qiang Du, Maria Emelianenko, and Lili Ju. Convergence of the lloyd algorithm for computing centroidal voronoi tessellations. SIAM Journal on Numerical Analysis, 2006. 15
[14] Qiang Du, Vance Faber, and Max Gunzburger, Centroidal voronoi tessellations: Applications and algorithms. SIAM Review, 1999. 2
[15] Dheeru Dua, Casey Graff, et al. Uci machine learning repository. 2017. 8, 24
[16] Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, JACM, 1972. 29
[17] Paul Embrechts and Marius Hofert. A note on generalized inverses. Mathematical Methods of Operations Research, 2013. 20
[18] Maria Emelianenko, Lili Ju, and Alexander Rand. Nondegeneracy and weak global convergence of the lloyd algorithm in dd SIAM Journal on Numerical Analysis, 2008. 15
[19] Michael Firman, Neill DF Campbell, Lourdes Agapito, and Gabriel J Brostow. Diversenet: When one right answer not enough. In IEFF/CVF Conference on Computer Vision and Pattern Recognition, CVPR, 2018.

---

[20] Pasi Fränti and Sami Sieranoja. How much can k-means be improved by using better initializa- tion and repeats? Pattern Recognition, 2019. 1
[21 ]] Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian international workshop on approxima- tion algorithms for combinatorial optimization, approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning. ICML, 2016. 8, 24
[22] Nuno Cruz Garcia, Sarah Adel Bargal, Vitaly Ablavsky, Pietro Morerio, Vittorio Murino, and Stan Sclaroff. Distillation multiple choice learning for multimodal action recognition. In IEEE/CVF Winter Conference on Applications of Computer Vision, WACV, 2021. 2
[23] Thore Graepel, Matthias Burger, and Klaus Obermayer. Phase transitions in stochastic self- organizing maps. Physical Review E, 1997.
[24] Robert M Gray. Source coding theory. Springer Science & Business Media, 1989. 20
[25] Abner Guzman Riveer, Dhruv Batra, and Pushmeet Kohli. Multiple choice learning: Learning to produce multiple structured outputs. Advances in Neural Information Processing Systems, NeurlPS, 2012. 1,2
[26] Bruce Hajek. Cooling schedules for optimal annealing. Mathematics of Operations Research, 1988. 2, 4, 22, 23
[27] Xizewen Han, Huangjie Zheng, and Mingyuan Zhou. Card: Classification and regression diffusion models. Advances in Neural Information Processing Systems, NeurlPS, 2022. 24
[28] W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. 1970. 1, 2, 22, 23
[29] José Miguel Hernández-Loband and Ryan Adams. Probabilistic backpropagation for scalable learning of bayesian neural networks. In International Conference on Machine Learning, ICML,
2015. 8, 24
[30] John R Hershey, Zhuo Chen, Jonathan Le Roux, and Shinji Watanabe. Deep clustering: Discriminative embeddings for segmentation and separation. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, 2016. 9, 27
[31] Po-Sen Huang, Scott Decann Chen, Paris Smaragdis, and Mark Gasegawa-JJhnsoon Singing- voice separation from monaural recordings using robust principal component analysis. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, 2012. 26
[32] Mikaela lacobelli. Asymptotic quantization for probability measures on riemannian manifolds.
ESAIM: Control, Optimisation and Calculus of Variations, 2016. 20
[33] Eddy Ilg, Ozgun Cicek, Silvio Galesso, Aaron Klein, Osama Makansi, Frank Hutter, and Thomas Brox. Uncertainty estimates and multi-hypotheses networks for optical flow. In European Conference on Computer Vision, ECCV, 2018.
[34] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- lional Conference on Learning Representations, ICLR, 2015. 24
[35] Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. Optimization by simulated annealing.
Science, 1983. 1,2
[36] Tobias Koch. The shannon lower bound is asymptotically tight. IEEE Transactions Informa- tion Theory, 2016. 8
[37] Morten Kolbæk, Dong Yu, Zheng-Hua Tan, and Jesper Jensen. Multitalker speech separation with utterance-level permutation invariant training of deep recurrent neural networks. JEEE/ACM Transactions on Audio, Speech, and Language Processing, 2017. 10
[38] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in Neural Information Processing Systems, NewrIPS, 2017. 8, 24
12

---

[39] Jonathan Le Roux, Scott Wisdom, Hakan Erdogan, and John R Hershey. hal-hhaf-baked or well done? In IEEE International Conference on Acoustics, Speech and Signal Processing. ICASSP. 2019. 10, 26
[40] Kimin Lee, Changho Hwang, KyoungSoo Park, and Jinwoo Shin. Confident multiple choice learning. In International Conference on Machine Learning, JCML, 2017.
[41] Stefan Lee, Senthil Purushwalkam Shiva Prakash, Michael Cogswell, Viresh Ranjan, David Crandall, and Dhruv Batra. Stochastic multiple choice learning for training diverse deep ensembles. Advances in Neural Information Processing Systems, NeurIPS, 2016. 1, 2, 4
[42] Victor Letzelter, Mathieu Fontaine, Mickaël Chen, Patrick Pérez, Slim Essid, and Gael Richard. Resilient multiple choice learning: learned scoring scheme with application to audio scene analysis. Advances in Neural Information Processing Systems, NeurlPS, 2023. 2, 3, 4, 8, 15, 16, 23
[43] Victor Letzelter, David Perera, Cédric Rommel, Mathieu Fontaine, Slim Essid, Gaël Richard, and Patrick Perez. Winner-takes-all learners are geometry-aware conditional density estimators. In International Conference on Machine Learning, ICML, 2024. 3, 15, 23
[44] Chenda Li. Jing Shi, Wangyou Zhang, Aswin Shanmugam Subramanian, Xuankai Chang, Naoyuki Kamo, Moto Hira, Tomoki Hayashi, Christoph Boeddeker, Zhuo Chen, et al. Espnet- se: End-to-end speech enhancement and separation toolkit designed for asr integration. IEEE Spoken Language Technology Workshop, SLT, 2021. 9, 26
[45] Stuart Lloyd. Least squares quantization in pem. IEEE Transactions on Information Theory, 1982.
[46] Yi Luo, Zhuo Chen, and Takuya Yoshioka. Dual-path rnn efficient long sequence modeling for time-domain single-channel speech separation. In IEEE International Conference Acoustics, Speech and Signal Processing, ICASSP, 2020. 9, 27,28 28
[47] Yi Luo and Nima Mesgarani. Conv-tasnet: Surpassing ideal time freeufrey magnitude masking for speech separation. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2019. 27, 28
[48] Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan. The planar k-means problem np-hard. Theoretical Computer Science, 2012. 15
[49] Osama Makansi, Eddy llg, Ozgun Cicek, and Thomas Brox. Overcoming limitations of mixture density networks: A sampling and fitting framework for multimodal future prediction. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR, 2019. 1, 2, 29
[50] Amparo Marti, Maximo Cobos, and Jose Lopez. Automatic speech recognition in cocktail- party situations: A specific training for separated speech. The Journal of the Acoustical Society of America, JASA, 2012. 9, 26
[51] Neri Merhav. distorrioo function via minimum mean square error estimation. lEEE Transactions Information Theory, 2011. 20
[52] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 1953. 2, 22, 23
[53] Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2012. 22
[54] Sriram Narayanan, Ramin Moslemi, Francesco Pittaluga, Buyu Liu, and Manmohan Chandraker. hivide-and-conquer for lane-aware diverse trajectory prediction. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR, 2021. 1,
[55] Elias Nehme, Rotem Mulayoff, and Tomer Michaeli. Hierarchical uncertainty exploration via feedforward posterior trees. Advances in Neural Information Processing Systems, NeurIPS, 2024. 22, 23
13

---

[56] Gilles Pagès and Jacques Printems. Optimal quadratic quantization for numerics: the gaussian
case. Monte Carlo Methods and Applications, 2003. 3, 15
[57] Gilles Pages and Jun Yu. Pointwise convergence of the lloyd algorithm in higher dimension.
SIAM Journal on Control and Optimization, 2016. 15
[58] José M Pena, Jose Antonio Lozano, and Pedro Larranaga. An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recognition Letters, 1999. 1
[59] Kenneth Rose. A mapping approach rate-distortion computation and analysis. IEEE Transac- rions on Information Thheory 1994. 2, 5, 6, 8, 20, 22
[60] Kenneth Rose. Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proceedings of the IEEE, 1998. 2, 5, 7, 21
[61] Kenneth Rose, Eitan Gurewitz, and Geoffrey C Fox. Statistical mechanics and phase transitions
in clustering. Physical Review Letters, 1990. 2, 4, 4, 6, 7, 15, 21
[62] Kenneth Rose, Eitan Gurewitz, and Geoffrey C Fox. Vector quantization by deterministic annealing, IEEE Transactions Information Theory, 1992. 2, 4, 15
[63] Christian Rupprecht, Iro Laina, Robert DiPietro, Maximilian Baust, Federico Tombari, Nassir Navab, and Gregory D Hager. Learning in uncertain world: Representing ambiguity through multiple hypotheses. In International Conference on Computer Vision, ICCV, 2017. 1, 2, 3, 4,
5, 8, 15, 23, 29
[64] Claude E Shannon et al. Coding theorems for a discrete source with fidelity criterion. International Convention Record, IRE, 1959. 2, 20
[65] Cem Subakan, Mirco Ravanelli, Samuele Cornell, Mirko Bronzi, and Jianyuan Zhong, Attention all you need in speech separation. In IEEE International Conference on Acoustics, Speech and Signal Processing. ICASSP, 2021. 9
[66] Hideyuki Tachibana. Towards listening to 10 people simultaneously: An efficient permutation invariant training of audio source separation using sinkhorn's 's algorithm. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, 2021. 29
[67] Kai Tian, Yi Xu, Shuigeng Zhou, and Jihong Guan. Versatile multiple choice learning and its application to vision computing. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR, 2019. 2
[68] Efthymios Tzinis, Zhepei Wang, and Paris Smaragdis. Sudo rm-rf: Efficient networks for universal audio source separation. In International Workshop on Machine Learning for Signal Processing, MISP, 2020. 28
[69] Andrea Vattani. K-means requires exponentially many iterations even in the plane. In Annual symposium on Computational geometry, SoCG, 2009. 15
[70] Emmanuel Vincent, Rémi Gribonval, and Cédric Févotte. Performance measurement blind audio source separation. IEEE/ACM Transuctions on Audio, Speech, and Language Processing, 2006. 10, 26
[71] Thilo Von Neumann, Keisuke Kinoshita, Mare Delcroix, Shoko Araki, Tomohiro Nakatani. and Reinhold Haeb-Umbach. All-neural online source separation, counting, and diarization for meeting analysis. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, 2019. 9,26
[72] DeLiang Wang and Jitong Chen. Supervised speech separation based on deep learning: An overview. JEEE//CM Transactions on Audio, Speech, and Language Processing, 2018. 26
[73] Thong-Qiu Wang, Samuele Cornell, Shukjae Choi, Younglo Lee, Bycong- Yeol Kim, and Shinji Watanabe. Tf-gridnet: Making time-frequency domain models great again for monaural speaker separation. In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, 2023. 9
[74] Kenneth Zeger, Jacques Vaisey, Allen Gersho, et Globally optimal vector quantizer design by stochastic relaxation. IEEE Transactions Signal Processing, 1992. 23
14

---

Organisation of the Appendix
The Appendix is organized as follows. Appendix A presents the theoretical analysis of our algorithm. It begins with the introduction of the notations and the definition of the training scheme in Appendices A.1 and A.2 respectively. This is followed by an interpretation of the algorithm in terms of entropy- constrained alternate optimization in Appendix A.3. Appendix A.4 provides an analysis of the training dynamics of the algorithm in relation to rate-distortion theory. and Appendix A.5 discusses phase transitions. Connection with the literature and additional discussions are provided in Appendix B. Additional details and results from experiments on synthetie data and UCI datasets are provided in Appendices C and D. Finally, Appendix E offers an extensive description of the Source Separation experiment, including the impact of the number of hypotheses in Appendix E.3.2, and the analysis of phase transitions for this task in Appendix E.3.3.
A Theoretical analysis
A.1 Notations and motivations
Following the main paper notations, let A' C Rdi and y C Rdd denote the input and target spaces respectively. We will assume that X' and are bounded. We note p(z, y) the continuous density of a joint data distribution on X' x V. Let f = (fi...., fr) E Fe C F(X, )") denote the hypothesis models, which are families of n neural networks with parameters in O. Likewise, let
= (?1,.... : 7n) E Fer C F(X, [0, 1)*)) denote the score models, with parameters in O'. We will sometimes write F= F(X))))
We denote by A, the set of discrete distributions on n items conditioned by points on X x y (typically representing soft assignment of target the hypotheses). We denote by (4) the entropy of a distribution q. If q E An, we write (4)) = -Jxxy Σk= q(Kk|zr y) log g( Jz, v)p(r, yddddy.
If Z is a random variable with density p(z) and Y is another random variable, we define the differential entropy of Z as (Z) -E [lo (p( []]] and its conditional entropy as H Y)- - -E(2,r) [log[p( Z Y))]. Mutual information I Y) between two random variables Z and Y is defined as ((; = H(Z) - (V).
Let t E N denote training step, and tepoch E N U {oo} denote the number of training epochs. T + T(t)= 2 be a temperature schedule that decreases with the training step and verifies lim T(t) 0. Note that consider the temperature to be constant across epoch, with linear or exponential decrease between epochs. Let é y IR, denote an underlying loss function. We will restrict our analysis to the Fuclidean squared distance f(j, y) = yyy أ|| unless otherwise stated. For any vector rate schedule, that we note d
note z' as its vector transposition. Gradient descent involves learning
Multiple Choice Learning (MCL) aims at training the hypotheses (fi,..., fn) such that, for each input & E X. the hypothesis predictions (f1 (n.)...:.f((... provide an efficient quantization of the conditional distribution p(y x)) [63, 42, 43]. The quality of the quantization can be evaluated using the distortion:
J
D(f)
min ((fu(z))))p(.) y)),dy
(16)
Jxxy kE]l.n]
which can be seen generalization of the conditional distortion [56]. The two definitions coincide when p(y æ) is independent of x. Minimizing (16) is NP-hard [1, 10, 48]. The K-means algorithm, which is the standard approach for this task, can lake an exponential number of steps before converging [69], and is only guaranteed to find a local minimum in general settings [13, 7J. The same applies to WTA: due to its greedy nature, it can be trapped, at any point of its training trajectory, into local minimum that it will never manage to escape. One common issue is the hypothesis collapse [57, 18]. situation in which some of the hypotheses are left unused, therefore leading to a suboptimal configuration (see Figure 1).
To mitigate these issues, we introduce an annealed version of MCL. It can be seen an input- dependent version of deterministic annealing [61, 62]. Our training scheme is described in Appendix A.2.
15

---

A.2 Training scheme of aMCL
Let (z, y) be a training example sampled from p at step t. Our proposed annealed MCL training process is defined through the following subsequent steps:
1. Perform a forward pass through fi(x)..... (x())....
2. Compute the Boltzmann distribution (T(1) defined for each fx by
1 Zz
((f((a))))
n
e(fa(x))))
(fu)(fe x. -
exp
Zu,y Σ
exp
T(t)
T(t)
k=1
(17)
and detach it from the computational graph.
3. Perform gradient step the loss
C" Σ (ra))ff ()))(((())))))
(18)
Note that we used the same scoring loss Lacoring (4) in rMCL, the score-based method in [42]. In this paper, we extend the distortion D(f) to account for a distribution g on the hypotheses, and define the resulting soft distortion as
D(q,
(Lfa(z).)))4l |2, (o)p(x,))drdy
(19)
XXXY
When g = (T()), the soft distortion D(grc), f) corresponds to the expectation of the aWTA loss (18).
We will now introduce a decoupling assumption, which states that the family of models Fe is expressive enough to encompass the global minimizer of the soft distortion. Noting Dx J) the integrand of (19) over the X' integral, we can formalize this assumption follows.
Assumption 1 (Decoupling). We assume that the model family is perfectly expressive, i.e. Fe F.
Note that under this assumption, the global minimizer of the soft distortion D(g, f), minimizes the integrand of (19) for all X:
D(a inf D(a.f) = ( (EF(X.))) Dz(g. f) p(z)dr. FEFe
bq E An inf
(20)
(EF(X.
In the subsequent Sections, our goal is to analyze the aMCL training scheme and justify its design. Specifically, we show that annealing simplifies the optimization problem defined by (16). In Appendix A.3, first focus studying the properties of the soft distortion D(g. f)-
In the following, a E X' fixed and when the context clear, we will omit the dependency on the input and denote the hypotheses position (fi,..., E y
A.3
Soft assignation and entropy constraint
In this Section, we rewrite the assignation and optimization steps of aMCL as an antropy-constrainee block optimization of the soft distortion D(g, f). Noting HT = [[g]), we formalize this result with the following Theorem.
Theorem 2 (Entropy constrained distortion minimization). The assignation (17) and optimization (18) steps of aMCL correspond to block coordinate descent on the soft distortion. For all l E [1,n].
q argmin D(g,
(21)
9Ea..
H(o)2Hroo
fi t fx V D(g.f)
(22)
16

---

Theorem 2 is a corollary of the following Proposition, which provides additional intuition into the dynamic of aMCL.
Proposition 5 (aMCL training dynamic). For all T > 0, E F, strictly positive An. X and y E V, the following statements are true.
exp (-((f((z)) 9) /T)
(i) argmin D(g, 1) = QT qea.
4T (r(()) E (xp(([([_(()))))
Ak E [1,n]
Hr
fī(z) fy (.g x)dy
(ii)
grgmingeDD(y.l =
vk [1.m]
Sy Hht x. s)p(y x)dy
1= ft), a / a( y)y o)dy.
(ite)
vk [1.n]
Part (i) states that the softmin operator is the solution of the entropy entropy-constraiin constrained minimization of the soft distortion. Therefore, gradient- based optimization of D(g, f) along axis q is unnecessary, and we can directly use the closed-form expression in (i) for each temperature level T()), or equivalenty each corresponding entropy level (1)- Consequently, the optimization of D(g, f') reduces to the gradient-based minimization D D(qr(): f) along axis f for each temperature level (t)..
Part (ii) states that a necessary condition for the minimization of the soft distortion is that each fx is soft barycenter of the assignation distribution (2) for each temperature T. Part (iii) states that each gradient update moves f&r towards this soft barycenter fk. and that the update speed depends on the probability mass V of the points softly assigned to fx- Together, these results describe the training dynamics of aMCL. Let us prove these results.
Proof. (i) First observe that under the decoupling assumption, minimizing D(q, f) amounts to minimizing the integrand Dz(9, f) = Jy Σx=1 ((f((z), y)) æ, v)p(y æ)dy for each x E X (see (20)). When x is fixed, the distribution becomes a tuple of n scalars (g) (gi,...,9a) Ja), and the Lagragian of (21) writes
n
D Hr] +
Σ qk
-
Using the first-order necessary optimization conditions, we find that
{(fu.)) T(og((a)) +
+]++
HT H[g] = =0,
Σ 9k 1- 1= k=1
From this it immediately follows that \ = 1 + 1/ Ex= exp (- (-((p is normalization factor,
Do exp (- (- E exp (- (-17
f(fe.w))
((fa.)) T
is the Boltzmann distribution, and Hr H H(rr)
correspond to its entropy.
(it) Using the same reasoning than in (1) we set x X. Then each fr y becomes a simple vector. Observing that V Dx(g. (q. J) vanishes at the minimum of Dz(g, f') necessary condition to minimize D(g.1
V Dala, f) I de (sr. glfela v)p( axdy = 0fk
(23)
/ (Jr - w)g(falz, x)dy 0.
(24)
(25)
Then, as we assumed q > 0, we have
J3 g(fx 2x, x. v.v)p(y xddy > 0, and x. v)l( m)
fa(x) Jy v q(fk
(26)
Jy q(f x, z,y)p(v r)dy
17

---

(iii) It follows immediately from (iz) that
Dz (Ls alfulor 1 (ih
y bualla v)l( x)dy So (0alla, r)dy
22(' 12)
Before further analyzing the training dynamics of aMCL, let us pause examine a few properties
of the soft distortion (g. First, observe that the hard distortion D(f) given by (16) is particular case of soft distortion D(g, f) where {[fa[æ, y) 1[k argmin segminseel.. (f) v)]. Second, ser D2(9r: f) and inf fe. D(qr, f) are non-decreasing functions of T. Third, entropy-
constrained soft distortion minimization (21) is equivalent to the minimization of the free energy
FQg. f) D(g. f) (H)
(27)
quantity defined in statistical physics, that will be analyzed in more detail in the following Section. Moreover, optimal free energy has a closed-form formula in our case. We group these observations in the following Proposition.
Proposition 6 (Additional properties of the distortion and the free energy). For all T E E Am I E &' and y, the following statements are true.
( q(f xz v) (1kk E argmin, ((fa(z), v)] kETILa + Vg' E An. D(g f) S D(d f) inf ff and D + inf D(gr, f) non-decreasing 10, co fEF
(ii) D T
JEF
(iit) min & fq. = $ (qr. f) = -T -T / xxx
Σ exp (- (_((f((e).)) p(x, y)drdy.
log
geA..
T
Proof. (i) Notice that argmin,g]1.nf (z), y) selects the hypothesis fa with lowest loss (ffa v). Therefore, for all of E An, omitting the æ dependency in the notations.
a(fulo)e(Fe.v)) = min ((kk.u) = Σ (Jelv) min e(S..v) S ((Lio))( R=1
kE[L.n]
sE[1.n]
1=1
R=1
We conclude by multiplying by p(a, y) and integrating over x y. (fi) Let us first show that for any E F, T + Dz(gr; J' is non-drecreasing. For that, let us define (TT) Ex (fe (ay)
(z),x(z), v)] - (f x, (f))),f(x)) y) for each > 0, N. E X XX,,
and f E F. to is a differentiable function of T, with derivative
Σ gr(Sn /.l0kl1,,,00000 (.1))((()))))) 21
(T))
Σ cr(Su 1 1))
T
1
[ [fff v)1 2 0.
T2
Therefore, &p is non-decreasing. By the growth of the integral, we deduce that T + Dz(q1 f) is non non-decra.sing.
Let 7" > T 0. Then Dz(yT > Du(gT, 2 inl Dalgr,I') for all ʃ E F, and by definition of the infimum, we have fnF DT(TT', f) 2 inl Dz(Tr: So D is a non- decreasing function of T, and the same reasoning applies to Dr. (iii) There are two equalities to prove. First observe that
F (4. = D(g. - (1) - HT)
T
Lagragian (21)
independent of
We deduce
argminges, f) argmin
-D - Hr] gT
18

---

which establishes the first equality. Then we conclude by substituting the definition of into I (qr. and simplifying the expression. Again, we drop the dependency the notations for readability.
f(rr,))= = / xxy xxy
Σ
(r 11) (e(fk.)) v) + Tlog (rk v)) p(,, y)drdy
((fk.v)
{(fa:
JxXY Σ fr (fxl
e(fk.v) -
log Σ
exp
p(z, y dzdd
T
T
s=1
sums
independent
B(fkr
-T
log
exp
(- T
p(a, v)drdy.
Note that the last equality can be written as:
-xXX log( (( J Foler, flp(x)dx
f)
(28)
where we define the conditional free energy F (gT f) as
Fx(UT, 1) -T / log Zn Zpy) xddy.
(29)
A.4 Rate distortion curve
We have established in the previous Section that aMCL moves the hypotheses fx towards the soft barycenter of soft Voronoi cells. We now describe the impact of temperature cooling on the position of these soft barycenters.
At high temperature, we observe that the soft barycenters (hence the hypotheses) converge towards the conditional barycenter E| X z] and fuze. When temperature decreases, they iteratively split into sub-gnu uub-groups. To capture the virtual number of hypotheses, we introduce the conditional rate-distortion function
R₂ (D') &
min gEA Delg.fiSD*
LY;;)),
(30)
where the target Y ~ p(y x). the hypothesis position y q(fi x) follows a distribution over y with g(xx x) = fy a(hx k4,8)p(s æ)dr, and I2(Ý; LÝ;; is their mutual information.
The following Proposition shows that (30) corresponds fact to the same optimization problem as minimizing the conditional free energy (29), and therefore as minimizing the entropy constrained distortion (21) conditionally on x. then describes the shape of the parametric curve (D*, (D))))),, and provides lower bound of the rate distortion. For this purpose, we introduce for each æ E X
fiey Dmnax inf / ((f1.8)d x)dy - !(E = x).v))(( xy
(31)
the optimal conditional distortion when using single hypothesis.
Proposition 7 (Rate-distortion properties). For each x E X, we have the following results.
(i) For each T > 0, minimizing the free energy
-((r)))-TH(r) TH()r)
(32)
over all hypotheses positions I E F(X,y") comes down solving the optimization problem that defines (10) for each X under decoupling Assumption I.
19

---

(ii) Rs is non-increasing. convex and continuous function of D R2(D") = 0 for
D 2 D and for each x the slope can be interpreted as R (D*) -T when is differentiable
(iii) For each n, R2(D") is bounded below by the Shannon Lower Bound (SLB)
R2(D") 2 SLB(D") & - ((Y)-H(D)
(33)
where Y p(y ax) and (D))) is the entropy of a Gaussian with variance D
These results are well-known properties of the rate-distortion function [11, 4, 24, 51, 6].
Proof. (i) Under the decoupling assumption 1, optimizing & comes down to optimizing Ag for each a E X. Consequently, we can use the known relationship between the rate-distortion curve and free energy minimization [4, 24, 59].
(it) See [4, 24].
(iti) See [64].
key characteristic of the SL.B its asymptotic tightness in the low distortion regime for a broad range of probability distributions [32]. For some distributions, such the Gaussian case, the SLB and the rate-distortion curve align perfectly for D < D=
The Rate-Distortion interpretation of aMCL applies for each x, but defining notion of global rate that is independent of the input is more challenging. This because the distortion optimal distortion at given temperature level T, inl (2(T J), can vary across inputs x. This is left for future work.
A.5
First phase transition
In the previous Section, mentioned that aMCL predictions fuze high temperature into the conditional barycenter Y X = =x]- Moreover, these fuzed predictions iteratively split as the temperature (or equivalently the distortion) decreases during training. With each split, the number of sub-groups formed by the hypotheses increases. The number of sub-groups, measured in bits, captured by the rate-distortion R. (D*). In this Section, we focus on the critical temperature corresponding to the first of these splits.
The predictions fuze into single point at high temperatures so that the number of sub-groups is and Ry (D*) = in this regime. The first splitting therefore occurs when Rg (D*) > 0. Correspondingly, define the first critical temperature in Definition 1.
Definition 1. The first critical temperature [ each x and the defined global variant Tÿ are defined as:
(x) (x) A inf T
inf Dz(gr,
max
(34)
fEF
Te
A inf
T
inf D(gr, f) 2 Dmax
(35)
fEF
the conditional and the non-conditional setting, where Dmax A Pxx) D dxr and D defined in (7).
Note that we have also equality in the definition Tz(x) = inf {T jer Dx f) = Dmaa since inf fer (g(gr, f) < Dmmxx Moreover, recalling that D T + inf Da f) is non- decreasing function (Proposition (ii)), we can equivalently define (x) as the generalized inverse (x) (Dt)= (Dmax) (e.g., Definition 1 in [17]). The same observations hold for TÇ.
We also know that aMCL's predictions implicitly minimize the free energy (27) (see Proposition part (i)). Therefore, the conditional barycenter E|Y|X = xx] is stable as long as the Hessian of the free energy is positive definite. This observation can alternatively used to define the first critical temperature.
20

---

Interestingly, all these definitions are equivalent, shown by the next Proposition. For this purpose, let us introduce the following covariance matrices:
(R,AU. (1(l)) ())((x)) -M000a))((000--0000))))-))---)-- u)¹ gly [k,z))(y x) dy
where g(y fu; x) denotes the posterior probability assigning the point y to the hypothesis calculated using Bayes's 's rule [60]. At high temperatures, all hypotheses merge into the conditional barycenter of the distribution (9), and the matrices Cs.k are equal to the data covariance matrix C(r) (xx(xxy)==px..)) IY X x].
Proposition 8 (First critical temperature). We have the two following results.
(i) We know from [61] thatfor all X, (z(2) 2)max(C(x)).
(ii) Under decoupling assumption TD suprex Amax (C()).
Proof. (i) See [61].
(ii) Let T = suprex (x)). By definition of To(x) and due to Proposition (iz). inf SEF D2(gr, 2 sEF D2 (2rg(e)) Dmaxx for all X. Then, deduce from (20):
inf D(gr. inf / Delar.fl(zzdda feF
f inf Dalar, 2 D p(x)d, FEF
FEF
inf D(gr. Dmax
FEF
Using (i), we can write:
To = inf { T inf D(gr, 2 Dmax
ST sup (x)
JEF
We now analyze why the predictions converge towards the conditional barycenter E = x2. In the next Proposition, first focus the asymptotic regime, when the temperature T increases to infinity, and then extend this analysis at finite temperature.
Proposition 9 (Training Dynamics with Temperature). For all x E X and all l E [1, n]. we have the following properties.
(i) If T = x and f E argminges f), then fu(x) = E[Y X = x].
(ii) The gradient of the soft distortion can be re-written for each T > 0 as
De = yy Σ [1fx(z)
-11 -18l-1l)
(fa(z) 3) Zn (T) p(y x)dy.
(36)
T
Therefore, the first order approximation of V Dr in T writes:
V De T-100 / (f((z) - y)p(y x)dy + (1)
(37)
When T' + oc, aMCL reduces to standard risk minimization, so that a necessary condition of optimization is that all the hypotheses fxx are located the conditional barycenter E[ (Proposition 9, part (i)). This conditional barycenter is stable and corresponds to the global minimizer of the aMCL training objective when T co. We further analyze the force that pushes all the hypotheses toward this conditional barycenter, by looking at an expansion (36) of V f D. which provides the direction of the hypotheses updates
each T - oc, we see that global driving force, to which all the data points contribute, is pushing the hypotheses toward the barycenter (37). As decreases, local interactions corresponding to the higher-order terms appear and increase in amplitude. They responsible for the phase transitions.
0 (Proposition part (ii)).
21

---

Proof. (1) By definition of the Boltzmann distribution
exp (-<(fe()).
qr(fu x2 = Σ exp (- w)/ T-
Therefore D(gr, f) T-+00
Ek- ly (ff(())) v)p(y 2)dy, and all the hypotheses solve the
same quantization problem. necessary condition to minimize D(gr, f) then
vk [1. (x) E|
(it) We note (T) Et= exp (-1 f1) /T/ Then, accounting for the stop_gradient
operator in (6), the gradient of the soft distortion writes
Si D2(1r, 1) = / exp (-11:(())-v11//1 /T²
(Sa(x) - y)p(y I x)dyy.
(T)
Using the series expansion of the exponential, we have for each T O,
exp (-1 (-15A(x) vll
[lfx(z) - u11
T
T
We can rewrite the gradient of the soft distortion:
VDD =2 2 r!
/
[ff())) v11
(fa(z) ply xxdy
Zn (T)
Keeping only the first term, and observing (T)
71 we get:
T-200
V D2 = 20 / (fa(z) - y)p(u 1xd
This Section focuses on the first phase transition. However, multiple phase transitions may occur during training, as shown in Figure interesting to note that, for deterministic annealing, the final phase transition occurs when the rate-distortion curve hits the Shannon Lower Bound defined in (33) (see [59]).
B Connection with the literature and discussion
B.1 Annealing at inference time
promising direction for future research consists in using annealing at inference time. With this scheme, aMCL could be used to perform input-dependent hierarchical clustering [53] test time, similarly to the idea proposed in [55]. More precisely, we can store the model's parameters at different times of the training schedule (i.e., several temperature levels). During inference, this allows replaying the temperature cooling for new test samples, by performing forward passes through each of the trained models.
Replaying this trajectory may have several advantages. Indeed, the hypotheses trajectory follows the dist-rittttion curve and consequently explores recursively the modes of the distribution as the temperature decays. Crucially, at each critical temperature, when the hypotheses are about to split, they exactly located at the barycenter of these modes. If we can track these splitting moments, for instance by counting the number of distinct virtual hypotheses at each step of the cooling schedule, can perform a hierarchical clustering that iteratively uncovers the modes of the distribution.
B.2 Discussion on Stochastic simulated annealing
Non-deterministic simulated annealing [28, 52] a promising research direction due to its strong convergence properties (see Hajek theorem [26]). It requires to define the state ff of the system and
22

---

the optimization objective D(f). At each step, the state f is updated to neighbor state f based on stochastic exploration criterion. The probability of accepting neighbor state f depends on the objective variation D(J) - D(J) and the temperature T.
Our objective Dff) corresponds the Distortion (1), However, the state of the system can be defined in various ways. In the non-conditional setting, [74] defines the state as the hypothesis positions (fe))e]I.nn (similarly to the present work), while [26, 28, 52] defines it as the cluster assignation of each dataset sample.
In both cases, we expect that storing and updating this state using neural networks would be costly. Moreover, evaluating D(f) requires going through validation set, which is time-consuning. Further investigation in this direction is left for future research.
B.3 Comparison with an additional baseline: Relaxed WTA with annealed e
Relaxed WTA [63] suffers from a bias toward the barycenter. As suggested in [55], natural idea to tackle this issue would be to anneal e during training. In Figure I, we have shown the results of this additional baseline on Gaussian synthetic dataset, using linearly decreasing epsilon during training s(t) = Eo (1 1000) with Ey = 0.98.
In Figure 5, we show its training trajectory when using the same setup as in Figure 1. All hypotheses initially converge to the barycenter. then the winners gradually move towards the modes as decreases. As approaches O, only few additional hypotheses escape from the barycenter to reach the modes, indicating that annealing does not solve the collapse issue of Relaxed- Selaxed-WTA.
Results on the UCI datasets confirm this qualitative analysis (Table 5 and Figure 6). Figure 6, aMCL outperforms the best Relaxed-WTA, variants on Distortion.
E 0.98
E 0.92
E 0.52
E 0.049
E 0.00098
Figure 5: Training dynamics of Relaxed-WTA with annealed. Predictions during training of WTA with annealed linearly over 1000 epochs. We use the same setup as in Figure I of the main paper, with 49 hypotheses as shaded blue points (shade proportional to the predicted scores), and the targets as green points. For large e, the hypotheses converge at the distribution barycenter. As decreases, three Winners gradually move towards the barycenter of the Gaussians. When approaches 0, the Winner-Take-Al dynamic prevails and some hypotheses escape the barycenter to reach the Gaussian modes. However, the modes are quickly saturated, the unused hypotheses stop receiving gradient, and they remain stuck at the barycenter.
C Experimental details in the synthetic data experiments
This Section provides detailed description of the synthetic data experiments presented in the paper, particularly the results and visualizations in Figures 1, 3 and 4. Note that for each of those experiments, a two-hidden-layee Multi-Layer Perceptron (MLP) with 256 neurons per layer and ReLU activation functions was used, except for the last layer. The final layer of the MLP was duplicated to account for multiple hypotheses (fa())) (followed by a tanh activation to restrict (followed by sigmoid activation), similar to
the output in the square [-1, 1J3)) and scores [42, 43], with n = 49 hypotheses in this study. At each epoch, 100,000 points were sampled from the corresponding synthetic datasets, and the models were trained for lepoch 1000 epochs. Note also that the visualization of the output space in Figure and Figure 4 is restricted to the square [-1, 1)2.
Settings of Figure 1. In this Figure, the dataset consists of a mixture of three two-dimensional Gaussians located at μg (-0.5, -0.5), #n (0, 0.5) and #2 (0.5, -0.5), each with standard
23

---

deviation of 0.1. In this Figure, each model was trained with Stochastic Gradient Descent optimizer with a constant learning rate of 0.01. For the Relaxed WTA run, we used 0.1, and for the Annealed MCL. run, we used an exponential scheduler in the form T(t) = Top', with To = 0.6 and p 0.99.
Settings of Figure 3 and Figure 4. In these experiments, the dataset is conditional variant of that used in Figure 1, with ground-trure distribution of the form pyy | x)
Zi=0 (z), o"), with = 0.1, (x)x) = =pe for x E [0, 1]. and H4 is defined as above for E [0. 2|. Here. aMCL was trained with a linear scheduler defined by T(t) = To Iupochs with To = 1.0. Note that in the results of Figure 4, we have (+1. &3. t4) (50, 745, 870, 1000) with associated temperature values (T(t,), (tt,) (ta)), T(ta)) = (0.950, 0. 25, 0.131, 0.001). Here, aMCL was trained with Adam optimizer [34], with a constant learning rate of 0.01. In Figure 3, TV (upper bound) correspond the right-hand-side of (15) and was computed as 2Amax (fy p(y x 1)dy) = 0.46, approximating the covariance matrix over 1,000 samples. Note that the distortion plotted in the curve of Figure corresponds to the hard distortion (1) averaged over validation set of 25,000 samples every 5 epoch.
D Additional results from UCI Datasets experiments
The UCI Regression Datasets [15] serve as standard benchmark for conditional distribution estima- tion. This Section provides additional details and results from the experiments presented in Section 5.1.
Experimental setup. The experiments were conducted using the protocol from [29]. Each dataset is divided into 20 train-test folds, except the protein dataset, which had 5 folds, and the Year Prediction MSD dataset which used a single test-set split. We used the same neural network backbone for each baseline: one-hidden layer MLP with ReLU activation function, containing 50 hidden units except for the Protein and Year datasets, for which 100 hidden units were used. In the WTA models, the final layer of the MLP was duplicated to account for multiple hypotheses {f (x) (followed by no activation) and scores {2)( (followed by sigmoid activation). The WTA-based methods (Relaxed-Me MCLL, MCL, and aMCL) were trained with n 5. All models were trained with the Adam optimizer over 1,000 epochs with a constant learning rate of 0.01. The data loading pipeline was adapted from the implementation of [27]. The best models for each dataset are highlighted in bold in Table 2 and Table 1, with the second-best models underlined.
Baselines. Table 2 of the main paper includes results from three baselines reported from Table I of [38], which we use as references for those benchmarks. 'PBP' stands for Probabilistic Back Propagation [29]. and 'MC-dropout" corresponds to Monte Carlo Dropout [21]. Relaxed-MCL was trained with 0.1 in Tables and 2. Other values of are experimented in Appendix D.2.
Metrics.
We used RMSE and distortion as metrics. RMSE is defined as RMSE = V 1 v where ú; denotes the estimated conditional mean, defined as EL=1 (=) for the WTA variants, and N is the number of samples in each test set. The distortion of the multi-hypotheses models was computed as Distortion | Ein,, min 11 110x~ w: kE]l.n]
N
Temperature scheduler. For training aMCL in those experiments, an exponential temperature scheduler was used, defined as T(I) Top', with p 0.95 and To 0.5, where / denotes the current epoch and lepach = 1, 000 is the maximum number of epochs. When the temperature of the exponential scheduler was lower than 5e 4, we set the training back to the vanilla Winner-takes-all mode.
Evaluation details. During the evaluation, following [29]. both input and output variables were normalized using the training data's 's means and standard deviations. For evaluation, the original scale of the output predictions
restored using the transformation f (z) H Ptrain + ftrain (x) where Merain and Train are the empirical mean and standard deviation of the output variable, computed across the training set.
The results concerning the distortion metric on the UCI datasets are presented in Table 1, and their analysis is provided in Section 5.1.
24

---

D.1 Impact of the scheduler type in aMCL
The impact of the scheduler type on the performance on the UCI dataset provided in Table 4. We see that for large dataset sizes, the exponential scheduler outperforms the linear one. Further study on the impact of the speed the scheduler on the performance left for further work.
Table 4: Impact of the scheduler type in aMCL. We display the results on the UCI datasets comparing two types of temperature schedules aMCL. Here, both use an initial temperature To = 0.5. aMCL (exp) uses exponential scheduler of the form T()) = Top', " with 0.95, and aMCL (lin) uses a linear scheduler (()) = To Eepact
The rows are ordered by dataset size N.
RMSE (4)
Distortion (4)
Datasets
aMCL (exp)
aMCL (lin)
aMCL (exp)
aMCL (lin)
.V
Year
9.08 + NA
9.20 E NA
4.46 + NA
4.50 + NA
513345
Protein
4.25 + 0.02
4.26 + 0.04
0.77 + 0.03
0.92 + 0.06
45730
Naval
8.00e-4 4.04e-4
1.72e-3 1 1.71e-3
5.37e-7 + 3.83e-7
3.97e-6 1: 1.36e-5
11934
Power
1: 0.20
4.07 0.16
2.18 0.64
13.24 2.88
9568
Kin8nm
0.08 + 0.00
0.08 + 0.00
6.81e-4 + 8.14e-5
2.94c-3 + 1.80c-3
8192
Wine
0.63 + 0.04
0.67 0.05
0.03 + 0.01
0.09 + 0.02
1599
Concrete
5.47 + 0.67
4.99 + 0.63
5.71 1.72
10.18 + 4.55
1030
Energy
1.35 + 0.97
0.80 = 0.33
0.28 + 0.09
0.55 0.51
768
Boston
3.05 = 0.91
3.12 0.68
2.69 +
6.18 +
506
Yacht
1.62 + 0.53
0.85 0.25
0.97
0.51 0.37
308
D.2 Impact in Relaxed WTA
RMSE compares the barycenter of the predicted distribution with the target positions. For this metric, Relaxed-MCL, outperforms other approaches on the UCI datasets when high (see Table 5 and Figure 6). This outcome is expected, as Relaxed-Wi -TTx is biased towards the distribution barycenter under this regime (see Figure of the paper).
However, using RMSE for comparison discards valuable spatial distribution information of the hy- potheses. Distortion, defined in (1), addresses this limitation by measuring quantization performance, which our theoretical analysis is based on. When focusing on the Distortion metric, Table 5 shows that lower values of epsilon (e.g., E 0.1 annealed epsilon) consistently perform better than for
0.5 across nearly all settings. This improvement is attributed to the reduced bias toward the barycenter this configuration. Additionally, for Distortion, aMCL. (trained with an exponential scheduler) generally outperforms Relaxed-Wi WTTA on the UCT datasets for the tested Relaxed WTA variants (see Tables 1, 5 and Figure 6). This is especially true on large datasets (Year, Protein).
Overall, aMCL demonstrates strong balance between Distortion and RMSE compared to the baselines, especially on the largest datasets. Figure further supports this trend, providing additional analysis on Year and Protein, where aMCL, MCL, and Relaxed-MCL. are compared across different values the (RMSE, Distortion) space.
Table 5: Impact of s in Relaxed- WTA on UCI regression benchmark datasets comparing RMSE and Distortion. Best results are bold, second bests are underlined. The annealed version of Relaxed- WTA (R- (T-W uses a linear scheduler starting at Eg = 0.5 and decreasing to O.
RMSE (J)
Distortion (L)
R- te 0.5)
R-WTA 0.1)
R-WTA (5 unnealed)
R-W-TA (5 0.5)
R-WTA (E 0.1)
R-WTA ( annealed)
Year
+
NA
1445 NA
4.89
515145
Noval
147e:3 7.47e44
1.00-3 5.60e-4
2.08c-3 8.49-4
1.13e-6 4: L.55-6
4.2ce-7 2.36e-7
7.70p-7 7.85e-
11934
Power
3,99 i: 0.16
1.02 0.1.8
4.10 1.001100 0.14
7.69 1. 1,26
2.95 J: 0.91
4,26 1 2.28
9568
KinSam
7.68e-2 1.89e-
7.80e22 91e:3
8.61c-2 1. 25c-3
2.82c3 1. 09c-l
9.32g-1 7.97-5
9.06e-4 3.89e-4
8192
Concrete
4.91 0.65
5:28 0.58
5.14 0.56
15.08 5.11
6.91 2.81
7.40 3.12
1030
Energy
1.03 0.21
1.61 1.111:000 0.36
T48 0.59
0.40 0.13
0.30 0.12
0.33 0.10
768
Boston
285 4 0.57
288 + 0.72
2.30 I.69
5.95 2.94
3.32 2,84
3.73 + 2.38
S016
2.53 1.04
1173 0.49
308
25

---

Year
Protein
85-
11:3
MCL
MCL
aMCL
aMCL
Annealed Relaxed WTA (co 0.5)
6-
Annealed Relased WTA (6u 0.5)
Relaved WTA
Relased WTA
Distartion
Distortion
00
0.1
0.1
1155
3-
3.900
8.000
8.775
0.005
5:000
9.073
9.100
3.30
1.20
(.30
0.35
1.10
6.05
4.00
RMSE
RMSE
Figure 6: (RMSE, Distortion performance on Year and Protein datasets, for Relaxed- WTA with E (0.05, 0.1, 0.2, 0.5) (blue points, with black error bars for std), Relaxed-WTA with annealed (purple) and aMCL (red). Blue lines link the Relaxed- WTA score points. We see that aMCL is below and left of these lines, which indicates good tradeoff those two datasets.
E Application to speech separation
This Appendix provides a detailed description of the speech source separation experiments. Speech separation consists of isolating the audio signals of each individual speaker from a mixture in which they are simultaneously active. This task is major interest for speech processing applications such as Automatic Speech Recognition [50, 44], Speaker Diarization [71], singing voice extraction from music [31]. Most of the recent speech separation systems are deep neural networks trained in a supervised setting, where the ground truth of the separated speaker tracks is known [72].
E.1 Task description
Formally, let y/..... Vm Re denote the raw speech signals from m individual speakers, with I denoting the number of time frames in the corresponding audio recordings. Under anechoic (no reverberation) and clean (no background noise) conditions, the mixture can be expressed as Th
- Vs- Hence, the task is to provide estimates ....... 2m of the isolated speech tracks from mixture signal æ using neural network fa. The quality of the estimation E(jx:: ys) is commonly measured using the audio-domain distance Signal-to- Distortion
signal-to-Distortion Ratio (SDR) and its scale-invariant
(SI) variant SI-SDR [70, 39J. Since there a fundamental ambiguity concerning the best association
tk + Vss separation systems are trained using the Permutation Invariant Training (PIT) loss:
(ú. v) min Seep
PIT
((oo(s), yo)
(38)
m
where E is the set of permutations of [1, m].
Instead, we propose use the MCL framework solve this assignment problem. Naming CMCL the resulting loss, L its annealed variant, and (Relaxed-We WTA its relaxed variant, we define sep
MCL. (0.y) = sep
1 min
l(gk. k
(39)
1 m
CaMCL (j.y)
(rn 1v) ( ys).
(40)
see
m
Rolaxxd WTA (0.y) sep
1
qe Cūx yo ys) vo)
(41)
m71
(1 (1 (e/nn-
if = argmin:eee..l. ((w
where go vz)
otherwise
26

---

This gives the separation task new interpretation: the targets Us are samples drawn from common distribution pyy z) conditional on the mix 2, the estimated speech signals yr f&. (x) are the output of neural networks SK, and the mix æ is their common input.
Notice that (39) is subject to collapse. Furthermore, when m, (38) always finds the best assignation, and acts as topline, while MCL acts as baseline. The goal of these experiments is therefore threefold:
applying proposed aMCL algorithm more realistic and data-intensive setting; extending the analysis of aMCL more general setting where the underlying metric (SI-SDR) is non-Euclidean;
ensuring that MCL is valid substitute for PIT in the context of source separation, thus opening up a new avenue for MCL research this domain.
E.2 Experimental settings
E.2.1 Separation model architecture
We use the Dual-Path Recurrent Neural Network (DPRNN) [46] separation architecture for our experiments. This model follows the encoder-masker- masker-decoder structure, originally proposed in ConvTasNet [47]. Each component of the network is described below:
Encoder. The encoder transforms the raw audio signal E Rd, with / the number of time frames, 1-D convolutional layer with channels, kernel
into a sequence of features. It implemented size K, and stride S. It outputs the sequence X E RxT where 7 is the number of encoded frames.
Masker. The masker of the DPRNN model first applies sliding window of width W the sequence of encoded features X. The input sequence is transformed from R x2 to X' E R xPxxxx where P the number of windows. DPRNN composed of two recurrent layers, processing the sequence X' over two different directions (dual-path)
intra-chunk: processes the dimension W,
inter-chunk: processes the dimension P.
Thus, the model learns local and global dependencies. The RNN is implemented as a bidirectional Long Short-Term Memory layer (LSTM) with hidden dimension H. The sequence X' is processed by B successive DPRNN blocks. The output of the last block is denoted x" e #xxx X Before decoding, the sequence is mapped back to the original dimensions using overlap-and-add. convolutional layer maps the sequence X" to the masks M E Fx" where n is the number of predictions. The k-th source latent sequence Ý, = M2 @ X is inferred by the element-wise product between the k-th mask M2 and the encoded sequence X.
final
Decoder. The decoder is implemented as a 1-D transposed convolutional layer with n groups, F channels, and a kernel of size K and stride S. It maps the latent sequences Y E R to the audio domain, and note ý Rexl the corresponding vector. Therefore, using the MCL framework notations, the output of the prediction model is fx(x)) = ÿk-
Scoring. We do not use scoring models in these experiments. Indeed, we will focus on the case where n = m and all predictions should be matched a corresponding source. This ensures fair comparison with the PIT baseline, which uses the same setting.
The model configuration used for our experiments is presented in Table 6. It corresponds to the model configuration from the original paper. The variables I, T, and P, which depend on the unknown input length 1, are not specified.
E.2.2 Training configuration
Dataset. The source separation experiments are conducted on the Wall Street Journal mix dataset (WSJO-mix) [30] which is the current benchmark dataset for speech source separation. It consists of clean utterances of read speech linearly combined build synthetic speech mixtures. Several versions of the dataset are available to separate from 2-speaker to 5 5-speaker mixtures. In the present
27

---

work, we focus on the 2- and 3-speaker scenarios. Each version features 20000, 5000, and 3000 mixtures for training, validation, and testing respectively. The audio signals are samples 8kHz. Training objectives. Four types of systems are compared in the following experiments:
PIT: training with CPIT defined in (38),
sep
MCL: training with sep defined in (39).
aMCL: training with LaMeL defined in (40),
Relaxed-WTA: training with - -TA defined in (41).
Soo
We the SI-SDR score as the separation quality measure
(y. 5)²
fly 0) = 10 1og
(42)
(y.0)²
where (.--) denotes the scalar product on R'
Training parameters. The separation models trained 5-second audio segments. Since the utterances from the training set might have a longer duration, 5-second segments are randomly cropped inside the training utterances. The utterances shorter than 5s removed. The batch size is set to 22 to reduce training time compared to the standard setup [47, 46, 68), in which a batch size of 4 used. We verified that our models match the originally reported scores [46] when using this original setting. To analyze robustness to initialization, we train each method with different seeds, and report the inter-seed average scores and standard deviations. More precisely, the prediction scores are first averaged across the evaluation dataset for each single seed. Then these dataset-wise scores are used to compute the final average and standard deviations. Each model is trained on tepoch 200 epochs, without early stopping. All the training set is processed during each epoch. Unless otherwise stated, the temperature scheduler chunk linear:
T(t) To (1
t (1-
1[t < fmax]
(43)
Emax
with initial temperature To = 0.1 and fmax 100. Note that the end of the training, when I E [lmaxs (epoch]. annealing is disabled by setting T()) = 0 in order to fine-tune the hypotheses on the target MCL objective.
The neural network weights are updated using the Adam optimizer, with a learning rate set to 10-3 The learning rate is halved after every epochs with no improvement in the validation metric. Separation models are trained on Nvidia A40 GPU cards. The DPRNN has 3.7 million parameters.
Evaluation. The separation scores computed the evaluation subset of the WSJO-mix datasets. Two types of scores are presented:
PIT SI-SDR: the assignment performed with PIT (38) as standard source separation approaches;
MCL SI-SDR: the assignment is performed with MCL (39), and this score can be seen as a form of quantization error.
Table Configuration of the DPRNN model used for source separation experiments.
Parameter
Symbol
Value
Feature dimension
64
Encoder/decoder kernel size
K
16
Encoder/decoder stride
DPRNN Chunk size
W
100
Hidden dimension
128
Number of DPRNN blocks
B
6
28

---

E.3
Experimental results
This Section presents the results of the experiments conducted on speech separation with the aMCL framework, and is organized as follows:
Appendix E.3.1: comparison of the separation performance of each approach;
Appendix E.3.2: impact of the number of hypotheses on the separation performance with MCL and aMCL;
Appendix E.3.3: analysis of the phase transitions of aMCL in the context of speech separa- tion.
E.3.1 Separation performance on and 3-speaker mixtures
Table 7 shows the average score of each separation model in the 2- and 3-speaker scenarios.
First, we observe that PIT and aMCL. achieve similar performances, both in terms of the average PIT SI-SDR and MCL. SI-SDR scores, and both in the 2- and the 3- speaker settings (see lines 1 and 3 of Table 7). Looking at the inter-seed variance, we further see that the differences in performances between these approaches are not significant. Note that MCL and aMCL have (mm) complexity, while PIT is (m))) with the Hungarian algorithm [16]. Therefore aMCL reaches the same performance PIT with a gain in terms of complexity. Further work includes an analysis of this complexity gap when the number of speakers is high, similarly to [66].
Second, see that aMCL achieves better performance than MCL in the 2-speaker scenario, both in terms of PIT SI-SDR and MCL SI-SDR metrics (see lines 2 and of Table 7). More precisely, we see that this performance discrepancy between MCL and both PIT and aMCL is due higher variance of the MCL training method. In fact, MCL has a higher inter-seed variance than aMCL and PIT in all settings. Indeed this method known be sensitive to initialization [49, 633. In contrast, that aMCL is more robust to initialization, having a lower inter-seed variance and higher average score. This phenomenon was highlighted in Section A, which provided theoretical analysis of the Euclidean case. This experiment suggests that our conclusions hold even for the source separation task, where the underlying loss function is -uncldudd.....
see
In the subsequent Sections, we further study these two claims. In Section E.3.2, we demonstrate the advantages of aMCL over PIT by letting the number of predictions exceed the number of sources m. In Section E.3.3, we show that other conclusions of our theoretical analysis concerning phase transitions also seem hold in the non-Euclidean setting.
Table 7: Comparison of the training methods PIT, MCL, and aMCL, for the task of source separation of and speakers. The performance measured using the PIT SI-SDR metric (lefi) and the MCL SI-SDR metric (right) computed on the WSJO-mix evaluation subset. Each method is trained using three seeds and we report inter-seed average score and standard deviation.
(a) PIT SI-SDR (1)
(b) MCL SI-SDR (1)
Method 2 speakers
3 speakers
Method 2 speakers
3 speakers
PIT
16.88 + 0.10
10.01 + 0.04
PIT
16.88 + 0.10
10.04 + 0.04
MCL
16.30 0.59
10.06 0.21
MCL
16.30 0.59
10.09 0.21
aMCL
16.85 = 0.13
10.00 + 0.21
aMCL
16.86 + 0.13
10.04 + 0.20
E.3.2
Impact of the number of hypotheses in MCL and aMCL
In this Section, we study the impact of the number of hypotheses on the source separation perfor- mances. We focus on the 3-speaker scenario, and we increase the number of predictions. More precisely, we consider the cases n E {3. 5, 10). . If n 3, the number of hypotheses is the same as the number m of sources to separate. If n E {5, 10) case the number of hypotheses is higher. Since the number predictions and sources differ, it is not possible to compute the PIT SI-SDR metric, which is ill-defined in this setting. Therefore, we only present results for the MCL SI-SDR metric. In this experiment, we use a single seed across the considered methods to ensure a fair comparison. We report Bataset-wisc score statistics in Figure 7,
29

---

First, we observe that the separation performance increases as the number of predictions increases, both for MCL and aMCL. This shows that the additional hypotheses are effectively used by both methods, despite the risk of collapse convergence towards suboptimal configuration. Recalling that MCL,, aMCL., and PIT performances are similar in the case m 3, this demonstrates strong advantage of the MCL family compared to PIT. Indeed, we can improve MCL. SI-SDR score beyond what achievable by PIT training, by increasing the number predictions n. Moreover, this improvement comes minimal computational complexity cost, as discussed in Section E.3.1. This property can be exploited to handle settings where the number speakers is unknown. This is left to further work.
Second, we observe that there are no significant discrepancies between MCL and aMCL performances in this setting. This suggests that the main difference between these two approaches is their sensitivity initialization.
20
5103 SISDR (ud]
MCL. MCL SISDI [(6]
Slyp.
llyp.
1yp
1lpp
1lyp.
(a) MCL
(h) aMCL
Figure 7: Impact of the number of hypotheses. Comparison of MCL (left) and aMCL (right) on the WSJO-3mix dataset, using the MCL SI-SDR metric. Dataset-wise scores average (blue triangle), median (red line), and quartiles (main box) are reported. The whiskers extend the box by 1.5 times the interquartile gap. The number of hypotheses n is selected among {3, 5, 10). A higher score indicates better separation performance.
E.3.3 Phase transition in aMCL training
In this Section, analyze the training trajectory of aMCL in speech separation. We focus exponential schedulers defined by
T(t) To pt 1[ < fmax]
(44)
where م 0.9 is the decay factor, and To E 10.1, 23) is the initial temperature. Figure indicates the negative MCI. SI-SDR score computed during training on a validation set. In order to compare meaningfully the different temperature schedules, plot the separation score against the temperature, regardless of the training step when this temperature is reached.
We see that that aMCL exhibits phase transitions in this setting. Indeed, when use scheduler with high initial temperature To E (5, 23), the negative MCL SI-SDR metric stays on a plateau and then decreases after seems to be independent the initial temperature To > TÍ Moreover, when using a scheduler with initial temperature To 0.1 < Tg. aMCL does not undergo phase transition. This suggests that the phase transition phenomenon exhibited in Section A also exists in the non-Fuclidean case, though the properties of the barycenter and the shape of the Voronoi cells have be redefined. Further work will analyze more exhaustively the impact of the scheduler type on this phase transition phenomenon. We hypothesize that the temperature decay speed the critical temperature T5 will play key role in this analysis.
critical temperature Tg has been reached. As expected, this critical temperature
30

---

To
To 23
Th
25 (observed)
0.0
MCL Nogative SISDR (dB)
2.5
-5.0
10.0
-2255
-15.0-
17.5
10a
10
10
Temperature (lng scale)
Figure 8: Phase transition speech separation training. Impact of the initial temperature To of the temperature scheduler the source separation performance during training. The y-axis corresponds to the negative MCL SI-SDR metric. The x-axis corresponds to the temperature ('t) at each training step and is displayed in logarithmic scale. Comparison of several initial temperatures To ss 0.1 (green solid line), To s (red dashed and dotted line), and To se 23 (blue dashed line). A lower score indicates better separation performance.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We strictly describe the scope our article (introduction new training method, theoretical analysis, experimental validation).
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: we include this discussion at the end of Section in a special entry. The main arguments are hyperparameter tuning (temperature schedule) and algorithm duration (due to annealing).
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We strove to make apparent all the hypotheses of the provided theoretical results, either at the beginning of the Proposition that encapsulates them or factorized the beginning of the theoretical Section A in the appendix. Proofs are complete, or we give specific reference toward external source proving it.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: All the experimental settings are extensively described in the Appendices C, D, and provide enough detail to reproduce the experiments.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide code for reproducibility of our results. Moreover, the datasets featured in this work (UCI and WSJO) are publicly available.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental details provided in Appendices C, D, and E covering the synthetic data, UCI regression benchmark, and source separation studies, respectively.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We always report indications of the statistical significance of the provided results, either in the main paper or in the Appendix.
32

---

8. Experiments Compute Resourees
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We mentioned in the Appendix E the number of parameters of the models we used as well as the hardware architecture used in our main experiments.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: btttps://neurippp /ttp//euurrrr/eeee/eee/ee ottp.///ooooooee.ccccccoooeoeee.
Answer: [Yes]
Justification: This research does not involve human subjects participants, we referred the licensed dataset that we used (namely wsjO). We are not aware of any potential misuse of our algorithm.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We did not discuss the potential societal impacts of work, since believe that it should not be clearly different from those of the previous learning algorithms based Multiple choice learning.
11. Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: No such safeguard has been put in place, because do believe that our method has a high risk of misuse.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have properly refered to the prior work (articles or code framework,
datasets) we base research
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not introduce any new assets.
14. Crowdsourcing and Research with Human Subjects
Question: crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer[[NA]
Justification: We did not use crowdsourcing.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
33

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our research did not involve experiments on human subjects.
34


Reviews:
[{"review_id": "tCoWBkXPGi", "reviewer": "Reviewer_WAaS", "summary": "The paper proposes to apply deterministic simulated annealing to multiple choice learning (MCL) as a means to mitigate some of the drawbacks associated with the winner-takes-all (WTA) scheme used to train MCLs, such as sensitivity to initialization and hypothesis collapse. They demonstrate that the proposed annealed CML (aCML) method works well in practice, on par with previous approaches, and allows for an interesting and sound theoretical analysis of the training trajectory.", "questions": "1. Do the authors compare against the score-based method of Letzelter et al.? In line 232, it is suggested that this was one of the baselines, but it was not mentioned again in the paper, unless I missed it.\n2. On a similar note, could the authors elaborate on the relation between aMCL and rMCL (Letzelter et al., 2023)? It seems to be both have similar objectives, but the assignments in aCML are a function of the temperature of the system and the loss function, while in rMCL the assignments are learnable. If that is correct, would be fair to say that, given enough data and sufficient learnable parameters, we can always expect rMCL to outperform aCML?\n3. It is somewhat surprising that aCML does not outperform $\\epsilon$-CML in many cases. Do the authors have any intuition as to why that could be? Is it because the temperature schedule is hard to tune or aCML would require a larger number of epochs to fully converge? Or maybe the datasets are not particularly sensitive to bias of $\\epsilon$-CML?\n4. Have the authors considered stochastic simulated annealing as well?\n\n### References\n\nLetzelter, Victor, et al. \"Resilient Multiple Choice Learning: A learned scoring scheme with application to audio scene analysis.\" Advances in neural information processing systems 36 (2023).", "limitations": "The limitations section is very well written and covers all possible shortcomings of the model and analysis proposed in the paper that I could think of.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The proposed method, aMCL, is very well motivated both theoretically and based on existing open research questions in multiple choice learning. Moreover, the mathematical development of the paper is very clear and seems sound.\n- The paper is very well written and easy to follow.", "weaknesses": "- The main weakness of the paper is that the experimental results, with the exception of the quite enlightening toy experiments, are somewhat underwhelming and aCML does not seem to outperform the baselines in most cases. I think the paper could benefit from a more in-depth discussion as to why that is the case.\n- Admittedly, I am not an expert on the CML literature and maybe guilty of hindsight bias, but the idea of applying simulated annealing to CML seems quite intuitive and, one might argue, somewhat incremental. For instance, simply annealing $\\epsilon$ in $\\epsilon$-CML (Rupprecht et al., 2017) seems quite natural, and perhaps a good baseline for the authors to compare against. That does not take away from the solid mathematical motivation and theoretical results in the paper though.\n\n### Minor issues\n- Line 201: “in no longer” should probably be “is no longer”.\n- The work of Rupprecht et al. is mentioned under different names (Relaxed WTA, $\\epsilon$-WTA and $\\epsilon$-CML) which can be a bit confusing.\n- It is not entirely clear to me what the authors want to show in Figure 2.\n- The robustness result in Figure 8 is quite interesting and could be expanded upon (perhaps with more random seeds) or at least mentioned in the main paper.\n\n### References\nChristian Rupprecht, Iro Laina, Robert DiPietro, Maximilian Baust, Federico Tombari, Nassir Navab, and Gregory D Hager. Learning in an uncertain world: Representing ambiguity through multiple hypotheses. In Proceedings of the IEEE international conference on computer vision, pages 3591–3600, 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed suggestions.\n\n---\n## Experimental validation\n\n> It is surprising that aMCL does not outperform epsilon-MCL in many cases.\n\nRMSE (line 239) compares the barycenter of the predicted distribution with the target positions. For this metric, epsilon-MCL (refered to as Relaxed-WTA in the following) outperforms other approaches on the UCI datasets if $\\varepsilon$ is high ($\\varepsilon = 0.5$ in the main paper). This is expected, as Relaxed-WTA is biased towards the distribution barycenter in this regime (see Figure 1 of the paper). \n\nHowever, barycenter comparison using RMSE discards spatial distribution information of the hypotheses. Distortion (1) corrects this issue by measuring quantization performance, on which our theoretical analysis relies.\n\nFocusing on the Distortion metric, aMCL (trained with an exponential scheduler) outperforms Relaxed-WTA both for the UCI datasets and for the audio data (see Tables A and C of the supplementary pdf). This is especially true on large datasets (Year, Protein, audio data).\n\n> aMCL does not seem to outperform the baselines in most cases. \n\nLooking at the performance on the UCI datasets in Table A, we see that aMCL provides a good tradeoff between Distortion and RMSE compared to the baselines, especially on the largest datasets. Figure B confirms this trend with further analysis on Year and Protein, comparing aMCL, MCL, and Relaxed-MCL for several $\\varepsilon$ in the (RMSE, Distortion) space.\n\nOn the audio data, we trained all compared methods on 3 different seeds (Table C). These experiments extend the findings presented in Figure 8 of the Appendix: aMCL has a better inter-seed average score and lower inter-seed variance than MCL for the PIT SI-SDR. This suggests that aMCL is more robust to initialization than MCL, which is consistent with our theoretical analysis.\n\n> Annealing in epsilon-MCL seems a good baseline.\n\nUsing annealing in Relaxed MCL is an interesting idea: it may reduce the bias toward the barycenter of this method.\n\nOn the synthetic dataset of Figure 1, Relaxed-WTA with annealed $\\varepsilon$ has the following trajectory (Figure A). All hypotheses initially converge to the barycenter, then the winners gradually move towards the modes as $\\varepsilon$ decreases. As $\\varepsilon$ approaches 0, only few additional hypotheses escape from the barycenter to reach the modes, indicating that annealing does not solve the collapse issue of Relaxed-WTA. \n\nResults on the UCI datasets confirm this qualitative analysis (Table B and Figure B). In Figure B, aMCL outperforms the best Relaxed-WTA variants on Distortion.\n\n---\n## Connection with the literature\n\n> Do the authors compare against the score-based method of Letzelter et al. ?\n\nIn synthetic and UCI experiments, 'MCL' refers to rMCL, the score-based method of Letzelter et al. (Figure 1, Table 1, and Table 3 of the paper). For audio experiments, scoring is not relevant since all sources are active. \n\n> Could the authors elaborate on the relation between aMCL and rMCL.\n\nrMCL uses a hard assignment based on the Winner-takes-all scheme (3) for the prediction heads $\\\\{f_{k}\\\\}$. It is not learned, but determined by the hypotheses positions. \n\naMCL uses a soft assignment based on a temperature schedule (5) to train the prediction heads $\\\\{f_k\\\\}$ (6). With high temperatures, the assignment is uniform. As the temperature decreases, the assignment converges toward the WTA scheme.\n\nUsing a soft assignment with annealing guides the optimization process of aMCL towards a good local minimum. This is critical since optimizing the Distortion (1) is difficult by gradient descent (this task is NP-hard [1,9,42]).\n\nNote that rMCL and aMCL are however identical with respect to the scoring heads $\\\\{\\gamma_k\\\\}$, which are trained using the same loss $\\mathcal{L}_{\\mathrm{scoring}}$ (4).\n\n> Have the authors considered stochastic simulated annealing as well?\n\nStochastic simulated annealing [23,46] is a promising research direction due to its strong convergence properties (see Hajek theorem [22]).\n\nIt requires to define the state $f$ of the system and the optimization objective $D(f)$. At each step, the state $f$ is updated to a neighbor state $\\tilde{f}$ based on a stochastic exploration criterion. The probability of accepting a neighbor state $\\tilde{f}$ depends on the objective variation $D(\\tilde{f})-D(f)$ and the temperature $T$.\n\nOur objective $D(f)$ corresponds to the Distortion (1). However, the state of the system can be defined in various ways. In the non-conditional setting, [A] defines the state as the hypothesis positions $\\\\{f_k\\\\}$ (similarly to the present work), while [22, 23, 46] defines it as the cluster assignation of each dataset sample.\n\nIn both cases, storing and updating this state using neural networks is costly. Moreover, evaluating $D(\\tilde{f})$ requires going through a validation set, which is time-consuming.\n\nFurther investigation in this direction is left for future research.\n\n---\n## Additional comments\n\n> It is not entirely clear to me what the authors want to show in Figure 2.\n\nFigure 2 illustrates the training trajectory of MCL and aMCL in the rate-distortion space. It shows that MCL has a constant rate during training, i.e., a constant number of hypotheses with distinct positions. In contrast, aMCL's rate varies during training: at high temperatures, hypotheses merge into a single cluster, then recursively subdivide as the temperature decreases. \n\nCrucially, this Figure shows that MCL always has a higher rate than aMCL. Yet, it is known that the optimization procedure is more difficult in this regime [52]. This motivates the use of annealing and will be made clearer in the next revision. \n\n[A] Zeger, Kenneth, Jacques Vaisey, and Allen Gersho. \"Globally optimal vector quantizer design by stochastic relaxation.\" IEEE Transactions on Signal Processing 40.2 (1992): 310-322.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Msdb0aFu3B", "reviewer": "Reviewer_WQVX", "summary": "I read the response and found it convincing, and I appreciate the new results.  I decided to raise my score.  \n--\nThis paper aims to tackle the local minima problems in MCL optimization.  Inspired by simulated annealing, a temperature-controlled soft assignment is used and then soft-cells are directly optimized in the MCL process.  Some theory and 2d analysis sheds insight into why this approach works.  This work seems well motivated and reasonable, but the experimental gains on real datasets are quite small.  Additionally, the performance seems similar to the older epsilon-MCL approach, in which some gradient is used to increase the weighting on non-selected cells.  \n\nnotes from reading the paper: \n  -Multiple choice learning handles ambiguous tasks by producing a set of hypotheses.  \n  -Hypotheses trained using winner-take-all technique, to encourage diversity.  \n  -This paper aims to apply simulated annealing ideas to MCL.  \n  -Try to increase variance in the annealing process, to address MCL's issue of falling into local minima based on the initialization.  \n  -aMCL uses softmin assignment, followed by gradient steps on the soft cells.", "questions": "-Because it could be difficult to tune the temperature schedule over the course of training, I wonder if it could be possible to move the temperature schedule into the inference process (a bit like what's done in diffusion generative models)?  I.e., we would train a few models with different temperature levels, and force the cell assignment to be consistent with the higher temperature level.", "limitations": "Limitations aren't discussed in much detail in the paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-The basic theoretical analysis is nice, providing relevant bounds on the performance of the algorithm.  \n  -The analytical results also nicely complement the theory.", "weaknesses": "-The empirical results seem lackluster.  Epsilon-MCL and aMCL seem to work roughly equally well on the UCI datasets.  For the speech separation datasets, the improvement over MCL seems quite small, and Epsilon-MCL doesn't have results presented.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. We provide here a detailed answer to the raised concerns.\n\n---\n## Performance of aMCL\n\n> The experimental gains on real datasets are quite small. For the speech separation datasets, the improvement over MCL seems quite small.\n\nTo compare MCL and aMCL we provide two additional experimental validations. For the UCI datasets, we experimented with an additional temperature schedule. For the speech separation data, we trained PIT, MCL, and aMCL with 3 seeds to measure sensitivity to initialization. See Tables A and C of the supplementary pdf.\n\nOn the UCI datasets, we observe that aMCL is competitive with MCL for the Distortion metric, and better for the RMSE metric. This effect is exacerbated on large datasets. This suggests that with careful temperature schedule tuning, aMCL can outperform MCL.\n\nOn the audio data, we observe that aMCL has better inter-seed average PIT-SISDR score, and lower inter-seed variance than MCL in all settings. This is consistent with our theoretical analysis, which suggests that aMCL is less sensitive to initialization than MCL.\n\n> The performance seems similar to the older epsilon-MCL approach. Epsilon-MCL and aMCL seem to work roughly equally well on the UCI datasets. For the speech separation datasets, Epsilon-MCL doesn't have results presented.\n\nWe thank the reviewer for this suggestion. We provide two additional experiments. On the UCI datasets, we experiment with different values of $\\varepsilon$ for the epsilon-MCL baseline (refered to as Relaxed-WTA in the following), in Table B and Figure B. On the speech separation data, we compare Relaxed-WTA with the other approaches (Table C).\n\nOn the UCI datasets and for the RMSE metric, we observe that Relaxed-WTA outperforms all other approaches for high values of $\\varepsilon$, but not for lower values. This is expected since Relaxed-WTA is biased towards the barycenter for high values of $\\varepsilon$, and RMSE compares the predicted distribution barycenter with the target positions.\n\nHowever, barycenter comparison discards information concerning the spatial distribution of the hypotheses. Distortion (1) corrects this issue by measuring quantization performance, and we used it in our theoretical analysis.\n\nFor this metric, we observe that aMCL outperforms Relaxed-WTA in most cases, and especially for large datasets. A higher $\\varepsilon$ in Relaxed-WTA comes at the cost of a higher Distortion error. Comparatively, aMCL strikes a balance between RMSE and Distortion (Figure B).\n\nOn the audio data, we observe an advantage of aMCL over Relaxed-WTA for the PIT SI-SDR metric on the 2-speaker dataset. Preliminary experiments suggests that this is also true on the 3-speaker dataset, where Relaxed-WTA reaches a PIT SI-SDR score of $9.64 \\pm 0.03$ compared to $10.00 \\pm 0.21$ for aMCL (average and standard deviation over 3 seeds).\n\n---\n## Temperature schedule\n\n> I wonder if it could be possible to move the temperature schedule into the inference process (a bit like what's done in diffusion generative models)? I.e., we would train a few models with different temperature levels, and force the cell assignment to be consistent with the higher temperature level.\n\nThe idea of moving the temperature schedule into the inference process is interesting: with this, aMCL can be used to perform hierarchical clustering at test time. \n\nMore precisely, we can store the model's parameters at different times of the training schedule (i.e., at several temperature levels). During inference, this allow to replay the temperature cooling for new test samples.\n\nReplaying this trajectory has several advantages. Indeed, the hypotheses trajectory follows the rate-distortion curve and consequently explores recursively the modes of the distribution as the temperature decays. Crucially, at each critical temperature, when the hypotheses are about to split, they are exactly located at the barycenter of these modes. If we can track these splitting moments, for instance by counting the number of distinct virtual hypotheses at each step of the cooling schedule, we can perform a hierarchical clustering that iteratively uncovers the modes of the distribution.\n\nWe appreciate the reviewer's suggestion, which presents an opportunity for further research. We hope our response addresses their question and we remain available for additional discussion on this topic.\n\n> It could be difficult to tune the temperature schedule over the course of training.\n\nThe temperature schedule is indeed a new degree of freedom that may require some tuning.\n\nHowever, we conjecture that the theoretical analysis of aMCL convergence will lead to the characterization of optimal temperature schedules, similarly to Hajek theorem for deterministic annealing [22]. We leave this analysis for future work. \n\n---\n## Limitations\n\n> Limitations aren't discussed in much detail in the paper.\n\nWe thank the reviewer for raising this issue. In addition to the \"Limitations\" paragraph that we had already provided at the end of the main paper, we will update Sections 3 and 5 in order to provide more insights into the specific challenges raised by aMCL. In particular, we will insist on the temperature schedule choice, and the potentially longer training time of optimal schedules.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "XbgBdGc9F9", "reviewer": "Reviewer_qUke", "summary": "The paper introduces Annealed Multiple Choice Learning (aMCL), a method that integrates simulated annealing with Multiple Choice Learning (MCL), in applications where the output label may be ambiguous, and many values may be plausible given the same input.\n\nThe authors show that problems arise with the use of winner-takes-all in the optimization step of MCL, where the output space is partitioned in Voronoi cells based on the individual predictors. Instead, the authors suggest to soft-weight the predictors to replace hard-WTA assignments, in a way that depends on a temperature parameter. Low values of the temperature make the weighting scheme behave close to hard-WTA (sharpening the softmin distribution of weights).", "questions": "N/A", "limitations": "- Since the authors argue that WTA is sensitive in particular to initialization, it would have been interesting to see experiments comparing the robustness of vanilla MCL vs aMCL over different initializations.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The integration of simulated annealing and MCL is novel and effective;  I also like that the objective in eq. (6) becomes fully differentiable, without any non-differentiable assignment or operators.\n\n- Extensive theoretical analysis.\n\n- Extensive validation over a large number of datasets, although from the results in seems that epsilon-MCL seems to perform better, overall.", "weaknesses": "- The introduction of the temperature schedule as hyperparameter complicates the use of the method, while it seems that epsilon-MCL would be both easier (one hyperparameter, but fixed, without schedule) and overall better performing.\n- I am not sure how representative the UCI datasets are of real world problems, but that is not a big problem.\n\n- Minor: typo?  'broaden impact' -> 'broadeR impact'?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their suggestions to improve the quality of this manuscript.\n\n---\n## Comparison with baselines\n\n> From the results in seems that epsilon-MCL perform better, overall.\n\nWe compare epsilon-MCL (refered to as Relaxed-WTA in the following), MCL and aMCL on the UCI datasets for two metrics: RMSE (line 239) and Distortion (1).\n\nRMSE compares the barycenter of the predicted distribution with the target positions. For this metric, Relaxed-WTA outperforms other methods for high values of $\\varepsilon$ (e.g., with $\\varepsilon = 0.5$, see Table B). This is expected, since Relaxed-WTA is biased towards the distribution barycenter, especially for high values of $\\varepsilon$ (see Figure 1 of the paper).\n\nHowever, barycenter comparison discards information concerning the spatial distribution of the hypotheses. Distortion (1) corrects this issue by measuring quantization performance, and we used it in our theoretical analysis.\n\nFor this metric, aMCL outperforms Relaxed-WTA in most cases, and especially for large datasets (Year, Protein, see Table A). Hence, aMCL strikes a balance between RMSE and Distortion (See Figure B). \n\nIn order to verify this behavior on audio data, we have additionally trained Relaxed-WTA on the speech separation data. We show that  aMCL still outperforms Relaxed-WTA in this more realistic setting (see Table C of the supplementary pdf). \n\n> It would have been interesting to see experiments comparing the robustness of vanilla MCL vs aMCL over different initializations.\n\nWe thank the reviewer for this suggestion. We have extended the experiments presented in Figure 8 of the Appendix by comparing PIT, MCL, aMCL and Relaxed-WTA for 3 different seeds on audio data (see Table C of the supplementary pdf).\n\nFirst, we confirm that PIT, which performs perfect assignation, acts as a topline in this experiment. Moreover, the difference between PIT and aMCL is not statistically significant. Therefore, aMCL reaches the same performances as PIT, while improving from $\\mathcal{O}(m^3)$ to $\\mathcal{O}(nm)$ in terms of complexity (noting $m$ the number of speakers and $n$ the number of hypotheses) [A]. This complexity gap is best exploited when the number of speakers is high, similarly to [B], and this will be the object of further work.\n\nSecond, we see that aMCL is better performing than MCL when we average over seeds. Moreover, aMCL has lower inter-seed variance than MCL. This validates our theoretical analysis, which suggests that aMCL guides the hypotheses towards a better local minimum than MCL, independently of the initialization.\n\n---\n## Limitations\n\n> The introduction of the temperature schedule as hyperparameter complicates the use of the method.\n\nWe thank the reviewer for raising this issue. The temperature schedule is indeed a new degree of freedom that may require some tuning. \n\nHowever, we conjecture that the theoretical analysis of aMCL convergence will lead to the characterization of optimal temperature schedules, similarly to Hajek theorem for deterministic annealing [22]. We leave this analysis for future work. \n\n> How representative are the UCI datasets of real world problems ?\n\nThe UCI datasets correspond to real world tabular data for 1D predictions, and constitute a widely used benchmark to evaluate uncertainty quantification algorithms. We have included it our manuscript in order to compare ourselves to the customary multi-hypothesis baselines (see Table 1 of the main paper).\n\nThe datasets are sorted by size in Tables A and B. Interestingly, aMCL obtains the best Distortion results for large datasets (Year, Protein, see Table A and Figure B), which are the most realistic. This will be emphasized in the main paper.\n\n[A] Jack Edmonds and Richard M Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM), 19(2):248–264, 1972.\n\n[B] Hideyuki Tachibana. Towards listening to 10 people simultaneously: An efficient permutation invariant training of audio source separation using sinkhorn’s algorithm. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 491–495. IEEE, 2021.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank reviewers WAas [R1], WQVX [R2] and qUke [R3] for their precise and detailed comments. We summarize hereafter the main changes in the submission, in accordance with the reviewers' feedbacks. 

* We provide additional experimental validation on the UCI benchmark [R1, R2, R3]. We demonstrate that our proposed method aMCL has superior performance in terms of Distortion error, which is the customary quantization metric, without underperforming for the RMSE metric. This is especially true for large datasets.

* We provide additional experimental validation on the speech separation benchmark [R1, R2, R3], where we further demonstrate the competitiveness of our method, in particular its robustness to initialization and its performance compared to Relaxed-WTA [55].

* We provide additional discussion of aMCL, including its connection with similar approaches introduced in the literature (rMCL [36], Relaxed-WTA [55], Stochastic simulated annealing [29]), its challenges concerning the choice of an optimal temperature schedule, and its potential extention to hierarchical clustering [R1, R2, R3]. 

* Following advice from the reviewers, we introduce an additional baseline, Relaxed-MCL with annealed $\varepsilon$ [R1]. We analyze its behavior using a synthetic dataset, and confirme this qualitative analysis with more extensive experiments on the UCI benchmark.

We provide a supplementary pdf, and refer to its Figures and Tables in the rebuttal. In the rebuttal, we will refer to Epsilon-MCL as Relaxed-WTA.

Meta-review: This paper presents a modification to multiple choice learning (MCL), which is for dealing with situations where the correct output for a given input cannot be determined wholly from the information available in the input. Specifically, the authors seek to improve on existing MCL approaches by incorporating annealing into the gradient descent process for MCL, thereby exploring a wider range of the hypothesis space. The authors provide analysis of the training trajectories and show empirically that their analyses hold.

Overall, the reviewers were fairly positive about this paper. They raised some concerns related to the strength of the performance improvements and comparisons to other MCL learning variants, and also highlighted the need for additional benchmarks. The authors were largely able to address the reviewer concerns in rebuttal, and the final average score was above acceptance threshold (6.33). Given these considerations, the AC decided to accept the paper as a poster.
Decision: Accept (poster)