Research map / Label-efficient and robust learning / Recognition and long-tail

One-Pass Feature Evolvable Learning with Theoretical Guarantees

ICML 2025 · Label-efficient and robust learning › Recognition and long-tail · approach: Contrastive representation theory

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 Kernel Ortho-Mapping (KOM) discrepancy to characterize relationships between old and new feature spaces and a one-pass online kernel learner (OPFES) using random Fourier features for feature evolvable streams, with regret/error bounds.

Problem

Feature evolvable learning on data streams where old features vanish and new features emerge; needs a formal characterization of feature-space relationships and a one-pass method without storing past data.

Approach

Defines the KOM discrepancy, a rotation-invariant distance between kernel mappings of two feature spaces, shows it bounds the gap between optimal classifiers, and optimizes it in one pass via random Fourier features and mirror descent, combined with ideal-kernel label information and reuse of the old model.

Key results

• OPFES achieves the lowest mean CER on 15 of 20 datasets with 5 ties and no losses against align-FESL (win/tie/loss 15/5/0) and 20/0/0 against ker-ROGD, ker-FESL, rff-ROGD, lin-ROGD, lin-FESL and OCDS.
• On pol, OPFES CER is 0.0654 ± 0.0036 versus 0.0686 for rff-FESL and 0.0956 for ker-ROGD; on letter 0.1354 vs 0.1557 for rff-FESL.
• Ablation on Pol shows removing KOM discrepancy raises CER from 0.0654 to 0.1290, and removing the previous-model initialization raises it to 0.1418.

Measured effects reported in the paper

Surprising findings

• OPFES is worse than rff-FESL on acoustic, runwalk and higgs, attributed to class imbalance hurting the ideal-kernel learning.

Limitations

• Theoretical analysis of the KOM discrepancy is limited to binary classification.
• Performance degrades on class-imbalanced datasets (acoustic, runwalk, higgs) due to hard ideal-kernel learning.
• Experiments restricted to shift-invariant Gaussian kernels with random Fourier features.

Experimental setup

Datasets: jungle splice bioresponse christine svmguide1 usps aileron pol elevators magic letter house

Benchmarks: jungle splice bioresponse christine svmguide1 usps aileron pol elevators magic letter house

Metrics: cumulative error rate (CER)

Baselines: align-FESL rff-ROGD rff-FESL ker-ROGD ker-FESL lin-ROGD lin-FESL OCDS

Builds on: random Fourier features Fourier online gradient descent kernel alignment FESL (Hou et al.) ideal kernel

Closest papers by meaning

• Storage Fit Learning with Feature Evolvable Streams (AAAI 2021 · similarity 0.87)
• Learning with Feature Evolvable Streams (NeurIPS 2017 · similarity 0.86)
• On the Efficiency of ERM in Feature Learning (NeurIPS 2024 · similarity 0.84)
• On the Consistency of Kernel Methods with Dependent Observations (ICML 2024 · similarity 0.83)
• From Kernels to Features: A Multi-Scale Adaptive Theory of Feature Learning (ICML 2025 · similarity 0.83)
• Complexity Matters: Feature Learning in the Presence of Spurious Correlations (ICML 2024 · similarity 0.83)