Optimistic Rates for Learning from Label Proportions

We study the Empirical Proportional Risk Minimization (EPRM) learning rule (Yu et al., 2014), which is a natural extension of Empirical Risk Minimization (ERM) to the LLP setting. Concretely we prove that under realizability, $\widehat{f}_{\mathrm{EPRM}}\coloneqq\argmin_{f\in\mathcal{F}}\tfrac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\{\tfrac{1}{k}\sum_{j=1}^{k}f(x_{i,j})\neq\alpha_{t}\}$ achieves the sample complexity guarantee

$\displaystyle n=O\left(\frac{d\log k\cdot\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right).$

However, in the agnostic setting we show that EPRM cannot attain polynomial (in $k$) sample complexity, and similar “folklore” learning rules based on minimization of proportional square or log losses even fail to return a predictor with constant suboptimality.

To address the failure of proportional loss learning rules in the agnostic setting, we consider a simple debiased variant of the proportional square loss. We show that the debiased square loss learning rule $\widehat{f}_{\mathrm{DSQ}}$ achieves the optimistic rate:

$\displaystyle\mathcal{L}(\widehat{f}_{\mathrm{DSQ}})\leq L^{\star}+\widetilde{O}\left(\frac{k^{2}\left(d+\log(1/\delta)\right)}{n}+\sqrt{\frac{L^{\star}\cdot k^{2}\left(d+\log(1/\delta)\right)}{n}}\right),$

where we denote $L^{\star}=\min_{f\in\mathcal{F}}\mathcal{L}(f)$. Here, observe that under realizability (with $L^{\star}=0$), $\widehat{f}_{\mathrm{DSQ}}$ enjoys a fast $1/n$ rate, while in the agnostic setting we recover the $1/\sqrt{n}$ rate, both of which are optimal (up to log factors) in terms of $d$, $\log(1/\delta)$, and $n$.

We study an alternative approach called EasyLLP, which was recently proposed by Busa-Fekete et al. (2023). Specialized to the classification setting, they show a $1/\sqrt{n}$ rate (hiding dependence on $d$, $k$, and $\delta$). We improve upon their result to show an optimistic rate similar to the one achieved by the debiased square loss, showing that EasyLLP can indeed adapt to realizability. Our analysis reveals a curious phenomenon: in the realizable setting, EasyLLP exhibits a separation between loss estimation (which is necessarily $\Omega(1/\sqrt{n})$ even for the optimal predictor $f^{\star}$) and learning (which is $\widetilde{O}(1/n)$ by the optimistic rates guarantee).

We investigate the optimal dependence on the bag size $k$, since our bounds are tight (up to log factors) in the other parameters. A trivial lower bound of $n=\Omega(1/k)$ follows because LLP with $n$ bags is only harder than supervised learning with $nk$ bags. It turns out this cannot be improved in general for all $\mathcal{F}$, but we give an explicit example of a function class $\mathcal{F}$ for which the minimax sample complexity has larger dependence on $k$.

We empirically evaluate gradient-based versions of the learning rules considered herein on binary classification versions of MNIST and CIFAR10 studied in Busa-Fekete et al. (2023) for a wide range of NN architectures. We find that proportion matching and the debiased square loss perform the best; furthermore, we demonstrate that the debiased square loss enjoys faster optimization than proportion matching, as early in training the debiased square loss is a better estimate of the true instance-level loss.

The problem of LLP has been studied in a long line of work (Chen et al., 2006; Musicant et al., 2007; Kück and de Freitas, 2005; Quadrianto et al., 2008). Most works either assume some kind of distributional assumptions on bag/label generation (Kück and de Freitas, 2005; Quadrianto et al., 2008; Patrini et al., 2014; Scott and Zhang, 2020; Zhang et al., 2022), construct bags adaptively (Chen et al., 2023; Javanmard et al., 2024b), or study approaches to minimize a surrogate loss (Rueping, 2010; Yu et al., 2013; Qi et al., 2016; Shi et al., 2019; Dulac-Arnold et al., 2019; Javanmard et al., 2024a). On the computational side, Saket (2021); Saket (2022) shows that even in the realizable setting learning linear thresholds for LLP is NP-hard and study SDP relaxations for this task. Thus, the aforementioned papers are not directly relevant to the goals of this work in providing distribution-free statistical guarantees on classification loss.

Several works provide guarantees on the instance-level classification loss. Yu et al. (2014) introduce the EPRM learning rule. While their main focus is proving guarantees on the proportional risk, they show how to translate these to instance-level guarantees when the bags are “pure”—meaning the label proportions $\alpha_{t}$ are close to $0$ or $1$. They also give numerical bounds which indicate that EPRM achieves instance-level guarantees under realizability. Chen et al. (2023) introduce a similar debiased square loss learning rule and prove a $O(1/\sqrt{n})$ rate in the agnostic setting; while Busa-Fekete et al. (2023) introduce the EasyLLP framework and prove a $O(1/\sqrt{n})$ rate.

Optimistic rates date back to seminal work of Vapnik and Chervonenkis (2015) and were expanded upon by Bousquet (2002); Koltchinskii and Panchenko (2000); Bartlett et al. (2005) using the technique of localized Rademacher complexities. Optimistic rates have been studied in various other contexts such as optimization with smooth losses (Srebro et al., 2010), multi-task learning (Yousefi et al., 2018; Watkins et al., 2023), vector-valued learning (Reeve and Kaban, 2020), and overparameterized regression (Zhou et al., 2021; Zhou et al., 2022; Zhou et al., 2023).

We rewrite our problem as a binary classification problem and apply standard uniform convergence guarantees. Define the function class $\mathcal{G}:\mathcal{X}^{n}\times[0,1]\to\{0,1\}$ as

$\displaystyle\mathcal{G}=\left\{g_{f}:(B,\alpha)\mapsto\mathbbm{1}\left\{\frac{1}{k}\sum_{j=1}^{k}f(x_{j})\neq\alpha\right\}:f\in\mathcal{F}\right\}.$

We claim that $\mathrm{VC}(\mathcal{G})\leq O(d\log k)$. To show this, consider any $X=\{(B_{1},\alpha_{1}),\cdots,(B_{m},\alpha_{m})\}$, and define the projection of $\mathcal{G}$ onto $X$ as $\mathcal{G}_{X}\coloneqq\{(g_{f}(B_{1},\alpha_{1}),\cdots,g_{f}(B_{m},\alpha_{m})):f\in\mathcal{F}\}$. It suffices to show that when $m=O(d\log k)$, the set of labellings for $X$ is of size $\lvert\mathcal{G}_{X}\rvert<2^{m}$. Observe that the labelling of $X$ is determined by the labellings of $\mathcal{F}$ on the $mk$ points, so by Sauer’s lemma $\lvert\mathcal{G}_{X}\rvert\leq(emk/d)^{d}$. Therefore, when $m=O(d\log k)$ we have $\lvert\mathcal{G}_{X}\rvert<2^{m}$.

The EPRM can be written as $\widehat{f}_{\mathrm{EPRM}}\coloneqq\argmin_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\ell^{01}(0,g_{f}(B_{i},\alpha_{i}))$. Applying the uniform convergence guarantee for VC classes (Shalev-Shwartz and Ben-David, 2014, e.g.,), we see that as long as $n=O(\frac{d\log k\cdot\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon})$, with probability at least $1-\delta$ we have

$\displaystyle\Pr_{(B,\alpha)\sim\mathcal{D}}\bigg[\frac{1}{k}\sum_{j=1}^{k}\widehat{f}_{\mathrm{EPRM}}(x_{j})\neq\alpha\bigg]\leq\varepsilon.$

(3)

Henceforth, we will condition on the event in Eq. (3) holding.

Now we show that a proportional risk guarantee of the form Eq. (3) translates to a guarantee on the instance-level loss $\mathcal{L}(\cdot)$. Let $f^{\star}\in\mathcal{F}$ be the optimal predictor that achieves $\mathcal{L}(f^{\star})=0$, and for any $f\in\mathcal{F}$ define $\mathrm{dis}(f,f^{\star})\coloneqq\left\{x\in\mathcal{X}:f(x)\neq f^{\star}(x)\right\}$ to be the disagreement region on which $f$ and $f^{\star}$ disagree. By definition, $\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})=\Pr_{x\sim\mathcal{D}}[x\in\mathrm{dis}(\widehat{f}_{\mathrm{EPRM}},f^{\star})]$. We will show that $\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})\notin[\varepsilon,1-\varepsilon]$.

