A Characterization of List Regression
There has been a recent interest in understanding and characterizing the sample complexity of list learning tasks, where the learning algorithm is allowed to make a short list of $k$ predictions, and we simply require one of the predictions to be correct. This includes recent works characterizing the PAC sample complexity of standard list classification and online list classification. Adding to this theme, in this work, we provide a complete characterization of list PAC regression. We propose two combinatorial dimensions, namely the $k$-OIG dimension and the $k$-fat-shattering dimension, and show that they characterize realizable and agnostic $k$-list regression respectively. These quantities generalize known dimensions for standard regression. Our work thus extends existing list learning characterizations from classification to regression.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationregressionSimilar Papers 제목 키워드 기반
Autocart -- spatially-aware regression trees for ecological and spatial modeling
Many ecological and spatial processes are complex in nature and are not accurately modeled by linear models. Regression trees promise to handle the high-order interactions that are present in ecological and spatial datas…
regressionTRIAGE: Characterizing and auditing training data for improved regression
Data quality is crucial for robust machine learning algorithms, with the recent interest in data-centric AI emphasizing the importance of training data characterization. However, current data characterization methods are…
regressionFusionCell: Cross-Attentive Fusion of Layout Geometry and Netlist Topology for Standard-Cell Performance Prediction
Standard cells form the building blocks of digital circuits, so their delay and power critically influence chip-level performance; yet characterization still relies on slow simulation sweeps, and many fast predictors ign…
Probabilistic Symbolic Regression for Equation Discovery via Operator-induced and Regularized Symbolic Forests
Symbolic regression has emerged as a powerful tool for artificial intelligence-driven scientific discovery by learning interpretable analytical expressions that reveal governing relationships directly from data. Existing…
Physically Interpretable Probabilistic Domain Characterization
Characterizing domains is essential for models analyzing dynamic environments, as it allows them to adapt to evolving conditions or to hand the task over to backup systems when facing conditions outside their operational…
Autonomous VehiclesDomain Adaptation