Hardness of Learning Boolean Functions from Label Proportions

arXiv:2403.19401v1 Announce Type: cross
Abstract: In recent years the framework of learning from label proportions (LLP) has been gaining importance in machine learning. In this setting, the training examples are aggregated into subsets or bags and only the average label per bag is available for learning an example-level predictor. This generalizes traditional PAC learning which is the special case of unit-sized bags. The computational learning aspects of LLP were studied in recent works (Saket, NeurIPS'21; Saket, NeurIPS'22) which showed algorithms …

abstract arxiv bag cs.cc cs.ds cs.lg example examples framework functions importance machine machine learning per subsets training type