To do so, we bound the probability that $\widehat{f}_{\mathrm{EPRM}}$ does not match the proportion on a freshly sampled bag. We already have an upper bound on this from Eq. (3). Now we compute a lower bound.

	$\displaystyle\Pr_{(B,\alpha)\sim\mathcal{D}}\bigg[\frac{1}{k}\sum_{j=1}^{k}\widehat{f}_{\mathrm{EPRM}}(x_{j})\neq\alpha\bigg]$	$\displaystyle\geq\Pr_{(B,\alpha)\sim\mathcal{D}}\bigg[\sum_{j=1}^{k}\mathbbm{1}\left\{x_{j}\in\mathrm{dis}(\widehat{f}_{\mathrm{EPRM}},f^{\star})\right\}\text{ is odd}\bigg]$
		$\displaystyle=\frac{1}{2}-\frac{1}{2}\left(1-2\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})\right)^{k}.$		(4)

The first inequality follows because if the bag contains an odd number of points in the disagreement set, then it is impossible for $\widehat{f}_{\mathrm{EPRM}}$ and $f^{\star}$ to have the same proportional label.

For sake of contradiction, suppose that $\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})\in[\varepsilon,1-\varepsilon]$. Then we know $\tfrac{1}{2}-\tfrac{1}{2}(1-2\mathcal{L}(\widehat{f}_{\mathrm{EPRM}}))^{k}\geq\tfrac{1}{2}-\tfrac{1}{2}(1-2\varepsilon)^{k}$. However, if $\varepsilon\in(0,1/2)$, we arrive at a contradiction, since $\varepsilon\in(0,1/2)$ implies that for any bag size $k\geq 2$, we have $1-2\varepsilon>(1-2\varepsilon)^{k}$, which implies that $\varepsilon<\frac{1}{2}-\frac{1}{2}\left(1-2\varepsilon\right)^{k}$, so Eqs. (3) and (4) cannot simultaneously hold. Therefore we must have $\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})\notin[\varepsilon,1-\varepsilon]$.

