Imbalances in Neurosymbolic Learning: Characterization and Mitigating Strategies
Authors: Efthymia Tsamoura
Kaifu Wang
Dan Roth
Venue: NeurIPS 2025 poster ()
Keywords: neurosymbolic learning
learning theory
learning imbalances
Primary area: general_machine_learning

Abstract: We study one of the most popular problems in **neurosymbolic learning** (NSL), that of learning neural classifiers given only the result of applying a symbolic component $\sigma$ to the gold labels of the elements of a vector $\mathbf x$. The gold labels of the elements in $\mathbf x$ are unknown to the learner. We make multiple contributions, theoretical and practical, to address a problem that has not been studied so far in this context, that of characterizing and mitigating *learning imbalances*, i.e., major differences in the errors that occur when classifying instances of different classes (aka **class-specific risks**). Our theoretical reveals a unique phenomenon: that $\sigma$ can greatly impact learning imbalances. This result sharply contrasts with previous research on supervised and weakly supervised learning, which only studies learning imbalances under data imbalances. On the practical side, we introduce a technique for estimating the marginal of the hidden gold labels using weakly supervised data. Then, we introduce algorithms that mitigate imbalances at training and testing time by treating the marginal of the hidden labels as a constraint. We demonstrate the effectiveness of our techniques using strong baselines from NSL and long-tailed learning, suggesting performance improvements of up to 14\%.

Imbalances in Neurosymbolic Learning: Characterization and Mitigating Strategies
Efthymia Tsamourat
Kaifu Wangi
Huawei Labs
University of Pennsylvania kaifu@sas. upenn. edu
of thymiia wew.uaaaaaaaaaaac.coooom
Dan Roth
University of Pennsylvania
danroth@seas upenn. edu
Abstract
We study one of the most popular problems in neurosymbolic learning (NSL), that of learning neural classifiers given only the result of applying a symbolic component a to the gold labels of the elements of a vector x. The gold labels the elements in are unknown the learner. We make multiple contributions, theoretical and practical, to address a problem that has not been studied so far this context, that of characterizing and mitigating learning imbalances, i.e., major differences in the errors that occur when classifying instances of different classes (aka class-specific risks). Our theoretical reveals a unique phenomenon: that can greatly impact learning imbalances. This result sharply contrasts with previous research on supervised and weakly supervised learning, which only studies learning imbalances under data imbalances. On the practical side, we introduce a technique for estimating the marginal of the hidden gold labels using weakly supervised data. Then, we introduce algorithms that mitigate imbalances at training and testing time by treating the marginal of the hidden labels as a constraint. We demonstrate the effectiveness of our techniques using strong baselines from NSL and long- ttiied learning, suggesting performance improvements of up to 14%.
Introduction
The need to address the limitations of deep learning motivated researchers explore neurosymbolic learning (NSL) [13], a family of techniques that integrate neural mechanisms for inference and learning with symbolic ones. This work considers one of the most popular NSL learning settings [12, 61, 20, 28, 40, 39, 37] in which a neural classifier f is learned assuming access only to a vector and to the result of applying a the gold labels of the 2,S. The gold labels are hidden during learning. An example is illustrated below:
of inputs x (I1,.... F.M)
Example 1.1 (Example adapted from [36]). We aim to learn an MNIST classifier f. using only 32, 8), where In and 22 MNIST digits and is the maximum of their samples of the form (2,,
gold labels, i.e. a (v,, 32) = max (11, y2) with yi being the label of I;. The gold labels are hidden during training. We will refer to the y: 's and hidden and weak labels, respectively.
Our learning setting, which we will refer to as NESY, has been extensively adopted in NLP [58, 49, 47, 68, 16]. Recently, NESY has been successfully adopted fine-tunt tune language models [73, 29], align
* Work started before Efthymia Tsamoura joined Huawei Labs.
"These authors contributed equally to this work.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

video to text [21], perform visual question answering [20], and learn knowledge graph embeddings
[34, 35]. The wide range of applications of NESY motivated its extensive study [67, 39, 40, 28].
We, for the first time, study an unexplored topic in the context of NESY: the characterization and mitigation of learning imbalances, i.c., the major differences in errors occurring when classifying instances of different classes (aka class-specific risks). Existing work on supervised [42, 6] and weakly supervised learning [65, 18] studies im- balances under the prism of long- tail-t (aka imbalanced) data: data in which instances of different classes occur with very different frequencies, [17, 19, 4]. However, these results cannot fully characterize learning imbalances in NESY. This is because the symbolic component may cause learning imbalances even when the hidden or the weak labels are uniformly distributed. Figure I demon- strates this phenomenon by showing the accuracy of the classification per class at different training epochs when an MNIST classifier is trained as in Example 1.1 and the hidden labels are uniform. Hence, to formalize the imbalances in NESY, need to account for the symbolic component σ.
100
Per-class accuracy
40
2
3
7
8
9
MNIST classes
Figure 1: Class-specific accuracies of classifier f (Example 1.1). Blue, red, and green curves show accuracy at 20, 40 and 100 epochs. Learning converges in 100 epochs.
On the practical side, mitigating learning imbalances (a problem typically referred to as long- tailed learning) has received considerable attention in supervised and weakly supervised learning with the proposed techniques operating at training [6, 60, 59, 9, 4] or at testing time [25, 46, 42]. However, these previous algorithms are not appropriate for NESY. First, they rely on (good) approximations of the marginal distribution of the hidden labels. Although approximating may be easy in supervised learning [42] since the gold labels are available, in our setting the gold labels are hidden. Second, the state-of-the-an art for training time mitigation [65, 6, 60, 59, 9, 4, 18] is designed for settings in which a single instance is presented each time to the learner and hence, they cannot take into account the correlations among the instances.
Contributions. We first provide class-specific error bounds in the context of NESY. Complementary to previous work in supervised learning [6] and weakly supervised one [10], our theory shows that can significantly affect learning imbalances, see Theorem 3.1. Our analysis extends the theoretical analysis in [67] by providing stricter error bounds and making fewer assumptions and the theoretical analysis in [10].
We then propose a statistically consistent technique for estimating the marginals of the hidden labels given weak labels and two algorithms to mitigate imbalances during training and testing time. The first algorithm assigns pseudolabels to training data based on a novel linear programming formulation of NESY, see Section 4.2. The second algorithm uses the marginals of the hidden labels to constrain the model's predictions on test data using robust constrinnt optimal transport [26], see Section 4.3. Our empirical analysis shows that our techniques can improve the accuracy over strong baselines in NSL. [71, 67] and long-tailed learning [42, 18] by up to 14% and that the straightforward application of previous tate-offthheaat to NESY is impossible [65] or problematic [18].
Proofs, additional backgrounds and details on our empirical analysis are in the appendix. The source code to run our empirical analysis are available at https:// htte::///tttbbb/t grtb....c.. com/ htt///saouura//// imbalances-nsil
2
Preliminaries
Our notation is summarized in Table 5 and 6 and builds on [67, 28, 61].
Data and models. For an integer > 1, let [m] := (1.... .......,,] n). Let also X' be the instance space and y= [c] be the output space. We use z, y to denote elements in X' and V. The distribution of two random variables X, Y over X' x y is denoted by D. and Dx, Dy denote the marginals of X and Y. The vector r = (ri,...,re, ,Y)) denotes Dy, where r := P(Y j) is the probability (or ratio) label j E )' occurs in D. We consider scoring functions f that given instances from X' output softmax probabilities (or scores). We use (x) to denote the score of ʃ for class j E y. A scoring function f
induces classifier [f] X + y, whose prediction z is given by argmax,ele, f (z). We denote

---

by F the set of scoring functions and by [F] the set of classifiers. The zero-one risk R(f) of f is the probability misclassifies an imput instance. The class- Spess-e of f for class j is the probability f misclassifies an instance of that class, i.e., RJ( == (a) # j|y j).
Neurosymbolic learning. We align with the notation from [12, 61, 28] and assume that each NESY training sample is of the form (x, s), where x = (II,..., .MM is a vector of instances in X.M and s E S is the result of applying the symbolic component a over the hidden gold labels y = (yl,... ..M) of the elements of x. We assume that o is known to the learner, similarly to [20, 28, 40, 39]. As first notated in [61], using abduction [24], the symbolic component a can be seen as a function from )dM to S. We refer to S = {aI..... Ges J. where |S] = cs 2 1, as the space of weak labels and to an element from S as weak label. We denote the set of all label vectors that map to s under o by o (s). Each vector in σ (s) may be the gold vector of labels. Return- ing to Example 1.1, - = 1) = =(00, 1), (1, 0), (1,1)) We refer to each vector o (s) as a pre-image. The distribution of samples (x, 8) is denoted by Dp. We denote a set of mp NESY sam- ples by Tp. We set [f](x) = (I1) (((=1))..... [f((==)))
The zero-one partial loss defined as Lo (y,s) L(a(y). s) (( + s}. for any y E y.M and s E S. We aim to find the classifier with the minimum zero-one partial risk given by Rf(f:o) == (x............). X....-. (Lo ((L]](X)) S)].
Relevant NSL work [37, 20, 40] may denote training samples differently. However, this notation is equivalent with ours, see Appendix A. Furthermore, our definition of NESY aligns with that of multi- instance partial label learning (MI-PLL) without assuming that the X' instances in Dp are i.i.d. As discussed in [67]. partial label learning (PLL) [10, 5, 70]. where each training instance associated with set of mutually exclusive candidate labels, is a special case of NESY, see Appendix E.
Vectors and matrices. A vector is diagonal if all of its elements equal. We denote by e; the one-hot vector, where the i-th element equals 1. We denote the all-one and the all-zero vectors by 1, and O.. and the identity matrix of size n n by I,. Let A E Raxm be a matrix. We use Ai, to denote the value of the (i.j) cell of A and oq to denote the i-th element of v. The vectorization of A inverse by A
is given by vec(A) := [a1.1..... an,1,.... Q1.m: an.m] I and its Moore-Penree If A is square, then the diagonal matrix that shares the same diagonal with A is denoted by D( (A). For matrices A and B, A 8 B and (A,B) denote their Kronecker and Frobenius inner products.
3 Theory: Characterizing Learning Imbalances In NESY
We provide error bounds that measure the difficulty of learning instances of each class in y using NESY data. The bounds indicate that, unlike supervised learning. learning imbalances in NESY arise not only from imbalances in the hidden or weak label distributions, but also from the symbolic component a. Our analysis is based on the assumption that the X' instances in Dp are i.i.d. To simplify the presentation, our analysis focuses on M 2 However, it can be generalized to M > 2.
Our theory is based on a novel nonlinear program formulation that allows us to compute an upper bound of each (f). The first key idea (K1) to that formulation is a rewriting of Rp (ffor) and (f). To start with, given the function o, the zero-one partial risk can be expressed the weak label is misclassified
probability of the label pair (i.j)
Rp(f:o) = Σ riny
Σ
1|a + of'' H. Hf)
(1)
()
conditional probability that the labels i and are (mis)classified as i' and j
where H()) is an e x matrix defined as H() = [T([[(()) = j|Y = =)leete.sedd- To derive (1), we enumerate all the 4-ary vectors "". E yd, where i are the gold hidden labels and i', are the predicted labels, so that the predicted labels lead to wrong weak label, i.c. j) o aii,, ("), The risk (f:: a) is the sum of the probabilities of those wrong predictions, with Ha Hf) (f) encoding the probability of occurrence of the vectors ji. J'). Now, let hnf) be the vectorization of Hf)) The partial risk R)(f;o) in (1) is quadratic form of h(f). Therefore, there is a unique symmetric matrix Σx.r in Rxxx that depends only on and such that (1) can be rewritten Rf(f;o) h(f) (f,) Furthermore, for each j y, let W, be the matrix defined by (1, e,)ee and wj be its vectorization. We can rewrite the class-specific risk R₂(S) = w/ w[[(
The second key idea (K2) to form nonlinear program that computes class-specific risk bounds is to upper bound the class-specift risk Ry(f) (f) of model f with the model's partial risk Rp(f:
3

---

The latter can be minimized with NESY training data Tp. Putting (K1) and (K2) together, the worst class-specific risk of for class y given by the optimal solution to the program below:
w) h(f))
max h
s.t.
h(f)
Rp(f:o)
(partial risk)
h(/)= 2 20
(positivity)
(Le @ (J() = 1c
(normalization)
Let analyze (2). The optimization objective states that our aim is to find the worst possible class-specific risk, expressed as (J) = w.]h(f). The first constraint specifies the partial risk of the model. The second one requires the (mis)classification probabilities to be nonnegative. The last constraint, where (Ic @ ! (f()) represents the row sums of matrix H Hf)), enforces the classification probabilities to sum one. Let Do (Rp(f:o) denote the optimal solution of program
(2). We have: Proposition 3.1 (Class-specific risk bound). For any j y, we have that R2 (J) S & (Rp(:: o)).
Characterizing learning imbalances. Proposition 3.1 suggests that the worst risk associated with each class in y is characterized by two factors: (i) the model's partial risk Rp(ʃ; which is independent of the specific class and (ii) since a affects the mapping Pa.i from the model's partial risk the class- specific risk. Therefore, the learning imbalance can be assessed by comparing the growth rates of Do We use this approach to analyze Example 1.1.
Example 3.2 (Cont' Example 1.1). Let D and Dp be defined as in Section Consider the two cases:
CASE
The marginal of the hidden label Y uniform. The left-hand side of Figure 2 shows the risk bounds for different classes obtained by solving the program (2). The bounds are presented as functions of the different values of Rp (f; o)). In this plot, the curve for class "zero" " (resp. "nine") has the steepest (resp. smoothest) slope, suggesting that f will tend to make more (resp. fewer) mistakes when classifying instances of that class. In other words, class "zero" " is the hardest to learn, as also shown to be the case in reality, see Figure 1.
CASE 2
The marginal of the weak label S is uniform. Similarly, the right-hand side of Figure 2 plots the corresponding risk bounds, suggesting that the class "zero" now the easiest to learn.
Computable bounds. Via Proposition 3.1, we can de-
1.0
1.0
Classification Risk
rive a bound for (f) that
0.8
0.8
can be computed using a
Classiiicttoon
0.6
NESY dataset. This can be done by using standard learning theory tools (e.g., the VC-dimension or the Rademacher complexity) to show that, given fixed con- fidence level 8 E (0, 1), the partial risk of) will not exceed a generalization hound Rp(f;o, a, o, 6) with probability - 6:
0.4
0.2
0.2
0.0
0.0
0.00
0.05
0.10
0.15
0.20
0.00
0.05
0.10
0.15
0.20
Partial Risk
Partial Risk
Figure 2: Class-specific upper bounds obtained via (2). (left) Dy is uniform. (right) Dps is uniform.
Proposition 3.3. Let diip be the Natarajan dimension of [F]. Given a confidence level 8 E (0, 1), we have that Rf) < (Rp Tp, 5)) with probability 1 - 8 for any j E [c], where
2 logg(emp/2d log( /o)) +
log(1/8)
Rp(f:o, T) = Rp(f:o, Tp) +
(3)
mp mp/2d log(
2mp
The first term the right-hand side of (3) denotes the empirical partial risk of classifier f. the second term upper bounds the Natarajan dimension of ff [55], and the third term quantifies the confidence level or the probability that the generalization bound holds, which is typical in learning theory. The Proposition 3.3 shows the speed decrease of the risk of f for class j E y when using NESY samples for training. Further on bounds and Example 3.2 are in Appendix B.2.
Comparison to previous work. Our result extends [67] (see Section for a discussion about MI-PLI and NESY) in three ways: (i) we bound the risks (f) instead of bounding the total risk R(f); (ii

---

our bounds do not rely on M -unambigguit.. in contrast to those in [67]; and (iii) the program (2) leads to tighter bounds for R(f). Before proving (iii). let us first recapitulate M --nnmbiiguity [67], where a function is M -unanmiiguous if for any two diagonal label vectors y and y' E yaul such that y * y', we have that or (y') * (y)). Now, let us move to point (iii). By relaxing the constraints in (2), we can recover Lemma 1 from [67] (which is the key to proving Theorem 1 from [67]). In particular, if we: (i) drop the positivity and normalization constraints from (2) and (ii) replace the partial risk constraint by the more relaxed inequality h(f) D(Eo,) ()ff) I Rp(f:o), o), we obtain the following:
Proposition 3.4. o is M M-unambiguous, we have
B() S /
(R)(foo))) = (CCC-1)R((Ji1)
which coincides with Lemma 1 from [67] for M 2, where w == Ej=1
4 Algorithms: Mitigating Imbalances In NESY
Section sends a clear message: NESY is prone to learning imbalances that may be exacerbated due to a. The results of our theoretical analysis motivate to develop a portfolio of techniques to address learning imbalances. Our first contribution, see Section 4.1, is a statistically consistent technique for estimating r, assuming access to weak labels only. We then proceed with training and testing time mitigation. Our mitigation algorithms enforce the class priors to a classifier's 's predictions, a common idea in long-tailed learning. The intuition is that the classifier will tend to predict the labels that appear more often in the training data. Hence, enforcing the priors gives more importance to the minority classes at training time and encourages the model to predict minority classes at testing time. Our marginal estimation algorithm requires the assumption that the X' instances in Dp are i.i.d.; the other algorithms work even when this assumption fails. Table 6 summarizes the notation in Section 4.
4.1 Estimating The Marginal Of The Hidden Labels
We begin with our technique for estimating r using only NESY data Tp. We denote the probability of occurrence (or ratio) of the j-th weak label aj S by Pj == P(S aj) and set p = (P1:---. Pes )- To estimate r, we rely on the observation that in NESY, Py equals the probability of the label vectors in o o- (aj). namely Pj E(m (ag) II Tu., which is polynomial of
Example 4.1. Consider CASE (2) from Example 3.2. Assume that the marginals of the weak labels are uniform. Then, we can obtain by solving the following system of polynomial equations: (rō. + 2rofi..... + Ei=orr)) T [1/10, 1/10, ......... 1/10]T. The first equation denotes the probability a weak label is zero, which is 1/10 (uniformity). Due to a, this can happen only when 31 1/2 = 0. Under the independence assumption. the above implies that ră = 1/10. Analogously, the second and the last polynomials denote the probability a weak label is one and nine.
Let Pa be the system of polynomials [pi]eetc)) ('(y.....pee (yn....pprr) 1(a,) Maj)lEtoaa Let V, be the func- tion mapping each ry 3 to its solution in Pa. assuming p is known. In practice, p is unknown, but
Tel 1( = a,) //TTpl As the py's can can be estimated from a NESY dataset Tp, namely p3 == Ei be noisy, the system of polynomials could become inconsistent. Therefore, instead of solving the polynomial equation as in Example 4, we find an estimate F, so that its induced prediction for the weak label ratio p- : V, (T) best fits to the empirical probabilities py 's by means of cross-entropy. Since this requires optimizing over the probability simplex A., we reparametrize the estimated ratios T by softmax (u), leading to the Algorithm 1. We prove its consistency in Appendix C.
4.2 Training Time Imbalance Mitigation Via Linear Programming
We now turn to training time mitigation. We aim to find pseudolabels Q that are close to the classifier's 's scores and adhere to f and use Q to train the classifier using the gross-entropy loss. There are two design choices: (i) whether to find pseudolabels at the individual instance level or at the batch level; (ii) whether to be strict in enforcing the marginal In addition, we face two challenges: (iii) we are provided M-ary tuples of instances of the form (æ1,..., .Ar):: ); (iv) Q must additionally abide by the constraints coming from a and the weak labels, e.g., when s = Example 1.1, then the only valid label assignments for (I1, 22) are (1,1), (0,1) and (1,0). Regarding (i), finding pseudolabels at
5

