\paragraph{Discrete Fourier Models} In this experiment, we use Fourier series models $\mF \in \sC^{n\times D}, D=1024, n=64$ with $r$-decaying multivariate Gaussian  coefficients ($r=0.3, 0.5, 1.0$). 
$\Fst \in \sC^{n \times p}, {\color{black}\forall p \in [D]}$ is the observation matrix. The weighted min-norm estimator uses $\Sigma^q$, $q \geq 0$ to define the weighted $\ell_2$-norm. The theoretical curves are the risks calculated according to Theorems \ref{thm:diff-equi} and \ref{thm:under} on {\color{black} $p<n$ in the underparameterized regime and $p=l n, l=1,2,\dots, \tau$ in the overparameterized regime}. The empirical mean curves and the $80\%$ confidence intervals (CI) are estimated {\color{black}on all $p \in [D]$} by $100$ runs of independently sampled feature vectors $\vtheta$. 

\begin{figure}[ht]
    \centering
    \includegraphics[width=.98\linewidth]{figs/all_p/main_legend.png}
    \includegraphics[width=.32\linewidth]{figs/all_p/D1024_n64_r0.3_q0.3_100runs.png}
    \includegraphics[width=.32\linewidth]{figs/all_p/D1024_n64_r0.5_q0.5_100runs.png}
    \includegraphics[width=.3\linewidth]{figs/all_p/D1024_n64_r1.0_q1.0_100runs.png}
    \vspace{-.4cm}
    \caption{Theoretical and empirical risks ($\|\vtheta - \hat{\vtheta}\|_2^2$) of plain and weighted min-norm estimators in log-log scale. Left to right: $r=q=0.3, 0.5, 1.0$.} 
    \vspace{-.4cm}
    \label{fig:fourier}
\end{figure}
Figure \ref{fig:fourier} shows that the empirical mean risks match the theoretical risks $\ex [\|\vtheta - \hat{\vtheta}\|^2]$ of Theorems \ref{thm:diff-equi} and \ref{thm:under} very accurately. Figure \ref{fig:fourier} validates that weighted optimization results in better generalization in the overparameterized regime (Theorem \ref{thm:lower bound}), and shows non-degenerated double descent curves when $r=q=0.5$.

\paragraph{Function Interpolation} {\color{black}In this experiment, we interpolate the functions at $n$ equispaced points. The observed $n$ samples are $(\vx_j, y_j)_{j=1}^n$, where $y_j = f(\vx_j)$ with Fourier series $f(\vx) = \sum_{\vk} \theta_{\vk} \exp{(\pi i \vk^T\vx)}$. We fit training samples to a hypothesis class of $p$-truncated Fourier series: $ f_{\hat{\vtheta}}(\vx) = \sum_{\vk}  \hat{\theta}_{\vk} \exp{(\pi i \vk^T\vx)}$ with $k_j = -m, \dots, 0, \dots, m, \forall j \in [d]$ and then $p = (2m + 1)^d$ via least squares in underparameterized case; via plain and weighted min-norm estimators in the overparameterized case. $\mF_T^{\otimes d} \vtheta = {\bf y}$, where $\mF_T \in \mathbb{C}^{n_i \times p_i} \text{ with } F_{j,k} = e^{2 \pi i j k /n}$, $n = n_i^d$, and $p=p_i^d$. In the $1$-dimensional case, we use $D=1000$, $n=15$, $q = 1.5$ for $f_1(x)$ and $q=2$ for $f_2(x)$; in the $2$-dimensional case, $D=100^2$, $n=10^2$, $p_{under}=3^2$ and $p_{over}=41^2$.}
\begin{figure}[ht]
    \centering
    \includegraphics[width=\linewidth]{figs/interp_noisy_D1000_n15_q1.5_False.png}
    \includegraphics[width=\linewidth]{figs/interp_noisy_D1000_n15_q2_True.png}
    \vspace{-.6cm}
    \caption{Interpolation (in orange) of stage function and smooth function. Up: $f_1(x)=1, \forall x \in [-1,0); f_1(x) = 1, \forall x \in [0,1]$. Down: $f_2(x)= 2.5(x^3-x)$ with noise. From left to right: least square with $p=1$; least square with $p<n$; $p=n$; interpolation by weighted min-norm estimator ($p>n$); interpolation by plain min-norm estimator ($p>n$).} 
    \vspace{-.4cm}
    \label{fig:interp}
\end{figure}

Figure \ref{fig:interp} presents the function interpolations (in orange) using different estimators with the same set of equispaced samples (dark green). We observe that overparameterization with the plain min-norm estimator is useless, while the weighted min-norm estimator has the best performance in both noiseless and noisy cases. We also see the benefit of the weighted optimization's regularization towards smoother interpolants.

\begin{figure}[ht]
    \centering
    \includegraphics[width=.32\linewidth]{figs/highd/original_withz.png}
    \includegraphics[width=.32\linewidth]{figs/highd/under_withz.png}
    \includegraphics[width=.32\linewidth]{figs/highd/plain_min_withz.png}
    \includegraphics[width=.32\linewidth]{figs/highd/weighted_min_q1_withz.png}
    \includegraphics[width=.32\linewidth]{figs/highd/weighted_min_q2_withz.png}
    \includegraphics[width=.32\linewidth]{figs/highd/weighted_min_q4_withz.png}
    \vspace{-.4cm}
    \caption{Interpolation of $2D$ function $f(\vx) = \cos(6.28\cdot(2x+3y))$. Up: from left to right are original function with sampled points, least square with $p < n$, and interpolation with plain min-norm estimator ($p > n$); Bottom: from left to right are interpolations by weighted min-norm estimators ($p>n$) with $q=1, 2, 4$.} 
    \vspace{-.4cm}
    \label{fig:interp2d}
\end{figure}
{\color{black}
Figure \ref{fig:interp2d} shows a $2$-dimensional function interpolation. Similar to the $1$-dimensional case, the function approximated with $p<n$ is smooth but does not fit all the samples. The weighted min-norm estimator results in a smooth surface and almost recovers the original function with $q \geq 2$ while the plain min-norm estimator results in multiple sharp spikes.}
{"config": "arxiv", "file": "2006.08495/sections/exp_section.tex"}