summaries: This work studies the problem of learning from label proportions (LLP), that is given bags of vectors and given the average of the positive labels in each bag, we need to find an LTF that satisfies most of the bags. The authors study the case where the bags contain at most 2 vectors. They study two cases, one where the vectors are taken from $\mathcal X\subseteq \mathbb{R}^d$ and they are searching for an LTF; in the other case the vectors are taken from the $d$-dimensional hypercube $\{0,1\}^d$, and they are looking for an OR-LTF. In the first case, they provide an algorithm that satisfies $2/5$ of the bags and if all the bags are non-monochromatic (contain vectors with different labels) then the algorithm satisfies $1/2$ of the bags, for the other case they provide an algorithm that satisfies $(2/5 + \gamma_0/d)$ bags and if all the bags are non-monochromatic it satisfies $(1/2+\gamma_0/d)$ of the bags. Furthermore, for the last case, the authors provide an NP-hardness reduction to the Label Covering problem that shows that their result is qualitatively tight and that in general, we cannot hope for an algorithm that satisfies all the bags. This work considers the problem of learning a linear threshold function (LTF) from label proportions. In particular they consider the special case where both single (as in the standard PAC learning setting) labeled (as 0 or 1) examples are observed or pairs of points $(x_1, x_2)$ together with their average label (which can be 0, 1, or 1/2) are observed.  They give two main results: a polynomial time algorithm that finds an LTF that satisfies at least 2/5 of the labeled examples (pairs and singletons together) and a lower bound that shows that finding an LTF that satisfies more than 1/2 of the labeled examples is NP-Hard.  For the special case where only mixed pairs, i.e., with label 1/2, are observed, the provided algorithm satisfies 1/2 of the labeled examples matching the lower bound (which also assumes only mixed pairs). This paper studies proper learning of linear threshold functions (LLFs) in the learning from label proportions model.  There are two main contributions.  The first is a polynomial time algorithm that, given a collection of bags each of size at most two consistent with some (unknown) LLF, identifies an LLF that satisfies at least $2/5$ of the bags.  The second main contribution, which complements the first, shows that it is NP-hard to compute, given a collection of bags all satisfied by some monotone OR, to compute any function of constantly many LLFs that satisfies $(1/2+\epsilon)$ of the bags for any positive $\epsilon$.          This paper intends to make a few theoretical contributions for the learning from label proportions framework. In this framework training data arrives in the form of bags that contain several feature vectors and the proportion of positive labels in the bag as ground truth. The authors focus on learning linear threshold functions, while making a restriction to bags of size two.   A few theoretical results are presented. A first theorem gives a lower bound on the number of bags that can be "satisfied" with a polynomial time algorithm -- the authors define a bag as satisfied if the predicted proportion of positive labels equals the real proportion in the bag. A second theorem states that finding a linear threshold function that satisfies all bags is NP-hard in the worst case. 
abstractText: We study the problem of properly learning linear threshold functions (LTFs) in the learning from label proportions (LLP) framework. In this, the learning is on a collection of bags of feature-vectors with only the proportion of labels available for each bag. First, we provide an algorithm that, given a collection of such bags each of size at most two whose label proportions are consistent with (i.e., the bags are satisfied by) an unknown LTF, efficiently produces an LTF that satisfies at least (2/5)-fraction of the bags. If all the bags are non-monochromatic (i.e., bags of size two with differently labeled feature-vectors) the algorithm satisfies at least (1/2)-fraction of them. For the special case of OR over the d-dimensional boolean vectors, we give an algorithm which computes an LTF achieving an additional Ω(1/d) in accuracy for the two cases. Our main result provides evidence that these algorithmic bounds cannot be significantly improved, even for learning monotone ORs using LTFs. We prove that it is NP-hard, given a collection of non-monochromatic bags which are all satisfied by some monotone OR, to compute any function of constantly many LTFs that satisfies (1/2 + ε)-fraction of the bags for any constant ε > 0. This bound is tight for the non-monochromatic bags case. The above is in contrast to the usual supervised learning setup (i.e., unit-sized bags) in which LTFs are efficiently learnable to arbitrary accuracy using linear programming, and even a trivial algorithm (any LTF or its complement) achieves an accuracy of 1/2. These techniques however, fail in the LLP setting. Indeed, we show that the LLP learning of LTFs (even for the special case of monotone ORs) using LTFs dramatically increases in complexity as soon as bags of size two are allowed. Our work gives the first inapproximability for LLP learning LTFs, and a strong complexity separation between LLP and traditional supervised learning.
authors.name: Rishi Saket
references.authors: E. Amaldi V. Kann
references.title: On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
references.venue: Theor. Comput. Sci., 209(1-2):237–260,
references.authors: S. Ben-David N. Eiron P.M. Long
references.title: On the difficulty of approximately maximizing agreements
references.venue: J. Comput. Syst. Sci., 66(3):496–514,
references.authors: A. Bhattacharyya S. Ghoshal R. Saket
references.title: Hardness of learning noisy halfspaces using polynomial thresholds
references.venue: Proc. COLT, volume 75, pages 876–917. PMLR,
references.authors: A. Blumer A. Ehrenfeucht D. Haussler M.K. Warmuth
references.title: Learnability and the vapnikchervonenkis dimension
references.venue: J. ACM, 36(4):929–965,
references.authors: N.H. Bshouty L. Burroughs
references.title: Maximizing agreements and coagnostic learning
references.venue: Theor. Comput. Sci., 350(1):24–39,
references.authors: L. Chen Z. Huang R. Ramakrishnan
references.title: Cost-based labeling of groups of mass spectra
references.venue: Proc. ACM SIGMOD International Conference on Management of Data, pages 167–178,
references.authors: C. Cortes V. Vapnik
references.title: Support-vector networks
references.venue: Mach. Learn., 20(3):273–297,
references.authors: N. de Freitas H. Kück
references.title: Learning about individuals from group statistics
references.venue: In Proc. UAI,
references.authors: L.M. Dery B. Nachman F. Rubbo A. Schwartzman
references.title: Weakly supervised classification in high energy physics
references.venue: Journal of High Energy Physics, 2017(5):1–11,
references.authors: G. Dulac-Arnold N. Zeghidour M. Cuturi L. Beyer J.P. Vert
references.title: Deep multi-class learning from label proportions
references.venue: CoRR, abs/1905.12909,
references.authors: V. Feldman P. Gopalan S. Khot A.K. Ponnuswami
references.title: On agnostic learning of parities, monomials, and halfspaces
references.venue: SIAM J. Comput., 39(2):606–645,
references.authors: V. Feldman V. Guruswami P. Raghavendra Y. Wu
references.title: Agnostic learning of monomials by halfspaces is hard
references.venue: Proc. FOCS, pages 385–394,
references.authors: B. Fish L. Reyzin
references.title: On the complexity of learning from label proportions
references.venue: Proc. IJCAI, pages 1675–1681,
references.authors: S. Ghoshal R. Saket
references.title: Hardness of learning DNFs using halfspaces
references.venue: Proc. STOC, pages 467–480,
references.authors: V. Guruswami P. Raghavendra
references.title: Hardness of learning halfspaces with noise
references.venue: Proc. FOCS, pages 543–552,
references.authors: J. Hernández-González I. Inza J.A. Lozano
references.title: Learning bayesian network classifiers from label proportions
references.venue: Pattern Recognit., 46(12):3425–3440,
references.authors: D.S. Johnson F.P. Preparata
references.title: The densest hemisphere problem
references.venue: Theor. Comput. Sci., 6: 93–107,
references.authors: D. Kotzias M. Denil N. de Freitas P. Smyth
references.title: From group to individual labels using deep features
references.venue: In Proc. SIGKDD,
references.authors: J. Liu B. Wang Z. Qi Y. Tian Y. Shi
references.title: Learning from label proportions with generative adversarial networks
references.venue: Proc. NeurIPS, pages 7167–7177,
references.authors: S. Mahajan R. Hariharan
references.title: Derandomizing semidefinite programming based approximation algorithms
references.venue: Proc. FOCS, pages 162–169,
references.authors: M. Minsky S. Papert
references.title: Perceptrons: an introduction to computational geometry
references.venue: MIT Press, Cambridge, MA,
references.authors: D.R. Musicant J.M. Christensen J.F. Olson
references.title: Supervised learning by training on aggregate outputs
references.venue: Proc. ICDM, pages 252–261. IEEE Computer Society,
references.authors: G. Patrini R. Nock T.S. Caetano P. Rivera
references.title: almost) no label no cry
references.venue: Proc. Advances in Neural Information Processing Systems, pages 190–198,
references.authors: N. Quadrianto A.J. Smola T.S. Caetano Q.V. Le
references.title: Estimating labels from label proportions
references.venue: J. Mach. Learn. Res., 10:2349–2374,
references.authors: F. Rosenblatt
references.title: Principles of Neurodynamics: Perceptions and the Theory of Brain Mechanisms
references.venue: Spartan Books, New York,
references.authors: S. Rueping
references.title: SVM classifier estimation from group probabilities
references.venue: Proc. ICML, pages 911–918,
references.authors: C. Scott J. Zhang
references.title: Learning from label proportions: A mutual contamination framework
references.venue: Proc. NeurIPS,
references.authors: J. Wojtusiak K. Irvin A. Birerdinc A.V. Baranova
references.title: Using published medical results and non-homogenous data in rule learning
references.venue: Proc. International Conference on Machine Learning and Applications and Workshops, volume 2, pages 84–89. IEEE,
references.authors: F.X. Yu D. Liu S. Kumar T. Jebara S.F. Chang
references.title: ∝SVM for learning with label proportions
references.venue: Proc. ICML, volume 28, pages 504–512,
references.authors: F.X. Yu K. Choromanski S. Kumar T. Jebara S.F. Chang
references.title: On learning from label proportions
references.venue: CoRR, abs/1402.5902,
sections.heading: 1 Introduction
sections.text: A linear threshold function (LTF) over the d-dimensional feature-vectors x is given by pos(g(x)) for some linear function g(x1, . . . , xd) = ∑d i=1 cixi + cd+1, where pos(z) := 1{z>0}. Also known as linear classifiers or halfspaces, LTFs are one of the most fundamental classes studied in computational learning and lie at the core of several machine learning algorithms such as Perceptron [25, 21] and SVM [7]. It is known [4] that LTFs are properly learnable in the supervised learning setup: given a training set of labeled feature-vectors which are consistent with some LTF, using polynomial-time linear programming one can efficiently find one such LTF.
  In this work we initiate an investigation into the proper learnability of LTFs in the framework of learning from label proportions (LLP). In this, instead of labels for each feature-vector, the training data consists of bags (subsets) of feature-vectors along with the proportion of labels in each bag.
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  Given a collection of bags with their respective label proportions which are consistent with (i.e, are satisfied by) some unknown feature-vector level classifier, the goal is to find a classifier (from the same concept class for proper learning) satisfying the most number of bags. Such a model was formalized by Yu et. al [30] who showed bounds on the generalization error for predicting the label proportion on unseen bags.
  When all bags are unit-sized this becomes the usual supervised learning in which as we noted above LTFs are efficiently properly learnable. A natural question is whether this remains true even when larger bag sizes are allowed. In particular, we consider the simplest setting with bags of size at most two and study the following question: Given a collection of bags, all of size at most two and guaranteed to be satisfied by some unknown LTF, what is the maximum fraction of bags that can be satisfied using an efficiently computable LTF?
  There naturally are two types of bags: monochromatic bags whose feature vectors have the same label, and the non-monochromatic ones whose feature-vectors have different labels and are necessarily of size two. Clearly, the monochromatic bags determine the labels of their constituent feature-vectors. Therefore, for a collection of bags consistent with some LTF, one can efficiently find an LTF using linear programming to satisfy all the monochromatic bags. However, such an algorithm is not guaranteed to satisfy any non-monochromatic bag.
  In traditional supervised learning of LTFs, the trivial algorithms of taking the best of any LTF or its complement, or a random homogeneous LTF, both achieve an accuracy of half. Unfortunately, these algorithms provide no such guarantees in the LLP setting, even for bags of size at most two. At a high level, in LLP the objective is given by comparing the predicted labels of a bag’s feature-vectors with each other, unlike supervised learning where they are only compared with observed ones. This seems to qualitatively change the nature of the problem in terms of the applicable techniques.
  We first provide an algorithm that satisfies (in expectation) at least half of the non-monochromatic bags and one-fourths of the monochromatic ones. This can be combined with the linear programming algorithm which satisfies all monochromatic bags (and possibly none of the non-monochromatic ones) to obtain an algorithm which outputs an LTF satisfying (2/5)-fraction of the bags. We also show that for the special case of the feature vectors being d-dimensional boolean and the bags being consistent with an OR (boolean disjunction) the algorithmic guarantees improve by an Ω(1/d) additional factor.