---

Algorithm LABEL. RATIO SOLVER
Algorithm 2 CAROT
Input: weak labels {sk k=1 function o,
Input: model's raw scores P Rex" ratio estimates F E R,, entropic reg. parameter > 0, margin reg. parameter
step size t, iterations Niter
Initialize: logit
1 Pj. for j E [cs]
0, iterations Niser
for N = = 1,..., Nier do
Initialize: + O,, V v O.
F softmax(1)
for N = 11. 11....... Natr do a <- Bu, v) b + 1)
for each j E [cs] do
Pj
Σ
I Pu:
if is even then update v //see Section 4.3
(9) - V.r (az)
+ E j=1 pylog
else
update u //see Section 4.3 return B(u, v)
Backpropagate to update u return softmax(u)
the individual instance level does guarantee that the modified scores match F [46]. Regarding (ii), strictly enforcing F could be problematic as F can be noisy.
To accommodate the above requirements while avoiding the crux of solving nonlinear programs, rely on a novel linear programming (LP) formulation NESY that finds pseudolabels for batch of scores. We use (Z.,,1,... J Sz) to denote the f-th NESY training sample in batch of size We also use P, E [0, 1|mxe and Q E [0. 1|mxs, for E [M]] to denote the classifier's ' scores and the pseudolabels assigned to the i-th input instances of the batch. In particular, P.
fz(,))), while Qi(e, j] is the corresponding pseudolabel. Before continuing, it is crucial to explain how to associate each training sample se with a Boolean formula in disjunctive normal form (DNF). Associating weak labels with DNF formulas is standard in the neurosymbolic literature [71, 61, 20, 67]. For E [n]. i [M], and j [c]. let qe,ij be Boolean variable that is true if ø2,4 is assigned label E and false otherwise. Let Rş be the size of o (sc). Based on the above, we can associate each label vector y in o (sz) with a conjunction Φτ,+ of Boolean variables from {9e,., je(()) such that qe,i, occurs in Φe,s only if the i-th label in y is j E V. We assume canonical ordering over the variables occurring in each Sr,t, for E [Ry], and use PP,,, to refer to the k-th variable. We use |scc,e to denote the number of variables in yPe.t-
Based on the above, finding a pseudolabel assignment for (Ze,,,-.., TEM that adheres to a and 8e reduces to finding an assignment to the variables in {qe,a (E( that makes 4 hold. Previous work [50, 57] has shown that we can cast satisfiability problems to linear programming problems. Therefore, instead of finding Boolean assignment to each qt.i.j. we can find an assignment in [0, 1] for the real counterpart of qe,á, denoted by [.]. Via associating the [qe..,l'ss to the entries in the Q 's. i.e. Qi(e,5] [q...,l. we can solve the following linear program to perform pseudolabeling:
M
objective
min QQ..... Qm)
(P.)..). Q+).
Rd [ove,e]
2 1,
E [M]
- -1pr.el
+
Σ
[
2 0,
E [m], E [Ra]
(5)
s.t.
- -D
el
+ [axe,]]
2 (1
EE [n], E [Rg]
[qc,a.j
1,
LE [n], E [M]
E [0, 1].
E [m]. E [M].j E [c]
Q
1n
nr
S S.
ie [M]
The objective in (5) aligns with our aim to find pscudolabels close to the classifier's 's scores. The independence among the classifier's scores for different x 's justifies the sum over different i's in the minimization objective. The first three constraints force the pseudolabels for the é-th training sample to adhere to a and st, where the ai,, 's are Boolean variables introduced due converting the 4y's 's into conjunctive normal form using the Tseytin transformation [62]. The fourth and the fifth constraint wants the pseudolabels for each instance Ty.s to sum up to one and lie in [0, 1]. Finally, the last constraint wants for each i E [M]. the probability of predicting the j-th pseudolabel for an element { to match the ratio estimates hand Pj up to some e 2 0: the smaller gets, the stricter the adherence to f becomes. The detailed derivation of (5) and an example are in Appendix D.

---

In summary, in training time mitigation, for each epoch, we split the training samples into batches. Then, for each batch [ZE.I..... ( Mr, 8t) Relnj- we form PI...., M by applying f to the zz,i and solve (5) to get the pseudolabels Qi,..., Qv- Finally, we minimize the cross-entropy loss between Q...... Qu and PI. ....... Pas We name this training technique I.P. Our formulation in (5)
is oblivious to F, which can be estimated using Algorithm 1 or any other technique, e.g., [65].
4.3 CAROT: Testing Time Imbalance Mitigation
We conclude with CAROT, our algorithm to mitigate learning imbalances at testing time by modifying the model's scores to adhere to the estimated ratios F. Incorporating f' into the model's scores involves the design choices (i) and (ii) presented at the beginning of Section 4.2- challenges (iii) and (iv) are specific to training. Regarding (i), most existing testing time mitigation algorithms (e.g.. [42]) modify a model's scores at the level of individual instances. Regarding (ii), as explained in Section 4.2, strictly enforcing f may also be problematic, since F may be different from the label marginals underlying the test data. Similarly to Section 4.2, we propose to adjust the model's scores for whole batch of n > test samples (represented by a matrix P E Rax9) so that the adjusted scores P' roughly adhere to F. Precisely, we propose to find the P' that optimizes the following objective:
min p P1.-L,, (=log(P), P") + 1L("",, ll nf)
(P')
(6)
The first term (6) encourages P' be close to the original scores. The second term encourages the column sums of P' to match r, with r > O controlling adherence, where KL is the Kullback-eeibe divergence. This formulation leads to a robust semi-constrained optimal transport (RSOT) problem [26]. The regularizer (P'), where H denotes entropy, allows to approximate the optimal solution using the robust semi-Sinkhorn algorithm [26], leading to CAROT Soonfidence-Aijusmnee via Robust semi-constrained Optimal Transport), see Algorithm 2.
In Algorithm 2, Bu,, v) denotes an n X e matrix whose (i,J) cell is computed as function of and v by exp(1; uy + "yy + (Pa))/)) In each iteration, the algorithm alternates between updating the c-dimensional vector v and the n--imensional vector u. The former update, which is computed 7+ 17 + log(nf) log(b)): forces Buu, v) to adhere to T; the latter, which is computed
as V nT
as u 7 log((,,) (l.) - log(a)) ) forces the elements in each row of B(u, v) to add up to one.
Choice of 7 and r. In practice, we use a small NESY validation set to choose 7) and T. By doing so, the validation set can be obtained by splitting the training set of NESY data Tp. Guarantees. The matrix B(u, v) converges to the optimal solution to (6) as Nuer + co, see [26].
5 Experiments
We consider the thht-of-thh-art loss semantic loss (SL) [71, 67, 20] and use the engine Scallop [20] that performs NESY training using that loss. We do not consider [12, 28, 61, 37, 38, 72] for reasons related to scalability (see [67, 20D, while the work in [40, 39] is orthogonal to ours. Since there are no prior NESY techniques for mitigating imbalances at testing time, we consider Logit Adjustment (LA) [42] as a competitor to CAROT The notation +A, for A E CAROC,, J. means that the scores of baseline model are modified at testing time via We do not assume access to a validation set of gold labelled data, applying LA and CAROT using the estimate f obtained via Algorithm 1. We also run experiments with RECORDS [18], a technique that mitigates imbalances at training time for [10] (no previous NESY training time baseline exists). We use SI. RL.RECODD DS when a classifier has been trained using RECORDS in conjunction with SL. RECORDS acts as a competitor to LP. Finally, we run experiments using LP, see Section 4.2. We use LP(ALGI) and LP(EMP), when LP is applied using the ratios obtained using Algorithm I and the approximation from [65].
Benchmarks. We carry experiments using NESY benchmarks previously used in the NSL literature [36, 38, 20, 28], namely MAX-M, SUM-M [36, 20] and HWF-M [28, 30], as well as a newly introduced, called Smallest Parent. Training samples in MAX-M are as described in Example 1.1. We vary M to (3, 4, 5) and use the MNIST benchmark to obtain training and testing instances. In Smallest Parent, training samples are of the form (x1, x2,P), p). where 21 and x2 are CIFAR-10 images and p is the most immediate common ancestor of y1 and y/2 assuming the classes form hierarchy. To simulate long-tail phenomena (denoted as LT), we vary the imbalance ratio p of the distributions
7

---

MAX-5, p-15
MAX 3, p=15
SMALLEST PARENT, 0-
Class Cles-speciffe ratios
Class-spo cess-speciftt ratlos
0.03
Absolute difference
Class-ppeiic retios
Nosolute affrrence
0,0100
0.2
0.2
0.0015
0.0075
0.02
0.0010
0.0050
Ansolute
0.1
0.02
0.1
0.0005
0.0025
0.00
5
0
1
3 4
5
6
9
6 8
Cless index
Class
Figure 4: Accuracy of the marginal estimates computed by Algorithm 1. Blue denotes the gold ratios, red the estimated ones, and green the absolute difference between the gold and estimated ratios.
of the input instances as in [6, 65]: p = O means that the hidden label distribution is unmodified and balanced. Our scenarios are quite challenging. First, the pre-image of may be particularly large, making the supervision rather weak, e.g., in the MAX-5 scenario, there are 5 x 9 candidate label vectors when the weak label is 9. Second, the functions may exacerbate the imbalances in the hidden labels, with the probability of certain weak labels getting very close to zero. For example, in MAX-5, the probability of 0 is 10 5 when - This probability becomes even smaller when p = 50. The results of our analysis are summarized in Table and Figure 4. The accuracies in all the tables (obtained over three different for low-variance scenarios and ten runs over high-variance scenarios) are balanced, i.e., they are the weighted sums of the class-specific accuracies, where each weight is the ratio of the corresponding class in the test data. Due lack of space, we discuss the results on SUM-M, HWF-M, and further details in Appendix F.
Table 1: (Top) Results for MAX-M & mp 3K. (Bottom) Results for Smallest Parent & mp 10K.
Algorithms
Original
L
LT 50
SL
84.15 11.92
73.22 2
55.48
66:24
55.13
66,74 5.42
6.58
2,58
11.95
2
55,48
05.63
5,09
-CAROT
56.53
68.25
57.00
RECORDS
85.56 7.25
70.20
N7.63 5:11
75.11
77.98
05.43
70.09 1.26
69.78
CAROT
90.97
2.03
71.46
LPPEMP)
94.07
77.86
55.27
11:27
80.15
70.73
77.16 3,46
1.58
.LA
94:00 1.60
77.91
4.16
55.34
11.19
80.08
1.55
77.1
3.52
1.56
-CAROT
95.07 1.20
75.53 1 7.42
53.07
12:99
80.29
1 2.33
2.22 70.88
57.85
4.05
3.04 77.58
72.08
57.00 1.90
LP(ALGI)
96.09 0.41
78.34
4,80
59.91
6.63
78.56 1 1.32
69.71
1.0.3
57.61
3.09
73.39
9.35
69:28
11.78
63.67 1. 7.04
LL
95.81 0.74
73.
= 4.09
59.9%
= 6.56
78.48
= 1.53
69.71
: 0.05
57.47
3,09
73.39
9.35
69:21 = 11.86
63.07
#: 7.04
CCARTT
96.13 22 0.38
50.78 2: 2.30
59.71
3: 6.35
78:93 4: 1.85
70.32
0.86
57.62
3.08
73.39 = 9.35
74.50
7.54
64.29 2: 0.45
Algoritions
Original p-
ET p-
LT -
Algorithms LRFMP)
Originat p-
1.7 p-
1.T
p
60.82-0.53 0.53
0.00
74.65
1.03
68
69.83
65.70
68.40
CAROT
09.82
68.70 0.41
74.15
CAROT
79.41
79.28 = 0.91
77.10
80.71
1.50
RECORDS
48.71-300
50.14
LPALGI)
81.27
81.09
33.44
-LA
54,12 2.00
45.48
1 2.31
56.83
1.30
1.20 75.09
60.87
80.20
0.74
81.25 0.72
81.99 0.51
83.64
0.48
+ CARUT
08.16 0.47
09.00 = 0.74
71.70
3: 0.54
0.90
CAROT
68.90 = 11.09
70.38 = 3.08
82.00 4: 0.51
83.44
0.48
Conclusions. We observed many interesting phenomena: (i) training time mitigation can significantly improve the accu- racy; (ii) state-of- tf-heooft on training time mitigation might not be appropriate for NESY; (iii) approximate techniques for estimating r can sometimes be more effective when used for training time mitigation- - however, it is robust to softmax reparametrization; (iv) testing time mitigation can substantially improve the accuracy of a classifier; however, it tends to be less effective than training time mitigation; (v) CAROT may be sensitive to the quality of estimated ratios F; (vi) Algorithm I offers quite accurate marginal estimates.
gold ratoo
CAROT accurecy
0.65
0.60
0.55
divergence
Figure 3: Impact of the label ratio
Starting from the last conclusion, Figure 4 shows that Algo- rithm I offers quite accurate estimates even in challenging scenarios with high imbalance ratios. Regarding (i), let us focus on Table 1. We can see that both LP(EMP) and LP(ALG1) lead to higher accuracy than models trained exclusively via SL. For exam- ple, when p = in Smallest Parent, the mean accuracy obtained via training under SI. is 67.94 97%9% the mean accuracy increases to 79. 79.24% under LP(EMP) and to 8 81.27% under LP(ALGI). In MAX-4,
quality on CAROT's performance.
8

---

the mean accuracy under SL is 55.48%, increasing to 78.56% under LP(ALGI). Regarding (ii), consider again Table I: when RECORDS is applied jointly with SL, the accuracy of the model can drop substantially, e.g., when p 5 in Table 1, the mean accuracy drops from 67.94% to 48.15%% The above stresses the importance of I.P (Section 4.2).
Let us move to (iii.. In most of the cases, LP(ALGI) leads to higher accuracy than LP(EMP). However, the opposite may also hold in some cases. One such example is MAX-3 for p = 50: the mean accuracy for the baseline model is 66.74%. increasing to 72.23% under LP(ALGI) and to 77.16% under LP(EMP). The above suggests that there can be cases where employing the gold ratios is not the best solution. A similar observation is made in [18]. One cause of this phenomenon is the high number of classification errors during the initial stages of learning. Those classification errors can become higher in our experimental setting, as in MAX-M, we only consider a subset of the pre-images of each weak label to compute SI. and (5), to reduce the computational overhead of computing all pre-images. We conclude with CAROT. Table 1 shows that CAROT can be more effective than LA. For example, in Smallest Parent and p 50, the mean accuracy of LPPEMP) increases from 70.29% to 80.7 %% under CAROT: LA has impact. CAROT may also improve the accuracy of RECORDS models, often, by a large margin. For example, for Smallest Parent and p 15, the mean accuracy of a RECORDS-rained model increases from 50. 14% to 71.70% when CAROT is applied. CAROT is also consistently better than LA when applied on top of RECORDS. However, there may be cases where LA and CAROT drop the accuracy of the baseline model. One such example is met in Smallest Parent and p = 5.
We analyze the sensitivity of CAROT to the quality of the input F. Quality is measured by means of the KL divergence to Fig-
of TV Distance
Variance of TV Distance
0.25
0,006
0.20
0.005
LR=0.1
0.004
LR=0.1
0.15
LR=0.01
LR-0.01
ure 3 shows the accuracy of an MNIST model (trained with the MAX-3 dataset), when CAROT is applied at testing time using 500 ran- domly generated ratios f of varying quality. We observe that CAROT's effectiveness drops as the estimated marginal diverges more from r. Its performance may also decrease by more than 10% with only small perturbation in the KL divergence. This instability may be the reason CAROT fails to improve base model.
Mean
0.10
LR=0,001
Variance
0.003
LR-0.001
UR=0,0001
0.002
LR-0.0001
0.05
0.001
0.000
4
0
2
Temperature
Temperature
Figure 5: Sensitivity of Algorithm I to softmax reparameterization.
To test the sensitivity of CAROT to softmax reparameterization, we performed an additional empirical analysis for MAX-3. We consider range of different learning rates (LR) (0.1, 0.01, 0.001, 0.0001)) and temperatures ((0.1, 0.5, 1,2, 5)) when running Algorithm 1. In each run, we randomly generate (1) true label ratio and (2) 20 initialization points for Algorithm 1. We run the Adam optimizer for 10,000 iterations and compute the total variation (TV) distance between the estimated label ratio and the gold label ratio. Then, we compute the mean and variance of the TV for each experiment. The results are shown in Figure 5. We see that when the temperature is I 2 and the learning rate E (0.1, 0.01, 0.001} (which are typical choices in machine learning experiments), CAROT consistently achieves < 0.01 TV distance, suggesting its robustness.
6 Related work
A more detailed comparison against the related work is in Appendix E.
NESY. We start with some recent theoretical results and training techniques for NESY. The authors at [67] show PAC learnability for NESY, the authors at [40] characterize the number of deterministic optimal neural classifiers function of and propose techniques to improve learning accuracy. However, they make additional assumptions about the training data or the classifiers, In contrast, we propose imbalance mitigation techniques without making additional assumptions. The authors in [28] and [39] propose learning techniques based on unified expectation maximization [54] and entropy regularization, respectively. Unlike our work, none of the above studies empirically or theoretically learning imbalances in NESY. An interesting direction is to combine the active learning strategy in [39] with our training time mitigation technique. particular, we could encourage the acquisition of labels for classes that maximize the entropy and, at the same time, appear with smaller ratios. The

---

latter can be achieved, for example, by assigning higher weight to classes with smaller (estimated) ratios in the entropy computation.
Long-tailed supervised learning. Two supervised learning techniques related to our work are LA [42] and OTLM [46]. Both aim at testing time mitigation. LA modifies the classifier's scores by subtracting the gold ratios. CAROT can be substantially more effective than LA, see Section 5, OTLM assumes that the marginal is known, resorting to an OT formulation to adjust the classifier's scores. In contrast, we propose statistically consistent technique to estimate r, see Section 1.1, and resort to RSOT to accommodate noisy F's. Finally, well-known re- reieetgg schemes [2, 53] are not applicable to our setting: they require access to the gold labels; we assume the gold labels are hidden.
Long-tailed PLL. There is no previous work long-tailes MI-PLL. Hence, we focus on standard PL... The authors in [10] showed that certain classes are harder to learn than others in PL... We are the first extend these results to NESY The only two works at the intersection of long-tailed learning and PL.L are R RECORDS DS [18] and SOLAR [65]. RECORDS modifies the classifier's scores using the same idea as LA and employs a camnentum-updatee prototype feature estimate F. Section 5 shows that RECORDS is less effective than our proposals, degrading the baseline accuracy on multiple occasions. SOLAR cannot act as a competitor our technique, since it cannot be straightforwardly extended to handle training samples with multiple instances, see Appendix E.
7 Conclusions and Future Work
Comments on the theory. In Section 3, the probability of misclassifying an instance x depends only on its class. This assumption is also adopted in other settings, such noisy label learning [74, 45J. Although there are scenarios where this assumption does not hold, our theory is an over- approximation to those scenarios similarly to the connection between class- and instance-dependent noisy label learning. Our analysis in Section 3 assumes that the weak label s depends on the instance only via its class. Nevertheless, it is straightforward to extend our theory to instance-dependent symbolic components a. This can be done by partitioning the input space into sub-regions, where in each region, the symbolic component is fixed function. Generalization bounds can then be derived per region using our methods and averaged to obtain an overall bound. Furthermore, our formulation in (2) can be extended when the instances (x (Zi....,,)) TMr have few correlations. Our theory is good starting point for cases where these correlations are strong, since learning imbalances will also occur in these cases, but now are easier to describe.
Training vs testing time mitigation. CAROT is a more lightweight technique, however, it may lead to lower classification accuracy than LP. On the contrary, LP may increase the training overhead over the ofat--of-thh-art namely training by applying the top-k SL per training sample [71, 67]. This is because when l is fixed, the complexity of computing the SL is polynomial; in contrast, solving (5), which is a linear program calculated out of a batch of samples, is an NP-hard problem. However, when the SL runs without approximations and the pre-image of is very large, the complexity of SL is worst case #P-complete per training sample [8], making (5) more computationally efficient. From a computational viewpoint, it is worth stressing that the LP has a linear growth in o -1 we employ the Tseytin transformation D to translate from the pre-image into the ILP The complexity of enumerating a -1 is inherent to all relevant NESY frameworks [37, 20, 61], as they all rely on the pre-image to compute a loss, see the discussion in [67]. To reduce the computational overhead of our ILP-based technique, we could adopt multiple techniques solve ILP efficiently [22]. We could treat the program in (5) as a differentiable layer by applying optimization techniques as in [1]. When allowing the variables to take values in [0. 1]. (5) becomes an LP. Then, we can employ the simplex algorithm, which runs quite efficiently in practice [56].
We are the first to theoretically characterize and mitigate learning imbalances in NESY. Our character- ization complements the existing theory in long-tailed learning, identifying and addressing the unique challenges in NESY. Our empirical analysis revealed two topies for future research: computing marginals for testing time mitigation and designing more effective testing time mitigation techniques.
References
[1] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. In NeurIPS, 2019.
10

---

[2] Martin Arjovsky, Léon Bottou. Ishaan Guirajani, and David Lopez-Paz. Invariant risk mini- mization. CoRR, abs/1907.02$$5 2020.
[3] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[4] Mateusz Buda, Atsuto Maki, and Maciej A. Mazurowski. A systematic study of the class imbalance problem in convolutional neural networks. Neural Networks, 106:249-259, 2018.
[5] Vivien Cabannes, Alessandro Rudi, and Francis Bach. Structured prediction with partial labelling through the infimum loss. In ICML, page 1230-12:3 2020.
[6] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with dibel-distrbbution-awarr margin loss. In Newr/PS, pages 1567-1578, 2019.
[7] Ming-Was Chang, Lev Ratinov, and Dan Roth. Guiding Semi-Supervision with Constraint- Driven Learning, In ACL, pages 280-287, 6 2007.
[8] Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, 172(6):772 - -799, 2008.
[9] Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, and W. Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 16(1):321-3555 2002.
[10] Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. Journal of Machine Learning Research, 12:1501-1536, 2011.
[11] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurlPS, 2013.
[12] Wang-Zhou Dai, Qiuling Xu, Yang Yu, and Zhi-Hua Zhou. Bridging Machine Learning and Logical Reasoning by Abductive Learning. In NeurlPS, pages
2019.
[13] Jonathan Feldstein, Paulius Dilkas, Vaishak Belle, and Efthymia Tsamoura. Mapping the neuro- symbolic ai landscape by architectures: A handbook on augmenting deep learning through symbolic reasoning. 2024.
[14] Lei Feng, Jiaqi Lv, Bo Han, Miao Xu, Gang Niu, Xin Geng, Bo An, and Masashi Sugiyama. Provably consistent partial-label learning. NeurIPS, page 10948-10960, 2020.
[15) Kuzman Ganchev, João Graça, Jennifer Gillenwater, and Ben Taskar. Posterior regularization for structured latent variable models. Journal of Machine Learning Research, 11:2001-204) 2010.
[16] Nitish Gupta, Sameer Singh, Matt Gardner, and Dan Roth. Paired examples indirect supervision in latent decision models. In EMNLP, pages 5774-5785, 2021.
[17] Haibo He and Edwardo A. Garcia. Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering, 21(9):1263-1284 2009.
[18) Feng Hong, Jiangehao Yao, Zhihan Zhou, Ya Zhang, and Yanfeng Wang. Long-tailed partial label learning via dynamic rebalancing. In ICLR, 2023.
[19] Grant Van Horn and Pietro Perona. The devil is in the tails: Fine-grained classification in the wild. CORR, abs/1 7709001450, 2017.
[20] Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. Scallop: From probabilistic deductive databases to scalable differentiable reasoning. In NeurIPS, pages 25134-25 25145, 2021.
[21] Jiani Huang, Ziyang Li, Mayur Naik, and Ser-Nam Lim. Laser: neuro-symbolic framework for learning spatial-temporal scene graphs with weak supervision, 2024.
11

---

[22] Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Local branching relaxation heuristies for integer linear programs. In CPAIOR, page 96-113, 2023.
[23] Robert I. Jemnrich. Asymptotic properties of non- non-linear least squares estimators. The Annals of Mathematical Statistics, 40(2))633 643, 1969.
[24] Antonis C. Kakas. Abduction. In Claude Sammut and Geoffrey I. Webb, editors, Encyclopedia of Machine Learning and Data Mining, pages 1-8. Springer US, Boston, MA, 2017.
[25] Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. In ICLR, 2020.
[26] Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho. On robust optimal transport: Computational complexity and barycenter computation. In Advances in Neural Information Processing Systems, pages 21947-21959, 2021.
[27] Qing Li, Siyuan Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, and Song-Chun Zhu. Closed loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning. In ICML, 2020.
[28] Zenan Li, Yuan Yao, Taolue Chen, Jingwei Xu, Chun Cao, Xiaoxing Ma, and Jian Lu. Softened symbol grounding for neurosymbolic systems. In ICLR, 2023.
[29] Ziyang Li, Jiani Huang, Jason Liu, Felix Zhu, Eric Zhao, William Dodds, Neelay Velingker, Rajeev Alur, and Mayur Naik. Relational programming with foundational models. Proceedings of the AAAI Conference on Artificial Intelligence, 3869):10635-10644 10644, 2024.
[30] Ziyang Li, Jiani Huang, and Mayur Naik. Scallop: A language for neurosymbolic programming. Proceedings of the ACM on Progrumming Languages, 7(PLDI), 2023.
[31] Tianyi Lin, Nhat Ho, Marco Cuturi, and Michael Jordan. On the complexity of approximating multimarginal optimal transport. Journal of Machine Learning Research, 23(1), 2022.
[32] Wenpeng Liu, Li Wang, Jie Chen, Yu Zhou, Ruirui Zheng, and Jianjun He. A partial label metric learning algorithm for class imbalanced data. ACMI., volume 157, pages 1413-1428, 2021.
[33] Jiaqi Lv, Miao Xu, Lei Feng, Gang Niu, Xin Geng, and Masashi Sugiyama. Progressive identification of true labels for partial-label learning. ICMI,, page 6500-6510, 2020.
[34] Jaron Maene and Lue De Raedt. Soft-unification in deep probabilistic logic. In NeurlPS, 2023.
[35] Jaron Maene and Efthymia Tsamoura. Embeddings as probabilistic equivalence in logic programs. In Proceedings of the Thirty-Ninth Conference on Neural Information Processing Systems (NeurIPS), 2025.
[36] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In NeurlPS, pages 3749- 3759, 2018
[37] Robin Manhaeve, Sebastijan Dumančié, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Neural probabilistic logic programming in deepproblog. Artificial Intelligence, 298: 103504, 2021.
[38] Robin Manhaeve, Giuseppe Marra, and Luc De Raedt. Approximate Inference for Neural Probabilistic Logic Programming. In KR, pages 475-486, 2021.
[39] Emanuele Marconato, Samuele Bortolotti, Emile van Krieken, Antonio Vergari, Andrea Passerini, and Stefano Teso. BEARS make neuro-symbolie models aware of their reason- ing shorteuts. CoRR, abs/2402.122400 2024.
[40] Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini. Not all neuro- symbolic concepts are created equal: Analysis and mitigation of reasoning shortcuts. In NeurIPS, 2023.
12

---

[41] Stephen Mayhew, Snigdha Chaturvedi, Chen-Tse Tsai, and Dan Roth. Named Entity Recogni- tion with Partially Annotated Training Data. In CoNLL, 2019.
[42] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In ICLR, 2021.
[43] Tsvetomila Mihaylova, Vlad Niculae, and André F. T. Martins. Understanding the mechanics of SPIGOT: Surrogate gradients for latent structure learning. In EMNLP, pages 2186-2202, 2020.
[44] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. The MIT Press, 2nd edition, 2018.
[45] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In CVPR, pages 2017.
[46] Hanyu Peng, Mingming Sun, and Ping Li. Optimal transport for long-tailed recognition with learnable cost matrix. In ICLR, 2022.
[47] Hao Peng, Sam Thomson, and Noah A. Smith. Backpropagating through structured argmax using a SPIGOT. In ACL, pages 1863-1873, 2018.
[48] Gabriel Peyré and Marco Cuturi. Computational optimal transport, 2020.
[49] Aditi Raghunathan, Roy Frostig, John Duchi, and Percy Liang. Estimation from indirect supervision with linear moments. In ICML, volume 48, pages 2568 2568-2577, 2016
[50] Dan Roth and Wen-tau Yih. Global Inference for Entity and Relation Identification via Linear Programming Formulation. MIT Press, Introduction to Statistical Relational Learning edition, 2007.
[51] Sivan Sabato, Nathan Srebro, and Naftali Tishby. Reducing label complexity by learning from bags. In PMLR, volume 9, pages 685-692, 2010.
[52] Sivan Sabato and Naftali Tishby. Multi-instance learning with any hypothesis class. Journal of Machine Learning Research, 13(97):2999-3039, 2012.
[53) Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang. An investigation of why overparameterrization exacerbates spurious correlations. In ICML, 2020.
[54] Rajhans Samdani, Ming-Wes Chang, and Dan Roth. Unified expectation maximization. In ACL, pages 688-698, 2012.
[55] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory Algorithms. Cambridge University Press, USA, 2014.
[56] Daniel A. Spielman and Shang- Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51:385 2004.
[57] Vivek Srikumar and Dan Roth. The integer linear programming inference cookbook. ArXiv, abs/2307.00171, 2023.
[58] Jacob Steinhardt and Percy S Liang. Learning with relaxed supervision. In NewrlPS, volume 28, 2015.
[59] Jingru Tan, Xin Lu, Gang Zhang, Changqing Yin, and Quanquan Li. Equalization loss v2: A new gradient balance approach for long-tailed object detection. In CVPR, pages 1685-1694, June 2021.
[60] Jingru Tan, Changbao Wang, Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan. Equalization loss for long-tailed object recognition. In CVPR, pages 11662-11671, 2020.
[61] Efthymia Tsamoura, Timothy Hospedales, and Loizos Michael. Neural-symbolic integration: compositional perspective. In AAAI, pages 5051-5060, 2021.
13

---

[62] Grigori S Tseitin. On the complexity of derivation in propositional calculus. Automation of reasoning, 298:466-4833 1983.
[63] Shyam Upadhyay, Ming-Wei Chang, Kai- Chang, and Wen-tau Yih. Learning from explicit and implicit supervision jointly for algebra word problems. In EMNLP, pages 297-306, 2016.
[64] A. W. van der Vaart. Asymptotic Statisties, Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998.
[65] Haobo Wang, Mingxuan Xia, Yixuan Li, Yuren Mao, Lei Feng, Gang Chen, and Junbo Zhao. Solar: Sinkhorn label refinery for imbalanced partial-label learning. In NeurIPS, 2022.
[66] Kaifu Wang, Hangfeng He, Tin D. Nguyen, Piyush Kumar, and Dan Roth. On Regularization and Inference with Label Constraints. In ICML, 2023.
[67] Kaifu Wang, Efthymia Tsamoura, and Dan Roth. On learning latent models with multi-instance weak supervision. In NewrIPS, 2023.
[68] Lei Wang, Dongxiang Zhang. Jipeng Zhang, Xing Xu, Lianli Gao, Bing Tian Dai, and Heng Tao Shen. Template-baseee based math word problem solvers with recursive neural networks. In AAAI, pages 7154-7151, 2019.
[69] Rei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In ICML, 2019.
[70] Hongwei Wen, Jingyi Cui, Hanyuan Hang, Jiabin Liu, Yisen Wang, and Zhouchen Lin. Lever- aged weighted loss for partial label learning. CoRR, abs/2106.05733 2021.
[71] Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. A semantic loss function for deep learning with symbolic knowledge. In ICML, pages 5502-5511, 2018.
[72] Zhun Yang, Adam Ishay, and Joohyung Lee. NeurASP: Embracing neural networks into answer set programming. In IJCAI, pages 1755-1762, 2020.
[73] Hanlin Zhang, Jiani Huang, Ziyang Li, Mayur Naik, and Eric Xing. Improved logical reasoning of language models via differentiable symbolic programming. In ACL, pages 3062-3077, July
2023.
[74] Mingyuan Zhang, Jane Lee, and Shivani Agarwal. Learning from noisy labels with no change to the training process. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 18468-12478. 2021.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction accurately reflect the paper's contributions in theory (Section 3) and algorithms (Section 4).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitation of the theory part is pointed out in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
The assumptions have been listed in the first paragraph of Section 3 and in the statement of the propositions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided code that implements our algorithms and experiments. The experimental settings are stated in Section 5, with details being included in Appendix F,
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided our source code. The details of the code and experiments are provided in Appendix F.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc
wwtpamiissssoooiiiiiiiooooieeeee onPolicy) icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cccpublic//eeecccccccccccccc wwtpc//ggg/ee/eeeeeeeeeeeeeeeeee /CoeeS//om ietimmsssonnn ssionsolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental settings are stated in Section with details being included in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All the experiments are repeated three times. We report the standard deviations of all the results on these experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
The compute resources that we used are described in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https http///eurrpp.ee/ee//e cc
Answer: [Yes]
Justification: All the authors have reviewed the NeurlPS Code of Ethics and the research conducted in the paper fully adheres the NeurlPS Code of Ethics in all aspects including preserving anonymity.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: There is direct societal impact of the work performed. This paper focuses on the foundational research weakly-supervise learning and is not tied particular
applications.
18

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The libraries with their license that we used are mentioned in Appendix F.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comddatases has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We don't introduce new datasets, but all code is provided and documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
This paper is not based on or linked to LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httpp::///euripaaae ccCc////eeeeeeeeee/222255555 for what should or should not be described.
21

---

Appendix Organization
Our appendix is organized follows:
Appendix A introduces notions related to (robust) optimal transport and discusses the
relationship between our notation and the notation used in the relevant NSL literature.
Appendix B provides the proofs of all the formal statements in Section 3 and more detailed discussion of our error bounds.
Appendix C provides the proof of statistical consistency of Algorithm and discusses other technical aspects related to Algorithm 1.
Appendix discusses a nonlinear program formulation of NESY. In addition, it presents in detail the steps to derive the optimization objective in (5), as well as example of (5) in the context of Example 1.1.
Appendix presents an extended version of the related work.
Appendix F provides further details our empirical analysis and presents results more
benchmarks.
Tables 5 and 6 summarize our notation.
A Extended Preliminaries
Optimal transport. Let Zı and Z2 be two discrete random variables over [mn]] and [ma]] For i E [2] vector b' E IRT denotes the probability distribution of Z;, i.e., P(Z: = m,) - by. for each j E [m.]. Let U be the set of matrices defined as {Q E R xm2 | m, = b² Q1m, = b'). The optimal transport (OT) problem [48] asks us to find the matrix Q E U that maximizes linear object subject to marginal constraints, namely
min (P, Q)
QEU
Assume that we are strict in enforcing the probability distribution b', but not in enforcing b². The robust semi-constrained optimal transport (RSOT) problem [26] aims to find:
min (P, Q) (KL(Q1mm,I1) QEU
(8)
where U' [Q E RT x [Q1m, = b and 0 is regularization parameter. The solution to
(8) can be approximated in polynomial time using robust semi-Sinkhorn from [26], which generalizes the classical Sinkhorn algorithm [11] for OT.
Other NESY notation. We now show that our notation for NESY samples is equivalent to the notation adopted by previous works on the topic [37, 20, 40].
Let AC be background logical theory that "sits" top of f, i.e., it reasons over the predictions of f. In practice, we may have one or more classifiers, f1....;JN=: each with its own input and output domains. To simplify the description, we focus on the single-classifie case. However, both our notation and the notation in [37, 20, 40] can be trivially extended to support these scenarios.
In previous works, NESY training samples may be denoted by (x,Φ), Φ), where x is set of elements from X' and é is a logical sentence (or single target fact in the simplest scenario). The gold labels of the input instances are unknown to the learner. Instead, we only know that the gold labels of the elements in x satisfy the logical sentence 6 subject to IC. The sentence ø and the logical theory IC allow to "guess" what the gold labels of the elements in x might be that Φ is logically satisfied subject to K.. This is essentially the process of abduction [61]. To align with the terminology in our paper, for training sample (x, d). we use the term pre-image" labels of the elements in x, such that á is logically satisfied subject to IC The gold pre-image is the one mapping each instance to its gold label. Abduction allows us "get rid of" & and K and represent each training sample via x and its corresponding pre-images, i.c., as (x, (4 where each pre-image o; is a mapping from x into labels in y/ By assuming canonical ordering on the elements in x, we can view each (x()) (x) as vector of labels, one for each element in x. Therefore,
denote combination of
Prre-images correspond to proofs in [61, 20, 37].
22

