Efficient Learning with Partially Observed Attributes

Abstract

We describe and analyze efficient algorithms for learning a linear predictor from examples when the learner can only view a few attributes of each training example. This is the case, for instance, in medical research, where each patient participating in the experiment is only willing to go through a small number of tests. Our analysis bounds the number of additional examples sufficient to compensate for the lack of full information on each training example. We demonstrate the efficiency of our algorithms by showing that when running on digit recognition data, they obtain a high prediction accuracy even when the learner gets to see only four pixels of each image.

This is a full version of the paper appearing in The 27th International Conference on Machine Learning (ICML 2010)

References in corpus (1)

• Optimal Algorithms for Ridge and Lasso Regression with Partially Observed Attributes

Cited by in corpus (19)

• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• On-Device Machine Learning: An Algorithms and Learning Theory Perspective
• An Equivalence between the Lasso and Support Vector Machines
• Classification with Costly Features as a Sequential Decision-Making Problem
• Optimal Algorithms for Ridge and Lasso Regression with Partially Observed Attributes
• Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization
• Active Structure Learning of Bayesian Networks in an Observational Setting
• Coupled Compound Poisson Factorization
• Online and Batch Learning Algorithms for Data with Missing Features
• The Attentive Perceptron
• Attribute Efficient Linear Regression with Data-Dependent Sampling
• Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP
• Few-shot Learning for Unsupervised Feature Selection
• Classification with Costly Features in Hierarchical Deep Sets
• Feature Multi-Selection among Subjective Features
• Rapid Learning with Stochastic Focus of Attention
• Focus of Attention for Linear Predictors
• Online Sparse Linear Regression
• Data-Driven Online Decision Making with Costly Information Acquisition