Joint Learning of Energy-based Models and their Partition Function
Authors: Michael Eli Sander
Vincent Roulet
Tianlin Liu
Mathieu Blondel
Venue: ICML 2025 poster (2025)
Keywords: energy-based models
maximum likelihood estimation
stochastic optimization
structured prediction
MCMC-free
Primary area: optimization
TL;DR: We propose a method to jointly learn energy-based models and their partition function.

Abstract: Energy-based models (EBMs) offer a flexible framework for parameterizing probability distributions using neural networks.
However, learning EBMs by exact maximum likelihood estimation (MLE) is generally intractable, due to the need to compute the partition function.
In this paper, we propose a novel min-min formulation for approximately learning probabilistic EBMs in combinatorially-large discrete spaces, such as sets or permutations. Our key idea is to jointly learn both an energy model and its log-partition, parameterized as a neural network. Our approach not only provides a novel tractable objective criterion to learn EBMs by stochastic gradient descent (without relying on MCMC), but also a novel means to estimate the log-partition function on unseen data points.
On the theoretical side, we show that our approach recovers the optimal MLE solution when optimizing in the space of continuous functions.
Furthermore, we show that our approach naturally extends to the broader family of Fenchel-Young losses, allowing us to obtain
the first tractable method for optimizing the sparsemax loss in combinatorially-large spaces.
We demonstrate our approach on multilabel classification and label ranking.