---

we can equivalently see each training sample as a tuple of the form (x, (-))). supporting our claim that the two notations are equivalent.
B
Proofs and Details on Section 3
B.1 Proofs
Proposition 3.1 (Class-specific risk bound). For any Y, we have that Ry(f) S Pos
Proof. This result follows directly from the definition of the program (2).
Proposition 3.3. Let d[zj be the Natarajan dimension of [F)- Given confidence level 8 E (0,
we have that Rf(f) & Po, (Rp(f: T), with probability 1 8 for any j [c]. where
2 (ogg 10g(6
1og(1/8)
Rp(f:o, 8) R Tp) +
(3)
2mp
Proof. Let L. o [F] be the function space that maps (training) example (x, s) to its partial loss defined as follows:
La [F] = f(x, s) + Lo (l)) s)lf F
(9)
The standard generalization bound with VC dimension (see, for example, Corollary 3.19 of [44]) implies that:
log(emp/dvo(LL o (FI))
log(1/6)
Rp(f) Tp) +
(10)
mp//vv o [F))
2mm
where (.) (.) is the VC dimension. For simplicity, let = dve Lor o [F)) and dizp be the Natarajan
dimension of [F]. Using a similar argument as in [67], given any samples in 2 x O using [F],
we let N be the maximum number of distinct ways assign label vectors (in y to these samples. Then, the definition of VC-dimension implies that:
2d S N
(11)
On the other hand, these d samples contain Md d input instances in X. By Natarajan's 's lemma (see, for example, Lemma 29.4 of [55]), we have that:
N s (Md)dmee2d)
(12)
Combining (12) with the above equations, follows that
(Md)4ri2240) 2 N > 2d
(13)
Taking the logarithm on both sides, we have that:
dرzl log(Md) + 2dpr log 2 dog
(14)
Taking the first-order Taylor series expansion of the logarithm function at the point (d we have:
d
log(d) <
+ log(6d
(15)
6dll
Therefore,
dlog2 < d1z] log d d log M + 2d loge
log(6d -1) + +d log M + 2dpr loge
< dlt 6d|
(16)
din 2
Rearranging the inequality yields
d d1z log log(
log 2 1/6
(17)
$ log
claimed.
23

---

1.0
1.0
Classification Risk
Classification Risk
0.8
0.8
2
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
0.00
0.05
0.10
0.15
0.20
0.00
0.05
0.10
0.15
0.20
Partial Risk
Partial Risk
Figure 6: Class-specific upper bounds obtained via (2). (left) Dy uniform. (right) Dp, is uniform. (Enlarged version of Figure 2).
Proposition 3.4. I is M-unambiguous, have
R()) & () = ())c-))
(4)
which coincides with Lemma from [67] M = 2, where Ej-1
Proof. Since w == Eis ToW,, we have R(f) = w Th. Then, we consider the following relaxed program:
max whh
h
(18)
s.t. h D S Rp
where D(Errr) is the diagonal part of E..r, namely:
D(E.r) = (nr, j}1f (mod ()HKe())))))))))
(19)
In other words, D(E,.r) encodes all the partial risks caused by repeating the same type of mis- classification twice. On the other hand, the M M-unambiguity condition ensures that each type of misclassification, when repeated twice, leads to a misclassification of the weak label. Therefore, E Range( ((E,.)
The problem in (18) is special case of the songle-constraint quadratic optimization problem. Then, the fact that w E Range (((r,,)) implies that the dual function of this problem (with dual variable A) is
g(A) ARp + w (D((E,,,)))'
(20)
41
where (D(Eor))) is the pseudo-inverse, namely
(D(E..))'=I(nnn)) ( j} (mod e) H)E(()))))))))
(21)
Therefore,
w w((D(EE,:)) ccc 1)
(22)
According to Appendix of [3], strong duality holds for this problem. Therefore, the optimal value given exactly as
inf X g(A) 2/ clc-1) 1) Rp Volc- 1)Rp
(23)
claimed.
24