sections.heading: 1.1 Previous Work on LLP
sections.text: The LLP problem naturally arises in many real world scenarios where the labels are not available individually but only as proportions for bags of feature-vectors due to privacy [28] and legal [26] reasons, high label supervision cost [6] or technical limitations of labeling mechanisms [9]. Some of the earlier works [8, 16, 22, 26] applied supervised learning methods such as MCMC, clustering, and linear classifiers to the LLP problem. The work of [24] assumed an exponential generative model and proved performance bounds under assumptions on the distribution of the bags, and was further generalized by [23] while the work of [29] proposed novel proportional SVM based algorithms. Subsequently, approaches based on deep neural nets for large-scale and multi-class data [18, 10, 19], as well as bag pre-processing techniques [27] have been developed for LLP.
  In contrast to the long line above of application focused research in LLP, the theoretical study of algorithmic and complexity issues in LLP has been rather limited. On the complexity side, [13] studied a one-bag version of this problem where the observed global label proportion is given over all the feature-vectors and the goal is to find a classifier to minimize the deviation from this. They showed, among other results that common concept classes such as monotone-ORs cannot be learnt in their model to arbitrary accuracy.
  The LLP model which we study – of predicting the bag label proportions – was first formalized in the work of [30] who also bounded the generalization error when taking the (bag, label-proportion)-pairs as instances sampled iid from some distribution. Their bound has the same dependence on the featurevector classifier’s VC-dimension as in supervised learning, with an additional logarithmic dependence on the bag size. While the loss function they consider is slightly different, their bound can be applied to minimizing the number of unsatisfied bags of size two (see Appendix E of the supplemental). In the rest of this section we define the problem of learning LTFs from label proportions, describe our results and the previous related work along with an informal description of our methods and proof techniques.
sections.heading: 1.2 Problem Definition
sections.text: Let X = {x1, . . . ,xn} ⊆ Rd be the set of feature-vectors, and bags B = {B1, . . . , Bm} ⊆ ( X 1 ) ∪ ( X 2 ) , i.e. each bag is of size at most 2. The label set is binary i.e., {0, 1}, and for each bag Bk there is a proportion σk which is the average of the labels of the vectors in the bag, satisfying σk ∈ {0, 1} if |Bk| = 1 and σk ∈ {0, 0.5, 1} if |Bk| = 2. If σk 6= 0.5 then Bk is said to be monochromatic i.e., bags which have same labels for their feature-vectors. The remaining bags Bk necessarily of size 2 having σk = 0.5 are called non-monochromatic.
  A bag Bk ∈ B is satisfied by some f : X→ {0, 1} if (∑ x∈Bk f(x) ) / |Bk| = σk.
  An instance of LLP-LTF is given (X,B = {Bk}mk=1, {σk}mk=1). It is said to be satisfiable if there exists an LTF that satisfies all the bags. The goal is to find an LTF that satisfies the most bags.
  We denote by LLP-OR the special case when X has boolean vectors and the guaranteed LTF for satisfiable instances is an OR. A further special case is when the guaranteed OR is monotone i.e., it has no negated variables.
sections.heading: 1.3 Our Results
sections.text: We provide the following algorithmic guarantees for LLP-LTF on bags of size at most 2. Theorem 1.1. There is a polynomial time algorithm which given a satisfiable instance of LLP-LTF on bags of size at most 2, computes an LTF that satisfies at least (2/5)-fraction of the bags. If all bags are non-monochromatic this satisfies at least half of the bags. For satisfiable LLP-OR on bags of size at most 2 with d-dimensional boolean feature-vectors, there is a polynomial-time algorithm computing an LTF satisfying at least (2/5 + γ0/d)-fraction of the bags in general, and (1/2 + γ0/d)-fraction if all bags are non-monochromatic, for some absolute constant γ0 > 0.
  The above theorem for LLP-LTF is proved in Sec. 2 with the proof for LLP-OR provided in Sec. 2.1. The algorithms use random hyperplane rounding of vectors, so the above guarantees are in expectation. They can however be derandomized by the sophisticated procedure given in [20] and we provide an explanation in Appendix A of the supplemental.
  Our result on the intractability of LLP-OR (an thereby of LLP-LTF) is stated below. Theorem 1.2. Given a satisfiable instance of LLP-OR consisting only of non-monochromatic bags each of size 2 s.t. there is a monotone OR that satisfies all bags, it is NP-hard to find any function of ` LTFs that satisfies (1/2 + δ)-fraction of the bags, for any constants ` ∈ Z+, δ > 0.
  The proof follows via a reduction from a variant of the Label Cover problem. We include the guarantees of the hardness reduction as Theorem 3.3 which directly implies Theorem 1.2. However, due to lack of space we defer the formal proof of Theorem 3.3 to Appendices C and D of the supplemental, while including an informal description in Sec. 1.5. We note that Theorem 1.2 shows the optimality of the approximation factor obtained in Theorem 1.1 for non-monochromatic bags.
  Previous Related Work. As mentioned earlier, the proper supervised-learnability of LTFs [4] is well known without any distributional assumptions. In the presence of adverserial label noise however, the problem was shown to be NP-hard [17] and the works of [1, 2, 5] proved stronger inapproximability bounds with the optimal (1/2 + ε)-factor hardness obtained independently by [11] and [15], further generalized by [3] to apply for constant degree polynomial thresholds as hypotheses. Subsequently, [12] showed that this also holds for the special case of learning OR with an LTF which was recently strengthened by [14] to also rule out functions of constantly many LTFs as hypotheses.