Joint Learning of Energy-based Models and their Partition Function
Michaël E. Sander Vincent Roulet
Tianlin Liu'
Mathieu Blondel
Abstract
distribution p(ylæ:). Probabilistic EBMs include Bolzmann machines (Ackley et al., 1985) as a special case.
Probabilistic energy-based models (EBMs) offer a flexible framework for parameterizing proba- bility distributions using neural networks. How- ever, learning probabilistic EBMs by exact maxi- mum likelihood estimation (MLE) is generally in- tractable, due to the need to compute the partition function (normalization constant). In this paper, we propose novel formulation for approximately learning probabilistic EBMs in combinatorially- large discrete spaces, such as sets or permutations. Our key idea to jointly learn both an energy model and its log-partition, both parameterized neural networks. Our approach not only provides novel tractable objective criterion to learn EBMs by stochastic gradient descent (without relying on MCMC), but also a novel means to estimate the log-partition function on unseen data points. On the theoretical side, we show that our approach re- covers the optimal MLE solution when optimizing in the space of continuous functions. Furthermore, we show that our approach naturally extends to the broader family of Fenchel- Fenchel-Young losses, al- lowing us to obtain the first tractable method for optimizing the sparsemax loss in combinatorially- large spaces. We demonstrate our approach on multilabel classification and label ranking.
Unfortunately, this flexibility makes learning, sampling and inference with probabilistic EBMs much more challenging. Indeed, without factorization assumptions, turning an en- ergy function into valid probability distribution involves computing the partition function (normalization constant), which generally intractable to compute exactly in contin- uous spaces or combinatorially
discrete spaces. To perform maximum likelihood estimation (MLE) of the net- work parameters, standard approach rely on Markov chain Monte Carlo (MCMC) methods to estimate stochastic gradients of the log-likelihood function (Song & Kingma, 2021). However, deriving an MCMC sampler is usually case by case. For instance, for continuous outputs we may use Langevin-MCMC and for binary outputs we may use Gibbs sampling. practice, is the case in contrastive divergences (Hinton, 2002), MCMC iterations to convergence, leading biased stochastic gradient esti- mates (Fischer & Igel, 2010). In continuous spaces, score matching (Hyvärinen & Dayan, 2005) is often used as an alternative to MILE but it requires computing the Lapla- cian operator, which is challenging in high dimension. In combinatorialll-Iarrg discrete spaces, one can use the gen- eralized perceptron loss (LeCun et al., 2006) or the gen- eralized Fenchel- Fenchel-Young loss (Blondel al., 2022), which only involve computing argmax a regularized argmax, respectively. These losses sidestep computing the partition function, but they learn non-probabilistic EBMs.
run
1. Introduction
In this paper, we propose a novel formulation for learning probabilistic EBMs p (yla in combinatorially-Ieee discrete spaces (such as sets or permutations in our experiments) by MLE any loss function in the Fenchel- Young family (Blondel et al., 2020a). Our approach not only provides a new tractable objective criterion that can be optimized by stochastic gradient descent (SGD) without MCMC, but also a new means to estimate the log per-patttiinn function on unseen data points using a jointly-learned separate neural network. We demonstrate our method on multilabel classification (space of sets) and label ranking (space of permutations).
Probabilistic mbaed models (EBMs) are a powerful framework for parameterizing probability distributions us- ing neural networks, without any factorization assumptions. They have been successfully used both in the unsupervised setting (density estimation, image generation). where the goal is learn probability density function p(æ) and in the supervised learning setting (classification, structured pre- diction), where the goal is to learn conditional probability
'Google DeepMind. Correspondence to: Mathieu Blon- del <mblondel google.com>>, Michaël E. Sander <michacl- sander@ gow.leo.oooooo..m.......
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Contributions.
After reviewing some extensive background, we propose

---

Joint Learning of Energy-basee Models and their Partition Function
novel min-min formulation for learning probabilistic EBMs p(y (z)) in combinatorially-larg discrete spaces. Our approach consists in jointly learning two separate functions: an energy model and its log-partition.
energy-based model (EBM) as
q ( exp(g(ax y))
Po(y) = Eye g(y' (æ) exp(g(a; y²))
(1)
When minimizing the proposed objective in the space of continuous functions, we show that our approach exactly recovers MLE.
where q & (D a prior conditional positive measure.
When such a measure is not available, we can just use the uniform positive measure, which gives
In practice, propose to parameterize the log-partition as neural network and we replace minimization in the space of functions with minimization in the space of net- work parameters. An advantage of our approach is that the learned log- partitioo network can benefit from the universal approximation properties of neural networks, as we empirically demonstrate.
exp(g(a, y))
(o(() EyeEy exp(g(x y"))
We focus (1) for generality, though in experiments we will use uniform reference measure. Throughout this paper, we leave the dependence on implicit, as it is fixed reference measure. It well-known (Boyd, 2004) that (1) can be written from a variational perspective as
To jointly learn the energy model and the pert-aattiion, we propose an MCMC-free doubly stochastic optimiza- tion scheme. Our stochastic gradients are unbiased: our only assumption is that we are able to sample from a reference distribution, which can be the uniform distri- bution when no prior knowledge is available.
Ps (- = (g( )).) KT ((12))) (2)
pEPi())
The corresponding log log-partition, a.k.a. log-sum-exp, is
(x) == log
Σ
q exp(((x, y')). (3)
We generalize our approach to the broader family of
y'EY'
Fenchel- Young losses (Blondel et al., 2020a), such
It is related to the log- ligeliidldoodd of the pair (æ, y) through
the sparsemax loss (Martins & Astudillo, 2016). In this case, our approach consists in jointly learning the energy-based model and Lagrange mutiplier (dual variable), that we parametrize as a neural network in practice. This is to our knowledge the first tractable approach for learning EBMs with the sparsemax loss in general combinatorially-large discrete spaces.
Po g(æ, y) LSE (2)) + loga(ylæ))
(4)
Similarly to (2), we have
LSEg(1) max (o(z, ).p) (LLpp9(-1x)) (5)
pEP)
Architecture of EBMs. As g is affinity function, it is both natural and standard decompose it as
Notation. We denote the continuous input space by X and the discrete output set by V We denote the set of continu- ous functions g: X' x y + R as F(X's x y). Similarly. we use F(X') for continuous functions 7: X + R. We denote the set of conditional positive measures over y conditioned on X' as P+ ())))). Similarly, we use Pi ()) for condi- tional probability measures. Given æ X, we denote the partial evaluation of g F(X x }) as g(x.,) F()). Given h E F()) and p E (D)),, we define (h,p) == Evey hy))p(y). We denote the convex conjugate of f() by [v) = sup,, fu). Throughout this paper, we will use ((z.g) as a shorthand for E ((2.))>oxx> where Pxxy is the joint data distribution over X' y and Er as a shorthand for Eap where px the marginal data distribution, i.c., px(x)) Evey Pxxy( (x, y).
g(x, y) = 2 (h(()) y)
(6)
where (00,)) 3) is coupling function and 0 = h(xx) is model function producing logits 0 E θ (Blondel et al., 2022). Typically, h and & are designed on a per-task basis. The simplest example of coupling is the bilinear form
s ( y) (0, 1.
In this case, an EBM coincides with an exponential family distribution with natural parameters O. We will define more advanced couplings in Section 4.
2.2. Inference with EBMs
Computing the mode. Predicting the most likely output associated with input æ according to an EBM corre- sponds to computing the mode of the learned probability distribution, defined as
2. Background
2. Probabilistic energy-based models (EBMs)
Given function g E F(X' x y), which captures the affinity between an input æ E X' and an output y E y (typically, a parameterized neural network), we define probabilistic
(x) arggaax (y)x) argmax ((y(x) exp(g(x; y)). yey
yey
2

---

Joint Learning of Energy-based Models and their Partition Function
Unfortunately, when Y is a combinatorialll--arg discrete set, this problem is often intractable. A common approxima- tion is to replace Y' with convex set C > V. The tightest such set is C = conv ()), the convex hull of y. For ex- ample, in multilahel classification with & labels, the output space is the power set of [k:], which can be represented as = (0, }} and whose convex hull is conv()) = [0. 1]a.
expected risk minimization with a logistic loss, is
(MLE(g) == (z.y)) |- log Po (
= F [T.SE (a=) B( (a( y) log(((y [=]]]
(11)
Unfortunately, when y is a combinatorially- discrete set continuous set, this objective is intractable due to the log- prg-partition function over all possible outputs.
With uniform prior g, assuming that g E F(X C), and not just g F(X x )), we can solve the relaxed problem
2.4. Approximate MLE of EBMs with MCMC
x + argmax g(æ, 14) x y (x),
(9)
Let denote by Iw a function with parameters w. Then, the gradient can be computed by (Song & Kingma, 2021)
where we used that exp is monotonically increasing. If the coupling ( (u) is concave μa, this problem can be solved optimally in polynomial time. Typically, one can use a gradient-based solver to obtain an approximate solution in C. and then use a rounding procedure to produce a prediction that belongs to y. If (0 (u) is the bilinear coupling (7), then (9) is known as maximum a posteriori (MAP) inference (Wainwright& & Jordan, 2008) when C = conv()). ()). According to the fundamental theorem of linear programming. a solution happens at one of the vertices of C and therefore 3 (x) Y in this case.
VwLLLL((ww) -Ego [By'rrew (1ax)) / Iw (a, y 3/D]]
((a,)) (V W (z, y)]
For completeness, see Appendix C.7 for proof. Therefore, as long as we can draw samples from Paw (-12)), we can have access to an unbiased Monte-Carlo estimate of the gradient, allowing us to perform optimization based on stochastic gra- dient descent. However, sampling from Pow. (-|z²) is difficult, The literature has focused on Markov chain Monte Carlo (MCMC) methods, such as Hattooolls-HHssting Gibbs sam- pling and Langevin. Typically, running MCMC until con- vergence is expensive. Therefore, MCMC is usually run for a small number of iterations, as in contrastive divergences (Hinton, 2002). Unfortunately, truncated MCMC can lead to biased gradient updates that hurt the learning dynam- ies (Song & Kingma, 2021). There are methods for bias removal but they typically greatly increase the variance.
Computing the mean. Another important problem is that of computing the conditional expectation
(x(xx)= = (-ax)((aa)l0)) = Σ
Po(y)æ) E conv()). yEY
(10) In the special case of the bilinear coupling (7), we have that (x) is the gradient w.r.t. h of LSE, (x). Moreover, (10) is known as marginal inference and c)nv()) is known as the marginal polytope, because, y uses a binary en- coding (indicator function) of outputs, then H (xx) contains marginal probabilities (Wainwright & Jordan, 2008). For ex- ample, if y f0, 1)A; then [x)( contains the marginal probability of label j given
2.5. Non-MLE probabilistic approaches
Departing from MLE, we can learn probabilistic EBMs of the form (1) using score matching (Hyvärinen & Dayan, 2005). It trains a model to estimate the gradient of the log- density function of the data, known as the score function. However, score matching requires the log-density of the data distribution to be continuously differentiable and finite everywhere, which limits it to continuous output spaces. In addition, score matching requires to compute and differenti- ate the Laplacian operator (the trace of the Hessian), which is often challenging in high dimension. Even though some extensions to discrete spaces have been proposed, such as concrete score matching (Meng et al., 2022) and ratio match- ing (Hyvärinen, 2007), score matching is seldom used in discrete spaces.
When using the bilinear coupling (7) and when the variables in y form a tree, LSE, and Mg can be computed by message- passing-like dynamic programming algorithms (Wainwright & Jordan, 2008; Blondel & Roulet, 2024). Efficient algo- rithms also exist for partieular structures, such as spanning trees (Zmigrod et al., 2021). However, these algorithms longer work for non-bilinear couplings. In addition, even in the case of bilinear couplings, computing LSE, and μ4 is intractable in general. For example, if Y' is the space of permutations, then computing LSE, and Mg is known to be #P-complete, making exact MLE intractable.
Another non-MLE approach is noise contrastive estimation (NCE) (Pihlaja et al., 2010; Gutmann & Hyvärinen, 2010; Gutmann & Hirayama, 2011). It works by training a model to discriminate between true data samples and generated noise samples. However, the performance of NCE can be sensitive to the choice of the noise distribution. In addi- tion, the ratio of noise samples to data samples can affect
2.3. MLE of EBMs is intractable in general
The log-like likelliodoood of an observed pair (z, y) is given in (4). Accordingly, the MLE objective, which corresponds to
3

---

Joint Learning of Energy-basee Models and their Partition Function
performance and finding the optimal ratio usually requires experimentation.
as an (intractable) equality constraint Σyey Pa (y/ [x)
for all æ: E X. To deal with that constraint, our key idea is to introduce a Lagrange multiplier (dual variable), that we treat as separate function T E F(X) to minimize over. The Lagrange multiplier exactly coincides with the log-pan oog-partition function the MLE (logistic loss) case. Our approach con- sists in jointly learning the energy function y É F(X x ))) and the oog-patiiiion function F(X). Using duality ar- guments in the space of functions (see Proposition 1 below), we arrive at the objective function
2.6. Loss functions for non-probabilistic EBMs
When the goal is not to learn the probabilistic model (1) but just the relaxed argmax (9), perceptron loss (LeCun et al., 2006),
the generalized
(a. y) max g(x, 14) g(z, WEC
To ensure uniqueness of the argmax, we can add regulariza- tion in (9) to define the regularized relaxed problem
LMEE(O, r) = Ex [L (x)) - (( (g(a, (12)
where
Ø - argmax g(,, pa) 22())- HEC
(x) = [(x)+ Σ ( (z) (exp(g(x, y') T())) - 1).
The corresponding generalized Fenchel-Young loss (Blon- del et al., 2022) is
y'E)
(13)
The minimization problem in the space of functions is then
(a. v) + max g(., 14) - 22())= - g(., y) + -yy). MEC
min min (MLE(g,T). XEF(XX))
Crucially, the gradient w.r.t. the parameters of g can computed easily using the envelope theorem. However, these losses do not learn probabilistic models. They only learn to make the (relaxed) argmax predict the correct output. See also the discussion distribution-space vs. mean-space losses in Blondel et al. (2020a).
Intuitively, by minimizing the proposed objective with re- spect to both g and r, we are able to approximate the true log-partition function while simultaneously learning the energy function as to fit the data. In practice, we param- eterize the energy model as Iw and the log- partition as Te- The minimization problem in the space of parameters is then
2.7. Log- log-partition as an optimization variable
The idea of treating the log-partition as optimization vari- able, rather than as quantity to compute or estimate, was also explored in several earlier works in the unsupervised setting (Wang et al., 2018; Arbel et al., 2021; Senetaire et al., 2025). Compared to these works, our paper provides new theoretical guarantees regarding MLE recovery when opti- mizing in function space (Propositions 1 and 2), extends to the broader senchel-Young losses (Proposition 4), focuses on the supervised structured prediction setting, and most im- portantly, parameterizes the input-dependent log-partinn log-partition as a neural network with generalization ability (in the unsu- pervised setting, the log-partition is an input-independent scalar value, therefore parameterizing the oog-parttiinn neural network would not make sense).
min min LMLE(9W; wEW VEV
In our experiments in Section 4, we consider linear mod- els, multilayer pecerptrons (MLPs) and residual networks (ResNets) for Jw. and we consider constant models, MLPs, ResNets and input-convex neural networks (ICNNs) (Amos et al., 2017) for Ty.
Doubly stochastic gradient descent. When g a proba- bility distribution (if such distribution is not available, we simply use the uniform distribution), we can rewrite (13) as
(x) = T(x) + (()a)) [exp(g(x 3²) -xx))] - 1. (14)
As a result, we can estimate (MLE(g, r) and its stochastic gradients, provided that we can sample from q(-la)) for any x. This suggests a doubly stochastic scheme, in which we sample both (x, y) pairs from the data distribution px'xy' and y' prior samples from the reference distribution q(: [);; see Algorithm 1. For simplicity, we group w E W and v E V as a tuple and optimize both blocks of parameters simultaneously using Adam (Kingma, 2014). Although not explored in this work, it would also be possible to perform alternating minimization w.r.t. w E W and v E V.
3. Proposed approach
In this section, we first propose a novel min-min formu- lation for learning probabilistic EBMs by MLE. We then generalize to the family of Fenchel- Young losses.
3.1. A min-min formulation for MLE in EBMS
Overview of the approach. The partition function (nor- malization constant) in (1) can equivalently be formulated
4

---

Joint Learning of Energy-basee Models and their Partition Function
Algorithm I Doubly stochastic objective value computation
also been explored in optimal transport (Seguy et al., 2018; Korotin al., 2021) and in generative adversarial networks (Nowozin et al., 2016).
Inputs: models and T, batch sizes B and B'
Draw (#1.91). 91).-.. BB yB) Lid.
pxxx
Draw -1 Di Ltd. g(-1214) for [B] T.g.r (mz)) == T(x)) + B Zj=1 (exp(g( vhss (aa)))
3.2. Finite sum setting
The MLE objective (11) corresponds to the expected risk minization setting, in which there are potentially infinitely- many (æ, y) pairs. In practice, we often work in the empiri- cal risk minimization or finite sum setting, in which we use a finite number of pairs (I1, 31), ..., (In. yo). The classical MLE objective (11) then becomes (removing constants)
Output: B (I 1 (x1) g( vi)
Equivalence with MLE. Although our proposed objec- tive (12) appears quite different from the original MLE (expected risk) objective, we can show that they are in fact equivalent when minimizing over the space of functions.
EMLE(9) = Σ LSSE,(D:) g( U.)
(15)
Proposition 1. Optimality of min- MLE case
Suppose that for all y E V. x + 4(y) x) is continuous. Then, we have
and proposed objective (12) becomes
min (MLE(9) = min (MLE(g,T) gEF(XX)) TEF(X)
EMLE T) = Σ -...((a))))
g(2;, glax;
(16)
gEF(XXY)
and for all (x, E EXXX
In the finite sum setting, if we do not need to generalize to unseen a instances (recall that the log- uog-partition is not needed at inference time if all we want to compute is the mode, i.e., the argmax prediction), then we can set To (2;;) = v, for v == (VI, va) E R". Our approach then solves the finite- sum MLE objective optimally.
LSEg (x) -T'(w) Pg (y|æ) l (z) exp(9" (z. v) (xx).
See Appendix C.2 for a proof. The optimality in Proposi- tion 1 holds because we perform minimization in the space of continuous functions. If we parameterize 7 neural network, and perform minimization in the space of parame- ters instead, our approach only performs approximate MLE. However, thanks to the universality of neural networks, min- imization in the space of parameters should be close to minimization in the space of continuous functions, provided that the neural network used sufficiently expressive. This confirmed in Figure 1. The larger the number of y' sam- ples we draw to estimate the expectation in (14), which corresponds to B' in Algorithm 1, the faster we converge to the exact MLE objective.
Proposition 2. Optimality, finite sum setting
Suppose To (x.)) = foror E [n]. Then,
min [MIL(OW)) min [M To) weW
wEW vER"
and Uy = LSE (a;) for all i [n]]
See Appendix C.3 for a proof. Remarkably, the result holds even if guo is nonlinear in w E W.
Joint convexity in the case of linear models. If Iw (2.; y:) = (her (2;)) yt),, where haw is linear in w,, then the classical MLE objective (15) is that of conditional ran- dom fields (Lafferty et al., 2001; Sutton & McCallum, 2012) and it is convex in w. However, despite convexity, it could be intractable if for example ) is the set of permutations. In contrast, our objective (16) is jointly convex in (w, v). as proved in Appendix C.6, and it remains tractable as long as we can sample from <(-lx=). In this convex setting, SGD enjoys convergence rate of O(I/V). and if we further add strongly-convex regularization on the parameters, the rate becomes (11))) (Garrigos & Gower, 2023; Bach, 2024). Therefore, our objective can be optimized using stochastic gradient methods, and we have obtained convergence rates for learning EBMs in arbitrary combinatorial spaces.
Generalization ability of the learned log-partition. Our approach not only provides tractable objective criterion to learn EBMs by SGD, but also novel means to estimate the log-partition function on unseen data points. Indeed, because we parameterize Tu as a neural network, we can evaluate it on new datapoints at inference time. Figure? 2 empirically confirms the generalization ability of our our learned log-pan partition function unseen data points.
Learning the partition function, as opposed to computing it or estimating it, bears some similarity with learning the value function in reinforcement learning (Konda & Tsit- siklis, 1999; Schulman et al., 2017). Parameterizing dual variables as neural networks, as we do in this work, has
5

---

Joint Learning of Energy-basee Models and their Partition Function
120
0,40
110
0.35
100
0.30
2000
4000
2000
4000
2000
4000
(a) Loss (train)
(b) Gradient norms (train)
(c) fi fi-se (test)
y sample
samples 1000 samples
samples
10 samples
Exact MLE
Figure 1. Convergence of the proposed approach function of the number of iterations, when varying the number of prior samples y' drawn. be able to compute exact MLE objective (15), we use the unary multilabel model (Section 4.1) on the cal500 dataset (174 classes and therefore 2 27 possible configurations) as the test bed. Note that the loss and gradient in plots (a) and (b) computed using (15) even for our method. We make two key observations: i) our approach converges to exact MLE as predicted by our theory, ii) the number of y' samples can have regularization effect the test fcore... See Figure 3 for more results.
3.3. Comparison with min-max formulation
3.4. Generalization to Tenchel-Young losses
One distinguishing feature of our approach is that uses min-min formulation. It is therefore insightful to compare it with min-max formulation. With some overloading of the notation, let us define
Another advantage of our proposed approach is that natu- rally generalizes to any loss function in the Fenchel- Young family (Blondel et al., 2020a). It is well-known that the log-sum-exp can be interpreted as a "softmax". To obtain more general notion of softmax, we replace the KL di- vergence in (5) with f-divergences (Csiszár, 1967; Ali Silvey, 1966), which are defined when ) a finite set as
(MLE(g.P) = Ex 1m y')] (L(p(-12))
(( (g y) + const.
Dy(p.9) = Σ f(plw)//(w))(())
DEY
We then have the following proposition.
We assume that strietly convex and differentiable (0, +cc). We can then define the f-softmax as
Proposition 3. Optimality of min-max, MLE case
softmax (x) = max (g(x, )).)) Dy q(-1x))) pEPi
We have
min (ET(XX))
(MIE(())
min PEP.)))
EMLE(g.p).
and the f f-softargmax as
P (-(x) = argmax(g(zz.)) - (()=)) pEPi
proof given Appendix C.4. This is akin to adversarial approaches, where the function g plays the role of discrim- inator and the distribution p plays the role of generator (Nowozin al., 2016; Ho & Ermon, 2016). Because the maximization w.r.t. in the space of distributions is usually intractable when ) is combinatorial or infinite and because we need to be able to sample from p(-[z), is common to replace p with a parameterized distribution from which is easy to sample. An additional challenge comes from gradient computations: since p appears in the sampling, one typically the score function estimator (REINFORCE) to estimate the gradient w.r.t. the parameters of p. How- ever, this estimator suffers from high variance. In contrast, in our min-min approach, the variable 7 is a function, not a distribution and its gradients are easy to compute, since expectations are w.r.t. 4; not p.
By analogy with the MLE objective in (11), we can then consider the objective
(g( = En [softmax/ (m) - E [g(x, y)
Unfortunately, just for the log-sum-exp in the MLE set- ting, the f-softmax is intractable compute when y is combinatorially large. Similarly to (12), using duality argu- ments, we arrive at the objective
Cylg, E. TI (z)) E( [g(xr, y)]. with L/ 4/.- (x)
Here, fī is the convex conjugate of /+, the restriction of to R4, We have the next generalization of Proposition 1.
6

---

Joint Learning of Energy-bass -based Models and their Partition Function
w
yeast
(b) scene
birds
ma
(d) emations
(e) cal500
Figure 2. Generalization ability of the learned log-partition function for multilabel classification. As testhed compare the learned log- partition (dark purple), we use the unary model (see Section 4,1 for details), which enjoys closed-form expression for the exact log partitionnon (light purple). pick randomly 100 test samples (z-axis) on multilabel classification datasets, after training models with hyper- parameters optimized against the validation set.
Proposition 4. Optimality of min-min, general case
4. Experiments
Let f be a strictly convex differentiable function such that (0, +o0) S dom f'- Suppose that for all y E Y, x + (3y(2)) x) is continuous. Then, we have
We now demonstrate our approach through experiments multilabel classification and label ranking. Through- out experiments, in (6), assume that g(z, y) ((((ar)) y) where Φ0 y) is coupling function and h():) is model function producing logits 0. Experimental details and additional results are presented in Appendix A.
min Cy(9)= (E)(X())
min (g.
9EF(XX))) TEX(X)
and y) x
4.1. Multilabel classification
= (1) - (x)).
In this section, we perform experiments on multilabel clas- sification with classes. Here, given an input æ, the goal is to predict an output y belonging to the powerset of [k)], which can represented as y = {0, 1} The cardinality is | 2 and the convex hull is conv()) [0, 1)s.
A proof is given in Appendix C.5. In the MLE case, incided exactly with the log-partition function. In the more general setting, corresponds to the Lagrange multiplier as- sociated with the equality constraints Eyey P3 (y)=z) =
Unary model. To perform multilabel classification, the simplest approach is to use the bilinear coupling (7) (00, y) ΣØ 0,H, together with logits 0 h(x)) R& In this case, predicting the mode (8) with uniform g reads
Example: sparsemax for EBMs. When (w) 1 (u² 1), which is the generating function of the chi-square diver- gence, we obtain the first tractable method for optimizing the sparsemax loss (Martins & Astudillo, 2016) on EBMs in combinatorialll-lagge discrete spaces. We have
y (a) argmax 400, y) (0.1)))
10gmax(0..2 y),
(0.10
for which the optimal solution is
1 Σ (()1))) [g(a, 2 2
(x) = [ +
1
if > 0 <
Vj
[k).
DEy
if 0
and p/- (y)2z) ((yla)) 1g* (x, y) - - (xx))+ where [++ m) the nen-negative part. Previous at- tempts use the sparsemax loss for structured prediction require k-best maximization oracle (Pillutla al., 2018). Unfortunately, such oracles are not available for all sets y (c.g., permutations) and their cost is usually polynomial in k. while could be arbitrarily large. In contrast, our doubly- stochastic approach only requires us to able to sample from the reference probability measure q(-(a)).
The log-sum-ent (3) and marginal inference (10) both enjoy closed-form solutions:
(x) Σ softplus(0
(17)
[mg( = sigmoid(H,) Vj E [1]]
Therefore, the unary model boils down to placing sigmoid activations on top of the logits 0 h((x), as usual in deep
7

---

Joint Learning of Energy-bass -based Models and their Partition Function
Table 1. fi-score on multi-label classification different models and losses (with constant 7 model, that (m)) = n..))
Loss
Model
yeast
scome
birds
emotions
cal500
Logistic (min-min)
I Linear (unary)
63.41
70.78
45
61.6 13.63
40.19
(unary)
75.35
65.33
44,91
RosNet (unary)
65.03
75.64
36,93
67.45
45.23
Linear (puirwise)
63.40
70.72
45.49
61.63
40.23
MI.P (painwise)
65.11
75.22
46.08
64.84
45,00
ResNet (pairwise)
64,84
75.68
41 41.34
64,26
44.61
Sparsemx (min-min)
Lincar (unary)
45.12
63.14
45.18
MLP (unory)
63.22
75.83
42
66,86
46.39
ResNet (unary)
62.27
75.44
28.63
44.53
39.11
Linear (puirwise)
62.91
69,89
45.12
63,14
45.18
ML.P (pairwise)
63.39
74.94
40.68
66.28
46.39
ResNet (pairwise)
62.32
75.63
27.85
64.58
30.93
Logistic (exact MI.F)
Linear (unary)
61.46
70.64
43.97
63,35
37.31
MLP (unary)
60.71
70.81
40.88
62,99
36.24
(unary)
61.50
37.45
Generalized Fenchel- Youngg
Lincar (unary)
61.41
70.26
44.13
61,70
36.85
MI.P (unary)
61,31
70.84
40.73
61.85
37.35
Linear (pairwise)
61.62
70.42
42.28
63.05
35. 12.12
Logistic (MCMC)
I Linear (unary)
61.98
70.53
44.93
61.76
44.61
(unary)
71.57
33.13
62.23
35.70
Rosnet (unary)
56.57
71.24
27.03
58.98
44.34
Linear (puirwise)
61.96
70.50
44.93
61.76
44.61
ML.P (pairwise)
60.83
71,92
34.61
63.15
45,95
Resnet (pairwise)
56.68
70.46
27.08
64.05
44,35
Logistic (min (min-max)
Linear (unary)
$2.80
52.29
27.59
61.72
35.08
MLP (unary)
58.58
52.54
24.95
60.53
46.08
Resnet (unary)
57.53
42.82
25.32
55,85
47.59
Linear (pairwise)
52.80
52.29
27.59
61.72
35.08
MLP (pairwise)
58.76
51.59
26.71
58.68
43.31
Resnet (pairwise)
57.53
42.95
22.35
46.72
47.67
learning. While our approach is not needed in the unary model, the unary model is a useful testbed for our method, as we can use (17) as a ground-truth for evaluating T.
Results. We evaluate our models on classical multilabel classification datasets. The hyperparameters (learning rate and regularization) are optimized on a validation set. Once the best hyperparameters are found, we refit the model on the combined training and validation sets and evaluate on the test set. Our results in Table show that the logistic and sparsemax losses trained with our approach work better than the generalized Fenchel- Young loss as well as min-mas max and MCMC sampling approaches in various configurations. For the min-max approach, we use optimistic ADAM as solver, an MIP as generator and we use REINFORCE (score func- tion estimator) for gradient estimation. For MCMC sam- pling, we standard Metropolis Hastiings-astssss algorithm with uniform proposal distribution. We also present learning curves in Figure 1. We numerically validate that our ap- proach converges to true MLE as more y samples are used. We also observe a regularization phenomenon: using fewer y' samples leads to better f1 scores than exact MLE. These findings are confirmed on other datasets (Figure 3).
Pairwise model (Ising model). To try our approach on model for which a closed form is not available for the oog-paritiinn, we consider quudar-quadratic coupling,
$00, y) (u, y) + (/ , Uy)
4: b
Uزbs +
U UijykUb
1=1
;=1==1
where = (w, & Rixk As its name indicates, this coupling linear 6, but quadratic in y. The model function h associates weights uy to labels yj and weights U,j to pairwise label interactions y.yly. The relaxed inference problem (9) becomes
3 (x) argmax & (0, v1) argmax(u, μ1) (m, U). 1]
Generalization ability of the learned partition function. A natural question is whether the learned log- partition gen- eralizes to unseen test samples, that is, whether it correctly approximates the true log partition function. To empirically demonstrate this, we consider the unary model, for which the log-sum-ex, enjoys the closed form solution (17). We parameterize т as an ML. and g as linear network. Af-
Contrary to the unary model case, there is no longer closed- form solution. However, if we assume that U is negative semi-definite (which is easy to impose), this problem is concave in f and can be solved optimally without learning rate tuning using coordinate ascent (Blondel al., 2022).
8

---

Joint Learning of -hargy-baased Models and their Partition Function
Table 2. Kendall rank correlation coefficient on label ranking for different models and losses, with MI.P model
Loss
Polytope C
Model g
authorship
glass
vehicle
vowel
Logistic (min-min)
P
Linear
85.14
80.47
57.78
79.74
50.82
91.36
P
MLP
$8.69
84.39
97.78
86.27
74.26
90.12
B
Linear
87.71
81.29
97.78
83.33
56.33
95.06
B
90.80
85.43
98.52
Sparsemax (min-min)
P
Linear
84.88
79.84
52.59
78.76
50.25
93.83
P
MLP
86.52
85,94
99.26
85.75
68.34
91.36
B
Linear
89.09
79.43
97.78
82.81
56,24
90, 12
B
MLP
87.84
80.47
98.52
87.19
55,43
85,80
Logistic (MCMC)
P
Linear
84,29
80.67
55.56
79.15
49,97
91.36
P
MLP
87.90
75.50
97.04
86.34
57.90
91.98
B
88.10
79.33
97.78
B
ML.P
89.68
80. 16
97.78
85.88
48.90
91.98
Logistic (min max)
P
Linear
61.01
79.22
61.48
70.20
45.68
65.43
P
MLP
70.02
67.03
55,56
68.56
40.22
70.99
B
82.58
78.40
61.48
B
MLP
78.50
71.68
42,96
68.76
48.99
83.33
ter training, we evaluate the learned T on 100 randomly sampled test samples and compare it with the true log-sum- exp. Results are shown in Figure 2. We observe strong correlation between the learned and true log-sum-exp.
linear model, while the logits when using the permutahe- dron are in R² which gives the ability to assign weight to single labels only. However, when using an MLP, we ob- serve that the permutahedron works as well as the Birkhoff polytope, which is thanks to nonlinearity. The logistic and the sparsemax losses perform comparably overall.
4.2. Label ranking
In this section, we perform label ranking of labels. Given an input æ, the goal is to predict a ranking y of the labels,
5. Conclusion and future work
that is, permutation of (L, (L....,k) k). The cardinality then D = k!. We focus the bilinear coupling Φ y) (0, y)- We consider two representations for permutations.
In this paper, we proposed a novel min-min formulation for jointly learning probabilistic EBMs and their log- partition in combinatorially-Iarg spaces. Our method provably solves the MLE objective when minimizing the expected risk in the space of continuous functions. To optimize the model parameters, we proposed a doubly-stochastic MCMC-frre SGD scheme, which only requires the ability to sample outputs from a prior reference probability distribution. We experimentally showed that parameterizing t as a neural network leads to successful generalization on unseen data points. We demonstrated our method through experiments multilabel and label ranking tasks.
Permutahedron. permutation can be represented as a vector. In this case, c)nv()') = P, where is the per- mutahedron (Bowman, 1972; Ziegler, 2012; Blondel al., 2020b). We set the logits 0 h(()) & The argmax (ar) = argmax (f,, y) argmax (0. y) can be solved optimally using an argsort (Sander et al., 2023, Proposition 1). However, LSE,, and Hg are known to be #P-complete to compute, making classical MLE intractable.
In this paper, we evaluated our proposed method primarily in the prediction setting (finding the mode). Our paper does not directly address the challenge of sampling from p(y x), which is central to evaluating performance a probabilistic or generative setting. We leave to future work whether the learned log-partitee pertitaiiin function can be used design better samplers.
Birkhoff polytope. A permutation can also be represented as permutation matrix. In this case, conv())) = B, where B is the Birkhoff polytope, the set of doubly-stochastic matrices. The logits are 0 = h(x) E & The argmax (x)) argmaxyey (0, y) = argmaxyes' (0. y) can be solved optimally using the Hungarian algorithm (Kuhn, 1955). However, LSE, and Hg are again #P #P-complete to compute, making classical MLE intractable.
Acknowledgements
Results. We use the same procedure as before to tune the hyperparameters. Our main results are in Table 2, confirm- ing that our approach successfully learns in the space of permutations. The Birkhoff polytope works better than the permutahedron when using linear models. This makes sense because the logits when using the Birkhoff polytope are in k enabling to capture label interactions even with a
We thank Alexandre Ramé as well as the anonymous re- viewers for constructive feedbacks on this paper.
9

