Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP
Online sparse linear regression is an online problem where an algorithm repeatedly chooses a subset of coordinates to observe in an adversarially chosen feature vector, makes a real-valued prediction, receives the true label, and incurs the squared loss. The goal is to design an online learning algorithm with sublinear regret to the best sparse linear predictor in hindsight. Without any assumptions, this problem is known to be computationally intractable. In this paper, we make the assumption that data matrix satisfies restricted isometry property, and show that this assumption leads to computationally efficient algorithms with sublinear regret for two variants of the problem. In the first variant, the true label is generated according to a sparse linear model with additive Gaussian noise. In the second, the true label is chosen adversarially.
Code (0)
등록된 구현이 없습니다.
Tasks
feature selectionregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Online Sparse Streaming Feature Selection Using Adapted Classification
Traditional feature selections need to know the feature space before learning, and online streaming feature selection (OSFS) is proposed to process streaming features on the fly. Existing methods divide features into rel…
ClassificationFeature Correlationfeature selectionDual feature reduction for the sparse-group lasso and its adaptive variant
The sparse-group lasso performs both variable and group selection, making simultaneous use of the strengths of the lasso and group lasso. It has found widespread use in genetics, a field that regularly involves the analy…
SPOT-Occ: Sparse Prototype-guided Transformer for Camera-based 3D Occupancy Prediction
Achieving highly accurate and real-time 3D occupancy prediction from cameras is a critical requirement for the safe and practical deployment of autonomous vehicles. While this shift to sparse 3D representations solves th…
Autonomous VehiclesAn Online Sparse Streaming Feature Selection Algorithm
Online streaming feature selection (OSFS), which conducts feature selection in an online manner, plays an important role in dealing with high-dimensional data. In many real applications such as intelligent healthcare pla…
feature selectionFeature Selection using Sparse Adaptive Bottleneck Centroid-Encoder
We introduce a novel nonlinear model, Sparse Adaptive Bottleneck Centroid-Encoder (SABCE), for determining the features that discriminate between two or more classes. The algorithm aims to extract discriminatory features…
feature selection