Learning from Label Proportions by Learning with Label Noise
Authors: Jianxin Zhang
Yutong Wang
Clayton Scott
Venue: NeurIPS 2022 Accept (2022)
Keywords: Machine Learning
Semi-supervised Learning
Learning Theory
Learning from Label Proportions
Learning from Label Noise

Abstract: Learning from label proportions (LLP) is a weakly supervised classification problem where data points are grouped into bags, and the label proportions within each bag are observed instead of the instance-level labels. The task is to learn a classifier to predict the labels of future individual instances. Prior work on LLP for multi-class data has yet to develop a theoretically grounded algorithm. In this work, we propose an approach to LLP based on a reduction to learning with label noise, using the forward correction (FC) loss of \textcite{Patrini2017MakingDN}. We establish an excess risk bound and generalization error analysis for our approach, while also extending the theory of the FC loss which may be of independent interest. Our approach demonstrates improved empirical performance in deep learning scenarios across multiple datasets and architectures, compared to the leading methods. 

Learning from Label Proportions by Learning with Label Noise
Jianxin Zhang, Yutong Wang, and Clayton Scott Electrical Engineering and Computer Science
University of Michigan Ann Arbor, MI 48109
[jianxinz, yutongu, clayscot)@umich edu
Abstract
Learning from label proportions (LLP) is weakly supervised classification prob- lem where data points are grouped into bags, and the label proportions within each bag are observed instead of the instance-level labels. The task to learn a classifier to predict the labels of future individual instances. Prior work on LLP for multi-class data has yet to develop a thcoretically grounded algorithm. In this work, we propose approach to LLP based reduction to learning with label noise, using the forward correction (FC) loss of Patrini et al. [30]. We establish an excess risk bound and generalization error analysis for approach, while also extending the theory of the FC loss which may be of independent interest. Our approach demonstrates improved empirical performance in deep learning scenarios across multiple datasets and architectures, compared to the leading methods.
Introduction
In the weakly supervised problem of learning from label proportions (LLP), the learner is presented with bags of instances, where each bag is annotated with the proportions of the different classes in the bag. The learner's objective is to produce classifier that accurately assigns labels individual
instances in the future. LLP arises in various applications including high energy physics 7 election prediction
445] computer vision 20), medical image analysis (2) remote sensing
activity
recognition and reproductive medicine [2].
To date, most methods for LLP have addressed the setting of binary classification 50
36
39
24 37, 38), although multiclass methods have also recently been investigated 9 22 46)
The dominant approach to LLP in the literature is "label proportion matching": train classifier to accurately reproduce the observed label proportions on the training data, perhaps with additional regularization. In the multiclass setting, the Kullback-Leibler (KI.) divergence between the observed and predicted label proportions adopted by the leading approaches to assess proportion matching. Unfortunately, while matching the observed label proportions is intuitive and work well in some settings, it has little theoretical basis (50 38), especially in the multiclass setting, and there are natural
settings where fails [50 39
Recently, Scott and Zhang 39 demonstrated a principled approach to LLP with performance guarantees based
reduction learning with label noise (LLN) in the binary setting. Their basic strategy was to pair bags, and view each pair of bags as an LLN problem, where the observed label proportions are related to the "label flipping" "noise transition" probabilities. Using existing technique for LLN based on loss correction, which allows the learner to train directly on the noisy data, they formulated bags. They established generalization error analysis and consistency for the method, and also showed that in the context of kernel methods, their approach outperformed the leading kernel methods.
overall objective based (weighted) of objectives for each pair of
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The objective of the present paper is to develop theoretically grounded and practical approach to multiclass LLP, drawing inspiration from Scott and Zhang (39. The primary challenge stems from the fact that Scott and Zhang (39] employed the so-called "backward correction" loss, which solves LLN by scaling the output of a loss function of interest according to the noise transition probabilities 28 50 35). While this loss correction was demonstrated to work well for kernel methods in a binary setting, Patrini et al. 30J introduced an alternative loss correction that performs better empirically in deep learning settings (see also [53). They proposed the "forward correction" loss, which scales the inputs to a loss function of interest according to the noise transition probabilities. Patrini et al. [30] find that backward correction "does not seem to work well in the low noise regime," and is "a linear combination of losses" with "coefficients that can be far [apart] by orders of magnitude which "makes the learning harder".
The present work is thus inspired by Scott and Zhang 39 but uses the forward correction (FC) loss in multiclass setting. This requires number of technical modifications to the arguments of Scott and Zhang 33.. Most notably, it now becomes necessary to demonstrate that the FC loss is calibrated with respect to the 0-1 loss, critical property needed for showing consistency. Such analysis is inherently not needed when using the backward correction, where the target excess risk is proportional to the surrogate excess risk (from which calibration follows trivially). Furthermore, Scott and Zhang (39] does not require analysis of proper composite losses, which are needed in the FC framework. Finally, the multiclass setting involves new estimation challenges not present in the binary case. These factors mean that our work is not a straightforward extension of Scott and Zhang [39]. Indeed, the authors of recent report acknowledge that it is "difficult to extend [the method of Scott and Zhang
[39] to multiclass classification" " [16]-
Additional related work: Much work on LLP has focused on learning specific types of models.
including support vector machines [36, 50
47
33
5
19 40), probabilistic models [88]
13|
45
32
12]. random forests [41), neural networks 21
46 and clustering-basee models, 5
Many of these works develop learning criteria that are specific to the model being learned.
On the theoretical front, Quadrianto et al. 34 and Patrini et al. (30) initiated the learning theoretic study of LLP, introducing Rademacher style bounds for linear methods, but they do not address consistency w.r.t. a classification performance measure. Yu et al. (5T) provides support for label proportion matching but only under the assumption that the bags are very pure. Saket (37] studies learnability of linear threshold functions. Recently Saket et al. (38) introduced a condition under which label proportion matching does provably well w.r.t. a squared error loss in the binary setting, and developed an associated algorithm. This method does not scale easily to large datasets, and further requires knowledge of how bags are grouped according to different bag-generating distributions.
A handful of recent papers have studied multiclass LLP in deep learning scenarios. Dulac-Arnold et al. (9] study the KL loss for label proportion matching, and a variant based on optimal transport. Liu et al. [2 23 examine an approach based on generative adversarial models. Tsai and Lin (46) study the use of regularizer derived from -upeevvid learning. One challenge common to these approaches is that their implementations employ mini- maii-batches of bags, which becomes computationally prohibitive for large bag sizes when the batch size still very small, e-g., 2 or 3 bags. In contrast, our approach avoids this issue. Finally, recent technical report presents a risk analysis for multiclass LLP under the assumption of fixed bag size, which we do not require [16]. Their method is not tractable for large bag sizes in which case they approximate their objective "using the bag-level loss proposed in the existing research." "
Contributions and Outline: Our contributions and the paper structure are summarized as follows. In Section 2 we review the FC loss as solution LLN. In Section 3 we extend the theory of the FC loss for LLN. In particular, we show that the FC loss is "uniformly calibrated" with respect to the 0-1 loss using the framework of Steinwart
4 establish an excess risk bound, and determine an explicit lower bound on the calibration function in terms of the noise transition matrix. In Section 4 we extend the results of Section B to the setting with multiple noise transition matrices, which form the basis of our approach to LLP. In particular, we establish an excess risk bound and generalization error analysis for learning with multiple noise transition matrices, which turn enables proofs of consistency. In Section 5 we state the probabilistic model for reducing LLP to LLN with multiple different noise transition matrices and present the LLPFC algorithms. Experiments with deep neural networks are presented in Section 6 where we observe that our approach outperforms competing methods by a substantial margin. Proofs appear in the supplemental material.
2

---

2 Learning with Label Noise and the Forward Correction Loss
This section sets notation and introduces the FC loss as solution learning with label noise. Let X' be the feature space and y = (1,2....,C C} be the label space, C E N. We define the C-simplex as AC = (p RC; p: 2 0, Vi = 1,,,... ..... C, E. 2i=11: 1} and denote its interior by A Let P be probability measure on the space X y.
Viewing P as the "clean" probability measure, a noisy probability measure with label-dependen label noise can be constructed from P in terms of a C x C' column-stochasti matrix T, referred to as the noise transition matrix. Formally, we define a measure Pr on X' x y x y by requiring events A C Pr {i] x {(}) P(A x {i))tz, where f3,, is the element at the j-th row and i-th column of T. Let (X, X.YY have joint distribution Pr where X is the feature vector, Y is the "clean" label, and y is the "noisy" label. Thus the element of at row and column j is t. = Pr = Y = j). In addition, is the marginal distribution of (X, Y). Define Pr to be the marginal distribution of (x, Y). Let F be the collection of all measurable functions from X' to AC
The existence of a regular conditional distribution is guaranteed by the Disintegration Theorem (e.g. Theorem 6.4 in Kallenberg (14) under suitable properties (e.g. when X' is a Radon space). While the existence of regular conditional probability beyond the scope of this paper, we assume fixed regular conditional distributions for Y and Y given X exist, denoted by P(- (-- > x X [0 and Pr(- | .) y' x X - [0, 1]. respectively. Given I E X, we define the probability vectors 7(x)= = [P(1 z)..... ..)....P((I.) P(C z))" and (z) (1 x)....,
x)1² where we use tr to
denote transposition. It directly follows that 7)r (a) Tn(x).
We use R, to denote the positive real numbers. The goal of LLNN is to learn a classifier that optimizes
a performance measure defined w.r.d. P. given access to corrupted training data (X,, Y:) i.dd Pr. In this work we assume T' is known or can be estimated, as is the case when we apply LLN techniques to L.P (see Section
5p. more formal formulation of I.LP is given in Section 5
When attempting to minimize the risk associated to the 0-1 loss and the clean distribution P, it common employ smooth or convex surrogate loss. For LLN problems, the idea of loss correction is to modify the surrogate loss so that when optimized using the noisy data, it still achieves the desired goal. Below, we introduce the forward correction loss, before which we need define inner risk and proper loss. For this purpose we focus on loss functions of the form L :: A x ) - R. Definition Let L AC y + E. be a loss function. The inner L-risk at x with probability measure P is CL.P. AC + R, CL,P.a() == Ey- Y). The minimal inner L-risk at with probability measure P is CL, == infgesc CT.p,,(1)-
Definition 2. E: C y - IR is proper loss i probability measures P on X x Y, Vo E x, X.Ci.r.- = Ct.p.x (n(x))) and a proper loss is called strictly proper if the minimizer of Ct is unique for all x E X.
Commonly used proper losses include the log loss glog (g. c) log ge, the square loss (52 c) = (1= - )² and the 0-1 loss 10d (g. c) = min (arg max, 9;), among which only the log loss and the square loss are strictly proper 49 Here 1 denotes the indicator function. Note that it is common to compose proper losses with inverted link funetions, leading to familiar losses like the cross-entropy loss. Such losses are discussed further in Section
We now ready introduce the forward correction loss.
Definition 3. Let E be a strictly proper loss and let T be a noise transition matrix. Define the forward correction loss of l &r C y IR, Cr(g,c) c) == c).
It follows from the definition that, if T is invertible, then the inner rirr under the distribution Pr has a unique minimizer 17(x). Next we introduce L-risk and L-Bayes risk associated with a loss L. Definition 4. Let L C y + R and P be a probability measure. Define the L-risk of f with distribution P to be RL.P : F + R. RL,P(f) == Ep [L(f(X), Y)] and the L-Bayes risk to be RE, inf / JEF (f.
We call -f) the excess L-risk of f under distribution P. Given proper loss l, Theorem 2 of Patrini et al. 30 establishes Fisher consistency of the FC loss, meaning the minimizer of 4-risk
3