---

Joint Learning of Energy-based Models and their Partition Function
Impact statement
Fischer, A. and Igel, C. Empirical analysis of the divergence of gibbs sampling based learning algorithms for restricted boltzmann machines. In International conference on artificial neural networks, pp. 208 108-217.2 Springer, 2010.
This paper introduces a novel formulation for learning con- ditional EBMs. We do not foresee any specific ethical or socictal implications arising directly from this work.
Garrigos, G. and Gower, R. M. Handbook of conver- gence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301.11235, 2023.
References
Ackley, D. H., Hinton, G. E., and Sejnowski, T. J. A learning algorithm for Boltzmann machines. Cognitive Science, 9 (1):147-169, 1985.
Gutmann, M. and Hirayama, J.-i. Bregman divergence as general framework to estimate unnormalized statistical models. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2011.
Ali, S. M. and Silvey, S. D. A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society: Series B (Methodological), 28(1):131-28 142, 1966.
Gutmann, M. and Hyvärinen. A. Noise-contrastive esti- mation: A new estimation principle for unnormalized statistical models. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AIS- TATS), pp. 297-304, 2010.
Amos, B., Xu, I.., and Kolter, J. 7. Input convex neural networks. In Proceedings the the International Conference on Machine learning (ICML), pp. 146-155, 2017.
Hinton, G. E. Training products of experts by minimizing contrastive divergence. Neural Compulation, 14(8):1771- 1800, 2002.
Arbel, M., Zhou, L., and Gretton, A. Generalized Energy Based Models. In International Conference On Learning Representations, 2021.
Ho, J. and Ermon, S. Generative adversarial imitation learn- ing. Advances in neural information processing systems, 29, 2016.
Bach, F. Learning theory from first principles. MIT press, 2024.
Blondel, M. and Roulet, V. The elements of differentiable programming. arXiv preprint arXiv:2403.1 14606, 2024.
Hyvärinen, A. Some extensions of score matching. Com- putational Statistics & Data Analysis, 5195):249--2512. 2007.
Blondel, M., Martins, A. F., and Niculae, V. Learning with Fenchel-Young losses. Journal of Machine Learning Research, 21(55) 2020a
Hyvärinen, A. and Dayan, P. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
Blondel, M., Teboul, O., Berthet, Q., and Djolonga, J. Fast differentiable sorting and ranking, In Proceedings of the International Conference on Machine learning (ICML), pp. 950-959, 2020b.
Kingma, D. P. Adam: A method for stochastic optimiza- tion. In Proceedings of the International Conference on Learning Representations (ICIR), 2014.
Blondel, M., LJinares-López, F., Dadashi, R., Hussenot, L.., and Geist, M. Learning energy networks with generalized Fonchel-young losses. Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), 35: 12516-12528, 2022.
Konda, V. and Tsitsiklis, J. Actor-critic algorithms. Ad- vances in neural information processing systems, 12, 1999.
Korotin, A., Li, L., Genevay, A., Solomon, M., Filip- pov, A., and Burnaev, E. Do neural optimal transport solvers work? continuous wasserstein-2 benchmark. Advances in neural information processing systems, 34: 14593-14605, 2021.
Bowman, J. Permutation polyhedra. SIAM Journal Applied Mathematics, 22(4):580-589, 1972.
Boyd, S. Convex optimization. Cambridge 2004.
Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., and Zhang, Q. JAX: composable transformations of Python+NumPy programs, 2018. URL http:// /tl::///ittin tuuh..uubb.... com/ jax-mi/ jjax
Kuhn, H. W. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2): 83-97, 1955.
Lafferty, J., McCallum, A., Pereira, F., et al. Conditional random fields: Probabílistic models for segmenting and labeling sequence data. In Proceedings of the Interna- tional Conference on Machine learning (ICML), 2001.
Csiszár, I. On information-tye -tppl measure of difference of probability distributions and indirect observations. Studia Sei. Math. Hungar., 2:299-318, 1967.
10

