Linear Classification

Follow this topic Ask about this topic

Latest papers

19 papers3 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Oct 16, 2026

Towards optimal selection schedules for online active learning

We consider the problem of online linear classification, where a stream of unlabeled samples is available, and annotation is costly. We investigate the optimal query policy, that prescribes whether and when a sample should be labeled and used for a training step, or instead discarded, so as to minimize a given objective. We focus on the realizable case, under Gaussian design, in the high-dimensional regime where data dimension and number of unlabeled samples grow proportionally. We consider two objectives: 1) the generalization error under a labeling budget, and 2) a cumulative cost function where mistakes have unit cost and queries cost

Δ

. We first show that the myopic policies that greedily minimize at all times the increment in the objective correspond to either small or intermediate-margin policies, that prescribe the selection of samples whose margins fall within certain intervals that shrink with time. Within this class, we numerically ascertain the optimal schedules for the selection thresholds that minimize the final values of the objectives. Taking inspiration from the myopic policy for the cumulative cost, we design a very simple query policy schedule that we compare to other proposed heuristics, on synthetic data and real medical image datasets. Finally, we discuss myopic policies for two-layer neural networks, and exemplify how naive margin-based policies can cease to be optimal.

Hugo Cui, Francesca Mignacco, Francesco Mori

Université Paris-Saclay, CNRS, Laboratoire de mathématiques d’Orsay, 91405, Orsay, France · Joseph Henry Laboratories of Physics and Lewis–Sigler Institute, Princeton University, Princeton NJ 08544, USA · Initiative for the Theoretical Sciences, The Graduate Center, City University of New York, 365 Fifth Ave, New York NY 10016, USA +1

Active Learning Linear Classification Margin-Based Learning Cost-Sensitive Learning

Oct 2, 2026

Ideal Paths for Approximating Logistic Gradient Descent Trajectories at Large Initialization

Modern training on a new task often starts from a previously trained model rather than from scratch, raising the question of how this initialization affects the subsequent training trajectory. Classical implicit-bias results characterize the direction selected by prolonged training, but this direction alone does not provide information regarding the intermediate behavior. We address this question through a geometric approximation of full-batch logistic gradient descent (GD) trajectories on strictly linearly separable data, with large initialization of scale

R

motivated by prior training. From any limiting normalized initial position, we use minimum-norm projection rules to construct a unique continuous ideal path consisting of finitely many linear segments. The path has two stages: negative-margin correction followed by minimum-margin growth. We prove that, after an explicit two-stage time reparameterization, the fixed-step GD trajectory divided by

R

converges uniformly to this path on every fixed parameter interval as

R\to\infty

. Further, our quantitative error bounds account for initialization perturbations and the transition between stages. This approximation provides asymptotic formulas for peak evaluation loss and cumulative training loss. In particular, peak evaluation loss can grow linearly in

R

even when both endpoint losses tend to zero. The cumulative losses in the correction and margin-growth stages, normalized by

R^2

and

R

, respectively, converge to explicit limits. Experiments on controlled geometries and fixed image features complement our theoretical results.

Junjie Xiao, Huiwen Jia

Department of Mathematics, Peking University · Department of Industrial Engineering and Operations Research, University of California, Berkeley

Logistic Regression Neural Network Initialization Linear Classification Gradient Descent Dynamics

Sep 27, 2026

On the Two Faces of Adam in Separable Linear Classification

We consider the behavior of deterministic, full-batch, bias-corrected Adam in separable linear classification with softmax parametrization under log-loss. In this setting, under a wide range of conditions Adam is known to approach max-norm-margin optimality when its stability constant

ε

is zero, while with a positive

ε

, it is known to approach Euclidean-margin optimality. Our main contribution is the quantitative description of Adam's behavior for small fixed positive

ε

. We give sufficient conditions under which an Adam-trained classifier nearly maximizes the max-norm margin before the updates become gradient-like. We also show that the classifier reaches a fixed target Euclidean margin only much later. Specifically, we show that for polynomially decreasing stepsizes with exponent

a

, where

1/3<a<1

, the updates become approximately proportional to the negative gradient after

Θ(\log(1/ε)^{1/(1-a)})

iterations. At that time, the classifier still nearly maximizes the max-norm margin. Reaching a fixed target Euclidean margin above that of every max-norm-optimal classifier, but below the optimum, is shown to require

ε^{-Θ(1)/(1-a)}

iterations. Under inverse-linear stepsize decay (

a=1

), the update transition takes polynomially many iterations, whereas reaching the target margin takes exponentially many. Experiments support these predictions. The later change in the classifier can improve or worsen generalization after training error reaches zero, connecting the analysis to grokking and its reverse.

Chen Fan, Csaba Szepesvári

University of Alberta

Implicit Bias Classification Adaptive Gradient Methods Gradient Descent Dynamics Linear Classification

Sep 18, 2026

Strategic Classification Has a Missing Lever: Audit Risk

Strategic classification studies how a decision maker should choose a classifier when the agents being classified can adjust their features in response to it. In existing models, the classifier is the only instrument available to the decision maker, and therefore a feature that is predictive but easy to fake can only be down-weighted or discarded. However, in many settings the decision maker can also verify: lenders verify income, admissions offices check documents, and tax authorities audit returns. In this paper, we propose a model of strategic classification in which the firm jointly designs a linear classifier and an audit profile, which assigns to each fakeable feature a probability of detection and a penalty when caught. We show that under linear costs, the classifier affects the audit problem only through the distribution of gaming rents it induces, so that the joint design problem decomposes into the choice of a score rule and an audit allocation problem. We use this decomposition to characterize the optimal audit allocation, to identify when the allocation problem is tractable and when it is NP-hard (namely, when agents can game through overlapping features under an inspection cap), and to bound the regret of a firm that has to learn the rents by auditing. We further show that audit intensity is a quantity to be tuned rather than maximized: welfare is single-peaked in it, and a firm and a social planner disagree on the mix of detection and penalty that delivers a given level of deterrence. Notably, two populations with identical costs and causal structure can game in one domain and improve in the other, a difference that a cost-only model cannot account for. Together, our findings highlight that whether a feature is ``gameable'' depends on the institution's verification policy as much as on the feature itself.

Raman Ebrahimi, Massimo Franceschetti

Department of Electrical and Computer Engineering, University of California, San Diego

Linear Classification Strategic Classification Game Theory

Aug 30, 2026

Multiclass Linear Perceptrons with Multiplicative Margins

This paper introduces a family of multiclass linear Perceptron classifiers with a multiplicative margin mechanism (MMPerc), as an alternative to standard margin-free and additive margin Perceptrons. The multiplicative formulation enforces classification confidence by requiring the true class score to exceed that of competing classes by a specified fraction of itself, rather than by a fixed additive threshold. This avoids dependence on score magnitudes arising from varied norms of data and class weight vectors. We propose several architectural and algorithmic variants of MMPerc, derive associated loss functions and mistake bounds for both linearly separable and non-separable data, and analyze key design considerations, including bias, margin threshold selection, and training modes. Extensive experiments on synthetic and real datasets show that MMPerc classifiers typically outperform the standard Perceptron, as well as classic baselines such as Support Vector Machines and Ridge classifiers. Owing to their simplicity, minimalistic design, and computational efficiency, MMPerc classifiers are promising candidates for conventional machine learning tasks, linear evaluation of Deep Neural Networks, integration with Hyperdimensional Computing / Vector Symbolic Architecture representations, and deployment in resource-constrained applications.

Dmitri Rachkovskij, Evgeny Osipov, Olexander Volkov +2

Department of Computer Science, Electrical and Space Engineering, Luleå University of Technology, 971 87 Luleå, Sweden · Institute of Information Technologies and Systems, 03187 Kyiv, Ukraine · Centre for Data Analytics and Cognition, La Trobe University, Melbourne, Australia +2

Linear Classification Multiclass Classification Classification

Jul 21, 2026

Fundamental limits of distributed multiclass classification from simple binary decisions

We consider the problem of constructing a

K

-class classifier from the combination of

O(\log K)

simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the

K

class centers are independent Gaussian points in

\mathbb R^d

and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.

Ioannis Papageorgiou, Srinivas Nomula, Ayalvadi Ganesh +2

School of Mathematics, University of Bristol · Department of Electrical Communication Engineering, Indian Institute of Science.

Linear Classification Multiclass Classification Classification Statistical Learning Theory

Jul 5, 2026

Fast, Parallel, Query-Efficient Binary Classification

We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size

n

with normalized

d

-dimensional features. Letting

Φ\in \mathbb{R}^{n \times d}

denote the feature matrix and

γ

the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in

\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2(ω+1)/3})

-sequential running time (work),

\tilde{O}(γ^{-2/3})

-parallel (computational) depth, and accesses

Φ

only through

\tilde{O}(γ^{-2/3})

-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a

\tilde{O}(γ^{-2/3}\, \operatorname{nnz}(Φ) + γ^{-2})

-sequential running time that uses

\tilde{O}(γ^{-2/3})

-matvecs to

Φ

, but achieves only

\tilde{O}(γ^{-4/3})

-parallel depth. Both algorithms match the near-optimal deterministic matvec complexity recently established by Kornowski and Shamir [2025], Karmarkar et al. [2026] and achieve improved sequential runtime and parallel depth, albeit at the expense of using randomness.

Ishani Karmarkar, Liam O'Carroll, Aaron Sidford

Stanford University

Binary Classification Classification Linear Classification

Jun 7, 2026

Directional Linear Separability of Neural Representations: Geometry and Transformations

Neural networks build representations through affine maps and nonlinear activations. Injective affine maps preserve linear separability, raising the problem of how they prepare data for nonlinear improvement and how much gain can be guaranteed before complete separation. We introduce the directional linear separability measure (D-LSM), which quantifies unavoidable competing-sample intrusion over affine halfspaces retaining every target sample, characterize its supporting geometry, and prove invariance under injective affine embeddings. For gated activations including ReLU, GELU, and SiLU, pre-activation projection bounds yield sufficient conditions for preserving all previous exclusions and recovering additional samples, with a gain bound determined by the certified recovery count. Under an aggregate-tube condition, an explicit affine construction realizes recovery with sufficient width, scaling conditions, and simultaneous multiclass guarantees through a shared layer. Exact controlled experiments compare certified and realized gains, assess certificate coverage, and exhibit bound attainment before complete separation and in affine-tube constructions. In learned Vision Transformer (ViT) representations, a feasible lower-bound estimator yields earlier post-GELU saturation certificates of exact separability, while boundary transport numerically supports affine invariance.

Yi Wei, Xuan Qi, Suorong Yang +1

DITEN University of Genoa, Genoa, Italy · State Key Laboratory of Novel Software Technology School of Artificial Intelligence Nanjing University, Jiangsu, China

Neural Representation Geometry Linear Classification

Jun 4, 2026

How abundant are good interpolators?

Let

S

be the set of unit norm linear classifiers

θ\in \mathbb{R}^d

which correctly classify every point of a labeled dataset

(X_i,y_i)_{i=1}^n

,

X_i \in \mathbb{R}^d

,

y_i \in \{-1,+1\}

, with a possibly negative margin

κ

fixed in advance. Under two natural data-generating distributions of the

(X,y)

pairs -- a Gaussian mixture model and a logistic model with Gaussian features -- and in the proportional regime

n/d \to α

with small enough

α

, we establish a large deviation principle on the event that a point

θ

chosen uniformly at random from

S

achieves a given generalization error, with high probability over the choice of the data. The associated large deviation rate function is deterministic and describes the proportion, at the exponential scale in

d

, of interpolating classifiers having a given desired performance. As a consequence, we establish the following concentration phenomenon: all but an exponentially small fraction of interpolating classifiers have approximately the same generalization performance given by the unique maximizer of this rate function. We numerically compare this maximizer to the performance of empirical risk minimization by gradient descent and to the performance of a natural linear program, both finding a point in

S

, and deduce that in the overparametrized regime of small

α

, these efficient procedures outperform the vast majority of interpolators, pointing to their nontrivial benign overfitting in this setting.

August Y. Chen, Ahmed El Alaoui

Cornell University, Department of Computer Science. Ithaca, NY, USA. · Cornell University, Department of Statistics and Data Science. Ithaca, NY, USA.

Linear Classification Benign Overfitting Large Deviation Principles Statistical Learning Theory

May 31, 2026

Linear Strategic Classification with Endogenous Improvements

Classical models of strategic classification treat agents' responses to a deployed classifier as cosmetic: features change, but true labels do not. We study an improvement-aware variant in which strategic responses can change outcomes: agents choose post-deployment features strategically at a cost, and labels are then drawn from a fixed conditional outcome law. We formalize this problem for linear classifiers under a single-index qualification model and linear-decomposable costs. Under these assumptions, agents' best responses reduce to a closed-form shift of the decision boundary, and the resulting improvement-aware classification problem is learnable with linear sample complexity. As post-deployment labels are unavailable a priori, we begin by establishing a generalization bound with oracle access to the outcome law. One of our main contributions is a practical plug-in algorithm that replaces the oracle with an estimate, together with a bound on its improvement-aware error. We also show that the optimal classifier for standard strategic classification is a better proxy for the improvement-aware objective than the non-strategic Bayes-optimal classifier. Experiments on semi-synthetic and synthetic data support these findings and the plausibility of our assumptions.

Siddharth Shrivastava, Mahvith Akshintala, B Vamsha Vardhan Reddy +3

Department of Artificial Intelligence, IIT Hyderabad · IIIT Hyderabad · Departement of Artifical Intelligence, IIT Hyderabad

Strategic Classification Linear Classification Classification

May 20, 2026

Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals

We study the task of agnostic learning of multiclass linear classifiers under the Gaussian distribution. Given labeled examples

(x, y)

from a distribution over

\mathbb{R}^d \times [k]

, with Gaussian

x

-marginal, the goal is to output a hypothesis whose error is comparable to that of the best

k

-class linear classifier. While the binary case

k=2

has a well-developed algorithmic theory, much less is known for

k \ge 3

. Even for

k=3

, prior robust algorithms incur exponential dependence on the inverse of the desired accuracy in both complexity and representation size. In this work, we develop new structural results for multiclass linear classifiers and use them to design fully polynomial-time robust learners with dimension-independent error guarantees. Our first result shows that the standard multiclass perceptron algorithm requires super-polynomially many samples and updates, even with clean labels and Gaussian marginals, revealing a basic obstruction absent in the binary case. Our main positive result is a pairwise improper-learning framework which yields an efficient learner with error

\widetilde O(k^{3/2}\sqrt{\mathrm{opt}})+ε

for general

k

. Additionally, we develop a sharper localization-based framework which leads to error

O(\mathrm{opt})+ε

for

k=3

, and error

\mathrm{poly}(k)\mathrm{opt}+ε

for geometrically regular

k

-class linear classifiers.

Ilias Diakonikolas, Giannis Iakovidis, Mingchen Ma

University of Wisconsin-Madison

Agnostic Learning Multiclass Classification Classification Statistical Learning Theory Linear Classification Robust Classification

May 18, 2026

Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes

k

is at least

3

, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers

\{h_w:x\mapsto \arg\max_{y\in[k]}w_y\cdot x, x\in \mathbb{R}^d, w\in\mathbb{R}^{kd}\}

using at most

O(k^2\cdot (d\log d+\log k))

samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e.

k=2

, our result is strictly stronger than all prior works.

Rita Adhikari, Shiwei Zeng

Augusta University

Multiclass Classification Classification Learning with Noisy Labels PAC Learning Linear Classification

Apr 13, 2026

Symmetry Reveals Layerwise Dynamics: How Transformers Perform In-Context Classification

Transformers can perform in-context classification from a few labeled examples, yet the inference-time algorithm remains opaque. We study multi-class linear classification in the hard no-margin regime and make the computation identifiable by enforcing feature- and label-permutation equivariance at every layer. This enables interpretability while maintaining functional equivalence and yields highly structured weights. From these models we extract an explicit depth-indexed recursion: an end-to-end identified, emergent update rule inside a softmax transformer, to our knowledge the first of its kind. Attention matrices formed from mixed feature-label Gram structure drive coupled updates of training points, labels, and the test probe. The resulting dynamics implement a geometry-driven algorithmic motif, which can provably amplify class separation and yields robust expected class alignment.

Patrick Lutz, Themistoklis Haris, Arjun Chandra +2

Boston University, Departments of Computer Science and Electrical & Computer Engineering.

In-Context Learning Transformer Interpretability Transformer Attention Linear Classification

Mar 19, 2026

Hardness of High-Dimensional Linear Classification

We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms. However, only

O(n^d)

and respectively

\tilde O(1/\varepsilon^d)

upper bounds are known and complemented by polynomial lower bounds that do not support the exponential in dimension dependence. We close this gap up to polylogarithmic terms by reduction from widely-believed hardness conjectures for Affine Degeneracy testing and

k

-Sum problems. Our reductions yield matching lower bounds of

\tildeΩ(n^d)

and respectively

\tildeΩ(1/\varepsilon^d)

based on Affine Degeneracy testing, and

\tildeΩ(n^{d/2})

and respectively

\tildeΩ(1/\varepsilon^{d/2})

conditioned on

k

-Sum. The first bound also holds unconditionally if the computational model is restricted to make sidedness queries, which corresponds to a widely spread setting implemented and optimized in many contemporary algorithms and computing paradigms.

Alexander Munteanu, Simon Omlor, Jeff M. Phillips

TU Dortmund, Germany · University of Utah, UT, USA

Linear Classification Classification

Mar 13, 2026

On Linear Separability of the MNIST Handwritten Digits Dataset

The MNIST dataset containing thousands of handwritten digit images is still a fundamental benchmark for evaluating various pattern-recognition and image-classification models. Linear separability is a key concept in many statistical and machine-learning techniques. Despite the long history of the MNIST dataset and its relative simplicity in size and resolution, the question of whether the dataset is linearly separable has never been fully answered -- scientific and informal sources share conflicting claims. This paper aims to provide a comprehensive empirical investigation to address this question, distinguishing pairwise and one-vs-rest separation of the training, the test and the combined sets, respectively. It reviews the theoretical approaches to assessing linear separability, alongside state-of-the-art methods and tools, then systematically examines all relevant assemblies, and reports the findings.

Ákos Hajnal

Laboratory of Parallel and Distributed Systems Institute for Computer Science and Control (SZTAKI) Hungarian Research Network (HUN-REN) · John von Neumann Faculty of Informatics Óbuda University Budapest, Hungary

Linear Classification

Feb 9, 2026

On the Dynamics of Delayed Generalization in Linear Models

Delayed generalization, where training accuracy becomes nearly perfect substantially before test accuracy, has often been studied in the context of the depth and compositional structure of deep networks. In this paper, we ask whether delayed generalization can occur in simpler settings. We show that it can arise in a linear model trained with gradient descent and an exponential-tail loss on linearly separable data. We characterize the finite-time hyperplane dynamics into three phases: a population phase, a support vector dominated unlearning phase and a generalization phase. The convergence of the residual beyond the maximum-margin direction is sufficient for the unlearning phase to begin. In the support vector dominated phase, we characterize the hyperplane dynamics. The time scale in these dynamics causes delayed generalization. We validate our theory through controlled experiments varying population and support-vector distributions, and further verify the predicted bias behavior in a deep model with a single output neuron on MNIST. Our results provide a unified characterization of the asymptotic and finite-time dynamics underlying delayed generalization in linear models.

Atreya Vedantam, Nataraj Das, Chandrashekar Lakshminarayanan

Indian Institute of Technology Madras, Chennai.

Linear Classification Neural Network Generalization Gradient Descent Dynamics

May 22, 2025

Improved generalization bounds for binary linear classification via isoperimetry

We examine the concentration of uniform generalization errors around their expectation in binary linear classification problems via an isoperimetric argument. In particular, we establish Poincaré and log-Sobolev inequalities for the joint distribution of the output labels and the label-weighted input vectors, which we apply to derive concentration bounds. The derived results improve upon existing bounds obtained from general unbounded empirical processes, as well as that tailored specifically to logistic regression. In asymptotic analysis, we also show that almost sure convergence of uniform generalization errors to their expectation occurs in very broad settings, such as proportionally high-dimensional regimes. Using this convergence, we establish uniform laws of large numbers under dimension-free conditions.

Shogo Nakakita

Binary Classification Generalization Bounds Linear Classification

Jan 17, 2025

Universality of Benign Overfitting in Binary Linear Classification

The practical success of deep learning has led to the discovery of several surprising phenomena. One of these phenomena, that has spurred intense theoretical research, is ``benign overfitting'': deep neural networks seem to generalize well in the over-parametrized regime even though the networks show a perfect fit to noisy training data. It is now known that benign overfitting also occurs in various classical statistical models. For linear maximum margin classifiers, benign overfitting has been established theoretically in a class of mixture models with very strong assumptions on the covariate distribution. However, even in this simple setting, many questions remain open. For instance, most of the existing literature focuses on the noiseless case where all true class labels are observed without errors, whereas the more interesting noisy case remains poorly understood. We provide a comprehensive study of benign overfitting for linear maximum margin classifiers. We discover a phase transition in test error bounds for the noisy model which was previously unknown and provide some geometric intuition behind it. We further considerably relax the required covariate assumptions in both the noisy and noiseless cases. Our results demonstrate that benign overfitting of maximum margin classifiers holds in a much wider range of scenarios than was previously known and provide new insights into the underlying mechanisms.

Ichiro Hashimoto, Stanislav Volgushev, Piotr Zwiernik

Department of Statistical Sciences, University of Toronto

Neural Network Generalization Linear Classification Benign Overfitting Binary Classification Classification Generalization Bounds

Jun 1, 2019

Linear and Quadratic Discriminant Analysis: Tutorial

This tutorial explains Linear Discriminant Analysis (LDA) and Quadratic Discriminant Analysis (QDA) as two fundamental classification methods in statistical and probabilistic learning. We start with the optimization of decision boundary on which the posteriors are equal. Then, LDA and QDA are derived for binary and multiple classes. The estimation of parameters in LDA and QDA are also covered. Then, we explain how LDA and QDA are related to metric learning, kernel principal component analysis, Mahalanobis distance, logistic regression, Bayes optimal classifier, Gaussian naive Bayes, and likelihood ratio test. We also prove that LDA and Fisher discriminant analysis are equivalent. We finally clarify some of the theoretical concepts with simulations we provide.

Benyamin Ghojogh, Mark Crowley

Department of Electrical and Computer Engineering, Machine Learning Laboratory, University of Waterloo, Waterloo, ON, Canada

Classification Linear Classification