A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Authors: Kosuke Sugiyama
Masato Uchida
Venue: ICML 2025 poster (2025)
Keywords: weak features learning
impute-then-regress
complementary features learning
missing value
weak supervised learning
Primary area: theory->learning_theory
TL;DR: This paper presents a unified framework for learning with low-quality discrete features and analyze the theoretical interplay between feature estimation performance and downstream predictive performance.

Abstract: In many real-world applications, predictive tasks inevitably involve low-quality input features (Weak Features; WFs) which arise due to factors such as misobservations, missingness, or partial observations. While several methods have been proposed to estimate the true values of specific types of WFs and to solve a downstream task, a unified theoretical framework that comprehensively addresses these methods remains underdeveloped. In this paper, we propose a unified framework called Weak Features Learning (WFL), which accommodates arbitrary discrete WFs and a broad range of learning algorithms, and we demonstrate its validity. Furthermore, we introduce a class of algorithms that learn both the estimation model for WFs and the predictive model for a downstream task and perform a generalization error analysis under finite-sample conditions. Our results elucidate the interdependencies between the estimation errors of WFs and the prediction error of a downstream task, as well as the theoretical conditions necessary for the learning approach to achieve consistency. This work establishes a unified theoretical foundation, providing generalization error analysis and performance guarantees, even in scenarios where WFs manifest in diverse forms.

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Kosuke Sugiyama
Masato Uchida
Abstract
privacy concerns, high observation costs, and uncertainties in sensor measurements. Consequently, challenges often stem from low-quality labels (referred to as Weak Labels; WLs) that contain incorrect, incomplete, or ambiguous su- pervisory information, and low-quality features (referred to as Weak Features; WFs), which manifest as misobservations, missing values, ambiguous observations. Extensive re- search has focused on WLs within the framework of weakly supervised learning ( (WSL), covering methods such as semi- supervised learning and learning with label noise, which have provided substantial theoretical guarantees (Chapelle et al., 2006; Elkan & Noto, 2008; Cour et al., 2011; Natara- jan et al., 2013; Ishida et al.. 2017). In contrast, research on WFs has proposed methods such as seapute-then-rereee (ItR), which imputes missing before regression (Josse et al., 2024; Bertsimas et al., 2021: Le Morvan et al., 2020b; 2021), and complementary features learning (CFL), which lever- ages complementary features (CFs) that differ from the true values (Sugiyama & Uchida, 2024). However, a unified framework that provides consistent theoretical guarantees across the various forms of WFs remains underexplored.
In many real-world applications, predictive tasks inevitably involve low-quality input features (Weak Features; WFs) which arise due to fac- tors such as misobservations, missingness, or par- tial observations. While several methods have been proposed to estimate the true values of spe- cific types of WFs and solve a downstream task, a unified theoretical framework that com- prehensively addresses these methods remains un- derdeveloped. In this paper, we propose a uni- fied framework called Weak Features Learning (WFL), which accommodates arbitrary discrete WFs and a broad range of learning algorithms, and we demonstrate its validity. Furthermore, we introduce class of algorithms that learn both the estimation model for WFs and the predictive model for downstream task and perform gener- alization error analysis under finite-sample condi- tions. Our results elucidate the interdependencies between the estimation errors of WFs and the pre- diction error of a downstream task, as well as the theoretical conditions necessary for the learning approach to achieve consistency. This work es- tablishes unified theoretical foundation, provid- ing generalization error analysis and performance guarantees, even in scenarios where WF's manifest in diverse forms.
Motivated by these challenges, this study focuses weak features learning (WFL), a generalized learning problem involving arbitrary WFs. A common approach involves se- quentially or iteratively learning g to estimate the true values of WFs (referred to as exact val- ues) and label prediction model f to predict downstream task labels using the outputs of g. This strategy is consid- ered rational for improving both the quality of WFs and the predictive performance of downstream task (Yoon et al., 2018: 8; Mattei & Frellsen, 2019; Le Morvan et al., 2020a; Ipsen et al., 2021; Zaffran et al., 2023; Ipsen et al., 2022; Sugiyama & Uchida, 2024). Indeed, prior approaches such as ItR and CFL are grounded in this learning strategy, utiliz- ing various machine learning methods to construct g. These methods aim to improve the quality of WFs, thereby enhane- ing the generalization performance and explainability of in a downstream task.
estimation models
1. Introduction
The performance and explainability of machine learning models are highly dependent the quality of the training data. However, in practical applications, obtaining high- quality data is often infeasible due to constraints such as
'Major in Computer Science and Communications Engineering, Waseda University, Tokyo, Japan. Correspondence to: Kosuke Masato Uchida
Sugiyama <koosukk032226 @ <m.uchida @ waseda.jp>..
However, in the context of WFL, where various methods have been proposed, significant gaps remain in understand- ing how the learning g and f impacts each other's leam- ing efficiency and under what conditions WFL can achieve
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
optimal g and I (i.e., consisteney). For example, in ItR, while the conditions under which g and f become Bayes rules have been analyzed, the generalization error analy- sis under finite samples and any data distribution has not yet been sufficiently conducted (Josse et al., 2024; Bertsi- mas et al., 2021; Le Morvan et al., 2020b; 2021). Also, in CFL, which addresses CFs, theoretical analysis remains underdeveloped, and clear guidelines for handling diverse forms of WFs in unified manner have yet to be established (Sugiyama& & Uchida, 2024).
the estimation errors of g influence the error bound for J- By integrating the theoretical framework of WSL in (i), we further analyze how the properties of WFs influence f's error bound, how the order of the error bound evolves with the learning of g, and the conditions under which sequential learning in LAC-dWFL (performing steps (i) and (ii) in sequence) achieves consistency.
4.For step (iii), we evaluate the generalization error of g given any fixed f (Section 4.3) and analyze how the prop- erties and generalization performance of affect the error bound for g. By integrating the results of Contributions 3 and 4, we establish the conditions under which itera- tive learning in LAC-dWFL (alternating steps (ii) and (ii)) achieves the consistency for f g.g.
This study aims to investigate the mutual influence between estimating the exact values of WFs and learning a down- stream task. Specifically, we focus on scenarios involving discrete WFs (hereafter referred to as discrete WFL.) and pro- vide a unified formalization. By performing haite error analysis for generalized class of learning algorithms, we systematically address these questions. The proposed theoretical framework extends beyond situations involving missing values or CFs. It also accommodates cases where WFs arise in the diverse forms discussed in the WLs liter- ature, such as erroneous observations or scenarios where only a candidate set containing the exact value observed (Natarajan et al., 2013; Cour et al., 2011; Feng et al., 2020; Xu et al., 2021). Consequently, the framework not only reinterprets existing approaches such as ItR and CFL but also offers new theoretical insights into previously unex- plored WF settings. Furthermore, as the class of learning algorithms analyzed in this study encompasses various ex- isting methods (Yoon et al., 2018; Mattei & Frellsen, 2019;
5. We validate the proposed theoretical framework on real- world datasets to evaluate how accurately the derived error bounds reflect actual learning behaviors (Section 5).
2. Related work
2.1. Learning Problems involving WFs
ItR and CFL. are representative learning problems that serve as special cases of WFL, involving specific types of WFs. This section provides overview of these frameworks.
In ItR, the focus lies on scenarios where input features contain missing values. The fundamental approach of ItR involves imputing the missing values and utilizing the re- sulting complete dataset to learn a label prediction model f for a downstream task. Sequential learning methods have been proposed, employing feature estimation models g that utilize techniques such constant imputation (Josse et al., 2024) or machine learning- based approaches (Yoon et al., 2018; Mattei & Frelisen, 2019; Ipsen et al., 2021). Further- more, joint or iterative optimization of g and f has also been explored in the litcrature (Le Morvan et al., 2020a; Ipsen et al., 2022).
Ipsen et al., 2021; Josse et al., 2024; Le Morvan al., 2021; Ipsen et al., 2022: Sugiyama & Uchida, 2024), our results provide unified theoretical evaluation framework for these methods. We have also developed a unified formulation and analysis for scenarios involving continuous WFs, and the results for continuous WT' are presented in a separate paper (Sugiyama & Uchida, 2025).
The main contributions of this study are as follows:
1. We propose risk-based formulation to address arbitrary discrete WFs and demonstrate that the introduced objective function facilitates the learning of f. which captures the true onput-output relationship. This validates the proposed formulation (Section 3.2).
Theoretical analyses of ItR have investigated whether com- binations of g and exist that equal Bayes rule, focusing on regression or classification as downstream tasks (Josse et al., 2024; Bertsimas et al., 2021: Le Morvan et al., 2021). How- ever, these studies do not address the existence of learning algorithms capable of constructing optimal g and f. More- over, analyses in finite-sample settings have been confined to restrictive cases where the true f is assumed be a linear model, leaving more general problem settings unexplored (Le Morvan et al., 2020b). Additionally, these analyses of- ten restrict downstream tasks to regression or classification and, in some cases, confine the loss function of f to mean squared error (Le Morvan et al., 2020b; 2021). In this paper, while we focus on discrete WFs, we achieve a generalization error analysis of WFL in finite-sample settings by assum-
2. Within the proposed formulation, we define the Learning Algorithm Class for discrete WFL (LAC-dWFL), which flexibly combines three steps: (i) learning g using WFs as weak supervision, (ii) learning f with a fixed g. and (iii) learning g with a fixed f. This framework accommodates both sequential and iterative learning approaches, offering a unified perspective on diverse methods (Section 3.3).
3. For step (ii), we derive the error bound for given any fixed g (Section 4.2), providing theoretical insights into how
2

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
ing only the boundedness and Lipschitz continuity of the loss function of f. without imposing any constraints on downstream task and a data distribution.
bounds. Thus, if WSL is employed to learn g in WFL, the learning of g alone can be analyzed based on the WSL theories.
In CFL, the primary focus lies on learning problems where input features include CRs (Sugiyama & Uchida, 2024). Within this framework, the feature estimation model g and the label prediction model f are defined as probabilistic models, and an objective function leveraging the Kullback- Leibler divergence has been derived to learn g and f. For learning 9 in CFL, complementary label learning (CLL) (Ishida et al., 2017; 2019: Yu et al., 2018; Lin & Lin, 2023; Ruan et al., 2024), a weakly supervised learning approach that predicts true labels from datasets labeled exclusively with incorrect labels, can be employed. Moreover, since partial label learning (PLL) (Cour et al., 201 Feng et al., 2020; Xu et al., 2021; Tian et al., 2023), where supervision is provided in the form of a set containing the true label, can be interpreted as a generalized learning problem of CLL (Katsura & Uchida, 2020). Therefore, PLL is also applicable to the learning of g.
However, in WFL, it is necessary to consider the learning of both g and f. For example, in sequential learning, the learning of f depends on the output of g. In iterative learn- ing, the learning of g depends on f. unlike the case where g is learned solely using WSL. Therefore, a theoretical dis- cussion that establishes the relationship between g and f is essential. In this paper, we perform generalization er- ror analysis of WFL, explicitly considering the relationship between g and f.
3. Formulation
3.1. Review of ERM
In this paper, we formulate WFL from the perspective of risk minimization and adopt empirical risk minimization (ERM) as the learning framework. Below, we briefly review ERM in ordinary supervised learning (Shalev-Shward & DaviD, 2014; Mohri et al., 2018). Let the input space be X' C Rd and the label space be y C IR. Here, d E N4 rep- resents an input dimension. We denote the random variables representing an instance by X and the random variable rep- resenting labels by Y, assuming that (X,Y) follows the true distribution p. (ar, y) over X' x y independently and identically distributed (i.i.d).. The goal in the ERM frame- work is to find a label prediction model s X + RREF that minimizes the expected risk:
However, in CFL, the learning behavior under finite samples, as well as the conditions required to obtain asymptotically optimal g and/ f. have yet to be theoretically clarified. In this paper, we restrict 9 and f to deterministic models and perform a generalization error analysis of WFL for arbitrary downstream task and bounded, Lipschitz-contimuuus loss functions, thereby shedding light on the theoretical proper- ties of CFL.
2.2. WF's Whose Exact Values Can Be Estimated
(f) == Ep. (f)
(3.1)
When constructing a feature estimation model g. it is natural to treat the observed values of each WF as WLs and employ the WSL methods. In fact, depending on the types and settings of WFs, 9 can be learned using WSL methods. In WSL, variety of WL settings have been studied, including the aforementioned CLL and PLL. For instance, noisy label learning (Natarajan et al., 2013) deals with learning from data containing incorrect labels, while
where 1 : R x R + R4 is a loss function, and F is the hypothesis set of label prediction models. Since only finite samples are available in practice, ERM approximates the expected risk with the empirical risk computed as a sample average and learns by minimizing this empirical risk.
3.2. Formulation of discrete WFL
learning (Elkan& & Noto, 2008) focuses on learning binary classifiers using only positive and unlabeled samples.
In this section, formulate WFL based on risk minimiza- tion and employ ERM as the learning method. To account for the presence of WT' in instances, we decompose X representing an instance, into X representing the exact values of WFs and X representing the remaining ordi- nary features (OFs), such that X = (X",x)) Let A and x denote the domains of X w and XX, respectively. with X x X. Here, X is assumed to be a finite set. We denote the observed values of WFs the random variables X", which follows the probability distribution P. (œ. v).
Various WSL methods have been theoretically formulated, and their generalization error has been analyzed under finite- sample conditions (Cour et al., 2011; Feng et al., 2020: Xu et al., 2021; Natarajan et al., 2013; Ishida et al., 2017; Yu et al., 2018). Many of these objective functions were defined using unbiased estimators of the expected risk in supervised learning, the expected risk's upper bounds that computable with WLs, or risks whose optimal solutions align those of the expected risk. Their theoretical analyses elucidated the conditions under which optimal hypotheses can be obtained by minimizing each objective function, as well as the relationship between WL settings and the error
We define the feature estimation models for estimating the exact values of WFs as g == : E 9 := G1 x .... x Gr- : X - 2w, where FW is the number of
3

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
WFs, and each タ E G3 : X + 25, Vj E [F Here, [P*]= == (1, [1,.................... FW), and Gj represents the hypothesis set for estimating X The probability mass function (PMF)
The RHS of (3.(3. equals Rt, By scaling I, Uj can be aligned with any X, and minimizing RdWFL is expected to yield an f that also minimizes Rj. In other words, by using x RAWEL f is learned to capture the true relationship between X and Y, despite relying on X"
representation of is defined as 9g [z(="/z" := 1 g(a")(ar"))) For simplicity, this paper primarily focuses on binary classi-
fication, but the proposed formulation and analyses can be easily extended to other prediction tasks such as multi-class classification or regression.
This result of Theorem 3.1 is directly applicable to the fol- lowing two scenarios. The first scenario occurs when test instances contain the exact values of WFs. For instance, practical scenarios arises when WFs are observed during training, but exact values available during testing. In this scenario, minimizing R2 is essential, but it cannot be computed directly from the training data containing WFs. In contrast, since Theorem 3.1 ensures that minimizing I indirectly minimizes R,, our framework is a valuable ap- proach for overcoming incomplete inputs during training while enhancing performance with complete inputs at test time.
The primary objectives of WFL are improve the gener- alization performance of a downstream task and to restore explainability lost due to WFs. The primary factor reducing explainability is the inaccuracy of information provided by WFs. The most natural approach to address this issue is to estimate the exact values of WFs accurately. Accordingly, WFL aims to learn f and g that minimize the following two risks. The first risk evaluates the generalization error of f:
Ri,g(f) (f) = Ep. Wag (x)) (((f()), = Ex. " X"), Y)
(3.2)
The second scenario involves training data containing mix of instances with exact values of WFs X and instances with WFs X", In practical applications, some portions of the data may be observed in detail, yielding cxact values, while other portions may be only partially observed. Theo- rem 3.1 guarantees that minimizing RY RdWFI contributes to minimizing Rg Thus, it enables the simultaneous use of both data types during training. This approach facilitates the development of learning methods that seamlessly integrate both data types into a unified framework.
The second risk that assesses the estimation errors of g:
(g),) == Ep. Poi (x, (x)), X""),, Vjj E [F*]. (3.3)
Here, loi (y. 3')= == [prtnl represents the 0-1 loss. Finally, the objective function for discrete WFL is defined as linear combination of these risks:
pdWFL. (g.f)= == Rl, + +XE Roi,(())) (3.4) R
where x E R4 is weighting parameter.
3.3. Learning Algorithm Class for discrete WFL
The objective function RdWFL facilitates the unified treat- ment of any discrete WFs. This unification arises from representing the error of 9₁ via the risk Røi,j. which is aimed to be minimized regardless of the type of WF. In practice, for various types of WFs, WSL methods that learn gj aim to minimize Ra by minimizing risks that serve as upper-bound of Roi.j risks whose optimal solutions align with those of Rot.j (Cour et al., 2011; Feng et al., 2020; Natarajan et al., 2013; Ishida et al., 2017; Yu et al., 2018). Therefore, such WSL methods can be utilized to learn Zj as part of minimizing Te(, IdWFFL
In this section, we introduce a class of learning algorithms that uniformly address not only any discrete WFss but also diverse methods within the discrete WFL framework. Build- ing on the formulation proposed in Section 3.2, we define a class that encompasses numerous existing methods in ItR and CFL follows:
Definition 3.2 (LAC-dWFL.). learning algorithm class for discrete WFL (LAC-dWFL) refers the set of algorithms in discrete WFL that learn the feature estimation models g and the label prediction model f using one or combination of the following three steps:
The validity of our formulation is demonstrated by the fol- lowing theorem! Its proof is given in Appendix A.I.
(i) Learning g by using W as weak supervision and min- imizing Σje(en] Ro either directly indirectly.
Theorem 3.1. For any f E F, 9 E G, and bounded by U1= < co, the following inequality holds:
(ii) Learning f with fixed by minimizing Ri.g-
Bi(f) < (f) + U1 EiE Ror (9i)
(3.5)
(iii) Learning g with f fixed by minimizing RdWFL
'Theorem 3.1 can also be derived from Lemma 4.1, which is introduced later in Section 4.1. However, while Lemma 4.1 is derived for the theoretical analysis in Section 4, Theorem 3.1
The introduction of LAC-dWFL allows for a unified treat- ment of a wide range of methods for WFL. Most methods ap- plicable to ItR and CFL fall under the category of sequential learning, where steps (i) and (ii) are executed in sequence
intended to establish the validity of our formalization. We
introduce this theorem to enhance the clarity of our discussion.
4

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
(Yoon et al., 2018; Mattei & Frellsen, 2019; Ipsen et al., 2021; Josse al., 2024; Le Morvan al., 2021; Sugiyama & Uchida, 2024). Additionally, methods that represent g and f as neural networks and combine them (Le Morvan et al., 2020a; Ipsen et al., 2022) can be regarded as teraaive learning, where steps (ii) and (iii) are executed repeatedly, when these components are alternately optimized. Such methods are thus encompassed within LAC-dWFL.
remains fixed. Since step (ii) involves learning S' based on the output of g rather than X", tthe relationship between g and f cannot be analyzed using ordinary supervised learning frameworks (Mohri et al., 2018 8). We derive an error bound for f that captures how the errors of influence the learning process of f. enabling an analysis of the step (ii).
To facilitate the analysis, we introduce the following def- initions. Given n E N+ training samples, we define the ordinary dataset, S = {( y:) p and the weak dataset, S = {0,"" <g.34)]b ) Here, Ex represent the realizations of X = (X", X)), Y and w respectively. Also, the i-th samples in S and S cor- respond to the same instance, for any E [n]] We as- sume that {( yr, a.,) ")")]=== are independently drawn from P. (at, y " (z, y). Let R2 and Rú, denote the empirical risks calculated by the sample average over S and 5, respec- tively. For any g E G, the empirical risk minimizer obtained from LAC-dWFL's step (ii) is defined as follows:
4. Theoretical analysis
= (a). xx",, Us and
This section presents a theoretical analysis of the unified learning algorithm class, LAC-dWFL. Through this analy- sis, we elucidate the common properties of LAC-dWFL and establish a foundation for the theoretical exploration of vari- ous methods encompassed within this class. To achieve this, is necessary to elucidate the properties of steps (i), (ii), and (iii) within LAC-dWFL. As established in Section 3.3, step (i) involves WSL methods, and its properties can therefore be analyzed using existing WSL theories. Consequently, our theoretical focus is directed toward steps (ii) and (ii). In Section 1.1, we derive a fundamental inequality to analyze steps (ii) and (iii). In Section 4.2, we establish an error bound for learned via step (ii), given any g. In Section 4.3, we establish an error bound for g learned via step (iii), given any f.
f == arg minser (f).
Using Lemma 4.1, we establish the error bound for f learned via LAC--WFII step (ii) in the following theorem. The proof provided in Appendix A.3.
Theorem 4.2. Let S and S be the ordinary dataset and weak dataset, respectively, each containing n samples. For any measurable g E G, Lı-Lipschitz continuous I bounded by Ut < co and 8 E (0, 1), the following holds with probability at least 1- 8:
4.1. Deriving an Analytical Tool
Our objective is to examine how the learning of in step (ii) and g in step (iii) depend on the performance of and f. respectively. To achieve this, the error bounds for f and g must be expressed in terms of Rot,; for any j E [F=]] and RG, respectively. To achieve this requirement, we present the following lemma, with its proof provided in Appendix A.2.
(
4 ((L + L.9R + Ut
log(4/8) 2n
+ (L) + 2U1 log(4/8)
Lemma 4.1. For any measurable I bounded by Ui co, I E F and g E G, the following holds:
+
(4.7)
+ (2U) EjElm Rot. $1
[R((]- - (f)s
(21 Ejetrn Roi,(l;))
(VRI())+ (Re)(T) (2U) Ese(on) Ras(ag)) 3/2
(4.6)
Here, JF == arg mingene Ri(J) represents the true risk minimizer in ordinary supervised learning.
Equation (4.6) shows that [R(J) - RI, (f) = 0 is achieved when either Ej{(p)) Roi,((9)) 0 or / [J} +
The terms (F) and (FFF) represent the Rademacher complexities of the hypothesis class F under the distribu- tions (x)) and p. (xx (gr))gg( (x* (x*),, respectively, and mea- sure the complexity of F. Equation (4.7) reveals that the errors of g combine with the result of virtual ordinary super- vised learning (Ri(F)) + ...)//// to affect the error bound for f in WFL..
VBr. (f)= = O. Although intuitive, this inequality serves a critical role in deriving subsequent error bounds. Lemma 4.1 enables the analysis of how f and g influence each other's learning processes.
4.2. Analysis of Learning Label Prediction Model f
The first contribution of Theorem 4.2 is its ability to reveal the following property concerning the learning of f under LAC-dWFL's step (ii). Theorem 4.2 demonstrates how the
In this section, we conduct a theoretical analysis of the learning process of ff under LAC-dWFL's step (ii), where g
5

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
convergence rate of the error bound for / with respect to depends the estimation errors of g- Given the estab- lished result that the order of the Rademacher complexity's s upper bound is (1(1/'// /2) for kernel ridge regression and multilayer perceptrons (Mohri et al., 2018; 8; Neyshabur et al., 2015), we assume the orders of Rademacher complexities about F or G are (p(1/n)/2)) Additionally, assume that F sufficiently expressive and that (f(f=) = O. Under these assumptions, and with g fixed, the first and second terms in the error bound have orders of (p(n////2) and (1/n//2/)) respectively. Therefore, the second term, which decreases more slowly, becomes dominant when [je(F]] Roi,5 is large. This result suggests that when learning g to improve the generalization performance of f, maximizing the estima- tion accuracy of g sufficient, rather than tailoring the out- puts of g to be specifically suited for f. Furthermore, when WFs contain ambiguous information such as CFs, their val- ues X can serve as inputs to f. The choice between X= and the learned g is critical decision, empirically validated in the context of CFL (Sugiyama& & Uchida, 2024). Theo- rem 4.2 concludes that, if the learned g estimates X= more accurately than X", using g contributes more significantly to reducing the error bound for f compared to directly using X"
value or X T is used as g the order of the error bound remains O/(1/n//1), whereas learning g improves this or- der to (,(Inn In addition, Theorem 4.2 theoretically connects the error bounds of f and g. thereby elucidating the conditions under which sequential learning achieves consistency, as following theorem. The proof is shown in Appendix A.4.
Theorem 4.3. Assume the existence of true deterministic functions 0j X - >xW for all j E [F*], such that (gi...., gp-) E G, and f X + y such that f E F. Additionally, suppose bounded by Ut- < oo is Li-Lipschitz continuous, and (F) and Ry (F) asymptotically ap- proach O as n + co. If. for all j E [FW], the number of samples available for learning 9i tends to infinity as - oc, and consistent method is employed to learn 9j. then sequential learning achieves consistency (i.e., as n. + 0c, Bl.g(fg.s) + R((fr)).
Thus, under the conditions stated in Theorem 4.3, an asymp- totically optimal pair of I and f can be obtained through sequential learning alone. In contrast, in practical finite- sample scenarios, iterative learning involving LAC-dWFL's steps (ii) and (iii) may be necessary (Le Morvan et al., 2020b; 2021). In Section 4.3, we examines the step (iii) for a comprehensive understanding of LAC-dWFL.
The second contribution of Theorem 4.2 is its ability to integrate our WFL theory with the theories of WSL meth- ods used to Iearn g under LAC-dWFL's step (i). This is because, when 9j is learned using certain WSL methods, their theoretical frameworks enable the derivation of error bounds for (o in Eq. (4.7) (Cour al., 201 1; Feng et al., 2020; Xu et al., 2021; Natarajan et al., 2013; Ishida et al., 2017: Yu et al., 2018). For example, when X" is CF. applying the CLL method by Ishida et al. (Ishida et al., 2017) for learning Jj. and assuming that 93 is sufficiently large to satisfy ming,es, (og)) = O, the following holds for any Li-Lipschitz continuous I and any 8 e (0, 1) with 8:
4.3. Analysis of Learning Feature Estimation Models g
This section provides a theoretical analysis of the learning of g with f fixed in LAC-dWFL's step (ii). We aims to reveal how the learning of g using RI,,, with f fixed, is influenced by
The learning of g using REWFL in Eq. (3.4) involves the si- multaneous minimization of two risks, which makes it chal- lenging to conduct generalization error analysis for ERM directly. In contrast, in ordinary supervised learning, the simultaneous minimization of an expected risk and a regu- larization term is formulated as structural risk minimization (SRM), which has established methods for generalization er- ror analysis (Mohri et al., 2018). SRM selects hypothesis from restricted hypothesis class in which the regularization term is below a certain threshold and derives error bounds for the selected hypothesis. Focusing on the influence of f on the learning of g. we treat Ra. as the expected risk for which bounds are derived and Eje(zog Rot,5 as the regular- ization term, and apply SRM theory.
probability least 1-8:
Roi (0t) < 4 ((2771 DR (c,)
(4.8)
+ (12571 - / 8 12/(2/8)
The combination of such error bound with Eq. (4.7) enables a unified generalization eтror analysis for the sequential learning of g and f under LAC-dWFL's steps (i) and (ii), elucidating the following three aspects: Firstly, the combi- nation enables the analysis the influence of WFs' properties on the learning of f. For instance, since Eq. (4.8) depends on 1, combining it with our bound allows for analyzing how the number of possible values |x,71 influence I's learn- ing, Secondly, this combination elucidates the impact of whether g is learned or not on the learning of f. Applying Eq. (4.8) to Eq. (4.7) demonstrates that the order of the error bound for f is (p(1/n//2). Thus, when constant
To apply SRM theory, for any j E [FW], we in- troduce the following definitions. Let 1, denote the loss function for gj computed using Xy. Define the datasets 5,
(0 )))) Let Ru, (g,) = Ep, (m.a)))) (m)) 1 (X,) Xy))] represents the ex- pected risk of gj computed using Xy. Additionally, RG de-
6

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
notes the empirical risk, which approximates Ry by taking the sample average over 5j. We assume that Rú satisfies either (o))) = R2, (gz) or RoI,)(g)) S Rs, (0j) for any Gj. or that the optimal solutions of Ri, coincide with those of Roi.j- For any r (ri,...,,TM E IR. define the following hypothesis class:
also Op(1/n1/2). Furthermore, assuming that (G)) 0 as oc, it follows that Ro (r:) 0 as n + 00.
In the following discussion, we assume that Roi. (7)) can be upper-bounded by probability inequality of form similar to that of Eq. (4.8).
Theorem 4.4 elucidates the influence of f's prediction error and characteristics on the error bound for learning g via LAC-dWFL''s step (iii), as well as the convergence of g's learning. First, Theorem 4.4 demonstrates that the conver- gence rate of the upper bound of (ggh)) n significantly depends on the expected risk (f). Specifi- cally, assuming the orders the Rademacher complexities in Eq. (4.10) are (p(1/n1/2), the orders of the first and second terms on the RHS of Eq. (4.10) are Op (1(n///)) and (1/n/2//4), respectively. Consequently, the slower- decreasing second term becomes dominant when Rf(f) is large. Although Rf(f) cannot be directly minimized in WFL, it has been shown that minimizing R; R;WFF (f,, helps reduce R((ʃ) (Theorem 3.1). Therefore R&(f) is expected to decrease through LAC-dWFL's step (ii). Additionally, if is L,-Lipschitz continuous and f is L,-Liscchitz con- tinuous, then R (Gr, S)) S IR S)) holds (Mohri al., 2018). This implies that the learning efficiency of g improves when f exhibits smoother variation with re- spect to its input. Furthermore, combining Theorem 4.4 with Theorem 4.2 reveals the conditions under which itera- tive learning in LAC-dWFL achieves consistency. The proof is shown in Appendix A.6.
x... GF- (rpw, Spm);
where,
= ووارا E EG, A Rí, (g)) S <ryjije E
[F"]. To explicitly indicate that (f) is part of the ob- jective function of g. we denote it as (g)(())(= (f)) and the empirical risk of (g) is defined as (g)= R (f)). By performing the learning of in LAC-dWFL's
(r) with respect to
step (iii) as outlined below, the analysis of minimizing R
while reducing ]j(pp Rot, becomes feasible:
9 f = arg aig gES((. (g)
(4.9)
Based on the above definition, the assumptions and Lemma 4.1, the error bound for 9j.s is presented in the following theorem. The proof is provided in Appendix A.5. Theorem 4.4. Suppose S and 5 represent an ordinary dataset and weak dataset of n samples, respectively. Then, for any measurable f E F, I bounded by Ut < and 6 E (0.1), the following holds with probability at least 1 -- 6:
Ri. (7,))) R((f) S
(G ()) + +UUI log(2/6) 2n
Theorem 4.5. In addition to the conditions stated in Theo- rem 4.3, assume f obtained via LAC-dWFL's step (ii) is Lip- schitz continuous, and the Rademacher complexities about g asymptotically converge to 0 as n. increases. Furthermore, for any j E [F"), define G,(r,,S) as the set of empirical risk minimizers obtained by methods that use Sy and are guaranteed to achieve consistency. Then iterative learning achieves consistency.
(4.10)
/2/ + (2U1 EyE|Fn Rol.(05)) $ }}}
x (20)E, Rois(o5]) (11)))
Here, (r,( S)= = [(x01 v) + ((f(g())) x)),)) : (),.
The term Ro (1a)) in Eq. (4.10) can be further upper- bounded by defining Gy (ry, as the set of empirical risk minimizers obtained via weakly supervised learning using 3,. For instance, when Xy is a CF, and every hypothesis in 55) is an empirical risk minimizer obtained us- ing the method of Ishida et al. (Ishida et al., 2017) and Gj is sufficiently large to satisfy min Rois(ag) = O, then (o (ra)) can be upper-bounder by Eq. (4.8). There- fore, when we define (r(r,,S)) as the class of empirical risk minimizers obtained by such a method with guaran- teed consistency, and assume that the order of 9 (9,) is
5. Experiments
In Section 4 we revealed two key properties of LAC-dWFL: (1) the mutual influence between the feature estimation mod- els g and the label prediction model f during their respective learning processes, and (2) the relationship between the gen- eralization error and the number of training samples n in WFL. Furthermore, the theoretical analysis demonstrates that sequential learning alone suffices for WFL. To validate the critical aspect of WFL, namely the impact of the esti- mation error of g on the learning of f (Theorem 4.2), we evaluate how varying the estimation errors of g affects f's learning performance.
(1/n)//)) the order of the upper bound of Roi, (9 (7))
is
S.j
7

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Aduls
X10-1
Bank
x10-1
Kick
100
Census
60
Raul0)) [F*]
3.5
(9y)
Ray
4.5
Rayio) -0.4 [F*]
Raulo) -0.2 [F*]]
2.5
4.5
4.11
Ray -0.6 60.6.% [F*)
Rauin) -0.7% [F*)
2.0-
3.5
Raylo) -0.8 (F*)
Na. (9,) [P*)
0.1
033
0.5
0.7
0.9
1.1
633
0.5
0.7
0.
1.1
133
6.5
08
0.7
09
1.3
0.5
0.5
0.7
0.9
1.3
X:00
X100
X10
X100
Pigure 5.1. The relationship between the number of training samples R and various estimation errors of g.
Adult
Bank
Kick
Census
Pcoususannee
Barilgal Bun dou -0.1 We (F7))
-
Bunnd (Ro -0.1 (PMI)
Barilgst (Rs -0.3 (179)
[177]
Basilasl Ban -0.5 Yy (171)
Baund (Ri dn) mith (177))
Resido af Rey -0.7 vy (F7))
Baund (Rin
(179))
Rosilasl RRalle w0o Wy (171)
000000
Bonnd (Raala) (o) -0.0%% (171)
0.3
Figure 5.2. A comparison between Ri, (Jg,z) and the error bound derived Theorem 4.2, for various estimation errors of
5.1. Experimental Settings
settings are summarized in Appendix B.2. The follow- ing results are the average of 5 trials. The experimental scripts used in this paper available the following URL: https///giibbbcom/oooeePP/ddssdd
We used four real-world datasets: Adult (Becker & Ko- havi, 1996), Bank Marketing (Moro Cortez, 2014), kick (Vanschoren al., 2013), and Census-Income (KDD) (cen, 2000; Dua & Graff, 2017). We refer to them Adult, Bank, Kick, and Census, respectively. Details of these datasets are summarized in Appendix B.I. For each dataset, 50% of the samples were reserved as test data to estimate the generalization error. In this experiment, we focused on representative case of WFs, where all categorical fea- tures treated CFs (Sugiyama & Uchida, 2024). Both the feature estimation models g and the label prediction model f were implemented using two-layer perceptrons with hidden layers of width 500 and ReLU as an activation function. Logistic loss was used as The Rademacher complexity, required for calculating the error bounds, was estimated using the method proposed by Neyshabur et al. (Neyshabur al., 2015). Details of the experimen-
5.2. Impact of on f's learning
This section investigates how the estimation errors of fea- ture estimation models g affects the learning of the label prediction model f. To perform this investigation, precise control over the estimation errors of g is required. However, achieving such fine ame-grained control through WSL methods is challenging. Importantly,
this experiment, the method used obtain g is less relevant than the influence of its estimation errors f. Thus, synthetic estimation functions for g are employed, which randomly misestimate with con- trolled error rates, enabling systematic examination of the impact of g estimation errors on f's learning.
8

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
We vary the estimation error of g from 10% to 90% and train under these settings. Figure 5.1 shows the relationship between and Ri. g.g.)). The results confirm that, as shown in Theorem 4.2, lower estimation errors of g lead to a higher reduction rate of (.,g(gg33) 5) as n. increases.
biases. The theoretical results presented in this work are ex- pected to provide foundational perspective for discussions concerning the interplay between input feature quality and the safety of machine learning.
Additionally, Figure 5.2 compares the generalization error of f. shown in Figure 5.1, with the error bound in Theo- rem 4.2. Figure 5.2 shows that the decrease in (f and its bound with increasing exhibits similar trend, with the reduction becoming more significant as the es- timation error of 9. Therefore, Theorem 4.2 effectively captures a fundamental characteristic of WFL, specifically the influence of g on the actual learning of f. which is con- sistent across various scenarios. The discrepancy between R (fg,s) and our bound in Figure 5.2 can be attributed to the fact that our bound does not account for the feature importance of WFs in predicting Y. This suggests a new research direction for deriving error bounds that incorporate the feature importance of WFs. Our results are considered to provide a critical foundation for such an approach.
A Acknowledgment
This work was supported in part by the Japan Society for the Promotion of Science through Grants-in-Aid for Scientific Research (C) (23K11111).
References
Census- Income (KDD). UCI Machine Learning Repository, 2000. DOI: https///doo.rr/11.2443322
Becker, B. and Kohavi, R. Adult.
UCI Ma-
chine Learning Repository, 1996.
DOI:
stpss//doo.org/10.4444///
Bertsimas, D., Delarue, A., and Pauphilet, J. Prediction with missing data. stat, 1050:7, 2021.
6. Conclusion
Chapelle, O., Scholkoff, B., and Zien, A. Semi-supervised learning. 2006. Cambridge, Massachusettes: The MIT Press View Article, 2, 2006.
This presented a unified formalization and theoretical anal- ysis of discrete WFL. First, we proposed formulation of WFL capable of handling arbitrary discrete WFs. We vali- dated this formulation by demonstrating that the introduced objective function aids in learning a label prediction model f that captures the true input-output relationship. Within this framework, performed a generalization error analysis for LAC-dWFL, generalized learning algorithm class de- signed to learn both feature estimation models g and f. This analysis revealed the detailed influence of the estimation errors of and f on the error bounds of f and g. respec- tively. Additionally, we identified theoretical conditions under which consistency can be achieved for the sequential and iterative learning approaches in LAC-dWFL. Finally, numerical experiments real- world datasets verified that our theoretical results align with observed learning behav- ior. This study provides comprehensive theoretical insights into various problem settings, such as ItR and CF, involving discrete WFs.
Cour, T., Sapp, B., and Taskar, B. Learning from partial labels. J. Mach. Learn. Res., 12(mul): July 2011. ISSN 1532-4435.
Dua, D. and Graff, C. UCI machine learning repository, 2017. URL http://////// http://archvveee ics www.uuiiuuuueeeeo
Elkan, C. and Noto, K. Learning classifiers from only posi- tive and unlabeled data. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discov- ery and Data Mining, KDD '08. pp. 213-220, New York, NY, USA, 2008 Association for Computing Machinery. ISBN 978160558 1934. doi: 10.1 (41514411900.400
Feng, L., Lv, J., Han, B., Xu, M., Niu, G., Geng, X., An, B., and Sugiyama, M. Provably consistent partial-label learning. In Proceedings of the 34th International Con- ference Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc ISBN 9781713829546.
Impact Statement
Our paper presents formalization and theoretical analy- sis of discrete WFL that accommodates arbitrary discrete WFs. Understanding the impact of low-quality input fea- tures on the training of predictive models is crucial for the development and deployment safe machine learning sys- tems. This is because degraded input feature quality can potentially lead to predictive models that are vulnerable to adversarial attacks that propagate socially undesirable
Ipsen, N., Mattei, P.-A., and Frellsen, How deal with missing data in supervised deep learning? In Pro- ceedings of 2022 International Conference on Learn- ing Representations, 2022. URL nettps://iee /tt///icrr... cc/ Con Conferences/2000 2202.. 10th International Conference on Learning Representations, ICLR 2022; ; Conference date: 25-04-2022 Through 29-04-2022

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Ipsen, N. B., Mattei, P.-A., and Frellsen, J. not-(miwae): Deep generative modelling with missing not at random data. In International Conference on Learning Represen- tations. 2021.
Lin, W.-I and Lin, H.-T. Reduction from complementary label learning to probability estimates. In Kashima, H., Ide, T., and Peng, W.-C. (eds.), Advances in Knowledge Discovery and Data Mining, pp. 469-481, Cham, 2023, Springer Nature Switzerland. ISBN 978-3-031--3377-4
Ishda T., Niu, G., Hu, W., and Sugiyama, M. Learning from complementary labels. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30, Curran Associates, Inc., 2017.
Mattei, P.-.. and Frellsen, J. MIWAE: Deep generative modelling and imputation of incomplete data sets. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceed- ings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learn- ing Research, pp. 4413 4423, PMLR, 09-15 Jun 2019.
Ishda,, T., Niu, G., Menon, A., and Sugiyama, M. Complementary-label learning for arbitrary losses and models. In International Conference on Machine Learn- ing. pp. 290-2991121 1-2980. PMLR, 2019.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of Machine Learning. The MIT Press, 2nd edition, 2018. ISBN 0262039400.
Josse, J., Chen, M., Prost, N., Varoquaux, G., and Scornet, E. On the consistency of supervised learning with missing values. Statistical Pupers, 65(9):5447-5479, 2024.
Moro, S., R. P. and Cortez, P. Bank Marketing. UCI Machine Learning Repository, 2014. DOI:
Kahn, M. Diabetes. UCI Machine Learning Repository.
DOI: https://doi.org// http://ddoi.rg//0.24433// 0.24////0002///
Natarajan, N., Dhillon, I. S., Ravikumar, P. K., and Tewari, A. Learning with noisy labels. In Burges, C., Bottou, I.,, Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), Advances in Neural Information Processing Systems, vol- ume 26. Curran Associates, Inc 2013.
Katsura, Y. and Uchida, M. Bridging ordinary-label learn- ing and complementary-label learning. In Pan, S. J. and Sugiyama, M. (eds.), Proceedings of The 12th Asian Con- ference on Machine Learning, volume 129 of Proceed- ings of Machine Learning Research, pp. 161-176. PMLR, 18-20 Nov 2020.
Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based ca- pacity control in neural networks. In Grünwald, P., Hazan, E., and Kale, S. (eds.), Proceedings of The 28th Confer- ence on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1401, Paris, France, 03-06 Jul 2015. PMLR.
Kingma, D. and Ba, J. Adam: A method for stochastic optimization. International Conference on Learning Rep- resentations, 12 2014.
Le Morvan, M., Josse, J., Morcau, T., Scornet, E., and Varoquaux, G. Neumiss networks: differentiable pro- gramming for supervised learning with missing values. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Pro- cessing Systems, volume 33, pp. 3980-5990. Curran As- sociates, Inc., 2020a.
Ruan, J., Zheng, Q., Zhao, R., and Dong, B. Biased complementary-latoe learning without true labels. IEEE Transactions on Neural Networks and Learning Systems, 35(2):611622677, 2024. doi: 10. 1..119NNNNSS.02...
3190528.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory algorithms. Cambridge university press, 2014.
Le Morvan, M., Prost, N., Josse, J.. Scornet, E., and Varo- quaux, G. Linear predictor on linearly-generant data with missing values: non consistency and solutions. In Chiappa, S. and Calandra, R. (eds.), Proceedings of the Twenty Third International Conference on Artificial In- telligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 3165-3371 -1744. PMLR, 26- 28 Aug 2020b.
Sugiyama, K. and Uchida, M. Learning from complemen- tary features. arXiv preprint 14788 2024.
Sugiyama, K. and Uchida, M. Unified analysis of continu- ous weak features learning with applications to learning from missing data. In Proceedings of the 42nd Interna- tional Conference on Machine Learning, 2025.
Le Morvan, M., Josse, J., Scornet, E., and Varoquaux, G. What's s a good imputation to predict with missing values? In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Informa- tion Processing Systems, volume 34, pp. 11530-11540. Curran Associates, Inc., 2021.
Tian, Y., Yu, X., and Fu, S. Partial label learning: Taxonomy, analysis and outlook. Neural Networks, 161:708-721 734, 2023. ISSN 0893-6080. doi: https://toi.rr//1..01100 neumet.2023.02.019
10

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Vanschoren, J., van Rijn, N., Bischl, B., and Torgo, L. Openml: networked science in machine learn-
ing. SIGKDD Explorations, 15(2):99-00, 2013. doi: 19144//641110226411111
Xu, N., Qiao, C., Geng, X., and Zhang, M.-L. Instance- dependent partial lahel learning. In Ranzato, M., Beygelz- imer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.,, Advances in Neural Information Processing Systems, vol- ume 34, pp. 27119-271 130. Curran Associates, Inc., 2021.
Yeh, I.C.
Default of Credit Card Clients. Machine Learning Repository, 2009. DOI:
UCI
https///bi.ogg/0.443///55555
Yoon, J., Jordon, J., and van der Schaar, M. GAIN: Missing data imputation using generative adversarial nets. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th Inter- national Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5689- 5698. PMLR, 10-15 Jul 2018.
Yu, X., Liu, T., Gong, M., and Tao, D. Learning with biased complementary labels. In Proceedings of the Euro- pean Conference on Computer Vision IECCV), 2018.
Zaffran, M., Dieuleveut, A., Josse, J., and Romano, Y. Conformal prediction with missing values. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato. S., and Scarlett, J. (eds.), Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 40578- 40604. PMLR, 23-29 Jul 2023.

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
A. Proofs
A.1. Proof of Theorem 3.1
Proof of Theorem 3.1. For any f F.F.g. g E G, and bounded by Uj < co, the following inequality holds:
R( Rf)
(a,,00) ((f()), Bp. 22) (=m Y)]
Σ [(f(x) 2.), (x, 4g (2x (x0)) WEEW
= (mr.)))
Σ
x X3)
X) 1 -
Sxw EX'
Σ [ff(x, () " Y) - 1 , - g(xx)] (x 1 Y7)
< (m).)))
2t" EX"
Σ x1) Xx, Y) - 1x0 x
(x")))))
E
< (o..)
((f(X,Xx))) Y)
Σ (1 1xx 11x==
F
[[s(xo ( v)
Σ Ton ( XT))
(m,,))
FE
$ (aw)))
loi (gg( (X"), FF(
Σ
The second inequality arises from the decomposition of the 0-1 loss. This decomposition is intended derive the risk for each gj- The final inequality uses the assumption that the maximum value of the loss function l is U.. Therefore, Theorem 3.1 is proved.
A.2. Proof of Lemma 4.1
Proof of Lemma 4.1. The LHS of Eq. (4.6) can be rewritten as follows:
[R(()) - Ri, (f)
1Bp. (a.,y) (( ((f(),,)) Y)] - (a ((())) Y)]I
Ep. (z)
Σ [[(x" (O), X Y) (x
Ep.. (g)
Σ
[[(x""
Y) 1000 1
(x5% (wt v))
Σ
11f(a" X*), ")p,a"'''"" - 1[f(x" xa). I)1 x==1(X-]]
(x0 (z0 m)
Σ
[1 X"), 1 - 1[f("" Xº), V) = Ail (x X V)
+ +1[[("",X0 X"), (1"" X Y) 1[f(x (x)), Y) 8)
12

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
S By. ())
Σ 28 E
- 1ff(x, x)), Y) 100 ot= y)
(al)
x Y) 1[f(x", xx), |>>
|=-=-(X-|]
(A.11)
26
(a2)
The term (al) in Eq. (A.11) can be expressed as:
(al) = Σ
(I(x",X") (x. |x"
,Y(1 - 1e =o(=))
x"EA"
-p. 1[((X, x"), (o) Xw)
Here, los (g((),, xw) : 1x== The term (a2) Eq. (A.11) can be expressed as:
(a2) = Σ "([("",")), - 1()(xr" x²), Y)1 10" "x 10, V)}
x"EX"
=[f(g(X") X,), X) - 1(f(g((X")) X"), ()) Xo)
=I([(((X) (U()(("),x'):1)
Σ
P. P. 1x
- -(f(g(X)) X9),))
Σ
Po xh X Xx, ||/ [|0=-(X00)
[[((((9))
Σ
P. (x (x, Y)(1 - 1 1 =o(x-1))
1 Ext
(x1(((()),xx)))
By substituting these results into (al) and (a2) of Eq. (A.11), Eq. (A.11) can be rewritten as follows:
[R(()) (l.g((())))) (f) (a,v) [IIF(X XXX
(A.12)
Since 1, lor and g are all measurable functions, applying the Cauchy- inequality to the RHS of Eq. (A.12).
[R((J) - (J)] can be upper-bounded as follows:
RR(f) (f)
< (a.w))
+ +[[l(((X))))X)))))))))))))())))) X"), x| ()) XW)
Epp (m..)) (m..))
(1F(X", xx)),
Eps(z)
(lo1()(X0)) xx1))
(A.13)
(b1)
(b2)
(UU()(())) X.), x))
+
E (a
x Ep)(
(lo((((x)), x)))²
(b3)
(b2)
13

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
The terms (b1)-(b3) of Eq. (A.13) be expressed as:
(b1) = (p-( (I)( - 02| S -
(b2) p. (x) Fo1 (g) X"]] Σ
(2) (X)))))))
Σ
Roi,((9));
jE(P
JELF-]
(b3) = (m) m) (11F(((x)),x)),)))) - 02| - 2UU (ar (0
20 RUg
Here, (b1) and (b3), the fact that the function x22 2Up-Lipcchit continuous on the interval [0, Ui] was utilized. Applying the above inequalities related (b1)-(b3) the RHS of Eq. (A.13), [R((") R)) can be upper-bounded as follows:
RR(f) (f)
20R((()
Σ
Rois { + 20rRee(())
Σ
Rois(gi)
SE(FM)
JE(FM]
1
= (VRIL() + R(o(()))
2 Σ
Roos(os))
(A.14)
jE(FM]
Thus, Lemma 4.1 is proven.
A.3. Proof of Theorem 4.2
From Lemma 4.1, the following lemma holds:
Lemma A.1. For any f F. g and bounded by U₁ < co, the following inequality holds:
)(22)
[B((]) - R11S 2/B((+++++ 20: Σ SE[Fm]
Rons(os)
20, Σ
Rois(aj)
(A.15)
jE
Proof of Lemma A.I. From Lemma 4.1, for any J E F. g E G and bounded by Ur < co, the following inequality holds:
V Ri(f) (f) S 20 Σ
Roi (g.)
(A.16)
jE[F=]
Hence, (f) can be upper-bounded as follows:
(f) = v Rig(f) + RR(f) R((f)
S VR())+ + Ri( / (1)
(A.17)
$ /R(fF) +
20 Σ (
jE(Fw)
14

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
By applying the above inequality to the RHS of Eq. (A.14), (R(() R1.g (/)( can be upper-bounded as follows:
Raisles) )) 2U: jE[FM]
[R( Rigl (//Ri(s)+
2U: Σ
Σ
Roi (13)
(A.18)
jE[
By leveraging Lemma A.1, Theorem 4.2 proven as follows.
Proof of Theorem 4.2. From Section 3.1, we define the empirical risk minimizer in ordinary supervised learning follows:
fs =- arg minser R((.)
The LHS of Eq. (4.7) can be rewritten as:
Ri Reg ( - (((FF)
(iglsggs)) R + ( Ri,o(fs)
(A.19)
(al)
(a2)
RI.g (fs) Rd R((fs) R((fs) R((fs).
(a3)
(a4)
The terms (al) and (a2) in Eq. (A.19) can be upper-bounded as follows:
(al) < max fef R (f) (f),
(a2) < Rig( (fs)(fs) max Rl)g(f) (f).
feF
The term (a3) in Eq. (A.19) can be upper-bounded using Lemma A. as follows: Additionally, Ri(Js) can be upper-bounded as follows:
} {Z2 2U: Σ
1
(a3) < 2/ Re(Ss) + 20 Σ
Roi,(
Roi
(A.20)
JE(FM)
jj(FF)
Ri(fs) Ri(fs) Ri(fs) Ri(fs) +
s R((fs) Ri(fs) + Ro(fs) - Ri(fF) + R((ff)
s (((sF) max RR(J) R(())-
(A.21)
JEF
Hence, (a3) in Eq. (A.19) can be upper-bounded as follows:
+ max [Ri(f) - R((TI) + 2U1 Σ Rois(oi) " ")
1
(a3) < 2 (((i(f))+
20: Σ jE(FM)
Rold(ee)
(A.22)
Jer
jj(Fm)
Similarly, the term (a4) in Eq. (A.19) can be upper- upper-bounded bounded as follows:
Rs(fs) - R((F=) & 2 max
Ri( - R()-
FEF
By applying the above inequalities regarding (al) (a4) to the RHS of Eq. (A.19), it can be upper-bounded as follows:
R1.g (f.5( - -R((F=)
< 2 max Rf,g(f) - RRig(f)) + max R((f) -R(F)I fEF
JeF
(A.23)
$12 [((f)) + 2 max [R(()) R((H1)
+ 201 Σ
Roia(gs)
20: Σ jE(Fm]
Rois(o)))
fef
sE[Fm]
15

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
From the uniform law of large numbers (Mohri al., 2018), for any d E (0, 1), the following holds with probability of least 1 5/2:
log (4/(4/)
max
(f) - Ri)g(()) (F)) + ViV
JEF
2n
log(4/8)
[R(ss) - 29 (Fi) ViV
max FEF
2n
Here, Fi = (<r,)) + ()
From the assumption that is Lipischhitzz continuous, it follows that (F)) S (F) and Rg( & ((
(Lemma 26.9 in (Shalev-Shwartz & Ben-David, 2014)).
Thus, for any 8 E (0, 1), the following holds with probability of least 1 6:
R (f g. - -R(
log( 4/8)
S (F) + (F) ViV
2n
(A.24)
$ ( 2U, Σ SE(FM
1/2
[((Fs) (L -((0))+1,9(((F)) + 2014
log( 4//)
20 Σ
Roislos)
Rois(os)
2n
SE(P-]
A.4. Proof of Theorem 4.3
Proof of Theorem 4.3. By assumption, there exist true deterministic functions 9j 2 + XT for any j E [F"], and .gi....: -FF)) E G. Therefore, when gş- = (gs.1...., v is obtained by the methods that achieve consistency (Cour al., 2011; Feng et al., 2020; Xu al., 2021: Natarajan et al., 2013; Ishida al., 2017; Yu et al., 2018), the following holds:
0o, Roi (35,)) 0, Vj [F"].
(A.25)
Additionally, by assumption, there exists a true deterministic function f : X - y for label prediction, and f E F. Hence, the following holds:
R((fz) 0.
(A.26)
Thus, if ( and gig (F) are monotonically decreasing with respect and converge to O, the error bound established in Theorem 4.2 converges to 0 as n + cc.
A.5. Proof of Theorem 4.4
For a weak dataset 5 and a positive real-valued vector r, define the feature estimation models g (0 gg.F= as follows:
(n)
(rew)
))
(13) == arg min Ri) Vj E FF). I5. gEg(ry.3)
(A.27)
Using Lemma A.1, Theorem 4.4 is proven as follows.
Proof of Theorem4.4. The LHS of Eq. (4.10) can be rewritten as follows:
( (r) Rf(f) (77)) - (9 + (9 (r) (r) + Ri, (g (r)) - R().).
(g Ra, r
(A.28)
(1))
(n2)
(a3)
16

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
The terms (al) and (a2) of Eq. (A.28) can be upper-bounded follows:
(al)= v max [R) - -Ri,
(A.29)
gEg(r.S)
(a2) < {o
(r) Ra,s (r) S max
(B) (
(A.30)
gea(r.S)
The term (a3) of Eq. (A.28) can be bounded using Lemma A.1 as follows:
(a3) - (R) (r) Ri(S))
}
2 (V(((()+++ Ri(T++ +
20: Σ
Ron
(1a)))
20
Σ
Rois(o5.)
(1a))
(A.31)
jE[Fm)
jE(F
Therefore, by applying Eqs. (A.29), (A.30), and (A.31) to Eq. (A.28), we obtain:
Ri,5 Ri(f)= 2 max gEg(r.3)
(R) (g))
(A.32)
2 BVB((f)
20
Σ
R
(1))
20
Σ
(o
S.
JE[F"]
JE(F"]
From the uniform law of large numbers (Mohri et al., 2018), for any 8 E (0, 1), the following holds with a probability of at least 1 6:
log (2/8)
max (E
[R) R S 2DR, (r., (r) + ViV
(A.33)
2n
Furthermore, by applying Eq. (A.33) to Eq. (A.32), we obtain that, for any (0, 1), with probability least 6, Eq. (4.10) holds:
log(2/5)
Re.5 Ri( S (r., + +2U
2n
}
(ri)) $ Rot
+ 2V R(Rt(
20 Σ
Rot (
(r:)
20, Σ
Ro
(A.34)
jE[Pm]
JELFM]
A.6. Proof of Theorem 4.5
Proof of Theorem 4.5. By assumption, there exist true deterministic functions 93 X X2" for any j E [F"]. and (gi....,.h Few) E G. this case, for any r and S, it holds that g" Sr. Therefore, the following holds:
Ro
0, Vj [F"].
(A.35)
For any j E [F*], define (r,,, 35) as the set of hypotheses that satisfy the following two conditions: (i) each element is a solution obtained by methods that are guaranteed achieve consistency (Cour al., 2011; Feng et al., 2020; Xu et al., 2021; Natarajan al., 2013; ry the assumptions Ru, and the theoretical guarantees of these consistent methods for gj imply the following:
Ishida et al., 2017: Yu al., 2018), and (ii) its empirical risk is at most rú As increases and
Roi,( + Vg, S,),, Vj
[F").
(A.36)
Additionally, by assumption, there exists true deterministic function f : X' + y for label prediction, and f E F. Hence, the following holds:
Rí(fz) 0.
(A.37)
17

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Thus, under the conditions of Theorem 4.3, the following holds for fg.s obtained through LAC-dWFL's step (ii):
n + -0, ( - O.
(A.38)
Furthermore, using Theorem 3.1, and additionally letting rj - 0 as increases for any E [F*), the following holds: n + 00; Re(Sg.3) - 0, Ag E (),
(A.39)
Since is Li-Lipschitz continuous and ggs is Ly-Lipschitz continuous, using Talagrand's lemma (Shalev-Shwartz & Ben-David, 2014), the following holds:
R (91, S)) - LL, S)).
(A.40)
Consequently, if (S S)) and (r, Sj)) ) for any j E [F]] are monotonically decreasing with respect to n and converge to O, the error bound established in Theorem 4.4 converges to as n + cc.
B. Detail Information of Experiments
B.1. Details of Datasets
We used four real-world datasets: Adult (Becker & Kohavi, 1996), Bank Marketing (Moro & Cortez, 2014), kick (Vanschoren et al., 2013), and Census-Income (KDD) (cen, 2000; Dua & Graff, 2017) in Section 5. In Section C.I, we additionally used two datasets: Default of Credit Card Clients (Ych, 2009) and Diabetes 130-US Hospitals for Years 1999-2008 (Kahn). We will refer to them as Adult, Bank, Kick, Census, Default, and Diabetes, respectively. These datasets can be downloaded from UCI Machine Learning Repository (Dua & Graff, 2017) or OpenML (Vanschoren et al., 2013). Table B.1 summarizes the characteristics of these datasets. All binary features were set to take values of either 0 1, all categorical features were encoded using one-hot encoding, and all continuous features were scaled to fall within the range [0, 1]. For the Adult, Bank, Kick, Default, and Diabetes datasets, all available samples were used. For the Census dataset, experiments were conducted using 50,000 randomly sampled data points.
Table B.I. Outline of datasets. binary, categorical, and numerical represent the number of features of each type, respectively.
dataset
Adult
Bank
Kick
Census
Default
Diabetes
data size
48842
45211
72983
299285
30000
101766
binary
3
3
1
10
categorical
7
12
22
2
12
numerical
16
10
20
10
target
binary
binary
binary
binary
binary
classes
B.2. Details of Experimental setup
We summarize the settings of feature estimation models g and label prediction model f. Both g and f were implemented using two-layer perceptrons with hidden layers of width 500 and ReLU as activation function. The optimization algorithm used across all models is Adam (Kingma & Ba, 2014), with the following hyperparameters: learning rate of 0.0005, batch size of 512, 100 epochs, and weight decay of 0.0002. Logistic loss was used for training f.
We summarize the method for calculating the error bound presented in Theorem 4.2 for this experiment. The parameter was set to 0.01. Additionally, assuming that F is sufficiently expressive, we set R((f>) = 0. During inference, the predicted label from f was determined based on the largest output value of f. Consequently, scaling the outputs of f does not affect the inference results. Thus, we assumed that the maximum value of each element in f's output is 1 and set U/ 2.0. Since the loss function for label prediction is the logistic loss, which I-Lipschitz continuous, it follows that R (Fi) RA, (F) and 9A (Fi)- Rig (F) (Lemma 26.9 in "Shalev-Shwarte & Ben-Davic 2014)). The terms A (F) and (F) were computed using the upper bound on the Rademacher complexity of multilayer perceptron derived by Neyshabur et al. (Theorem 1 in (Neyshabur et al., 2015)). To compute this upper bound, it is necessary to determine which represents the upper bound on the 1,- norm of all parameters of f. as well as the value of p. In this experiment, p p= 2 was chosen. Furthermore, since is possible to scale all parameter values of f without affecting the inference results for predicting a single label, we set μ =
18

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Default
Diabetes
110
X10
1.75
1.50
Bound
1:25
Bound
(ai,(()) =0.1 vý [P]]
1.00
Rai,(ay) =0.3 vy [F*]
0.75
(ox,(8)) =0.5 Kj [AT*]
Ra1 =0.7 vj [AT]]
0.50
Rai,lay) =0.9 Ny [
0.1
0.3
0.5
0.1
0.3
0.5
0.7
0.9
1.1
1.3
1.5
x10
x10
6.0
Raillas)
Rg.1/38)
4.4
5.6
Rai,(a,) -0.1 Vy [F
5.4
4.3
Rai,(a)) -0.3 vy [F*]
5.2
(81,(8)) =0.5 vj [A*M]
R9y) =0.7 Vj [Pm]]
5.0
Bax,(8)) =0.9 vj [
0.7
0.5
0.7
x101
x100
Figure C.3. A comparison between (f. and the error bound derived Theorem 4.2, for various estimation crrors g using
Default and Diabetes datasets.
C. Additional Experiments
C.1. Additional Datasets
In Section validated our theoretical results through numerical experiments using real-world datasets. In this section, we further examine the validity of our findings two additional datasets that were not used in Section 5.2. The datasets used here are Default (Yeh, 2009) and Diabetes (Kahn), with details provided in Appendix B. Figure C.3 presents the results of the same experimental procedure applied to these datasets, following the methodology outlined in Section 5.2. In these datasets, variations in the estimation accuracy of the exact values WFs resulted in only minor changes the risk of downstream task. As consequence, visualizations similar to those in Figure 5.2 significantly compromised readability. To address this, we separately plot the observed risks and the theoretical bound derived from Theorem 4.7.
From Figure C.3, we observe that smaller value of Rot, leads to greater reduction in Rf trend is consistent with the behavior of the error bounds illustrated in the same figure. Regarding the rate of decrease in both Rf 3) and the bound with respect to we find that their sensitivity to changes in R is less pronounced in the Default dataset than in the Diabetes dataset. This difference can be attributed to the fact that the Default dataset contains only two WFs, whereas the Diabetes dataset includes four. Consequently, the influence of WFs on downstream tasks is inherently smaller in the Default dataset. Therefore, from the results on these two additional datasets, we further confirm that our derived error bound in Theorem 4.7 successfully capture the relationship between the rate of decrease in Rg (f with increasing and the value of Rot,
increases. This
C.2. Comparison with the Case WFs are Used for the Inputs of f
In this section, we compared the risk of the obtained by directly using X T for training (i.c., g(X") = X") with the experimental results risks presented in Section 5. We focused on the four datasets used in Section 5, the two additional datasets examined in Section C.I exhibited a relatively weaker dependency of the risk of f on the estimation accuracy of g. The training procedure for f remained identical to that described in Section 5. By conducting this comparison, we aim to provide empirical insight into how accurately g must estimate the exact values of WFs in order to improve the generalization performance of f.
Figure C.4 shows the results under the setting where all WFs are complementary features (CFs). Each observation of
19

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Adult
Bank
Kick
Crsous
1407
12.
Figure C.4. Comparison between the risks Section and the risk of ff when g ((x)) all WFs are CFs, and both the mean and standard deviation over five trials are reported.
X"
The results correspond the case where
Abllt
Book
Kick
Census
185
22
Rodial
10.007
-12
412
417
Figure C.5. Comparison between the risks Section and the risk of f when g( = X The results correspond to the case where each WF observed set of size two including the exact value, with mean and standard deviation over five runs reported.
CF is sampled uniformly from all values except the exact one. From this figure, we observe that for the Adult, Kick, and Census datasets, a classification error of g, below 0.5 is sufficient to achieve a model f that outperforms the baseline where g = X" In contrast, for the Bank dataset, the classification error of gj must be below least 0.3 to achieve similar improvement.
Figure C.5 presents the results for the setting in which each observed value of every WF is represented set of size two that includes the exact value. The additional value in the set, apart from the exact value, is uniformly sampled at random. When using such Xw as input to f. each WF is encoded as a one-hot vector, where the entries corresponding to the values in the observed set are set to one. These vectors are then used as inputs to f. From Figure C.5, in contrast to the case where WFs are CFs, we observe that g yielding better performance than the case where gXX) X depends on n. This difference attributed to the fact that X always includes the exact value, whereas estimation via g inevitably produces instances with incorrect values due estimation errors. These results suggest that, for estimating the exact values of WFs, may be more effective to output probability distribution over possible values, rather than predicting single deterministic value. Accordingly, developing methods where g produces distribution as output, along with establishing theoretical framework that accommodates such g. are important future directions for WFL. The findings in this paper are considered to provide a fundamental basis for such extensions.
D. Limitation
In this paper, we consider the basic framework of WFL, where a feature estimation model is constructed for each WF independently, using OFs inputs. Accordingly, framework does not consider approaches that incorporate dependencies among WFs into the construction of feature estimation models. For example, we do not address methods that first estimate the exact values of a given WF and then use those estimates as input features to infer the exact values of other WFs, or approaches that jointly estimate the exact values of multiple WFs within single model. Developing such approaches of practical importance and is left for future work. Furthermore, analyzing such methods would require a theoretical framework for quantifying how well the dependencies among WFs are captured, as well as for modeling these dependencies.
20

---

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features
Theoretical insights presented in this paper considered provide foundational basis for such future investigations.
For similar reasons, methods that construct f and g single unified model and train it jointly are not yet covered by the analysis presented in this paper. Developing and analyzing such methods also constitutes an important direction for future research.
Our analysis does not account for the feature importance of each WF in the downstream prediction task. Intuitively, the estimation accuracy for WF' that are more strongly related to the downstream target variable should have greater impact on the enror bound for learning f. compared to those WFs that are weakly related or irrelevant. However, the error bound we derived does not account for such feature importance and thus cannot differentiate the relative contributions of individual WT'. Therefore, deriving error bound that incorporates feature importance remains important direction for future work. It is considerd that the results presented in this paper provide solid foundation for such an extension.
21


Reviews:
[{"review_id": "NemMTqHebU", "reviewer": "Reviewer_guZX", "summary": "This paper introduces a unified framework for Weak Feature Learning (WFL), which aims to address the challenge of learning with arbitrary discrete weak features (WFs)—features that are incomplete, erroneous, or ambiguous due to various real-world constraints. The authors propose a risk-based formulation that jointly optimizes a feature estimation model to approximate the true WFs and a label prediction model to perform the downstream task. Theoretical guarantees on consistency and error propagation are validated empirically across real-world datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and constructive feedback on our work.\n\n**Extending the Framework to Handle Continuous Weak Features:** \n\nExtending weak features learning (WFL) to continuous weak features (WFs) is an important research direction. We have investigated this and found that replacing the 0-1 loss-based risk in discrete WFL with a mean squared error (MSE)-based risk yields a parallel theoretical result. However, deriving this required a completely different approach, making it difficult to unify both theories in a single paper. Thus, we have compiled continuous WFL separately.\n\nKey differences in continuous WFL are as follows:\n* Continuous WFL requires handling WFs with continuous-valued uncertainties, such as missing or misobserved values, added Gaussian noise, or intervals containing the exact value. \n\n* The estimation error of $g$ in continuous WFL must be measured using metrics suitable for continuous values, such as MSE. \n\n* The theoretical framework of discrete WFL is based on the 0-1 loss, and its derivation heavily relies on the discreteness of WFs (e.g., Theorem 3.1 and Lemma 4.1). Consequently, this theory cannot be directly applied to continuous WFL.\n\nTo establish a parallel theory, we derive an inequality that upper-bounds Lemma 4.1’s LHS by the product of the generalization error of $f$ and the MSE of $g$. Lemma 4.1’s LHS can be bounded using total variation distance and further upper-bounded by KL divergence via Pinsker’s inequality. Assuming $g$’s prediction follows a gaussian distribution, its log-likelihood corresponds to its MSE, allowing the desired inequality to be derived. \n\nThis result establishes a continuous WFL theory aligned with discrete WFL, suggesting that WFL provides a unified framework for both discrete and continuous WFs.\n\n**Scalability of Rademacher Complexity Computations:**\n\nWe agree that computing Rademacher complexity is challenging for high-dimensional data. However, this is a general issue for all analyses relying on Rademacher complexity, not a specific limitation of our work.\n\nOur results provide valuable theoretical insights, such as the convergence rates of error bounds for $f$ and $g$, their mutual interactions, and the impact of WF properties on $f$'s learning. These contributions remain valid regardless of whether Rademacher complexity can be explicitly computed. \n\nIf one needs to estimate error bounds in practice, approximation methods can facilitate Rademacher complexity computation. For instance, dimensionality reduction techniques can compress high-dimensional data before computing Rademacher complexity.\n\nImportantly, the computability of Rademacher complexity does not affect the validity of our theoretical analysis, which remains robust even in high-dimensional settings.\n\n**Incorporating Causal Inference into WFL:**\n\nWe have not yet explored integrating causal inference into WFL, but we agree that this extension is highly intriguing. Inspired by your suggestion, we considered an approach of modeling the observational process of WFs using a Structural Causal Model (SCM).\n\nThe ambiguity in WFs' observations arises from factors such as observational noise, anonymization processes, or the probabilistic nature of their exact values. By modeling the generation process of WFs with an SCM, we believe it is possible to separate these effects, leading to improved estimation accuracy of WFs' exact values and a better understanding of the factors of ambiguity. A potential approach involves Bayesian estimation of an SCM in which the parameters related to observational noise, anonymization, WFs' exact values, and their probabilistic components are treated as latent variables. \n\nFrom a theoretical perspective, an important question is how the structure of the SCM and the quality of latent variable estimation influence the error bounds of $f$. If such error bounds can be derived, they could provide insights into the theoretical foundations of model selection criteria.\n\n\n**Performance Under Adversarial Weak Features:**\n\nWhile our framework was not initially designed for adversarial WFs, your comment prompted us to examine its relevance to such scenarios. We identified two types of adversarial manipulation and found that our framework effectively captures their impact on learning behavior.\n\nFirst, adversarial perturbations to observed values of WFs in training data would likely degrade the accuracy of $g$. Our error bounds account for this, reflecting the increased difficulty of the downstream task due to reduced $g$’s accuracy.\n\nSecond, if only the most informative features are designated as WFs, accurately estimating their values becomes critical. As discussed in Section 4.2, our framework expresses the increased learning difficulty when these exact values cannot be precisely estimated.", "claims_and_evidence": "The claims are well-supported by both theoretical analysis and empirical evidence.", "methods_and_evaluation_criteria": "The evaluation strategy is well-structured and rigorously tests the framework’s effectiveness.", "theoretical_claims": "These theoretical results are well-supported and logically sound.", "experimental_designs_or_analyses": "The experiments are well-designed and convincingly validate the theoretical framework.", "relation_to_broader_scientific_literature": "1 . Weakly supervised learning (WSL) (e.g., complementary labels, positive-unlabeled learning).\n2. Imputation-based methods (ItR) and feature refinement strategies (CFL).", "essential_references_not_discussed": "The paper adequately cites major prior works.", "other_strengths_and_weaknesses": "Strengths\n1. This is the first work to unify WFL methods with finite-sample error bounds and consistency proofs.\n2. Validated on real-world datasets; code and appendix enhance reproducibility.\n3. Bridges ItR, CFL, and weakly supervised learning under a single framework.\nWeaknesses\n1. The proposed framework excludes continuous weak features, restricting applicability.\n2. Rademacher complexity computations may not scale to high-dimensional data.", "other_comments_or_suggestions": "Investigate merging causal inference to distinguish feature ambiguity from noise.", "questions_for_authors": "1. How would you extend the framework to handle continuous weak features (e.g., sensor readings with Gaussian noise)?\n2. How does the framework perform under adversarial weak features (e.g., manipulated inputs)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cq0p40E5SH", "reviewer": "Reviewer_udjK", "summary": "The paper presents a unified framework called WFL for analyzing generalization error in learning tasks involving arbitrary discrete WFs. The authors propose a risk-based formulation that accommodates various types of WFs and a broad range of learning algorithms.\n\n## update after rebuttal\n\nThe author's response has addressed some of my concerns, and I will keep the score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the time and effort the reviewer dedicated to evaluating our work and are grateful for your insightful feedback and constructive suggestions.\n\n**The Impact of Different Types of WFs on the Learning Process and Experimental Datasets:**\n\nOur framework and analysis hold regardless of the type of discrete WFs, which you have also acknowledged in \"Relation to Broader Scientific Literature.\" This generality is possible because, within our framework, the learning of $f$ and $g$ is decoupled: differences in WF types affect only the learning of $g$, while during the learning of $f$, the WF types are concealed, and only $g$ influences $f$. Also, the effect of WF types on $g$ can be thoroughly investigated through existing theories, such as those related to PLL and CLL. Therefore, to validate our theoretical results, it suffices to examine the behavior of $f$ under different levels of $g$'s accuracy rather than testing specific WF types. \n\nMeanwhile, we acknowledge your concern regarding the limited variety of datasets used in our experiments. We take your feedback seriously and are conducting additional experiments on a medical dataset and a dataset related to the prediction of defaults. The results will be included in the Appendix of the Camera Ready version. While our additional experiments are still ongoing, preliminary results indicate qualitatively consistent findings across new datasets.\n\n\n**Computational Complexity and Scalability, and Limitations in Real-World Applications (about Q.1 & .3) :**\n\nWe agree that computational complexity, scalability, and handling complex data distributions are crucial considerations for real-world applications. \n\nOur proposed framework is designed to integrate existing learning algorithms for estimating WFs and predicting a downstream task. Consequently, the computational complexity, scalability, and adaptability to complex data distributions depend on the choice of these algorithms. As for computational complexity, in sequential learning, the computational complexity is determined solely by the sum of computational complexities of the methods applied to learn $f$ and $g$, respectively. In iterative learning, the only additional factor is the number of iterations. Therefore, by selecting appropriate methods within our framework, we can ensure scalability and adaptability to complex data distributions while controlling computational complexity. This flexibility is largely due to the simplicity of our framework.\nHowever, this simplicity also imposes certain limitations, particularly in leveraging domain knowledge for real-world applications. For instance, our framework does not support approaches where dependencies among WFs are exploited to estimate certain WFs first and use their results for estimating other WFs. Addressing this limitation is an important direction for extending our framework, and we plan to explore this in future research. \n\nSince these points were not explicitly discussed in our paper, we appreciate your valuable feedback and will include additional clarifications in the Camera Ready version.\n\n\n**Handling Continuous Weak Features (about Q.2) :**\n\nWe have addressed a similar question from Reviewer guZX. Our framework can be applied to continuous WFs in almost the same manner as for discrete WFs. Please refer to our response (the response “Extending the Framework to Handle Continuous Weak Features” for reviewer guZX) there for details.\n\n**Grammatical Errors and Typos:**\n\nDue to time constraints, we are unable to make extensive revisions at this stage. However, we plan to have the paper professionally proofread before the Camera Ready submission.\n\n\n**Notation Consistency and Template Confirmation:**\n\nThank you for your feedback. We will carefully review the notation to ensure consistency throughout the paper. Regarding the template, we used the official ICML 2025 template downloaded from the conference website, but we will verify it again for correctness.", "claims_and_evidence": "The claims made in the paper are generally supported by theoretical analysis and experimental validation. However, the experimental results are limited to a few datasets, and the impact of different types of WFs on the learning process could be further explored.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem at hand. The authors use a combination of theoretical analysis and empirical validation to demonstrate the effectiveness of their framework.", "theoretical_claims": "I have reviewed the theoretical claims and proofs presented in the paper. The proofs appear to be correct, and the authors provide detailed derivations for their error bounds and consistency conditions. However, I am not an expert in this specific area, so I cannot fully verify the correctness of all the theoretical results.", "experimental_designs_or_analyses": "The experimental design is sound, and the authors provide a clear explanation of their setup and methodology.", "relation_to_broader_scientific_literature": "The paper builds on existing work in WSL and extends it to the problem of learning with WFs. The authors discuss related work in WSL, including semi-supervised learning and learning with label noise, and provide a unified framework that accommodates various forms of WFs. The paper also connects to prior work on ItR and CFL, providing a theoretical foundation for these methods.", "essential_references_not_discussed": "I am not an expert in this specific area, so I have no suggestion on more refrerences.", "other_strengths_and_weaknesses": "The paper's main strengths lie in its theoretical contributions and the unified framework it provides for analyzing generalization error in learning tasks with weak features.  However, the impact of different types of WFs on the learning process could be further explored.", "other_comments_or_suggestions": "- The paper is well-written, but there are a few minor grammatical errors and typos that could be corrected. For example, in Section 3.2, the phrase \"The primary factor reducing explainability is the inaccuracy of information provided by WFs\" could be rephrased for clarity.\n\n- The notation in some of the equations could be more consistent. For example, in Equation (3.4), the use of $\\lambda$ as a weighting parameter is clear, but the notation could be more consistent with the rest of the paper.\n\n\n***Note:*** the template of this paper seems to be different from the official template.", "questions_for_authors": "- Can the authors provide more details on the computational complexity and scalability of the proposed methods, particularly for large-scale datasets?\n\n- How does the proposed framework handle continuous weak features, and are there any limitations in this regard?\n\n- Could the authors discuss any potential challenges or limitations in applying the proposed framework to real-world applications, particularly in domains with complex data distributions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TfgABsuwa8", "reviewer": "Reviewer_Wr5c", "summary": "In this paper, the authors propose a unified framework called weak feature learning which accommodates arbitrary discrete weak features and a broad range of learning algorithms. The authors also introduce a class of algorithms that learn both the estimation model for weak features and the predictive model for downstream task and present generalization error analysis, as well as, theoretical conditions necessary for achieving consistency of the learning method.\n\n ### update after rebuttal\n\nThe authors have answered my questions and I will maintain my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and thorough review of our manuscript, and for pointing out areas for further clarification and improvement.\n\n**Necessity of Theorem 3.1 Given Lemma 4.1 (about Question 1.):**\n\nWe agree that Lemma 4.1 provides a tighter bound and that Theorem 3.1 can be derived from it. However, we introduced Theorem 3.1 to improve the clarity of our discussion. While Lemma 4.1 focuses on expressing the relationship between the risks of $f$ and $g$ for detailed analysis, Theorem 3.1 is intended to establish the validity of our proposed framework. Specifically, Theorem 3.1 explicitly illustrates the correspondence between the risk $R_l(f)$ in standard supervised learning and the objective function of WFL $R^{\\mathrm{dWFL}}_{l, \\lambda}(f)$. This correspondence is not straightforward to interpret directly from the inequality in Lemma 4.1. Since this clarification was not explicitly stated in our paper, we will include it in the Camera Ready version.\n\n**Dependence on Informative Ordinary (Normal) Features (about Question 2.):**\n\nYour understanding is correct. Since our framework is based on constructing a model that estimates $X^{\\mathrm{w}}$ from $X^{\\mathrm{o}}$​, accurate estimation of $X^{\\mathrm{w}}$ is feasible when $X^{\\mathrm{o}}$ is sufficiently correlated with $X^{\\mathrm{w}}$. However, while a strong correlation between $X^{\\mathrm{o}}$​ and $X^{\\mathrm{w}}$​ is a practical condition for achieving good performance, our theoretical results hold regardless of this assumption.\n\n**Experimental Design to Demonstrate the Effectiveness of Theorem 4.4 (about Question 3.):**\n\nTo demonstrate the effectiveness of Theorem 4.4, we would need to generate multiple functions $f$ with varying accuracy and examine whether the learned results of $g$ exhibit a trend similar to the error bound provided by Theorem 4.4.\nThere are two primary methods to construct $f$ with varying accuracy: (1) training $f$ directly using different learning settings and (2) constructing $f$ in a manner similar to $g$ in Section 5.2. \n\nThe first approach can be implemented by training a neural network while carefully adjusting training hyperparameters and dataset composition. However, ensuring that these adjustments are not arbitrary is challenging, which may introduce biases and compromise the justification and validity of the experimental results.\n\nThe second approach, following Section 5.2, is not feasible because the constructed $f$ would make $g$ untrainable. Since $f$ makes random predictions with a fixed accuracy, the empirical risk $\\hat{R}_{l,f}(g)$ becomes non-differentiable with respect to $g$, preventing effective learning.\n\nDue to these limitations, this experimental design is challenging. However, we note that the error bound for $f$ in Theorem 4.2 shares a highly similar form with the bound for $g$ in Theorem 4.4. Given the verification of $f$'s bound in Section 5.2, we can reasonably infer the validity of $g$'s bound as well.\n\n\n**Typographical Error in Theorem 3.1 Proof:**\n\nThank you for pointing this out. We confirm the mistake and will correct it in the Camera Ready version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check all the proofs. However, in the proof of Theorem 3.1, after the second inequality, $M_l$ should be $U_l$.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The results of this paper elucidates the interplay between estimation error of weak features and prediction error of a downstream task which seems to be an important problem.", "essential_references_not_discussed": "Yes.", "other_strengths_and_weaknesses": "1. Once Lemma 4.1 is established, why Theorem 3.1 is needed?\n\n2. Since the features $x_w$ and $x_0$ are disjoint set of features, when is it possible to learn weak features $x^w$ from normal features $x_0$? Is it inherently assumed that $x_0$ contains enough  information regrading $x_w$ so that the estimation function $g$ makes sense?\n\n3. How would one design experiment to demonstrate the effectiveness of Theorem 4.4?", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "La4BuSoRnb", "reviewer": "Reviewer_VwNg", "summary": "The paper presents a unified formalization and theoretical analysis of discrete Weak Features Learning (WFL) to handle learning with arbitrary discrete weak features (WFs). It introduces a set of algorithms that jointly learn the estimation model for WFs and the predictive model for a downstream task while conducting a generalization error analysis under finite-sample conditions. Additionally, the authors provide empirical results that support their findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful evaluation and valuable suggestions to improve our paper.\n\n**Comparison with Benchmark Methods:**\n\nThe most relevant benchmark is using WFs directly as input features, because our framework is designed to improve upon this approach by accommodating various learning methods for learning $f$ and $g$.\n\n\nSince this study focuses on the theoretical understanding of WFL, our experiments were conducted to validate the theoretical results rather than compare against the benchmark method. However, we recognize the importance of empirical comparisons with the benchmark method and will include them in the Appendix of the Camera Ready version.\n\nWe are currently conducting additional experiments, and preliminary results indicate that when $g$ is randomized, our framework outperforms the baseline if $g$’s error rate is below 0.5. Thus, for problem settings where the exact values of WFs can be well estimated, our framework could be a valuable tool for practitioners.\n\n**Clarification on the Second Inequality in A.1:**\n\nIn p.11 lines 567–568, the 0-1 loss is 0 when $g$ correctly predicts the exact values of all WFs and 1 otherwise. In contrast, in lines 570–571, the sum of the 0-1 losses is 0 when $g$ correctly predicts all WFs and equals $k \\ge 1$ when $g$ mispredicts $k$ WFs. Based on this fact, the second inequality in p.11 Eq.(A.1) holds.\n\n**Derivation from (a1) and (a2) in Eq.(A.11) to Eq.(A.12) in A.2:**\n\nEq. (A.11) shows that the LHS of Eq. (A.12) is upper-bounded by the expectation of the sum of (a1) and (a2). After Eq.(A.11), we analyze (a1) and (a2) separately. Substituting these results into the RHS of Eq.(A.11) and simplifying the expectation operation yields the RHS of Eq.(A.12), confirming its validity.\n\n**Clarification on the Two Inequalities in A.3 (P.15, Line 770):**\n\nThe question refers to lines. 827–829, but the uniform law of large numbers is actually used from l. 770 onward, so we interpret the comment as referring to that part. This law ensures uniform convergence of the empirical expectation to the true expectation over the function class, given that the finite samples are i.i.d. In the top two equations on p.15, the samples used for each empirical risk are indeed i.i.d., validating these inequalities. We will add a reference to Chapter 3.1 (pp. 30–34) in [Mohri 2018] in the Camera Ready version for further clarification.\n\n**Justification of the Second Equality in A.5 (Line 871):**\n\nThank you for your valuable comment. We acknowledge that the second equality in line 871 does not hold due to a minor mistake. We will not use this equality and instead consider only the first inequality in line 871. Additionally, we will replace $\\mathfrak{R}^*\\_{n}(\\mathcal{G}\\_j(r\\_j, \\bar{S}\\_j))$ with $\\mathfrak{R}^*\\_{n}( \\tilde{\\mathcal{G}}\\_j(r\\_j, \\bar{S}\\_j))$ in lines 874–887 and in Eq. (4.10) of Theorem 4.4. We explain why this modification is sufficient in the next section.\n\nThis correction does not affect the subsequent discussion and the theoretical results of the paper. This is because, in the discussion from Theorem 4.4 onward, including Theorem 4.5, the original assumption on the convergence rate of $\\mathfrak{R}^*\\_{n}(\\mathcal{G}\\_j(r\\_j, \\bar{S}\\_j))$  is simply replaced with the same assumption for $\\mathfrak{R}^*\\_{n}( \\tilde{\\mathcal{G}}\\_j(r\\_j, \\bar{S}\\_j))$, and these assumptions are equally valid. We will correct this in the camera-ready version.\n\n**Clarification on the Derivation of A.5 (Lines 876-886):**\n\nThe equations in A.5 (lines. 876–886) can be derived by applying Eq. (A.33) and the equation in lines. 870–873 to the RHS of Eq. (A.32). We acknowledge that this step was not explicitly stated and will clarify it in the Camera Ready version.\n\n**Theoretical Contributions of Theorems 4.3 and 4.5:**\n\nFor Weakness 1.1, the discussion on convergence rates appears follows Theorems 4.2 and 4.4, where error bounds are established (lines 258–320, 356–378). We used “rate of decrease” in the discussion but recognize that “convergence rate” is more precise. We will revise this in the Camera Ready version.\n\nRegarding Weakness 1.2, our study provides insights that go beyond a simple combination of existing theoretical results on $f$ and $g$. While their learning methods rely on prior approaches, a theoretical analysis of WFL requires explicitly modeling their interactions. We address this through Theorems 4.2 and 4.4. Theorems 4.3 and 4.5 establish the consistency of WFL by integrating existing theories using the results of Theorems 4.2 and 4.4. We acknowledge that this was not sufficiently clear and will provide further clarification in the Camera Ready version.\n\n**Procedure of Our Algorithm Class:**\n\nWe will make the algorithm class procedure easier to understand in the Camera Ready version.\n\nReference: \n\n[Mohri 2018] Mohri, M. Foundations of machine learning, 2nd edition. 2018.", "claims_and_evidence": "The authors offered both theoretical and empirical analyses to support all of their claims.", "methods_and_evaluation_criteria": "1. The proposed methods and evaluation criteria are suitable for the problem. \n\n2. However, no benchmark methods are provided to demonstrate and compare the performance of the proposed methods.", "theoretical_claims": "I checked the proof of the theoretical claims. Most of them are correct except that some key steps are not clear and demonstrating enough: for example\n\n1.P11. A.1 The second inequality arises from the decomposition of the 0-1 loss. This step is not clear enough.\n\n2.A.2 How (a1) and (a2) leads to (A.12) is not clear enough.\n\n3.A.3 P15, top two inequalities under From the uniform law of large numbers... (line 827-829) ? Why do they hold? Here is not clear enough.\n\n4.A.5 line 871, why does the second equality hold?\n\n5.A.5 line 876-886, how the analysis above this inequality leads to this result need to analyze clearly. This is not a simple step.", "experimental_designs_or_analyses": "The experimental design effectively supports the theoretical result. However, the absence of a baseline method comparison means there is no performance evaluation against existing methods. This limitation is unfavorable for practitioners.", "relation_to_broader_scientific_literature": "This study offers comprehensive theoretical insights into various problem settings, such as ItR and CFL, involving discrete WFs. This is beneficial to the statistical learning community.", "essential_references_not_discussed": "The literature review is extensive.", "other_strengths_and_weaknesses": "**Other Strengths:**\n\n1. The paper's motivation and structure are clear and reader-friendly. \n\n2. The notation and setup are also clearly presented.\n\n3. Codes are provided in the supplementary materials, which benefit practitioners.\n\n**Other Weaknesses:**\n\n1.Theorem 4.3 and Theorem 4.5 lack theoretical contributions. \n\n1.1 These two results provide only consistency findings; no convergence rates are presented.\n\n1.2 The proofs of these theorems rely predominantly on results from existing references.", "other_comments_or_suggestions": "1.Suggestion: Add an algorithm table to summarize the methods.", "questions_for_authors": "1. Is it possible to add the details of proof for my listed confusions in the Theoretical Claims* section?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper is concerned with learning with Weak Features. It provides a framework which consists of formulation of the problem of learning Discrete Weak Features and using this formulation several algorithms are derived. It provides proofs of consistency as well. These are novel contributions and should be interesting to ICML community.
However,  during the discussion phase there was no champion and thus it would be difficult to argue for a strong accept. Additional results involving Causality or continuous values.
Decision: Accept (poster)