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 and hardness for
learning halfspaces in the LLP setting. In this work we focus on the
intractability of LLP learning Boolean functions. Our first result shows that
given a collection of bags of size at most $2$ which are consistent with an OR
function, it is NP-hard to find a CNF of constantly many clauses which
satisfies any constant-fraction of the bags. This is in contrast with the work
of (Saket, NeurIPS'21) which gave a $(2/5)$-approximation for learning ORs
using a halfspace. Thus, our result provides a separation between constant
clause CNFs and halfspaces as hypotheses for LLP learning ORs.
Next, we prove the hardness of satisfying more than $1/2 + o(1)$ fraction of
such bags using a $t$-DNF (i.e. DNF where each term has $\leq t$ literals) for
any constant $t$. In usual PAC learning such a hardness was known (Khot-Saket,
FOCS'08) only for learning noisy ORs. We also study the learnability of
parities and show that it is NP-hard to satisfy more than $(q/2^{q-1} +
o(1))$-fraction of $q$-sized bags which are consistent with a parity using a
parity, while a random parity based algorithm achieves a
$(1/2^{q-2})$-approximation.

学习标签比例 (LLP) 框架在机器学习中日益重要。该研究关注 LLP 学习布尔函数的不可计算性，发现寻找满足 OR 函数一部分常数比例的子集 (包) 的恒定个子句的 CNF 是 NP 困难问题，同时探讨了学习偶函数的可行性，发现利用随机偶算法可以得到近似解。

从标签比例学习布尔函数的难度

Hardness of Learning Boolean Functions from Label Proportions

The ingrained principles of fairness in a dialogue system's decision-making
process and generated responses are crucial for user engagement, satisfaction,
and task achievement. Absence of equitable and inclusive principles can hinder
the formation of common ground, which in turn negatively impacts the overall
performance of the system. For example, misusing pronouns in a user interaction
may cause ambiguity about the intended subject. Yet, there is no comprehensive
study of equitable text generation in dialogue. Aptly, in this work, we use
theories of computational learning to study this problem. We provide formal
definitions of equity in text generation, and further, prove formal connections
between learning human-likeness and learning equity: algorithms for improving
equity ultimately reduce to algorithms for improving human-likeness (on
augmented data). With this insight, we also formulate reasonable conditions
under which text generation algorithms can learn to generate equitable text
without any modifications to the biased training data on which they learn. To
exemplify our theory in practice, we look at a group of algorithms for the
GuessWhat?! visual dialogue game and, using this example, test our theory
empirically. Our theory accurately predicts relative-performance of multiple
algorithms in generating equitable text as measured by both human and automated
evaluation.

This paper explores equitable text generation in dialogue systems using theories of computational learning, providing formal definitions of equity in text generation and proving formal connections between learning human-likeness and learning equity.