sections.heading: 1.4 Overview of Algorithmic Results
sections.text: Algorithm for LLP-LTF. Given a satisfiable instance of LLP-LTF we can first assume by slightly translating the constant part of the unknown satisfying LTF that it classifies all the feature-vectors of the instance with a non-zero margin. Next, we observe that there are strict quadratic constraints (over the coefficients of the LTF) that distinguish the monochromatic from the non-monochromatic bags. Indeed, consider the unknown LTF pos(〈c∗,x〉) (WLOG by appending a last coordinate with value 1 to all feature-vectors x of the instance) that satisfies all bags. Then, 〈c∗,xi〉〈c∗,xj〉 is positive for monochromatic bags and negative for the non-monochromatic ones whose constituent vectors are xi
  and xj . Taking C = c∗cT∗ we obtain the same conditions for x T i Cxj , which are constraints linear in the entries of positive semi-definite (psd) C, and can be efficiently solved for C using a semi-definite program (SDP). Using the psd decomposition C = LTL we map xi to the vector zi := Lxi so that 〈zi, zj〉 = xTi Cxj . From here, the random hyperplane rounding of zi to 〈g, zi〉 (g ← N(0, 1)d) yields an LTF pos(h(xi)) = pos(〈g, zi〉) that separates (in expectation) the vectors of at least half of the non-monochromatic bags and at most half of the monochromatic ones. Taking the better of pos(h(x)) and pos(−h(x)) satisfies in expectation at least half of the non-monochromatic bags and at least one-fourths of the monochromatic ones. Combining this with the known linear programming algorithm that satisfies all the monochromatic bags we obtain the desired (2/5)-approximation.
  Algorithm LLP-OR. Given a satisfying OR we can write an equivalent LTF with a margin property – the thresholded linear form has value either (−1/2) if the OR evaluates to 0, and otherwise takes values in the range [1/2, d]. This allows us to add margin terms in the SDP constraints corresponding to the bags. The rest of the algorithm mapping xi to zi remains the same, while the strengthened constraints imply an extra Ω(1/d) in the probabilities that the random hyperplane rounding separates the vectors of non-monochromatic bags and does not separate those of monochromatic bags, yielding a corresponding improvement in the fraction of satisfied bags.
sections.heading: 1.5 Overview of Hardness Result
sections.text: For this exposition of the proof techniques we focus only on a weaker version of Theorem 1.2 for one LTF rather than functions of constantly many LTFs as hypothesis. The proof is obtained via a reduction from a variant of the (by now standard) Label Cover problem. This consists of a bi-regular bipartite graph (V,U,E) where vertices in V and U have to be assigned labels from [M ] and [m] respectively for some M > m. Each edge e = (v, u) ∈ V × U is a constraint with a projection πv,u : [M ]→ [m] and is satisfied by the labels lv and lu for v and u respectively if πv,u(lv) = lu. It is NP-hard to distinguish whether a Label Cover instance is completely satisfiable (“Yes” case) , or any labeling satisfies only an o(1)-fraction of edges (“No” case).
  The goal of the reduction is to transform a Label Cover instance L to an LLP-OR instance of only non-monochromatic 2-sized bags s.t. (i) if L is a Yes instance there is an OR satisfying all the bags, (ii) if L is a No instance then there is no LTF satisfying more than (1/2 + o(1))-fraction of the bags.
  The above template of reduction from Label Cover and its variants has been widely used to prove hardness results, including in computational learning by the previous works mentioned in this section. The main technical ingredient for such reductions is a dictatorship test tailored to transform a specific local collection of variables/constraints of L into a sub-instance of the target problem. This is done by defining a coordinate in the feature-space for each variable of L and its label, and then constructing the feature-vectors and bags of the sub-instances in this space - zeroing out coordinates corresponding to variables not in the local collection. Taking the union the sub-instances for all local collections yields the hard instance of the target problem, in our case LLP-OR.
  Our dictatorship test needs to satisfy the following meta-properties, (i) completeness: any labeling satisfying the local collection of Label Cover constraints yields a good solution to the sub-instance i.e., an OR that satisfies all its bags, and (ii) soundness: any good enough solution to the sub-instances i.e., an LTF satisfying more than half the bags on average over the sub-instances, should be independently decodable into a labeling satisfying the local constraints. This notion of decodability is crucial, it depends on the fact (by design) that the good solution LTF will have coefficients on the disjoint sets of coordinates corresponding to each Label Cover variable. An independent decoding is any randomized procedure selecting a label for each variable considering only the LTF coefficients of the coordinates corresponding to that variable. In the next few paragraphs we motivate the design of our dictatorship test and provide an overview of its completeness and soundness analyses.
