We analyze the computational complexity of Quantum Sparse Support Vector Machine, a linear classifier that minimizes the hinge loss and the norm of the feature weights vector and relies on a quantum linear programming solver instead of a classical solver. Sparse SVM leads to sparse models that use only a small fr…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Sparse Linear Classifiers”
In this paper, we propose a semi-supervised dictionary learning method that uses both the information in labelled and unlabelled data and jointly trains a linear classifier embedded on the sparse codes. The manifold structure of the data in the sparse code space is preserved using the same approach as the Locally Linea…
The nearest-centroid classifier is a simple linear-time classifier based on computing the centroids of the data classes in the training phase, and then assigning a new datum to the class corresponding to its nearest centroid. Thanks to its very low computational cost, the nearest-centroid classifier is still widely use…
Study on recovering supports of multiple sparse vectors from mixed linear measurements.
problem Recovering supports of multiple sparse vectors from a mixture of linear measurements.
method Developed algorithms to identify the support of all component vectors using polynomial and quasi-polynomial number of measurements.
result Polynomial and quasi-polynomial number of measurements sufficient for recovering the supports of all component vectors.
Sparse coding approximates the data sample as a sparse linear combination of some basic codewords and uses the sparse codes as new presentations. In this paper, we investigate learning discriminative sparse codes by sparse coding in a semi-supervised manner, where only a few training samples are labeled. By using the m…
Study on recovering sparse linear classifiers from mixed binary responses.
problem Learning a mixture of sparse linear classifiers from binary responses.
method Query-based approach to identify all sparse vectors from a set.
result Upper bounds on the number of queries required for recovery.
New method for multiclass classification reduces error bounds.
problem High-dimensional multiclass classification with sparse coefficients.
method Sparse multinomial logistic regression with convex penalties.
result Plug-in classifiers achieve minimax generalization error bounds.
For the problem of multi-class linear classification and feature selection, we propose approximate message passing approaches to sparse multinomial logistic regression (MLR). First, we propose two algorithms based on the Hybrid Generalized Approximate Message Passing (HyGAMP) framework: one finds the maximum a posterio…
New research shows the maximum ℓ1-margin classifier doesn't adapt to sparse ground truths.
problem Understanding the limitations of the maximum ℓ1-margin classifier in high-dimensional settings.
method Analyzing convergence and prediction error rates of the maximum ℓ1-margin classifier.
result Proves tight upper and lower bounds for prediction error, showing benign overfitting.
Classifiers based on sparse representations have recently been shown to provide excellent results in many visual recognition and classification tasks. However, the high cost of computing sparse representations at test time is a major obstacle that limits the applicability of these methods in large-scale problems, or in…
Attention mechanism learns to focus on sparse tokens efficiently.
problem Detecting weak, rare, and sparsely located features in long sequences.
method Theoretical analysis and training of a single-layer attention classifier in a sparse-token classification model.
result A single-layer attention classifier can achieve vanishing test error with logarithmic signal strength growth, unlike linear classifiers requiring linear growth.
Several classification methods assume that the underlying distributions follow tree-structured graphical models. Indeed, trees capture statistical dependencies between pairs of variables, which may be crucial to attain low classification errors. The resulting classifier is linear in the log-transformed univariate and b…
Machine learning has played an important role in information retrieval (IR) in recent times. In search engines, for example, query keywords are accepted and documents are returned in order of relevance to the given query; this can be cast as a multi-label ranking problem in machine learning. Generally, the number of ca…
This paper shows neural networks can learn non-linear sparse parities.
problem The challenge of learning non-linear models with neural networks.
method Gradient descent on depth-two neural networks.
result Sparse parities are learnable by neural networks but not by linear methods.
In recent years, the crucial importance of metrics in machine learning algorithms has led to an increasing interest for optimizing distance and similarity functions. Most of the state of the art focus on learning Mahalanobis distances (requiring to fulfill a constraint of positive semi-definiteness) for use in a local …
We consider the problem of learning a non-negative linear classifier with a -norm of at most , and a fixed threshold, under the hinge-loss. This problem generalizes the problem of learning a -monotone disjunction. We prove that we can learn efficiently in this setting, at a rate which is linear in both and…
Efficient algorithms for sparse parameter recovery in mixture models.
problem Support recovery of high-dimensional sparse latent vectors in mixture models.
method Efficient algorithms with logarithmic sample complexity dependence on dimensionality.
result First guarantees on support recovery for various mixture models.
This work builds a fair classification algorithm that abstains from making predictions.
problem Building a fair classification algorithm that incorporates human decision-making and avoids disparities.
method Formalizes the problem of risk minimization under fairness and abstention constraints, derives the optimal classifier, and proposes a post-processing algorithm using unlabeled data.
result The proposed algorithm achieves fairness and abstention guarantees independently of the initial classifier, provided sufficient unlabeled data is available.
We introduce a sparse scattering deep convolutional neural network, which provides a simple model to analyze properties of deep representation learning for classification. Learning a single dictionary matrix with a classifier yields a higher classification accuracy than AlexNet over the ImageNet 2012 dataset. The netwo…
We propose an empirical Bayes estimator based on Dirichlet process mixture model for estimating the sparse normalized mean difference, which could be directly applied to the high dimensional linear classification. In theory, we build a bridge to connect the estimation error of the mean difference and the misclassificat…
Pixel-wise classification, where each pixel is assigned to a predefined class, is one of the most important procedures in hyperspectral image (HSI) analysis. By representing a test pixel as a linear combination of a small subset of labeled pixels, a sparse representation classifier (SRC) gives rather plausible results …
It is by now well-known that small adversarial perturbations can induce classification errors in deep neural networks (DNNs). In this paper, we make the case that sparse representations of the input data are a crucial tool for combating such attacks. For linear classifiers, we show that a sparsifying front end is prova…
We augment linear Support Vector Machine (SVM) classifiers by adding three important features: (i) we introduce a regularization constraint to induce a sparse classifier; (ii) we devise a method that partitions the positive class into clusters and selects a sparse SVM classifier for each cluster; and (iii) we develop a…
We consider high-dimensional binary classification by sparse logistic regression. We propose a model/feature selection procedure based on penalized maximum likelihood with a complexity penalty on the model size and derive the non-asymptotic bounds for the resulting misclassification excess risk. The bounds can be reduc…
Study selective classification with halfspaces, achieving error bounds under Gaussian distributions.
problem Modeling relationships in subsets of data defined by selection rules.
method Sparse linear classifiers for subsets defined by halfspaces, focusing on Gaussian feature distributions.
result First PAC-learning algorithm for homogeneous halfspace selectors with error guarantee $\bigO*{\sqrt{\mathrm{opt}}}$.
Robust Vertex Classificationstat.ML
For random graphs distributed according to stochastic blockmodels, a special case of latent position graphs, adjacency spectral embedding followed by appropriate vertex classification is asymptotically Bayes optimal; but this approach requires knowledge of and critically depends on the model dimension. In this paper, w…
We consider high-dimensional quadratic classifiers in non-sparse settings. The target of classification rules is not Bayes error rates in the context. The classifier based on the Mahalanobis distance does not always give a preferable performance even if the populations are normal distributions having known covariance m…
Deep neural networks (DNNs) are computationally/memory-intensive and vulnerable to adversarial attacks, making them prohibitive in some real-world applications. By converting dense models into sparse ones, pruning appears to be a promising solution to reducing the computation/memory cost. This paper studies classificat…
Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Modelscs.LG
Study resolves conjecture on overparameterized linear models' generalization.
problem Asymptotic generalization of multiclass classification with overparameterized models.
method Gaussian covariates bi-level model, Hanson-Wright inequality variant.
result Min-norm interpolating classifier can be suboptimal compared to noninterpolating classifiers.
Learning from Incomplete Features by Simultaneous Training of Neural Networks and Sparse Codingcs.LG
Develops method to train classifiers on incomplete feature datasets.
problem Training classifiers on datasets with missing feature subsets.
method Simultaneous training of neural networks and sparse coding.
result Classifier trained on incomplete features correctly separates original data.
SVGP KAN integrates sparse variational GP with KANs for scalable probabilistic inference.
problem Lack of probabilistic outputs in standard KANs and cubic scaling of Gaussian Process methods.
method Sparse Variational GP-KAN combines KAN topology with sparse variational inference and permutation-based importance analysis.
result Enables probabilistic KANs to handle larger datasets with linear computational complexity.
PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditsstat.ML
PopArt efficiently solves sparse linear bandits with tighter recovery guarantees.
problem Sparse linear bandits where rewards depend on a few covariates.
method PopArt: a simple, computationally efficient sparse linear estimation method.
result Improved regret bounds compared to state-of-the-art algorithms.
Gradient-based explanations correlate with Android malware classifier robustness.
problem Evasion attacks on Android malware classifiers using sparse perturbations.
method Investigated gradient-based attribution methods for explaining classifier decisions and their evenness, proposing metrics to assess adversarial robustness.
result Gradient-based explanations, especially Integrated Gradients, correlate with adversarial robustness of malware classifiers.
SCOPE iteratively optimizes sparsity-constrained problems without tuning hyperparameters.
problem Optimizing sparsity-constrained problems in signal processing, statistics, and machine learning.
method SCOPE (Sparsity-Constrained Optimization via sPlicing itEration) replaces gradient steps with a splicing operation guided by the objective value.
result SCOPE achieves linear convergence and superior support recovery performance.
AUC (Area under the ROC curve) is an important performance measure for applications where the data is highly imbalanced. Learning to maximize AUC performance is thus an important research problem. Using a max-margin based surrogate loss function, AUC optimization problem can be approximated as a pairwise rankSVM learni…
Study finds exact limits for sparse regression with fewer observations than usual.
problem Understanding sparse linear regression with sublinear sparsity.
method Adaptive interpolation method and modified AMP algorithm.
result Exact asymptotic expressions for mutual information and MMSE in sublinear sparsity.
IDS improves sparse linear bandits by balancing information and regret.
problem Sparse linear bandits in high-dimensional decision-making.
method Information-directed sampling (IDS) with Bayesian regret bounds and empirical Bayesian sparse posterior sampling.
result IDS nearly matches existing lower bounds and significantly reduces regret.
Adaptive classifier optimizes high-dimensional data with spiked covariance structure.
problem Classification of high-dimensional data with spiked covariance structure.
method Adaptive classifier that whitens data, screens features, and applies Fisher linear discriminant.
result The classifier is Bayes optimal under certain conditions and performs well on real and synthetic data.
High dimensional sparse learning has imposed a great computational challenge to large scale data analysis. In this paper, we are interested in a broad class of sparse learning approaches formulated as linear programs parametrized by a {\em regularization factor}, and solve them by the parametric simplex method (PSM). O…
In this paper we propose an algorithm that builds sparse decision DAGs (directed acyclic graphs) from a list of base classifiers provided by an external learning method such as AdaBoost. The basic idea is to cast the DAG design task as a Markov decision process. Each instance can decide to use or to skip each base clas…
Although deep learning has shown great success in recent years, researchers have discovered a critical flaw where small, imperceptible changes in the input to the system can drastically change the output classification. These attacks are exploitable in nearly all of the existing deep learning classification frameworks.…
Improves sparse recovery with non-linear Fourier features.
problem Sparse recovery challenges with non-linear Fourier features.
method Characterizes sufficient data points for perfect recovery.
result Sufficient data points depend on kernel matrix.
We study the problem of efficient PAC active learning of homogeneous linear classifiers (halfspaces) in , where the goal is to learn a halfspace with low error using as few label queries as possible. Under the extra assumption that there is a -sparse halfspace that performs well on the data ()…
PAC-Bayesian bounds improve understanding of K-NN classifier performance.
problem Improving the understanding of K-NN classifier's generalization error.
method PAC-Bayesian analysis applied to K-NN classifier in kernel space.
result PAC-Bayesian bounds provide a function of the number of redundant training examples.
Proposes FARM model combining latent factor and sparse regression.
problem Testing adequacy of latent factor and sparse regression models.
method Factor Augmented sparse linear Regression Model (FARM) with FabTest and ANOVA type tests.
result Model robustness and effectiveness validated through experiments.
Sparse linear models improve neural network debuggability.
problem Improving neural network interpretability and debugging.
method Using sparse linear models over learned deep feature representations.
result The approach leads to more debuggable and accurate neural networks.
Improved online Lasso reduces regret in sparse linear contextual bandits.
problem Sparse linear contextual bandit problem with inefficient sampling.
method Perturbed adversary approach to alleviate sampling inefficiency.
result Online Lasso achieves regret bound.
This paper explores loss landscapes of sparse neural networks, finding unique characteristics compared to dense networks.
problem Understanding the loss landscape of sparse neural networks, especially one-hidden-layer networks.
method Analyzes sparse networks with dense and sparse final layers, focusing on linear and non-linear models.
result Sparse networks can have no spurious valleys under certain conditions, but spurious valleys and minima can exist for wide sparse networks.