---

Joint Learning of Energy-basee Models and their Partition Function
LeCun, Y., Chopra, S., Hadsell, R., Ranzato, M., Huang. E., et al. A tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
Seguy, V., Damodaran, B. B., Flamary, R., Courty, N., Rolet, A., and Blondel, M. Large-scale optimal transport and mapping estimation. In Proceedings of the International Conference on Learning Representations (ICLR), 2018.
Martins, A. and Astudillo, R. From softmax to sparsemax: A sparse model of attention and multi- classification. In Proceedings of the International Conference Machine learning (ICML), pp. 1614-1623, 2016.
Senetaire, H., Jeha, P., Mattei, P.-A., and Frellsen, J. Learn- ing Ehergy-Baseed Models by Self-normalising the I. Likeli- hood. arXiv preprint arXiv:2503.0700 5000000002,, 2025.
Martins, A. F., Treviso, M., Farinhas, A., Aguiar, P. M., Figuciredo, M. A., Blondel, M., and Niculae, V. Sparse continuous distributions and Fenchel-Young losses. Jour- nal of Machine Learning Research, 23(257):1-74, 2022.
Song, Y. and Kingma, D. How to train your energy-based models. arXiv preprint arXiv:2 2021.
Sutton, C. and McCallum, A. An introduction to conditional random fields. Foundations and Trends@ in Machine Learning, 444:22673373, 2012.
Meng, C., Choi, K., Song, J., and Ermon, S. Concrete score matching: Generalized score matching for discrete data. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Informa- tion Processing Systems, volume 35, pp. 2022.
Wainwright, M. J. and Jordan, M. I. Graphical models, ex- ponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1-2):1-305, 2008.
Wang, B., Ou, Z., and Tan, Z. Learning Trans-dimensional Random Fields with Applications to Language Model- ing. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 4064))876-890, 2018.
Mensch, A., Blondel, M., and Peyré, G. Geometric losses for distributional learning. In Proceedings of the Inter- national Conference on Machine learning (ICML), pp. 4516 4525, 2019.
Ziegler, G. M. Lectures on polytopes, volume 152. Springer Science & Business Media, 2012.
Nowozin, S., Cseke, B., and Tomioka, R. f-GAN: Train- ing generative neural samplers using variational diver- gence minimization. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), volume 29, 2016.
Zmigrod, R., Vieira, T., and Cotterell, R. Efficient compu- tation of expectations under spanning tree distributions. Transactions of the Association for Computational Lin- guistics, 9:675-6999 2021.
Pihlaja, M., Gutmann, M., and Hyvärinen, A. A family of computationally efficient and simple estimators for unnor- malized statistical models. In Proc. Conf. Uncertainty in Artificial Intelligence (UAI), pp. 442-449. AUAI Press, 2010.
Pillutla, V. K., Roulet, V., Kakade, S. M., and Harchaoui, Z. A smoother way to train structured prediction models. Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), 31, 2018.
Rafailov, R., Sharma, A., Mitchell, E.,, Manning, C. D., Ermon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Proceed- ings of the Conference on Neural Information Processing Systems (NeurIPS), 36, 2024.
Sander, M. E., Puigcerver, J., Djolonga, J., Peyré, G., and Blondel, M. Fast, differentiable and sparse top-k: a convex analysis perspective. In Proceedings of the Inter- national Conference on Machine learning (ICML), pp. 29919 29939, 2023.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint 1707xv:7077066.40 2017.

---

Joint Learning of Energy- -baed Models and their Partition Function
A. Experimental details and additional results
Loss (train)
Gradient norms (train)
fi score (test)
1.50
0.55
Yeast
1.25-
0.50
1.00
0.45
7-
0.75
0
2000
4000
0
2000
4000
0
2000
4000
4.0
3.0
0.65
2.5
3.5
0.60
Scene
2.0
3.0
1.5
0.55
2.5
1.0
0.50
2.0
0.5
0
1000
2000
3000
4000 5000
0
1000
2000
3000
4000 5000
0
2000
4000
0.68
4.0
Emotions
2.0
0.65
3.5
1.5
0.62
3.0
1.0
0.60
2.5
0.5
0.58
0
2000
4000
0
2000
4000
0
2000
4000
12.5
0.35
10.0
Birds
7.5
0.30
5.0
0.25
2.5
2000
4000
2000
4000
20000
4000
70
Mediamill
65-
0.5
5-
60
554
0.3
50
0
2000
4000
0
2000
4000
0
2000
4000
1 y sample
100 y' samples
100 000 y' samples
10 y' samples
1000 y' samples
Exact MLE
Figure 3. Convergence of the proposed approach as function of the number of prior samples y' drawn. To be able compute the exact MLE objective (15), we use the unary multilabel model (Section 4. as the test bed. Note that the loss and gradient in the left and center columns are computed using (15) even for our method. We make two key observations: our approach converges to exact MLE as predicted by our theory, ii) the number of y samples can have a regularization effect on the test fi fi-score.
Our implementation is made using JAX (Bradbury et al., 2018).
12

---

Joint Learning of Energy-based Models and their Partition Function
Multilabel classification datasets. We the datasets in Blondel al. (2022). The datasets can be downloaded from https: : www. www..csieeeee......... nt.ieennu.eee edu. http://ttt...........//o//////// /tta://sssttoooosattttttttttt The dataset characteristics
described in Table below.
Table 3. Dataset Characteristics
Dataset
Type
Train
Dev
Test
Features
Classes
Avg. labels
Birds
Audio
134
45
172
260
19
1.96
Cal500
Music
376
126
101
68
174
25.98
Emotions
Music
293
98
202
72
6
1.82
Mediamill
Video
22,353
7,451
12,373
120
101
4.54
Scene
Images
908
303
1,196
294
6
1.06
Yeast
Micro-array
1,125
375
917
103
14
4.17
Convergence curves. Convergence curves are in Figure 3. We use linear model for (unary model). and an MLP for with ReLU acivation and a hidden dimension of 128. Models are trained with the logistic loss. We use the Adam optimizer (Kingma, 2014) with learning rate of 10 for the parameters of both and т. The models are trained for 5000 steps with full batch w.r.t. (æ,, Y/) pairs. The reason why we full batches is reduce the noise in the gradients and obtain more stable training procedure.
Results different models and losses.
Additional experimental results shown in Tables 4 and 5.
Table 4. fi-score on multi-label classification for different models and losses, with ICNN r model
Loss
Model g
yeast
scene
birds
emotions
cal500
logistic
Linear (unary)
63.53
70.44
45.36
62.90
42.74
MLP (unary)
65.16
74.64
46.58
64.99
44.89
Resnet (unary)
65.40
75.60
38.71
67.05
45.23
Linear (pairwise)
63.53
70.47
45.36
62.90
42.75
MLP (pairwise)
64.95
74.84
44.11
64.52
45,00
Resnet (pairwise)
65.15
75.53
39.59
66.17
44.62
sparsemax
Linear (unary)
63.15
71.07
45.79
63.36
45.94
MLP (unary)
63.52
74.34
40.77
66.50
46.44
Resnet (unary)
62.62
76.79
30.18
63.38
46.64
Linear (pairwise)
63.15
71.05
45.79
63.36
45.94
MLP (pairwise)
63.25
74.93
41.61
66.18
46.40
Resnet (pairwise)
62.07
75.59
28.14
63.42
37.53
13

---

Joint Learning of Energy-based Models and their Partition Function
Table fcore on multi-label classification differrnt models, with logistic
Model 7
Model
yeast
scene
birds
emotions
cal500
Constant
Linear (unary)
63.41
70.78
45.49
61.63
40.19
MLP (unary)
65.04
75.35
46.48
65.33
44.91
ResNet (unary)
65.03
75.64
36.93
67.45
45.23
Linear (pairwise)
63.40
70.72
45.49
61.63
40.23
MLP (pairwise)
65.11
75.22
46.08
64.84
45.00
ResNet (pairwise)
64.84
75.68
41.34
64.26
44.61
MLP
Linear (unary)
61.51
70.77
44.65
60.93
42.40
MLP (unary)
62.03
70.81
39.70
62.26
46.24
ResNet (unary)
63.01
70.69
25.25
62.60
45.65
Linear (pairwise)
61.52
70.81
44.65
60.85
42.08
MLP (pairwise)
62.42
69.96
38.89
63.38
46.08
ResNet (pairwise)
63.04
70.90
33.79
63.11
45.25
ICNN
Linear (unary)
63.53
70.44
45.36
62.90
42.42
MLP (unary)
65.15
74.65
44.99
64.99
44.89
ResNet (unary)
65.39
75.60
38.84
67.10
45.23
Linear (pairwise)
63.53
70.47
45.36
62.90
42.42
MLP (pairwise)
64.94
74.84
45.82
64.52
45.00
ResNet (pairwise)
65.14
75.30
39.52
66.30
44.62
Label ranking. The publicly-available datasets can be downloaded from https: //gpttbtbbttt////////////t com/ cww//korbaaaaaa..eoo aaooba/ St BalcttrredApproacee Labe ______aniinn The experimental results are summarized in Tables 6 and 7.
Table 6. Kendall's tau on label ranking for different models and losses, with MLP r model
Loss
Polytope
Model
authorship
glass
iris
vehicle
vowel
wine
logistic
P
Linear
85.14
80.47
57.78
79.74
50.82
91.36
logistic
P
MLP
88.69
84.39
97.78
86.27
74.26
90.12
logistic
P
Resnet
88.49
84.29
98.52
87.06
71.08
93.21
logistic
Linear
87.71
81.29
97.78
83.33
56.33
95.06
logistic
MLP
90.80
85.43
98.52
86.41
65.20
91.98
logistic
B
Resnet
88.89
85.74
97.04
86.73
62.17
91.98
sparsemax
P
Linear
84.88
79.84
52.59
78.76
50.25
93.83
sparsemax
P
MLP
86.52
85.94
99.26
85.75
68.34
91.36
sparsemax
P
Resnet
88.17
85.53
58.52
86.21
59.52
90.74
sparsemax
B
Linear
89.09
79.43
97.78
82.81
56.24
90.12
sparsemax
MLP
87.84
80.47
98.52
87.19
55.43
85.80
sparsemax
Resnet
89.22
84.70
97.04
87.52
55.87
91.98
14

---

Joint Learning of Energy-baser Models and their Partition Function
Table 7. Kendall's label ranking for different models, with logistic loss
Polytope C
Model
Model
authorship
glass
iris
vehicle
vowel
wine
P
Constant
Linear
84.94
79.64
57.78
79.61
49.18
91.98
P
Constant
MLP
87.38
84.39
97.04
85.75
73.68
89.51
P
Constant
ResNet
88.10
83.88
98.52
87.19
68.98
94.44
B
Constant
Linear
88.17
77.16
97.78
83.66
57.29
95.06
B
Constant
MLP
89.41
84.19
98.52
87.32
62.36
91.98
B
Constant
ResNet
88.76
84.60
98.52
87.78
62.70
91.98
P
MI.
Linear
85.14
80.47
57.78
79.74
50.82
91.36
P
MLP
MLP
88.69
84.39
97.78
86.27
74.26
90.12
MLP
Resnet
88.49
84.29
98.52
87.06
71.08
93.21
B
MLP
Linear
87.71
81.29
97.78
83.33
56.33
95.06
B
MLP
MLP
90.80
85.43
98.52
86.41
65.20
91.98
B
MLP
Resnet
88.89
85.74
97.04
86.73
62.17
91.98
P
ICNN
Linear
84.35
75.30
56.30
79.74
50.84
91.36
P
ICNN
MLP
84.62
83.67
82.96
84.84
65.24
93.83
P
ICNN
ResNet
87.25
82.53
85.19
83.66
65.09
93.83
ICNN
Linear
88.76
81.71
87.41
82.88
53.94
95.06
B
ICNN
MLP
90.20
77.98
90.37
84.97
46.83
94.44
B
ICNN
ResNet
89.81
85.01
91.11
85.42
54.48
93.83
B. Additional materials
B.1. Loss functions using other forms of supervision
To workaround the intractable log-partition function arising in MLE, another alternative is to use loss functions that leverage other forms of supervision than (x, z) pairs. We review them for completeness, though we emphasize that these methods do not learn the probabilistic model (1).
Learning from pairwise preferences. ær we can learn a Bradley-Terry model
If we have dataset of triplets of the form (æ, V+. U-) such that y+ > y- given
Po(y1 y2(z)) sigmoid(g(a; yi) g(x, 92))
exp(g(x, y1))
exp(g(æ, (x)(g(),)))) exp(g(a, y2))
where (u) = +x/(1=eep(x))) the logistic sigmoid. The loss associated with the triplet (æ, y+, y.. is the pairwise logistic loss, log Py (g y++ y-|=)) major advantage of this approach is that there no log- seg--artition involved. The DPO loss (Rafailov et al., 2024) can be thought generalization of this pairwise logistic loss to non-uniform prior distributions However, it learns probabilistic model of yı > y2 given not of y given
Learning from pointwise scores. As an alternative, if we have dataset of triplets (x, y.t) where t scalar score assessing the affinity between and y, for instance binary score or real value score, we can use {gg(x, y), for some classification or regression loss f. Again, pog-partiioon is involved However, this corresponds to learning probabilistic model of f. given (æ, y), not of given
estimate the parameters of directly.
B.2. Fenchel-Ye Fenchel-Young losses
Let us define some dual regularization
(p( = 0 + (p)
where is is the indicator function of the set and dom( C P))).. common choice for Ω4 is the negative Shannon entropy Q_ (p) = (p. log p) but we will see below how to define very general family of regularizations using f-divergences.
15

---

Joint Learning of Energy-based Models and their Partition Function
Given g E F()) and p E Pi()), we define the Fenchel- Fenchel-Young loss (Blondel al., 2020a) regularized by Qn
La, p) ()) (p) (g. p)
(9) (p) Eyyplg(y)]
The Fenchel- Young loss is primal-dual, in the sense that we see F()) as primal variable (a function) and Pi()') as dual variable (a distribution). We will omit the constant term {1()) in our derivations. While focus discrete spaces in this paper, Fenchel- Young losses were also extended to continuous spaces in Mensch et al. (2019); Martins et al. (2022).
C. Proofs
We define the shorthand notations Pee = p(-12x), Ux == q(11z> and IR g(xx :).
C.1. Lemmas
In this section, we state and prove useful lemmas.
Lemma S2 as unconstrained minimization of St
Ler Q1 = S2 + (P). where Q_ is convex with dom (2+) S P+)).. Then, all F()),
(h) min r + + 7) E FER
and
VhT = (h (") E F()),
where T* is an optimal solution.
Proof.
(h) (h.p) - (p)
PEP:())
max pEP pEP+()) FER
min(h,p) (p) 7(p,
min T + max (h-TT,P 0+(2) (p)
rEBl
p)P+()))
min + St (h -)..
FER
The expression of Vi2 (h) follows from Danskin's 's theorem. 0
Lemma Given f+: R4 + R. p E ())) and fixed reference measure q E P+()), let
(4(1:)) = (f+(p/g).
Σ
DEY
Then,
11(h) = [000)><0 (())) ER
yEY
and
-(0))))))) E R+-
Proof. This follows from classical conjugate calculus.
C.2. Proof of Proposition 1 (equivalence with MLE, expected risk setting)
Proposition a corollary of Proposition 4 with the choice
f(u) = woo (u - (+(
(18)
16

---

Joint Learning of Energy-basee Models and their Partition Function
In this case, obtain Using Lemma 2, we obtain for all a E X
((()))))) = Σ
cllv/=)esp(0(2.00 -(x)) 1].
vEy
For x fixed, minimizing w.r.t T, we get
Σ DEy
(f))) -) ((x)) =1
Σ
y) -(())) =
yey
cxp(g(z) y)) exp(r(x))
y
log
Σ
((yl)) v)) = r(x:),
MEY
which is continuous in if g itself continuous. Thus the overall objective
min min Em r(x)+ + TEF())
Σ
(exppxl) y) - =(x)) 1]
( v)
yEY
and
Tg To (y) = ( exp(g" (a, y) - r(x))
C.3. Proof of Proposition 2 (optimality in the empirical risk setting)
Using Lemma
with h = g(xx,)) +). we obtain
min gE)(X()) Σ (0m.i (g sw1i1
min xEF(Xx)) i=1
Σ
min T; + 12 (9u. Tsi (1x.) (ome (yc)) neR
min ,EF(Xx))
min TER
Σ
[(T + 22 (9x, Túi q0,))) - (gee, 0y.t)]
i=1
where by E P))) delta distribution such that (,/()/ for y = y and 0 for y + y. Choosing (18) as the proof of Proposition gives the final result.
C.4. Proof of Proposition 3 (min-max formulation)
We have
min (EF(XX))
C(g)
min 3EF(XX
Eg (z) (gas Pax) + const
( (eEE)))) (gm,Pa)) KL (mm) (ym, pm))
min gEF(XXy)
Ex
const.
min max xEF(XX)) P (>
Ex [(gg, Pw) KL qx)) (ger Poell + const
min (x)(XXX) PEP: ())
max
E (Eyypa [g(x, y)] KL 9m))
Eayxpa I9(x,, b)]l + const.
C.5. Proof of Proposition 4 (optimality in the general Fenchel- Tennhel-Young loss and expected risk setting) Using Lemma with = g(x, :). we obtain
(min Ta + 22 (9a Tai (xe) (ga. pal) (weE
min Ex [ (g2i que) (gxx px)) (xF(XX))
min (EF(Xx))
Ex
17

---

Joint Learning of Energy-basee Models and their Partition Function
We going show that
min Ta + 127 (gt Twi = ===(x) + 22 (9x - -x)();;; (m) ER
where r" E F(X).
Step 1. We first show that we can define function + T" (x))
We have Tæ + +2 (Ix Twi qw) = Eyey { (f (0( y) - Twi (0))) with f((0) = lim (x) U {-o0). Without loss generality, we can assume that q > 0 for all y and æ.
Since (0, +00) _ dom f', q and y is finite, I' ([EEe)((Vaa)) ") and f'( minyay )())))) )
are well defined. We can
then define
Fmin(x)) = max ((x y) - (mingey g(yl(x)) (( yEy
Σ ( NEY
Tmax (2) = max g(x; y) -
alv alylar)) ar)
yEy
Since q > 0 and since f' is increasing, one has Tmin Tm)n(()) < Tmax (x:)
We can then analyze the following function on [Tmin (x), Tmax (2)) x X::
h(T, x) + BEy
of (max(g() =f
First, need to ensure that (Tmia( Tmax [x=)] We have that f (max (g(#, y) (0)))) = (ʃ + (g(a,, y) - r) and dom + (R. Y, dom f,, f'()). Therefore, if (0) > -o0, the domain of (f+ Y' is unbounded below. Otherwise, if (0) = -00, since Im C dom S. the domain of f, and so of (s+1R) Yz. are unbounded below. Denoting then a = sup dom + )a, since maxyey g(x y) (m)n(x) = f ( mingey d(w x5) E dom fh, we have maxyey g(x, y) - Tmin(() < a and therefore
compute derivatives of this funetion with respect to its first variable in
Tiin (x)
= max y (xx y) < yEy
g (æ, y) - < a, for all y E y
dom h'
We can then show that h (Tmin(x), x) < 0 and // (T(maaxx(e (Fimax())) x) 2 0. Indeed, denoting y argmax g( y) (we omit the dependency in x to ease the notations), we have
(Tmin (x), x)) =1 Σ (f y) - Tmin (x),
yEy
(
S (1 (Inax
Tmin (z))
q( (x: (max {f
mingey (()))0) (0)))
n' (x)
minger((((, $
where (i) we used that q > and fl (max(2, f())) 2 for any E dom(f + 1R. Ya. and in (it), we used that f is increasing and (z) = p for any p E dom
18

---

Joint Learning of Energy-based Models and their Partition Function
Similarly, we have
11' (Tmmax (Tmax(2)),2))
= Σ ([ y) - (2),
(4)
2
( (m v²) Tmax: f())))
(Eee)((ola)) S. (max {s ((Eves((o)z)) - m(0)))
0,
where in (i) we used that Eg agby I (E maxy by if oy 2 with here ay = ((y)az) > 0 and by ft. (1 y) Fmmx(()), (0))), and in (it) we used the same reasoning as for h' (Tmmm)))
Finally, we show that h' is increasing on (mmin(a) (a)x When S Tm) one has maxyey g(a, y) maXyEy (x, y) Tmax (x) 2/ (O).
2
Since 0 + f. (0, (()))) is increasing on dom f (-00, [())] we have that J - (max y²) T, f'(0)))
increasing on [Tmii (ar), Tmax (a)] and therefore T + (T( x) = Ever ((y)))))) (max (g( (x,,))))) y) T, (())))
increasing on (2)), Tmax [z)]]
Overall h is well defined and strictly convex on (x)i,()), Tmax( such that ht' (Tmin(x)) 0 and h' (Tmaxx (x)) 0. Hence, since h is convex, we have
min inf l((T, x)) = Tmin (c)) h(T, x)
FER
and the unique minimizer (x)) can then be found by solving the first order optimality condition l'(T, x) 0
in [Tiin (x), Tmax (x)]. We can therefore define function I" mapping each to the unique root of hl(T, in (x), Tmax (.))
Step 2. We then show that 7* is continuous.
Note that, because Y is finite and æ + ((y) x), x + g( y) and f' are continuous, both Tiin and Tmax are continuous functions æ. Let (s be sequence such that æy - x as k + +oo. Since Tiin and Tmax are continuous, Tmin 72in(222) + Tmin (x) and (xx) + Tmax(() (z). Therefore, (r* (xx))) is bounded sequence. As such, it admits a converging sub- sequence (7* (I))()))) converging to some t" (=x).. One has h h'(r" (I=p()))) ((())) 0. By continuity of h', this gives h'(1" (xx), a²) = 0 and therefore 1" (xx) = r=()) by unicity of the root. Therefore, any converging subsequence of the bounded sequence (xxx) converges to 7* (x). This exactly proves that (*xx + (x) as l + +oo. Therefore, 7" is continuous and
Ex min [Te + 2- (gx r=)] Ez [r'(x)
S (g= 7 (ax)))
To ER
Step Last, we show that eF(2) En [T(x)) + 27, (0mm [xx))] FP min, eR [TH + 2 (g. - T=)]
By definition of T*, we have min Eg [T(x) + 27 (gx - T x(x)) v Ex [r*(x) + 2 (ox - [=))]] =
Eg min [To + 22 (gx rw)]. On the other hand, for any x and any 7 E F(X), we have
Ex (T(x) + 01 (gh - r(x))] 2 Ex min [Te + 22 (gr - Ta) T
Since this holds for any continuous function т, this gives
min F2 [T(x)) + 2 (Ix - r(x:))] 2 En min TE)(2)
[Te + 22 (gm - Tm)]
TxE3
We then have
min Ey [T(x)) + 2 (g - r(x))] = Ex min reF(x)
[Te + 22 (ge - Tm)]
T=ER
Therefore,
min )))
Exe [22] (gzi qxe) (a))
min
min Ex [T(x) + 527 (gx -(xx)) (ge, px))
DEF(Xx))
TFF())
19