---

1.0
0.8
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 7: Plot of function & + 1 + (1 - t)² + 4t(1 t)a.
B.2 Further Discussion on the Proposed Risk Bounds
Intuitively, the difficulty of learning is affected by (i) the distribution of weak labels in Dp and (ii) the size of the pre-image of a for each weak label. These two factors are reflected in our risk-specific bounds. Let us continue with the analysis in Example 3.2.
Example B.1 (Cont' Example 3.2). Let start with CASE 1. In this case, class dlass-specifie error bounds suggest that learning the zero class is more difficult than learning nine class, despite the fact that both hidden labels y1 and y2 are uniform in {0,....,)) 9), see the left side of Figure B.2. The root cause of this learning imbalance is a and its characteristics. In particular, the weak labels that result after independently drawing pairs of MNIST digits and applying a on their gold labels are long-tailed, with 17 17/100 in the training data. Hence, we have more supervision learn class nine than to learn zero.
occurring with probability 1/100 and = 9 occurring with probability
Now, let us focus on CASE 2. In this case, our class- class-specific bounds suggest that learning class zero is the easiest learn see right side Figure B.2. This is due two reasons. First, the weak labels follow the same uniform distribution. Hence, we have the same amount of supervision to learn all classes. Second, the pre-image of a for different weak labely is very different. Regarding the second reason, the weak label 8 = 0 provides much stronger supervision than the weak label 8 = 9: when O, have direct supervision (s implies y)1 U2 0); in contrast, when this only means that
and y/2 is any label in (0..... 9}, or vice versa.
The above shows that (i) can lead to imbalances in the weak labels even the hidden labels are uniformly distributed and (ii) may provide supervision signals of very different strengths. Hence, learning in NESY is inherently imbalanced due to a.
B.3 Details on Plotting Figure 2
In this subsection, we describe the steps we followed create the plots Figure 2. We produced the curves shown in each figure by plotting 20 evenly spaced points within the partial risk interval Rp [0, 0.2). To obtain the value of the classification risk at each point, we solved the optimization program (2) using the COBYLA optimization algorithm implemented by the scipy. optimize package. To mitigate numerical instability, for each point, we ran the optimization solver ten times and then dropped invalid results that were not in the range [0, 1]. The median of the remaining valid results was then taken as the solution to (2).
C Further details on Algorithm 1
Proof of statistical consistency of Algorithm1. The approximation given by Algorithm I can be viewed as method to find the maximum likelihood estimation whose consistency is guaranteed under suitable conditions. The most critical is the invertibility of . The invertibility is satisfied by practical transitions the one in Example 1.1, but may fail to hold for certain transitions even if the M M-unambiguity condition [67] holds. We will provide one such example later in this section.
Suppose that the backprobagation step in Algorithm I can find the maximum likelihood estimator: For a real e > 0, let A be the shrinked probability simplex defined as A == (r E Aelry 2 vVj E [c]]- ax Let Fm, argminfes: E5= Py log] V (f)l, be the maximum likelihood estimation. We have:
25

---

Proposition C.1 (Consistency).. If there exists an c > 0, such that r E Dr and V is injective in A then Fi, in probability as mp - 0c.
Proof. Let A = (V.(r))r E A.) be the image of Vr on A. The set A is a compact subset in eg
cg R For any weak label a, E S, let (a). == log([V, (r)1;) be the point-wise logliiklihood. The M-unambiguity condition ensures that each coordinate of every vector in Age should be at least eAM,, and hence the function H is bounded on Agg By Theorem of [23], this ensures that Σ, r). converges uniformly to (S, According to [64] (Theorem 5.7). the uniform convergence further ensures that V, (Fi,)) > p in probability as mp - oc. Since V is invertible, this implies that Fm + probability.
Counterexample where the invertibility of V does not hold. Consider the following transition function for binary labels ( (0,1)) and M = 4:
1,
3 E [1,2,4]
a (11, y2: U3. va)
(24)
0,
otherwise
The -unnmbbiguity condition [67] holds since (0,0,00)) * 11,1,1,1,, On the other hand, the probability the weak label is one can be expressed as:
(ss = 1) r 6riră + 4nin = = 61 r1 4r r))
(25)
which is not an injection. see the plot of function f 6t t)² +t(11 t) in Figure
D Details on Section 4.2
D.1 A Nonlinear Program Formulation
A straightforward idea that accommodates the requirements set in Section 4.2 is to reformulate (8) by (i) extending P (resp. Q) to a tensor of size n x c x M to store the scores (resp. pseudolabels) of M-ary tuples of instances and (ii) modifying U' so that the product of the combinations of entries in Q corresponding to invalid label assignments is forced to zero. However, modifying U' in this way, cannot employ Sinkhorn-like techniques the one in [31], leaving us only with the option to employ nonlinear' programming techniques to find Q.
D.2 Deriving the Linear Program in (5)
Let (zt.1...., Lt,M. se) denote the ê-th NESY training sample, where & E [nz]. To derive the linear program in (5), we associate each weak label st with a DNF formula $ a process that standard in the neurosymbolic literature [71, 61, 20, 67]. To ease the presentation, we describe how to compute te. Let {yr.1,.... .yt.,,...,yRRR be the set vectors of labels -xx.). We associate each prediction with a Boolean variable. Namely, let gr.i.j be Boolean variable that becomes true when ze, is assigned with label j E y/ Via associating predictions with Boolean variables, each ye, can be associated with conjunction Pr,, over Boolean variables from {qt, [M], [c]]. In particular, Qt,. occurs in de,t only if the i-th label in Ye,t is j E y. Consequently, the training sample (I'r, Ze,M, st) is associated with the DNF formula 4; = V iPt, that encodes all vectors of labels in - (sz). We assume canonical ordering over the variables occurring yet,t using Pt.,. to refer the j-th variable, and use |pt, to denote the number of (unique) Boolean variables occurring &Pe,.- Based on
the above, we have <Pr,t = A PEALA
|Pt.l
Similarly to [57], we use the Iverson bracket [] to map Boolean variables to their corresponding integer ones, c.g., [ge. denotes the integer variable associated with the Boolean variable qeii.-
We are now ready to construct linear program (5). Notice that the solutions of this program capture the label assignments that abide by o, i... the labels assigned to each either of yt.1,... Yi.Rg The steps of the construction are (see [57]):
should be
Nonlinearity comes from the KL term and by enforcing invalid label combinations to have product equal to
26

---

(STEP 1) We translate each 4 into a CNF formula Φ via the Tseytin transformation [62] avoid the exponential blow up of the (brute force) DNF CNF conversion.
(STEP 2) We add the corresponding linear constraints out of each subformula in 4%--
Given 4 V SPe,t, the Tseytin transformation associates fresh Boolean variable dg, with each disjunction fe,t in 4 and rewrites & into the following logically equivalent formula:
Rse
Ra (aga spex.)
4
V -1
(26)
After obtaining %y the construction of (5) proceeds as follows. The first inequality that will be added to (5) comes from formula v In particular, it will be the inequality E [ag,e] 2 1, due to
Constraint (3) from [57]. The next inequalities come from the subformula A (agg <> sp,s) from
(26). The latter can be rewritten to the following two formulas:
P
(27)
PE,C,
aee
(28)
k=1
According to Constraint (10) from [57], (27) and (28) are associated with the following inequalities:
-1pecelaeeul +
pppe 2 0
(29)
[pendd + [aee 2 (1
(30)
which will also be added to linear program.
Lastly, according to Constraint (5) from [57], we have an equality Σj=1 = 1, for each f e [n] and i E [MM. The above equality essentially requires the scores of all pseudolabels for given instance Iy, to sum up to one. Finally, we require each pseudolabel [gr,4.s. to be [0, 1], for each E [ni], i E [M], and j E [c].
Putting everything together, we have the following linear program:
M
minimize
min (Q.....Q... )
Σ
Qi, - log((:)) (Pi)),
Re
[
1.
i [n].
- -1ee,llazzd
+ Σ -D lozell
[pe,
2 0,
i [n], [R
1=
subject
[
[ave
1(1 (g,,))),
É [n], [Re]
1,
E [n]. E [
[qe,asl
E [0.
E [n], E [M].] E [c]
(31)
Program (5) results after adding to the above program constraints enforcing the hidden label ratios
Example D.1. We demonstrate an example of (5) in the context of Example 1.1. We assume n We also assume that the weak labels 91 and of the two NESY samples in the batch are equal to 0
and 1, respectively. Due to the properties of the max, we have:
a -'( ((,
(32)
(() {000 (1.0).
(33)
27

---

and formulas 11 and 22 are defined as:
t = 11,10 4122.0
(34)
P1,1
2 22,1, A 42,2,1 V 92.11 A 42.2.0 V 42,1, A 42.2,1
(35)
82,1
P2.2
12,,3
The Tseytin transformation associates the fresh Boolean variables 01,11, 02,1, 02.2: and 02,3 f1,1 P2,1, 22,2. and 92,3, respectively, and rewrites @ and 42 to the following logically equivalent formulas:
=1 A (011, + 91,1)
(36)
V = (a2,1 V 022, V (2233) A (a221 ++ (2.1) A (0222 ++ (2,2) A (02.3 ++ (2,3))
(37)
The linear constraints that are added due to V are:
[01,1]]
IIVII VIVVVV MVVV
|1I,llaa,1 + 100 + 41,200
(38)
1, [9,220 + [01,1]
1(1
The linear constraints that are added due to D/2 are:
[02
+ 2 [a2.3]
P2,1
|22
[22,1,0
42.2.1
VIVVVVVII
22,
[222
+ [92,1.1
+ 9222.0
P2.3
02,33
[42,1,1
+ 12,2,1
(39)
92.1.0)
+ [922.11
102.1
-1(1
|22,1
12.1.1
192,2,0
022
1(1
P222
12.1.1
92.2.1
[02.3)
1(1 [1
(2,33
Finally, the requirement that the pseudolabels for each instance Zg sum up one, for l [2] and i E [2], and to lie in [0, 1] introduces the following linear constraints:
[1.
=
11,21
[2211
=
(40)
[2222.]
1].
i [2).) (0.....
(2,1.
E 0. ie 22 E 99.
E Extended Related Work
NESY. NESY quite often arises in NSL [36, 69, 12, 72, 61, 38, 20, 28, 21]. However, we are the first to study the phenomenon of learning imbalances. Below we discuss some recent theoretical results [40, 39, 67]. The work in [40, 39] deals with the problem of characterizing and mitigating reasoning shortcuts. Intuitively, reasoning shortcut is classifier that has small partial risk but high classification risk. For example, reasoning shortcut is a classifier that has good accuracy in the overall task of returning the maximum two MNIST digits, but has low accuracy in classifying MNIST digits. The work in [40] showed that current NESY techniques are vulnerable to reasoning shortcuts. However, the work does not provide specific error bounds or any theoretical characterization of learning imbalances. The authors in [67] proposed necessary and sufficient conditions that ensure learnability of MI-PLL and provided error bounds for a state-of -hhte-rr neurosymbolic loss under approximations [20]. Our theoretical analysis extends the analysis in [67] by providing (i) class- specific risk bounds (in contrast to [67], which only bounds R(f)) and (ii) stricter bounds for R(f). show in Proposition 3.4,
In particular, relaxing (2).
recover the bound from Lemma 1 in [67] by
Long-tailed learning. The term long-tailed learning has been used to describe settings in which instances of some classes occur very frequently in the training set, with other classes being underrep- resented. The problem has received considerable attention in supervised learning, with the proposed
28

---

techniques operating at training or testing time. Techniques in the former category typically work by reweighting the losses computed using the original training samples [6, 60, 59] or by over- or under-sampling during training [9, 4]. The techniques in the latter category work by modifying the classifiers' scores at testing time and using the modified scores for classification [25, 46), with LA being one of the most well-known techniques [42]. LA modifies the classifier's scores during testing time by subtracting the (unknown) gold ratios. In particular, the prediction of the classifier f given input x is given by arg mäxjele] (z) In(rz). Our empirical analysis shows that CAROT is more effective than LA.
The most relevant to our work is the study in [46]. Unlike CAROT, the authors in [46] focus on PLL and use an optimal transport formulation [48] to adjust the scores of the classifier assuming that the marginal r is known. In contrast, CAROT relies on the assumption that f may be noisy. resorting to a robust optimal transport formulation [26] to improve the classification accuracy in these cases.
PLL. In PLL [10, 33, 14], each training sample is a tuple of the form (r, (71,...,44,) b....,,,))))) where x E X and 4,, ...,..., is a set of candidate, mutually exclusive labels for æ that includes the gold label of Since (1) each NESY training sample is represented as tuple of the form x, a (s). see Section 2, where each element in o (s) is vector of candidate labels for the elements in x, (2) the vectors in x, x are mutually exclusive, and (3) o --((s (s) includes the gold labels for the elements in x, we can see that PLL reduces (and MI-PLL) when restricting to input vectors of one label only.
The observation that certain classes are harder to learn than others dates back to the work of [10] in the context of PLL.. We are the first provide such results for NESY, also unveiling the relationship between a and class-specific risks.
Long-tailed PLL. A few recently proposed papers lie in the intersection of long-tailed learning and standard PLL, namely [32], RECORDS [18] and SOLAR [65], with the first one focusing on non-deep learning settings. RECORDS modifies the classifier's s scores following the same idea with LA and uses the modified scores for training. However, it uses a momentum-updated prototype feature to estimate F. RECORDS's design allows it to be used with any loss function and be trivially extended to support NESY. Our empirical analysis shows that RECORDS is less effective than CAROT, leading to lower classification accuracy when the same loss is adopted during training.
SOLAR shares some similarities with LP. In particular, given single-instance PL. samples of the form (1),,)) (#n,, Sn)}, where each S: C y is the weak label of the L-th PLL sample", SOLAR finds pseudolabels Q by solving the following linear program:
min (Q, - lPg( QEA
(41)
s.t. A = {Igeslnxe
Q1 c, c, qi = Off & 5t} S 1]
The program (41) shows that the information of each weak label Se is strictly encoded into A. To directly extend (41) to NESY, we have two options:
Use an n x M tensor to store the scores of the classifier, where the cell P(e. : stores the scores of the classifier for the label vector (Ji,...: Je) associated with the l- th training NESY sample, for 1 S E S n. However, that formulation would require an excessively large tensor, especially when M becomes larger.
Use separate tensors Pi...., ,, to represent the model's 's scores of the M instances, and set for each 1 < S n, the product Pile,ji x ... x PM [f, je] to be 0 if (Ji...., Je) does not belong to σ -1 (st). However, that formulation would lead to a non-linees program.
Neither choice is scalable for NESY when M is large". Our work overcomes these issues by translating the information in the weak labels into linear constraints, leading to an L.P formulation. Another difference between SOLAR and our work is that we developed Algorithm Ito estimate the ratios of the hidden labels, while SOLAR employs a window averaging technique to estimate r based on the model's 's scores [65]. Finally, although CAROT also uses a linear programming formulation procedure, it differs from SOLAR in that it adjusts the classifier's 's scores at
with a Sinkhorn-styy testing time rather than assigning pseudolabels at training time.
'In standard PL.,, each weak lahel is a subset of classes from V. 'Yet another non- linear formulation is presented in Section D based RSOT (see Section A).
29

---

Listing Theory for the Smallest Parent benchmark.
land_ transportation :- automobile, truck
other_ tuber_transportatiot ;- airplane, ship
transportation land_ tranporrnooot,, other_ citer.transportation home_land_ :- cat, dog
wild_ andialnimal :- deer, horse
aand_animal :- home_land_ la____nndd_all,, wild_land animal other animal :- bird, frog
animal :- animal, other_animal entity :- transportation, animal
Constrained learning. NESY closely related to constrained learning, in the sense that the predicted
label vector y should adhere to the constraint oly) Training classifiers under constraints has
been well studied in NLP [58, 49, 47, 43, 63, 68, 16, 41J. The work in [50] proposes formulation for training under linear constraints; [54] proposes a Unified Expectation Maximization (UEM) framework that unifies several techniques, including CoDL [7] and Posterior Regularization [15]. The UEM framework was also adopted by [28] for NSL. Our LP formulation is orthogonal to UEM it could be integrated with UEM, though.
The theoretical framework for constrained learning in [66] provides generalization theory that suggests that encoding the constraints during both training and testing results in a better model compared to encoding the constraints only during testing. This theory could be extended to explain the advantages ---edded techniques and to characterize the necessary conditions for CAROT to improve model performance.
Other weakly supervised settings. Another well-known weakly supervised learning setting is that of Mtulii-Instande Learning (MIL). In MIL, instances are not individually labelled but grouped into sets that contain least one positive instance, or only negative instances, and the aim is learn a bag classifier [52, 51]. In contrast, in NESY, instances are grouped into tuples, with each tuple of instances being associated with a set of mutually exclusive label vectors, and the aim is to learn an instance classifier.
F Further Experiments and Details
Why using SL and Scallop. SL [71, 37] has become the state-of-the-art approach to train deep classifiers in NSL settings. Training under SL requires computing a Boolean formula Φ encoding all the possible label vectors in --((s) for each NESY training sample (x, 8) and then computing the weighted model counting [8] of Φ given the softmax scores of f. SL has been effective in several tasks, including visual question answering [20]. video-to-text alignment [30], and fine-tuning language models [29], and has nice theoretical properties [67, 40J. Due to its effectiveness, SL is now adopted by several NSL engines, such as DeepProbL.og [37], DeepProbLog 's successors [38], and Scallop
Our empirical analysis only uses Scallop, since it is the only engine that provides scalable SL implementation that can support our scenarios when M 2 3. The computation of a ->) () is generally required by NSL techniques [28. 37, 12, 72]. This computation can become bottleneck when the space of candidate label vectors grows exponentially, as in our MAX-M, SUM-M, and HWF-W scenarios. As also experimentally shown by [61, 67]. the NESY techniques from [37, 38, 12, 28, 72] either time out after several hours while trying to compute o (s), or lead to deep classifiers of much worse accuracy than Scallop. So, Scallop was the only engine that could support our experiments, balancing runtime with accuracy.
A further discussion about scalability issues in NESY can be found in Sections 3.2 and 6 at [67].
Additional scenarios. We additionally carried experiments with two other scenarios that have been widely used as NESY benchmarks, namely SUM-M [36, 20] and HWF-M [28, 30J. SUM-M is similar to MAX-M, however, instead of taking the maximum, we take the sum the gold labels. The HWF-M ocenario was introduced in [27]. In this scenario, each training sample (.I....,TMM..
'The benchmark is available at https://liqing, 10/UG//.
30

---

consists of a sequence ......,,MM of digits in {O....,9) 9) and mathematical operators in { *). corresponding a valid mathematical expression, where s the result of the mathematical expression. As in SUM-M, the goal is to train classifier to recognize digits and mathematical operators. Notice that this benchmark is not ii.d. since only specific types of input sequences are valid. The benchmark comes with list of training samples. However, we created our own samples, to introduce imbalances in the distributions of the digits and operators.
Computational infrastructure. The experiments ran on an 64-bit Ubuntu 22.04.3 LTS machine with Intel(R) Xeon(R) Gold 6130 CPU @ 2. 200GH 3.16TB hard disk and an NVIDIA GeForee RTX 2080 Ti GPU with 1 1264 MiB RAM. We used CUDA version 12.2.
Software packages. Our source code was implemented in Python 3.9. We used the following python libraries: scallopy', hi highspy", or-tools', PySDD 10, PyTorch and PyTorch vision. Finally, used part of the code'' available at [18] to implement RECORDS and part of the code available at [65] to implement the sliding window approximation for marginal estimation.
Classifiers. For MAX-M and SUM-M, we used the MNIST CNN also used in [20, 36]. For HWF-M, we used the CNN also used in [28, 30J. For Smallest Parent, we used the ResNet model also used in [65, 18].
Data generation. To create datasets for MAX-M, Smallest Parent, SUM-M, and HWF-M we adopted the approach followed in previous work [12, 61, 67, 37, 20J. In particular, to create each training sample, we drew instances .i.....; RM independently by MNIST or CIFAR-10. Then, we applied the function over the gold labels .i..... J/M to obtain the weak label To create samples for HWF-M, we followed similar steps to the above. However, to ensure that the input vectors of images represent a valid mathematical expression, we split the training instances into operators and digits, drawing instances of digits for odd is and instances of operators for even is, for E [M]. Before sample creation, the images in HWF were split into training and testing ones with ratio 70%/30%, as the benchmark does not offer such splits, As we state in Section 5, to simulate long-tail phenomena (denoted as LT), we vary the imbalance ratio p of the distributions of the input instances as in [6. 65]: p = means that the hidden label distribution is unmodified and balanced. In each scenario, the test data follows the same distribution the hidden labels in the training NESY data, e.g., when = 0, the test data is balanced; otherwise, it is imbalanced under the same p.
Further details. For the Smallest Parent scenarios, we computed SL and (5) using the whole pre-image of each weak label. For the MAX-M scenarios, we only consider the top-1 proof [67] both when running Scallop and in (5) as the space of pre-images is very large. For the Smallest Parent benchmark, we created the hierarchical relations shown in Listing based on the classes from CIFAR-10.
Tables and plots. To assess the robustness of our techniques. we focus on scenarios with high imbalances, large number of imput instances, and few NESY training samples. Table 2 shows results for SUM-M, for M (5, 6, 7). p {50, 70). and mp 2000. Table shows results for the same experiment, but mp = 1000. In Tables 3, LP(ALGI) refers to running LP using the gold ratios-Algorinn Algorithm| cannot be applied, as the data is not i.i.d. in this scenario. Table 3 focuses on training time mitigation. RECORDS was not considered, as it led to substantially lower accuracy in the MAX-M and Smallest Parent scenarios. Figure shows the marginal estimates computed by Algorithm for different scenarios. Last, Table 4 presents all the results for the MAX-M scenarios. The tables follow the same notation with the ones in the main body of the paper.
Conclusions. The conclusions that we can draw from Tables 2, 3, and Figure 8 are very similar to the ones drawn in the main body of our paper. When LP is adopted jointly with the estimates obtained by Algorithm 1, we can see that the accuracy improvements are substantial on multiple occasions. For example, in SUM-6 with p = 50, the accuracy of classification increases from 67% under SL to 80% under LP(ALG) I); in HWF-7 with p = 15, classification accuracy increases from 37% under SL to 41% under LP(ALG1). We argue that this is due to the low quality of the empirical estimates
hhttps://github... http://ghhhh.ccommcaaaaaoaaaaaaa (MIT license).
hattp:://pppi.orr/ppojjeettt/
(MIT license).
(Apache-2.0 license).
h/tpp/pp.tg/ppopeetts/s////////p (Apach--2.. license).
Phttps://githe http://ghha.acccooeaaaaaaaaaaaaa
(MIT license).
Phttps://githur http:///thubbccom///g/////ssaatt
31

---

Table 2: Experimental results for SUM-M using mp = 2000.
LT 50
LT 70
Algorithms
M
M 6
M 7
M 5
M
M 7
SL
82.28
15.87
67.60
13.43
88.42 1 15.66
85.43 t 11.49
85.60
12.36
79.05
13.31
+ LA
81.74 1 16.27
67.04 1 13.27
78.33 1 15.61
85,38 1 11.58
85,47
12,49
68.95 1 12.91
+ CAROT
82.21 + 15.94
68.82 + 12.61
79.54 + 14.46
86.12 + 11.80
85.47 + 12.37
76.08 + 7.70
LP(ALGI)
89.86 = 8.54
80.10 + 18.45
87.94 = 10.72
91. = 7.62
91.52 = 7.24
63.79 = 12.97
+ LA
89.72 1 8.68
79.43 1 19.15
87.61 1 11.05
91 66 1 7.60
91.52 1 7.24
63.70 1 12.87
+ CAROT
89.14 + 9.16
78.85 + 19.55
77.74 + 19.69
91.29 + 7.86
91.97
+ 6.80
67.06 +: 9.78
Table 3: Experimental results for HWF-M using mp 1000.
Algorithms
M =
M =
M =
SL
94.01 = 0.49
95.34 + 0.14
48.23 + 6.91
I.(EMP)
84.27
10.01
50.90 12.17
LP(GOLD)
94,39 0.27
95.72 4 0.34
55.73 6.122
of r, a phenomenon that gets magnified due to the adopted approximations- recall that we run for SL and LP using the top-1 proofs, in order to make the computation tractable. The lower accuracy of LP(ALGI) for SUM-7 and p = 70 is attributed to the fact that the marginal estimates computed by Algorithm 1 diverge from the gold ones
Figure 8. In fact, computing marginals for this scenario is particularly challenging due to the very large pre-image of a when M = 7, the high imbalance ratio (p 70), and the small number of NESY samples (mp 2000). Table also suggests that SOLAR'S 's empirical ratio estimation technique may harm the accuracy of our LP-based formulation, supporting claim that also made in the main body of the paper, namely that the compulation of the marginals for training time miligation is an important direction for future research.
Figure 8 shows the robustness of Algorithm in computing marginals. Figure 9 shows the hidden label ratios and the corresponding class-specific classification accuracies under the MAX-M and the Smallest Parent scenarios for 50.
32

---

55.74 2.58
14.17
4.86
+4.88 4.88
5.92
56.79 = 1.58
56.81 + 1.56
57.09 # 1.90
63.67 7.04
63.67 = 7.04
M -
64.39 #
57.29
59.93
59.93
63.64
67.71 + 11.58
3.05
3.05
6.14
13.90
65.78 - 14,18
71.25 21 8.70
70,06 = 10.73
69.76 99.76 + 10.31
70.1 # 10.34
69.21 = 11.86
7.54
LT p
M
68.25
66.05
69.28 =
74.30
M 3
5:42
S-42
66.57 55009
68.16 :: 4.00
70.09
7146
77.16 3.46
77.1 77.1+ 3.52
77.58 # 3.04
72.23 = 11.49
10.18
70.20 +-
06.74
74,82
53.06 = 5.11
35.80 = 4.47
7.95
51.25 9.00
4.61
59 99.25 7.27
58.49 5.74
59 .9.56 = 8.14
3.74
56.37 =1 3.13
59.76 + 7.24
M -
13.85
56.5 06.81
Table 4: Experimental results for MAX- .M using mp = 3000.
66.98 3.2
3.20
+ 2.74
16.66
15.54
62.74 8114
69 69.67 5.47
+ 3,96
69 5:5
1.82
68. 73 2.23
69 69.19 1.81
13 p 15
M - 4
44,461111
67.44
53.34
54,46
68 92
71.25 4.48
70,80 + 4.52
74.95 =: 3.45
55 55.47 20.45
54 90 20.10
4 21.83
75.77 + 5.32
76.38 +: 4,72
74.26 3: 9.06
77.05 + 7.00
M - 3
75.83 +
54.32
74.51
4.20
4.20
# 3.42
54.40
4444
5 3.94
2.03
3.27
4
+ 3.09
57.47 + 3,09
57.62 + 3.08
M -
55.13
53.91
55.07
54,40
56.28
55.31
66.24 + 1.22
1.75
0 0.76
+ 0.62
65.43 - 0.87
67.57 1.74
70.54 + 1.82
70.88 = 2.22
69.71 = 0.03
70.32 0.86
M -
1. ppp=
66.70
65.85
70.73
23.23
3.23
21.70
3.13
77 .7.98 3.13
78.31 18.31:4.0 4.00
80.15 + 1.69
08 1.55
2.33 80.25
1.52
78 48 : 1.53
M 3
78:93 +
53 48
55.48
56 56.52
37.90 77.98
4: 5.58
60.26 +: 5.20
641
6.76
7.78
11.27
11.19
53.07 + 12.99
59.98 1 6,56
6.35
M 5
59 89.8
59.43
59 29
6045
50.91
39,71
55.
73.82 + 2.36
73. 2.36
3.10
0.77
- 0.77
1:94=-999
091
77.86 4.22
4.16
75.53 7.42
7.42
1 4.09
80.78 + 2.36
Original
75.11 73.11
78.97 78.97
M
73.08
25.
75.94
77.91
78.34
84.15 + 11.92
85.56 +: 7.25
90.97 + 2.03
1.32
94.69 + 1.60
95.07 + 1.20
95.81 + 0.74
96.13 0.38
M m 3
84.57 # 11
87.63 +
+
94.97
96.09
Algorithms
*CAROT
RECORDS
+ CAROT
LPIEMP)
CAROT
L
CAROT
+LA
LA
SL
33

---

MAX-3, pm5
MAX-3, p=15
MAX-3, 0-
Clas--ppccite relios
0.020
Class-spachie catlos
Abso une aiPerncc
Cless-speciff frecife ratios
0.0100
0.015
0.0075
0.2
0.010
0.10
0. 0.005
0.0050
0.1
0.005
0.05
0.0025
0.000
0.000
3
MAX-5. 5, p=15
MAX 5, p=
MAX 5, 2=5
Cles--pecife retios
0.20
Class-spest specie ratios
0.03
Absolute cifference
Clazs ratios
0.3
0.010
0.04
0.02
0.10
0.003
Absolute
0.1
0.05
0.000
0.00
0.0
0.00
2
0
3
6
2
5
8
Class index
Class index
SUM-5, pm1
SUM-5, p=15
SUM-5, p=50
Dlss-specffic ratios
0.03
Class-spes Doss-specfti ratlos
Absolute difference
Class Class-speciic ratios
0.15
0.2
0.06
dilfe
0.02
0.2
0.10
0.01
0.02
0.02
0.05
0.00
0.0
0.00
3
5
8
8
0
3
6
2
5
8
Class Index
Class Index
Class Indra
SUM-7, p=5
SUM 1=15
SUM-7, p=
Cless- specilc rells
0.15
0.20
0.06
citference
Class- Spes--peccfee ratios
0.2
0.04
Atzolute difference
Clazs-speshi ope--ie rellos
0.3
0.100
Abrelube cifferencce
0.04
0.075
0.02
0.02
0.1
0.050
0.075
0.00
0.00
0.0
0.000
3
5 6
8
0
3
6
6
8
Cless Index
Cless index
Class index
SMALLEST PARENT,
0=5
SMALLEST PARENT, p=15
SMALLEST PARENT, p=50
Cless-spers (les-speciffc tetlos
0.15
0.004
0.003
afference
Class- Coos-speecffc ratos
0.7
0.0015
AbSO ute afference
Cless-spec fecfffc raties
0.3
0.002
lifference
0.0010
0.10
0.002
0.1
0.1
0.001
0.001
0.0000
0.0
3 4
8 CosS Index
3
4 Class Index
8 10
4
7
9
10
Class
Indixx
Figure 8: Accuracy of the marginal estimates computed by Algorithm 1 for different scenarios. Blue
denotes the gold ratios, red the estimated ones, and green the absolute difference between the gold and estimated ratios.
34

---

MAX-3.
MAX-3.
100
100
% Par-clas clussification aczuracy
50
-LPIALL
Hidken label ratlos
60
MNIST classes
MNISTT classes
Smallest Parent,
Smallest p
56 Per-class clas sotiicttioon accuracy
S1. PLPALGG
50
Hidden label ratios
60
60
TO
CIFARIO indices
CIFARIO
Figure (Up left) hidden label ratios r for MAX-5 with p 50. (Up right) Class-specific
classification accuracies under SL and ILP(ALGI) for MAX-5 with 50. (Down left) hidden label ratios for Smallest parent with p = 50. (Down right) Corresponding class-specific classification accuracies under SL. and IL.((AL11) for Smallest parent with 50.
35

---

Table 5: The notation in the preliminaries and the theoretical analysis.
Supervised learning
10
Indicator function
[n] = [I,...,
Set notation
N.Y [c]
Input instance space and label space
I,Y.
Elements from X' and y
X,Y
Random variables over A' and
D,Dx, Dy
Joint distribution of (X, Y) and marginals of X and Y
rj P(Y== P(Y=) = Dy = Tr
probability of occurrence (or ratio) of label j y in Marginal of Y
A.
Space of probability distributions over y
1:X - A
Scoring function
((x)
Score upon æ for class j E
[x:x11 x
Argmax classifier induced by
F.
Space of scoring functions and corresponding space of classifiers
dip
Natarajan dimension of [J]]
E(y' = 16 F
Zero-one loss given V E E
R(F)
Zero-one risk of f
R₂(f) = P([f(()) +jy= =)
Risk of f for the j-th class in y
D(A)
The diagonal matrix that shares the same diagonal with square
matrix A
NESY
M > 0
Number of input instances per NESY sample
X (II, JM..y- UU....,yM.
Vector of input instances and their (hidden) gold label
{al, ..... dos}
Space of es weak labels
S
Random variable over S
σ: PM + S
Symbolic component (known to the learner)
oly)
Weak label
0 (8)
Pre-image of i.e., set of all vectors y E YM s.t. o(y)
(x,8)
NESY sample
Dp
Distribution of NESY samples over X x S
Dps
Marginal of S
Tp
Set of mp NESY samples
[s(x)
Short for ([f)(z)), (.])) (*)))
Ly(y, s(o
Zero-one partial loss subject
Rp(f:o) = (X
Zero-one partial risk subject to a
Rplfio, Tp)
Empirical zero-one partial risk subject to given set Tp of
NESY samples
Notation Section 3
1,, On
All-one and all-zero vectors Identity matrix of size n n
I,
c-dimensional one-hot vector, where the j-th element is one ex c matrix where the (i,j) cell is the probability of f classifying instance with label E to
Cj
H()
h(/) = vee vec(H(())
Vectorization of H())
Wy == vec(W,)
Vectorization of matrix W;:= e,)eJ. where j y Symmetric matrix in x=xxe² depending on and r Optimal solution program (2) and upper bound R
Σar
(Pp(RP((iO))
Rp(f:o, Tp,)0) 0)
Generalization bound of Ap σ) for probability 1
36

---

Table 6: The notation used our proposed algorithms.
Notation in Section 4.1
Pj = P(S 0z)
Probability of occurrence (or ratio) of aj E in
Po
System of polynomials [pil]etes] = (m....)))) (a;) (a:))
T
Vo
Mapping of each ry E y to its solution in Pa. assuming p is known
f.P
Estimates of and p
Pj =
Σ mp
k=
1(s amp/mp
Estimate of P, given NESY dataset Tp
Notation in Section 4.2
Size of each batch of NESY samples
i
Index over [M]
j
Index over [c]
Index over [n]
(32,
NE,M, 8E)
f-th NESY training sample in the input batch
Re
Size of o (
t
Index over [Rg]
P.
Matrix in [0, 1]axe where P.(e,j] = f
(xe,s)
Q
Matrix in 1],xe, where Qi(e,j] is the pseudo-label assigned with label j ) for instance Zz,
A Boolean variable that is true if we,s is assigned with label j E y and false otherwise Conjunction over the qe,i. Boolean variables that encodes the t-th label vector in (se)
iPE,
Φ Fe,1 v... V PLRR
DNF formula encoding the label vectors in o- ((se)
A fresh Boolean variable associated with each şe,t by the Tseytin trans- formation
Notation in Section 4.3
n n>0
Size of each batch of test input instances from X
P
Matrix in xa of the f's scores the test instances of the input batch
P H(P")
Matrix in Raxe storing the CAROT's adjusted scores for P
Entropy of P'
7>>00
Parameters of robust semi-constrained optimal transport problem [26]
37


Reviews:
[{"review_id": "zLwsuRYOH1", "reviewer": "Reviewer_qjJg", "summary": "This paper addresses the challenge of mitigating class imbalance in neurosymbolic learning (NESY) systems by proposing CAROT, a distributionally robust optimization framework that adjusts for class-specific risk at both training and test time. The authors formalize class imbalance as a risk reweighting problem using a linear program and propose a batch-level approximation algorithm (Algorithm 1) to compute instance weights dynamically. The framework is evaluated across synthetic and real-world benchmarks (MNIST, CIFAR-10), and claims to improve balanced accuracy in low-data and long-tail settings. The theoretical contributions include bounding excess risk in class-imbalanced settings and analyzing generalization under distribution shift.", "questions": "1. Can the authors relax the i.i.d. assumption to allow for structural dependencies among instances (e.g., compositional overlap in symbolic trees)? How might this affect the guarantees in Propositions 3.1–3.4?\n2. What is the sensitivity of Algorithm 1 to initializations, learning rate choices, or softmax reparameterization temperature? Were convergence pathologies (e.g., oscillations, mode collapse) observed?\n3. Given that CIFAR-10 and MNIST are not symbolic reasoning datasets, what modifications would be needed to deploy CAROT on real NESY benchmarks (e.g., CLEVRER, NLVR, or hybrid QA tasks)? Have the authors considered adapting the framework to hierarchical or graph-structured label spaces?", "limitations": "The authors acknowledge several limitations (computational overhead, symbolic domain coverage). However, the assumptions regarding instance independence, class-only misclassification risk, and the representativeness of synthetic benchmarks warrant deeper discussion. In particular, the societal risks of deploying fairness-motivated reweighting without proper calibration or robustness checks in high-stakes symbolic systems such as legal or medical rule-based AI deserve consideration.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Let's begin with Strengths:\nThe underlying issue of how NESY systems overfit to dominant symbolic patterns due to class imbalance in supervisory signals is an inadequately explored issue and I am glad the authors have done so in this paper. CAROT appears to be a thoughtful adaptation of DRO principles to symbolic learning. Of note, CAROT consistently improves balanced accuracy across synthetic and real-world datasets. In particular, it appears more robust than prior approaches like RECORDS and LA in long-tail settings. From a theoretical perspective,the generalization bounds in Section 3 provide formal support for the class-level risk minimization approach and the decomposability of the loss into class partitions seems well-leveraged.\n\nNow, let's get into the Weaknesses:\n1. Methodological Limitations\n- The LP in Equation (5) can have exponential constraint growth (via σ⁻¹ enumeration). No concrete approximation strategies are proposed, which limits scalability. Possible alternatives (e.g., sampling-based surrogates, hierarchical grouping of symbolic types, streaming approximations) are not discussed.\n- The softmax reparameterization in Algorithm 1 may cause optimization instability, particularly in skewed or underdetermined settings. No ablation is provided for this choice.\n- CAROT assumes known symbolic partitions, which is restrictive. Real-world NESY systems often operate with evolving or noisy taxonomies. This limits generalizability.\n\n2. Theoretical Gaps\n- The assumption that misclassification depends only on class is strong. Symbolic tasks typically involve multi-factor dependencies (e.g., depth of composition, operator type). This abstraction may misrepresent error dynamics.\n- The paper assumes i.i.d. symbolic structures, yet most NESY settings include structured dependencies (e.g., scene graphs, logic programs). It would strengthen the paper to either relax this assumption or justify it empirically.\n- The tightness and operational utility of the theoretical bounds (Propositions 3.1–3.4) is unclear. Do they guide parameter selection or batch size decisions? No empirical validation is provided.\n\n3. Experimental Limitations\n- Evaluation is done on overly synthetic symbolic tasks (MAX, SUM, etc.) that may not reflect real-world NESY generalization challenges. The authors may benefit from considering evaluation on more complex symbolic reasoning datasets like CLEVRER, ProofWriter, or GQA.\n- Only 3 seeds are used, which is insufficient given the observed variance across some datasets (e.g., CIFAR-10). For high-variance metrics like balanced accuracy, ≥10 seeds would improve statistical reliability.\n- Baseline selection could be expanded. While RECORDS and LA are relevant, stronger fairness-focused baselines like IRM (“Invariant Risk Minimization”, Arjovsky et al., 2019) or Group DRO (“An Investigation of Why Overparameterization Exacerbates Spurious Correlations”, Sagawa et al., 2020) are notably absent. Even basic class-reweighting schemes are omitted.\n- No computational benchmarks are provided. Training time overhead, LP solver configuration, and memory usage are critical in assessing CAROT’s deployability.", "was_revised": true, "final_justification": "As expressed below, I feel the authors have done a great job at addressing my concerns and I will be updating their rating to Borderline Accept.", "rebuttal": "> **Comment 1**: The LP in Eqn (5) can have exp constraint growth (via σ⁻¹ enumeration). No concrete approximation strategies proposed,... Possible alternatives (e.g., sampling-based surrogates, hierarchical grouping of symbolic types, streaming approximations) not discussed\n\n1. LP does NOT grow exponentially in σ⁻¹. It has a LINEAR growth, as we employ the Tseytin transformation to translate from the pre-image into the ILP (clarified in line 246). The transformed formula's size grows linearly to the input's. Details of this transformation is in Appendix D\n2. The complexity of enumerating σ⁻¹ is inherent to all relevant NeSy frameworks [32,18,65,25], as they all rely on the pre-image to compute a loss. This is discussed in Section 3.2 of [61]\n3. In our experiments, we consider top-$k$ pre-images to address the crux of exhaustively enumerating the preimage. Other techniques, such as [25], rely on sampling\n4. As discussed in line 383, the complexity of applying SOTA NeSy loss, SL [65], is \\#P-complete [6]. In contrast, the complexity of solving our ILP is NP-hard\n5. There are multiple techniques to solve ILP efficiently, e.g., “Local Branching Relaxation Heuristics for ILP” (Huang et al., 2023)\n6. We could treat the program in Eqn 5 as a differentiable layer by applying optimization techniques as in “Differentiable Convex Optimization Layers” (Agrawal et al., 2019)\n7. Eqn 5 is a LP when allowing the variables to take values in [0,1]. Then, we can employ the simplex algorithm which runs  quite efficiently in practice, see “Smoothed analysis of algorithms Why the simplex algorithm usually takes poly time” (Spielman et al., 2004)\n\nSince the literature in points 5-7 is orthogonal to our contribution (mitigating NeSy imbalances), we decided not to touch upon this topic. However, we'll include this discussion in the revised version.\n\nFinally, we are unsure what it means by “hierarchical grouping of symbolic types”. Could it be possible to clarify?\n\n> **Comment 2** on stability of Alg1 with softmax\n\nRegarding the sensitivity of Alg1 w/ softmax reparameterization, we did additional sensitivity analysis for M-MAX with M=3. We consider a range of LR in {0.1, 0.01, 0.001, 0.0001} and temperatures in {0.1, 0.5, 1, 2, 5}. In each run, we randomly generate a true label ratio and 20 init points. We run the Adam optimizer for 10000 iterations and compute the TV distance between the estimated ratio and gold ratio. We then compute the mean and variance of TV for each run. The results are as follows.\n\nMean:\n|Temp|LR=0.1|LR=0.01|LR=0.001|LR=0.0001|\n|-|-|-|-|-|\n|0.1|6.85e-03|9.57e-04|7.21e-04|3.92e-03|\n|0.5|8.30e-04|2.09e-04|2.76e-04|2.74e-02|\n|1|6.82e-04|3.15e-04|2.41e-03|9.83e-02|\n|2|1.56e-04|5.00e-06|2.62e-03|2.35e-01|\n|5|9.80e-05|3.58e-04|2.20e-02|2.50e-01|\n\nVar:\n|Temp|LR=0.1|LR=0.01|LR=0.001|LR=0.0001|\n|-|-|-|-|-|\n|0.1|1.42e-04|3.69e-06|6.00e-06|1.07e-04|\n|0.5|3.03e-06|1.36e-07|1.00e-06|3.61e-04|\n|1|3.00e-06|7.03e-07|3.90e-05|2.06e-03|\n|2|1.27e-07|5.37e-11|3.90e-05|5.83e-03|\n|5|2.83e-08|1.97e-06|2.71e-04|3.31e-03|\n\nWe see that when temp <=2 and LR \\in {0.1, 0.01, 0.001} (which are typical choices), Alg.1 can consistently achieve < 0.01 TV, suggesting robustness of Alg.1.\nAlso, we did not observe any oscillations or collapse during optimization.\n\n> **Comment 3**: CAROT assumes known symbolic partitions. Real-world NESY systems often operate with evolving or noisy taxonomies...\n\nOn “known symbolic partitions”: the most well-known NeSY frameworks that study our setting, such as DeepProbLog [32], Scallop [18], NeuroLog [65], assume both the semantics of the neural classifiers outputs, and the symbolic component σ are fixed and known. However, we agree that considering noisy or unknown σ and simultaneously learn the classifier and σ is an important future research direction.\n\n> **Comment 4**: The assumption that miscls depends only on class is strong. Symbolic tasks typically involve multi-factor dependencies (depth of composition, operator type)\n\nFirst, as we discuss in the conclusion, the assumption that misclassification are dependent only on class is typically adopted in relevant areas, such as noisy learning [68, 41] and weakly-supervised learning [A, B]. Also, a similar assumption that misclassification depends only on class is made by previous theoretical study of our NeSY setting where stylistic factors are independent of the classes, see Section 3 in [36].\nIt is important to study such a setup, as it serves as a solid foundation to generalize our techniques to more complex and realistic scenarios.\n\nSecond, our bounds do consider “operator type” if that means σ. Could you clarify what it means by the “depth of composition” or point us to theoretical research that characterizes imbalances by taking into account the “depth of composition”?\n\n[A] Learning from partial labels. JMLR, 2011\n\n[B] Wang et al. On learning latent models with multi-instance weak supervision. In NeurIPS, 2023b\n\n> **Comment 5**: The paper assume i.i.d. symbolic structures, yet most NESY include structure dependencies (e.g., scene graphs)\n\nNotice that the i.i.d. assumption is not related to logic programs, which correspond to σ in our formulation and the formulation of NeSy.\nAlso, one can still consider the scene graphs or other structures as a whole to be i.i.d. distributed. E.g., in NLP & CV, we consider i.i.d. documents & images, despite they have complex inner structures. In this way, we can still apply the theory developed here. Nevertheless, taking the structure into account may yield sharper bounds. This can be done using known techniques, e.g. [A], that analyze structured predictions assuming bounded dependency.\n\n[A] Stability and Generalization in Structured Prediction. JMLR, 2016\n\n> **Comment 6**: The tightness and operational utility of the theoretical bounds (Prop 3.1–3.4) unclear. Do they guide para selection or batch size decision\n\nTightness: The bound in Prop. 3.1 is tight in the sense that it can be achieved by constructing a classifier whose label-specific errors are equal to the maximizer of Eq. 2. The bound in Prop. 3.3 can become arbitrarily tight by plugging in any generalization bound for partial risk.\n\nAlgorithmic Implication: our bound is independent of any algorithm, which is typical in learning theory. So, it does not directly provide guidance on the hyperparas choice. The advantage of doing this is that it characterizes the intrinsic difficulty/imbalance of the problem itself, which is not caused by the choice of the algorithms.\n\n> **Comment 7**: Evaluation is done on overly synthetic tasks ... considering more complex symbolic datasets like CLEVRER, ProofWriter, GQA\n\nThe MAX, SUM, HWF and other benchmarks have been used by the most influential papers in the community, e.g., [32,18,25,36].\n\nAlso, we **additionally conducted experiments using VQAR** [18], a VQA benchmark based on GQA with high imbalances. With ILP, the mean balanced accuracy over 3,000 training samples increased from 46.84% (for baseline SL [65]) to to 53.06%. Further details are in our replies to reviewer MSJR’s Comment 2.\n\n> **Comment 8**: Only 3 seeds used, ... For high-variance metrics like balanced accuracy, ≥10 seeds would improve stat reliability\n\nOur Table 5 includes 144 experimental combinations, Table 2 (Appendix) has 72, and we also report results on two additional benchmarks. Given the large number of combos, it is impractical to consider 10 seeds per run. Nevertheless, to address this comment, we additionally provide results with 10 runs on cases with high variance (e.g., MAX-M for $\\rho=50$ with $m_P$ = 3K) here. \nResults of balanced accuracy over 10 runs are:\n| |M = 3|M = 4 |M = 5|\n|-|-|-|-|\n|SL|67.72±3.98|70.33±6.88|56.08±1.99|\n|LP(EMP)|78.23±2.71|72.72± 6.34|56.12±1.22|\n|LP(ALG1)|74.01±6.92|72.33±5.27|59.93±3.99|\n\nIn the revised version, we will consider more seeds for cases with large variance.  \n\n> **Comment 9**: Baseline selection could be expanded ... Even basic class-reweighting schemes are omitted\n\nWe kindly disagree that IRM or Group DRO could be considered as baselines in our case, as they focus on different settings: spurious correlations and overparameterization. Also, they assume access to the gold labels during training. So, it would be difficult to adapt them to our setting where the gold labels are unknown.\n\nWe considered RECORDS, because it operates at training time and fits our setting where access to gold label is not possible.\n\n> **Comment 10**: No computational benchmarks provided. Training time overhead, LP solver configuration, and memory usage are critical in assessing CAROT’s deployability\n\nWe guess the reviewer refers to LP’s deployability since CAROT does not rely on linear programming.\n\nOn solver configuration: we simply ran the solver with the default options without any special configuration. This can be confirmed by looking at our code – the solver in utils_algorithms.py and the scripts for reproducing experiments (folder “scripts”).\n\nOn computational benchmark: our reply to Reviewer YWhF’ Comment 2 reports all the relevant runtime and memory usage. It shows the baseline training approach and our LP technique are on par in terms of runtime and memory.\n\n> **Comment 11**: Can the author relax i.i.d. assumption to allow structural dependencies? How might this affect Prop 3.1–3.4?\n\nPlease see our reply to Comment 5.\n\n> **Comment 12**: What modifications are needed to deploy CAROT on real NESY benchmarks\n\nCAROT is a testing time mitigating technique that modifies the softmax predictions of a classifier given $x$. Hence, it does not require any modifications to be applied to any benchmark.\n\n> **Comment 13**: Have the author considered adapting to hierarchical or graph-structured label spaces?\n\nThe new experiments we conducted on a GQA-based benchmark [18], deals with hierarchical labels, e.g., supervision is of the form “Q(O) :- name(O, superclass)”. Further details are in our replies to reviewer MSJR, Comment 2."}, {"review_id": "YZRP5HLWVK", "reviewer": "Reviewer_mHmX", "summary": "This paper investigates learning imbalances in neurosymbolic learning (NSL), specifically focusing on class-specific risks that emerge when neural classifiers are trained with hidden gold labels revealed only through a symbolic component. Unlike previous research, this work highlights how the symbolic component itself can cause imbalances, not just data imbalances. The authors propose a method to estimate hidden gold label marginals and introduce algorithms to mitigate these imbalances during both training and testing, achieving up to 14% performance improvement over existing baselines.", "questions": "I notice that in the experiment part, you use only MAX-M to validate the effectiveness of your algorithm. Are there any other choices of $\\sigma$ in practical scenarios? Have you considered the approximation of $\\hat{\\boldsymbol{r}}$ and effectiveness of CAROT in different choices of $\\sigma$?", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. The authors continuously use simplified and intuitive examples to illustrate the important comcepts and strategies, making the paper easy to read.\n2. The paper introduces and addresses the unexplored problem of learning imbalances in Neurosymbolic Learning (NESY), which is novel and applicable.\n3. This paper has strong theoretical foundations, offering stricter bounds and makes fewer assumptions compared to existing work.\n4. Empirical experiments validates the effectiveness of the proposed CAROT algorithm.\n\n## Weaknesses\n\n1. Consider Case 1 in Example 3.2. The solution of (2), though tighter than exsiting bounds, are still worst-case upper bounds. It might not be appropriate to claim that class 0 is the hardest to learn by comparing the worst-case solutions of classification risks.\n2. A minor issue: missing noun in line 8: \"Our theoretical (?) reveals a unique phenomenon\".", "was_revised": true, "final_justification": "The authors addresses all of my concerns. This paper is overall in good quality as I have stated in \"strengths\" part of my review. I decide to keep my rating at 5.", "rebuttal": "> **Comment 1**: Consider Case 1 in Example 3.2. The solution of (2), though tighter than exsiting bounds, are still worst-case upper bounds. It might not be appropriate to claim that class 0 is the hardest to learn by comparing the worst-case solutions of classification risks.\n\nThanks for the question. While worst-case upper bounds does not imply that class 0 would necessarily have the highest label-specific risks in **all** the training scenarios – since it depends on the model/data/initialization – however, the worst-case analysis can serve as a conservative, distribution-free way to characterize the learning difficulty, just like in mathematical analysis, one may use supreme norm to characterize the distance between two functions, when the pointwise comparison is intractable. Such worst-case comparisons are also standard in learning theory. For example, people use VC dimension and Rademacher complexity to understand relative model complexity/task difficulty when exact risks are intractable. \n\nOn the other hand, our bound is tight in the sense that it can be achieved by constructing a classifier whose label-specific errors are equal to the maximizer of the program in Eq. (2). Therefore, we believe our theory serves as a meaningful description of the relationship between the partial risk and class-specific risk.\n\nNonetheless, we can add a discussion on this point in the revised version to avoid misinterpretation.\n\n> **Comment 2**: A minor issue: missing noun in line 8: \"Our theoretical (?) reveals a unique phenomenon\".\n\nIt should be “analysis”. Thanks for pointing it out. \n\n> **Comment 3** I notice that in the experiment part, you use only MAX-M to validate the effectiveness of your algorithm. \n\nWe do consider other benchmarks, such as Smallest Parent (lower part of Table 1) and SUM-M (Table 2 in the appendix). We have empirically shown that CAROT can considerably improve the model’s accuracy for the corresponding $\\sigma$s. \n\n> **Comment 4**: Are there any other choices of \\sigma in practical scenarios? \n\nRegarding choices of $\\sigma$ in practical scenarios, in the literature, people also considered other transitions such as sorting of numbers [32] and transitions induced by video to text alignment. We described several applications of our learning setting in lines 28 – 31. To address this comment, we additionally conducted experiments on a new VQA benchmark based on GQA, VQAR [18]. Detailed results on this benchmark are given in our replies to Reviewer MSJR’s Comment 2.\n\nWith other choices of $\\sigma$, our Algorithm 1 for estimating $\\hat{\\mathbf{r}}$ can be applied without modification as long as the i.i.d. assumption for the instances holds, and we believe that CAROT would also improve the model’s accuracy in such tasks if the transition itself introduces imbalance or the data is imbalanced. \n\nIn more complex settings where the i.i.d. assumption does not hold, one could still apply [1] to approximate $\\mathbf{r}$. However, this estimator can be biased, in general, depending on the strength/structure of the sample correlation. It will be an interesting future research direction to develop a more effective version of Algorithm 1 for cases where i.i.d. assumption does not hold. Notice that in the experiments we conducted on VQAR, we approximated $\\mathbf{r}$ by moving window heuristic [59]. Despite the approximations, our technique offered good accuracy improvements, especially for the minority classes, e.g., for the baseline SL [65], the mean balanced accuracy over 3,000 training samples was 46.84\\% for SL. For ILP, the mean balanced accuracy increased to 53.06\\%. Further details are given in our replies to Reviewer MSJR’s Comment 2. \n\n> **Comment 5**: Have you considered the approximation of \\hat{r} and effectiveness of CAROT in different choices of \\sigma?\n\nRegarding the effectiveness of CAROT under different choices of $\\sigma$, yes, CAROT has been applied in the MAX-M (upper part of Table 1), Smallest part (lower part of Table 1), and SUM-M (Table 2) scenarios. \n\nRegarding the methods we have tried to approximate $\\hat{r}$, please see our response above for Comment 4. Regarding the effectiveness of CAROT under different approximations of $\\mathbf{r}$, we analyze the sensitivity of CAROT subject to the quality of the input \\hat{\\mathbf{r}}. The results are shown in Figure 4 and discussed in lines 348 –353. We observed that CAROT’s effectiveness drops as the estimated marginal diverges more from $\\mathbf{r}$."}, {"review_id": "xK4xmVkFUM", "reviewer": "Reviewer_YWhF", "summary": "The paper focuses on a neglected core issue in neurosymbolic learning (NSL)—learning imbalance, which refers to systematic differences in classification errors across different classes. Through theoretical analysis and algorithmic design, it reveals the independent influence of symbolic components on class imbalance in NSL. The authors propose two algorithms (LP and CAROT) to mitigate imbalance during training and testing phases, and validate their effectiveness through experiments. These algorithms achieve significant performance improvements over existing baseline methods.", "questions": "How is the NP-hardness of LP mitigated on large-scale datasets? Are approximation algorithms or parallelization considered?", "limitations": "The computational complexity of nonlinear programming can be further discussed, particularly regarding its scalability in high-dimensional scenarios.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nThe paper provide a class-specific error bound in the context of NESY and show the effect of $\\sigma$ on learning imbalances.\n\nThe authors propose two algorithms to mitigate imbalances during training and testing time.\n\nWeaknesses\n\n1.The dependence of CAROT on the accuracy of $r$ and the dependence of the LP method on batch size and $\\sigma$ should be supplemented in the Discussion or Conclusion section with an analysis of these limitations.\n\n2. The LP-based method requires solving a linear program for each training batch, which may incur substantial computational overhead, especially for large batch sizes. It is recommended to report the runtime and resource consumption in the main text and to provide a discussion on the scalability of the approach.\n\n3. The main text (e.g., Section 2) references \"Tables 6 and 7,\" but these tables are absent in the main manuscript. While they may be included in the appendix, this is not explicitly stated. Section 4 introduces numerous mathematical symbols, yet their explanations are deferred to Table 7, creating a disconnect that hampers readability.\n\n4. The structure is densely packed, and transitions between concepts are abrupt. In particular, the shift from Section 3 to Section 4 is rather sudden. It is recommended to include a brief transitional paragraph to improve the flow.", "was_revised": true, "final_justification": "We have read the reply to Comment 1 and are willing to increase the score.", "rebuttal": "> **Comment 1**: The dependence of CAROT on the accuracy of r and the dependence of the LP method on batch size and \\sigma should be supplemented in the Discussion or Conclusion section with an analysis of these limitations.\n\n- About the dependence of CAROT on $\\mathbf{r}$, we do have such an analysis in Figure 4. The relevant discussion is in lines 348–353. \n- About the dependence of LP on $\\sigma$, we want to stress that, due to exponential explosion in the number of pre-images in $\\sigma^{-1}$ as $M$ increases (e.g., in the MAX-5 scenario, there are 5 × 94 candidate label vectors when the weak label is 9), we ran all experiments for M-MAX, M-SUM, and HWF both for the baseline SL using the top-$k$ pre-images, as we discuss in the paragraph starting in line 1201 in the appendix. The blow-up of enumerating $\\sigma^{-1}$ is independent of SL and LP. Notice also that by increasing the top-$k$, the experiments would quickly become infeasible to run both for SL and LP, due to the very large cost for exploring the pre-images. In the Smallest Parent benchmark, we considered the whole $\\sigma^{-1}$, as this exponential blowup was not occurring. To address this comment, we additionally conducted experiments on a new VQA benchmark based on GQA, VQAR [18], to assess LP's scalability on more realistic $\\sigma$s. In this benchmark, like in Smallest Parent, we also considered the whole $\\sigma^{-1}$. Detailed results on this benchmark are given in our replies to Reviewer MSJR’s Comment 2.\n- Regarding the dependence of our LP technique to the batch size and relevant measurements, we provide details to the Comment 2 just below.  \n\n> **Comment 2**: The LP-based method requires solving a linear program for each training batch, which may incur substantial computational overhead, especially for large batch sizes. It is recommended to report the runtime and resource consumption in the main text. provide a discussion on the scalability of the approach.\n\nBelow we provide results for all the additional experiments and measurements requested by the reviewer. A quick summary is as follows: \n1. The baseline training approach and our LP technique are on par in terms of runtime and max memory consumption in most cases. \n2. Our experiments in our original submission ran with a small batch size (64). By increasing it, the balanced accuracy increases. \n\nWe start by showing results on the runtime for SL and ILP for different batch sizes. The results in our submission were computed based on batch size = 64. As discussed in Section 5, we used Scallop’s implementation [18] of the SL and or-tools (as mentioned in line 1182) to solve the LP. Further details about our implementation are in Appendix F.   \n\n**Table A.** Mean runtime per epoch in minutes for MAX-$M$ (2,000 training samples). We form the LP based on the training samples in the current batch. \n\n| Technique |   M=3 |   M=4 |   \n|-------------|--------------:|--------------:|\n| SL(batch size = 64)    [65]     |    7.14  |    7.23  |  \n| SL(batch size = 128)   [65]      |    5.00  |    5.40  |  \n| SL(batch size = 256)  [65]       |   2.26  |   2.12  |  \n| SL(batch size = 512)    [65]     |   1.42  |   1.32  | \n| LP(batch size = 64)         |    7.16  |    8.21  |  \n| LP(batch size = 128)           |    5.16  |    5.29  |   \n| LP(batch size = 256)           |   3.12  |   3.28  |  \n| LP(batch size = 512)           |    4.01  |   5.42  |  \n\n**Max memory consumption.** The max memory consumption for the hardest case (MAX-4 for batch size = 512 and 2000 training samples) is: \n- SL [65]: 1.74 GB\n- LP: 1.80 GB \n\n**Table B.** Mean runtime per epoch in minutes for SUM-$M$ (1,000 training samples). We form the LP based on the training samples in the current batch. \n\n| Technique |   M=5 |   M=6 |   \n|-------------|--------------:|--------------:|\n| SL(batch size = 64)    [65]     |    5.59  |    5.48  |    \n| SL(batch size = 256)  [65]       |   0.43  |   0.57  |  \n| SL(batch size = 512)    [65]     |   0.44  |   0.55  | \n| LP(batch size = 64)         |    6.06  |    6.28  |  \n| LP(batch size = 256)           |   3.11  |  4.07  |  \n| LP(batch size = 512)           |    6.00  |  7.40  |  \n\n**Max memory consumption.** The max memory consumption for the hardest case (SUM-6 for batch size = 512 and 1000 training samples) is: \n-\tSL [65]: 823 MB \n-\tLP: 1.07 GB\n\nBelow, we show the balanced mean accuracy for LP(ALG1) for different batch sizes. The results that we show in our submission, were computed based on batch size = 64. \n\n**Table C.** Balanced accuracy for MAX-$M$, $\\rho$=50 (3,000 training samples).\n\n| Technique |   M=3 |   M=4 |   \n|-------------|--------------:|--------------:|\n| LP(batch size = 64)         |    72.23 ± 11.49  |    69.28 ± 11.78  |  \n| LP(batch size = 128)           |    72.98 ± 09.32  |    70.83 ± 08.45  |  \n| LP(batch size = 256)           |    73.35 ± 08.27  |   71.03 ± 05.01  |  \n\n**Table D.** Balanced accuracy for Smallest parent, $\\rho$=50 (3,000 training samples).\n\n| Technique |   M=2 |     \n|-------------|--------------:|\n| LP(batch size = 64)         |    83.44 ± 0.48  |  \n| LP(batch size = 128)           |    84.41 ± 0.69  |    \n| LP(batch size = 256)           |    85.87 ± 0.52  |   \n\n> **Comment 3**: The main text (e.g., Section 2) references \"Tables 6 and 7,\" but these tables are absent in the main manuscript. While they may be included in the appendix, this is not explicitly stated. Section 4 introduces numerous mathematical symbols, yet their explanations are deferred to Table 7, creating a disconnect that hampers readability.\n\nIndeed, Tables 6 and 7 are in the appendix. The corresponding symbols are all defined in the main body; however, to enhance readability, we summarized them in Tables 6 and 7. Unfortunately, as these tables are large, it is difficult to move them to the main body. \n\n> **Comment 4**: The structure is densely packed, and transitions between concepts are abrupt. In particular, the shift from Section 3 to Section 4 is rather sudden. It is recommended to include a brief transitional paragraph to improve the flow.\n\nThe paragraph in lines 183–192 explains the transition between Section 3 and Section 4. Perhaps the reviewer means something else?"}, {"review_id": "eNgLZXoxXM", "reviewer": "Reviewer_MSJR", "summary": "This paper addresses the problem of mitigating class-specific error disparities in NeSy classification tasks. The analysis is sound and highlights how the concept-extractor function significantly influences these imbalances and propose mitigation strategies applicable at both training and test time. This paper support the approaches with experiments demonstrating improvements in classification accuracy.", "questions": "The topic of learning imbalances in NeSy is novel and relevant. However, I find it difficult to grasp the practical implications of mitigating these imbalances, especially in comparison to existing strategies for addressing Reasoning Shortcuts [1]. Could you provide concrete and realistic examples where your proposed strategy offers clear advantages? I believe that including a compelling example would significantly strengthen the paper.\n\nFurthermore, how computationally demanding is the proposed linear programming approach during training? While the method appears to improve model accuracy, does it also lead to improvements in concept accuracy? The same question applies to the proposed test-time mitigation strategy.\n\nLastly, do you think the mitigation strategies you are proposing can be paired with those based on annotation acquisition like [2]?\n\n------\n\n**References**:\n\n[1] Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini. Not all neuro-symbolic concepts\nare created equal: Analysis and mitigation of reasoning shortcuts. In NeurIPS, 2023\n[2] Emanuele Marconato, Samuele Bortolotti, Emile van Krieken, Antonio Vergari, Andrea\nPasserini, and Stefano Teso. BEARS Make Neuro-Symbolic Models Aware of their Reasoning\nShortcuts. In UAI, 2024", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**:\n\nThe paper presents a solid theoretical analysis that extends prior work by providing a bound on the risk associated with class-specific learning imbalances. This result is well-founded and offers a promising direction for improving the trustworthiness of NeSy models. Additionally, the authors propose a mitigation technique applicable during both training and test time.\n\n------\n\n**Weaknesses**:\n\nThe proposed mitigation strategies rely on linear programming and optimization procedures, which I believe may be challenging to scale in practice. Moreover, it is unclear how addressing class-specific imbalances interacts with existing methods aimed at solving reasoning shortcuts. Finally, while the theoretical contributions are valuable, the empirical evaluation is limited to relatively simple datasets such as MNIST and CIFAR.", "was_revised": true, "final_justification": "The rebuttal satisfied all my concerns", "rebuttal": "> **Comment 1**: The proposed mitigation strategies rely on linear programming and optimization procedures, which I believe may be challenging to scale in practice. \n\nFirst, our testing time mitigation strategy, CAROT, relies on a PTIME Sinkhorn algorithm, hence it is very efficient. Regarding a discussion on scalability and optimizations related to our LP formulation, please see our reply to Reviewer qjJg’ Comment 1 that discusses complexity aspects of our technique and relevant optimizations to reduce the runtime.\n\nPlease also see our reply to Reviewer YWhF, Comment 2, where we provide runtimes for our LP formulation and the baseline SL. Furthermore, while our imbalance mitigation technique may mildly, in most cases, increase the training overhead as we empirically show, we would like to point the reviewers to similar issues that are encountered in other strategies for addressing the issue of ambiguous learning in NeSy and, in particular, to the mitigation strategies proposed in [1] and [2].\n\nStarting from [2], the proposed mitigation strategy involves training an ensemble of instance classifiers, which, as also acknowledged by the authors, in Section 3.6., increases the training time proportionally to the number of models in the ensemble. Instead, our formulation involves training a single classifier each time (with slightly increased runtime over the SOTA training loss). Second, the objective-based mitigation strategy in Section 5.3 from [1] involves training using an autoencoder which can be computationally expensive. As the authors state at the end of Section 5.3. “However, minimizing the reconstruction can be non-trivial in practice, especially for complex inputs”. \n\nOverall, we agree with the reviewer that our mitigation strategy may increase the training overhead, however, this may be inevitable to improve the model accuracy, as it is the case in relevant research as well. \n\n> **Comment 2**: Finally, while the theoretical contributions are valuable, the empirical evaluation is limited to relatively simple datasets such as MNIST and CIFAR.\n\nThe MAX, SUM, HWF, and other benchmarks have been used by the most influential papers in the relevant community, e.g., [32,18,25,36]. Unlike them, however, we considered larger values for M (up to 7, see Table 3). \n\n**Results on VQAR.** We additionally conducted experiments on VQAR [18], a VQA benchmark based on GQA. VQAR exhibits two types of imbalances. First, the base classes are highly imbalanced. For example, the most frequent “name” class is “window” with 35.9K training instances, the 20th most frequent “name” class is “table” with 10K instances, while the 30th most frequent class is “nose” with 7.6K instances. Second, the type hierarchies, practically $\\sigma$, further exacerbate those imbalances, e.g., there are five different warcraft types, but 75 different food types. As the training samples in VQAR are not i.i.d., we empirically approximated $\\mathbf{r}$ using the moving window heuristic from [59]. In our experiments, we considered queries of the form “Q(O) :- name(O, superclass)”, where superclass is a superclass of a base class, e.g., fruit is a superclass for orange. The benchmark comes with 500 classes. We considered the whole $\\sigma^{-1}$ to form the linear program. We ran experiments focusing on the 30 most frequent ones. \n\nFor the baseline SL [65], the mean balanced accuracy over 3,000 training samples was 46.84\\% for SL. For ILP, the mean balanced accuracy increased to 53.06\\%. The three classes with biggest improvements were door, fence, and nose where the accuracies improved from 22.76% to 29.68%, from 19.32\\% to 41.03\\%, and from 32.83\\% to 43.17\\%.  \n\n> **Comment 3**: The topic of learning imbalances in NeSy is novel and relevant. However, I find it difficult to grasp the practical implications of mitigating these imbalances, especially in comparison to existing strategies for addressing Reasoning Shortcuts [1].\n\nFirst, it is worth noting that reasoning shortcuts are essentially all the classifiers that minimize the weakly supervised loss, e.g., the semantic loss, but map the input instances to wrong concepts. Notice that the term “concept” in reasoning shortcuts corresponds to the term “instance label” in our notation. \n\nSecond, many strategies for mitigating reasoning shortcuts require *additional* assumptions:\n\n1. Knowledge-based Mitigation. Involves editing the symbolic component directly by, e.g., eliciting additional constraints from a domain expert. \n2. Multi-Task Learning (MTL). Involves training a classifier using samples corresponding to different symbolic components, e.g., mixing M-MAX with M-SUM training samples. \n3. Data-based Mitigation. Involves providing supervised samples with the weakly-supervised ones. \n4. Architecture-based Mitigation. Involves using a more complex neural architecture.\n5. Objective-based Mitigation. Uses an autoencoder along with the neural model.\n\nInstead, the focus of our work is to mitigate imbalances without making additional assumptions on the supervision. Nevertheless, we do not disagree that integrating these strategies with our imbalance mitigation techniques would potentially improve the classification accuracy. It’s like combining long-tailed learning techniques from standard deep learning with representation learning approaches, such as contrastive learning. They are proposed to tackle different aspects. Yet, their combination could be very effective. We will add this discussion in the revised paper. \n\nAs in standard ML [4, 54, 53, 7, 2, 22, 42, 38], the practical implication of mitigating imbalances in NeSY is to force the classifier to predict minority classes at testing time or give more mass to minority classes at training time. This intuition is discussed in lines 183–192 of our submission. \n\n> **Comment 4**: Could you provide concrete and realistic examples where your proposed strategy offers clear advantages? I believe that including a compelling example would significantly strengthen the paper.\n\nAbout using a compelling example. We follow the same approach with the reasoning shortcuts paper, where they exemplify the notion of reasoning shortcuts via the MNIST-Addition (see their Example 1 and 2), and exemplify the concept of learning imbalances via the MNIST-MAX example.\n\nConcretely: \n- Figure 1 shows the accuracy of an MNIST classifier trained with MNIST-MAX training samples using the SL, suggesting the phenomenon of learning imbalances in NeSy. \n- Example 3.2 and the left part of Figure 2 show that our class-specific error bounds align with the observations in Figure 1.\n- The upper part of Figure 8 in the appendix compares the class-specific accuracies of a classifier trained using MNIST-MAX data for $M=5$ and $\\rho=50$ under the SL (green curve) and our ILP technique (blue curve). This scenario is very challenging as the frequencies of the hidden labels are highly imbalanced: 0.0000e+00, 0.0000e+00, 6.67E-05, 0.0000e+00, 0.0000e+00, 6.0000e-04, 6.6667e-04, 7.3333e-03, 8.9667e-02, 9.0167e-01. In this scenario, the baseline model (row SL in Table 1, for $M=5$ and $\\rho=50$) has the following class-specific classification accuracies: \n0\\%, 0\\%, 13.33\\%, 0\\%, 0\\%, 0\\%, 0\\%, 0\\%, 99.28\\%, 93.35\\%. \nOur training-time mitigation technique (row ILP(ALG1) in Table 1, for $M=5$ and $\\rho=50$) leads to the following class-specific classification accuracies: \n0\\%, 0\\%, 43,33\\%, 0\\%, 0\\%, 0\\%, 2.29\\%, 42.80\\%, 97.61\\%, 96.91\\%, \nsubstantially improving the classification accuracy for the MNIST digits \n2, 6, and 7 -- especially for 6 and 7, the baseline model has accuracy zero. \n\nAs we wrote in reply to Comment 3, the practical implication of mitigating imbalances in NeSY is to force the classifier to predict minority classes during testing or give more mass to minority classes during training. \n\nAs a realistic example, please see our earlier replies to your Comment 2, where we included additional experiment results for VQAR.\n\n> **Comment 5**: Furthermore, how computationally demanding is the proposed linear programming approach during training? \n\nPlease see our response to Comment 1.\n\n> **Comment 6**: While the method appears to improve model accuracy, does it also lead to improvements in concept accuracy? The same question applies to the proposed test-time mitigation strategy.\n\nIn our work, the model accuracy is evaluated based on class-specific accuracies, i.e., how well the classifier predicts the class of each input. In particular, the class-specific accuracies are balanced to ensure a fair comparison, see lines 306–308. In addition, in our setting, the term “concept” in the reasoning shortcuts terminology coincides with the term “instance label” in our terminology. Hence, by improving the model accuracy, we do improve the concept accuracy.\n\n> **Comment 7**: Lastly, do you think the mitigation strategies you are proposing can be paired with those based on annotation acquisition like [2]?\n\nThis is a great point. We believe the reviewer refers to Section 3.5 in [2], which presents an active learning strategy for querying the most informative gold annotations: \"requesting supervision only for specific concepts G_j by maximizing H(p(Cj |xi)) for i and j.\" Yes, it is possible to combine this active learning strategy with our training time mitigation technique. In particular, we could encourage the acquisition of labels for concepts that maximize the entropy and, at the same time, appear with smaller ratios. The latter can be achieved, for example, by assigning a higher weight to concepts with smaller (estimated) ratios in the entropy computation. We will add the relevant discussion in the revision of our paper."}]

Author rebuttal:

Meta-review: This paper provides a new algorithmic framework for characterizing and mitigating class-wise imbalances in neurosymbolic learning through a LP-based approach. All the reviewers were ultimately enthusiastic about this contribution and in favor of acceptance. The authors are strongly recommended to address all reviewer feedback in the camera-ready version, especially (but not limited to): a) clarifications around the computational complexity of the procedure in theory (e.g. rate of growth of computational complexity in various parameters such as $\sigma$, characterization of the worst-case computational landscape with respect to other state-of-the-art methods), b) add the experiments that they ran in the rebuttal phase around sensitivity to hyperparameters, wallclock runtime compared to competing methods, and memory consumption.
Decision: Accept (poster)