---

under the clean distribution P is the same as the minimizer of éy-risk under noisy distribution Pr: arg migmineer (f) arg min Rty. PP. (f). Next, we present stronger result relating the excess fy-risk under the noisy distribution Pr to the excess 0-1 risk under the clean distribution P.
3 Calibration Analysis for the Forward Correction Loss
Our objective in this section to show that when is the 0-1 loss and & is a continuous strictly proper surrogate loss, there exists a strictly increasing, invertible function 0 with 0(0) such that Vf E F and V distributions P. ((L,, Rt.,p) Re,,Px - Pp. Given such bound, it follows that consistency w.r.t the surrogate risk implies consistency w.r.l. the target risk. The results in this section are standalone results for the FC loss that may of independent interest, and will be extended in the next section in relation to LLP. The following theorem guarantees the existence of such function 0, given that T is invertible.
Theorem 5. Let f be continuous strictly proper loss and T be an invertible column-stochane matrix. Let L be the 0-1 loss. Assume Rt,,Pr oo. Then 30 [0.1] + [0, xo] that is strictly increasing and continuous, satisfying ((0) = 0, such that ff E FfRLP(()) - Ri, S
0-1 (Ren.PP (f) -Rir
The function 0 in Theorem 5 depends on E and T. The following proposition provides convex lower bound on 0 for the commonly used log loss glog (q, c) = log 9c- Let M E RCCC be a matrix and let
[|Mx|| |I- || be norm on CCC The subordinate matrix norm induced by ||- is || := Supxe3C:afi [[
When || || is the 1-norm on RC, the induced norm is denoted | || 2. referred to as the matrix 1-norm,
and can be computed as |M maxigisc Di= (i,
10
Proposition 6. Lei T E RCCC be an invertible, [0, oo] by (c) 2 1| If the 0/1 loss, E the log loss, then for all f E F and distributions
matrix. Define 2r [0, [0, -
2
P. RLP((f) Ri,r S 27 [Re,, (f) Ri,,,,) V2 V211T / (f) (f)- Ri
The factor ||- || may be viewed constant that captures the overall amount of label noise. The more noise, the larger the constant. For example, let I and N be the identity and the all 1/C's matrices, respectively. Let [0, 1] and T (1 a:) a.. Thus, a 0 represents the noise-free case and a = the noise-only case. It is easy to verify that T-1 = (1 - aa- aN) and ||T (1 a) -1
2/C)a.).
Learning with Multiple Noise Transition Matrices
Our algorithms for LLP, formally stated in subsection 5.4 reduce the problem of L.PP to LLN by partitioning bags into groups and modeling each group as an LLN problem. Since each group has its problem that refer as learning with multiple
own noise transition matrix, this leads noise transition matrices (LMNTM). In this section, we show how to extend the calibration analysis of section B to this setting. In addition, offer generalization error bound that justifies empirical risk minimization learning procedure based on a weighted sum of FC losses.
4.1 Learning with Multiple Noise Transition Matrices
We first define the LMNTM problem formally. For all E N. denote N,, = 21, Consider a clean distribution P X' x y and noise transition matrices Tı, T2...., Ty. .T. For each i we denote the noisy prior as the ag E c where, Ve E y, (c(c) = Pr. (Y = c). We assume the a, are known for theoretical analysis. In practice, is estimable as discussed below. In LMNTM, we observe data
points S = {X,,.. E Nv, c C y, j E Nn,.c} where Xt.e, sid Pr; (- c), and ni,e E N is the number of data points drawn from the class conditional distribution Pr; (- c). Assume all X mutually independent. We make additional remarks on this setting in Section in the appendix.

---

4.2 A Risk for LMNTM
The following result extends Theorem to LMNTM. It establishes that the risk Re.P.T. which can be estimated from LMNTM training data, is a valid surrogate risk. This type of result is not needed for the backward correction approach of Scott and Zhang (3).
Theorem 7. Let L be the 0-1 loss and N E N. Consider sequence of invertible column-stochastie N matrices T {T:) i=1 and a continuous strictly proper loss function f. Let (mx) E A
N
Define P.T F + R by (e, = Em= W,Rer, Pr. (f) and R2,,,T = inf (e...T((). Assume Vi E (1.2..... N). Ri,,P < oc. Then a strictly increasing continuous function 0
[0, 1] + [0, oc] with (()) = 0 f.r.for all P. Vf e F, ((RL, - RT,p) S (f) Ri.
The weights ue allow the user flexibility, for example, to place different weights on noisier or larger subsets of data. Unlike Scott and Zhang [39 however, because the weights appear in both our excess risk bound and generalization error bound, it is not straightforward to optimize them a priori. We discuss weight optimization in detail in Section ii the appendix.
4.3 Generalization Error Bound
The aggregate risk P.T is desirable because it can naturally be estimated from the given data. We propose the empirical risk
N
(c
Thg.
Rw.s( = Σ
En (f((iss))))) j=1
(I)
4he
should be noted that Rw.s(f) is an unbiased estimate of (.T) Here we establish a general- ization error bound for this estimate which builds on Rademacher complexity analysis.
To state the bound, we must first introduce the notion of proper composite loss 49 This stems from the fact that in practice, a function f outputting values in A is typically obtained by composing -valuee function (such
neural network with C output layer nodes), with another function RC + A such as the softmax function. Thus, let &b 2 C A + V be an invertible function where subset of a normed space, referred to as an invertible link function. Consider & C sh o F == {ub o f: f E F). and observe that Vgg 9, ab- g E F. In practice, v0 is fixed and we seek to learn g E 9 that leads to an f E with a risk close the Bayes risk. An example of de 6-11 is the softmax function so that xb l + V, (p) = logp: - =/4 Eb log
Pk. (v (,()) = EE e^N where 24 is
the interior of A and V {s e RC: Di 8; 0). This motivates the following definition.
Definition 8. Given an invertible link function u C + V, we define the proper composite loss de of a proper loss f: C x x to be b V x y + I, Xe(u, c) = e(v (v)
For example, when E is the log loss and + is the softmax function, Ar is the cross-entropy (or multinomial logistic) loss. With this notation, are now able state our generalization error bound for LMNTM. We study two popular choices of function classes, the reproducing kernel Hilbert space (RKHS) and the multilayer perceptron (MLP). We use G1 to denote the Cartesian product of C' balls of radius R in the RKHS and G2 to denote a multilayer perceptron with C' outputs.
Definition 9. Let & be a symmetric positive definite (SPD) kernel, and let H be the associated reproducing kernel Hilbert space (RKHS). Assume k is bounded by K, meaning Va, [[((,,)]lx S K. Let IK.a denote the ball of radius R in H. Define G1 = =Gk x 9K.R R ... X G (C copies).
We follow Zhang et al. (54) and define real-valued ML.Ss inductively: Definition 10. Define No = fx (2,0) E Rdd ||e1/2 I 3), and > 2, inductively define RRd, ||o|h S I E Nm-13. where 3 TR and μ is 1- Lipschitz activation function. Define an MLP which outputs a vector in R2C by G2 = Nm N X x Nm (C copies). We additionally assume that the choice of p satisfies Vmm E N, E N Theorem 11. Let Tı, T2. ..., Tn be invertible aolumn-stochant matrices. Let E. be a proper loss such that Vi, the function der, (-)c) is Lipschitz continuous w.r.t. the 2-norm. Let S be the set of
Nn {x Σj=1 (zn((,
5

---

data points as defined in Section 4.7 Assume suPzex,,ee 11((x)112 S Ag for some constant Ag
pq E {1,2}. Let Rw, be as defined in equation U R(g)) Re. (V- o og) Es R Then for each q (1,2), vg E [0, 1). with probability at least -, 6,
N c w
sup Ru s(g) - R - (max( Ag + Memmlloy 2 8 gE9,
2 + CB max Men Dg
1=1
where Bg is a constant depending on gg. | lo maxc/ Mer. (0, c)), and |er, is the smallest real number such that it is Lipschitz constant of Aer, (-. c) for all
Theorem II is special case of of Lemma 26 which extends the notion of Rademacher complexity to the LMN MIM setting and applies to arbitrary function classes. Lemma 26 presented in the appendix.
Let HM, denote the harmonic mean of Ri,11 ni,c, i.e, HM;
The and is optimized by w;
term V VE Ee
N c wi could be written V V N wi HM.
HM// ΣN HM leading VE DC ni.. V EN HM. The term V E HM, van- ishes (needed to establish consistency) when N goes to infinity, or when Bi s.t. Ve, niçe goes to infinity. For the special case where all bags have the same size and all weights w; are 1/N,
V E
N EE wf
C Thus, consistency is possible even if bag size remains bounded. As-
R5,e V Nn suming E is the log loss and - is the softmax function, we next study the constants |dez, and Ner:1o
Proposition 12. Let l be the log loss, v/-1 be the function, and T be a column-stochastic matrix. Then [dez S 22.
The constant |der la = maxe/Der (0, = max - llog 2 E te.j). The invertibility of T guar- antees Σ5=1 te is positive and hence the finiteness of Aerlo However, we have a "bad" T. E5=1 fe.5 could be arbitrarily close to leading to a large PAerlo
Following Theorem 1 if the function class G has a universal approximation property, such as an RKHS associated to a universal kernel, or an MLP with increasing number of nodes, consistency for LMNTM via (regularized) minimization of Rg) can be shown by leveraging standard techniques, provided N - do (bag size may remain bounded). Then the excess risk bound in Theorem 7 would automatically imply consistency with respect to 0-1 loss.
5
The LLPFC algorithms
In this section, we define a probabilistic model for LLP, show how LLP reduces to LMNTM, and introduce algorithms that refer the LLPFC algorithms.
5.1 Probabilistic Model for LLP
Given a measure P on the space X' x V. let (P c E y} denote the class-conditional distributions of X, i.e., events C X. (A( = P(A (a(1)....., .CC)) the clean prior. Assume Vc E V. ((()) * O. Given 2 = ((1)....,,(()),,, E C let Pz be the probability measure on X' y s.t. events C X, Vi V. PA = Thus P; has the same class-conditional distributions as P but a variable prior z.
= c). Let (c) P(Y = c). Vc y and call o
We first define model for single bag. Given = A
say that bag b is governed by 2 E C if b is a collection of feature vectors {X, :j E N b annotated by label proportion = ( (())..... ,(C)), where [b] denotes the cardinality of the bag, each X, is paired with
an unobserved label Y s.t. (X,, Yj) dtd P., and &(c) = 1 E 1ly, Note E,, [2] = 2 and
1b] P. P. c) =(c). We think of as the true label proportion and é as the empirical label proportion.

---

The gray triangle represents the probability simplex A The squares represent T/, 72, and 73- The cross is σ. The temarr graph on the left visualizes an example where Assumption [3] holds. The one on the right visualizes example where Assumption 13 fails.
Figure 1:
Using this model for individual bags, we now formally state model for LLP. Given bags {bk): let each by be governed by Each by is a collection of feature vectors {X j E Nb., where (XH, 1 i.d. P72 and YI is unknown. Further assume the X independent for all is and j. In practice, 7 is unknown and observe 9n with (x(c) To Σ Iul lyp=c instead. The goal is learn an f that minimizes the risk RI, P(xx)) Y) where the 0-1 loss, given access to the training data {(b).
5.2 The Case of C Bags: Reduction to LLN
To explain our reduction of LLP to LLN, we first consider the case of exactly C' bags b1, be, bc. governed by respective (unobserved) m..... "O A and annotated with label proportions ..... .c.. Define r E RCxC by I(i.j) = (j). and let I denote the transpose of I. Re- call that a is the class prior associated to P. To model LLP with C bags as an LLN problem, we make the following assumption on and a:
Assumption 13. 3 unique a Å C s.t. I
Assumption is equivalent to: (?...... is linearly independent set and a is in the interior of the convex hull of (?,,..., ). Ternary plots in Figure
We write a
5.2
visualize examples where assumption 13 holds and fails when C 3. Intuitively, assumption
13 is more likely to hold when (7: E Ne) are more "spread out" in A in which case it is more
likely for a to reside in the convex hull of (7 : Nc).
To reduce LLP with C' bags LLN, we simply propose assign the "noisy label" y i to all elements of bag b; and to construct a noise transition matrix T with T(i.j) ( Assumption 13 ensures T is indeed a column-stochasee
matrix. Thus, the probability measure Pr on X' y x satisfies axii) = (r = and (-) = (r =), i), which further implies (c)) = Py = c i). We confirm these facts Section E in the appendix. Such construction transforms LLP with C bags into LLN with estimable noise transition matrix T. Each element of bag then be viewed from Pap. After assigning the noisy labels, we have dataset U ( c) : E N p along with the noise transition matrix T. This allows us to leverage the forward correction loss er to minimize the objective Rey. (f) = (r,((r(((X),))) which can be estimated by the empirical risk
triplet (X, YY), with Y unobserved, such that (X, Y) is drawn
a(e)
Σ) bel
Jocl (X(())).
[b.
5.3 The General Case: Reduction to LMNTM
More generally, consider LLP with NC bags, N E N. We propose to randomly partition the bags into N groups, each with C' bags indexed from 1 to C. Let kū denote the index of the e-th bag in the i-th group. Thus, bR is the e-th bag in the i-th group and is governed by "A,,e- For i Nv. define the matrix I, E CCC by Pa(c), 02) = =kk.e, (c2), Ve,, C2 E y. We make the following assumption on the T,'s and o:
Assumption 14. For each i Ny. unique a; E A s.t. I aT =0
Thus, every group can be modeled as above as an LLN problem with noise transition matrix T. where Ti(ci, (2) Th.., (c2)a;(c) (c2). Data points in the bag assigned with noisy label in the i-th group be viewed as drawn i.i.d. from the class conditional distribution (-.(- cc. This
7

---

Algorithm LLPFC-ideal
1: Input: {(bb: [b]k: NC and E A where
5:
at 1-r;"0 0
bk = { ; Nbbl
6:
for c1 = =1:0,00 02 do
2: Randomly partition the bags into groups
7:
Ti(r, 02) t Th.. (o))a((()/((()))
3: for i= s.t. G₁
[G:)==
N
{bkk.. Thi,e) : c y}
8:
end for
do
9:
end for
10: Train ff with the empirical objective |
4: r < 17 7 Met
Algorithm 2 L.LPFC-unffrm
1: Input: {bbb ;x) NC and E AN where
Tx)]km
6: (c(c) + lbn, 1/, for each c == 1:
by = {X j E NEzl]-
à; + fTr
2: Partition the bags as step in Algorithm
8: for C1 = = 1
3: for 1: N do
9: Ti(c,, 02) t Mhi (02)a((c1)/0((0))
4: r -- [9 92, 10
10: end for
5: n4 Σ [kkee
11: end for
12: Train with Ei, Wi Ej (x(xf((
problem now maps directly LMNTM described in Section and satisfies the associated performance guarantees. In the next subsection, we spell out the associated algorithm.
5.4 Algorithms
As above, assume we have NC bags where N. Let each bag by governed by " E A and be annotated by label proportion Ai- We first present the LLPFC-ideal algorithm in ideal setting where a, the " 's and the a; are known precisely and Assumption 14Jhold. We then present the real-world adaptations LLPFC-uniform and LLPFC-approx in practical settings.
The L.PPFCideel algorithm presented Algorithm | We follow the idea in section 5.3 to partition the bags into N groups of C' bags, and model each group as an LLN problem. In Algorithm T we assume ? and a are known and Assumption [4 holds. The theoretical analysis in Section immediately applicable to the LLPFC-ideal algorithm. We partition the bags by uniformly randomly partitioning the set of indices NN into disjoint subsets (ki,e c V) NN, where kg.c denotes the index the c-th bag in the i-th group. We denote the inverse transpose of T, by Tr"
In practice, when 7% is unknown, we replace with 7 as plug-in method. Hence, we work with NNC Ibalf and r; = [f,,, ; STNC [be]
instead of a and I in Algorithm respectively. Here the label proportion of all training data points and we use as an estimate of the clean prior a. Likewise, a; = - in Algorithm should be replaced with à; p- and we would like to use f,, 5, and å; to calculate T; as an estimate of T,. For this to make sense, we need &; = f--r Åç, which equivalent to being in the interior of the convex hull of (fk, c for all However, this may not be the case in practice. Thus, we consider two
Algorithm 3 LLLPFC-appros
1: Input: {bb, Ne and w E A where
6:
à; + arg aigm ||l p
by {x] E Nba1]-
7:
ô; + f &
2: ④ + ΣNS balfe
8:
for C1 = =1 =
EAS lbal
9:
TT 02) t fihl (2))
3: Partition the bags as step in Algorithm I
10: end for
4: for 1: N do
11: end for
5: r - P T........ kkk
12: Train with Σ.e
w(a((e) Inncel
(f(((((X

---

heuristics to estimate T, as real-world adaptations of the LLPFC-ideal algorithm. The first, called LLPFC-uniform. is presented in Algorithm 2 which sets &, by counting the occurrences of the noisy labels. This is motivated by our model wherein is the noisy class prior for the i-th group. The second, called LLPFCC-pprox, is presented in Algorithm S and sets (; to be the solution of arg me ||ō f'
- It should be noted that both practical algorithms, we use a different o; as an estimate of a for each group, to ensure that each T, is column-stochastie matrix. In experiments where we have NC + k number of bags with 0 < k < C, we can randomly resample NC number of bags and regroup them in every few epochs. Both real-world adaptations perform reasonably well in experiments.
Experiments
We compare against three previous works that have studied LLP applying deep learning to image
Table 1: Test Accuracy for Wide ResNet-16-44
Method
32
256
512
1024
2048
KL
4255
1.3
.617
1 .6
.5346 1.11
.3749
- 1.14
2938 1 004
Out of RAM
Out RAM
CIFARIO
ILPVAT
.911
-5137
-22
4423
Out RAM
Out
RAM
LLPFC uniform
79266 1. .01
.7683
.02
.7999
022
.7881
.01
.7244 1. 1.01
.7182 1. .01
6925 1 .03
I.PPFC-approx
.7404
.00
.7409 .02
.283
KL
2465 10
.1122 = 07
1022 + 03
.1244
1039
= 04
Out of RAM
Out RAM RAM
SVHN
I.PVAT
.2755
.1988
.1294
04
RAM
Out
LLPFC-uniform
9012 + .02
.885 + .02
8760 02
8736
01
8681 = 02
.709 + 02
8717 + .01
IpPrFo-approx
8844
022
8808
.01
8771
.02
8738
KL
8413 1 .4
8637 1 .04
9111
.361
.12
.0845 1 .01
.0826
Of RAM
EMNIST
LLPFC-uniform
LLPVAT
8254 - 044
9165
+ .01
.9455 + 02
.060
= .01
.9366
9015
01
5071
8790
= .99
.03
0859 = .01
8886
02
Out RAM
8461 05
Out of RAM
.8817 = .01
LLPFC-approx
.092 = 01
.9744
.01
.0655 .00
.9933
= .01
.948 = .00
8969 + .01
.9077 =
Table 2: Test Accuracy for ResNet18
Methed
1024
2048
KL.
7837 .01
.7565
.01
6918 1 011
6106 1. 04
.5866 1 .05
3197
1 044
4576
.03
CIFARIO
ELPVAT
.7907
.3499
.5670
.8811
.6244
LLPFC-uniform
.600 .001
.310
01
5867
5603
+ 01
.5670
+ 01
5623
- 01
5288 = .03
.6567 :.01
.616
01
5997
5931 + 02
.6062 -
.6169 - .01
.5591 = .04
KL.
.129
0716
01
3042 .30
11026 1. 04
.2499 1 24
3123
1 .99
.2977
.12
SVHN
ILPVAT
.179 + +.06
.1999
.27
6962
.3673
.003 + .31
3999 + .33
.3736
24
LLLFC-uniform
8823 001
8644
01
8433
8390
.360 +
8086 +
8188
.11
LLPFC-apprex
.8244 +: .01
.662
= .01
.870
: .01
.8433 + 01
.8492 - .01
.848 - .01
.8534 = .01
KL
9319 +
9295
00
.306
9269
.9677
9239
9106
EMNIST
L.LPFC-unifomm
LLPVAT
.914
.9008 1: .00
+
.9999
8954
.00
00
8744
9299
1 000
9281
8600
1: .00
.8448
.9488 1 00
8388
9222
1 .00
01
.9128 + .00
8045 +
LLPFC-approx
9146 0.00
8998
00
.874
# 00
8764
00
8670 = 00
8736 - 01
8660 = .01
Table 3: Test Accuracy for VGG16
Data set
Method
32
64
128
256
312
1024
2048
KL
21131.11
.1794 1:
.1160
002
.1117
1049
CIFARIO
LLPFC-anifonm
ILPVAT
.7602 +
4634 1 .07
.7372
.293
1: .03
.7300
.139
:: .03
.01
.7226
.145
+: 002
.01
.7136
.1172
: 002
.7111
.1889
00
Of RAM
.7033
L.PFC approx
.7566 1: .00
.7310
1 .01
.7003
+: 00
.7004
.6870
à .03
.6857
002
.6645 + .03
KL
1277 1: .06
0893
.04
.1054 :: .05
.1024
1: 00
.1104
1 04
.0885
1372 03
SVHN
LLPVAT
1117 1.
.0736
11.11
.1051
1 .05
.1023
1. .66
.1125
1 04
.1061
.05
Out of RAM
LLPFC-unifom
4177
1115
.4708
23
.5402
: .21
.1734
1 .11
.4249
: .30
.5691
.6869 .13
LLPFC approx
.2999
.28
.4994
.23
.1091
.04
.1188
1. .05
.1903
.14
.4097
.429 .18
KL.
5952 4:45
2348
4:22
0974
=.01
0842
0.02
.0702
=.01
0692
F:01
1197 4.02
EMNIST
LLPFC-umifom
LLPVAT
.9111 .00
8593 11
.3329
9279
+ .00
.9588
.1042
= .00
.9242
.0833
- .00
022
.9399
.0696
= .00
.01
.9333
.0711
.00
.9220 :: .00
RAM
approx
9910
.9499
.9240
.00
Table 4: Test Accuracy for LLPGAN architecture
Data
Method
32
64
128
256
512
1024
2048
LLPGAN
.630 +
.313 = 02
.3328 00
.3363
.3400 + .03
2824 + 05
.236 + 088
CIFARIO
LLPFC-uniform
6145 +
.5226
5565
5452
.5511
.20
5358 + 01
5438 .03
Capprox
.6169 1 .01
.5875 = .01
.542 1 .02
.5877 + 002
.5621 - .03
.5100 : .01
.5567 = .02
LLPGAN
2378
24
7680
.1725
.1382 .01
SVHN
8800 + .00
8581
+ .01
8480 + .01
8393 + 01
8347 + .01
8258 + 01
8127 + 001
LLPFC-approx
.8799 + .8199
.7061 + .843
.8423
.8366 - .01
.8527 = .01
data: Dulac-Arnodd et al. study the KL loss described in the introduction, and a novel loss
Code is available at htttttt:://gttiii wwtp:///wmo/mmmaa//iiiiii///

---

based on optimal transport. They find that KL performs just as well as the novel loss. Liu et al. [22] employ the KL loss within a generative adversarial framework (LLPGAN). Tsai and Lin [46] propose augmenting the KL. loss with a regularizer from semi semi-supervised learning and show improved performance (LLPVAT). We compare both L.LPFC-uniform and I.LPPC-approx against the KI. loss, LLPGAN, and LLPVAT to clearly establish which empirical objective is better. Recent papers on multiclass LLP for which code is not available were not included [23 16).
We generate bags with fixed, equal sizes in {32, 64, 128, 256, 512, 1024, 2048}. J. To generate each bag, we first sample label proportion y from the uniform distribution on A Then we sample data points from benchmark dataset without replacement using multinomial distribution with parameter y. It should be noted that Tsai and Lin [4)] Dulac-Amoll by shuffling all data points and making every B data points a bag where B is fixed bag size. Their method is equivalent to sampling data points without replacement using a multinomial distribution with fixed parameter
al. (9. and Liu et al. [22] generate bags
{ C C..... č As noted by Scott and Zhang (39), this leads to bags
1)
with very similar label proportions which makes the learning task much more challenging.
We repeat each experiment 5 times and report the mean test accuracy and standard deviation. All models are trained on a single Nvidia Tesla 100 GPU with 16GB RAM. In our implementation of LLPFC algorithms, the weight w is set to be (N 1 #) E A and our choice of the proper composite loss is the cross-entropy loss.
For the comparison against KL and LLPVAT, we perform experiments on three benchmark image datasets: the "letter" split of EMNIST 6 SVHN 29 and CIFARIO 17 To show that our approach is robust to the choice of architecture, we experiment with three different networks: Wide ResNet- 1644 (52) ResNet18 . and VGG16 42 We train these networks with the parameters suggested in the original papers. The test accuracies are reported in Tables I 2 and Since convergence in the GAN framework sensitive to the choice of architecture and hy hyperparameters. we compare LLPFC against LLPGAN using the architecture proposed in the original paper along the
with the hyperparameters suggested in their code It should be noted that for LLPFC we only discriminator for classification and did not use the generator to augment data. Since Liu et al. [2] only provide hyperparameters for colored images, we perform experiments on SVHN and CIFARIO only. The test accuracies are reported in Table
LLPFCCuniform and LLPFC-approx substantially outperform the competitors in clear majority of settings. The experiment results clearly establish our methods as the state-of-the-ar by a substantial margin. All three competitors perform gradient descent with minibatches of bags and the GPU times runs out of memory when the bag size is large. Our implementation, which also uses stochastic optimization, does not suffer from this phenomenon. Full experimental details are in the appendix.
7 Conclusions and Future Work
We propose theoretically supported approach to LLP by reducing it to learning with label noise and using the forward correction (FC) loss. An excess risk bound and generalization error analysis are established. Our approach outperforms leading existing methods in deep learning scenarios across multiple datasets and architectures. A limitation of our approach is that the theory makes an assumption that may not be verifiable in practice. Future research directions include optimizing the grouping of bags and adapting LLPFC to other objectives beyond accuracy.
Acknowledgement The authors were supported in part by the National Science Foundation under awards 1838179 and 2008074, and by the Department of Defense, Defense Threat Reduction Agency under award HDTRA1-22 200-2-0000..
10


Reviews:
[{"review_id": "Vs_cdfvt7y", "reviewer": "Reviewer_djWm", "summary": "Multi-class label proportion learning (LLP) is a weakly supervised learning problem that aims at obtaining a multi-class classifier with only bags (each bag is a collection of data points) and the proportions of different classes contained in the bags. In this paper, it is shown that the problem of label proportion learning can be solved efficiently with the techniques in the field of noisy label learning (LLN). The authors first give the consistency results on the Forward Correction (FC) technique, which is one of the prevailing methods in the field of  LLN, and then extend it to enable the use of multiple transition matrices. Under some mild assumptions, the authors show that the problem of LLP can be solved with the proposed extension of FC. Experiments on benchmark datasets are conducted to show the efficiency of the proposed method.", "questions": "There can be quite a number of assignments of labels w.r.t. different bags and thus the construction of transition matrices can be flexible. For example, in the scenario mentioned in Section 5.2, there can be C! different assignments. If there exists an optimal assignment of pseudo noisy labels?", "limitations": "The authors have addressed the limitation of assumptions made in Section 5.1.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. A novel extension of FC technique is proposed that removes the limitation on the number of transition matrices.\n\n2. A clear connection between LLP and LLN is constructed with a strategy of converting label proportion to noisy labels and noise-transition matrices. With this conversion, the problem of multi-class LLP can be solved with consistency guarantee.\n\n3. Rigorous theoretical analyses are conducted to support all the claims made in this paper. The provided generalization error bound well depicts factors that have influence on the proposed method.\n\nWeaknesses:\n\nThe presentation of this paper should be improved for better readability. LLPFC, the main result of this paper, appears in the latter part of this paper, which makes the key point of this paper ambiguous. I think this problem can be mitigated by exchanging the order of Section 4.3 and Section 5.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JwK1obfIOst", "reviewer": "Reviewer_tEEw", "summary": "-This paper considers a conventional weakly supervised learning problem called learning from label proportions, where the training data are given in the form of bags and the proportions of each class within each bag are also given; the goal is to train a classifier predicting instance labels from such bag data. To solve the problem, they partition the bags into groups and model each group as a standard label noise problem. Next, they apply the forward correction loss, which was proposed for dealing with class-conditional label noise, to each group and study the generalization error bound of the proposed method. They also conduct some experiments to verify the effectiveness of the proposed method on some benchmark datasets.\n", "questions": "-The proposed method randomly partitions the given bags into groups and then formulates the problem of learning with multiple noise transition matrices. This random partition step seems problematic to me. As different partitions may lead to different noise transition matrices, which determine the difficulty of each LLN problem and will significantly affect the performance of the learned classifier. In Scott and Zhang 2020, they have discussed that the optimal pairing of bags can be obtained by solving an integer programming problem. In the current paper, could the authors provide similar analysis on the optimal partition strategy?\n\n-In theorem 7, the weights w_i are expected to reweight noiser or larger subsets of data differently. But it is still unclear to me how to choose them in practice.\n\n-In Section 5.3, the authors discuss a general case of LLP with NC bags. What if we are given m bags and m is not divisible by C? How to deal with such a general case in the current learning framework?\n", "limitations": "-The paper has some unclear parts that need to be carefully modified, and the organization of the paper can be improved.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "pros:\n\n-The paper studies the problem of learning from label proportions in a theoretically grounded way. They provide calibration analysis of the forward correction loss and then apply it to their problem setting. They also derive the generalization error bound of the proposed method under some assumptions.\n\ncons:\n\n-The title of the paper is a bit misleading, as the problem settings of learning from label proportions (LLP) and learning with label noise (LLN) are not mutually exclusive. To be specific, both of them can be seen as learning from corrupted distributions, where the class-conditional densities p(x/y) are corrupted in the former setting (LLP), while the class posterior probabilities p(y/x) are corrupted in the latter setting (LLN). In the binary case, the former is also called mutually contaminated (MC) learning, and the latter is also called class-conditional label noise (CCN) learning. It is proved that CCN is a special case of MC, see sections 2.2-2.3 in the following paper for details:\n\nMenon et al. \"Learning from corrupted binary labels via class-probability estimation.\" International conference on machine learning. PMLR, 2015.\n\nTherefore, my feeling is that, in a general viewpoint, LLP can also be seen as a kind of label noise problem, and the title may cause some confusion that how to solve one label noise problem by another label noise problem.\n\n\n-The writing of the paper is unclear and some parts are hard to follow. For example, in lines 40-42, the authors claim that Patrini et al. 2017 proposed forward correction loss to remedy the backward correction loss since it is poorly suited for multi-class deep learning settings; however, in the original Patrini et al. 2017 paper, they seem only mention that forward correction is an alternative method that corrects the model predictions (see Section 4.2 in Patrini et al. 2017 paper), without any discussions on how it remedies the backward correction. Also in lines 50-52, it seems that the mutual contamination model is not that different from the noise transition matrix used in this paper, which can be seen as a 2 by 2 noise matrix corrupting the class-conditionals.\n\n-Some sections seem incomplete. Especially for the algorithm section, how to estimate the noise matrix is an important step for the proposed method, but the details of these steps are not included in the main paper. And there are no experimental results provided in the main paper. I strongly recommend simplifying section 4.3, as the definitions are mainly borrowed from existing papers and may be moved to the appendix, and using the saved space for discussing the noise matrix estimation algorithm and reporting experimental results.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IVHRuOmBU-X", "reviewer": "Reviewer_vSZS", "summary": "The paper investigates multiclass learning from label proportions, i.e. the situation in which the training data is only available in \"bags\". For each bag, the fraction of samples belonging to a certain class is known, but the exact assignment of instances to classes is not. The idea is to assign an arbitrary label to each instance in a bag, and then consider the bag to be a noisy learning problem with known transition matrix. For learning with noisy labels, they employ the forward-correction approach, proving new calibration-style generalization bounds for this, and then extending these to the multiple-noise matrix (i.e. multiple bags -- learning from label proportions case).", "questions": "In equation (1), shouldn't $\\alpha_i(c)$ also be an empirical/estimated quantity?\n\nl. 713 How de we know $A(\\epsilon)$ is the closed interval, as opposed to being open?\n\nProof of Thm. 17\nWhere does the first line, $\\mathcal{C}_2 < \\delta(\\mathcal{C}_1) \\implies \\ldots $, come from? \n\nLemma 22 should require that the matrix be invertible, I think.", "limitations": "Not a limitation per se, but as far as I can see this work leaves open quite trivial imporvements of the proposed algorithm, i.e. choosing the labels that are assigned to the bags in a way that minimizes the amount of noise that needs to be assumed. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While the idea of interpreting learning from label proportions as a noisy-label-learning problem is not original to this paper, the multiclass application and use of forward-correction instead of unbiased loss functions constitute a non-trivial step over the existing literature. I agree with the authors that the additional results for forward correction may be of independent interest, though whether people working on noisy-label-learning will find these results in this paper I don't know. Maybe these results should, in addition to being stated here, be presented at some workshop or similar.\n\nOverall, I found the paper to be well written and easy enough to follow in the main argument. In terms of notation, maybe this could be improved a bit, e.g. the symbol $\\gamma_{k_{i, c_1}}$ has 3(!!) levels of subscripts. Similarly, the acronyms can get rather long:\nLLPFC-..., LLPGAN, LLPVAT, LMNTM. None of these are actually pronouncable. Given that the context of the paper is LLP, I think it would be enough to mark the algorithms as FC-..., GAN, VAT, for example. \n\nSo far, I've only gone through the math in appendices C1 and C2. Aside from the comments below, this looks good. I will update the review once I've managed to go through the rest of the proofs. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2HVIVaFLBs7", "reviewer": "Reviewer_SBPr", "summary": "The paper focused on learning from label proportions (LLP) task. First, they show that background theory of forward correction loss in learning with label noise (LLN), and extend the results with multiple noise transition matrices. Next, they propose LLPFC algorithm with probabilistic model for reducing LLP to LLN with multiple noise transition matrices.", "questions": "- It would be nice to provide the explanation of the experiment results and what they support.\n- Is it easy to estimate the clean prior $\\sigma(c)$?\n- Are Assumption 13 and 14 empirically reasonable in LLP?\n", "limitations": "They addressed the limitations in the paper.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- The connection between LLP and LLN is reasonable and novel.\n- They provide theoretical analysis and this would be useful for both LLN and LLP community.\n\n### Weaknesses\n\n- Lack of the experiment results\n  - The paper did not provide any empirical results in the main paper.\n  - Also, there are no/few explanation of the main experiment results in both main and supplementary paper.\n- Gap of theory and practice\n  - The theoretical analysis has many assumptions, but they did not give theoretical or empirical explanations to show that the assumption is reasonable in practice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept