# One-Bit Quantization and Sparsification for Multiclass Linear Classification with Strong Regularization

arXiv: https://arxiv.org/abs/2402.10474 · HTML: https://mlsanity.com/paper/2402.10474/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 40 references that are in the map.
- First posted on arXiv 16 Feb 2024.

## Builds on (most cited first, 28 of 28)

- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [BitNet: Scaling 1-bit Transformers for Large Language Models](https://mlsanity.com/paper/2310.11453/) (2023)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [PB-LLM: Partially Binarized Large Language Models](https://mlsanity.com/paper/2310.00034/) (2023)
- [A modern maximum-likelihood theory for high-dimensional logistic regression](https://mlsanity.com/paper/1803.06964/) (2018)
- [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019)
- [The role of regularization in classification of high-dimensional noisy Gaussian mixture](https://mlsanity.com/paper/2002.11544/) (2020)
- [Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions](https://mlsanity.com/paper/2106.03791/) (2021)
- [The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression](https://mlsanity.com/paper/1804.09753/) (2018)
- [Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation](https://mlsanity.com/paper/2106.10865/) (2021)
- [QMoE: Practical Sub-1-Bit Compression of Trillion-Parameter Models](https://mlsanity.com/paper/2310.16795/) (2023)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization](https://mlsanity.com/paper/1906.03830/) (2019)
- [The Impact of Regularization on High-dimensional Logistic Regression](https://mlsanity.com/paper/1906.03761/) (2019)
- [Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View](https://mlsanity.com/paper/2011.07729/) (2020)
- [Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization](https://mlsanity.com/paper/1806.00952/) (2018)
- [Universality laws for Gaussian mixtures in generalized linear models](https://mlsanity.com/paper/2302.08933/) (2023)
- [Sharp Asymptotics and Optimal Performance for Inference in Binary Models](https://mlsanity.com/paper/2002.07284/) (2020)
- [Generalization for multiclass classification with overparameterized linear models](https://mlsanity.com/paper/2206.01399/) (2022)
- [Regularized Linear Regression for Binary Classification](https://mlsanity.com/paper/2311.02270/) (2023)
- [Symbol Error Rate Performance of Box-relaxation Decoders in Massive MIMO](https://mlsanity.com/paper/1711.11215/) (2017)

## Built on by (most cited first, 1 of 1)

- [Physics-Inspired Binary Neural Networks: Interpretable Compression with Theoretical Guarantees](https://mlsanity.com/paper/2502.01908/) (2025)

## Abstract (arXiv)

We study the use of linear regression for multiclass classification in the over-parametrized regime where some of the training data is mislabeled. In such scenarios it is necessary to add an explicit regularization term, λ f(w), for some convex function f(·), to avoid overfitting the mislabeled data. In our analysis, we assume that the data is sampled from a Gaussian Mixture Model with equal class sizes, and that a proportion c of the training labels is corrupted for each class. Under these assumptions, we prove that the best classification performance is achieved when f(·) = |·|22 and λ → ∞. We then proceed to analyze the classification errors for f(·) = |·|1 and f(·) = |·|_∞ in the large λ regime and notice that it is often possible to find sparse and one-bit solutions, respectively, that perform almost as well as the one corresponding to f(·) = |·|22.