Research map / Learning theory and algorithms / Kernels and regression theory

A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features

ICML 2025 · Learning theory and algorithms › Kernels and regression theory · approach: Statistical perspectives on generalization

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a unified risk-based framework (WFL) and learning algorithm class (LAC-dWFL) for arbitrary discrete weak features, with finite-sample generalization error bounds for sequential and iterative learning of feature estimators and predictors.

Problem

Learning predictive models when input features are weak (misobserved, missing, or partially observed, e.g., complementary features or candidate sets) lacks a unified finite-sample theory covering estimation of the true feature values and the downstream predictor.

Approach

Formulates discrete weak features learning as a linear combination of a downstream risk under estimated features and a 0-1 estimation risk for each weak feature, defines a learning algorithm class combining three steps (learn estimator g from weak labels, learn f given g, learn g given f), and derives Rademacher-based generalization bounds showing how g's estimation error affects f's bound and whe

Key results

• Empirically, lower estimation error of g yields a faster decrease in Rl,g(fg,S) as n grows, consistent with Theorem 4.2 (estimation error 10% to 90%, averaged over 5 trials).
• Theorem 4.2 implies the bound for f is Op(1/n^1/2) when g is learned via a consistent WSL method, versus Op(1/n^1/4) when g is a constant or the raw weak feature is used.
• The derived bound follows the trend of the actual generalization error but is looser, as it ignores feature importance of WFs.

Measured effects reported in the paper

Surprising findings

• The bound does not account for the feature importance of weak features, so its values differ notably from the actual generalization error despite matching trends.

Limitations

• Restricted to discrete weak features and binary classification in the main text; continuous WFs deferred to a separate paper.
• Bound ignores the feature importance of weak features, leading to loose values relative to actual error.
• Experiments use synthetic estimators for g rather than actual WSL methods for the estimation step.

Experimental setup

Datasets: Adult Bank Marketing Kick Census-Income (KDD)

Benchmarks: Adult Bank Marketing Kick Census-Income (KDD)

Metrics: generalization error Rl,g(f) error bound (Theorem 4.2) estimation error R01

Builds on: impute-then-regress complementary features learning complementary label learning structural risk minimization Lemma on loss discrepancy via Rademacher complexity

Closest papers by meaning

• Unified Analysis of Continuous Weak Features Learning with Applications to Learning from Missing Data (ICML 2025 · similarity 0.93)
• From Linear to Nonlinear: Provable Weak-to-Strong Generalization through Feature Learning (NeurIPS 2025 · similarity 0.87)
• Weak-to-Strong Generalization Even in Random Feature Networks, Provably (ICML 2025 · similarity 0.87)
• A General Framework for Learning from Weak Supervision (ICML 2024 · similarity 0.86)
• Relating Misfit to Gain in Weak-to-Strong Generalization Beyond the Squared Loss (ICML 2025 · similarity 0.86)
• On the Mechanisms of Weak-to-Strong Generalization: A Theoretical Perspective (NeurIPS 2025 · similarity 0.85)