---

Joint Learning of Energy-based Models and their Partition Function
In addition, for all (x, v) (X x))
Ty" (x) V2 r'(x))=))()) d(vl)) y)).
This concludes the proof.
C.6. Joint convexity
Proposition 5. Given E (+()))) f differentiable, strictly convex well defined on (0, f. a coupling Iu (2, y) linear in w E W and a finite dimensional representation of the log-partition function, To (2;) = vi for E [n], the objective
[gw To) Σ
12
L' Too (xx))
Iw (2 02((211))) (12..11))
n1
where
L To (ais)
To (xx))))
E
(x))) 1/ (x()))
y'ey
is jointly convex in w, v. where f is the convex conjugate of the restriction of f to R...
Proof. The function (w, U, + Iw (a;, v') To (x:) is linear in w, by assumption. Since f is convex, (w, v) + f4 (Iw (2 yz) To (xx)) is then jointly convex in w. since the composition of a linear function and a convex function is always convex. Since ((y/ (ax;) is positive, (wo, v) - q<y [ (a: y') - To (Rx)) is also jointly convex. The functions w + Iw (z;, ys) and v + To (2;;) are linear wo and v respectively. sum of convex functions is convex hence result.
C.7. Proof of gradient computation
One has
L.S. (x: = V. log w Sio
Σ ((ylar) (xp(s y)) NEY
Eney (yy x exp(sw (x, y))
E yyy ( a)) exp (2. y))
Eyey I'y x.) exp (rr, y) V (w (x)
Ey x)) [exp(sw (2x, 3)) ww y)
Evey ( x)) exp (x,
E Ey m) [exp(sw (x, 3))
Σ Par (y]x)) V ww (x. y) = E Byrpon (:1z)) [V Vwweao (2c, y)]
MEY
20