Now we establish that $\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})\notin[1-\varepsilon,1]$. We claim the following: for any near optimal predictor $\widetilde{f}\in\mathcal{F}_{\varepsilon}\coloneqq\{f\in\mathcal{F}:\mathcal{L}(f)\leq\varepsilon\}$, we must have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\left\{\frac{1}{k}\sum_{j=1}^{k}\widetilde{f}(x_{i,j})\neq\alpha_{i}\right\}<\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\left\{\frac{1}{k}\sum_{j=1}^{k}1-\widetilde{f}(x_{i,j})\neq\alpha_{i}\right\}.$

(5)

Call this event $\mathcal{E}(\widetilde{f})$. From here, the result that $\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})\notin[1-\varepsilon,1]$ follows because if $\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})\in[1-\varepsilon,1]$, then it could not have been the EPRM, as the predictor $1-\widehat{f}_{\mathrm{EPRM}}$ has strictly better empirical proportional risk and also lies in the class $\mathcal{F}$ by the symmetric assumption.

We now prove Eq. (5). Consider any predictor $\widetilde{f}\in\mathcal{F}_{\varepsilon}$. Define the indicator variable $Z_{i}\in\{0,1\}$ as $Z_{i}=\mathbbm{1}\{\frac{1}{k}\sum_{j=1}^{k}\widetilde{f}(x_{i,j})=\alpha_{i}\}\cdot\mathbbm{1}\{\frac{1}{k}\sum_{j=1}^{k}1-\widetilde{f}(x_{i,j})\neq\alpha_{i}\}$. We see that $\left\{\frac{1}{n}\sum_{i}Z_{i}>1/2\right\}\subseteq\mathcal{E}(\widetilde{f})$. We bound the expectation of $Z_{i}$ as:

$\displaystyle\En[Z_{i}]\geq\Pr_{(B,\alpha)\sim\mathcal{D}}\left[\forall x_{j}\in B:x_{j}\notin\mathrm{dis}(\widetilde{f},f^{\star})\text{ and }\alpha\neq\frac{1}{2}\right].$

To lower bound this, we can bound the two events separately. First we have

$\displaystyle\Pr_{(B,\alpha)\sim\mathcal{D}}\left[\forall x_{j}\in B:x_{j}\notin\mathrm{dis}(\widetilde{f},f^{\star})\right]\geq(1-\varepsilon)^{k}\geq\frac{3}{4},$

where the last inequality is true whenever $\varepsilon\leq 1/(4k)$. In addition,

$\displaystyle\Pr_{(B,\alpha)\sim\mathcal{D}}[\alpha\neq 1/2]=1-\Pr_{(B,\alpha)\sim\mathcal{D}}[\alpha=1/2]\geq 1-2^{-k}{k\choose k/2}\geq 1-\frac{1}{\sqrt{3k/2+1/2}},$

by Stirling’s approximation. Using the law of total probability we get

	$\displaystyle 1$	$\displaystyle\geq\Pr_{(B,\alpha)\sim\mathcal{D}}\Big[\forall x_{j}\in B:x_{j}\notin\mathrm{dis}(\widehat{f},f^{\star})\text{ or }\alpha\neq\frac{1}{2}\Big]$
		$\displaystyle=\Pr_{(B,\alpha)\sim\mathcal{D}}\Big[\forall x_{j}\in B:x_{j}\notin\mathrm{dis}(\widehat{f},f^{\star})\Big]+\Pr_{(B,\alpha)\sim\mathcal{D}}\Big[\alpha\neq\frac{1}{2}\Big]$
		$\displaystyle\quad\quad\quad-\Pr_{B}\Big[\forall x_{j}\in B:x_{j}\notin\mathrm{dis}(\widehat{f},f^{\star})\text{ and }\alpha\neq\frac{1}{2}\Big]$
		$\displaystyle\geq\frac{3}{4}+1-\frac{1}{\sqrt{3k/2+1/2}}-\Pr_{(B,\alpha)\sim\mathcal{D}}\Big[\forall x_{j}\in B:x_{j}\notin\mathrm{dis}(\widehat{f},f^{\star})\text{ and }\alpha\neq\frac{1}{2}\Big],$

so therefore

$\displaystyle\Pr_{(B,\alpha)\sim\mathcal{D}}\Big[\forall x_{j}\in B:x_{j}\notin\mathrm{dis}(\widehat{f},f^{\star})\text{ and }\alpha\neq\frac{1}{2}\Big]\geq\frac{3}{4}-\frac{1}{\sqrt{3k/2+1/2}}.$

Whenever $k\geq 11$ the RHS is at least $0.507$. As a consequence by Hoeffding’s inequality, we have $\Pr[\mathcal{E}(\widetilde{f})^{c}]\leq\Pr[\tfrac{1}{n}\sum_{i}Z_{i}\leq 1/2]\leq\exp\left(-2n\cdot 0.07^{2}\right)$. By union bound, we have $\Pr[\exists f\in\mathcal{F}_{\varepsilon}:\mathcal{E}(\widetilde{f})^{c}]\leq\Gamma_{\mathcal{F}}(nk)\cdot\exp\left(-2n\cdot 0.07^{2}\right)$, where $\Gamma_{\mathcal{F}}:\mathbb{N}\to\mathbb{N}$ is the growth function for $\mathcal{F}$. Setting the RHS to $\delta$ and using Sauer’s lemma we get that as long as $n=O\left(d\log k+\log(1/\delta)\right)$, the event $\mathcal{E}(\widetilde{f})$ holds for all $\widetilde{f}\in\mathcal{F}_{\varepsilon}$.

Therefore, with probability at least $1-2\delta$, $\mathcal{L}(\widehat{f}_{\mathrm{EPRM}})\leq\varepsilon$ as long as $\varepsilon\leq 1/(4k)$ and

$\displaystyle n=O\left(\frac{d\log k\cdot\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right).$

After rescaling $\delta$, this concludes the proof of Theorem 1. ∎

Fix any $\varepsilon\in(0,1/2)$ and consider the input space $\mathcal{X}=\{x\}$, with $\mathcal{D}$ given by $(x,1)$ with probability $1/2+\varepsilon$ and $(x,0)$ with probability $1/2-\varepsilon$. Let $\mathcal{F}$ consist of two functions $f_{0}(x)=0$ and $f_{1}(x)=1$. The optimal predictor within the class $\mathcal{F}$ is $f_{1}$. However, observe that the loss estimates for proportion matching are $\widehat{L}(f_{0})\coloneqq 1-\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\{\alpha_{i}=0\}$ and $\widehat{L}(f_{1})\coloneqq 1-\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\{\alpha_{i}=1\}$. For small $\varepsilon$, unless the number of bags is exponential in $k$, with constant probability we do not see any “pure” bags (with $\alpha_{i}=0$ or $\alpha_{i}=1$), so we have no way of distinguishing which of $f_{0}$ and $f_{1}$ achieves smaller loss.

One may object that the previous failure mode is due to the fact that we are using a noncontinuous measure of discrepancy between the predicted and true label proportion, and such issues can be resolved if we minimize a continuous measure of discrepancy. We show that this does not help, as proportion matching approaches can return a predictor with constant suboptimality. This is because in the agnostic setting, the predictor which matches the bag-level proportions may not be the optimal instance-level predictor.

Consider the learning rule that minimizes the proportional square loss:

$\displaystyle\widehat{f}_{\mathrm{SQ}}\coloneqq\argmin_{f\in\mathcal{F}}\widehat{L}_{\mathrm{SQ}}(f)=\frac{1}{n}\sum_{i=1}^{n}\bigg(\frac{1}{k}\sum_{j=1}^{k}f(x_{i,j})-\alpha_{i}\bigg)^{2}.$

(6)

We show that in general, minimizing the proportional square loss can fail in the agnostic setting.

The proportional square loss learning rule, as well as the proportional log loss learning rule

$\displaystyle\widehat{f}_{\mathrm{LOG}}\coloneqq\argmin_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}-\alpha_{i}\cdot\log\bigg(\frac{1}{k}\sum_{j=1}^{k}f(x_{i,j})\bigg)-(1-\alpha_{i})\cdot\log\bigg(1-\frac{1}{k}\sum_{j=1}^{k}f(x_{i,j})\bigg)$

(7)

are regarded as folklore learning rules, and they were evaluated in the context of gradient-based learning (Busa-Fekete et al., 2023). Busa-Fekete et al. show that while gradient-based minimization of either the proportional square or log loss performs well in practice, it can fail in synthetic experimental settings. Proposition 1 demonstrates a simple theoretical failure mode for $\widehat{f}_{\mathrm{SQ}}$. For completeness, in Appendix A we provide a similar result for the failure of $\widehat{f}_{\mathrm{LOG}}$ on the same construction, but note that even in the standard classification setting ($k=1$) it is well known that minimizing surrogate losses like the log loss do not necessarily give guarantees on the classification error in the agnostic setting (Ben-David et al., 2012). Lastly, we remark that Appendix A of Scott and Zhang (2020) shows an example of similar flavor that in the limit as the bag size $k\to\infty$, proportion matching learning rules can suffer constant suboptimality.

