On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning
muliti-instance partial label learning;weakly-supervised learning;neurosymbolic learning;learning theory;long-tailed learning;learning imbalances;class-specific error bounds
Yes
No ethics review needed.
How hard is it to generalize the theory to allow transition $\sigma$ to be instance-dependent and how will that change the analysis? I think the proofs in Patrini et al., 2017 can be naturally adapted to instance-dependent noise by letting noise transitions $T$ depend on $x$.
The exploration of class-specific risk in MI-PLL settings is a novel angel. The theory is sound and robust. The proposed algorithms lead to empirical improvements.
This paper addresses Multi-Instance Partial Label Learning (MI-PLL). The primary contributions are :  1. a theoretical characterization of class-specific learning imbalances in MI-PLL; 2. practical algorithms for mitigating these imbalances at training and testing stages.
I'm a bit concerned on the assumption that the transition $\sigma$ is instance-independent. I'm not sure how consistent it is with the real-world datasets. I think recent literatures on learning with noise and domain changes assume instance-dependent transitions (e.g. https://www.arxiv.org/pdf/2408.16189).
Yes
No ethics review needed.
a).	In line 301, why is each training sample uniquely associated with a Boolean formula of $R_{\ell}$ disjuncts of the form $\Phi_{\ell} := \psi_{\ell, 1} \vee \ldots \vee \psi_{\ell, R_n}$? Is each $\psi_{i, t}$ a bool variable or a function? How to determine $ R_{\ell}$. 
b).	In line 302, why it is that “Formula $\Phi_{\ell}$ encodes the valid label assignments for the $\ell$-th partial training sample subject to $\simga$ and $s_{\ell}$?
c).	Can you show that “Each disjunct in Φℓ is a conjunction of Boolean variables from $\{q_{\ell,i,j}\}_{i,j}$, where $q_{\ell,i,j}$ is true if and only if $x_{\ell, i}$ is assigned to the $j$-th label in $\mathcal{Y}$”.
d)    The introduction of $\alpha_{\ell, t\}$ is also not easy-to-follow.
e)    Exact definition of $\Phi_{\sigma}$ in Section 4.1 is missing.
1. They derive class-specific error bounds that depend on the MI-PLL risk under minimal assumptions.
2. They introduce an algorithm to estimate the marginal of the hidden labels.
3. They mitigate learning imbalances at testing-time by modifying the model’s scores to adhere to the estimated ratios.
In the multi-Instance partial label learning problem, the authors provide class-specific error bounds and show that the transition function $\simga$ can significantly impact learning imbalances. On the practical side, we first propose a statistically consistent technique for estimating the marginal of the hidden labels given partial labels. They propose two algorithms that mitigate imbalances at training- and testing-time. The first algorithm assigns pseudo-labels to training data based on a novel linear programming formulation of MI-PLL. The second algorithm uses the hidden label marginals to constrain the model’s prediction on testing data
1. The presentation about the algorithm in Section 4.2 becomes confusing from line 300. I will list my doubts in the questions below.
2. Can you explain why you enforce the first three constraints in Equ. (6)?
3. In experiments, for $\rho = 0$, i.e., the hidden label distribution is unmodified and balanced, the performance of CAROT is even worse than LA under $M=5$.
4. Figure 1 seems to indicate that within 100 epochs, almost all classes are not well classified. Does the model converge in 100 epochs? If not, can you provide the curve after 100 epochs until the network converges?
Yes
No ethics review needed.
Please see above
1. The paper provides a theoretical contribution by analyzing learning imbalances in MI-PLL, offering a deeper understanding of the problem.

2. The authors introduce novel algorithms for both training and testing phases, with empirical evidence.
This paper addresses the problem of learning imbalances in Multi-Instance Partial Label Learning (MI-PLL), where the true labels are hidden and supervision is provided via a transition function. The authors derive theoretical bounds for class-specific risks, and propose methods to estimate hidden label distributions and introduce algorithms to mitigate these imbalances during both training and testing.
1. The notation used in this paper is quite convoluted and makes it really hard to follow. I spent a lot of time carefully reading Section 2, but I still don’t have a clear understanding of what exactly the MI-PLL setting is or how it’s supposed to be used in practice.I would recommend reconsidering whether certain notations, e.g., $r_y = r_{l_j} = r_j$ , are essential in the manuscript. Additionally, including a notation table may be helpful for readers to quickly reference symbols, which would enhance the overall clarity and accessibility of the paper.

2. I understand that the setup in this paper seems different from previous work called MI-PLL, but the motivation of this pape is that earlier "MI-PLL" (which has a different meaning than this paper) methods cannot handling the long-tail issue well. What’s puzzling is that it doesn’t actually compare the proposed approaches to those prior MI-PLL methods in the experiments, which feels really inconsistent.

3. From the algorithmic side, I’m left wondering why the proposed methods should work for long-tail distributions. The explanation for how they handle rare classes is pretty vague, and it’s not easy to see how the approach directly addresses the long-tail problem. And the assumption that transition function is known to the learner is too strong. As far as I know, in weakly supervised learning people generally don't make such strong assumption, but it is crucial to learn the function。
Yes
No ethics review needed.
1. Is Equation 1 introduced by the authors or derived from previous works? I find the mathematical connections a bit challenging to grasp, particularly as it doesn’t seem to directly correspond to the definition of partial risk outlined by Cour et al. If this is an original contribution from your team, shouldn’t Equation 1 be presented as a lemma with accompanying proofs to substantiate its validity?

2. I'm not completely certain, but it appears that Proposition 3.3 suggests the dependency of the empirical partial risk on the imbalance of partial labels, while your measure of complexity (e.g., the Natarajan dimension) remains unaffected by the level of imbalance. If this interpretation is accurate, does this imply that minimizing the partial risk is invariably advantageous in imbalanced MI-PLL scenarios, regardless of the extent of imbalance?
1. This is an theoritically-solid paper - the proofs and theorems appears to be correct and sound.

2. This paper have proposes several notable and interesting theoritical properties, which could be benefical for the future development of MI-PLL.

3. This paper introduces two new algorithms to mitigate imbalances at training and inference time.

4. The proposed method obtained competitive performances comparing with its closest counterparts.
This paper explores a weakly-supervised learning framework that integrates aspects of partial label learning and partial label learning. It presents theoretical contributions by establishing class-specific risk bounds under minimal assumptions and demonstrating the significant impact of transition functions on learning imbalances. Additionally, the paper introduces practical algorithms for estimating hidden label distributions and mitigating learning imbalances at both training and testing phases, achieving performance improvements of up to 14% over strong baselines.
1. This paper becomes challenging to comprehend as the authors have not provided clear definitions of a partial label. Specifically, by examining Example 1.1 alone, the authors' characterization of partial labeling seems to differ from existing work [1].

2. It appears that the authors' proposed method is somewhat orthogonal to their theoretical results, suggesting a divergence between practice and theory.

3. While it is reasonable to assume that imbalances in Multi-Instance Partial Label Learning (MI-PLL) arise not only from label distribution but also from the partial labeling process, the theoretical results of this paper seem to only consider the imbalances caused by partial labeling. This limitation potentially restricts the flexibility and applicability of the theoretical findings.

[1] Learning from Partial Labels, JMLR 2011.
@inproceedings{
anonymous2024on,
title={On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=oZdaEiDBpF},
note={under review}
}
\textit{Multi-Instance Partial Label Learning} (MI-PLL) is a weakly-supervised learning setting encompassing \textit{partial label learning}, \textit{latent structural learning}, and \textit{neurosymbolic learning}. Unlike supervised learning, in MI-PLL, the inputs to the classifiers at training-time are tuples of instances $\mathbf{x}$. At the same time, the supervision signal is generated by a function $\sigma$ over the (hidden) gold labels of $\mathbf{x}$. In this work, we make multiple contributions towards addressing a problem that hasn’t been studied so far in the context of MI-PLL: that of characterizing and mitigating \textit{learning imbalances}, i.e., major differences in the errors occurring when classifying instances of different classes (aka \emph{class-specific risks}). In terms of theory, we derive class-specific risk bounds for MI-PLL, while making minimal assumptions. Our theory reveals a unique phenomenon: that $\sigma$ can greatly impact learning imbalances. This result is in sharp contrast with previous research on supervised and weakly-supervised learning, which only studies learning imbalances under the prism of data imbalances. On the practical side, we introduce a technique for estimating the marginal of the hidden labels using only MI-PLL data. Then, we introduce algorithms that mitigate imbalances at training- and testing-time, by treating the marginal of the hidden labels as a constraint. We demonstrate the effectiveness of our techniques using strong baselines from neurosymbolic and long-tail learning, suggesting performance improvements of up to 14\%.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
muliti-instance partial label learning weakly-supervised learning neurosymbolic learning learning theory long-tailed learning learning imbalances class-specific error bounds
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/94f9984ad46b5bd762a5beb1ab96f87240a9054d.pdf
other topics in machine learning (i.e., none of the above)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/5a3d0d9ff8a66d205cf488447a3df1edea4c80bd.zip
On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission