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

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, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda f(\cdot)$</tex-math></inline-formula>, for some convex function <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f(\cdot)$</tex-math></inline-formula>, 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 of the training labels is corrupted for each class. Under these assumptions, we prove that the best classification performance is achieved when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f(\cdot)=\|\cdot\|^{2}_{2}$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda\to\infty$</tex-math></inline-formula>. We then proceed to analyze the classification errors for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f(\cdot)=\|\cdot\|_{1}$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f(\cdot)=\|\cdot\|_{\infty}$</tex-math></inline-formula> in the large <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\lambda$</tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$f(\cdot)=\|\cdot\|_{2}^{2}$</tex-math></inline-formula>.