We consider the online multiclass linear classification under the bandit feedback setting. Beygelzimer, Pál, Szörényi, Thiruvenkatachari, Wei, and Zhang [ICML'19] considered two notions of linear separability, weak and strong linear separability. When examples are strongly linearly separable with margin , they prese…
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,657 papers · 148 categories
Trend · papers per month
48 results for “Linear Separability”
This paper investigates how data augmentation improves linear separation of manifold data.
problem Understanding how data augmentation enhances linear separation of manifold data.
method Investigates the conditions under which self-supervised representations can linearly separate multi-manifold data.
result Self-supervised learning can linearly separate manifolds with a smaller distance than unsupervised learning.
New algorithms improve blind source separation for linear-quadratic mixtures.
problem Blind source separation of linear-quadratic mixtures under separability assumptions.
method Proposed two algorithms: SNPALQ and BF. SNPALQ generalizes SNPA for LQ model, BF post-processes SNPALQ.
result Proven robustness and computational tractability of SNPALQ in separating sources even with noise.
In this paper, we presented a novel semi-supervised one-class classification algorithm which assumes that class is linearly separable from other elements. We proved theoretically that class is linearly separable if and only if it is maximal by probability within the sets with the same mean. Furthermore, we presented an…
Adam optimizes linear classifiers with separable data.
problem Understanding Adam's implicit bias in linear logistic regression.
method Study of Adam's behavior on linearly separable data.
result Adam converges to a linear classifier with maximum -margin.
The paper extends optimal transport for linear separability of sheared distributions in supervised learning.
problem Learning on the space of probability measures using shifts and scalings.
method Embedding probability measures into spaces using optimal transport, then applying regular machine learning techniques.
result Sheared distributions can be linearly separated under certain conditions, with bounds on transformations.
Neural networks use their hidden layers to transform input data into linearly separable data clusters, with a linear or a perceptron type output layer making the final projection on the line perpendicular to the discriminating hyperplane. For complex data with multimodal distributions this transformation is difficult t…
We study the problem of efficient online multiclass linear classification with bandit feedback, where all examples belong to one of classes and lie in the -dimensional Euclidean space. Previous works have left open the challenge of designing efficient algorithms with finite mistake bounds when the data is linear…
Shallow Neural Network can Perfectly Classify an Object following Separable Probability Distributioncs.LG
Guiding the design of neural networks is of great importance to save enormous resources consumed on empirical decisions of architectural parameters. This paper constructs shallow sigmoid-type neural networks that achieve 100% accuracy in classification for datasets following a linear separability condition. The separab…
A spectral-based analysis of the separation between two-layer neural networks and linear methodsstat.ML
Spectral analysis shows neural networks separate from linear methods in approximating functions.
problem Separating two-layer neural networks from linear methods in function approximation.
method Spectral-based approach using Kolmogorov width and kernel spectrum.
result Upper and lower bounds on separation, explicit hard functions identified.
A new algorithm finds a separating hyperplane with fewer updates.
problem Finding a separating hyperplane with minimal updates.
method Optimistic Perceptron algorithm.
result The Optimistic Perceptron finds a separating hyperplane with no more than $ rac{1}{γ}$ updates.
New PCstar algorithm discovers causal structure of max-linear Bayesian networks.
problem Discovering causal structure in max-linear Bayesian networks due to non-faithfulness.
method PC algorithm modified with -separation assumptions.
result PCstar algorithm can orient additional edges not possible with standard PC algorithm.
Shallow nonlinear networks can separate classes linearly with polynomially scaling width.
problem Understanding the linear separability of deep networks' features.
method Modeling inputs as a union of low-dimensional subspaces and using random weights and quadratic activations.
result Shallow nonlinear networks can achieve linear separation with polynomially scaling width.
We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, and demonstrate its effectiveness by designing algorithms with improved noise tolerance guarantees for learning linear separators. We consider both the malicious noise model and the adversarial label nois…
StrADiff separates sources from mixtures without labels, using structured priors.
problem Blind source separation of linear and nonlinear mixtures without labeled data.
method Structured Source-Wise Adaptive Diffusion Framework with Gaussian process priors.
result StrADiff can recover latent source trajectories in an unsupervised manner, especially stable in linear mixtures.
Study high-dimensional Bayesian linear regression using variational inference.
problem High-dimensional Bayesian linear regression with product priors.
method Non-linear large deviations theory and variational inference.
result Unique optimizer in variational problem governs posterior distribution under separation condition.
Develops large-sample theory for non-stationary source separation.
problem Lack of large-sample results for non-stationary source separation methods.
method Large-sample theory for NSS-JD method under specific assumptions.
result Consistency of unmixing estimator and its convergence to Gaussian distribution.
Adversarial noises are linearly separable for random neural networks.
problem The challenge of adversarial examples in neural networks.
method Theoretical proof and empirical evidence for two-layer networks with random initialization and neural tangent kernel setup.
result Adversarial noises are linearly separable with corresponding labels.
Transformers can learn noisy linear systems with depth and IID data.
problem Learning noisy linear dynamical systems with transformers.
method Theoretical analysis of multi-layer and single-layer transformers with respect to -testing loss.
result Single-layer transformers have a non-diminishing lower bound on approximation error, suggesting depth separation.
A new method separates data points using entropy minimization over a hypercube.
problem Classifying data points with linear or non-linear decision boundaries.
method Minimizing entropy over a hypercube to find separating parameters.
result Efficient and versatile for linear and non-linear separability.
We show linear XOR classification is possible and propose equality separation for anomaly detection.
problem Linearly separating XOR data.
method Equality separation, adapting SVM objective for data within/outside margin.
result Equality separation can detect both seen and unseen anomalies.
Graph convolution improves linear separability and generalizes to out-of-distribution data.
problem Improving linear separability in semi-supervised classification.
method Applying graph convolution to mixtures of Gaussians in a stochastic block model.
result Graph convolution extends the linear separability regime by a factor of .
We develop randomized (block) coordinate descent (CD) methods for linearly constrained convex optimization. Unlike most CD methods, we do not assume the constraints to be separable, but let them be coupled linearly. To our knowledge, ours is the first CD method that allows linear coupling constraints, without making th…
BELIEF framework interprets GLMs using binary linear models.
problem Understanding and interpreting generalized linear models (GLMs) with binary outcomes.
method Developed a framework called binary expansion linear effect (BELIEF) to interpret GLMs through transparent linear models.
result BELIEF framework reveals perfect predictors in complete separation scenarios.
New findings on robust learning with well-separated data.
problem Learning robust classifiers with well-separated classes.
method Analyzing sample complexity for linear classifiers with robustness.
result For linear classifiers on well-separated data, robust loss is at least $Ω( rac{d}{n})$.
We address the problem of causal discovery from data, making use of the recently proposed causal modeling framework of modular structural causal models (mSCM) to handle cycles, latent confounders and non-linearities. We introduce σ-connection graphs (σ-CG), a new class of mixed graphs (containing undirected, bidirected…
Generalization of an Upper Bound on the Number of Nodes Needed to Achieve Linear Separabilitystat.ML
An important issue in neural network research is how to choose the number of nodes and layers such as to solve a classification problem. We provide new intuitions based on earlier results by An et al. (2015) by deriving an upper bound on the number of nodes in networks with two hidden layers such that linear separabili…
We present an approach to learn the dynamics of multiple objects from image sequences in an unsupervised way. We introduce a probabilistic model that first generate noisy positions for each object through a separate linear state-space model, and then renders the positions of all objects in the same image through a high…
KPCA improves OoD detection by separating InD and OoD data.
problem Insufficiency of PCA in detecting OoD data from InD data.
method Kernel PCA (KPCA) with task-specific kernels.
result KPCA achieves superior OoD detection performance.
slimTrain simplifies DNN training by separating features and adapting hyperparameters.
problem Challenges in training deep neural networks, including non-convexity, non-smoothness, and hyperparameter sensitivity.
method slimTrain exploits separability in DNN architectures to reduce hyperparameter sensitivity and improve convergence.
result slimTrain outperforms existing methods with recommended hyperparameters and reduces sensitivity to remaining hyperparameters.
We provide new results concerning label efficient, polynomial time, passive and active learning of linear separators. We prove that active learning provides an exponential improvement over PAC (passive) learning of homogeneous linear separators under nearly log-concave distributions. Building on this, we provide a comp…
This work examines a semi-blind single-channel source separation problem. Our specific aim is to separate one source whose local structure is approximately known, from another a priori unspecified background source, given only a single linear combination of the two sources. We propose a separation technique based on lo…
Paper develops robust methods for panel data with latent groups, improving inference under group separation violations.
problem Inference in latent group panel models under group separation violations.
method Selective conditional inference approach to derive conditional distribution of coefficients given estimated group structure.
result Valid inference under violations of group separation, superior to traditional asymptotic methods.
New algorithms reduce slate bandit regret for large slates, outperforming existing methods.
problem Non-separable reward functions in slate bandits with many slates.
method Design of algorithms with sub-linear regret.
result Sub-linear regret with respect to the time horizon for large number of slates.
Reservoir computing's success depends on mapping different input time series to separable states.
problem Quantifying the ability of random linear reservoirs to map different input time series.
method Mathematical framework using spectral properties of the connectivity matrix.
result Separation capacity is fully characterized by the spectral properties of the connectivity matrix.
This paper proposes a new evaluation metric and boosting method for weight separability in neural network design. In contrast to general visual recognition methods designed to encourage both intra-class compactness and inter-class separability of latent features, we focus on estimating linear independence of column vec…
Online learning of linear operators between infinite-dimensional spaces is possible but with limitations.
problem Learning linear operators between infinite-dimensional Hilbert spaces in an online setting.
method Online learning approach for linear operators with bounded -Schatten norm, proving impossibility for operator norm.
result Separation between online learnability and uniform convergence for bounded linear operators.
Paper optimizes hyperspherical prototypes for better class separation.
problem Previous HPL approaches either lack principled optimisation or are limited to one latent dimension.
method Develops a principled optimisation procedure and uses linear block codes to create well-separated prototypes in various dimensions.
result Optimal prototype placement is characterized with achievable and converse bounds, showing near-optimality.
Singing voice separation attempts to separate the vocal and instrumental parts of a music recording, which is a fundamental problem in music information retrieval. Recent work on singing voice separation has shown that the low-rank representation and informed separation approaches are both able to improve separation qu…
Grokking occurs in simple binary logistic classification near linear separability and noise.
problem Delayed generalization in binary logistic classification.
method Analytical and empirical insights into gradient descent dynamics near critical points.
result Logistic regression exhibits grokking when training data is nearly linearly separable from the origin with strong noise.
On the achievability of blind source separation for high-dimensional nonlinear source mixturesstat.ML
For many years, a combination of principal component analysis (PCA) and independent component analysis (ICA) has been used for blind source separation (BSS). However, it remains unclear why these linear methods work well with real-world data that involve nonlinear source mixtures. This work theoretically validates that…
Algorithm finds frequencies, amplitudes, and phases of sinusoids in noisy data.
problem Finding frequencies, amplitudes, and phases of sinusoids in noisy data.
method Maximum likelihood approach to estimate tone parameters from contaminated observations. Successively estimates frequencies and jointly optimizes amplitudes and phases.
result Near-linear computational complexity (O(N)) for estimating number of sinusoidal sources.
This paper presents a new ensemble learning method for classification problems called projection pursuit random forest (PPF). PPF uses the PPtree algorithm introduced in Lee et al. (2013). In PPF, trees are constructed by splitting on linear combinations of randomly chosen variables. Projection pursuit is used to choos…
The Trek Separation Theorem (Sullivant et al. 2010) states necessary and sufficient conditions for a linear directed acyclic graphical model to entail for all possible values of its linear coefficients that the rank of various sub-matrices of the covariance matrix is less than or equal to n, for any given n. In this pa…
We present a novel blind source separation (BSS) method, called information geometric blind source separation (IGBSS). Our formulation is based on the log-linear model equipped with a hierarchically structured sample space, which has theoretical guarantees to uniquely recover a set of source signals by minimizing the K…
This paper explains a mechanism called phase collapse that improves image classification accuracy.
problem Understanding the role of non-linearities and convolutional filters in image classification.
method Demonstrates phase collapse as a mechanism that eliminates spatial variability and linearly separates classes.
result Phase collapse improves classification accuracy, while thresholding operators degrade performance.
Eigen-Spike Emergence and Quadratic Equivalents for Conjugate Kernels on Nonlinearly Separable Datastat.ML
Study of eigenvalues in nonlinear kernels for classification of separable data.
problem Understanding the applicability of linear equivalents in nonlinearly separable data classification.
method Analysis of conjugate kernels and their quadratic equivalents for a canonical nonlinearly separable dataset (XOR problem).
result Identification of regimes where nonlinear kernels deviate from linear equivalents, leading to label-aligned eigenspaces.
The paper improves prediction and testing for signals from a linear combination of translated features with Gaussian noise.
problem Predicting and testing signals from a linear combination of translated features with varying scale parameter and Gaussian noise.
method Extends previous off-the-grid prediction results, improves minimal distance between features, proposes a goodness-of-fit test with upper bounds.
result Upper bounds on the minimax separation rate match those for the high-dimensional linear model, matching the lower bound.