Reviews:
[{"review_id": "26Q5PiFBBY", "reviewer": "Reviewer_2WK7", "summary": "Authors formulate the MLE of Energy Based Models as a constraint problem with the equality contraint defining the partition function. Then they suggest performing stochastic optimization by learning jointly the energy model and its associated dual variable. Amortization is suggested by parameterizing the dual as a neural network.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback. \n\n> **Lack of baselines, comparison with MCMC and adversarial approaches**\n\nWhile our paper includes GFY and exact MLE (logistic loss) baselines, it did lack comparisons with MCMC and min-max approaches. We have run additional experiments with these baselines.\n\n**Link to updated Table 1 and Table 3:** https://anonymous.4open.science/r/ebms/tables.pdf\n\nIf the paper is accepted, these tables are going to be included in the main text, thanks to the extra page allowed by the camera-ready.\n\n**Technical details:** For the the min-max approach, we use optimistic ADAM as solver, an MLP as generator and we use REINFORCE (score function estimator) for gradient estimation. For MCMC, we use standard Metropolis–Hastings algorithm. Similarly to the min-min approach, we tune the learning rate and L2 regularization using grid search.\n\n> **Amortized optimization in the dual problem, neural OT [1]**\n\nWe agree that parameterizing dual variables as neural networks is a commonly-used technique in the OT literature. We already cited Seguy et al. (2018) and will gladly add the suggested citation [1]. Technically, the dual variable in [1] is a convex function, hence the use of ICNNs. In our work, the Lagrange multiplier $\\tau$ is a continuous function.\n\nThat said, we believe our application of that idea to EBMs remains novel and significant. To our knowledge, we are the first to parameterize the log-partition function of conditional EBMs as a neural network. We believe that parameterizing dual variables with neural networks is a powerful concept with potential applications beyond OT and EBMs.\n\nRegarding amortized optimization, its goal is typically to accelerate the process of repeatedly solving similar optimization problems. In our paper, the primary goal of parameterizing the log-partition function $\\tau$ as a neural network is different: it is to enable the approximation of the log-partition function to generalize to unseen data points $x$.\n\n> **Why EBMs are particularly suited to this approximation over Monte Carlo-based methods?**\n\nAs discussed in Section 2.4, sampling from EBMs, especially in discrete spaces, is often challenging and typically requires MCMC methods like Langevin-MCMC (for continuous spaces). For discrete output spaces, constructing an MCMC sampler is less explored and can be more challenging. Typically each particular output space (such as sets or permutations in our work) will require a specifically-designed sampler.  In contrast, our proposed approach offers a simpler, more generic alternative that avoids MCMC sampling during training by jointly learning the energy and the log-partition function.\n\n> **Relocating section on Fenchel-Young losses**\n\nWe chose to include the Fenchel-Young losses because they encompass the sparsemax loss. Our work presents, to our knowledge, the first tractable method for optimizing the sparsemax loss for EBMs in general combinatorial spaces without needing a k-best oracle. Thanks to the extra page in the camera-ready, we believe we do not need to move this.\n\n> **Experiments [in Figures 1 and 2] appear to be limited in scale and provide minimal insight**\n\nOur primary goal in these experiments was to demonstrate scalability concerning the number of classes $k$, which determines the size of the output space ($|Y| = 2^k$ for multilabel classification, $|Y| = k!$ for label-ranking). Scalability with respect to the number of training samples $n$ is handled via standard SGD. \n\n\n> **Table 1 not discussed enough**\n\nThe key takeaway from Table 1 is that the Birkhoff polytope representation tends to perform better with linear models for label ranking, likely due to its ability to capture more interactions. However, with more expressive MLP models, both the Birkhoff and Permutahedron representations achieve strong performance.\n\n> **Eq 12 and 13 should be better introduced**\n\nThank you for the suggestion.  By minimizing the overall objective with respect to both $g$ and $\\tau$, the optimization process encourages $\\tau$ to approximate the true log-partition function while simultaneously learning the energy function $g$ that fits the data under the EBM framework. We will add a brief, self-contained explanation to the paper.\n\n> **When using f-divergences what are the challenges in terms of optimization?**\n\nWhen $f$ is strictly convex, which is the case for the sparsemax loss, the loss is smooth, leading to a well-behaved optimization landscape. The primary challenge associated with the sparsemax loss in structured prediction is the need for a k-best oracle, which our approach alleviates (similarly, we do not need an LSE oracle in the logistic case).\n\n> **Which other f-divergences could be interesting ?**\n\nWe may consider alpha divergences, which interpolate between the logistic loss ($\\alpha=1$) and the sparsemax loss ($\\alpha=2$). Our approach can readily be applied with these divergences by selecting the appropriate $f$ function.", "claims_and_evidence": "In the introduction, the authors motivate their work by emphasizing the limitations of MCMC-based methods. However, the experimental section lacks a thorough benchmarking analysis and comparisons with currently established methods, leaving the practical relevance of the proposed approach unverified.\n\nFurthermore, while the authors employ an amortized optimization technique to handle a polytope constraint in the dual problem, a very common method used for instance extensively in the literature on neural OT [1], the paper does not clearly explain why the structure of the EBM problem is particularly suited to this approximation over traditional Monte Carlo-based methods. This omission underscores the need for thorough empirical ablation studies, which are notably absent.\n\nBased on this important shortcoming, I believe the paper does not meet the acceptance threshold. \n\nAdditionally, the discussion on generalization to Fenchel-Young losses appears to offer limited practical utility. For future revisions, I recommend relocating the section on Fenchel-Young losses to an appendix, thereby allowing more space for extensive large-scale experiments and detailed comparisons with current benchmarks in EBMs.\n\n[1] Korotin, A., Li, L., Genevay, A., Solomon, J. M., Filippov, A., & Burnaev, E. (2021). Do neural optimal transport solvers work? a continuous wasserstein-2 benchmark. Advances in neural information processing systems, 34, 14593-14605.", "methods_and_evaluation_criteria": "Figures 1 and 2 aim to validate the presented theoretical results. However, the experiments appear to be limited in scale and provide minimal insight into performance in real-world settings.\n\nFor the experimental part, it would be beneficial to include a thorough comparison with current MCMC-based approaches in terms of runtime, memory consumption, and final performance.\nAlso a comparison with adversarial approaches described in section 3.3 can be valuable.\n\nRemark: I believe Table 1 is not discussed enough and it is hard to understand what conclusions to draw there.", "theoretical_claims": "The theoretical claims seem sound and rigorous.", "experimental_designs_or_analyses": "This is the weakest part of the paper as discussed above.", "relation_to_broader_scientific_literature": "This work applies the very well known technique of amortized optimization on the dual problem of a convex optimization problem to the problem of learning EBMs.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "/", "other_comments_or_suggestions": "I think equations 12 and 13 should be better introduced. It would be nice to be guided in this critical part without having to look at other sections.", "questions_for_authors": "- When using f-divergences like square loss instead of KL, thus leading to sparsity, can the authors provide details about the associated challenges in terms of smoothness of the optimization? Is the method as stable as in the KL \"dense\" case?\n- Which other f-divergences could be interesting beyond the square loss and KL?   \n\nThanks!", "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": "zB3LzTSv2A", "reviewer": "Reviewer_XFTo", "summary": "The paper proposes a method for learning discrete energy-based models and their partition function. Specifically, by parameterizing the partition function as $\\gamma(x)$, the paper introduces the constraint $\\sum_y p(y|x) - \\gamma(x) = 0$, which can be incorporated into the maximum likelihood estimation using the Lagrange multiplier method. Experimental results on multilabel classification and label ranking demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback.\n\n> **Challenges of min-max implementation**\n\nTo avoid any controversial claim, we will remove “notoriously hard to optimize”. Instead, we will explain the technical challenges that arise using this formulation in more detail. \n\nThe min-max objective is $\\mathbb{E}_x \\mathbb{E}{y \\sim p(\\cdot|x)} [g(x, y)] - \\Omega(p(\\cdot|x)) - \\mathbb{E}{(x,y)} [g(x,y)]$, where $\\Omega$ is the negative Shannon entropy. The variable $p$ appears in the sampling (expectation) and in the entropy. In practice, we parameterize $p$ as a neural network. If $p$ is an EBM, sampling from $p$ is difficult and the min-max formulation does not bring any benefit. Therefore, it is common to use a parameterization such that it is easy to sample from the mode instead. \n\nAnother challenge comes from the gradient computation. Since $p$ appears in the sampling, one typically uses the score function estimator (REINFORCE) to estimate the gradient w.r.t. the parameters of $p$. However, this estimator suffers from high variance. In our min-min formulation, the variable $\\tau$ is a function, not a distribution and its gradients are easy to compute\n\n> **High-variance of Monte-Carlo estimation of expectations**\n\nOur experiments (e.g., Table 1, Table 3) were designed to show scalability with respect to the output space size, governed by the number of classes $k$ ($|Y|=2^k$ or $k!$). Scalability with the number of training samples $n$ is addressed through standard SGD optimization. Regarding the MC estimation in Eq. (13), while MC estimates can introduce variance, our doubly stochastic approach (Alg. 1) proved stable and effective in practice across our experiments. Fig. 1 illustrates that even with a small number of prior samples ($y'$), the method converges effectively, although more samples accelerate convergence towards the exact MLE objective. \n\n> **Lack of baseline comparison with other approaches, such as the variational-based min-max method.**\n\nOur paper included logistic regression (“Exact MLE” in Fig. 1 & 3) and generalized Fenchel-Young losses (GFY) (Table 3) as baselines. However, our paper did lack comparisons with MCMC and min-max approaches.\n\n**Links to updated Table 1 and Table 3** https://anonymous.4open.science/r/ebms/tables.pdf. \n\nIf the paper is accepted, we are going to include these tables in the main text, thanks to the extra page allowed by the camera-ready.\n\nFor convenience, we also show the new results below:\n\nTable 1\n\n|Loss|Polytope C|Model $g$|authorship|glass|iris|vehicle|vowel|wine|\n|---|---|---|---|---|---|---|---|---|\n|Logistic(MCMC)|P|Linear|84.29|80.67|55.56|79.15|49.97|91.36|\n||P|MLP|87.90|75.50|97.04|86.34|57.90|91.98|\n||B|Linear|88.10|79.33|97.78|82.22|55.99|**96.91**|\n||B|MLP|89.68|80.16|97.78|85.88|48.90|91.98|\n|Logistic(min-max)|P|Linear|61.01|79.22|61.48|70.20|45.68|65.43|\n||P|MLP|70.02|67.03|55.56|68.56|40.22|70.99|\n||B|Linear|82.58|78.40|61.48|74.90|52.86|93.21|\n||B|MLP|78.50|71.68|42.96|68.76|48.99|83.33|\n\nTable 3 \n\n|Loss|Model$g$|yeast|scene|birds|emotions|cal500|\n|---|---|---|---|---|---|---|\n|Logistic (exactMLE)|Linear (unary)|61.46|70.64|43.97|63.35|37.31|\n||MLP (unary)|60.71|70.81|40.88|62.99|36.24|\n||Resnet (unary)|62.27|71.02|40.78|61.50|37.45|\n|Logistic( MCMC)|Linear(unary)|61.98|70.53|44.93|61.76|44.61|\n||MLP (unary)|60.34|71.57|33.13|62.23|45.70|\n||Resnet (unary)|56.57|71.24|27.03|58.98|44.34|\n||Linear (pairwise)|61.96|70.50|44.93|61.76|44.61|\n||MLP (pairwise)|60.83|71.92|34.61|63.15|45.95|\n||Resnet (pairwise)|56.68|70.46|27.08|64.05|44.35|\n|Logistic (min-max)|Linear (unary)|52.80|52.29|27.59|61.72|35.08|\n||MLP (unary)|58.58|52.54|24.95|60.53|46.08|\n||Resnet (unary)|57.53|42.82|25.32|55.85|47.59|\n||Linear (pairwise)|52.80|52.29|27.59|61.72|35.08|\n||MLP (pairwise)|58.76|51.59|26.71|58.68|43.31|\n||Resnet (pairwise)|57.53|42.95|22.35|46.72|**47.67**|\n\n**Technical details**: For the the min-max approach, we use optimistic ADAM as solver, an MLP as generator and we use REINFORCE. For MCMC, we use Metropolis–Hastings algorithm. We tune the learning rate and L2 regularization using grid search.\n\n> **Whether the proposed min-min formulation could also perform well in a probabilistic EBM setting**\n\nWe indeed focus primarily on the prediction setting (i.e., finding the mode, $\\mathrm{argmax}_y ~ p(y|x)$), because our approach, while learning the model $p(y|x)$ and approximating its normalization constant, doesn’t directly address the challenge of sampling from this distribution, which would be central to evaluating performance in a generative/probabilistic setting. Sampling in structured discrete spaces can be challenging. Thank you for pointing out the work of Ou et al, that we will cite.\n\n> **Missing references**\n\nThank you, we will add these relevant citations.", "claims_and_evidence": "The paper is well written and most claims are well supported. However, there is one point I hold different opinions.\n\n*In line 295, it states: “However, min-max formulations are notoriously hard to optimize. In contrast, our approach is based on a min-min formulation, which is easier to optimize.”*\n\nThere are no experimental results in the paper to support this claim. I suspect whether the proposed min-min formulation is indeed easier to optimize than the min-max formulation, which parameterizes a variational distribution to estimate the partition function. In fact, in the continuous domain, variational methods have demonstrated scalability in modeling high-dimensional data [1].\n\nThe proposed min-min formulation requires Monte Carlo estimation of the intractable sum, as seen in Equation 13. This approach generally suffers from high variance, which can make optimization unstable. In this regard, I am curious about the scalability of the proposed method.\n\n[1] Duvenaud, David, et al. \"No MCMC for me: Amortized samplers for fast and stable training of energy-based models.\" *International Conference on Learning Representations (ICLR)*. 2021.", "methods_and_evaluation_criteria": "The proposed method is straightforward and easy to follow. However, the evaluation criteria are insufficient. In the experiments, the paper only presents the results of the proposed method, lacking a baseline comparison with other approaches, such as the variational-based min-max method.\n\nThe paper focuses solely on the non-probabilistic EBM setting, specifically computing the mode argmax_y p(y, x).  It would be beneficial to explore whether the proposed min-min formulation could also perform well in a probabilistic EBM setting, where the goal is to learn an EBM to model the data distribution rather than merely finding the mode.\n\nMoreover, [2] addresses a similar problem—learning set functions—which can be viewed as a type of mode-finding problem (i.e., argmax). [2] explores broader applications, including product recommendation, set anomaly detection, and compound selection, making it a valuable reference. Additionally, [2] proposes a method for training discrete EBMs. Although it is based on a biased objective, it serves as a competitive baseline for performing the mode-seeking task of argmax.\n\n[2] Ou, Zijing, et al. \"Learning neural set functions under the optimal subset oracle.\" *Advances in Neural Information Processing Systems* 35 (2022): 35021-35034.", "theoretical_claims": "The theoretical results appear to be correct.", "experimental_designs_or_analyses": "As mentioned before, the experimental designs is insufficient. More comparison to the baseline and including more settings, like learning probabilistic EBM s. The experiment in [2] can also be a good reference.", "relation_to_broader_scientific_literature": "None", "essential_references_not_discussed": "There are some missing references regarding the training of discrete EBMs with non-MLE approaches, which could be cited in Section 2.5.\n\n- Energy discrepancy [3] is one such non-MLE approach that has an interesting connection to MLE.\n- Ratio matching and concrete score matching are also applicable for training discrete EBMs.\n\n[3] Schröder, Tobias, et al. \"Energy-Based Modelling for Discrete and Mixed Data via Heat Equations on Structured Spaces.\" *Advances in Neural Information Processing Systems* 37 (2024): 79246-79281.\n\n[4] Hyvärinen, Aapo. \"Some extensions of score matching.\" *Computational statistics & data analysis* 51.5 (2007): 2499-2512.\n\n[3]Meng, Chenlin, et al. \"Concrete score matching: Generalized score matching for discrete data.\" *Advances in Neural Information Processing Systems* 35 (2022): 34532-34545.", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "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": "f3f5SNPzxp", "reviewer": "Reviewer_bVTG", "summary": "It is well-known that computing normalising constants of energy-based models is intractable, and a significant and important problem. The authors propose a simple and elegant technique for discrete models - instead of computing the normalising constant, consider a constrained maximum likelihood optimisation problem with the density constrained to sum to 1, and use Lagrange multipliers to enforce the constraint. Two neural networks are used to jointly learn the energy based model and the normalising constant, as the title suggests. Experiments are conducted on multiabel classification and ranking.\n\n## update after rebuttal \nAs I indicated in my original review, I found and still find the empirical results a little bit underwhelming. However, I believe the other results in this paper are interesting, and are enough to warrant publication even without very strong empirical results. I'm maintaining my current score of accept, noting that the overall average still seems to be erring on accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive review and constructive feedback.\n\n> **The approach is limited to a discrete target space**\n\nOur approach can in principle be applied to continuous output spaces $\\mathcal{Y}$. However, we believe standard regression tasks are less common applications of conditional EBMs, compared to structured prediction over discrete spaces. This motivated our focus on discrete, combinatorially-large spaces like sets and permutations.\n\n\n> **Figure 2: a single scalar number for each of the datasets would be more informative and a comparison with other techniques**\n\nIndeed, Figure 2 plots the learned vs. true log-partition for 100 individual test samples, rather than a time series. We chose this visualization to show the correlation across diverse samples. While scalar metrics like correlation coefficients could summarize this, the plot provides a better view of the approximation quality. We agree that summarizing with a scalar metric in the caption would be beneficial and will add this. A comparison with other techniques for learning the log-partition function is difficult as, to our knowledge, parameterizing and learning $\\tau$ as a parametrized function is novel to our work.\n\n\n> **Empirical comparison with other techniques**\n\nFor multilabel classification, in Table 3, logistic (unary) corresponds exactly to using sigmoids as output layers and binary cross-entropy as loss. In addition, Table 3 includes the results when using the generalized Fenchel-Young loss, which is state-of-the-art for structured prediction tasks.\n\nFor label ranking, we use full rankings as supervision, which is naturally cast as a structured prediction task. We could potentially reduce full rankings to many pairwise rankings and use pairwise ranking losses instead, but we believe such a comparison is out of the scope of our paper.\n\nHowever, we acknowledge that the paper did lack comparisons with **MCMC** and **min-max** baselines. We therefore added these comparisons to Table 1 and Table 3.\n\n**Link to updated Table 1 and Table 3:** https://anonymous.4open.science/r/ebms/tables.pdf\n\nIf the paper is accepted, these tables are going to be included in the main text, thanks to the extra page allowed by the camera-ready.\n\n**Technical details:** For the the min-max approach, we use optimistic ADAM as solver, an MLP as generator and we use REINFORCE (score function estimator) for gradient estimation. For MCMC, we use standard Metropolis–Hastings algorithm. Similarly to the min-min approach, we tune the learning rate and L2 regularization using grid search.\n\n> **The variational perspective in equation (2) is generalised on page 6. NLL loss and KL divergence gives a standard \"Bayes posterior\" (which is not actually a posterior in this context). Arbitrary loss and KL divergence gives a \"Gibbs posterior\", which is equation (1). Arbitrary loss and arbitrary divergence (or, more specifically, f divergence) gives a generalised posterior. Maybe you would like to mention this (I guess \"posterior\" can be replaced by \"measure\")? --- see Knoblauch**\n\nThis is a good remark. If $g(x, y) = \\log p(x|y)$ and $q(y) = p(y)$, then Eq. (1) indeed gives the posterior $p(y|x)$ (in the sense of Bayes’ rule).\n\n> **As far as I understand, the problem of sampling from the probabilistic EBM is not studied. Is that right? Would you expect any particular sampling algorithm to be especially well suited to this formulation of EBM, or are we no better off than generic samplers?**\n\nIndeed, we do not address the issue of sampling in this paper. We wonder whether the learned log-partition function can help design a better rejection sampling scheme. We leave this to future work.\n\n> **The constraint is on the normalising constant equal to 1. Why not constrain the log normalising constant to be equal to zero? Wouldn't this then be of the same \"scale\" as the likelihood term in the loss?**\n\nWe haven’t considered this. Our proof is based on the more general Fenchel-Young losses, where the Lagrange multiplier $\\tau$ naturally appears as a consequence of Lemma 1.", "claims_and_evidence": "Claims and evidence are supported by evidence.", "methods_and_evaluation_criteria": "Evaluation criteria are appropriate.", "theoretical_claims": "Theoretical claims appear sound.", "experimental_designs_or_analyses": "The experiments appear sound, although only two datasets are used (see below).", "relation_to_broader_scientific_literature": "It is very well placed in broader scientific literature, tackling a central problem in machine learning.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "**Strengths:**\n- The paper is very well written, provides a good amount of background which is accessible to even those who are not familiar with the area, citing appropriate canonical background texts. The notations seem sensible and easy to read. I was not able to spot typos or errors. Easily the best written paper in my pile this year.\n- The idea is relatively simple --- use the constraint of the normalising constant equal to 1 as a separate function multiplied by the Lagrange multiplier. Then just use neural nets for both the constraint and the original log loss. A simple idea seems to give good results, without convoluted hacks.\n\n**Weaknesses:**\n- The approach is limited to a discrete target space $\\mathcal{Y}$.\n- Figure 2 is perhaps misleading and I am also not sure what I should take from it. Firstly, the horizontal axis shows randomly selected x values (i.e. there is no \"metric\" between x and no \"continuity\" in y), but the plot makes it look like a timerseries or something similar. Secondly, the errors are entirely qualitative, relying on the reader to try and eyeball the difference between the dark and light plots. All I can say is \"emotions\" looks good and \"cal500\" looks relatively poor. Finally, there is no \"control\", i.e. it shows the proposed method, but doesn't compare with any baseline. I think a single scalar number for each of the datasets would be more informative, and a comparison with other techniques. \n- In the empirical comparison with other techniques, I am not seeing comparisons with other (perhaps intractable?) techniques, like standard (non-probabilistic) deep net classifiers, logistic regression, etc. Could you provide these, or discuss why they are inappropriate?", "other_comments_or_suggestions": "**Detailed comments:**\n- The variational perspective in equation (2) is generalised on page 6. NLL loss and KL divergence gives a standard \"Bayes posterior\" (which is not actually a posterior in this context). Arbitrary loss and KL divergence gives a \"Gibbs posterior\", which is equation (1). Arbitrary loss and arbitrary divergence (or, more specifically, f divergence) gives a generalised posterior. Maybe you would like to mention this (I guess \"posterior\" can be replaced by \"measure\")? --- see Knoblauch \n- As far as I understand, the problem of sampling from the probabilistic EBM is not studied. Is that right? Would you expect any particular sampling algorithm to be especially well suited to this formulation of EBM, or are we no better off than generic samplers?\n- The constraint is on the normalising constant equal to 1. Why not constrain the log normalising constant to be equal to zero? Wouldn't this then be of the same \"scale\" as the likelihood term in the loss?", "questions_for_authors": "See above.", "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": "MgBL3xRqmp", "reviewer": "Reviewer_Vp3e", "summary": "This paper proposes a min-min training paradigm for simultaneously training energy models and their log-normalization constants in a combinatorially-large space. It demonstrates that this approach can effectively approximate the Maximum Likelihood Estimation (MLE) objective and extends it to Fenchel-Young losses. Notably, the training of the objective function does not rely on traditional MCMC sampling; instead, It only needs to sample from the prior distribution and use stochastic gradient descent. Experiments are conducted on two tasks: multi-label classification and label ranking.\n\n*Strengths*\n\n- The insight that lagrange multiplier exactly coincides with the log-partition function in the MLE (logistic loss) case is good. Based on this insight, the proposed min-min formulation for MLE of EBMs seems to be new.\n\n- The proposed min-min training method is supported via theoretical development.\n\n- Experiments investigate variations in model architecture, regularization functions, and the number of sampled points, and show the effectiveness of the proposed method.\n\n*Weaknesses*\n\n- In addition to learning EBM model parameters, learning partition functions simultaneously is interesting. But the experiments conducted in this paper do not show the benefit of such joint learning.\n\n- Missing relevant references and comparisons\n\nLearning probabilistic EBMs in combinatorially-large discrete spaces have been studied with substantial progress in recent years, particularly in language modeling [a-d]. The discrete space in language modeling is V^k, where V is the vocabulary size and k is the sentence length. \nA variety of methods have been proposed for learning discrete EBMs, including augmented stochastic approximation (AugSA) [b], noise contrastive estimation (NCE) [c].\nParticularly, the AugSA method has been developed to be able to jointly estimate the model parameters and partition functions (up to a constant). The idea of formulating equations with partition functions and then estimating them in this work is very similar to AugSA.\n\nConnecting and comparing to these previous studies are needed.\n\n- Limitation in experiment evaluation\n\nThe experiment comparisons are only conducted between different versions of the proposed method, by varying settings such as unary vs pairwise, different network architectures, and different losses.\n\nPresenting at least one experiment comparing the proposed method and one of the SOTA methods for learning discrete EBMs is necessary; otherwise, the effectiveness of the proposed method is not convincing.\n\nRegarding the results for multilabel classification, only learning curves in Figure 1 and the learned log-partition functions in Figure 2 are shown in the main text. Not clear why the numerical metrics are not reported in the main text, which should be major results.\n\n[a] Energy-Based Models with Applications to Speech and Language Processing. Foundations and Trends® in Signal Processing, 2024.\n\n[b] Learning Trans-dimensional Random Fields with Applications to Language Modeling. TPAMI, 2018.\n\n[c] Learning neural trans-dimensional random field language models with noise-contrastive estimation. ICASSP, 2018.\n\n[d] Residual Energy-Based Models for Text Generation. ICLR 2020.\n\n*Questions*\n\n- The right hand sides of Eq 2 and 5 are the same, which is confusing.\n\n- Line 243: \"We have therefore obtained convergence rates for learning EBMs in arbitrary combinatorial spaces.\" Not clear.\n\n- In section 3.3, where does the min-max formulation come from?\n\n- Figure 3: what are plots (a) and (b)?", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and relevant references.\n\n> **Presenting at least one experiment comparing the proposed method and one of the SOTA methods for learning discrete EBMs is necessary**\n\nThe original Table 3 contained generalized Fenchel-Young (GFY) losses comparisons, and Figures 1 and 3 contained comparison to logistic regression, which serves as a relevant baseline for structured prediction tasks learned without explicit partition function estimation. Following reviewers feedback, we have now added comparisons with **MCMC** and **adversarial (min-max)** training baselines.  \n\n**Link to updated Table 1 and Table 3:** https://anonymous.4open.science/r/ebms/tables.pdf\n\nIf the paper is accepted, we are going to include these tables in the main text, thanks to the extra page allowed by the camera-ready.\n\nFor convenience, we also show the new results below:\n\nTable 1(label ranking)\n\n\n|Loss|Polytope C|Model $g$|authorship|glass|iris|vehicle|vowel|wine|\n|---|---|---|---|---|---|---|---|---|\n|Logistic (MCMC)|P|Linear|84.29|80.67|55.56|79.15|49.97|91.36|\n||P|MLP|87.90|75.50|97.04|86.34|57.90|91.98|\n||B|Linear|88.10|79.33|97.78|82.22|55.99|**96.91**|\n||B|MLP|89.68|80.16|97.78|85.88|48.90|91.98|\n|Logistic (min-max)|P|Linear|61.01|79.22|61.48|70.20|45.68|65.43|\n||P|MLP|70.02|67.03|55.56|68.56|40.22|70.99|\n||B|Linear|82.58|78.40|61.48|74.90|52.86|93.21|\n||B|MLP|78.50|71.68|42.96|68.76|48.99|83.33|\n\nTable 3 (multilabel)\n\n|Loss|Model$g$|yeast|scene|birds|emotions|cal500|\n|---|---|---|---|---|---|---|\n|Logistic (exactMLE)|Linear (unary)|61.46|70.64|43.97|63.35|37.31|\n||MLP (unary)|60.71|70.81|40.88|62.99|36.24|\n||Resnet (unary)|62.27|71.02|40.78|61.50|37.45|\n|Logistic (MCMC)|Linear(unary)|61.98|70.53|44.93|61.76|44.61|\n||MLP (unary)|60.34|71.57|33.13|62.23|45.70|\n||Resnet (unary)|56.57|71.24|27.03|58.98|44.34|\n||Linear (pairwise)|61.96|70.50|44.93|61.76|44.61|\n||MLP (pairwise)|60.83|71.92|34.61|63.15|45.95|\n||Resnet (pairwise)|56.68|70.46|27.08|64.05|44.35|\n|Logistic (min-max)|Linear (unary)|52.80|52.29|27.59|61.72|35.08|\n||MLP (unary)|58.58|52.54|24.95|60.53|46.08|\n||Resnet (unary)|57.53|42.82|25.32|55.85|47.59|\n||Linear (pairwise)|52.80|52.29|27.59|61.72|35.08|\n||MLP (pairwise)|58.76|51.59|26.71|58.68|43.31|\n||Resnet (pairwise)|57.53|42.95|22.35|46.72|**47.67**|\n\n**Technical details:** For the the min-max approach, we use optimistic ADAM as solver, an MLP as generator and we use REINFORCE (score function estimator) for gradient estimation. For MCMC, we use standard Metropolis–Hastings algorithm. Similarly to the min-min approach, we tune the learning rate and L2 regularization using grid search.\n\n> **References [a-d]**\n\nThank you for these references. We will add them.\n\n> **Differences with AugSA [b]**\n\nThank you for this very relevant reference. We will cite it and clarify the distinctions. First, this paper studies linear conditional random fields for whole-sentence LMs while we study more general energy-based models. In addition, our method supports the broader class of Fenchel-Young losses (including sparsemax), not just MLE. They indeed propose the idea to optimize the normalization constant but in their case it’s a constant, while in our case it’s a function, parameterized as a neural network  that approximates the input-dependent log-partition function. Last, we empirically demonstrate (Figure 2) that our learned $\\tau$ generalizes to unseen inputs $x$. \n\n> **Not clear why the numerical metrics are not reported in the main text, which should be major results.**\n\nThis was due to space constraints in the initial submission. If our paper is accepted, we plan to use the extra page allowed for the camera-ready version to move the expanded Table 3 (which now includes MCMC and a min-max approach) into the main text.\n\n> **The right hand sides of Eq 2 and 5 are the same, which is confusing.**\n\nPlease note that Eq. (2) is using an argmax while Eq. (5) is using a max.\n\n> **Line 243: \"We have therefore obtained convergence rates for learning EBMs in arbitrary combinatorial spaces.\" Not clear.**\n\nOur claim refers to the fact that our proposed objective can be optimized using standard stochastic gradient methods, with the convergence rate discussed after Proposition 2. This is achieved without requiring an oracle for the exact partition function (needed for traditional MLE gradient computation) or k-best solutions (needed for traditional sparsemax loss optimization), which are often intractable in arbitrary combinatorial spaces. We will clarify this context in the paper.\n\n\n> **In section 3.3, where does the min-max formulation come from?**\n\nWe derived the min-max formulation presented in Proposition 3 and Appendix C.4 ourselves. It serves as a comparison point to our proposed min-min formulation and draws parallels to adversarial learning approaches.\n\n\n> **Figure 3: what are plots (a) and (b)?**\n\nThank you for catching that typo.  We were referring to the left and center columns of the Figure.", "claims_and_evidence": "see above", "methods_and_evaluation_criteria": "see above", "theoretical_claims": "see above", "experimental_designs_or_analyses": "see above", "relation_to_broader_scientific_literature": "see above", "essential_references_not_discussed": "see above", "other_strengths_and_weaknesses": "see above", "other_comments_or_suggestions": "see above", "questions_for_authors": "see above", "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:

Meta-review: This paper proposes a method for learning discrete energy-based models by formulating MLE as a constrained optimization problem, jointly learning the energy function and its partition function using Lagrange multipliers. The approach avoids costly MCMC sampling and shows strong performance on multi-label classification and label ranking tasks.

The method is surely an interesting contribution. The main concern of the reviewers, which was raised again in the reviewers' discussion, is the experimental evaluation, both in terms of setup and results.
Decision: Accept (poster)