sections.heading: 1.5.1 Dictatorship test construction
sections.text: We fix as our local collection any two vertices v, w ∈ V which are neighbors of some u ∈ U in L with πv,u and πw,u being the respective projections. Making sure that completeness holds is usually straightforward. For the soundness we want to ensure that if the LLP-OR sub-instances have an LTF satisfying more (1/2 + δ)-fraction of the bags (on an average over the local collections) then there should be independent decodings of v and w assigning labels lv and lw s.t. πv,u(lv) = πw,u(lw) with significant probability depending on δ. We call such lv and lw consistent labels. To begin, we
  provide a first cut approach and illustrate its shortcomings to provide the insights for developing the actual dictatorship test used in our reduction.
  First Cut Approach. For v and w we have a separate set of [M ] boolean coordinates denoted by the boolean variables {Xv,i}Mi=1 and {Xw,i}Mi=1. Let us construct a distribution that samples bags with two feature-vectors X(1) and X(2), the former supported only on {Xv,i}Mi=1 and the latter other only on {Xw,i}Mi=1, such that the OR formula (Xv,lv ∨Xw,lw) for any consistent labels lv and lw evaluates to 1 exactly on one of them. One way to do this is as follows. Sample a random set Jv by choosing each j ∈ [m] w.p. 1/2 and let Jw := [m] \ Jv. Then, (i) for each j ∈ Jv set X(1)v,i = 1 for all i ∈ π−1v,u(j) and X (2) w,i = 0 for all i ∈ π−1w,u(j), and (ii) for each j ∈ Jw set X (1) v,i = 0 for all i ∈ π−1v,u(j) and X (2) w,i = 1 for all i ∈ π−1w,u(j); with the undefined coordinates in X(1) and X(2) set to 0. This distribution – call it D0 – then outputs a non-monochromatic bag B containing X(1) and X(2). It is easy to verify that exactly one of (X(1)v,lv ∨X (1) w,lw ) = X (1) v,lv and (X(2)v,lv ∨X (2) w,lw ) = X (2) w,lw evaluate to 1 for any consistent labels lv and lw. Therefore, this dictatorship test given by D0 satisfies the completeness property. Unfortunately however, it does not have the soundness property. To see this, suppose that the pre-images of the two projections are all of the same size d i.e,
  ∣∣π−1v,u(j)∣∣ = d and
  ∣∣π−1v,u(j)∣∣ = d for all j ∈ [m], implying M = md. Then, the linear threshold pos(h(X)) where h(X) := ∑m i=1 (Xv,i +Xw,i)−M/2, evaluates to 1 exactly on one of X(1) and X(2) w.p. 1 when
  m is odd and w.p. 1−O(1/ √ m) if m is even. Thus, pos(h) which is a majority-threshold is a good solution. However, h has equal weight on each of its {Xv,i}Mi=1 and {Xw,i}Mi=1 coordinates, so any independent decoding of v and w using the corresponding coefficients of h will yield consistent labels with probability only around O(1/M), much lower than desired.
  Final Dictatorship Test. The problem with D0 is that the total number of 1s in X(1) and X(2) together is exactly M and therefore the majority threshold works. If the coordinates were real-valued this could be mitigated by choosing the non-zero coordinates from some range of values randomly, introducing enough variability in the sum to fool the majority threshold. While this of course is not possible in the boolean case, we employ the following trick to achieve a similar effect: replace each original coordinate with some large number of new coordinates. When the original coordinate was set to zero set all the corresponding new ones to zero, and when the original was set to 1, sample the new ones from some distribution such that (i) at least one of the new coordinates is always 1, and (ii) the number of 1s sampled has a large variation. In particular, we replace Xv,i (i ∈ [M ]) with {Xv,i,b,q | b ∈ {0, 1}, q ∈ [Q]} for some large Q. The vector X(1) is constructed as follows. For all i s.t. πv,u(i) ∈ Jv independently, we first sample b = (1 − a) ∈ {0, 1} u.a.r. then set exactly one u.a.r. chosen value from {X(1)v,i,b,r} Q r=1, to 1 and rest to zero. Further, after choosing J
  v, a random subset Jvε ⊆ Jv is chosen by including every j ∈ Jv with probability ε. For those i s.t. πv,u(i) ∈ Jvε the variables {X(1)v,i,a,r} Q r=1 are sampled iid unbiased {0, 1}-Bernoulli. We can think of Jvε be those blocks of coordinates which introduce the variability in the number of 1s due the fact that while a given j ∈ Jv is included in Jvε with probability only ε, once it is then roughly half of the coordinates in X(1) corresponding to i ∈ π−1v,u(j) are sampled (as iid Bernoulli) to be 1, rather than ∼ 1/Q fraction. For a choice ε > 0 letting Q to be sufficiently larger than 1/ε yields the desired variation.
  The coordinates Xw,i (i ∈ [M ]) are analogously replaced with {Xw,i,b,q | b ∈ {0, 1}, q ∈ [Q]}, and a similar process using Jwε ⊆ Jw is followed to sample the new variables for the point X(2).
  With the above transformations, D0 is replaced by the distribution D which samples vectors X(1) and X(2) now over the extended coordinate sets corresponding to v and w respectively. Since we maintain the property that if the original coordinate Xv,i was 1 then at least one of {Xv,i,0,r, Xv,i,1,r}Qr=1 is set to 1, and when the former was 0 then the latter are all 0 as well (similarly for Xw,i), we still
  have that (∨ b∈{0,1} ∨Q q=1Xv,lv,b,q ) ∨ (∨ b∈{0,1} ∨Q q=1Xw,lw,b,q ) for consistent labels lv and lw,
  satisfies all the bags sampled from D. On the other hand, the soundness analysis for D is quite lengthy and technical, and we provide below an informal description of the main steps involved and the techniques used for them, using some convenient simplified notation.
  Consider a linear form h on the above set of coordinates and a candidate solution pos(h(X)) to the dictatorship test. For simplicity let us assume that it does not have any constant term. If cv and cw
  are the coefficient vectors of h restricted to the coordinates corresponding to v and w separately, then pos(h(X(1)) = pos(〈cv,X(1)〉) and pos(h(X(2)) = pos(〈cw,X(2)〉). For v let the weight of its label i be given by ‖cv,i‖22 = ∑ b,q c 2 v,i,b,q with the total weight of cv being ‖cv‖22 normalized to 1. Using the notion of critical index with small parameter τ > 0 we partition [M ] into subsets regv of regular coordinates which all have weight at most τ , topv of the top-K (for some large enough K) non-regular coordinates in terms of their weight, and torsov of the rest of the coordinates. Let hv, hvtop, h v reg and h v tor be the linear forms on X
  (1) given by the restrictions of cv to coordinates in [M ], topv , regv and torsov respectively. Similarly we obtain for w the subsets topw, torsow, regw of coordinates and the restrictions hw, hwtop, h w reg and h w tor.
  For the soundness analysis of D we assume that h does not admit a consistent independent decoding of v and w, and based on this wish to show that the distributions pos(h(X(1))) and pos(h(X(2))) are independent of each other. We do this through the following arguments.
  Truncation: hvtor(X (1)), hwtor(X (2)) are too small to affect the value of pos(h(X(1)) and pos(h(X(2)) respectively, with any significant probability. This uses an anti-concentration result of [14] applied to hvtop and h w top.
  Non-Intersection. πv,u(topv) ∩ πw,u(topw) = ∅. Further, the total weights of coordinates in regv ∩ π−1v,u (πw,u(topw)) and those in regw ∩ π−1w,u (πv,u(topv)) are tiny. If not, one could select a label for v from either w.p. 1/2 choosing randomly from topv , or w.p. 1/2/ sampling one from regv with probability proportional to its weight, and do a similar independent decoding for w, yielding a consistent labeling with significant probability, thereby contradicting our assumption above.
  Decoupling the regular parts. We show that with high probability over the choice of Jv, the distribution of hvreg(X
  (1)) is close to a fixed Gaussian random variable. This is via an application of the Berry-Esseen theorem after a series of estimates on the conditional (on choice of Jv) mean and variance of hvreg(X (1)). We obtain the same for Jw and hwreg.
  Using the truncation argument, one can ignore the contribution of hvtor and h w tor. From the non-intersection and decoupling arguments we obtain that pos(hvreg(X (1)) + hvtop(X
  (1)) and pos(hwreg(X (2)) + hwtop(X (w)) are independent of each other. A short argument averaging over all pairs of neighbors v, w of a given u shows that the fraction of bags satisfied (on an average over the choice of v and w) is at most 1/2 + o(1).
  In several steps of the above arguments we are aided by the smoothness property of the the Label Cover variant (see Sec. 3) which allows us to assume that in any pre-image π−1v,u(j) there is at most one coordinate either from topv or of weight greater than 1/poly(d), where d is the pre-image size of the Label Cover projections. Overall, our analysis follows (at a high level) the analytical approach of [12] and [14], though our decoupling step is more involved as it requires sharper as well as conditional bounds to obtain invariance as a high probability statement over the choice of Jv .
  Finally, extending our analysis to rule out functions of constantly many LTFs considerably complicates the above arguments. In particular, we apply the multi-dimensional version of the Berry-Esseen theorem to do the decoupling step. For this, we add additional noise to the hreg parts to lower bound the smallest eigenvalue of a correlation matrix which determines the error bounds when applying the multi-dimensional version of this theorem.
  2 Approximation for LLP-LTF on bags of size 2
  Let I = (X,B = {B1, . . . , Bm}, {σk}mk=1) be a satisfiable instance of LLP-LTF. We begin with the following simple lemma which implies that the existence of an LTF satisfying all the bags of I while classifying each point of the instance with non-zero margin. Lemma 2.1. There is an LTF pos(f(x)) that satisfies all the bags of I, along with |f(x)| > 0 for all x ∈ ∪mj=1Bj .
  Proof. By definition there is an LTF pos(g(x)) that satisfies all the bags of I. Since pos(z) = 1{z>0} and the total number of feature vectors in the bags is finite, the quantity κ given by
  κ := min { g(x) | x ∈ ∪mj=1Bj , pos(g(x)) = 1 } (1)
  satisfies κ > 0. Thus, we obtain the desired linear form f by decreasing the constant term of g by exactly κ/2, ensuring that f(x) ≥ κ/2 if g(x) > 0, and f(x) ≤ −κ/2 if g(x) ≤ 0, ∀x ∈ ∪mj=1Bj .
  We first provide in Fig. 1 a SDP based algorithm A and prove the following lemma. Lemma 2.2. Algorithm A (Fig. 1) satisfies in expectation half of the non-monochromatic bags and one-fourth of the monochromatic bags.
  Proof. Let pos(f(x)) be the LTF given by Lemma 2.1 satisfying all the bags of I. Letting x̃ as defined in Step 1 of A along with the non-zero margin of pos(f(x)) implies that there is some c∗ ∈ Rd+1 such that:
  〈c∗, x̃i〉〈c∗, x̃j〉 = x̃Ti ( c∗c T ∗ ) x̃j ≤ 0 ∀{xi,xj} = Bk s.t. |Bk| = 2, σk = 0.5 (5)
  〈c∗, x̃i〉〈c∗, x̃j〉 = x̃Ti ( c∗c T ∗ ) x̃j ≥ 0 ∀{xi,xj} = Bk s.t. |Bk| = 2, σk 6= 0.5 (6)
  〈c∗, x̃i〉〈c∗, x̃i〉 = x̃Ti ( c∗c T ∗ ) x̃i > 0 ∀xi ∈ ∪mj=1Bj . (7)
  Thus, C = c∗cT∗ satisfies (2), (3) and (4). and the SDP solved by A is feasible. Let C = L TL denote a solution and its psd decomposition. For each i ∈ [n] consider the vector zi ∈ Rd+1 given by zi := Lx̃i ∈ Rd+1. Observe that 〈zi, zj〉 = 〈Lx̃i,Lx̃j〉 = x̃Ti LTLx̃j = x̃Ti Cx̃j , for i, j ∈ [n]. This, along with (2), (3), and (4) yields,
  〈zi, zj〉 ≤ 0 ∀{xi,xj} = Bk s.t. |Bk| = 2, σk = 0.5 (8) 〈zi, zj〉 ≥ 0 ∀{xi,xj} = Bk s.t. |Bk| = 2, σk 6= 0.5 (9) ‖zi‖ > 0 ∀xi ∈ ∪mj=1Bj (10)
  Let g be as in the algorithm and note that as defined in Step 4 of A, h(xi) = 〈Lx̃i,g〉 = 〈zi,g〉. Thus, {pos(h(xi))}ni=1 is a random hyperplane rounding of the vectors {zi}ni=1. Using this observation along with (8), (9) and standard geometric facts (see Appendix A of the supplemental) we obtain:
  Pr [pos(h(xi)) 6= pos(h(xj))] ≥ 1/2 ∀{xi,xj} = Bk s.t. |Bk| = 2, σk = 0.5 (11) Pr [pos(h(xi)) = pos(h(xj))] ≥ 1/2 ∀{xi,xj} = Bk s.t. |Bk| = 2, σk 6= 0.5 (12) Pr [pos(h(xi)) = pos(h(xi))] = 1 ∀{xi} = Bk (13)
  where the last equation for bags of size 1 is trivially true. Further, (10) implies that over the choice of g the values of all the h(xi) occurring in the above three equations are non-zero almost surely i.e., with probability 1. This implies that pos(h(x)) = 1 − pos(−h(x)) for all x ∈ ∪mj=1Bj , with probability 1. Thus, it can be seen that both pos(h) and pos(−h) satisfy all the non-monochromatic bags B = {xi,xj} such that pos(h(xi)) 6= pos(h(xj)). Furthermore, at least one of pos(h) and pos(−h) satisfy half of the monochromatic bags B which have vectors xi,xj (xi = xj if |B| = 1) for which pos(h(xi)) = pos(h(xj)). This implies that pos(h∗) returned by A satisfies in expectation at least half of the non-monochromatic bags and one-fourth of the monochromatic bags.
  Proof. (of Theorem 1.1 for LLP-LTF) We use A in combination with the linear programming method A that is guaranteed to satisfy all monochromatic bags. If the fraction of monochromatic bags q is at least 2/5 of the total bags, then A finds an LTF to satisfy all of them. Otherwise, A finds one to satisfy (in expectation) q/4 + 1/2(1− q) = 1/2− q/4 ≥ 1/2− 2/20 = 2/5 fraction of the bags. If q = 0 i.e., all bags are non-monochromatic the LTF satisfies 1/2-fraction of the bags.
  2.1 Special Case: LLP-OR
  Let I be a satisfiable instance of LLP-OR. We have xi ∈ {0, 1}d (i ∈ [n]) and there is boolean OR function f of the form:
  f(x) = ∨ s∈Sf1 xs + ∨ s∈Sf0 ¬xs, x ∈ {0, 1}d, (14)
  for disjoint subsets Sf1 , S f 0 ⊆ [d] such that f satisfies each bag of the instance I. Observe that for any x ∈ {0, 1}df(x) = 1⇔ ∑ s∈Sf1 xs + ∑ s∈Sf0 (1− xs) ≥ 1  , f(x) = 0⇔ ∑ s∈Sf1 xs + ∑ s∈Sf0 (1− xs) = 0  (15) Let us define cf = (cf1 , . . . , c f d , c f d+1) ∈ Rd+1 as cfs = 1 if s ∈ S f 1 , else c f s = −1 if s ∈ S f 0 , else
  cfs = ∣∣∣Sf0 ∣∣∣ − 1/2 if s = d + 1, and cfs = 0 otherwise. Then, letting x̃ = (x1, . . . , xd, 1), (15) is transformed to[ f(x) = 1 ⇔ 〈cf , x̃〉 ∈ [1/2, d− 1/2] ] , [ f(x) = 0 ⇔ 〈cf , x̃〉 = −1/2 ] (16)
  Given the above it can be seen that
  〈cf , x̃i〉〈cf , x̃j〉 ≤ −1 4d
  ( 〈cf , x̃i〉2 + 〈cf , x̃j〉2 ) ∀{xi,xj} = Bk s.t. |Bk| = 2, σk = 0.5
  〈cf , x̃i〉〈cf , x̃j〉 ≥ 1
  4d
  ( 〈cf , x̃i〉2 + 〈cf , x̃j〉2 ) ∀{xi,xj} = Bk s.t. |Bk| = 2, σk 6= 0.5
  Thus, one modifies the algorithm in Fig. 1 to obtain A′ by replacing (2) and (3) with
  x̃Ti Cx̃j ≤ −1 4d
  ( x̃Ti Cx̃i + x̃ T jCx̃j ) ∀{xi,xj} = Bk s.t. |Bk| = 2, σk = 0.5 (17)
  x̃Ti Cx̃j ≥ 1
  4d
  ( x̃Ti Cx̃i + x̃ T jCx̃j ) ∀{xi,xj} = Bk s.t. |Bk| = 2, σk 6= 0.5 (18)
  Following the same analysis as in the LTF case, noting that ‖zi‖2 = x̃Ti Cx̃i > 0 for any i ∈ [m] (by (10)), and using the AM-GM inquality we obtain that:
  〈zi, zj〉 ‖zi‖‖zj‖ ≤ −1 4d
  ( ‖zi‖2 + ‖zj‖2
  ‖zi‖‖zj‖
  ) ≤ −1
  2d ∀{xi,xj} = Bk s.t. |Bk| = 2, σk = 0.5 (19)
  〈zi, zj〉 ‖zi‖‖zj‖ ≥ 1 4d
  ( ‖zi‖2 + ‖zj‖2
  ‖zi‖‖zj‖
  ) ≥ 1
  2d ∀{xi,xj} = Bk s.t. |Bk| = 2, σk 6= 0.5 (20)
  Therefore, from standard geometric facts (see Appendix A of the supplemental), the random hyperplane rounding of the {zi}ni=1 yields probabilities 1/2 + Ω(1/d) instead of 1/2 in (11) and (12). Following the rest of the arguments as in the LLP-LTF case we obtain the following lemma. Lemma 2.3. The algorithm A′ described above satisfies at least (1/2 + α0/d)-fraction of the nonmonochromatic bags and (1/4 + α0/2d)-fraction of the monochromatic bags in expectation, for some positive constant α0 ∈ (0, 1].
  Proof. (of Theorem 1.1 for LLP-OR) The guarantee of the linear programming algorithm A satisfying all monochromatic bags case holds for LLP-OR as well. Thus, if the fraction of monochromatic bags x is greater than 2/5 + α0/(8d) then A obtains an LTF that satisfies all the monochromatic bags. Otherwise, A′ from Lemma 2.3 finds one to satisfy (1/2 +α0/d)(1− x) + x(1/4 +α0/2d) fraction of the bags which is at least (1/2 + α0/d) − (2/5 + α0/(8d))(1/4 + α0/2d) ≥ (2/5 + α0/(4d)) since α0 ∈ (0, 1] and d ≥ 1. If x = 0 i.e., all bags are non-monochromatic the LTF satisfies (1/2 + α0/d)-fraction of the bags.
sections.heading: 2.2 Experimental Evaluation
sections.text: We evaluate Algorithm A (Fig. 1) on synthetically generated satisfiable LLP-LTF instances over dimension d ∈ {10, 40, 100} and number of bagsm ∈ {50, 100, 200}. For each (d,m) the algorithm solves 100 independently generated instances - each by choosing a random satisfying linear form f (with iid N(0, 1) coefficients) and m bags independently, for each bag sampling two points iid from N(0, 1)d with their label proportions given by pos(f(x)). Note that the bags and their constituent points are not correlated with f .
  For each instance the SDP in (2)-(4) is solved and the best h∗ chosen using 100 independent Gaussians g. With m0 and m1 denoting the number of monochromatic and non-monochromatic bags respectively, the theoretical performance threshold is given by t := (m0/4 +m1/2) (Lemma 2.2). We measure s as the number of bags satisfied by pos(h∗) and the average and minimum values of (s/t) over the 100 instances per (d,m), both of which are quite a bit larger than 1, showing that the algorithm performs much better than than the theoretical guarantee on such instances. We also compute r as the number of bags satisfied by the best {pos(h′), pos(−h′)} out of 100 random linear forms h′, and the average value of (r/s). The latter is below 1 in all cases indicating that our algorithm performs better on average than the random linear threshold with the gap being higher when d is smaller. The results are presented in Table 1.
  In the previous evaluation, for larger d we observe only small gap between the performance of A and the random linear threshold. Our next experiment shows that this is not the case on instances with bags/points that are correlated to f . Here we choose f passing through origin and random monochromatic bags having two points on the unit sphere which are nearly diametrically opposite and random non-monochromatic bags having two points on the unit sphere very close to each other. We reduce the number of trials to 5: taking the output of A from best of 5 samples of g as pos(h∗), and the best {pos(h′), pos(−h′)} out of 5 random linear forms h′. The results are in Table 2. Unsurprisingly, due to this geometry of points, the performance of the random linear thresholds (avg r, avg (r/s)) is much worse than before. On the other hand h∗ given by A performs better than before as the SDP is more discriminative and its solution C is highly correlated to f .
  Table 1: Results on random 2-sized bags with iid points uncorrelated with satisfying linear form f . 100 instances per (d,m) row.
  d m avg m0 avg m1 avg t avg s avg
  (s
  t
  )
  min
  (s
  t
  )
  avg r avg
  (r
  s
  )
  10 50 27.20 22.80 18.20 39.24 2.162 1.714 33.09 0.847 10 100 52.98 47.02 36.76 85.26 2.325 1.949 64.12 0.754 10 200 105.83 94.17 73.54 181.95 2.479 2.217 125.04 0.688 40 50 25.94 24.06 18.52 29.12 1.574 1.405 28.83 0.993 40 100 50.59 49.41 37.35 54.59 1.462 1.316 53.26 0.978 40 200 101.43 98.57 74.64 104.96 1.406 1.265 100.70 0.961 100 50 24.97 25.03 18.76 28.74 1.533 1.317 28.28 0.987 100 100 50.06 49.94 37.48 52.08 1.390 1.266 51.49 0.990 100 200 100.04 99.96 74.99 97.24 1.297 1.216 96.58 0.994
  Table 2: Results on random 2-sized bags with points highly correlated with satisfying linear form f . 100 instances per (d,m) row.
  d m avg m0 avg m1 avg t avg s avg
  (s
  t
  )
  min
  (s
  t
  )
  avg r avg
  (r
  s
  )
  10 50 25.73 24.27 18.57 48.74 2.632 1.200 2.37 0.049 10 100 49.94 50.06 37.52 98.17 2.619 2.222 5.19 0.053 10 200 98.58 101.42 75.36 199.61 2.650 2.500 8.86 0.044 40 50 24.81 25.19 18.80 47.19 2.517 1.639 2.54 0.055 40 100 49.36 50.64 37.66 96.77 2.574 1.176 4.36 0.045 40 200 99.26 100.74 75.18 195.42 2.601 2.135 8.59 0.044 100 50 24.92 25.08 18.77 46.05 2.460 1.105 2.62 0.060 100 100 50.70 49.30 37.33 93.20 2.498 1.139 4.21 0.046 100 200 99.26 100.74 75.18 189.85 2.527 1.462 8.69 0.046
sections.heading: 3 Smooth Label Cover and Statement of Hardness Reduction
sections.text: The Smooth-Label-Cover problem is defined as follows.
  Definition 3.1. A Smooth-Label-Cover instance L((VL, UL, EL ⊆ VL × UL),M,m, {πv,u}(v,u)∈EL) consists of a bi-regular connected bipartite graph with vertex sets VL, UL, a directed edge set EL, and a set of projections {πv,u : [M ] 7→ [m]}(v,u)∈EL . A labeling σ := (σV , σU ) s.t. σV : VL 7→ [M ] and σU : UL 7→ [m] is said to satisfy an edge (v, u) if πv,u(σV (v)) = σU (u).
  The hardness of Smooth-Label-Cover is given by the following theorem (see Appendix B.2 of the supplemental).
  Theorem 3.2. There exists an absolute constant κ0 > 0 such that for all integer parameters z and J , it is NP-Hard to distinguish whether an instance L of Smooth-Label-Cover with M = 7(J+1)z and m = 2z7Jz , satisfies,
  • YES: There exists a labeling σ := (σV , σU ) which satisfies all the edges. • NO: There is no labeling σ which satisfies more than 2−κ0z-fraction of the edges.
  Additionally, L satisfies the following properties:
  • (Smoothness) For every vertex v ∈ V and for a randomly sampled edge (v, u) incident on v, Pru∼v [πv,u(i) = πv,u(j)] ≤ 1J , for any fixed pair of distinct labels i, j ∈ [M ]. • For any edge (v, u), and any label j ∈ [m], |π−1v,u(j)| ≤ d, where d = 4z .
  The hardness reduction from the above to LLP-OR is given below:
  Theorem 3.3. For any constants δ > 0 and ` ∈ Z+, there is a polynomial time reduction from an instance L of Smooth-Label-Cover given by Theorem 3.2 with J and z depending only on δ and `, to an instance I of LLP-OR with only non-monochromatic 2-sized bags such that:
  • (Completeness) If L is a YES instance then there is a monotone OR that satisfies all the bags of I. • (Soundness) If L is a NO instance then there is no function of at most ` LTFs that satisfies more
  than 1/2 + δ fraction of the bags of I
  Due to lack of space, the proof of the above theorem is omitted and appears in Appendices C and D of the supplemental.
sections.heading: 4 Conclusions and Future Work
sections.text: We present in this work the first study of the proper learnability of LTFs from label proportions, on bags of size at most two. Defining this formally as the LLP-LTF problem and the special case of learning OR using LTFs as LLP-OR (in Section 1.2) we give efficient algorithms to compute an LTF satisfying (2/5)-fraction of the bags of a satisfiable LLP-LTF instance, and (1/2)-fraction of them if all bags are non-monochromatic. For satisfiable LLP-OR over d-dimensional boolean vectors we improve these factors to (2/5 + Ω(1/d)) and (1/2 + Ω(1/d)) respectively. In our main (and most technically challenging) result we prove the NP-hardness of satisfying using any function of constantly many LTFs more than (1/2 + o(1))-fraction of bags of an instance of LLP-OR with only non-monochromatic 2-sized bags all guaranteed to be satisfiable by some monotone-OR, thus establishing the optimality of our algorithms for the non-monochromatic bags case.
  While the above we feel, is notable progress in understanding the complexity of LLP-LTF, there are many interesting related directions for future work. First is resolving the gap between the (2/5)-factor algorithm and the (1/2 + o(1))-factor hardness. Obtaining efficient proper learning algorithms for larger bag sizes is a natural followup problem. Whether using more complicated hypotheses – like polynomial-threshold functions (PTFs) – allows us to obtain better bounds for LLP learning LTFs is another important question. Proving NP-hardness results ruling PTFs out as good classifiers seems challenging – and is open even for agnostically learning noisy ORs in supervised-learning. All these questions can also be studied for other classes such as DNF-formulas. We hope that our work along with this rich landscape of open questions generates further interest in the study of learnability of common concept classes from label proportions.
title: Learnability of Linear Thresholds from Label Proportions