Our analysis provides an answer to the question raised by Busa-Fekete et al. (2023) on understanding when proportion matching is consistent. Suppose the learner minimizes the square loss of Eq. (6), $\widehat{L}_{\mathrm{SQ}}(f)=\frac{1}{n}\sum_{i=1}^{n}k\cdot(\frac{1}{k}\sum_{j=1}^{k}f(x_{i,j})-\alpha_{i})^{2}$. (For sake of comparison, we multiply the loss by a factor of $k$.) One can show an optimistic-rate style guarantee for $\widehat{f}_{\mathrm{SQ}}$, albeit one that is weaker than Theorem 2. Let $L_{\mathrm{SQ}}(\cdot)$ denote the expectation of $\widehat{L}_{\mathrm{SQ}}$. In the proof of Theorem 2, we get the following guarantee on $\widehat{f}_{\mathrm{SQ}}$:

$\displaystyle L_{\mathrm{SQ}}(\widehat{f}_{\mathrm{SQ}})\leq\inf_{f\in\mathcal{F}}\bigg\{L_{\mathrm{SQ}}(f)+\widetilde{O}\bigg(\frac{kd+k^{2}\log(1/\delta)}{n}+\sqrt{\frac{L_{\mathrm{SQ}}(f)\cdot k(d+\log(1/\delta))}{n}}\bigg)\bigg\}.$

This bound essentially replaces the instance-level classification error $\mathcal{L}(f)$ with the (larger) $L_{\mathrm{SQ}}(f)$ in Theorem 2. Applying the substitution $L_{\mathrm{SQ}}(f)=\mathcal{L}(f)+B(f)$, where $B(f)\coloneqq(k-1)\left(\En f-p\right)^{2}$, we see that this bound implies

$\displaystyle\mathcal{L}(\widehat{f}_{\mathrm{SQ}})\leq\inf_{f\in\mathcal{F}}\bigg\{\mathcal{L}(f)+B(f)+\widetilde{O}\bigg(\tfrac{kd+k^{2}\log(1/\delta)}{n}+\sqrt{\tfrac{\left(\mathcal{L}(f)+B(f)\right)\cdot k(d+\log(1/\delta))}{n}}\bigg)\bigg\}.$

(9)

When is Eq. (9) a useful bound? Under realizability, we have $\mathcal{L}(f^{\star})=0$ and $B(f^{\star})=0$, and since any minimizer $\widehat{f}_{\mathrm{EPRM}}$ is also a minimizer of $\widehat{L}_{\mathrm{SQ}}(\cdot)$ and vice versa, Eq. (9) recovers the guarantee of Theorem 1, albeit with worse dependence on $k$. More generally, in the agnostic setting, as long as it is possible to achieve a good trade-off between $\mathcal{L}(f)$ and $B(f)$, we expect $\widehat{f}_{\mathrm{SQ}}$ to generalize well. This reasoning suggests why proportion matching learning rules perform well in practice (Busa-Fekete et al., 2023), despite the negative result of Proposition 1. In the modern over-parameterized regime, where the function class at hand (i.e., neural networks) are nearly realizable for the data distribution, Eq. (9) delivers strong guarantees.

Lastly, observe that there is no contradiction between the guarantee of Eq. (9) and the lower bound in Proposition 1: in Proposition 1, there is no predictor for which the two terms $\mathcal{L}(f)$ and $B(f)$ are both small, as the suboptimal predictor has larger classification loss but satisfies $B(f)=0$.