Double descent in the condition number

Abstract

In solving a system of $n$ linear equations in $d$ variables $Ax=b$, the condition number of the $n,d$ matrix $A$ measures how much errors in the data $b$ affect the solution $x$. Estimates of this type are important in many inverse problems. An example is machine learning where the key task is to estimate an underlying function from a set of measurements at random points in a high dimensional space and where low sensitivity to error in the data is a requirement for good predictive performance. Here we discuss the simple observation, which is known but surprisingly little quoted (see Theorem 4.2 in \cite{Brgisser:2013:CGN:2526261}): when the columns of $A$ are random vectors, the condition number of $A$ is highest if $d=n$, that is when the inverse of $A$ exists. An overdetermined system ($n>d$) as well as an underdetermined system ($n<d$), for which the pseudoinverse must be used instead of the inverse, typically have significantly better, that is lower, condition numbers. Thus the condition number of $A$ plotted as function of $d$ shows a double descent behavior with a peak at $d=n$.

Removed parts relating to kernel regression to streamline the presentation, fixed some typos

References in corpus (2)

• The generalization error of random features regression: Precise asymptotics and double descent curve
• Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Models

Cited by in corpus (6)

• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
• Conditioning of Random Feature Matrices: Double Descent and Generalization Error
• On the Double Descent of Random Features Models Trained with SGD
• For interpolating kernel machines, minimizing the norm of the ERM solution minimizes stability
• On the Role of Optimization in Double Descent: A Least Squares Study
• Distilling Double Descent