Algorithms and Hardness for Learning Linear Thresholds from Label Proportions
Authors: Rishi Saket
Venue: NeurIPS 2022 Accept (2022)
Keywords: learning from label proportions
linear thresholds
algorithm
hardness

Abstract: We study the learnability of linear threshold functions (LTFs) in the learning from label proportions (LLP) framework. In this, the feature-vector classifier is learnt from bags of feature-vectors and their corresponding observed label proportions which are satisfied by (i.e., consistent with) some unknown LTF. This problem has been investigated in recent work (Saket21)  which gave an algorithm to produce an LTF that satisfies at least $(2/5)$-fraction of a satisfiable collection of bags, each of size $\leq 2$, by solving and rounding a natural SDP relaxation. However, this SDP relaxation is specific to at most $2$-sized bags and does not apply to bags of larger size. 
    
In this work we provide a fairly non-trivial SDP relaxation of a  non-quadratic formulation for bags of size $3$. We analyze its rounding procedure using novel matrix decomposition techniques to obtain an algorithm which outputs an LTF satisfying at least $(1/12)$-fraction of the bags of size $\leq 3$. We also apply our techniques to bags of size $q \geq 4$ to provide a $\Omega\left(1/q\right)$-approximation guarantee for a weaker notion of satisfiability. We include comparative experiments on simulated data demonstrating the applicability of our algorithmic techniques.
    
From the complexity side we provide a hardness reduction to produce instances with bags of any constant size $q$. Our reduction proves the NP-hardness of satisfying  more than $({1}/{q}) + o(1)$ fraction of a satisfiable collection of such bags using as hypothesis any function of constantly many LTFs, showing thereby that the problem is harder to approximate as the bag size $q$ increases. Using a strengthened analysis, for $q=2$ we obtain a $({4}/{9}) +o(1)$ hardness factor for this problem, improving upon the $({1}/{2}) + o(1)$ factor shown by Saket21.


