# Enhancing the Fairness and Performance of Edge Cameras with Explainable AI

Truong Thanh Hung Nguyen23, Vo Thanh Khang Nguyen3, Quoc Hung Cao3,
Van Binh Truong3, Quoc Khanh Nguyen3, Hung Cao2  3Quy Nhon AI, FPT Software,
Vietnam 2Analytics Everywhere Lab, University of New Brunswick, Canada
Email: {hungntt, khangnvt1, hungcq3, binhtv8<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The rising use of Artificial Intelligence (AI) in human detection on Edge
camera systems has led to accurate but complex models, challenging to
interpret and debug. Our research presents a diagnostic method using XAI for
model debugging, with expert-driven problem identification and solution
creation. Validated on the Bytetrack model in a real-world office Edge
network, we found the training dataset as the main bias source and suggested
model augmentation as a solution. Our approach helps identify model biases,
essential for achieving fair and trustworthy models.

###### Index Terms:

Explainable AI, Edge Camera

##  I Introduction

Human detection through security cameras, a pivotal AI task, employs AI models
like YOLO and its YOLOX variant for alerts, such as falls and intrusions.
Specifically, Bytetrack, based on YOLOX, excels in multi-object tracking [1,
2]. Yet, it struggles in detecting obscured or disabled individuals (Fig. 1a,
Fig. 1b). Given their black-box nature, these models pose debugging
challenges. Though XAI aids debugging in tabular and text data [3], its use in
image data is less explored. Hence, our paper introduces an XAI-driven
framework to debug human detection models in security cameras. The approach
leverages experts for diagnosing problems and proposing solutions, with
potential wider relevance to object detection and classification.

(a)

(b)

Figure 1: (a) A security camera on the ceiling of an office can detect
ordinary people (green boxes), but not people who cover their bodies with a
cloth. (b) The Bytetrack model cannot detect the disabled woman but still
detect the other, who is not disabled.

##  II Related Work

###  II-A Human Detection

Human detection identifies humans in images or videos and has evolved with
various methods. Deep Learning (DL) brought forward models that address
challenges like object size and illumination differences. Capitalizing on
YOLOX’s [1] success, Bytetrack [2] was designed for human detection,
leveraging YOLOX for detection and Byte for post-processing.

###  II-B Explainable AI

AI’s integration into real-world scenarios has led to multiple Explainable AI
(XAI) strategies: perturbation-based, backpropagation-based, and example-
based. Perturbation techniques, such as D-RISE [4], which work independently
of model design, perturb input images, then analyze predictions to gauge pixel
or superpixel influence on outcomes. While widely applicable, their
computational demand can be limiting. Backpropagation methods delve into model
architecture to fetch explanatory data. Recognized techniques include GradCAM
[5], SeCAM [6]. Example-based methods, like Influence Function [7], explain
using training data samples to ascertain their effects on predictions. While
XAI’s application to object detection is complex due to the intricate models,
some methods, such as D-RISE [4], D-CLOSE [8], and G-CAME [9], are adaptations
from classification for object detection.

###  II-C Debugging Model Framework with XAI

Many studies utilize XAI methods [10], primarily answering, “Why does the
model predict this?” Yet, the follow-up, “How can explanations improve the
model?” requires using XAI to better the AI system. No research has yet
outlined a framework for debugging human detection models. This paper,
therefore, introduces such a framework, leveraging XAI to pinpoint issues and
improve model fairness and efficacy.

##  III Methodology

We present a structured debugging model framework shown in Fig. 2, with seven
sequential stages. Each stage relies on the results of its predecessor. Where
multiple methods or assumptions exist per stage, we offer strategy selection
guidelines. In this framework, XAI aids experts in identifying core model
issues and suggesting performance-enhancing solutions.

Figure 2: The Debugging Framework for Human Detection Models

###  III-A Data Selection and Extraction of Predictions

Our framework starts by selecting a training dataset subset for model
enhancement, addressing potential dataset concerns. Public datasets like
CrowdHuman [11], used in Bytetrack training, can face data poisoning [12],
affecting data quality and model results. Error detection in the model or
dataset is optimized using random testing [13], which randomly picks data for
testing, spotting major flaws without full dataset checks. Based on the idea
that small samples can be indicative, we use statistical sampling heuristics
to set an optimal sample size, which should not surpass 10% of the full
dataset or 1000 samples, ensuring a meaningful and efficient subset [14].
After selecting the data subset, it’s fed into the model to generate
predictions. These are then analyzed against the ground truth, helping gauge
model metrics like accuracy, precision, and areas needing enhancement.

###  III-B Statistical Analysis of Prediction Results

After obtaining predictions, they are categorized by comparing them with the
ground-truth. This classification is guided by experts and, in our human
detection context, results in four categories. Initially, dataset
categorization relies on whether the model’s predicted count aligns with the
ground truth. Images are labeled as “Under-detection” if the model detects
fewer people, and “Over-detection” if it detects more. If the model’s count
matches the ground truth, detection quality is evaluated by comparing model-
detected boxes with ground truth boxes using Intersection over Union (IoU)
values. Images with all box pairs having $\text{IoU}\geq 0.5$ are deemed
“Correct Localization”, while others are “Mislocalization”.

This process organizes the dataset based on prediction results, with three
categories signaling potential model enhancements. The next stage delves
deeper into error sources, laying the groundwork to boost the model’s
precision in detecting people within images.

###  III-C Explanation Generation

In this phase, we use XAI methods to explain each image category. Given that
D-RISE [4] is adaptable to diverse models without needing their architecture
details and offers explanations for ground truth boxes (enabling comparison
with model-detected boxes), we opt for D-RISE in human detection. These
explanations assist experts in identifying the root of incorrect predictions
in the following stage.

###  III-D Problem Identification

Using the XAI results from the prior phase, experts analyze each category
presented in the statistical analysis (Sec. III-B). The XAI indicates the
model’s focal regions on the input image. Experts assess these areas for
relevance and potential biases. By comparing these regions across images in
the same category, common patterns are identified. These patterns are then
cross-referenced with other categories to spot shared features. Additionally,
we compare XAI results across various models to further address potential
challenges.

###  III-E Solution Proposal

The solution proposal phase is important for enhancing model performance. Once
the issue is identified, experts review the dataset and model to identify
potential causes like data distribution, labels, biases, or model design.
Solutions may involve tweaking model parameters, refining training data, or
enhancing the training procedure.

###  III-F Solution Assessment

Rather than implementing all possible solutions, we shall assess the
feasibility of proposed solutions on a small dataset initially. We evaluate
the advantages and disadvantages of each solution, drawing from prior case
studies to assess their relevance to the present problem. The infeasible
solutions can be identified and eliminated, thereby allowing for the selection
of the most suitable solution.

###  III-G Model Enhancement

After implementing the effective solution identified earlier, we refine the
model to address issues highlighted in Sec. III-D. We then assess the model’s
enhancement by contrasting its performance pre and post-refinement,
specifically comparing predictive metrics on initially selected images.
Additionally, we might test using cases the original model struggled with to
validate the model’s enhanced capability in tackling the pinpointed issue.

##  IV Experiment

In our study, we detail each step as illustrated in Fig. 2. We experiment
using the Bytetrack model pre-trained on datasets like MOT17 [15], Cityperson
[16], ETHZ [17], and CrowdHuman [11].

###  IV-A Data Selection and Prediction Extraction

Our training dataset amalgamates four public datasets [15, 16, 17, 11]. We use
CrowdHuman for our tests, divided into training (15000 images), validation
(4370 images), and testing (5000 images) sets. These sets, with a combined
470K human instances, offer varied bounding box annotations. We choose a
random 1000-image subset from CrowdHuman’s training set for extracting model
predictions, as outlined in Sec. III-A.

###  IV-B Analyzing Prediction Results

Here, we match predicted boxes with the ground truth. “Under-detection” is the
predominant issue, constituting 85.5%. While, “Under-detection” accounts for
17%, “Over-detection” accounts for 10.8%, and “Mislocalization” accounts for
20%.

Figure 3: Examples of XAI Explanations with Bytetrack and YOLOX model. In
which, each image in the second column is the XAI Explanations for a
corresponding box.

###  IV-C Explanation Generation

The Bytetrack model is a composite of YOLOX, responsible for detection, and
the Byte phase that processes these detections. YOLOX is vital as the
subsequent Byte step relies on its outputs. Byte’s role is to maintain low-
score predictions possibly hidden by other items [2]. We use D-RISE to
interpret YOLOX, referencing the final box coordinates from Bytetrack [18].
Additionally, comparing Bytetrack and YOLOX using D-RISE on YOLOX’s weights
aids in identifying differences, showcased in Fig. 3 [1].

###  IV-D Problem Identification

The XAI explanations in Fig. 3 indicate Bytetrack’s focus on entire human
bodies, exposing its struggle to detect individuals showing only their heads.
Experiments with images of people in wheelchairs, where bodies are partly
concealed, amplify this limitation, with the model overlooking them as seen in
Fig. 1b. Similar misses happen with people hidden behind objects, highlighted
in Fig. 1a. Hence, Bytetrack’s challenge in spotting partially visible humans
emerges as a key concern needing attention and resolution.

###  IV-E Solution Proposal

Figure 4: Predictions of the Bytetrack model before and after fine-tuning.

We pinpointed specific issues and proposed assumptions accordingly:

  * •

Dataset: On average, images have 23 people, making heads smaller than bodies,
potentially leading to a body bias. We also suspect label issues with ground
truth box coordinates outside the image, shown in Fig. 3 and Table II.

  * •

Model: Bytetrack tries to resolve occluded objects [2]. For head-only images,
Bytetrack expects an associated body.

TABLE I: Ground truth boxes’ coordinate of the input image in the first row of
Fig. 3, where 7/8 boxes are outside the image.

Left | -50 | -12 | 308 | 499 | 618 | 608 | 318 | 303
---|---|---|---|---|---|---|---|---
Top | 35 | 87 | 292 | 171 | 370 | 61 | -14 | -3
Right | 531 | 451 | 635 | 988 | 1034 | 758 | 673 | 444
Bottom | 131 | 1325 | 1228 | 1201 | 1243 | 444 | 745 | 437
Outside image | $\times$ | $\times$ | $\times$ | $\times$ | $\times$ |  | $\times$ | $\times$

Proposed solutions include:

  * •

Data enrichment: Add images with mostly obscured body sections.

  * •

Data blurring: Based on XAI findings, blur bodies to make the model focus on
heads.

  * •

Padding: Ensure bounding boxes are fully within images.

  * •

Relabeling: Adjust bounding boxes to remain inside the image.

###  IV-F Solution Assessment

We conduct a comprehensive analysis to identify and implement the most
suitable solution to the problem. Each solution is evaluated as follows:

  * •

Data enrichment: The current dataset already has partly hidden figures, so
more data might not help much.

  * •

Data blurring: Effective for image classification, but might not suit human
detection where only humans are predicted.

  * •

Padding: While sometimes effective, as in Fig. 5, it often fails, especially
when objects obstruct people.

  * •

Relabeling: Given dataset inconsistencies and variant model features,
relabeling seems promising.

Following this analysis, relabeling emerges as the most impactful solution.

Figure 5: Example of padding result. (Top, Left, Right, Bottom) = (100, 200,
200, 200) signifies padding of 100, 200, 200, and 200 pixels respectively on
the top, left, right, and bottom.

###  IV-G Model and Dataset Enhancement

Bytetrack model | Fine-tuned Bytetrack model
---|---
|
|

Figure 6: Model’s prediction on physically disabled person images. After fine-
tuning, the model performs better than the original pre-trained model. Figure
7: Model’s prediction on a security camera. The fine-tuned model performs
better than the original pre-trained model detecting covered people.

The CrowdHuman dataset is reannotated by constraining bounding box coordinates
within the image dimensions, as delineated by $x^{{}^{\prime}}_{\text{top,
left}}=\texttt{max}(0,x_{\text{top, left}})$, $y^{{}^{\prime}}_{\text{top,
left}}=\texttt{max}(0,y_{\text{top, left}})$, $x^{{}^{\prime}}_{\text{bottom,
right}}=\texttt{min}(w,x_{\text{bottom, right}})$,
$y^{{}^{\prime}}_{\text{bottom, right}}=\texttt{min}(h,y_{\text{bottom,
right}})$. Here, $w,h$ represents the image’s width and height, respectively.
The coordinates $(x^{{}^{\prime}}_{\text{top,
left}},y^{{}^{\prime}}_{\text{top, left}})$ and
$(x^{{}^{\prime}}_{\text{bottom, right}},y^{{}^{\prime}}_{\text{bottom,
right}})$ denote the adjusted top-left and bottom-right points, respectively.
Subsequent model refinement occurs over 10 epochs, with performance
enhancement evaluated in three scenarios:

  * •

Training Dataset Testing: We test a 1000-image subset after refining the
model. Both quantitative and qualitative evaluations are made against the
original model, as seen in Table II and Fig. 4. The updated model better
localizes in 855 “Under-detection” images, improving by 21 cases.

  * •

Images of Disabled Individuals: The adjusted model shows better detection in
images featuring physically disabled people, highlighted in Fig. 6.

  * •

Detection in Surveillance Footage: We assess the model in real-life contexts,
like office security footage where people might be partly hidden. Post-
refinement performance, showcasing improvements, is depicted in Fig. 7.

TABLE II: Statistical result pre-trained model versus fine-tuned model. The
arrow $\uparrow$/$\downarrow$ indicates the higher/lower value, the better.
The bold indicates the better result.

Case | Pre-trained model | Fine-tuned model
---|---|---
Under-detection ($\downarrow$) | 855 | 834
Over-detection ($\downarrow$) | 17 | 13
Correct Localization ($\uparrow$) | 108 | 133
Mislocalization ($\downarrow$) | 20 | 20

##  V Conclusion and Future work

This study introduces a human detection debugging framework using XAI aided by
experts. Our approach pinpoints data labeling as a significant issue in
Bytetrack’s biases and can adapt to other detection problems, especially those
focusing on specific classes.

## References

  * [1] Z. Ge, S. Liu, F. Wang, Z. Li, and J. Sun, “YOLOX: exceeding YOLO series in 2021,” _CoRR_ , vol. abs/2107.08430, 2021. [Online]. Available: https://arxiv.org/abs/2107.08430
  * [2] Y. Zhang, P. Sun, Y. Jiang, D. Yu, Z. Yuan, P. Luo, W. Liu, and X. Wang, “Bytetrack: Multi-object tracking by associating every detection box,” _CoRR_ , vol. abs/2110.06864, 2021. [Online]. Available: https://arxiv.org/abs/2110.06864
  * [3] R. Yousefzadeh and D. P. O’Leary, “Auditing and debugging deep learning models via decision boundaries: Individual-level and group-level analysis,” _CoRR_ , vol. abs/2001.00682, 2020. [Online]. Available: http://arxiv.org/abs/2001.00682
  * [4] V. Petsiuk, R. Jain, V. Manjunatha, V. I. Morariu, A. Mehra, V. Ordonez, and K. Saenko, “Black-box explanation of object detectors via saliency maps,” _CoRR_ , vol. abs/2006.03204, 2020. [Online]. Available: https://arxiv.org/abs/2006.03204
  * [5] R. R. Selvaraju, A. Das, R. Vedantam, M. Cogswell, D. Parikh, and D. Batra, “Grad-cam: Why did you say that? visual explanations from deep networks via gradient-based localization,” _CoRR_ , vol. abs/1610.02391, 2016. [Online]. Available: http://arxiv.org/abs/1610.02391
  * [6] P. Nguyen, H. CAO, K. NGUYEN, H. NGUYEN, and T. YAIRI, “Secam: Tightly accelerate the image explanation via region-based segmentation,” _IEICE Transactions on Information and Systems_ , vol. E105.D, pp. 1401–1417, 08 2022.
  * [7] P. W. Koh and P. Liang, “Understanding black-box predictions via influence functions,” 2017. [Online]. Available: https://arxiv.org/abs/1703.04730
  * [8] V. B. Truong, T. T. H. Nguyen, V. T. K. Nguyen, Q. K. Nguyen, and Q. H. Cao, “Towards better explanations for object detection,” _arXiv preprint arXiv:2306.02744_ , 2023.
  * [9] Q. K. Nguyen, T. T. H. Nguyen, V. T. K. Nguyen, V. B. Truong, and Q. H. Cao, “G-came: Gaussian-class activation mapping explainer for object detectors,” _arXiv preprint arXiv:2306.03400_ , 2023.
  * [10] T. T. H. Nguyen, V. B. Truong, V. T. K. Nguyen, Q. H. Cao, and Q. K. Nguyen, “Towards trust of explainable ai in thyroid nodule diagnosis,” _arXiv preprint arXiv:2303.04731_ , 2023.
  * [11] S. Shao, Z. Zhao, B. Li, T. Xiao, G. Yu, X. Zhang, and J. Sun, “Crowdhuman: A benchmark for detecting human in a crowd,” _CoRR_ , vol. abs/1805.00123, 2018. [Online]. Available: http://arxiv.org/abs/1805.00123
  * [12] R. S. S. Kumar, M. Nyström, J. Lambert, A. Marshall, M. Goertzel, A. Comissoneru, M. Swann, and S. Xia, “Adversarial machine learning - industry perspectives,” _CoRR_ , vol. abs/2002.05646, 2020. [Online]. Available: https://arxiv.org/abs/2002.05646
  * [13] J. Mayer and C. Schneckenburger, “An empirical analysis and comparison of random testing techniques,” in _Proceedings of the 2006 ACM/IEEE international symposium on Empirical software engineering_ , 2006, pp. 105–114.
  * [14] C. R. W. VanVoorhis and B. L. Morgan, “Understanding power and rules of thumb for determining sample sizes,” 2007.
  * [15] A. Milan, L. Leal-Taixé, I. D. Reid, S. Roth, and K. Schindler, “MOT16: A benchmark for multi-object tracking,” _CoRR_ , vol. abs/1603.00831, 2016. [Online]. Available: http://arxiv.org/abs/1603.00831
  * [16] S. Zhang, R. Benenson, and B. Schiele, “Citypersons: A diverse dataset for pedestrian detection,” _CoRR_ , vol. abs/1702.05693, 2017. [Online]. Available: http://arxiv.org/abs/1702.05693
  * [17] A. Ess, B. Leibe, K. Schindler, and L. Van Gool, “A mobile vision system for robust multi-person tracking,” in _2008 IEEE Conference on Computer Vision and Pattern Recognition_ , 2008, pp. 1–8.
  * [18] V. Petsiuk, R. Jain, V. Manjunatha, V. I. Morariu, A. Mehra, V. Ordonez, and K. Saenko, “Black-box explanation of object detectors via saliency maps,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 11 443–11 452.

  *[AI]: Artificial Intelligence
  *[XAI]: Explainable AI


The generalization performance of kernel ridge regression (KRR) exhibits a multi-phased pattern that crucially depends on the scaling relationship between the sample size $n$ and the underlying dimension $d$. This phenomenon is due to the fact that KRR sequentially learns
functions of increasing complexity as the sample size increases;  when $d^{k-1}\ll n\ll d^{k}$, only polynomials with degree less than $k$ are learned. In this paper, we present sharp asymptotic characterization of the performance of KRR at the critical transition regions with $n \asymp d^k$, for $k\in\mathbb{Z}^{+}$. Our asymptotic characterization provides a precise picture of the whole learning process and clarifies the impact of various parameters (including the choice of the kernel function) on the generalization performance. In particular, we show that the learning curves of KRR can have a delicate “double descent” behavior due to specific bias-variance trade-offs at different polynomial scaling regimes.

Kernel ridge regression, kernel method, double-descent, sharp asymptotics.

§ INTRODUCTION

Consider kernel ridge regression (KRR), where we seek to learn a function $\regressfn:\R^{d}\mapsto\R$ from a reproducing kernel Hilbert space (RKHS) associated with a positive semi-definite kernel $\Kernalfn(\cdot,\cdot)$ by solving the following
optimization problem:

\begin{equation}
\hat{\regressfn}=\argmin{\regressfn}\sum_{i=1}^{n}[y_{i}-h(\invec_{i})]^{2}+\lambda\|\regressfn\|_{\Kernalfn}^{2}.\label{eq:kernel_1}
\end{equation}

Here, $\{\invec_{i},y_{i}\}_{i=1}^{n}$ is a collection of training samples, $\|\cdot\|_{\Kernalfn}$ is the RKHS norm and $\lambda>0$ is the regularization parameter.

The performance
of KRR can be characterized by the training error

\[
\mathcal{E}_{\text{train}}=\frac{1}{n}\Big[\sum_{i=1}^{n}\big(y_{i}-\hat{\regressfn}(\invec_{i})\big)^{2}+\lambda\|\hat{\regressfn}\|_{\Kernalfn}^{2}\Big]
\]

and the test error

\[
\mathcal{E}_{\text{test}}=\E_{\text{new}}[\E(y_{\text{new}}\mid\invec_{\text{new}})-\hat{\regressfn}(\invec_{\text{new}})]^{2},
\]

where $(\invec_{\text{new}},y_{\text{new}})\sim\mathcal{P}$ denotes an independent
test sample, and $\E_{\text{new}}$ denotes the expectation with respect to $(\invec_{\text{new}},y_{\text{new}})$ while keeping the training samples $\{\invec_{i},y_{i}\}_{i=1}^{n}$ fixed.

Kernel ridge regression is a classical method for supervised learning [Schölkopf et al., 2002]. Due to its connection
to modern overparameterized neural networks [Neal, 1996, Williams, 1996, Daniely et al., 2016, Jacot et al., 2018, Belkin et al., 2018, Du et al., 2019],
there has been a strong resurgence of interest in studying the performance of KRR, especially in various high-dimensional settings. See, e.g., [Rakhlin and Zhai, 2019, Liang et al., 2020, Liang et al., 2020, Bordelon et al., 2020, Canatar et al., 2021, Ghorbani et al., 2021, Mei et al., 2021].

Illustration of the hierarchical
learning process of kernel ridge regression. Top figure: test error as a function of $\log n / \log d$, where $n$ is the sample size and $d$ is the dimension. The test error appears to remain unchanged when $d^{k-1}\ll n\ll d^{k}$, for $k\in\mathbb{Z}^{+}$, while drastic transitions
occur at $n\asymp d^{k}$. Bottom figures: the zoomed-in views of the test error within each transition region, corresponding to $n \asymp d^k$ for $k = 1, 2, 3$. The red curves show the asymptotic predictions obtained in this work. These learning curves exhibit delicate non-monotonic behavior, due to bias-variance trade-offs at different polynomial scaling regimes.

One intriguing phenomenon revealed by several recent works [Liang et al., 2020, Ghorbani et al., 2021, Mei et al., 2021] is that the generalization performance of KRR exhibits a hierarchical and multi-phased pattern that crucially depends on the scaling relationship between the sample size $n$ and the underlying dimension $d$. We illustrate this phenomenon in Fig. <ref> (top part), where we plot the test error $\mathcal{E}_{\text{test}}$ against the ratio $\log n / \log d$. The test error can be clearly partitioned into several consecutive “stationary” phases that are separated by more drastic transitions in between. More precisely, $\mathcal{E}_{\text{test}}$
appears to remain unchanged when $d^{k-1}\ll n\ll d^{k}$, for $k\in\mathbb{Z}^{+}$, while transitions
occur at $n\asymp d^{k}$. An explanation of this phenomenon was given in [Ghorbani et al., 2021]: It is shown that, when $d^{k-1}\ll n\ll d^{k}$, $\mathcal{E}_{\text{test}}$
is approximately equal to the approximation error of the function $h$ by all the polynomials
with degree less than $k$. This means that KRR sequentially learns
functions of increasing complexity as the sample size increases;  when $d^{k-1}\ll n\ll d^{k}$, only polynomials with degree less than $k$ are learned.

What is the performance of KRR near the critical regions, exactly where the transitions happen? This is the focus of the current paper. More precisely, we “zoom into” each transition region by assuming $n\asymp d^{k}$, and derive sharp asymptotics of KRR for different values of $k$. Such asymptotic characterization provides a precise picture of the whole learning process and clarifies the impact of various parameters (including the choice of the kernel function) on the generalization performance. As a preview of our results, we plot in the lower part of Fig. <ref> the theoretical predictions of $\mathcal{E}_{\text{test}}$
in the regimes $n\asymp d^{k}$, for $k=1,2,3$, for a specific choice
of the kernel function. It can be seen that the learning curves of KRR can exhibit delicate non-monotonic behavior due to bias-variance trade-offs: as the sample size $n$ increases, $\mathcal{E}_{\text{test}}$
can first increase and then decrease again after crossing certain
deterministic thresholds. Under the names of  “double descent” or “multiple descent”, such phenomenon
has been observed and analyzed in various other problems and models in learning [Mei and Montanari, 2019, d'Ascoli et al., 2020, Adlam and Pennington, 2020, Nakkiran et al., 2021].

Some of the asymptotic predictions given in the paper were first derived in [Bordelon et al., 2020, Canatar et al., 2021] (see also [Dietrich et al., 1999] for a related earlier work), via non-rigorous statistical physics methods and a “Gaussian equivalence conjecture” (see Sec <ref>). One of the technical contributions of this paper is to rigorously establish this conjecture, which allows us to characterize the exact performance KRR in the polynomial scaling regime.

When the current work was under review at COLT '22, we became aware of the recent paper [Misiakiewicz, 2022] that also studies the exact asymptotics of KRR in the polynomial scaling regime.
The target function considered in that paper is different from ours.
On one hand,  the expansion coefficients (i.e., $\tcoeff{k,d}$ in (<ref>) below) of low-degree components can be arbitrary, which is more general than ours; on the other hand, they require high-degree coefficients
to be independent random variables. In comparison, we consider a target function (as detailed in Sec. <ref>) whose coefficients are dependent.

In terms of the distribution of $\{\invec_i\}$, our work focuses on the uniform distribution over $d$-dimensional sphere.
In addition to this case, [Misiakiewicz, 2022] also considers the uniform distribution over the hypercube $\{-1,1\}^{d}$.

§ MAIN RESULTS

§.§ Model

We start by describing the statistical model under which we analyze the performance of KRR. Let $\dsphere d$ denotes the $d$-dimensional sphere with radius $\sqrt{d}$. We assume that the input data vectors  $\invec_{i}\iid\spmeasure{d-1}$, where $\spmeasure{d-1}$
denotes the uniform distribution over $\dsphere d$. The labels $\{y_{i}\}$ are generated from a generalized linear teacher model

\begin{equation}
\end{equation}

where $\teacherfn$ is an unknown teacher function, $\sgl\in\dsphere d$
is the teacher weight vector, and $\noisei_{i}\iid\mathcal{N}(0,\varnoise^{2})$
denotes independent additive noise. We consider
an inner-product kernel on $\dsphere d$, represented as

\begin{equation}
\Kernalfn(\invec,\invec')=\kernalfn_{d}(\invec^{\T}\invec'/\sqrt{d}), \label{eq:inner_product_kernel_def}
\end{equation}

where $\kernalfn_{d}$ is a transformation function that can
depend on $d$. It is known that
any inner-product PSD kernel $\Kernalfn\in L^{2}(\dsphere d\times\dsphere d,\spmeasure{d-1}^{\otimes2})$
can be expanded as <cit.>:

\begin{equation}
\Kernalfn(\invec,\invec')=\sum_{k=0}^{\infty}\tkcoeff{k,d}\sum_{i=1}^{\usdim k}Y_{ki}(\vx)Y_{ki}(\vx'),\label{eq:kernel_expansion}
\end{equation}

where $\tkcoeff{k,d}\geq0$ is the eigenvalue of the $k$th eigenspace (we will also denote the normalized eigenvalue as $\kcoeff{k,d}:=\usdim k\tkcoeff{k,d}$),
$\{Y_{ki}(\vx)\}_{i=1}^{\usdim k}$ are the associated eigenfunctions,
which is a set of orthonormal degree-$k$ spherical harmonics. We have

\[
\int Y_{ki}(\vx)Y_{\ell j}(\vx)\spmeasure{d-1}(d\vx)=\indicatorfn_{k\ell} \indicatorfn_{ij},
\]

where $\indicatorfn_{ab} = 1$ if $a = b$ and $\indicatorfn_{ab} = 0$ otherwise. Moreover, $\usdim k$ is the corresponding geometric multiplicity of the $k$th
eigenspace, which coincides with the dimension of the subspace spanned
by all degree-$k$ spherical harmonics. (We collect a list of related concepts and properties of spherical
harmonics in Appendix <ref>.)
Note that both $\usdim k$ and $\{Y_{ki}(\vx)\}_{i=1}^{\usdim k}$
can depend on $d$. However, To lighten the notation, we will omit this dependence when doing so causes no confusion. Finally, we denote by $\spmeasure{d-1,1}$ the distribution of the scalar random variable
$\vx^{\T}\ve_{1}$, where $\vx\sim\spmeasure{d-1}$ and $\ve_1$ is the first standard basis vector.

§.§ Technical Assumptions

Our main results are proved under the following assumptions.

(A.1)  Both the number of training samples $n$ and the input dimension
$d$ go to infinity, while $\frac{n}{d^{\msc}/\msc!}\to\delta_{\msc}\in(0,\infty)$,
for $\msc\in\mathbb{Z}^{+}$.

(A.2)  $\kernalfn_{d}(x)=\kernalfn(x/\sqrt{d})$, where
$\kernalfn(z)$ is well-defined on $[-1,1]$ and satisfies: (1) $\kernalfn(z)\leq C_{f}$, for some $C_{f}>0$ and (2) there exists some $\upsilon\in(0,1]$ such that $\kernalfn(z)\in C^{\infty}[-\upsilon,\upsilon]$.

(A.3) There exists $C>0$ such that $\kcoeff{k,d}\geq C$, for all $0\leq k\leq\msc$ and large enough $d$.

(A.4)  There exist constants $C_{g},K_{g}>0$ such that $g(x)\leq C_{g}(1+|x|^{K_{g}})$
for any $x\in\R$.

Assumption (A.2) put two constraints on the
kernel functions we consider. The first condition
ensures that the expansion (<ref>) is valid and
\sum_{k=0}^{\infty}\kcoeff{k,d}<\infty
holds uniformly over $d$, which directly follows from the properties
(<ref>) and (<ref>) given
in Appendix <ref>.
The boundedness condition
\sum_{k=0}^{\infty}\kcoeff{k,d}<\infty
is convenient as it makes all the quantities of interests
such as the training and test errors of size $\mathcal{O}(1)$, when $\lambda\in(0,\infty)$.
On the other hand, the second condition requires that $\kernalfn(z)$ is smooth in some neighbourhood of $0$. This guarantees that
for any fixed $k$, $\kcoeff{k,d} \to\frac{f^{(k)}(0)}{k!}$, as $d\to\infty$
(see Lemma <ref> in Appendix <ref>), where $f^{(k)}(0)$ denotes the $k$th derivative of $f(z)$ at $z = 0$. Below are two concrete examples of kernels that satisfy
Assumption (A.2).

Example 1: Polynomial kernel. In this case, $\kernalfn(z)=(z+b)^{k}$,
where $b\geq0$ is a fixed constant and $k\in\mathbb{Z}^{+}$. It
is a classical type of kernel, widely applied in several machine learning
problems such as support vector machine (SVM).

Example 2: Random feature model [Rahimi and Recht, 2008].The
random feature model is a computationally efficient random approximation
of kernel function, which is based on the following feature map:

\[
\vx\mapsto\frac{1}{\sqrt{p}}[\sigma(\vr_{1}^{\T}\vx),\sigma(\vr_{2}^{\T}\vx),\cdots,\sigma(\vr_{p}^{\T}\vx)]^{\T},
\]

where $\{\vr_{i}\}_{i=1}^{p}$ is a set of independent random feature
vectors and $\sigma(x)$ is an activation function satisfying $\E\sigma(G)^2<\infty$, with $G\sim\mathcal{N}(0,1)$. The associated random kernel function is as follows:

\[
\Kernalfn_{p}(\vx,\vx')=\frac{1}{p}\sum_{u=1}^{p}\sigma(\vr_{u}^{\T}\vx)\cdot\sigma(\vr_{u}^{\T}\vx').
\]

In particular, when $\vr_{u}\iid\mathcal{N}(\boldsymbol{0},\mI/d)$
and $p\to\infty$, $\Kernalfn_{p}(\vx,\vx')\to\kernalfn(\frac{\invec^{\T}\invec'}{d})$.
Here, $\kernalfn(z)=\E[\sigma(X)\cdot\sigma(Y)]$, with

\[
\begin{pmatrix}X\\
\end{pmatrix}\sim\mathcal{N}(\boldsymbol{0},\mSig),\;\mSig=\begin{bmatrix}1 & z\\
z & 1
\end{bmatrix}.
\]

The smoothness of $f$ near 0 can be directly checked by taking derivatives
of $\kernalfn(z)$.

In fact, we can also let $\kernalfn(z)$ depend on $d$, as long as: (1) $\kernalfn_{d}\in L^{2}([-\sqrt{d},\sqrt{d}],\spmeasure{d-1,1})$, (2) $\sum_{k=0}^{\infty}\kcoeff{k,d}<\infty$ for large enough $d$, and (3) for any fixed $k$, $\kcoeff{k,d}\to\kcoeff k$ as $d\to\infty$.

Assumption (A.3) guarantees
that the RKHS associated with the kernel $\Kernalfn$ is not degenerate:
the condition that $\mu_k > 0$ for $0 \le k \le K$ is satisfied as long as all the degree-$k$ ($k\leq\msc$) polynomials
are in the RKHS. This is equivalent to requiring $\kernalfn^{(k)}(0)>0$, for all $0\leq k \leq \msc$.

Assumption (A.4) implies that for all $d\in\mathbb{Z}^{+}$, $\teacherfn\in L^{2}([-\sqrt{d},\sqrt{d}],\spmeasure{d-1,1})$.
Therefore, we have the following expansion:

\begin{equation}
\teacherfn(x)=\sum_{k=0}^{\infty}\tcoeff{k,d}\usp k(x),\label{eq:teacher_expansion}
\end{equation}

where $\usp k(x)$ is the degree-$k$ ultraspherical polynomial in
$L^{2}([-\sqrt{d},\sqrt{d}],\spmeasure{d-1})$ (more details about these polynomials can be
found in Appendix <ref>) and $\{\tcoeff{k,d}\}_{k\geq0}$
satisfies $\sum_{k=0}^{\infty}\tcoeff{k,d}^{2}<\infty$. Note that $\usp{k}(x)$ depends on $d$, but for notational simplicity, we will suppress the dependence.

In fact,
$g(x)\leq C\exp(C|x|)$, for some $C>0$ will suffice to guarantee
the $L^{2}$-integrability of $\teacherfn$. Here, we put a stronger
assumption to ensure that all the moments of $g(x)$ exists, which
helps simplify several parts of the proof.

§.§ Main Results and Insights

We are now ready to state our main theorem.

Under Assumption (A.1)-(A.4), we have
the following asymptotic characterization of the training and test errors.

\begin{equation}
\mathcal{E}_{\text{train}}\pconv\lambda\left[\frac{\tcoeff{\msc}^{2}R_{\star}}{1+\kcoeff{\msc}\delta_{\msc}R_{\star}}+\Big(\varnoise^{2}+\sum_{k>\msc}\tcoeff k^{2}\Big)R_{\star}\right],\label{eq:main_results_trainerr}
\end{equation}

where $R_{\star}$ is the unique non-negative solution of:

\begin{equation}
\frac{1}{R}=\tilde{\lambda}+\frac{\mu_{\msc}}{1+\delta_{\msc}\mu_{\msc}R},\label{eq:main_results_Stieltjes}
\end{equation}

with $\kcoeff k=\frac{\kernalfn^{(k)}(0)}{k!}$,
$\tcoeff k=\int_{-\infty}^{\infty}\teacherfn(x)\hermitefn_{k}(x)\tau_G(dx)$ and $\tilde{\lambda}=\lambda+\sum_{k>\msc}^{\infty}\kcoeff k$.
Here, $\hermitefn_{k}(x)$ is the degree-$k$ Hermite polynomial, $\tau_G(dx)$ is the standard Gaussian measure
and $R_{\star}=\mathcal{R}(\tilde{\lambda};\mu_{\msc},\delta_{\msc})$,

\begin{equation}
\mathcal{R}(\lambda;\mu,\delta)=\frac{-(\lambda+\mu-\mu\delta)+\sqrt{(\lambda+\mu-\delta\mu)^{2}+4\lambda\mu\delta}}{2\lambda\mu\delta}.\label{eq:main_results_Stieltjes_1}
\end{equation}

\begin{equation}
\mathcal{E}_{\text{test}}\pconv\frac{1}{\equisamp-1}\left[\frac{\equisamp\tcoeff{\msc}^{2}}{(1+\kcoeff{\msc}\delta_{\msc}R_{\star})^{2}}+\equisamp\sum_{k>\msc}\tcoeff k^{2}+\varnoise^{2}\right],\label{eq:main_results_testerr}
\end{equation}

where $\equisamp=\frac{(1+\kcoeff{\msc}\delta_{\msc}R_{\star})^{2}}{\delta_{\msc}\kcoeff{\msc}^{2}R_{\star}^{2}}$.
In both (<ref>) and (<ref>), $\pconv$ denotes convergence in probability as $d\to\infty$.

It turns out that $R_{\star}$
coincides with the Stieltjes transform of the Marchenko-Pastur (MP)
law, with aspect ratio parameter $1/\delta_{\msc}$ and variance $\kcoeff{\msc}$.
The MP law corresponds to the limiting empirical
eigenvalue distributions of the Wishart ensemble.

Bias-Variance Decomposition. The formulas in (<ref>)
and (<ref>) can be viewed from the perspective of bias-variance
decomposition. Conditioning on the input data vectors $\set{\vx_i}$, we consider the following
average squared bias and variance of an estimator $h$ <cit.>:

\begin{align*}
\mathcal{B}_{h} & :=\E_{\invec_{\text{new}}}[\E_{\noise}\regressfn(\invec_{\text{new}})-\E(y_{\text{new}}\mid\invec_{\text{new}})]^{2}\\
\mathcal{V}_{h} & :=\E_{\invec_{\text{new}}}[\var_{\noise}(\regressfn(\invec_{\text{new}}))]^{2}.
\end{align*}

Then $\mathcal{E}_{\text{test}}$
in (<ref>) can be decomposed as $\mathcal{E}_{\text{test}}=\mathcal{B}_{\hat{h}}+\mathcal{V}_{\hat{h}}$
and it holds that

\begin{align}
\mathcal{B}_{\hat{h}}\pconv & \frac{\equisamp}{\equisamp-1}\Big[\frac{\tcoeff{\msc}^{2}}{(1+\kcoeff{\msc}\delta_{\msc}R_{\star})^{2}}+\sum_{k>\msc}\tcoeff k^{2}\Big]\label{eq:bias_hhat}\\
\mathcal{V}_{\hat{h}}\pconv & \frac{\varnoise^{2}}{\equisamp-1}.\label{eq:variance_hhat}
\end{align}

[These can be directly verified via the same proof strategy underlying our proof of (<ref>).]
From (<ref>), we can regard $\equisamp$ as
an inflation factor of the variance. By its definition, $\equisamp$ only depends
on $\{\kcoeff k\}_{k\geq0}$ but not on $\{\tcoeff k\}_{k\geq0}$
or $\varnoise^{2}$. Therefore, $\equisamp$ reflects the influence
of the kernel function on
the learning performance. On the other hand, from (<ref>)
we can further decompose the bias term $\mathcal{B}_{\hat{h}}$ as $\mathcal{B}_{\hat{h}}=\sum_{k=0}^{\infty}\mathcal{B}_{k}$, where

\[
\mathcal{B}_{k}=\begin{cases}
0 & k<\msc,\\
\frac{\equisamp}{\equisamp-1}\frac{\tcoeff \msc^{2}}{(1+\kcoeff \msc\delta_{\msc}R_{\star})^{2}}+\frac{\sum_{\ell>\msc}\tcoeff \ell^{2}}{\equisamp-1} & k=\msc,\\
\tcoeff k^{2} & k>\msc.
\end{cases}
\]

It can be seen that $\mathcal{B}_{k}$ is equal to the average squared
bias when $\tcoeff k$ is the only non-zero coefficient in (<ref>).
In this sense, each $\mathcal{B}_{k}$ can be understood as the contribution
of degree-$k$ components to the total squared bias. Moreover, the
contributions from different components are linear. Similar results
also hold for the training error (<ref>).

Hierarchical learning process. Based on the characterizations
(<ref>), we can now have a better understanding
of the hierarchical learning process illustrated in Fig. <ref>.
Consider the limit: $\delta_{\msc}\to0$ and $\delta_{\msc}\to\infty$.
By (<ref>), we can get for any fixed $\tilde{\lambda}>0$
and $\mu_{\msc}>0$,

\[
(\tilde{\lambda}+\mu_{\msc})^{-1}& \delta_{\msc}\to0\\
\tilde{\lambda}^{-1}& \delta_{\msc}\to\infty
\end{cases}
\]

and $\equisamp\to\infty$ under both limits. Therefore, $\lim_{\delta_{\msc}\to0}\mathcal{B}_{\msc}=\tcoeff \msc^{2}$
and $\lim_{\delta_{\msc}\to\infty}\mathcal{B}_{\msc}=0$. Recall that
$\tcoeff k^{2}$ is the energy of the degree-$k$ component of the
teacher function, so this justifies that KRR learns
the degree-$k$ components in phase-$k$. Moreover we can also identify the roles
played by the components of different degrees. From (<ref>),
we can see that at phase-$k$: (i) all the low-degree ($\ell<k$) components
of the kernel function and the teacher function do not exert any influence;
(ii) high-degree ($\ell>k$) components of the kernel function act as
an additional regularization term, as manifested in $\tilde{\lambda}$; and
(iii) high-degree components of the teacher function act as
additive noise.

KRR essentially estimates all the degree-$k$ components as $0$,
while at the end of phase-$k$, the bias become $0$ which means that
the degree-$k$ components can be perfectly estimated. On the other
hand, we have, $\lim_{\delta_{\msc}\to0}\mathcal{B}_{k}=\lim_{\delta_{\msc}\to\infty}\mathcal{B}_{k}=\tcoeff k^{2}$
for all $k>\msc$. This means that at phase-$\msc$, the learning
of higher degree ($k>\msc$) components has not started yet and KRR
is only involved in learning the degree-$k$ component. Also we can
see that all $\tcoeff{\ell}$, $\ell<k$ do not contribute to $\mathcal{E}_{\text{test}}$,
which means that all the lower-degree components have been perfectly
learned by KRR. In summary, KRR hierarchically learns components
of different degrees, from low to high, as $n$ increases. This phenomenon
has been rigorously studied before in [Liang et al., 2020, Ghorbani et al., 2021].
In particular, [Ghorbani et al., 2021] focus on the regime:
$d^{k}\ll n\ll d^{k+1}$. This corresponds to the interval between
the end of phase-$k$ and the beginning of phase-$k+1$. In comparison,
our results provides the exact in-phase characterization of this learning
process. It depicts the transitioning process from phase-$\msc$ to
phase-$\msc+1$. From the characterization (<ref>),
we can see that at phase-$k$ (i) all the low-degree ($\ell<k$) components
of kernel function and teacher function do not exert any influence,
(ii) high-degree ($\ell>k$) components of kernel function act as
an additional regularization term, as manifested in $\tilde{\lambda}$,
(iii) high-degree components of teacher function plays the role of
additive noise. Only the degree-$k$ component is being learned. In
this way, we can interpret phase-$k$ as the phase of learning degree-$k$
component. An illustration of this hierarchical process is given in
Fig. <ref>. We can find that towards
end of phase-1 and phase-2, $\mathcal{E}_{\text{test}}$ converges
to a non-zero value. It will start decreasing again, only when the
sample size crosses the boundary of each phase. Moreover, we can find
that at each phase, the error can undergo some non-monotonic process:
it doesn't necessarily goes down as we use more training samples.
This happens when $\lambda$ is small.

Finally, it is worth mentioning that this type of characterization
were obtained recently in [Bordelon et al., 2020, Canatar et al., 2021]
for KRR and earlier in [Dietrich et al., 1999] for SVM using
non-rigorous statistical physics methods. Here, we provide a rigorous

Non-monotonicity of $\mathcal{E}_{\text{test}}$. In Fig. <ref>, we show that $\mathcal{E}_{\text{test}}$ can be non-monotonic with respect to the sample complexity. Based on our asymptotic characterization, this phenomenon can be explained as follows. In Fig. 1, we choose $f(z)=\frac{z^3}{30}+\frac{z^2}{2}+z+1$, $g(x)=\frac{x^4}{20}+\frac{x^3}{2}+x^2+x$, $\varnoise=0.5$ and $\lambda=10^{-4}\approx 0$. This corresponds to the ridgeless limit of KRR. Let us take $\lambda\to 0$ in the asymptotic characterization and suppose $\kcoeff k=0$ for all $k>\msc$.
In this case, we can show from (<ref>) and (<ref>) that $\mathcal{B}_{\hat{h}}\pconv\tcoeff{\msc}^{2}\max\{1-\delta_{\msc},0\}$
and $\mathcal{V}_{\hat{h}}\pconv\frac{\varnoise^{2}}{\delta_{\msc}-1}\min\{\delta_{\msc},1\}$. We can find that $\mathcal{B}_{\hat{h}}$ is monotonically decreasing and the non-monotonicity of $\mathcal{E}_{\text{test}}$ stems from the non-monotonicity of $\mathcal{V}_{\hat{h}}$. The peak at the interpolation threshold $\delta_{\msc}=1$ due to the explosion of the variance. In Fig. 1, this corresponds to the peak in the Transition-3.

On the other hand, we can find that the peak at Transition-2 is less notable and there is no peak at Transition-1. The reason is that when $K=1,2$, higher-degree components of kernel function do not vanish and they act as regularization terms (manifested by $\tilde{\lambda}=\lambda+\sum_{k>\msc}^{\infty}\kcoeff k$), which reduces the variance.

§.§ Gaussian Equivalence Conjecture

A key technical insight behind our proof of Theorem <ref> is the rigorous establishment of a so-called Gaussian equivalence conjecture. This conjecture was implicitly used (without proof) in several earlier works [Dietrich et al., 1999, Bordelon et al., 2020, Canatar et al., 2021] that study the generalization performance of kernel methods using non-rigorous statistical physics methods.

For simplicity, let us assume that the kernel and teacher functions are
both band-limited: there exists $L>0$ such that $\kcoeff k=\tcoeff k=0$,
for all $k>L$. First, based on the expansions (<ref>)
and (<ref>), we can obtain an equivalent formulation
of (<ref>) as a linear regression in the feature space
with the following feature map:

\[
\invec_{a}\mapsto\vgamma_{a}=[\underbrace{\widetilde{Y}_{01}(\invec_{a})}_{\usdim 0},\underbrace{\widetilde{Y}_{11}(\invec_{a}),\cdots,\widetilde{Y}_{1\usdim 1}(\invec_{a})}_{\usdim 1},\cdots\cdots\underbrace{\widetilde{Y}_{L1}(\invec_{a}),\cdots\widetilde{Y}_{L\usdim L}(\invec_{a})}_{\usdim L}]^{\T}
\]

where $\widetilde{Y}_{ki}(\cdot):=\sqrt{\tkcoeff{k,d}}Y_{ki}(\cdot)$.
Then (<ref>) is equivalent to:

\begin{equation}
\hat{\vtheta}=\argmin{\vtheta}\sum_{a=1}^{n}[y_{a}-\vtheta^{\T}\vgamma_{a}]^{2}+\lambda\|\vtheta\|^{2}\label{eq:kernel_1_feature}
\end{equation}

where $y_{a}=\vbeta^{\T}\mLa\vgamma_{a}+\noisei_{a}$, with

\begin{align*}
y_{a} & =\sum_{k=0}^{L}\frac{\tcoeff{k,d}}{\sqrt{\usdim k}}\sum_{i=1}^{\usdim k}Y_{ki}(\sgl)^{\T}Y_{ki}(\invec_{a})\\
& =\sum_{k=0}^{L}\frac{\tcoeff{k,d}}{\sqrt{\kcoeff{k,d}}}\sum_{i=1}^{\usdim k}Y_{ki}(\sgl)^{\T}\widetilde{Y}_{ki}(\invec_{a})
\end{align*}

\begin{align*}
\vbeta & =[Y_{01}(\sgl),Y_{11}(\sgl),\cdots,Y_{1\usdim 1}(\sgl),\cdots\cdots,Y_{L1}(\sgl),\cdots Y_{L\usdim L}(\sgl)]^{\T}
\end{align*}

\[
\mLa=\diag\Big\{\tfrac{\tcoeff{0,d}}{\sqrt{\kcoeff{0,d}}},\tfrac{\tcoeff{1,d}}{\sqrt{\kcoeff{1,d}}},\cdots,\tfrac{\tcoeff{1,d}}{\sqrt{\kcoeff{1,d}}},\cdots\cdots,\tfrac{\tcoeff{L,d}}{\sqrt{\kcoeff{L,d}}},\cdots\tfrac{\tcoeff{L,d}}{\sqrt{\kcoeff{L,d}}}\Big\}.
\]

If the entries of $\vgamma_{a}$ are independent Gaussian random variables, then we reach
the setting that has been analyzed in several recent papers [Dicker, 2016, Dobriban and Wager, 2018, Hastie et al., 2019, Wu and Xu, 2020, Richards et al., 2021].
The main challenge here is that different entries of $\vgamma_{a}$
are not independent and that there is no linear transformation that can
decouple this dependence. On the other hand, however, different entries $\vgamma_{a}$ are still uncorrelated: recall that
$\E\widetilde{Y}_{ki}(\invec)\widetilde{Y}_{\ell j}(\invec)=\tkcoeff{k,d} \indicatorfn_{k\ell}\indicatorfn_{ij}$,
since $\{Y_{ki}(\invec)\}_{k,i}$ are orthonormal with respect to
$\spmeasure{d-1}$. Thus, the so-called Gaussian
equivalence conjecture states that the learning performance of the original
KRR problem will remain asymptotically unchanged if we replace each $\vgamma_{a}$
by a Gaussian vector $\vg_{a}$ with the same mean and covariance

The general case $\tcoeff{k,d}\neq0$ can be analyzed in a similar
way by taking care of the (weak) correlation between $\vy$ and $\kmtx$.

Next, we explain why as the sample size grows, KRR learns the polynomials
with increasing degrees sequencially, instead of simultaneously. To
this end, we need to look at eigenvalues $\{\tkcoeff k\}_{k\geq0}$.
The key point is that the eigenvalues of kernel function $\Kernalfn(\cdot,\cdot)$
decays with respect to $k$ as: $\tkcoeff k\asymp\frac{1}{d^{k}}$.
Recall from (<ref>) that $\tkcoeff k$ corresponds
to the energy of each predictor in the linear regression formulation
(<ref>). Since the low-degree components possess
much higher energy than the high-degree components, under the same
sample size, they are estimated with much higher accuracy and are
learned in earlier phases.

Finally, let us explain why the transitions between different learning
phases happen at the scaling of $n\asymp d^{k}$, $k=0,1,2,\cdots$.
In other words, why the polynomial scaling is the transition point,
instead of some fractal scaling such as $n\asymp d^{k+1/2}$. One
way to understand this is by examining the spectrum of $\kmtx$. Again
based on our equivalence conjecture, we will consider $\kmtx_{G}$
as the surrogate for $\kmtx$. First, we partition each $\vg_{a}^{\T}$

\[
\vg_{a}^{\T}=[\vg_{a,1}^{\T},\vg_{a,2}^{\T},\cdots,\vg_{a,L}^{\T}]
\]

where each sub-vector $\vg_{a,k}\sim\mathcal{N}(\boldsymbol{0},\tkcoeff k\mI_{\usdim k})$
and are mutually independent. Denote $\mG_{k}:=[\vg_{1,k},\vg_{2,k},\cdots,\vg_{n,k}]^{\T}\in\R^{n\times\usdim k}$,
which is the sub-matrix of $\mG$ corresponding the $k$th eigenvalue
$\tkcoeff k$ and we can decompose $\kmtx_{G}$ as:

\[
\kmtx_{G}=\sum_{k\geq0}\mG_{k}\mG_{k}^{\T}.
\]

Now for a fixed $k$, let us analyze the eigenvalues of each component
$\mG_{k}\mG_{k}^{\T}$. We discuss over different scaling of $n$.

(i) $n\asymp d^{k}$. By (<ref>) in Appendix <ref>,
we have $\usdim k\asymp d^{k}$. Hence in this case, we have $n\asymp\usdim k$,
which is the scaling studied in <cit.>
and the spectrum of $\mG_{k}\mG_{k}^{\T}$ is described by the MP
distribution. In the current setting, it has the following (generalized)
density function:

\begin{equation}
\mu_{\text{MP}}(x)=\max\Big\{1-\frac{\usdim k}{n},0\Big\}\cdot\delta(x)+\frac{\usdim k}{2\pi\kcoeff kn}\frac{\sqrt{(\lambda_{+}-x)(x-\lambda_{-})}}{x},\quad x\in[\lambda_{-},\lambda_{+}]\label{eq:Marcheko_dist}
\end{equation}

where $\delta(x)$ is the delta distribution at $x=0$, $\lambda_{+}=\kcoeff k(1+\sqrt{n/\usdim k})^{2}$
and $\lambda_{-}=\kcoeff k(1-\sqrt{n/\usdim k})^{2}$. From the distribution
(<ref>) we can see under current scaling, the non-zero
eigenvalues of $\mG_{k}\mG_{k}^{\T}$ is supported over the interval

(ii) $n\ll d^{k}$. In this case, $n\ll\usdim k$. This corresponds to
the $n/\usdim k\to0$ limit in (<ref>), which indicates
that spectrum of $\mG_{k}\mG_{k}^{\T}$ converges to a single point
mass at $\kcoeff k$. In other words, $\mG_{k}\mG_{k}^{\T}\approx\kcoeff k\mI$.

(iii) $n\gg d^{k}$. We have $n\gg\usdim k$, indicating that $\mG_{k}\mG_{k}^{\T}$
is a highly low-rank matrix. Moreover, since different columns of
$\mG_{k}$ are i.i.d. Gaussian vector with mean zero and covariance
$\tkcoeff k\mI_{n}$, it is not hard to show that the squared $\ell_{2}$-norm
of each column of $\mG_{k}$ converge to $\frac{n}{\usdim k}\kcoeff k\gg1$
and they are almost orthogonal to each other. Therefore, the non-zero
eigenvalues of $\mG_{k}\mG_{k}^{\T}$ must be much larger than 1.

From the above discussions, we can find the general picture about
how the spectrum of $\mG_{k}\mG_{k}^{\T}$ evolves as $n$ increases.
When $n\ll d^{k}$, the spectrum are concentrated at a single point
$\kcoeff k\asymp1$ and it only start to enlarge and form a bulk when
$n\asymp d^{k}$. If $n$ further increases such that $n\gg d^{k}$,
the non-zero eigenvalues will be much larger than 1 and conceivably
all the eigenvalues will be outside the bulk spectrum of $\kmtx_{G}$.
From this perspective, we obtain one interpretation on the phase transitions
occurring at $n\asymp d^{k}$: under this scaling, the eigenvalues
of the $k$h component $\mG_{k}\mG_{k}^{\T}$ start to pop out of
the $\mathcal{O}(1)$ bulk spectrum of $\kmtx_{G}$.

§.§ Limitations of the Current Work

Finally, we point out several important limitations of our results. First, we have assumed that the input vectors $\invec$
are uniformly distributed over $\dsphere d$. Although this is a convenient model for theoretical analysis, the spherical symmetry of the model might impose too strong an assumption on the input data. It will be desirable to explore other more general data distributions such as those considered in [Liang et al., 2020, Liang et al., 2020, Mei et al., 2021].
Second, we have assumed that the labels $\set{y_i}$ in the training set are generated by a specific teacher-student model, which is essentially a generalized linear model. On the contrary, in [Liang et al., 2020, Liang et al., 2020, Mei et al., 2021],
there is no such constraint and a generic non-parametric model for the labels $\set{y_i}$ is
Since current proof crucially hinges on the fact that the distribution of $\invec_i$ is isotropic and that $h(\invec)$ only depends on the projection $\invec^{\T}\sgl$, handling more general function classes may require substantial changes to our current proof technique.
Finally, we only analyze the inner-product kernels here.
It will be interesting to consider other types of kernels, e.g., radial kernel $\Kernalfn(\invec,\invec')=k(\|\invec-\invec'\|/\sqrt{d})$ and translation invariant kernel $\Kernalfn(\invec,\invec')=k(\invec-\invec')$. In the current setting, since $\invec_{i}\iid\spmeasure{d-1}$, it is easy to see that radial kernels can be viewed as inner-product kernels. For more general settings, we conjecture that some versions of
Gaussian equivalence may still hold.

The extensions to the above more general cases are left as
interesting future work.

[Adlam and Pennington, 2020]
Ben Adlam and Jeffrey Pennington.
The neural tangent kernel in high dimensions: Triple descent and a
multi-scale theory of generalization.
In International Conference on Machine Learning, pages 74–84.
PMLR, 2020.

[Belkin et al., 2018]
Mikhail Belkin, Siyuan Ma, and Soumik Mandal.
To understand deep learning we need to understand kernel learning.
arXiv preprint arXiv:1802.01396, 2018.

[Billingsley, 2008]
Patrick Billingsley.
Probability and measure.
John Wiley & Sons, 2008.

[Bordelon et al., 2020]
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan.
Spectrum dependent learning curves in kernel regression and wide
neural networks.
In International Conference on Machine Learning, pages
1024–1034. PMLR, 2020.

[Canatar et al., 2021]
Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan.
Spectral bias and task-model alignment explain generalization in
kernel regression and infinitely wide neural networks.
Nature communications, 120 (1):0 1–12, 2021.

[Cheng and Singer, 2013]
Xiuyuan Cheng and Amit Singer.
The spectrum of random inner-product kernel matrices.
Random Matrices: Theory and Applications, 20
(04):0 1350010, 2013.

[Dai and Xu, 2013]
Feng Dai and Yuan Xu.
Approximation theory and harmonic analysis on spheres and
balls, volume 23.
Springer, 2013.

[Daniely et al., 2016]
Amit Daniely, Roy Frostig, and Yoram Singer.
Toward deeper understanding of neural networks: The power of
initialization and a dual view on expressivity.
In Advances In Neural Information Processing Systems, pages
2253–2261, 2016.

[d'Ascoli et al., 2020]
Stéphane d'Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala.
Double trouble in double descent: Bias and variance (s) in the lazy
In International Conference on Machine Learning, pages
2280–2290. PMLR, 2020.

[Dicker, 2016]
Lee H Dicker.
Ridge regression and asymptotic minimax estimation over spheres of
growing dimension.
Bernoulli, 220 (1):0 1–37, 2016.

[Dietrich et al., 1999]
Rainer Dietrich, Manfred Opper, and Haim Sompolinsky.
Statistical mechanics of support vector networks.
Physical review letters, 820 (14):0 2975,

[Dobriban and Wager, 2018]
Edgar Dobriban and Stefan Wager.
High-dimensional asymptotics of prediction: Ridge regression and
The Annals of Statistics, 460 (1):0 247–279,

[Du et al., 2019]
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.
Gradient descent finds global minima of deep neural networks.
In International conference on machine learning, pages
1675–1685. PMLR, 2019.

[Ghorbani et al., 2021]
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.
Linearized two-layers neural networks in high dimension.
The Annals of Statistics, 490 (2):0
1029–1054, 2021.

[Hastie et al., 2009]
Trevor Hastie, Robert Tibshirani, and Jerome H Friedman.
The elements of statistical learning: data mining, inference,
and prediction, volume 2.
Springer, 2009.

[Hastie et al., 2019]
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani.
Surprises in high-dimensional ridgeless least squares interpolation.
arXiv preprint arXiv:1903.08560, 2019.

[Jacot et al., 2018]
Arthur Jacot, Franck Gabriel, and Clément Hongler.
Neural tangent kernel: Convergence and generalization in neural
In Advances in neural information processing systems, pages
8571–8580, 2018.

[Liang et al., 2020]
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai.
On the multiple descent of minimum-norm interpolants and restricted
lower isometry of kernels.
In Conference on Learning Theory, pages 2683–2711. PMLR,

[Liang et al., 2020]
Tengyuan Liang, Alexander Rakhlin, et al.
Just interpolate: Kernel “ridgeless” regression can generalize.
Annals of Statistics, 480 (3):0 1329–1347,

[Lu and Yau, 2022]
Yue M. Lu and Horng-Tzer Yau.
An equivalence principle for the spectrum of random inner-product
kernel matrices.
arXiv preprint, 2022.

[Mei and Montanari, 2019]
Song Mei and Andrea Montanari.
The generalization error of random features regression: Precise
asymptotics and double descent curve.
arXiv preprint arXiv:1908.05355, 2019.

[Mei et al., 2021]
Song Mei, Theodor Misiakiewicz, and Andrea Montanari.
Generalization error of random feature and kernel methods:
hypercontractivity and kernel matrix concentration.
Applied and Computational Harmonic Analysis, 2021.

[Misiakiewicz, 2022]
Theodor Misiakiewicz.
Spectrum of inner-product kernel matrices in the polynomial regime
and multiple descent phenomenon in kernel ridge regression.
arXiv preprint arXiv:2204.10425, 2022.

[Nakkiran et al., 2021]
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya
Deep double descent: Where bigger models and more data hurt.
Journal of Statistical Mechanics: Theory and Experiment,
20210 (12):0 124003, 2021.

[Neal, 1996]
Radford M Neal.
Priors for infinite networks.
In Bayesian Learning for Neural Networks, pages 29–53.
Springer, 1996.

[Rahimi and Recht, 2008]
Ali Rahimi and Benjamin Recht.
Random features for large-scale kernel machines.
In Advances in neural information processing systems, pages
1177–1184, 2008.

[Rakhlin and Zhai, 2019]
Alexander Rakhlin and Xiyu Zhai.
Consistency of interpolation with laplace kernels is a
high-dimensional phenomenon.
In Conference on Learning Theory, pages 2595–2623. PMLR,

[Richards et al., 2021]
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco.
Asymptotics of ridge (less) regression under general source
In International Conference on Artificial Intelligence and
Statistics, pages 3889–3897. PMLR, 2021.

[Schölkopf et al., 2002]
Bernhard Schölkopf, Alexander J Smola, Francis Bach, et al.
Learning with kernels: support vector machines, regularization,
optimization, and beyond.
MIT press, 2002.

[Vershynin, 2018]
Roman Vershynin.
High-dimensional Probability: An Introduction with
Applications in Data Science.
Cambridge University Press, 2018.

[Williams, 1996]
Christopher Williams.
Computing with infinite networks.
Advances in neural information processing systems, 9, 1996.

[Wu and Xu, 2020]
Denny Wu and Ji Xu.
On the optimal weighted l2 regularization in overparameterized linear
Advances in Neural Information Processing Systems,
33:0 10112–10123, 2020.