PAC Learning Linear Thresholds from Label Proportions
Anand Brahmbhatt Rishi Saket Aravindan Raghuveer
Learning from label proportions (LLP) is a generalization of supervised
learning in which the training data is available as sets or bags of
feature-vectors (instances) along with the average instance-label of each bag.
The goal is to train a good instance classifier. While most previous works on
LLP have focused on training models on such training data, computational
learnability of LLP was only recently explored by [Saket'21, Saket'22] who
showed worst case intractability of properly learning linear threshold
functions (LTFs) from label proportions. However, their work did not rule out
efficient algorithms for this problem on natural distributions.
  In this work we show that it is indeed possible to efficiently learn LTFs
using LTFs when given access to random bags of some label proportion in which
feature-vectors are, conditioned on their labels, independently sampled from a
Gaussian distribution $N(\mathbf{\mu}, \mathbf{\Sigma})$. Our work shows that a
certain matrix -- formed using covariances of the differences of
feature-vectors sampled from the bags with and without replacement --
necessarily has its principal component, after a transformation, in the
direction of the normal vector of the LTF. Our algorithm estimates the means
and covariance matrices using subgaussian concentration bounds which we show
can be applied to efficiently sample bags for approximating the normal
direction. Using this in conjunction with novel generalization error bounds in
the bag setting, we show that a low error hypothesis LTF can be identified. For
some special cases of the $N(\mathbf{0}, \mathbf{I})$ distribution we provide a
simpler mean estimation based algorithm. We include an experimental evaluation
of our learning algorithms along with a comparison with those of [Saket'21,
Saket'22] and random LTFs, demonstrating the effectiveness of our techniques.