Algorithms and Hardness for Learning Linear Thresholds from Label Proportions
Rishi Saket
Google Research India
rishisakett@goglle.com
Abstract
We study the learnability of linear threshold functions (LTFss in the learning from label proportions (LLP) framework. In this, the feature-vector classifier learnt from bags of nature-vectorr and their corresponding observed label proportions which are satisfied by (i.e., consistent with) some unknown LTF. This problem has been investigated in recent work ([37)) which gave an algorithm to produce an LTF that satisfies at least (2/5)- (2/b)-fraction of a satisfiable collection of bags, each of size < by solving and rounding natural SDP relaxation. However, this SDP relaxation is specific to at most 2-sized bags and does not apply to bags of larger size.
this work we provide a fairly non-trivial SDP relaxation of a non-quadratic formulation for bags of size 3. We analyze its rounding procedure using novel matrix decomposition techniques to obtain an algorithm which outputs an LTF satisfying at least (1/12)-fraction of the bags of size < 3. We also apply our techniques to bags of size q 2 to provide a (pa)oxappooi guarantee for weaker notion of satisfiability. We include comparative experiments simulated data demonstrating the applicability of our algorithmic techniques.
From the complexity side we provide a hardness reduction to produce instances with bags of any constant size q. Our reduction proves the NP-hardness of satisfying more than (2/) + o(1) fraction of a satisfiable collection of such bags using as hypothesis any function of constantly many LTFs, showing thereby that the problem is harder to approximate as the bag size increases. Using strengthened analysis, for 2 obtain (+/9) + o(1) hardness factor for this problem, improving upon the (1/2) + o(1) factor shown by [37].
Introduction
Our work studies the computational learnability of linear threshold functions (LTFs) in the learning from label proportions (LLP) framework, which is a generalization of traditional supervised learning. In this, bag B is a set of some (say q) feature vectors {x]... ,.....,. X2y with corresponding {0, 1 llabell proportion Ø [o, 1] implying that exactly qoB out of the q feature-vectors have as their true label. Given a collection (or distribution) of (B, (B) consistent with an unknown classifier, in LLP the goal to fit a feature-vector level classifier hypothesis that matches the bag label proportions as closely as possible. One way to formalize this is by defining that hypothesis classifier satisfies bag (B, BB iff its predicted label proportion equals B, with the goal being to maximize the number of bags satisfied by the hypothesis. This notion of satisfiability boils down to supervised learning when all bags are of size 1, and a reasonable measure of classifier performance small bags.
An LTF over d-dimensional feature-vectors x is given by pxs(g(x)) for some linear function g(Z1...., ) Σd - C + Ca+1, where pos(2) 1 ((200)- Recently, [37] studied the proper LLP learnability LTFs i., given a collection of bags and their label proportions consistent with an
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

unknown LTF, compute an LTF satisfying the maximum number of bags. It is well known ([7) that in supervised learning (all bags of size 1) LTFs are learnable by LTFs (i.e., all bags can be satisfied) using linear programming. This however does not work for bags sizes >> 1, and neither are random LTFFs guaranteed to satisfy any significant fraction of the bags. The work of [37] studied this problem when all bags are of size I 2, giving an algorithm that satisfies at least (2/5)- -fractionn of all the bags, and - if all bags are monochoccciiiiiicccc i.e., OB & {0, 1 for all bags B. From the hardness side [37] showed that even on satisfiable instances where all bags are non-monochromatic of size 2, it is NP-hard to find an LTF satisfying more that (1/2) + (1) fraction of them.
The main algorithmic technique of [37] is based on the observation that the label proportion of a bag x2)
B {2) determines the sign of g(x1) (x22) where pos(g) satisfying LTF with non-zero margin i.e. (xx)) gx()) # O. Thus, one can write a collection of quadratic constraints over the coefficients of g. The corresponding semi-definite programming (SDP) relaxation can then be rounded using random hyperplanes to obtain the desired LTF.
However, the above approach is not directly applicable even for bags B B- X2, of size since their label proportions no longer determine the products g(x. (x.))((()) (1 iisisss 3). Therefore, the following question remained: there an efficient algorithm which given a collection of (B, σB) s.s. [B] S 3 consistent with some LTF, computes an LTF that satisfies al least (21)-fraction of the bags.
Our work answers the above question in the affirmative, using fairly non-trivial SDP relaxation and new techniques to analyze the rounding algorithm. In particular, we show that allowed the presence of certain boolean variables the problem admits a non-quadratic formulation which nevertheless can be relaxed to an SDP. For further analysis we prove a novel characterization of the condition A > B for two symmetric positive semi-definite (psd) matrices A and B in terms of their decomposition. Our algorithm provides an LTF satisfying at least (1/12)-fraction of the bags of size S 3. For bags of sizes 2 4, we adapt this approach to provide a (rtt/)/aaprooimatiion for weaker notion of bag satisfiability which is the same as satisfiability for monochromatic bags, but only requires splitting the non-monochromatic bags.
We also show hardness reduction to this problem for bags of any constant size q 2 2. Unlike the reduction of [37], ours produces mixture of mo-noormoooteic and monochromatic bags, and for general hag sizes E Z it yields a (1/n) + (1) hardness factor for any boolean function of constantly many LTFs as hypothesis, providing evidence that the problem becomes harder as the bag size q increases. For the specific case of = 2 we obtain a hardness factor of (+/9) + o(1) improving on the (4/2) + o(1) bound of [37].
An overview of our algorithms, hardness result and their analysis is provided later in this section.
1.1 Previous Related Work
The study of LLP is motivated by applications in which only the aggregated labels for sets (bags) of feature vectors are available due to privacy or legal [35, 40J constraints or inadequate or costly supervision [13, 11]. LLP has been applied to several weakly supervised tasks, for e.g. IVF prediction [23] and image classification [8, 30J. Notably, small bag sizes- studied in this work arise in real-world scenarios, e.g. [30] consider bags of size 50, and bag sizes 10 20 are relevant for IVF applications (see Sec 1.2 of [4]).
There have been several works works applying variety of techniques e.g. MCMC, clustering, linear classifiers, variants of SVM ([12, 22, 29, 35, 41], others ([33, 32, 39, 38) provided guarantees under distributional assumptions, while recent works [26, 15, 27] have proposed deep neural net based methods. There methods typically attempt to fit an ML model to a collection of bags and their label proportions by minimizing some loss between the label-proportions and the average model predictions, summed over all the bags. However, while being practically applicable, they do not provide any non-trivial worst case performance guarantees, even for learning LTF' in the LLP setting.
In contrast to the above, the study of computational learning in the LLP framework has been apart from the work of [37] fairly sparse. The LLP framework (as an analogue of PAC learning) was first formalized in the work of [42]. They bounded the generalization error of a trained classifier when taking the (bag, label- proportoooo -pairss instances sampled iid from some distribution. Their loss
It is easy to see that the non-zero margin property can be assumed for a finite set of linearly separable points (see Lemma 2.1 of [37])
2

---

function was different weaker notion than the strict bag satisfaction predicate that [37] and our work use.
As mentioned, LTFFs [7] are well known to be properly learnable without any distributional as- sumptions. In the presence of adversarial label noise however the problem is NP-hard to approximate [l, 5, 10J with the optimal (4/2 + e)-factor hardness shown by [16, 20], and generalized by [6] to hold even for constant degree polynomial thresholds as hypotheses.
1.2 Problem Definition
For an integer q. an instance of LLP-LTF((g) consists of (Xt B = (Bt) (=)))=) where fxi...., X,, S I is set of feature-vectors. and B = { [B..... Bm] S 2 s.t. [By] S is a collection of bags each of size most q. For each bag Bg there is number Ye which is the sum of the {0, J-labells of the vectors in the bag, satisfying t E (0..... |Be]), with the label proportion given by 02 re/|Bel When og {0, 1} then Bg is said to be monochromatic i.e., hags which have same label (either 0 or 1) for all their feature-vectors. The remaining bags B₁ necessarily of size are called non--monochromatic..
bag Be E B is satisfied by some F X if (ExEB, F(x)) - = oel Bel. We say that a bag is split by F if (ExEB, F(x)) E {1,.... |Bel - 1}. while it is unsplit by F if the latter assigns the same label to all the vectors in the bag. We say that a bag Bg weakly satisfied by F if (i) B is monochromatic and is satisfied by F, or (ii) B is con-monochromatic and is split by F. Note that weak satisfiability implied by satisfiability.
An instance of LLP-LTF(gg q] is said to be satisfiable if there exists an LTF that satisfies all the bags. It said be weakly satisfiable the LTF weakly satisfies all the bags. The goal is to find an LTF that (weakly) satisfies the most bags.
Choice of objective. The satisfiability condition is natural generalization of the "classification" objective in supervised learning in which a (0, J-labelld example is either classified correctly or incorrectly. For small-sized bags, it is also reasonable approximation to objectives based on the deviation of (Exe B. f(x)) from "t. More importantly, as we shall see later in this paper, the satisfiability objective allows for a compact and tractable SDP relaxation in which any feasible
solution can be rounded to an LTF with (in expectation) a non-trivial approximation guarantee.
1.3 Our Results
Our algorithmic result for satisfiable LLP-LTF(33 is as follows.
Theorem 1.1. Let be a satisfiable LLP-LTF(3] instance with m bags partitioned into mo monochro- matic bags of size < 2, my non-monochromatic bags of size 2, m2 monochromatic bags of bags of size 3, and ma mon-oooochoomatic bags of size 3. Then, there nomial time algorithu which on input 'J produces and LTF that satisfies in expectation at least ((ma/2 + m²244 + ma/s)) /2 =m1/2) bags. In the worst case, (if m = ma) the algorithm satisfies in expectation at least (1/12)-fraction of the bags.
randomized poly-
The following theorem states our hardness result for satisfiable LLP-LTF(gg) [[]] and the improved hardness for satisfiable LLP-LTF(22..
Theorem 1.2. For any E Z- and constant Ç > is NP-hard to find any boolean valued falueefunction function of E LTFs that satisfies more than (1/4+ {)-fraction of the bags of satisfiable LLP-LTF(gg instance. For q = 2 in particular, a strengthened result holds with a hardness factor of (4/9 C)-
We also provide the following algorithm for weakly- bags of weakly-satisfiable LLP- LTF(g] instance for any q E =
Theorem 1.3. Let I be a
LLP-LTF(gg instance with m bags. Then, there is randomized polynomial time algorithm which on input produces an LTF that weakly- seatsy-satisfies in expectation at least (com/y) bags for some absolute constant co > 0.
3

---

1.4 Overview of the Algorithm
First, observe that the non monochromatic bags that make the LLP-LTF problem difficult, as one can simply use linear programming to find an LTF satisfying all the monochromatic bags. This LTF may however not satisfy even a single non-monochromatic bag.
Let us first see how the algorithm of [37] for satisfiable LLP-LTF[2] proceeds. Since we can always append coordinate with all feature vectors, assume that the satisfying LTF is given by pos( (r, x)) (where r is the normal vector of the separating hyperplane) with non-zero margin, the latter is possible by perturbing the LTF if necessary. For bag B {x1,X), X2). (r. x1)(x,r X2) is either positive or negative depending on whether the bag is monochromatic or non-monn monochrooom....c.. There is a straightforward relaxation of this quadratic program an SDP- substitute rr" with a symmetric psd matrix R and replace (r, x1) (r. X2) by x Rxg. Solving this SDP and using the psd decomposition R L L one obtains the same sign pattern for (Lx1, Lx2). Further, the non-zero margin property guarantees [[ = (Lx, Lx) = x Rxx > 0 for all the feature vectors x of the instance. A standard hyperplane rounding of Lx and taking the best of the obtained LTF or its negation yields a random LTF that satisfies non-mon non-monochromatic bags with probability 1/2 and the monochromatic ones with probability 1/4.
Note that the above algorithm erucially hinges on the fact that the label proportion of the 2-sized bag determines the sign of (r, (r, ((rr,,x X2) This clearly is no longer true for a monoooochhooaiicc B = {x1, X2, X3} of size 3. and therefore it doesn't seem possible to write an SDP relaxation with only terms of the form x Rx, and solve for as the relaxation of rr Nevertheless, we observe that at least one of the two products (r, x1) ) (r, xz) (j 2) is negative. Let us define boolean variables 8 {(.f) to be indicator of the event that (r, xx) (r, x,) < O. Then, we have the following valid inequalities:
(1.)) (x) Rx,) 0O A1
3, and Σ 8(J) 21. 2-3,3
Of course, such constraints do not yield an SDP or a convex program due to the presence of the unknown variables (i.j) in products with R.
The key step for obtaining an SDP is to relax s(i.)) R to symmetric psd matrix R ((3) with the constraint R. > R (6.) which is valid since ((1,) (0, 1}. Now, the above constraints can be rewritten as
x TRUdx x 50 Mivsissjs
and
R 7 R. 2=
From the last constraint above, we have x R (1.2 + x ( 2 x Rxi, and assuming x R (12)) 2 xJR (1.3), WLOG we have
(122 2 xx] (+) along with,
x R (1.2
(*+).
The above suggests that the angle between Lx and Lx₃ cannot too small, where L Indeed, suppose for the moment that we could replace the LHS of the first inequality above with (Lx1, z) and the LHS of the second inequality with (Lx2, z) with the guarantee that |z| /22 S |[ A simple calculation shows that the angle between and Lx is most r/3, while the angle between z and Lx is at least 7/2. implying lower bound π 7/6 on the angle between Lx, and Lx2- Thus, random hyperplane rounding will separate Lx, and LXx with probability at least 1/6, and the obtained LTF or its negation will satisfy the bag with probability at least 1/12.
The only question that remains is whether such
assumed above exists. We answer this in the affirmative by proving (in Sec. 2.1) the following: given psd A, 3L s.t. A = L'L, and for any psd B these two conditions are equivalent: (i) A ž B; and (ii) 3C s.t B L and A Z CTC. Moreover, efficiently obtained by the spectral decomposition of A.
For our analysis, letting A R and B R (1.2), can take z Cx1, and the last implication of (ii) yields [[x 1|2 2 2/|2--
This decomposition characterization of A > B for psd A, B seems novel to the best of the authors' knowledge, and may prove useful in other geometric and SDP rounding techniques. It easy to see that (ii) (i). The proof of the other direction is based on specific choice of L which yields the

---

decomposition of B = C. To show A = CTC we invoke a variant of Schur complement positive definiteness condition.
For monochromatic 3-sized bags we use a standard SDP relaxation and random hyperplane rounding analysis. The complete algorithm for LLP-LTF(33 and its analysis provided in Sec. 3. We include in Sec. 5 an experimental validation of our algorithm for LLP-LTF[3] on simulated data, showing that our method outperforms random LIF classifier, especially in the small margin scenarios. In these scenarios, the LTF of our algorithm has high predictive accuracy on instance-level test data, demonstrating the practical applicability of our algorithmic methods.
1.4.1 LLP-LTF(c))
In Appendix G, we extend the above algorithm to weakly satisfy bags of a weakly satisfiable LLP- LTF g] instance for q 4. Such instances also admit analogous analysis for non-monnchromatic bags as above and we obtain (*) and (**) except with a factor of 1/(q 1) instead of 1/2, yielding an 12(1/9) probability for random hyperplane rounding splitting q-sized non-m monochromatic bags. Our techniques are also applicable to the related multiple instance learning (MIL) [8] of LTFs and we include an explanation
Appendix L. Obtaining guarantees for satisfying mon-hooochromatic bags size of q 2 4 seems to require qualitatively stronger geometric techniques and in Appendix H of the supplementary we describe the technical issues in more detail. We also provide in Appendix K similar (to the LLP-LTF(33 experiments) empirical evaluation of our weak-satisfaction algorithm for LLP-LTF(44. Lastly, in Appendix M we discuss how previous works can be used to derive generalizations bounds for satisfying LLP-LTF(gg instances.
1.5 Overview of Hardness for LLP-LTF(4g]
The hardness reduction uses the template of dictatorship test (see Chap. 7 of [31], Sec. 2 of [18)) and combines it with variant of the Label Cover problem [3, 21]. A dictatorship test over a domain [M] produces an instance 3 of the target problem, in our case LLP-LLF [g]. such that (i) (completeness) corresponding to each E [M]] there is an LTF satisfying all bags of J, (ii) (soundness) an LTF that does not have any distinguished (relatively large) coefficients does not satisfy more than some y < fraction of the bags. The crux is to construct dictatorship tests with large completeness vs soundness gap i.c., small 7
Fix any E (1,.....) and consider the following distribution D" on bags of q feature vectors x(",,..,,X" ....),((v) E R each bag with label proportion r/q. First, sample Z E R M x so that each row of Z, is sampled iid uniformly from the set of vectors in {0, 1, 2} which have exactly one coordinate with 2, (r- 1) with and rest O. We derive the vectors X ..... x(1) from Z as follows for each j E [q]: if Zzy is 0 then set x = 0, if Zay is then set x(3) = 6. Independently for each i where Zij 2, set x( w.p. (1- =). set x. 1 w.p. 2/2 and set x, w.p. e/2. Here d is taken to be small depending on M and while e is a small constant depending on but not on [M].
Note that for any there exactly of the q vectors X(1), ...., X have non-zero entries in the äth coordinates. Thus, each coordinate yields an LTF pos(X,) which satisfies all the bags. The dictatorship test and the completeness analysis are presented in Appendix D.
For the soundness analysis (Appendix F), consider any LTF given by pos(h(X)), such that it has no large coefficients. Observe that (h(x()))} are identically distributed but not necessarily independent, while conditioned analysis we show is that there is a fixed Gaussian distribution N (p, )) (independent of the choice of Z, r) such that with high probability over the choice of Z each of (4(x(0))} are distributed close to N (p, o). In effect, this implies that the probability that the bag is satisfied is at most, Ar + o[1), where Ana := (9)a²( a)9-r, and : E(pos(g)], ~ N (4, o), whre E is the expectation operator.
Z they are independent but not identical. Using fairly involved
The above invariance is obtained (in Appendix F.1) through the randomness induced by the noise coordinates in x() for given j i.e those i for which Zij is sampled to be 2, which x,") are independently sampled to be 1 or w.p. s/2 each. Due to their small magnitude the d-valued coordinates in x!!)) can essentially be ignored. After estimating bounds on the conditional (on
5

---

Zi) expectation and variance of h h((()) we apply the Berry-Esser theorem to obtain the desired invariance.
In Appendix C.1 we use the trick of folding over a real subspace [25] to encode the Label Cover and combine the above dictatorship test only on the [M] labels of the Label Cover vertices. This combination and the label decoding (in Appendix C.3) is along the lines as previous works c.g. by [25, 21]. In fact, we combine the Label Cover instance with D on bags of size q with label proportions r/q for all r E (l,...,9) q). in each D Thus, we are able to use the same μ and Σ for each r obtain the Ar, + o(1) bound for each r with the same a. If we weigh each of these distributions uniformly. using the easy derivation that Σ A,,a S 1 for a E [0, 1). we obtain a (1/q + o()) factor hardness as shown in Sec. 4. For q 2, we obtain in Appendix B better 4/9 + (11) factor using explicit calculations.
We note that the noise coordinates are identically distributed
Like the reduction of [37], ours also works for functions of constantly many LTF's as hypotheses, requiring the application of the multi-dimensional version of Berry-Esseed theorem.
The approach of decoupling by conditioning on Z is similar in spirit to that followed by [37] though their reduction has boolean coordinates which does not readily admit generalizations to larger bag sizes q. The main contribution of our hardness result is the design and analysis dictatorship test that works for all bag sizes q yielding bag- dig-distributions of specific label proportions r/q (r = .,....9) with random-threee threshold like soundness A,, o(1).
Organization of the paper. The next section provides some mathematical preliminaries and the proof of our novel characterization of > B for psd matrices. The latter used the proof of Theorem 1.1 in Sec. 3 which provides and analyzes our algorithm A for LLP-LTF(33. Sec. 5 presents an experimental evaluation of our algorithm on simulated data. In Sec. 4, Theorem 1.2 is derived from the statement of our hardness reduction whose proof is deferred to the Appendix C. The proof of Theorem 1.3 is also omitted and appears in Appendix G.
2 Preliminaries
We state a few well known facts about matrices.
The pseudo-invess of diagonal matrix D = Diag( or, .) with top non-zero entries and the rest 0 is given by D Diag(o ..... o, .,........ 0). A symmetric matrix A has decomposition A- = UDUT for some diagonal matrix D and orthonormal matrix U i.e. satisfying UUT = U = I. The pseudo-inverse is A UDTUT.
Definition 2.1 (see [28, 9]). For a real symmetric n x n matrix A, the the following conditions are equivalent: (1) > O, i.e is positive semi-definite (psd), (2) UAU z 0 all orthonormal matrices U. (3) x Ax 2 for all x E R", (4) A = UDUT for some orthonormal U with D being a non-negative diagonal matrix(spectral decomposition), (5) all the principal minors of A have non-negative determinant.
B> 0. The square-roud of For any two matrices, the Loewner order is given by A > B A -
non-negative diagonal matrix D Diag(o Gn) is 1/2 == Diag(o ......ww o/2) For a psd
A UDUT, the square root is 1/2 UD The following lemma, a variant of the the Schur schur-complement definiteness property, can be found on page 88 of [9], see also Thm. 4.3 of [ [17].
Lemma 2.2. For any n X n matrices A, and C where A and C are symmetric, let X = ( B
B²
Then, X 2 0
A BCBB 0.
2.1 A characterization of A > B for psd matrices
We prove the following lemmas which are used in our algorithmic results.
Lemma 2.3. Given a real symmetric psd matrix A, 3L s.t. A = L'L and the following are equivalent: (i) A > B, and (ii) 3C s.t. B = L' and A > CTC, for any real symmetric psd matrix B. Further, can be efficiently obtained from the spectral decomposition of A.
Proof. It is easy to see that (ii) + (i) as follows. Considering any vector x we have,
Cx| 2 x C Cx < Ax= L Lx|
(I)

---

where we use A = C and A = LLLL Thus, using (1)
= (Lx, Cx) & [xx||||Cx|] 1 [x = Ax
Thus, (i) + (i). The reverse is proved in Lemma 2.4 along with the explicit formula for L.
Lemma 2.4. Let A and B be two real, symmetric, psd l x k matrices such that A Z B (t) Then, with the spectral decomposition A UDU L L where U is orthonormal, D non-negative diagonal and L = UT, there exists C such that (i) B = L and (ii) A Z CTC.
Proof. Let C BU be symmetric psd (Defn. 2.1). Condition (+) of the lemma implies,
U - U 2 0.
(2)
Suppose that D has top r diagonal elements positive and the rest zero. Then C is zero outside of the top r X submatrix. Otherwise, D C will have nonzero entries -Cip -C,' in the (i,r') and (r', entries for some r' and On the other hand, the diagonal entry at (r' r') is -Crr, since both (D C) and C are psd and have non-negative diagonals, and thus the x 2 principal minor of D C given by the ith and r'th rows/columns has negative determinant which contradicts Defn. 2.1.
Since C is zero outside of the top submatrix, letting I, be diagonal matrix with ones in the top entries and zero otherwise we have,
U = IBBU=I
BU- =
(D
B UD (D CU = (D*)**) CUT
(D'*)² f CUT yields property (i) of the lemma. For the second property observe that, Letting C:= CD=(D
cTc (D**)* (D**) CU UCD'CU""
(3)
using which A C a UTAU = CC < D CDIC = X O, where e X C ) = (BD), and the last implication follows from Lemma 2.2. It remains to show that
D
X z 0. For this let (x1, Tk. ,1,....... mkk, and (x1 -01:-..,,28 Fk), (V1,...; ;.)) Then, z Xz x I Dy + 2x Cy
(4)
Since C is symmetric psd we can write V that
x Cx y Cy 2x Cy (Vx, Vx) + (Vy, Vy) 2(Vx, Vy) |V + Vyl
(5)
Substituting 2x Cy 2 (x - Cy) into the RHS of (4) we obtain,
2x > x DD C)x (D C)y
by (2) which holds for any z. Thus, X psd which completes the proof.
3 Algorithm for LLP-LTF(33
3.1 SDP Relaxation
We define two collections of constraints NOSPLIT and SPLIT for monochromatic and non- monochromatic bags of size 3 respectively in Fig. 1. For a satisfiable instance J = (X {xi....,x,, x,} C R B- B far )m of LLP-LTF(33 let &; e IR++1 be given by appending an extra 1-valued coordinate x, for E [n]. With this the corresponding SDP relaxation is given in Fig. 2, and it enforces NOSPLIT constraints for monochromatic bags of size 3 and those given by SPL.TT for the non-monochromatic 3-sized bags. Constraints for margin and bags of size 2 are the same as in the algorithm of [37].
Feasibility of SDP-I. As discussed in Sec. 1.4, if (r,( is the satisfying LTF, then we can set R R==R Tr and ( = R if (r, x:) (r, < 0 and 0 otherwise. The arguments for the margin and 2-sized bag constraints are same as those Sec 2.1 of [37], and those for the 3-sized bag constraints informally presented in Sec. 1.4. We defer the formal proof to Appendix A.
7

---

NOSPLIT(U:, u2 us Q)
Given ([x.)=m. [Br) {o:)
Vars: real,
symmetric psd R. R R(J)
1si S s.t.
Sr Qu.
(7)
vi [n]: VB: = (t
x Rx: > 0 (13)
SPLIT in uz us. Q. (1.2)
Q (2.3)
Q (1.3))
if E (0,1):
x R 2 0 (14)
< 3::3::3
Σ 0
(8)
if & {0,1):
x S 0 (15)
Si<<=s3:0
(mg)
(9)
VB, (x,, xx), (1 < < k): o E (0,1) NOSPLIT & X3. Rt. R) (16)
Q (1.2) (1.3) Q
(10)
Q (..2 (2.3) Q
(11)
of $ {0,1]: SPLIT X 8,. 8k. R.
Q (1.3) (2.3)
(12)
R (1d) bikk R (68) (17)
Figure 1: NoSPLIT and SPLIT
Figure 2: SDP-I
Algorithm A. Input: satisfiable instance of LLP-LTF(3).
1. For cach x E IR define = (21,,.... Fa, 1) E R*
Solve SDP-I (Fig. 2) for psd matrix R E R(++)x((+1)
Let UDU be spectral decomposition. Let UT so that R L'L.
4.
Sample u.a.r from N(0, 1)
Define linear form l((x) == g)
6.
Let he E (h, h) such that pos(h" (.)) satisfies more bags of J. Output pos(h (.)).
Figure 3: Algorithm A for LLP-LTF(33.
3.2 SDP Algorithm and analysis
Fig. provides the algorithm A for the satisfiable LLP-LTF[33 instance J. We have the following lemma for bags of size 3.
Lemma 3.1. Consider the linear form obtained in Step 5 of A (Fig.
3). Then, the probability of non-monochromatic 3-size bag being split by pos(h(-)) is at least 1/6, and that of 3-sized monochromatic being unsplit by pos(h(-)) is at least 1/4.
Proof. Let B be a bag of size 3 and by relabeling WLOG we can assume that (x1, X2,,X2, X3).
Case: non-mooochromatic. Using (10) we have
x R (1.2) + +R(1.3) &1 2 x = |
(18)
where is as defined in Step of (Fig. 3). By averaging and WLOG we can assume that x (1.2), | /1//2 2 and by applying Lemma 2.4 the guarantee that R R(1,2) (from (9))
we obtain that there exists matrix s.t.,
R (1.2) L
(LL, Cx.) = L = x R (1,2) 2
LX 113/2,
(19)
and
R CTC
|cx;; = cT CX, S x Rx;
LX 12.
(20)
Further, using (8)
(1.2 (1.2) x S 0. (X2, Cx1) X TCC = xJ (12) = R
(21)
Eqn. (13) implies
|L > (b = 1,2), and by (19) we also have
C* ||2 > 0. Define the unit
vectors:
=
z = L LX 2 and 22 = Lx LX 2
(22)

---

From (19). (20) and (21) we obtain that (Zo. z1) 2 1/2, and (Zu, [2) - 0. For b = 0, 1 we can write
Z0 = Co0 + Co1 25 where ||a ll2 = 1 and % 1 %0 so that 2 + 61 1. Note that (2o, 21) 2 1/2
22
implies that Cı0 2 1/2 and therefore |c11| - v 3/22. Further, (Zo. Zz) I 0 implies that C20 I 0. Thus,
(21, 22) S C10020 + |en ||221 - - -11/2))c22) + (v3/2) 1 v3/2.
(23)
Thus, the angle between L j and LXg is at least x //6. From standard facts on random hyperplane rounding (see Appendix A of [37]) it is easy to see that pos(h(x1)) A pxs()(x2)) with probability at least (=/6)/= 1/6.
Case: B monochromatic. In this case, (13), (7) guarantee that [LX, b = 1, 1, are non-zero vectors with pairwise non-negative inner products. It is well known fact (see [19]) that such vectors can be rotated to be contained in three-diment dineesilme orthant (cone subtended by three coordinate rays). Thus, the probability that the bag is unsplit by pos()(.)) is at least the probability that the inner products of three orthonormal vectors with (as chosen in Step 4 of A) all have the same sign. Each of these three inner products is an independent standard Gaussian, so the latter probability is 1/4. O
Since our algorithm A when restricted bags of size < 2 is the same as that given by [37], we can reuse the following lemma which summarizes the analysis in Sec. 2 of [37].
Lemma 3.2 (Sec. 2 of [37]). Any monochromatic hag of size 2 is unsplit by pos(h(-)) with probability at least 1/2. Any non non-monochromatic bag 2-sized bag is split by pos(h(.)) with probability least 1/2. Further, h(x.) + (1 S i S n) w.p. 1.
Assuming that h does not vanish any x, (which happens w.p. 1) we obtain the following properties. If monochromatic bag is usplit by pos(h(-)) then it satisfied by exactly one of pos (h()) and pos(-h(.)) This also holds for any non- an--moncchromatic bag of size 3 split by vos(h(.)), On the other hand a non- monochromatic bag of size 2, split by pos(h..)), is satisfied by both pos()(.) and pos(-h(.)) This, along with Step 6 of A completes the proof of Theorem 1.1.
An analysis of the time complexity of A (which is asymptotically dominated by the time taken to solve the SDP) is provided in Appendix I.
4 Hardness Result
The following theorem, whose proof provided in Appendix C. states our detailed hardness result.
Theorem 4.1. For positive integers constants 1, 1.2 1, and any constants {> >> O and {pr 2 03 s.t. Ei= Pr = 1, given an instance 3 of LLP--LF((g) with pr fraction of bags of size q and label proportion r/q. for {1.....q). it is NP-hard to distinguish between the following cases:
YES Case. There is an LTF that satisfies all the bags Jf
NO Case. Any {0, 1)-functionn f of at most & LTFs satisfies at most A.pi.... + fraction of the bags in I where A A.Pr == maxae(0.1] (Er=1rrA,..) Pr..).))) and Agrn == (9)a a)9-".
Proofs of Theorem 1.2. We apply Theorem 4.1 with p. = 1/9 for r E [q]. In the NO case, the total fraction of bags satisfied by í is v = maxac(U.1)
1
q Σ A A,r.a + Ç for an arbitrarily small
constant >> 0. Observing that Σ Aq.. S E A.r. = (a + (1 ax) )9 1, we obtain that S 1/g + This, along with the Yes case, proves Theorem 1.2 for LLP-LTF(()) [g)
For the case of q = 2 we show (in Appendix B) that min max pa² + 2(1 p)pppppappl)ppp (1-a) 4/9 to obtain 4/9 + Ç hardness factor.
5 Experimental Evaluation
We compare our algorithm (A) to random LTF (R) evaluated on 25 instances for each row of Table I giving the avg. % bags satisfied by each method, and the last two columns providing the accuracy on test dataset obtained by sampling bag (same as the bag distribution) and sampling u.a.r. one of the three feature- vectors from the bag.

---

For each instance, bags (of 3 d-dim. vectors each) are sampled, where each is mon-monochromatic w.p. 3/4. The small and large margin cases are analogous to the correlated and uncorrelated cases in the experiments of [37], and we similarly follow a best-of
m
A
R Aust Riest
(small
margin)
10
50
93.0
6.3
96.2
51.4
10
100
97.1
4.4
98.6
53.2
5-trials based rounding for AA and best-of 5 u.a.r. LTFs or their
40
50
81.9
4.8
85.4
51.8
complements for R. We see that (i) A satisfies on avg. 80-97% of the bags in the small margin cases, vastly outperforming R. the average reature-vector level test accuracy of the LTF produced by algorithm is quite high: 96-98% for d = 10 and 85-90% for
40
100
83.0
90.1
52.0
(large
margin)
10
50
51.0 46.3
67.7
58.1
10
100
55.9
46.5
75.1
63.1
= 40, while that of random LTF is rather low at around 50.55%. (ii) A also betters R in most of the large margin cases. Additional details are included in Appendix which also provides similar experimental evaluation for weakly-satisfying LLP-LTF(44.
40
50
43.5
41.2
52.9
53.2
100
40.2
40.9
53.4
52.3
Table 1: Our alg. (A) vs rand.
LTF (R). Bag size
Remark. The SDP formulation in our experiments for 3-sized bags differs slightly from the one in Fig. 2 by using alternate valid constraints for non-monochromatic bags. In particular, instead of x R (,,x,x,,, I 0, i + j E [1,2.3} (as described in Sec. 1.4) we add x. (Id)) + (.(. x3 < 0 for each k
(1,2,3). It is easy to see that the new inequalities imply that there is E {1, such that for each j E {1, 3) \ {i). x! [R(+)) Using this condition the rest of the analysis can be done as before yielding the same approximation guarantee, while it provided better observed experimental performance. We defer formal explanation to Appendix J.
O.
6 Conclusions
Our work develops novel linear algebraic techniques to design and analyze non-trivial SDP relaxation based (other than trivial or random LTF) was known. We also prove 1/g o(1) factor hardness for LLP-LTF (g) for all constant q, and a strengthened 4/9 + o(1) factor for q = 2, improving on the previous 1/2 + o(1) factor [37]. We extend our algorithm to bag sizes bug-satisfiability. obtaining (2(1/g)-approxii)) -approximate algorithm.
for satisfiable LLP-LTF(33, for which no previous algorithm
for for weaker notion of
Experiments on simulated data of 3-sized bags shows that our algorithm can provide substantially improved (over random LTFs) performance, both in terms of bag satisfiability as well as on feature- vector level test evaluation.
The main open question in this line of work is to develop algorithms for satisfiable LLP-LTF(g) for q 2 4. Of course, learnability in the LLP setting can also be studied for other natural classifiers such DNF formulas and decision trees.
Another interesting direction to study variants of the bag satisfiabliltiy objective such as those which minimize the average deviation (according some distance e.g. li or L between the given bag label proportions and those induced by the solution classifier.
References
[1] E. Amaldi and V. Kann. On the approximability of minimizing nonzero variables unsatisfied relations in linear systems. Theor. Comput. Sci., (09(1-2):)3772226)) 1998.
[2] Amores. Multiple instance classification: Review, taxonomy and comparative study, Artif. Intell., 201:81-105, 2013.
[3] S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci., 54(2):317-331 1997.
[4] D. Barucic and J. Kybic. Fast learning from label proportions with small bags. CoRR, abs/2110.03426, 2021. URL
httpe///aawvvvvoaoaaabaeeeee org//bss/210..c. 03426.
[5] S. Bev-David, N. Eiron, and P. M. Long. On the difficulty of approximately maximizing agreements. J. Comput. Syst. Sci. 6665)4496-514, 2003.
10

---

[6] A. Bhattacharyya, S. Ghoshal, and R. Saket. Hardness of learning noisy halfspaces using polynomial thresholds. In Proc. COLT, volume 75, pages 876-917. PMLR, 2018. URL http://ppocceddii mlr. S.l.r.pres/v75..
bhattacharyya118a mal..prrss//////btataaaaaarr
html.
[7] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik- chervonenkis dimension. J. ACM, 36(4):929-96) 1989.
[8] G. Bortsova, F. Dubost, S. N. Ørting, 1. Katramados, L. Hogeweg, L. H. Thomsen, M. M. W. Wille, and M. de Bruijne. Deep learning from label proportions for emphysema quantification. In MICCAI, volume 11071 of Lecture Notes in Computer Science, pages 768-776. Springer, 2018. URL hwt.h:tt///aat //axxiv// htt.aaiww....a.aaaoaoo//a./ ataaa/b////110.//3
[9] S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2014.
[10] N. H. Bshouty and L. Burroughs. Maximizing agreements and coagnostic learning. Theor. Compul. Sci., 350(1):24-333) 2006.
[11] L. Chen, Z. Huang, and Ramakrishnan. Cost-based labeling of groups of mass spectra. In Proc. ACM SIGMOD International Conference on Management of Data, pages 167-178, 2004.
[12] N. de Freitas and H. Kück. Learning about individuals from group statisties. In Proc. UAI, pages 332-339, 2005.
[13] L. M. Dery, B. Nachman, F. Rubbo, and A. Schwartzman. Weakly supervised classification in high energy physics. Journal of High Energy Physics, 2017(5):1-11, 2017.
[14] L. Devroye, A. Mehrabian, and T. Reddad. The total variation distance between high- dimensional gaussians. CoRR, abs/1810.08693,, 2020. URL 08693.
[15] G. Dulac-Amold, N. Zeghidour, M. Cuturi, L. Beyer, and J. P. Vert. Deep multi-class learning from label proportions. CoRR, abs/1905. 12909, 2019. URL 12909.
org htsp/bbbs/990.
[16] V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM J. Compus.. 39(2):606-66 645, 2009.
[17] Jean Gallier. The Schur complement and symmetric positive semidefinite (and definite) matrices, 2019. URL https: hwwp:/wwwwwcccoo cis upenn. "aatuu"jea//ssse pean/schur--o wwwchruooop....oo.ooocc pdf.
[18] S. Ghoshal and R. Saket. Hardness of learning DNFs using halfspaccs. In STOC, pages 467-480. ACM, 2021.
[19] L.J. Gray and D.G. Wilson. Nonnegative factorization of positive semidefinite nonneg- ative matrices. Linear Algebra and its Applications, 31:119-127, 1980. URL https:
/ //www www.seeeeeceeeet...mm com/ httpa////aatcccee///////////////
[20] V. Guruswami and P. Raghavendra. Hardness of learning halfspaces with noise. In Proc. FOCS, pages 543-552, 2006.
[21] V. Guruswami, P. Raghavendra, R. Saket, and Y. Wu. Bypassing UGC from some optimal geometric inapproximability results. ACM Trans. Algorithms, 12(1):6:1-6:25, 2016. URL http://eccc. hpi - web. www.whp.wwwweeeeeeeeeeeeee. www.eedeerrepor//210/////
[22] J. Hernández-Gonnzález, I. Inza, and J. A. Lozano. Learning bayesian network classifiers from label proportions. Pattern Recognit., 46 (126112)44253444) 2013.
[23] J. González I. Inza, L. Crisol-Ortíz. M. A. Guembe, M. J. Iñaraa, and J. A. Lozano. Fitting the data from embryo implantation prediction: Learning from label proportions. Statisti- cal methods in medical research, (7(4) 2018.
[24] H. Jiang, T. Kathuria, T. Lee, Padmanabhan, and 7.. Song. A faster interior point method for semidefinite programming. In FOCS, pages 910-918, 2020.

---

[25] S. Khot and R. Saket. On the hardness of learning intersections of two halfspaces. J. Comput. Syst. Sci., -791):129-14,, 2011.
[26] D. Kotzias, M. Denil, N. de Freitas, and P. Smyth. From group to individual labels using deep features. In Proc. SIGKDD, pages 597-606, 2015.
[27] Liu, B. Wang, Z. Qi, Tian, and Shi. Learning from label proportions with generative adversarial networks. In Proc. NeurIPS, pages 7167-7177, 2019.
[28] C. D. Meyer. Matrix Analysis and Applied Linear Algebra. SIAM, 2000.
[29] D. R. Musicant, J. M. Christensen, and J. F. Olson. Supervised learning by training on aggregate outputs. In Proc. ICDM, pages 252-261. IEEF Computer Society, 2007.
[30] S. N. Ørting, J. Petersen, M. Wille, L. Thomsen, and M. de Bruijne. Quantifying emphysema extent from weakly labeled et scans the lungs using label proportions learning. In The Sixth International Workshop on Pulmonary Image Analysis, pages 31 31-42, 2016.
[31] R. O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014.
[32] G. Patrini, Nock, T. S. Cactano, and P. Rivera. (almost) no label no cry. In Proc. Advances in Neural Information Processing Systems, pages 190-198, 2014.
[33] N. Quadrianto, A. Smola, T. S. Cactano, and Q. V. Le. Estimating labels from label proportions. J. Mach. Learn. Res., (0:2349-23774, 2009.
[34] M. Raič. A multivariate berry-esseen theorem with explicit constants. Bernoulli, 25(4A), Nov 2019. ISSN 1350-7265. 18-BEJ1072.
doi: 10.3150/18-bej1077 URL http: http:///xx.do doi org. /150/
[35] S. Rueping. SVM classifier estimation estmattioo from group probabilities. In Proc. ICML, pages 91 911-918, 2010.
[36] S. Sabato and N. Tishby. Multi-instance learning with any hypothesis class. J. Mach. Learn. Res., 13:2999-3039, 2012.
[37] R. Saket. Learnability of linear thresholds from label proportions. In Proc. NeurlPS, 2021. URL https://opppeereiiie net/forum?in Fewforrmmddddnaaaeeeee
[38] R. Saket, A. Raghuveer, and B. Ravindran. On combining bags to better learn from label proportions. AISTATS, volume 151 of PMLR, pages 5913-5927.
[39] C. Scott and J. Zhang. Learning from label proportions: A mutual contamination framework. In Proc. NeurIPS, 2020.
[40] Wojtusiak, Irvin, A. Birerdinc, and Baranova. Using published medical results and non-homogenous data in rule learning. In Proc. International Conference Machine Learning and Applications and Workshops, volume 2, pages 84-89, IEEE, 2011.
[41] F. X. Yu, D. Liu, S. Kumar, T. Jebara, and S. F. Chang. xSVM for learning with label proportions. In Proc. ICML, volume 28, pages 504-512, 2013.
[42] X. Yu, K. Choromanski, S. Kumar, Jebara, and S. F. Chang. On learning from label proportions. CoRR, abs/1402.5902, 2014. URL http::/arxixi org.oogg///ooo abss/142..900
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix H.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
12

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results....
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proofs are contained in the main paper and appendix included with the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The experiments are on simulated data. The code included with the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes] Details included in Appendix K.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Details included Appendix K.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you' 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "pfwEq8H6fnL", "reviewer": "Reviewer_RxJW", "summary": "This work aims to propose an algorithm and theoretical analysis for learning from the label proportion problem, where the labels are given in aggregated form as a proportion of true labels in a bag of features. The proposed algorithm is for the case when the size of the bags is less than three and it comes with guarantees on the fraction of satisfying bags. The theoretical analysis shows the hardness of the learning problem. Some experimental results on synthetic data are provided.", "questions": "- Can the authors discuss the complexity of the proposed algorithm?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I find the hardness results, saying that satisfying more than 1/q + O(1) fraction of bags in the learning from label proportion problem is NP-hard, to be interesting since most of the previous work focus on developing new algorithms while not  much looks into the inherent hardness of this problem. However, here are a few concerns:\n- My main concern is the readability of this work. Even though the hardness result is interesting, I find it hard to understand the proofs. For the overview provided in Sec. 1.5, it would be helpful if the definitions of label cover problem and the template of a dictatorship test are formally stated to make this work more self-contained. Also, the proof in Sec. 5 is hard to parse since it is mostly formulas without intuitions. The readability of this proof needs to be improved, probably by making it more verbal. Besides, there are too many typos that harms readability a lot. See below.\n- It seems that the complexity of the proposed algorithm is at least cubic in the size of features, which make it impractical. It would be helpful if the authors provide a detailed discussion on the complexity of the proposed algorithm. I wonder how the runtime increases as the number of dimension d increases.\n- The empirical evaluation seems too toy and comparison with existing learning from label proportion algorithms are missing.\n- Missing references on existing work on learning from label proportion:\nScott C, Zhang J. Learning from label proportions: A mutual contamination framework. Advances in neural information processing systems. 2020;33:22256-67.\n\nTypos:\n- Line 97: the lower case f is not defined.\n- Line 97: it is unsplit by F is the latter ... -> it is unsplit by F if the latter ...\n- Line 110: In the worst, case -> In the worst case, \n- Line 129: r is not defined.\n- At Line 150, the symbol (*) is used to denote a formula while later at Lemma 2.4 the same symbol (*) is used to denote another formula.\n- Line 205: E is undefined.\n- Line 310: A right parenthesis is missing.", "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": "ak0EjzOHe66", "reviewer": "Reviewer_gUha", "summary": "The paper proposes algorithms for learning linear threshold functions (LTFs) from label proportions. In this model, the learning algorithm is given \"bags\" of points with the proportion of points in the bag labeled $1$. The goal is simply to find an LTF that maximizes the number of bags on which it labels the points exactly at the right proportion. The problem is NP-hard, so approximation algorithms are considered. The paper improves upon the previously known lower bound for bags of size $2$. It also gives a $\\frac{1}{12}$ guarantee for bags of size $3$, and in general an $\\Omega(1/q)$ guarantee for bags of size $q$. It is also shown that it's NP-hard to approximate the problem with bags of size $q$ beyond $\\frac{1}{q}+o(1)$. The method is to solve a semidefinite programming relaxation, then round the result using a random hyperplane.", "questions": "What's the justification for choosing this objective function over, say, minimizing the total deviation or maximum deviation over all bags? Do your methods extend to other choices of objective? Are there previous results on other choices? Are these alternatives easier? harder?", "limitations": "None.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main contribution of the paper is the new SDP relaxation, which is new, non-trivial, and interesting.\n\nThe model has been studied before, and the bags input is justified by issues of privacy/legal constraints. However, I'm not completely convinced by the justification for the objective function (that for small bags it's reasonable). Why insist on getting as many bags as possible to have the exact input ratio, perhaps at the expense of gross errors on the other bags? Alternatively, one can try to minimize the total deviation, or the maximum deviation, or a host of other alternatives.", "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": "YqN4d6sV-Je", "reviewer": "Reviewer_Bsrj", "summary": "This paper studies the fairly natural learning problem of \"learning from label proportions\". The underlying problem is realizable supervised classification, however, instead of receiving labelled instances, the learner receives multiple bags of instances and the proportions of positively labelled instances in each bag, i.e., the \"label proportions\". This is motivated by e.g., privacy concerns. The goal of the learner is to find a hypothesis (from a hypothesis space) which predicts the instance labels in all bags in a way such that the number of bags with correctly predicted label proportions is maximised. This generalises regular supervised learning, as for bags of size 1 this corresponds to classifying all instance labels correctly. The main concern of the authors is to construct a polynomial-time \"empirical risk minimiser\" (or the equivalent thereof in this label proportions scenario) and not generalisation aspects (e.g., to new independently drawn bags).\n\nIn particular, the authors focus on this label proportions learning scenario in the case of linear threshold functions, i.e., halfspaces. For bags of size $\\leq 2$ previous work suggested first algorithms and hardness results. This paper improves the hardness lower bound for bags of size at most 2 from essentially $1/2$ to essentially $4/9$. Additionally, this paper generalises these results to bags of size $\\leq 3$ and achieves similar results there through an involved SDP-based relaxation. They also derive hardness lower bounds for the general case with bags of arbitrary size, which also applies to the improper case of functions that depend on a constant number of halfspaces, and propose an algorithm which asymptotically achieves this bound, however, using a weaker notion of satisfied bags.\n\nThey also prove a novel characterisation of psd matrices A,B satisfying $A\\preccurlyeq B$, which might be of independent interest.\n\nFinally, the theoretical results are complemented by first practical experiments, where the authors compare their approach with a simple randomised baseline on synthetic datasets.", "questions": "While the achieved results for linear thresholds are interesting, the question arises whether similar algorithms and bounds are possible in the general case (for arbitrary hypothesis space / set systems). Maybe there is some complexity notion similar to the VC dimension determining \"learnability\" here. \n\nWhat about halfspaces with margin $\\gamma$? Does this help in the learning scenario?\n\nWhile it is true that for bag sizes $>2$ it is unclear whether $\\langle r, x_1\\rangle\\langle r, x_2\\rangle>0$ cannot be determined anymore, the label proportion still determines $\\langle r, x_1\\rangle\\cdot\\ \\dots\\ \\cdot\\langle r, x_q\\rangle>0$. Can this be used by some algorithm? Please elaborate, as it seems like a natural generalisation of the $q=2$ case.\n\nDo the authors thing the hardness bound of $4/9$ is best possible for $q=2$?", "limitations": "The paper only discusses the computational problem of finding a hypothesis such that a maximum number of bags is satisfied (have correctly predicted label proportions). However, as the problem is called \"learning from label proportions\" a discussion of possible generalisation bounds would be very interesting (prediction label proportions of unseen bags). Previous work, e.g., [28], apparently has generalisation bounds.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Very well-written and easy to follow paper. The contributions will be most likely interesting to a theoretical sub-community of NeurIPS and potentially enables further work building on top.\n\nThe experiments are sufficient for such a theoretical contribution. In fact, they are not really necessary.\n\nMinor points:\n* Why do the authors not use the more common and simple term \"halfspace\" instead of LTF\n* The two overview sections (1.4, 1.5) are helpful. To round it up the authors could include pointers to the actual Lemmas and Theorems (e.g., while discussing line 164 and following maybe note that the full statement is in Lemma 2.3, or multiple times on page 5). \n* Please add a short section on \"LLP-LTF[q]\" with the most important details in the main paper, as well. For example, by moving the experimental evaluation to the appendix.\n* (Standard) references for the dictatorship test, the lavel cover problem , and the folding trick would be very much appreciated.\n* I would switch the order of \"4. Experimental Evaluation\" and \"5. Hardness Result\" to separate the theoretical results from the empirical ones more clearly.\n\nTypos:\n* Berry-Essen --> \"Esseen\"\n* line 126: missing \" \" (space) between \"proceeds.Since\"", "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