$\displaystyle={\left(\hat{{\bm{\alpha}}}-\tilde{{\bm{\alpha}}}\right)}^{\top}{\left({\bm{G}}_{{K_{s}},n}-{\bm{G}}_{{\hat{K}_{s}},n}\right)}\hat{{\bm{\alpha}}}-n\beta_{n}{\left(\hat{{\bm{\alpha}}}-\tilde{{\bm{\alpha}}}\right)}^{\top}{\left(\hat{{\bm{\alpha}}}-\tilde{{\bm{\alpha}}}\right)}$
$\displaystyle\leq{\left\|\hat{{\bm{\alpha}}}\right\|}_{2}{\left\|{\bm{G}}_{{K_{s}},n}-{\bm{G}}_{{\hat{K}_{s}},n}\right\|}_{2}{\left\|\hat{{\bm{\alpha}}}\right\|}_{2}+{\left\|\tilde{{\bm{\alpha}}}\right\|}_{2}{\left\|{\bm{G}}_{{K_{s}},n}-{\bm{G}}_{{\hat{K}_{s}},n}\right\|}_{2}{\left\|\hat{{\bm{\alpha}}}\right\|}_{2}-0$
$\displaystyle\leq
2\left.\nabla_{\lambda}{\left(\frac{s(\lambda)}{\lambda}\right)}\right|_{\lambda=\lambda_{\max}}\frac{\beta_{n}^{-2}\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}\frac{\|{\bm{y}}\|_{2}^{2}}{n}.$

And note that we have
${\left\|\tilde{f}-f^{\dagger}\right\|}_{P_{\mathcal{X}}}^{2}\leq
s(\lambda_{1}){\left\|\tilde{f}-f^{\dagger}\right\|}_{{\mathcal{H}}_{{K_{s}}}}^{2}\leq
s(\lambda_{\max}){\left\|\tilde{f}-f^{\dagger}\right\|}_{{\mathcal{H}}_{{K_{s}}}}^{2}$.
Thus,

$\displaystyle{\left\|\hat{f}-\tilde{f}\right\|}_{P_{\mathcal{X}}}^{2}$
$\displaystyle\leq
2{\left({\left\|\hat{f}-f^{\dagger}\right\|}_{P_{\mathcal{X}}}^{2}+{\left\|\tilde{f}-f^{\dagger}\right\|}_{P_{\mathcal{X}}}^{2}\right)}$
$\displaystyle\leq
8s(\lambda_{\max})\left.\nabla_{\lambda}{\left(\frac{s(\lambda)}{\lambda}\right)}\right|_{\lambda=\lambda_{\max}}\frac{\beta_{n}^{-2}\kappa^{4}}{\sqrt{n+m}}{\left(2+\sqrt{2\log\frac{1}{\delta}}\right)}\frac{\|{\bm{y}}\|_{2}^{2}}{n},$

as desired. ∎

###  B.7 Proof of Proposition 3

By Assumption 3, there is
$\|f^{*}\|_{{\mathcal{H}}_{K_{s^{*}}}}^{2}\leq\epsilon\|f^{*}\|_{P_{\mathcal{X}}}^{2}$.
Let $f^{*}=\sum_{i}u_{i}\psi_{i}$, then this is equivalent to

$\sum_{i}\frac{u_{i}^{2}}{s^{*}(\lambda_{i})}\leq\epsilon\sum_{i}u_{i}^{2}.$

Let $s(\lambda)=\frac{\lambda}{1-\eta\lambda}$ be the inverse Laplacian, then
we have

$\sum_{i}\frac{u_{i}^{2}}{s(\lambda_{i})}\leq\sum_{i}\frac{u_{i}^{2}}{\lambda_{i}}\leq\sum_{i}\frac{u_{i}^{2}}{s^{*}(\lambda_{i})/M}\leq
M\epsilon\sum_{i}u_{i}^{2},$

which means that $f^{*}$ also satisfies Assumption 3 w.r.t. $s$ by replacing
$\epsilon$ with $M\epsilon$. All other conditions are the same, so we can
continue to apply Theorems 2 and 3. ∎

###  B.8 Proof of Proposition 4

This proof is similar to the proof of Proposition 4 in Zhai et al. (2024).

Since $\hat{\Psi}$ is at most rank-$d$, there must be a function in
${\textnormal{span}}{\left\\{\psi_{1},\cdots,\psi_{d+1}\right\\}}$ that is
orthogonal to $\hat{\Psi}$. Thus, we can find two functions
$f_{1},f_{2}\in{\textnormal{span}}{\left\\{\psi_{1},\cdots,\psi_{d+1}\right\\}}$
such that: $\|f_{1}\|_{P_{\mathcal{X}}}=\|f_{2}\|_{P_{\mathcal{X}}}=1$,
$f_{1}$ is orthogonal to $\hat{\Psi}$, $f_{2}={\bm{u}}^{\top}\hat{\Psi}$
(which means that $f_{1}\perp f_{2}$), and
$\psi_{1}\in{\textnormal{span}}{\left\\{f_{1},f_{2}\right\\}}$. Let
$\psi_{1}=\alpha_{1}f_{1}+\alpha_{2}f_{2}$, and without loss of generality
suppose that $\alpha_{1},\alpha_{2}\in[0,1]$. Then,
$\alpha_{1}^{2}+\alpha_{2}^{2}=1$. Let
$f_{0}=\alpha_{2}f_{1}-\alpha_{1}f_{2}$, then $\|f_{0}\|_{P_{\mathcal{X}}}=1$
and ${\left\langle f_{0},\psi_{1}\right\rangle}_{P_{\mathcal{X}}}=0$. This
also implies that ${\left\langle
f_{0},\psi_{1}\right\rangle}_{{\mathcal{H}}_{{K_{s}}}}=0$.

Let $\beta_{1},\beta_{2}\in[0,1]$ be any value such that
$\beta_{1}^{2}+\beta_{2}^{2}=1$. Let $f=B(\beta_{1}\psi_{1}+\beta_{2}f_{0})$,
then $\|f\|_{P_{\mathcal{X}}}=B$. And we have
$\|f\|_{{\mathcal{H}}_{{K_{s}}}}^{2}=B^{2}{\left(\|\beta_{1}\psi_{1}\|_{{\mathcal{H}}_{{K_{s}}}}^{2}+\|\beta_{2}f_{0}\|_{{\mathcal{H}}_{{K_{s}}}}^{2}\right)}\leq
B^{2}{\left(\frac{\beta_{1}^{2}}{s(\lambda_{1})}+\frac{\beta_{2}^{2}}{s(\lambda_{d+1})}\right)}\leq\epsilon
B^{2}$, as long as
$\beta_{2}^{2}\leq\frac{s(\lambda_{d+1})}{s(\lambda_{1})-s(\lambda_{d+1})}{\left[s(\lambda_{1})\epsilon-1\right]}$.
This means that $f\in{\mathcal{F}}_{s}$.

Let
$F(\alpha_{1}):=\alpha_{1}\beta_{1}+\alpha_{2}\beta_{2}=\alpha_{1}\beta_{1}+\sqrt{1-\alpha_{1}^{2}}\beta_{2}$
for $\alpha_{1}\in[0,1]$. It is easy to show that $F(\alpha_{1})$ first
increases and then decreases on $[0,1]$, so
$F(\alpha_{1})^{2}\geq\min{\left\\{F(0)^{2},F(1)^{2}\right\\}}=\min{\left\\{\beta_{1}^{2},\beta_{2}^{2}\right\\}}$,
which can be
$\frac{s(\lambda_{d+1})}{s(\lambda_{1})-s(\lambda_{d+1})}{\left[s(\lambda_{1})\epsilon-1\right]}$
given that it is at most $\frac{1}{2}$. Thus, for this $f$, we have

$\min_{{\bm{w}}\in\mathbb{R}^{d}}\;{\left\|{\bm{w}}^{\top}\hat{\Psi}-f\right\|}_{P_{\mathcal{X}}}^{2}={\left\|B{\left(\alpha_{1}\beta_{1}+\alpha_{2}\beta_{2}\right)}f_{1}\right\|}_{P_{\mathcal{X}}}^{2}=B^{2}F(\alpha_{1})^{2}\geq\frac{s(\lambda_{d+1})}{s(\lambda_{1})-s(\lambda_{d+1})}{\left[s(\lambda_{1})\epsilon-1\right]}B^{2}.$

If the equality is attained, then we must have
$\|f_{0}\|_{{\mathcal{H}}_{{K_{s}}}}^{2}=s(\lambda_{d+1})^{-1}$. So if
$s(\lambda_{d})>s(\lambda_{d+1})$, then $\hat{\Psi}$ must span the linear span
of $\psi_{1},\cdots,\psi_{d}$.

Finally, we prove that
$\max_{f\in{\mathcal{F}}_{s}}\min_{{\bm{w}}\in\mathbb{R}^{d}}{\left\|{\bm{w}}^{\top}\hat{\Psi}-f\right\|}_{P_{\mathcal{X}}}^{2}\leq\frac{s(\lambda_{d+1})}{s(\lambda_{1})-s(\lambda_{d+1})}{\left[s(\lambda_{1})\epsilon-1\right]}B^{2}$
if $\hat{\Psi}$ spans
${\textnormal{span}}{\left\\{\psi_{1},\cdots,\psi_{d}\right\\}}$. For any
$f=\sum_{i}u_{i}\psi_{i}\in{\mathcal{F}}_{s}$, we have $\sum_{i}u_{i}^{2}\leq
B^{2}$, and
$\sum_{i}\frac{u_{i}^{2}}{s(\lambda_{i})}\leq\epsilon\sum_{i}u_{i}^{2}$. Let
$a=\sum_{i\geq d+1}u_{i}^{2}$, and $b=\sum_{i=1}^{d}u_{i}^{2}$. Then, $a+b\leq
B^{2}$. So we have

$\displaystyle 0$
$\displaystyle\geq\sum_{i}\frac{u_{i}^{2}}{s(\lambda_{i})}-\epsilon\sum_{i}u_{i}^{2}\geq{\left[\frac{1}{s(\lambda_{1})}-\epsilon\right]}b+{\left[\frac{1}{s(\lambda_{d+1})}-\epsilon\right]}a\qquad(\text{since
}s\text{ is monotonic})$
$\displaystyle\geq{\left[\frac{1}{s(\lambda_{1})}-\epsilon\right]}(B^{2}-a)+{\left[\frac{1}{s(\lambda_{d+1})}-\epsilon\right]}a={\left[\frac{1}{s(\lambda_{1})}-\epsilon\right]}B^{2}+{\left[\frac{1}{s(\lambda_{d+1})}-\frac{1}{s(\lambda_{1})}\right]}a,$

which implies that
$\min_{{\bm{w}}\in\mathbb{R}^{d}}{\left\|{\bm{w}}^{\top}\hat{\Psi}-f\right\|}_{P_{\mathcal{X}}}^{2}=a\leq\frac{s(\lambda_{d+1})}{s(\lambda_{1})-s(\lambda_{d+1})}{\left[s(\lambda_{1})\epsilon-1\right]}B^{2}$.
∎

###  B.9 Proof of Theorem 4

For any $f=\sum_{i}u_{i}\psi_{i}\in{{\mathcal{H}}_{{K_{s}}}}$ satisfying
Assumption 3,
$\|f\|_{{\mathcal{H}}_{K}}^{2}=\sum_{i}\frac{u_{i}^{2}}{\lambda_{i}}\leq\sum_{i}\frac{u_{i}^{2}}{s(\lambda_{i})/M}\leq\epsilon
MB^{2}$.

Define $\tilde{f}_{d}$ as the projection of $f^{*}$ onto $\hat{\Psi}$ w.r.t.
${{\mathcal{H}}_{K}}$. Define RKHS
${\mathcal{H}}_{\hat{\Psi}}:={\textnormal{span}}{\left\\{\hat{\psi}_{1},\cdots,\hat{\psi}_{d}\right\\}}$
as a subspace of ${\mathcal{H}}_{K}$, then
$\tilde{f}_{d}\in{\mathcal{H}}_{\hat{\Psi}}$. Let $K_{\hat{\Psi}}$ be the
reproducing kernel of ${\mathcal{H}}_{\hat{\Psi}}$. Let
$\tilde{{\bm{y}}}:=[\tilde{y}_{1},\cdots,\tilde{y}_{n}]$, where
$\tilde{y}_{i}:=\tilde{f}_{d}(x_{i})+y_{i}-f^{*}(x_{i})$. Then, the KRR of
$\tilde{f}_{d}$ with $K_{\hat{\Psi}}$ is given by

$\hat{f}_{d}^{\dagger}=\tilde{{\bm{w}}}^{*\top}\hat{\Psi},\quad\tilde{{\bm{w}}}^{*}={\left(\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}+n\beta_{n}{\bm{I}}_{d}\right)}^{-1}\hat{\Psi}({\bm{X}}_{n})\tilde{{\bm{y}}}.$

First, we show a lower bound for the eigenvalues of
$\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}$. Similar to Eqn. 14,
define
${\mathcal{F}}:={\left\\{f=g_{1}g_{2}\;\middle|\;g_{1},g_{2}\in{{\mathcal{H}}_{K}},\|g_{1}\|_{{\mathcal{H}}_{K}},\|g_{2}\|_{{\mathcal{H}}_{K}}\leq
1\right\\}}$, then we have:

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-\mathbb{E}_{X\sim{P_{\mathcal{X}}}}[f(X)]\right|\leq\frac{\kappa^{2}}{\sqrt{n}}{\left(2+\sqrt{2\log\frac{2}{\delta}}\right)}\qquad\text{for
all }f\in{\mathcal{F}};$ (16)
$\displaystyle\left|\frac{1}{m}\sum_{i=n+1}^{n+m}f(x_{i})-\mathbb{E}_{X\sim{P_{\mathcal{X}}}}[f(X)]\right|\leq\frac{\kappa^{2}}{\sqrt{m}}{\left(2+\sqrt{2\log\frac{2}{\delta}}\right)}\qquad\text{for
all }f\in{\mathcal{F}}$ (17)

hold simultaneously with probability at least $1-\delta$ for any $\delta>0$.
In what follows, we assume them to hold. Then for all $f\in{\mathcal{F}}$, we
have
$\left|\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-\frac{1}{m}\sum_{i=n+1}^{n+m}f(x_{i})\right|\leq\frac{\kappa^{2}}{\sqrt{n}}{\left(4+2\sqrt{2\log\frac{2}{\delta}}\right)}$.

For any unit vector ${\bm{u}}\in\mathbb{R}^{d}$, let
$f={\bm{u}}^{\top}\hat{\Psi}$. Then, $\|f\|_{{\mathcal{H}}_{K}}\in 1$, so
$f^{2}\in{\mathcal{F}}$. And we have

$\sum_{i=n+1}^{n+m}f(x_{i})^{2}={\left\|{\bm{G}}_{K,m}[{\bm{v}}_{1},\cdots,{\bm{v}}_{d}]{\bm{u}}\right\|}_{2}^{2}={\left\|[m\tilde{\lambda}_{1}{\bm{v}}_{1},\cdots,m\tilde{\lambda}_{d}{\bm{v}}_{d}]{\bm{u}}\right\|}_{2}^{2}=\sum_{j=1}^{d}m\tilde{\lambda}_{j}u_{j}^{2}\geq
m\tilde{\lambda}_{d},$

which implies that

$\frac{1}{n}\sum_{i=1}^{n}f(x_{i})^{2}\geq\tilde{\lambda}_{d}-\frac{\kappa^{2}}{\sqrt{n}}{\left(4+2\sqrt{2\log\frac{2}{\delta}}\right)}\qquad\text{for
all }f={\bm{u}}^{\top}\hat{\Psi}\text{ where }{\bm{u}}\in\mathbb{R}^{d}\text{
is a unit vector}.$

Thus, for any unit vector ${\bm{u}}\in\mathbb{R}^{d}$,
$\|{\bm{u}}^{\top}\hat{\Psi}({\bm{X}}_{n})\|_{2}^{2}\geq
n\tilde{\lambda}_{d}-\kappa^{2}\sqrt{n}{\left(4+2\sqrt{2\log\frac{2}{\delta}}\right)}$.

Second, we bound
$\|\hat{f}_{d}-\hat{f}_{d}^{\dagger}\|_{{\mathcal{H}}_{K}}^{2}$. Denote
$\Delta{\bm{y}}:=[f^{*}(x_{1})-\tilde{f}_{d}(x_{1}),\cdots,f^{*}(x_{n})-\tilde{f}_{d}(x_{n})]^{\top}\in\mathbb{R}^{n}$.
Note that
$\langle\hat{\Psi},\hat{\Psi}\rangle_{{\mathcal{H}}_{K}}={\bm{I}}_{d}$, so we
have

$\displaystyle{\left\|\hat{f}_{d}-\hat{f}_{d}^{\dagger}\right\|}_{{\mathcal{H}}_{K}}^{2}$
$\displaystyle={\left\|{\left[{\left(\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}+n\beta_{n}{\bm{I}}_{d}\right)}^{-1}\hat{\Psi}({\bm{X}}_{n}){\left({\bm{y}}-\tilde{{\bm{y}}}\right)}\right]}^{\top}\hat{\Psi}\right\|}_{{\mathcal{H}}_{K}}^{2}$
$\displaystyle={\left\|{\left(\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}+n\beta_{n}{\bm{I}}_{d}\right)}^{-1}\hat{\Psi}({\bm{X}}_{n})\Delta{\bm{y}}\right\|}_{2}^{2}.$

So it suffices to bound
${\left\|{\bm{Q}}^{-1}\hat{\Psi}({\bm{X}}_{n})\right\|}_{2}^{2}$ where
${\bm{Q}}=\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}+n\beta_{n}{\bm{I}}_{d}$,
which is equal to the largest eigenvalue of
$\hat{\Psi}({\bm{X}}_{n})^{\top}{\bm{Q}}^{-2}\hat{\Psi}({\bm{X}}_{n})$, which
is further equal to the largest eigenvalue of
${\bm{Q}}^{-2}\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}$ by
Sylvester’s theorem. Let the eigenvalues of
$\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}$ be
$\mu_{1}\geq\cdots\geq\mu_{d}\geq 0$, with corresponding eigenvectors
${\bm{\alpha}}_{1},\cdots,{\bm{\alpha}}_{d}$ that form an orthonormal basis of
$\mathbb{R}^{d}$. For all $i\in[d]$, if $\mu_{i}=0$, then
${\bm{Q}}^{-2}\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}{\bm{\alpha}}_{i}={\bm{0}}$,
meaning that ${\bm{\alpha}}_{i}$ is also an eigenvector of
${\bm{Q}}^{-2}\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}$ with
eigenvalue 0. And if $\mu_{i}>0$, then we have

${\bm{Q}}{\bm{\alpha}}_{i}=\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}{\bm{\alpha}}_{i}+n\beta_{n}{\bm{\alpha}}_{i}=(\mu_{i}+n\beta_{n}){\bm{\alpha}}_{i},$

which implies that
${\bm{Q}}^{2}\alpha_{i}={\bm{Q}}(\mu_{i}+n\beta_{n}){\bm{\alpha}}_{i}=(\mu_{i}+n\beta_{n})^{2}{\bm{\alpha}}_{i}=\frac{(\mu_{i}+n\beta_{n})^{2}}{\mu_{i}}\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}{\bm{\alpha}}_{i}$.
Thus, ${\bm{\alpha}}_{i}$ is an eigenvector of
${\bm{Q}}^{-2}\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}$ with
eigenvalue $\frac{\mu_{i}}{(\mu_{i}+n\beta_{n})^{2}}$. This means that
${\bm{\alpha}}_{1},\cdots,{\bm{\alpha}}_{d}$ are all eigenvectors of
${\bm{Q}}^{-2}\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}$. On the
other hand, we have $\mu_{d}\geq
n\tilde{\lambda}_{d}-\kappa^{2}\sqrt{n}{\left(4+2\sqrt{2\log\frac{2}{\delta}}\right)}$,
and suppose that $n$ is large enough so that
$\mu_{d}\geq\frac{n\tilde{\lambda}_{d}}{2}$, i.e.
$n\geq\frac{4\kappa^{4}}{\tilde{\lambda}_{d}^{2}}{\left(4+2\sqrt{2\log\frac{2}{\delta}}\right)}^{2}$.
Then, we have

${\left\|{\bm{Q}}^{-1}\hat{\Psi}({\bm{X}}_{n})\right\|}_{2}^{2}\leq\max_{i\in[d]}\frac{\mu_{i}}{(\mu_{i}+n\beta_{n})^{2}}\leq\max_{i\in[d]}\frac{1}{\mu_{i}}\leq\frac{2}{n\tilde{\lambda}_{d}}.$

Thus,
${\left\|\hat{f}_{d}-\hat{f}_{d}^{\dagger}\right\|}_{{\mathcal{H}}_{K}}^{2}\leq\frac{2}{\tilde{\lambda}_{d}}\frac{\|\Delta{\bm{y}}\|_{2}^{2}}{n}$.

Third, we bound $\|\hat{f}_{d}-\hat{f}_{d}^{\dagger}\|_{P_{\mathcal{X}}}^{2}$.
Denote
$\Delta{\bm{f}}:=[\hat{f}_{d}(x_{1})-\hat{f}_{d}^{\dagger}(x_{1}),\cdots,\hat{f}_{d}(x_{n})-\hat{f}_{d}^{\dagger}(x_{n})]^{\top}\in\mathbb{R}^{n}$.
Then, we have

$\Delta{\bm{f}}=\hat{\Psi}({\bm{X}}_{n})^{\top}(\hat{{\bm{w}}}^{*}-\tilde{{\bm{w}}}^{*})=\hat{\Psi}({\bm{X}}_{n})^{\top}{\left(\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}+n\beta_{n}{\bm{I}}_{d}\right)}^{-1}\hat{\Psi}({\bm{X}}_{n})\Delta{\bm{y}}.$

Similarly, we can show that the eigenvalues of
$\hat{\Psi}({\bm{X}}_{n})^{\top}{\left(\hat{\Psi}({\bm{X}}_{n})\hat{\Psi}({\bm{X}}_{n})^{\top}+n\beta_{n}{\bm{I}}_{d}\right)}^{-1}\hat{\Psi}({\bm{X}}_{n})$
are $\frac{\mu_{i}}{\mu_{i}+n\beta_{n}}$, which are no larger than 1. Thus,
$\|\Delta{\bm{f}}\|_{2}\leq\|\Delta{\bm{y}}\|_{2}$. And by Eqn. 16, we have

$\frac{\|\Delta{\bm{y}}\|_{2}^{2}}{n}\leq\|f^{*}-\tilde{f}_{d}\|_{P_{\mathcal{X}}}^{2}+\|f^{*}-\tilde{f}_{d}\|_{{\mathcal{H}}_{K}}^{2}\frac{\kappa^{2}}{\sqrt{n}}{\left(2+\sqrt{2\log\frac{2}{\delta}}\right)}.$

So by Eqn. 16, we have

$\displaystyle\|\hat{f}_{d}-\hat{f}_{d}^{\dagger}\|_{P_{\mathcal{X}}}^{2}$
$\displaystyle\leq\frac{\|\Delta{\bm{f}}\|_{2}^{2}}{n}+\|\hat{f}_{d}-\hat{f}_{d}^{\dagger}\|_{{\mathcal{H}}_{K}}^{2}\frac{\kappa^{2}}{\sqrt{n}}{\left(2+\sqrt{2\log\frac{2}{\delta}}\right)}$
$\displaystyle\leq\frac{\|\Delta{\bm{y}}\|_{2}^{2}}{n}{\left[1+\frac{2\kappa^{2}}{\tilde{\lambda}_{d}\sqrt{n}}{\left(2+\sqrt{2\log\frac{2}{\delta}}\right)}\right]}$
$\displaystyle\leq{\left[\|f^{*}-\tilde{f}_{d}\|_{P_{\mathcal{X}}}^{2}+\|f^{*}-\tilde{f}_{d}\|_{{\mathcal{H}}_{K}}^{2}\frac{\kappa^{2}}{\sqrt{n}}{\left(2+\sqrt{2\log\frac{2}{\delta}}\right)}\right]}{\left[1+\frac{2\kappa^{2}}{\tilde{\lambda}_{d}\sqrt{n}}{\left(2+\sqrt{2\log\frac{2}{\delta}}\right)}\right]}$
$\displaystyle\leq\frac{3}{2}{\left(\|f^{*}-\tilde{f}_{d}\|_{P_{\mathcal{X}}}^{2}+\frac{\tilde{\lambda}_{d}}{4}\|f^{*}-\tilde{f}_{d}\|_{{\mathcal{H}}_{K}}^{2}\right)},$

where the final step uses
$n\geq\frac{4\kappa^{4}}{\tilde{\lambda}_{d}^{2}}{\left(4+2\sqrt{2\log\frac{2}{\delta}}\right)}^{2}$.

Finally, we bound
${\left\|\hat{f}_{d}^{\dagger}-\tilde{f}_{d}\right\|}_{P_{\mathcal{X}}}$ using
Theorem 6 with $K=K_{\hat{\Psi}}$, $\alpha=\beta=1$, and $\gamma=0$. Recall
the four conditions:

  * •

(EVD) is satisfied for any $p\in(0,1]$ since $K_{\hat{\Psi}}$ has at most $d$
non-zero eigenvalues.

  * •

(EMB) is satisfied with $c_{2}=\kappa$ since
$\|f\|_{{\mathcal{H}}_{\hat{\Psi}}}=\|f\|_{{\mathcal{H}}_{K}}$ for all
$f\in{\mathcal{H}}_{\hat{\Psi}}$.

  * •

(SRC) is satisfied with $c_{3}=\sqrt{\epsilon M}B$ since
$\|\tilde{f}_{d}\|_{{\mathcal{H}}_{\hat{\Psi}}}\leq\|f^{*}\|_{{\mathcal{H}}_{K}}\leq\sqrt{\epsilon
M}B$.

  * •

(MOM) is satisfied by condition.

And we have $B_{\infty}=\kappa\sqrt{\epsilon M}B$. Thus, when
$\tau\geq\kappa^{-1}$, it holds with probability at least $1-4e^{-\tau}$ that

${\left\|\hat{f}_{d}^{\dagger}-\tilde{f}_{d}\right\|}_{P_{\mathcal{X}}}^{2}\leq\frac{c_{0}}{2}\tau^{2}{\left[{\left(\kappa^{2}M\epsilon
B^{2}+\kappa^{2}\sigma^{2}\right)}n^{-\frac{1}{1+p}}+\kappa^{2}\max{\left\\{L^{2},\kappa^{2}M\epsilon
B^{2}\right\\}}n^{-\frac{1+2p}{1+p}}\right]}.$

Combining the two inequalities with $(a+b)^{2}\leq 2(a^{2}+b^{2})$ yields the
result. ∎

###  B.10 Proof of Theorem 5

We start with the following lemma:

######  Lemma 9.

For any $g\in{{\mathcal{H}}_{K}}$ such that $\|g\|_{{\mathcal{H}}_{K}}=1$ and
$\langle g,\hat{\psi}_{i}\rangle_{{\mathcal{H}}_{K}}=0$ for all $i\in[d]$,
there is

$\|\hat{\psi}_{1}\|_{P_{\mathcal{X}}}^{2}+\cdots+\|\hat{\psi}_{d}\|_{P_{\mathcal{X}}}^{2}+\|g\|_{P_{\mathcal{X}}}^{2}\leq\lambda_{1}+\cdots+\lambda_{d+1}.$
(18)

###### Proof.

Let
${\left[\hat{\psi}_{1},\cdots,\hat{\psi}_{d},g\right]}={\bm{Q}}{\bm{D}}_{\lambda}^{1/2}{\bm{\Psi}^{*}}$,
where
${\bm{D}}_{\lambda}={\textnormal{diag}}(\lambda_{1},\lambda_{2},\cdots)$, and
${\bm{\Psi}^{*}}={\left[\psi_{1},\psi_{2},\cdots\right]}$. Then,
${\bm{Q}}{\bm{Q}}^{\top}={\left\langle{\left[\hat{\psi}_{1},\cdots,\hat{\psi}_{d},g\right]},{\left[\hat{\psi}_{1},\cdots,\hat{\psi}_{d},g\right]}\right\rangle}_{{\mathcal{H}}_{K}}={\bm{I}}_{d+1}$,
and

$\|\hat{\psi}_{1}\|_{P_{\mathcal{X}}}^{2}+\cdots+\|\hat{\psi}_{d}\|_{P_{\mathcal{X}}}^{2}+\|g\|_{P_{\mathcal{X}}}^{2}=\operatorname{Tr}{\left({\bm{Q}}{\bm{D}}_{\lambda}{\bm{Q}}^{\top}\right)}.$

So we obtain the result by applying Lemma 9 in Zhai et al. (2024). ∎

Define
${\mathcal{F}}_{d}:={\left\\{f=\sum_{i=1}^{d}g_{i}^{2}\;\middle|\;g_{i}\in{{\mathcal{H}}_{K}},\langle
g_{i},g_{j}\rangle_{{\mathcal{H}}_{K}}=\delta_{i,j}\right\\}}$. We now bound
its Rademacher complexity. For any $x$, denote
$\Psi(x)=[\lambda_{1}^{1/2}\psi_{1}(x),\lambda_{2}^{1/2}\psi_{2}(x),\cdots]$.
For any $S=\\{x_{1},\cdots,x_{m}\\}$, denote $\Psi_{k}=\Psi(x_{k})$ for
$k\in[m]$. Let $g_{i}(x)={\bm{u}}_{i}^{\top}\Psi(x)$, and denote
${\bm{U}}=[{\bm{u}}_{1},\cdots,{\bm{u}}_{d}]$. Then,
${\bm{U}}^{\top}{\bm{U}}={\bm{I}}_{d}$. Let
${\bm{\sigma}}=[\sigma_{1},\cdots,\sigma_{m}]$ be Rademacher variates. Thus,
the empirical Rademacher complexity satisfies:

$\displaystyle\hat{\mathfrak{R}}_{S}({\mathcal{F}}_{d})$
$\displaystyle\leq\underset{{\bm{\sigma}}}{\mathbb{E}}{\left[\sup_{{\bm{u}}_{1},\cdots,{\bm{u}}_{d}}\left|\frac{1}{m}\sum_{k=1}^{m}\sum_{i=1}^{d}\sigma_{k}{\bm{u}}_{i}^{\top}\Psi_{k}\Psi_{k}^{\top}{\bm{u}}_{i}\right|\right]}$
$\displaystyle=\underset{{\bm{\sigma}}}{\mathbb{E}}{\left[\sup_{{\bm{U}}:{\bm{U}}^{\top}{\bm{U}}={\bm{I}}_{d}}\left|\operatorname{Tr}{\left({\bm{U}}^{\top}{\left(\frac{1}{m}\sum_{k=1}^{m}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}\right)}{\bm{U}}\right)}\right|\right]}$
$\displaystyle=\underset{{\bm{\sigma}}}{\mathbb{E}}{\left[\sup_{{\bm{U}}:{\bm{U}}^{\top}{\bm{U}}={\bm{I}}_{d}}\left|\operatorname{Tr}{\left({\left(\frac{1}{m}\sum_{k=1}^{m}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}\right)}{\bm{U}}{\bm{U}}^{\top}\right)}\right|\right]}.$

Let $\mu_{1}\geq\mu_{2}\geq\cdots$ be the singular values of
$\frac{1}{m}\sum_{k=1}^{m}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}$. For any
${\bm{U}}$, the singular values of ${\bm{U}}{\bm{U}}^{\top}$ are $d$ ones and
then zeros. So by von Neumann’s trace inequality, we have:

$\sup_{{\bm{U}}:{\bm{U}}^{\top}{\bm{U}}={\bm{I}}_{d}}\left|\operatorname{Tr}{\left({\left(\frac{1}{m}\sum_{k=1}^{m}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}\right)}{\bm{U}}{\bm{U}}^{\top}\right)}\right|\leq\mu_{1}+\cdots+\mu_{d}\leq\frac{\sqrt{d}}{m}\cdot{\left\|\sum_{k=1}^{m}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}\right\|}_{F},$

where the last step is Cauchy-Schwarz inequality applied to the diagonalized
matrix. So we have:

$\hat{\mathfrak{R}}_{S}({\mathcal{F}}_{d})\leq\frac{\sqrt{d}}{m}\underset{{\bm{\sigma}}}{\mathbb{E}}{\left[{\left\|\sum_{k=1}^{m}\sigma_{k}\Psi_{k}\Psi_{k}^{\top}\right\|}_{F}\right]}\leq\frac{\kappa^{2}\sqrt{d}}{\sqrt{m}}\qquad\text{almost
surely},$

where the last step was proved in Proposition 13 of Zhai et al. (2024). Thus,
for the Rademacher complexity we have
$\mathfrak{R}_{m}({\mathcal{F}}_{d})=\mathbb{E}_{S}[\hat{\mathfrak{R}}_{S}({\mathcal{F}}_{d})]\leq\frac{\kappa^{2}\sqrt{d}}{\sqrt{m}}$.
Moreover, for ${P_{\mathcal{X}}}$-almost all $x$, we have:

$\sum_{i=1}^{d}g_{i}(x)^{2}=\Psi(x)^{\top}{\left(\sum_{i=1}^{d}{\bm{u}}_{i}{\bm{u}}_{i}^{\top}\right)}\Psi(x)=\Psi(x)^{\top}{\bm{U}}{\bm{U}}^{\top}\Psi(x)\leq\|\Psi(x)\|_{2}^{2}\|{\bm{U}}{\bm{U}}^{\top}\|_{2}=\|\Psi(x)\|_{2}^{2}\leq\kappa^{2},$

where the last step is because
$\Psi(x)^{\top}\Psi(x)=\sum_{i}\lambda_{i}\psi_{i}(x)^{2}\leq\kappa^{2}$ for
all $x$. Hence, by Theorem 4.10 of Wainwright (2019), we have:

$\left|\frac{1}{m}\sum_{i=n+1}^{n+m}f(x_{i})-\mathbb{E}_{X\sim{P_{\mathcal{X}}}}[f(X)]\right|\leq\frac{\kappa^{2}}{\sqrt{m}}{\left(2\sqrt{d}+\sqrt{2\log\frac{2}{\delta}}\right)}\qquad\text{for
all }f\in{\mathcal{F}}_{d}$ (19)

holds with probability at least $1-\frac{\delta}{2}$. Let
$F(x)=\sum_{i=1}^{d}\hat{\psi}_{i}(x)^{2}$. Then, $F\in{\mathcal{F}}_{d}$. And
for all $i\in[d]$, there is
$[\hat{\psi}_{i}(x_{n+1}),\cdots,\hat{\psi}_{i}(x_{n+m})]^{\top}={\bm{G}}_{k,m}{\bm{v}}_{i}=m\tilde{\lambda}_{i}{\bm{v}}_{i}$,
so
$\hat{\psi}_{i}(x_{n+1})^{2}+\cdots+\hat{\psi}_{i}(x_{n+m})^{2}=m^{2}\tilde{\lambda}_{i}^{2}\|{\bm{v}}_{i}\|_{2}^{2}=m\tilde{\lambda}_{i}$.
Thus,
$\frac{1}{m}\sum_{i=1}^{n+m}F(x_{i})=\tilde{\lambda}_{1}+\cdots+\tilde{\lambda}_{d}$.
So if Eqn. 19 holds, then

$\|\hat{\psi}_{1}\|_{P_{\mathcal{X}}}^{2}+\cdots+\|\hat{\psi}_{d}\|_{P_{\mathcal{X}}}^{2}\geq\tilde{\lambda}_{1}+\cdots+\tilde{\lambda}_{d}-\frac{\kappa^{2}}{\sqrt{m}}{\left(2\sqrt{d}+\sqrt{2\log\frac{2}{\delta}}\right)}.$

Since $\hat{\lambda}_{1},\cdots,\hat{\lambda}_{d}$ are the eigenvalues of
$\frac{{\bm{G}}_{k,m}}{m}$, by Theorem 3.2 of Blanchard et al. (2007), we
have:

$\tilde{\lambda}_{1}+\cdots+\tilde{\lambda}_{d}\geq\lambda_{1}+\cdots+\lambda_{d}-\frac{\kappa^{2}}{\sqrt{m}}\sqrt{\frac{1}{2}\log\frac{6}{\delta}}$

holds with probability at least $1-\frac{\delta}{2}$. By union bound, it holds
with probability at least $1-\delta$ that

$\|\hat{\psi}_{1}\|_{P_{\mathcal{X}}}^{2}+\cdots+\|\hat{\psi}_{d}\|_{P_{\mathcal{X}}}^{2}\geq\lambda_{1}+\cdots+\lambda_{d}-\frac{\kappa^{2}}{\sqrt{m}}{\left(2\sqrt{d}+3\sqrt{\log\frac{6}{\delta}}\right)}.$

Let $f^{*}-\tilde{f}_{d}=bg$, where $b\in\mathbb{R}$, and
$g\in{{\mathcal{H}}_{K}}$ satisfies $\|g\|_{{\mathcal{H}}_{K}}=1$ and $\langle
g,\hat{\psi}_{i}\rangle_{{\mathcal{H}}_{K}}=0$ for $i\in[d]$. Then, by 9, we
have

$\|g\|_{P_{\mathcal{X}}}^{2}\leq\lambda_{d+1}+\frac{\kappa^{2}}{\sqrt{m}}{\left(2\sqrt{d}+3\sqrt{\log\frac{6}{\delta}}\right)}.$

Let $a=\|\tilde{f}_{d}\|_{{\mathcal{H}}_{K}}$. Then,
$\|f^{*}\|_{{\mathcal{H}}_{K}}^{2}=a^{2}+b^{2}$. Since
$\|f\|_{{\mathcal{H}}_{K}}^{2}\leq\epsilon M\|f^{*}\|_{P_{\mathcal{X}}}^{2}$,
we have:

$\frac{a^{2}+b^{2}}{\epsilon
M}\leq\|f^{*}\|_{P_{\mathcal{X}}}^{2}\leq{\left(\|\tilde{f}_{d}\|_{P_{\mathcal{X}}}+b\|g\|_{P_{\mathcal{X}}}\right)}^{2}\leq{\left(a\sqrt{\lambda_{1}}+b\|g\|_{P_{\mathcal{X}}}\right)}^{2}\leq
2(a^{2}\lambda_{1}+b^{2}\|g\|_{P_{\mathcal{X}}}^{2}),$

which implies that

$(\lambda_{1}-\|g\|_{P_{\mathcal{X}}}^{2})b^{2}\leq{\left(\lambda_{1}-\frac{1}{2\epsilon
M}\right)}(a^{2}+b^{2})\leq{\left(\lambda_{1}\epsilon
M-\frac{1}{2}\right)}B^{2},$

which completes the proof. ∎

##  Appendix C Details of Numerical Implementations

Algorithm 3 Directly solving STKR

1:$K(x,x^{\prime})$, $s(\lambda)=\sum_{p=1}^{q}\pi_{p}\lambda^{p}$,
$\beta_{n}$, ${\bm{y}}$

2:# ${\bm{G}}_{K,n+m,n}$ is the left $n$ columns of ${\bm{G}}_{K}$

3:Initialize: ${\bm{M}}\leftarrow{\bm{G}}_{K,n+m,n}\in\mathbb{R}^{(n+m)\times
n}$

4:${\bm{A}}\leftarrow
n\beta_{n}{\bm{I}}_{n}+\pi_{1}{\bm{G}}_{K,n}\in\mathbb{R}^{n\times n}$

5:for $p=2,\cdots,q$ do

6:
${\bm{A}}\leftarrow{\bm{A}}+\frac{\pi_{p}}{n+m}{\bm{G}}_{K,n+m,n}^{\top}{\bm{M}}$

7: ${\bm{M}}\leftarrow\frac{1}{n+m}{\bm{G}}_{K}{\bm{M}}$

8:Solve ${\bm{A}}\hat{{\bm{\alpha}}}={\bm{y}}$

STKR amounts to solving ${\bm{A}}\hat{{\bm{\alpha}}}={\bm{y}}$ for
${\bm{A}}={\bm{G}}_{{\hat{K}_{s}},n}+n\beta_{n}{\bm{I}}_{n}$. First, consider
$s(\lambda)=\sum_{p=1}^{q}\pi_{p}\lambda^{p}$ with $q<\infty$. Provided that
computing $K(x,x^{\prime})$ for any $x,x^{\prime}$ takes $O(1)$ time, directly
computing ${\bm{A}}$ and then solving ${\bm{A}}\hat{{\bm{\alpha}}}={\bm{y}}$
as described above has a time complexity of $O((n+m)^{2}nq)$ as it performs
$O(q)$ matrix multiplications, and a space complexity of $O((n+m)n)$.
Calculating ${\bm{A}}$ directly could be expensive since it may require many
matrix-matrix multiplications.

Alternatively we can use iterative methods, such as Richardson iteration that
solves ${\bm{A}}\hat{{\bm{\alpha}}}={\bm{y}}$ with
$\hat{{\bm{\alpha}}}_{t+1}=\hat{{\bm{\alpha}}}_{t}-\gamma({\bm{A}}\hat{{\bm{\alpha}}}_{t}-{\bm{y}})$
for some $\gamma>0$, as described in Algorithm 1 in the main text. This is
faster than the direct method since it replaces matrix-matrix multiplication
with matrix-vector multiplication.

It is well-known that with a proper $\gamma$, it takes
$O(\kappa({\bm{A}})\log\frac{1}{\epsilon})$ Richardson iterations to ensure
$\|\hat{{\bm{\alpha}}}_{t}-\hat{{\bm{\alpha}}}_{*}\|_{2}<\epsilon\|\hat{{\bm{\alpha}}}_{*}\|_{2}$,
where $\hat{{\bm{\alpha}}}_{*}$ is the real solution, and $\kappa({\bm{A}})$
is the condition number of ${\bm{A}}$. Let $\lambda$ be a known upper bound of
$\lambda_{1}$ (e.g. for augmentation-based pretraining, $\lambda=1$ (Zhai et
al., 2024)). With a sufficiently large $n$, we have
$\kappa({\bm{A}})=O(\beta_{n}^{-1}s(\lambda))$ almost surely, so Richardson
iteration has a total time complexity of
$O((n+m)^{2}\beta_{n}^{-1}s(\lambda)q\log\frac{1}{\epsilon})$, and a space
complexity of $O(n+m)$. The method can be much faster if $K$ is sparse. For
instance, if $K$ is the adjacency matrix of a graph with $|E|$ edges, then
each iteration only takes $O(q\cdot|E|)$ time instead of $O(q(n+m)^{2})$.

Next, we consider the case where $s$ could be complex, but
$s^{-1}(\lambda)=\sum_{p=0}^{q-1}\xi_{p}\lambda^{p-r}$ is simple, such as the
inverse Laplacian (Example 1). In this case we cannot compute
${\bm{G}}_{{\hat{K}_{s}},n}$, but if we define
${\bm{Q}}:=\sum_{p=0}^{q-1}\xi_{p}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{p}$,
then there is
${\bm{G}}_{{\hat{K}_{s}}}{\bm{Q}}=(n+m){\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}$.
With this observation, we use an indirect approach to find
$\hat{{\bm{\alpha}}}$, which is to find a ${\bm{\theta}}\in\mathbb{R}^{n+m}$
such that ${\bm{Q}}{\bm{\theta}}=[\hat{{\bm{\alpha}}},{\bm{0}}_{m}]^{\top}$.
Note that by the definition of $\hat{{\bm{\alpha}}}$, the first $n$ elements
of
${\left({\bm{G}}_{{\hat{K}_{s}}}+n\beta_{n}{\bm{I}}_{n+m}\right)}[\hat{{\bm{\alpha}}},{\bm{0}}_{m}]^{\top}={\left({\bm{G}}_{{\hat{K}_{s}}}+n\beta_{n}{\bm{I}}_{n+m}\right)}{\bm{Q}}{\bm{\theta}}={\left[(n+m){\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}+n\beta_{n}{\bm{Q}}\right]}{\bm{\theta}}$
is ${\bm{y}}$, which provides $n$ linear equations. The last $m$ elements of
${\bm{Q}}{\bm{\theta}}$ are zeros, which gives $m$ linear equations. Combining
these two gives an $(n+m)$-dimensional linear system, which we simplify as:

${\bm{M}}{\bm{\theta}}=\tilde{{\bm{y}}},\quad\text{where
}{\bm{M}}:=(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}+n\beta_{n}{\bm{Q}},\quad\text{and
}\tilde{{\bm{y}}}:=[{\bm{y}},{\bm{0}}_{m}]^{\top}.$ (20)

Here, $\tilde{{\bm{I}}}_{n}:={\textnormal{diag}}\\{1,\cdots,1,0,\cdots,0\\}$,
with $n$ ones and $m$ zeros. Again, we can find ${\bm{\theta}}$ by Richardson
iteration, as described in Algorithm 2, with $O(n+m)$ space complexity. Let
${\bm{v}}_{K}$ be defined as in Eqn. 5. Then, at inference time, one can
compute
$\hat{f}(x)={\bm{v}}_{K}(x)^{\top}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r-1}{\bm{\theta}}$
in $O(n+m)$ time by storing
${\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r-1}{\bm{\theta}}$ in the memory.

We now discuss the time complexity of Algorithm 2. We cannot use the previous
argument because now ${\bm{M}}$ is not symmetrical. Let
$\rho(\lambda):=\frac{\lambda^{r}}{s(\lambda)}=\sum_{p=0}^{q-1}\xi_{p}\lambda^{p}$,
where $\rho(0)=\xi_{0}>0$ . Then, $\rho(\lambda)$ is continuous on
$[0,+\infty)$. Denote its maximum and minimum on $[0,\lambda]$ by
$\rho_{\max}$ and $\rho_{\min}$, where again $\lambda$ is a known upper bound
of $\lambda_{1}$. Then, we have the following:

######  Proposition 10.

With $\gamma=(n\lambda^{r})^{-1}$, Algorithm 2 takes
$O{\left(\frac{\lambda^{r}}{\beta_{n}\rho_{\min}}\log{\left(\max{\left\\{\frac{1}{\epsilon},\frac{\lambda^{r}\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}^{2}\rho_{\min}^{2}\|\hat{{\bm{\alpha}}}_{*}\|_{2}}\right\\}}\right)}\right)}$
iterations so that
$\|\hat{{\bm{\alpha}}}-\hat{{\bm{\alpha}}}_{*}\|_{2}\leq\epsilon\|\hat{{\bm{\alpha}}}_{*}\|_{2}$
almost surely for sufficiently large $n$, where $\hat{{\bm{\alpha}}}_{*}$ is
the ground truth solution and $\hat{{\bm{\alpha}}}$ is the output of the
algorithm. Each iteration takes $O(\max{\left\\{q,r\right\\}}(n+m)^{2})$ time.
Thus, the total time complexity is
$O{\left((n+m)^{2}\beta_{n}^{-1}\frac{\max{\left\\{q,r\right\\}}\lambda^{r}}{\rho_{\min}}\log{\left(\max{\left\\{\frac{1}{\epsilon},\frac{\lambda^{r}\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}^{2}\rho_{\min}^{2}\|\hat{{\bm{\alpha}}}_{*}\|_{2}}\right\\}}\right)}\right)}$.

###### Proof.

Let $\hat{\lambda}_{1}\geq\cdots\geq\hat{\lambda}_{n+m}$ be the eigenvalues of
$\frac{{\bm{G}}_{K}}{n+m}$. It is easy to show that ${\bm{Q}}$ has the same
eigenvectors as $\frac{{\bm{G}}_{K}}{n+m}$, with eigenvalues
$g(\hat{\lambda}_{1}),\cdots,g(\hat{\lambda}_{2})$. By 2 and Borel-Cantelli
lemma, as $n\rightarrow\infty$,
$\hat{\lambda}_{1}\xrightarrow{\textit{a.s.}}\lambda_{1}$. For simplicity, let
us assume that $\lambda$ is slightly larger than $\lambda_{1}$, so almost
surely there is $\hat{\lambda}_{1}\leq\lambda$. Then, all eigenvalues of
${\bm{Q}}$ are in $[\rho_{\min},\rho_{\max}]$.

The first part of this proof is to bound ${\left\|{\bm{u}}_{t}\right\|}_{2}$,
where
${\bm{u}}_{t}:=(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})$.
Let ${\bm{\theta}}_{t}$ be the ${\bm{\theta}}$ at iteration $t$, and
${\bm{\theta}}_{*}$ be the solution to Eqn. 20. Since
${\bm{\theta}}_{0}={\bm{0}}$, we have

$\displaystyle{\bm{\theta}}_{*}-{\bm{\theta}}_{t}=$
$\displaystyle{\left[{\left({\bm{I}}_{n+m}-\gamma{\left[(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}+n\beta_{n}{\bm{Q}}\right]}\right)}{\bm{\theta}}_{*}+\gamma\tilde{{\bm{y}}}\right]}$
(21)
$\displaystyle-{\left[{\left({\bm{I}}_{n+m}-\gamma{\left[(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}+n\beta_{n}{\bm{Q}}\right]}\right)}{\bm{\theta}}_{t-1}+\gamma\tilde{{\bm{y}}}\right]}$
$\displaystyle=$
$\displaystyle{\left({\bm{I}}_{n+m}-\gamma{\left[(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}+n\beta_{n}{\bm{Q}}\right]}\right)}{\left({\bm{\theta}}_{*}-{\bm{\theta}}_{t-1}\right)}$
$\displaystyle=$
$\displaystyle{\left({\bm{I}}_{n+m}-\gamma{\left[(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}+n\beta_{n}{\bm{Q}}\right]}\right)}^{t}{\bm{\theta}}_{*}.$

Note that

$\displaystyle{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}{\left({\bm{I}}_{n+m}-\gamma{\left[(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}+n\beta_{n}{\bm{Q}}\right]}\right)}$
$\displaystyle=\;$
$\displaystyle{\left({\bm{I}}_{n+m}-\gamma{\left[(n+m){\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}+n\beta_{n}{\bm{Q}}\right]}\right)}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}.$

Thus, by propagating ${\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}$ from left
to right, we get

${\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})={\left({\bm{I}}_{n+m}-\gamma{\bm{R}}\right)}^{t}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}{\bm{\theta}}_{*},$

where
${\bm{R}}:=(n+m){\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}+n\beta_{n}{\bm{Q}}$
is a p.s.d. matrix. Denote the smallest and largest eigenvalues of ${\bm{R}}$
by $\tilde{\lambda}_{\min}$ and $\tilde{\lambda}_{\max}$. Then,
$\tilde{\lambda}_{\min}\geq n\beta_{n}\rho_{\min}$. In terms of
$\tilde{\lambda}_{\max}$, we have

$(n+m){\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}={\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{\frac{r-1}{2}}{\left({\bm{G}}_{K}^{\frac{1}{2}}\tilde{{\bm{I}}}_{n}{\bm{G}}_{K}^{\frac{1}{2}}\right)}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{\frac{r-1}{2}}.$

By Sylvester’s theorem, all non-zero eigenvalues of
${\bm{G}}_{K}^{\frac{1}{2}}\tilde{{\bm{I}}}_{n}{\bm{G}}_{K}^{\frac{1}{2}}$ are
the eigenvalues of $\tilde{{\bm{I}}}_{n}{\bm{G}}_{K}\tilde{{\bm{I}}}_{n}$,
i.e. the non-zero eigenvalues of ${\bm{G}}_{K,n}$. By 2,
$\frac{1}{n}{\left\|{\bm{G}}_{K,n}\right\|}_{2}\xrightarrow{\textit{a.s.}}\lambda_{1}$,
so suppose ${\left\|{\bm{G}}_{K,n}\right\|}_{2}\leq n\lambda$. Then,
$\tilde{\lambda}_{\max}\leq n\lambda^{r}+n\beta_{n}\rho_{\max}$.

Since ${\bm{M}}{\bm{\theta}}_{*}=\tilde{{\bm{y}}}$, and
${\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}{\bm{M}}={\bm{R}}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}$,
we have
${\bm{R}}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}{\bm{\theta}}_{*}={\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}\tilde{{\bm{y}}}$.
Note that
${\bm{R}}({\bm{I}}_{n+m}-\gamma{\bm{R}})=({\bm{I}}_{n+m}-\gamma{\bm{R}}){\bm{R}}$.
Thus, we have

$\displaystyle{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})$
$\displaystyle={\left({\bm{I}}_{n+m}-\gamma{\bm{R}}\right)}^{t}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}{\bm{\theta}}_{*}$
$\displaystyle={\bm{R}}^{-1}({\bm{I}}_{n+m}-\gamma{\bm{R}})^{t}{\bm{R}}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}{\bm{\theta}}_{*}$
$\displaystyle={\bm{R}}^{-1}({\bm{I}}_{n+m}-\gamma{\bm{R}})^{t}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}\tilde{{\bm{y}}}.$

Now we bound $\|{\bm{u}}_{t}\|_{2}$. First, note that for any matrices
${\bm{A}},{\bm{B}}\in\mathbb{R}^{d\times d}$ where ${\bm{B}}$ is p.s.d., there
is
${\bm{u}}^{\top}{\bm{A}}^{\top}{\bm{B}}{\bm{A}}{\bm{u}}\leq\|{\bm{B}}\|_{2}\|{\bm{A}}{\bm{u}}\|_{2}^{2}\leq\|{\bm{B}}\|_{2}\|{\bm{A}}^{\top}{\bm{A}}\|_{2}\|{\bm{u}}\|_{2}^{2}$
for any ${\bm{u}}\in\mathbb{R}^{d}$, so
$\|{\bm{A}}^{\top}{\bm{B}}{\bm{A}}\|_{2}\leq\|{\bm{B}}\|_{2}\|{\bm{A}}^{\top}{\bm{A}}\|_{2}$.
Second, note that the last $m$ elements of $\tilde{{\bm{y}}}$ are zeros, which
means that $\tilde{{\bm{y}}}=\tilde{{\bm{I}}}_{n}\tilde{{\bm{y}}}$. Thus, we
have

$\displaystyle\|{\bm{u}}_{t}\|_{2}$
$\displaystyle={\left\|(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})\right\|}_{2}$
$\displaystyle={\left\|(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}{\bm{R}}^{-1}{\left({\bm{I}}_{n+m}-\gamma{\bm{R}}\right)}^{t}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}\tilde{{\bm{y}}}\right\|}_{2}$
$\displaystyle={\left\|(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}{\left({\bm{I}}_{n+m}-\gamma{\bm{R}}\right)}^{t/2}{\bm{R}}^{-1}{\left({\bm{I}}_{n+m}-\gamma{\bm{R}}\right)}^{t/2}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r/2}\tilde{{\bm{I}}}_{n}\tilde{{\bm{y}}}\right\|}_{2}$
$\displaystyle\leq{\left\|{\left({\bm{I}}_{n+m}-\gamma{\bm{R}}\right)}^{t/2}{\bm{R}}^{-1}{\left({\bm{I}}_{n+m}-\gamma{\bm{R}}\right)}^{t/2}\right\|}_{2}{\left\|(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}\tilde{{\bm{I}}}_{n}\right\|}_{2}{\left\|\tilde{{\bm{y}}}\right\|}_{2}$
$\displaystyle\leq\frac{1}{\tilde{\lambda}_{\min}}{\left\|{\bm{I}}_{n+m}-\gamma{\bm{R}}\right\|}_{2}^{t}(n\lambda_{1}^{r})\|{\bm{y}}\|_{2},$

where the last step is because we have already proved
${\left\|(n+m)\tilde{{\bm{I}}}_{n}{\left(\frac{{\bm{G}}_{K}}{n+m}\right)}^{r}\tilde{{\bm{I}}}_{n}\right\|}_{2}\leq
n\lambda_{1}^{r}$.

Now, for $\gamma=\frac{1}{n\lambda^{r}}$, when $n$ is sufficiently large it is
less than $\frac{2}{\tilde{\lambda}_{\max}+\tilde{\lambda}_{\min}}$, because
$\beta_{n}=o(1)$. Thus,
${\left\|{\bm{I}}_{n+m}-\gamma{\bm{R}}\right\|}_{2}\leq
1-\frac{\tilde{\lambda}_{\min}}{n\lambda^{r}}\leq
1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}$. Thus, we have

$\|{\bm{u}}_{t}\|_{2}\leq{\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}^{t}\frac{\lambda^{r}}{\beta_{n}\rho_{\min}}\|{\bm{y}}\|_{2}.$

The second part of this proof is to bound
$\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})\|_{2}$. Let us return to Eqn.
21, which says that

$\displaystyle{\left\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t+1})\right\|}_{2}$
$\displaystyle={\left\|{\left({\bm{I}}_{n+m}-\gamma
n\beta_{n}{\bm{Q}}\right)}{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})-\gamma{\bm{Q}}{\bm{u}}_{t}\right\|}_{2}$
$\displaystyle\leq{\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}{\left\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})\right\|}_{2}+\frac{\rho_{\max}}{n\lambda^{r}}\|{\bm{u}}_{t}\|_{2}.$

Here again, we assume that $n$ is large enough so that
$\lambda^{r}>\beta_{n}\rho_{\min}$. This implies that

$\displaystyle{\left\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t+1})\right\|}_{2}-t{\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}^{t}\frac{\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}\rho_{\min}}$
$\displaystyle\leq\;$
$\displaystyle{\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}{\left[{\left\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})\right\|}_{2}-(t-1){\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}^{t-1}\frac{\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}\rho_{\min}}\right]}$
$\displaystyle\leq\;$
$\displaystyle\cdots\leq{\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}^{t}{\left[{\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}+\frac{\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}\rho_{\min}}\right]}.$

Thus, there is
${\left\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})\right\|}_{2}\leq{\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}^{t}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}+t{\left(1-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\right)}^{t-1}\frac{\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}\rho_{\min}}$.
Using $1-x\leq e^{-x}$, we have

${\left\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})\right\|}_{2}\leq\exp{\left(-\frac{\beta_{n}\rho_{\min}t}{\lambda^{r}}\right)}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}+t\exp{\left(-\frac{\beta_{n}\rho_{\min}(t-1)}{\lambda^{r}}\right)}\frac{\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}\rho_{\min}}.$

When
$t=t_{0}:=\frac{4\lambda^{r}}{\beta_{n}\rho_{\min}}\log\frac{2\lambda^{r}\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}^{2}\rho_{\min}^{2}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}}$,
by $\log(2x)\leq x$ for $x>0$, we have

$\exp{\left(\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}\frac{t}{2}\right)}\geq{\left(\frac{2\lambda^{r}\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}^{2}\rho_{\min}^{2}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}}\right)}^{2}\geq\frac{4\lambda^{r}\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}^{2}\rho_{\min}^{2}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}}\log{\left(\frac{2\lambda^{r}\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}^{2}\rho_{\min}^{2}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}}\right)}.$

Let
$F(t):=\exp{\left(\frac{\beta_{n}\rho_{\min}}{2\lambda^{r}}t\right)}-\frac{\rho_{\max}\|{\bm{y}}\|_{2}}{n\beta_{n}\rho_{\min}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}}t$.
Then we have $F(t_{0})\geq 0$. And it is easy to show that for all
$t\geq\frac{t_{0}}{2}$, there is $F^{\prime}(t)\geq 0$. This means that when
$t\geq t_{0}$, there is $F(t)\geq 0$, so we have

${\left\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})\right\|}_{2}\leq\exp{\left(-\frac{\beta_{n}\rho_{\min}t}{\lambda^{r}}\right)}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}+\exp{\left(-\frac{\beta_{n}\rho_{\min}}{\lambda^{r}}{\left(\frac{t}{2}-1\right)}\right)}\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}.$

Hence, when
$t\geq\max{\left\\{\frac{2\lambda^{r}}{\beta_{n}\rho_{\min}}\log\frac{2}{\epsilon}+2,t_{0}\right\\}}$,
we have
${\left\|{\bm{Q}}({\bm{\theta}}_{*}-{\bm{\theta}}_{t})\right\|}_{2}\leq\epsilon\|{\bm{Q}}{\bm{\theta}}_{*}\|_{2}$,
which implies that the relative estimation error of $\hat{{\bm{\alpha}}}$ is
less than $\epsilon$. ∎

##  Appendix D Experiments

The purpose of our experiments is threefold:

  1. (i)

Verify that STKR-Prop (Algorithms 1 and 2) works with general polynomial
$s(\lambda)$ including inverse Laplacian under transductive and inductive
settings on real datasets, and compare them to label propagation (for the
transductive setting).

  2. (ii)

Explore possible reasons why canonical Laplacian works so well empirically, by
examining the effect of $p$ on the performance when using STKR with
$s(\lambda)=\lambda^{p}$.

  3. (iii)

Verify that STKR-Prop works with kernel PCA on real datasets, and compare it
to other methods.

###  D.1 Setup

##### Datasets.

We focus on graph node classification tasks, and work with the publicly
available datasets in the PyTorch Geometric library (Fey & Lenssen, 2019),
among which Cora, CiteSeer and PubMed are based on Yang et al. (2016);
Computers, Photos, CS and Physics are based on Shchur et al. (2018); DBLP and
CoraFull are based on Bojchevski & Günnemann (2018). See Table 3 for a summary
of the dataset statistics.

##### Train/val/test/other splits.

We split a dataset into four sets: train, validation (val), test and other.
Among them, train and val contain labeled samples, while test and other
contain unlabeled samples. The test performance which we will report later is
only evaluated on the test set. The val set is used to select the best model,
so it is used in a similar way as the test set as explained below:

  * •

In the transductive setting, the learner can see all four sets at train time.
The learner manually hides the labels of the samples in the val set (so that
the val performance approximates the test performance). Thus, $n$ is the size
of the train set, while $m$ is the size of the other three combined.

  * •

In the inductive setting, the learner can see train, val and other, but not
test. Neither can it see any edges connected to test nodes. Then, the learner
manually hides the entire val set (nodes, outcoming edges and labels), so that
the val performance approximates the test performance. Thus, $n$ is the size
of the train set, while $m$ is the size of the other set.

In all our experiments, these four sets are randomly split. This means that
with the same random seed, the four splits are exactly the same; With a
different random seed, the four splits are different, but their sizes are kept
the same for the same dataset.

##### Sizes of the splits.

First, we specify a hyperparameter $p_{\text{test}}$, and then
$p_{\text{test}}$ of all the samples will be in the test set. For Cora,
CiteSeer and PubMed, we use the default train/validation/test split size, and
from the test set we take out $p_{\text{test}}\times$ #(all samples) of the
samples to be the real test set, and the rest of the samples go to the other
set. For the other six datasets, we set the train and validation set size to
be $20\times$ number of classes. For example, the Physics dataset has 5
classes, so we randomly sample $100$ samples to be train data, and another
$100$ samples to be validation data. We also do an ablation study for
$p_{\text{test}}$ in our experiments, where $p_{\text{test}}$ could range from
1% to 50%.

Table 3: Number of classes, nodes, edges, and fractions (%) of train and validation sets. | Classes | Nodes | Edges | Train | Validation
---|---|---|---|---|---
Cora | 7 | 2,708 | 10,556 | 5.17 | 18.46
CiteSeer | 6 | 3,327 | 9,104 | 3.61 | 15.03
PubMed | 3 | 19,717 | 88,648 | 0.3 | 2.54
Amazon - Computers | 10 | 13,752 | 491,722 | 1.45 | 1.45
Amazon - Photos | 8 | 7,650 | 238,162 | 2.09 | 2.09
Coauthor - CS | 15 | 18,333 | 163,788 | 1.64 | 1.64
Coauthor - Physics | 5 | 34,493 | 495,924 | 0.29 | 0.29
DBLP | 4 | 17,716 | 105,734 | 0.45 | 0.45
CoraFull | 70 | 19,793 | 126,842 | 7.07 | 7.07

##### Implementations.

For label propagation, we use the version in Zhou et al. (2003), which solves:

$({\bm{I}}_{n+m}-\eta{\bm{S}})\hat{{\bm{y}}}=\tilde{{\bm{y}}},\qquad\text{where
}\tilde{{\bm{y}}}:=[{\bm{y}},{\bm{0}}_{m}]^{\top}.$ (22)

Here $\hat{{\bm{y}}}$ is the predicted labels for all $n+m$ samples under the
transductive setting, and ${\bm{S}}$ is defined as
${\bm{S}}:={\bm{D}}^{-\frac{1}{2}}{\bm{W}}{\bm{D}}^{-\frac{1}{2}}$, where
${\bm{W}}$ is the adjacency matrix such that ${\bm{W}}[i,j]=1$ if $x_{i}$ is
connected to $x_{j}$ and 0 otherwise, and ${\bm{D}}$ is a diagonal matrix
defined as ${\bm{D}}[i,i]=\sum_{j=1}^{n+m}{\bm{W}}[i,j]$ for $i\in[n+m]$. For
STKR, we define the base kernel $K$ as:

$K(x,x^{\prime})=(n+m)\frac{W(x,x^{\prime})}{\sqrt{D(x)D(x^{\prime})}},$ (23)

where $W(x_{i},x_{j})={\bm{W}}[i,j]$, and for the transductive setting there
is $D(x_{i})={\bm{D}}[i,i]$, so that ${\bm{S}}=\frac{{\bm{G}}_{K}}{n+m}$. For
the inductive setting, $D(x_{i})=\sum_{j\notin\text{test
nodes}}W(x_{i},x_{j})$ for all $i\in[n+m]$, i.e. the sum is only taken over
the visible nodes at train time.

##### Hyperparameters.

Below are the hyperparameters we use in the experiments. Best hyperparameters
are selected with the validation split as detailed above.

  * •

Label Propagation

    * –

Number of iteration $T\in[1,2,4,8,16,32]$

    * –

$\eta\in[0.7,0.8,0.9,0.99,0.999,0.9999,0.99999,0.999999]$

  * •

STKR transductive

    * –

Number of iteration $T\in[1,2,4,8,16,32]$

    * –

Laplacian $s^{-1}(\lambda)=\lambda^{-1}-\eta$:
$\eta\in[0.7,0.8,0.9,0.99,0.999,0.9999,0.99999,0.999999]$

    * –

Polynomial $s(\lambda)=\lambda^{k}$: $k\in[1,2,4,6,8]$

    * –

$\beta\in[10^{3},10^{2},10^{1},10^{0},10^{-1},10^{-2},10^{-3},10^{-4},10^{-5},10^{-6},10^{-7},10^{-8}]$

  * •

STKR inductive

    * –

Laplacian $s^{-1}(\lambda)=\lambda^{-1}-\eta$:
$\eta\in[0.7,0.8,0.9,0.99,0.999,0.9999,0.99999,0.999999]$

    * –

Polynomial $s(\lambda)=\lambda^{k}$: $k\in[1,2,4,6,8]$

    * –

$\beta\in[10^{3},10^{2},10^{1},10^{0},10^{-1},10^{-2},10^{-3},10^{-4},10^{-5},10^{-6},10^{-7},10^{-8}]$

  * •

Kernel PCA

    * –

Number of representation dimension $d\in[32,64,128,256,512]$

    * –

$\beta\in[10^{3},10^{2},10^{1},10^{0},10^{-1},10^{-2},10^{-3},10^{-4},10^{-5},10^{-6},10^{-7},10^{-8}]$

###  D.2 Results

We report the test accuracy of STKR-Prop with different transformations and
the Label-Prop algorithm in Table 4. To make a fair comparison between the
transductive and inductive setting, we report the test accuracy on the same
$p_{\text{test}}=0.01$ fraction of the data (for the same random seed). This
is a part of the unlabeled data in the transductive setting, but is completely
hidden from the learner in the inductive setting at train time.

First, our results show that STKR-Prop can work pretty well with a general
$s(\lambda)$ under the inductive setting. The drops in the accuracy of the
inductive STKR-Prop compared to transductive are small. In Table 5, we further
provide an ablation on the test accuracy as we increase $p_{\text{test}}$. As
$p_{\text{test}}$ is larger, the performance of inductive STKR decreases
across the board. Nevertheless, there are many datasets such as Photo,
Physics, Computer where the performance drop is fairly small — at around $2-3$
percent even when $p_{\text{test}}=0.3$. Our ablation study shows that
inductive STKR is quite robust to the number of available unlabeled data at
the training time. Our experiment clearly demonstrates that one can implement
STKR with a general transformation such as $s(\lambda)=\lambda^{p}$
efficiently. The running time of STKR-Prop is similar to that of Label-Prop
with the same number of iterations.

Table 4: The test accuracy (%) of Label-Prop (LP), STKR-Prop (SP) with inverse
Laplacian (Lap), with polynomial $s(\lambda)=\lambda^{8}$ (poly), with kernel
PCA (topd), and with $s(\lambda)=\lambda$ (KRR). (t) and (i) indicate the
transductive and inductive settings. We report the test accuracy when
$p_{\text{test}}=0.01$, i.e. test samples account for 1% of all samples.
Standard deviations are given across ten random seeds. The best and second-
best results for each dataset are marked in red and blue, respectively.

| CS | CiteSeer | Computers | Cora | CoraFull | DBLP | Photo | Physics | PubMed
---|---|---|---|---|---|---|---|---|---
LP (t) | $79.07_{2.19}$ | $52.73_{7.72}$ | $77.30_{3.05}$ | $73.33_{6.00}$ | $54.47_{3.24}$ | $66.44_{3.78}$ | $83.95_{5.78}$ | $84.33_{4.86}$ | $72.28_{5.55}$
SP-Lap (t) | $78.96_{2.53}$ | $52.12_{7.67}$ | $77.81_{3.94}$ | $77.04_{5.74}$ | $53.81_{2.34}$ | $65.42_{5.02}$ | $84.08_{6.52}$ | $84.22_{4.86}$ | $71.93_{4.86}$
SP-poly (t) | $79.13_{2.29}$ | $48.79_{8.51}$ | $76.72_{4.12}$ | $71.48_{5.80}$ | $53.25_{3.54}$ | $64.52_{4.20}$ | $79.21_{7.20}$ | $84.45_{4.89}$ | $72.18_{4.66}$
SP-topd (t) | $78.80_{3.22}$ | $46.06_{1.08}$ | $80.80_{3.06}$ | $69.26_{7.82}$ | $50.36_{2.85}$ | $64.86_{4.60}$ | $84.61_{6.30}$ | $83.20_{2.25}$ | $65.38_{5.66}$
SP-Lap (i) | $78.42_{2.81}$ | $46.06_{6.97}$ | $77.15_{2.64}$ | $67.78_{7.62}$ | $53.30_{3.24}$ | $65.20_{4.92}$ | $84.87_{5.66}$ | $83.11_{5.09}$ | $70.36_{4.80}$
SP-poly (i) | ${79.02}_{2.42}$ | ${44.55}_{9.15}$ | ${71.97}_{4.13}$ | ${65.19}_{9.11}$ | ${51.98}_{3.88}$ | ${64.52}_{4.05}$ | ${78.42}_{7.80}$ | ${84.68}_{4.83}$ | ${70.76}_{4.28}$
SP-topd (i) | $79.13_{3.35}$ | $41.52_{6.71}$ | $80.80_{3.28}$ | $63.70_{6.00}$ | $47.41_{3.39}$ | $63.16_{3.41}$ | $85.53_{5.68}$ | $82.44_{3.88}$ | $64.31_{4.95}$
KRR (i) | $13.11_{2.29}$ | $13.64_{5.93}$ | $26.35_{4.34}$ | $28.52_{8.56}$ | $19.80_{2.22}$ | $44.80_{3.86}$ | $33.95_{7.07}$ | $19.74_{1.46}$ | $20.76_{2.06}$

Second, we explore the impact of the “number of hop” $p$ on the performance of
STKR with $s(\lambda)=\lambda^{p}$ (Figure 2). We consider
$p\in\\{1,2,4,6,8\\}$, and note that for $p=1$, this STKR is equivalent to
performing a KRR with the base kernel. As we have already seen in Table 4, the
performance of such KRR is extremely poor compared to the other methods. This
is consistent with our analysis in Section 2 that KRR with the base kernel is
not sufficient. We find that by increasing $p$ which in turns increase the
additional smoothness requirement, the performance of STKR increases by a
large margin for all datasets. This clearly illustrates the benefits of the
transitivity of similarity, and offers a possible explanation why the inverse
Laplacian transformation performs so well in practice: It uses multi-hop
similarity information up to infinitely many hops.

Third, the results show that STKR also works pretty well with kernel PCA.
Comparing between kernel PCA and LP (or STKR with inverse Laplacian), on 3 of
the 9 datasets we use, the former is better. Thus, this experiment clearly
demonstrates the parallel nature of these two methodologies — STKR with
inverse Laplacian, and kernel PCA.

Figure 2: Test accuracy (%) of STKR-Prop (SP) with polynomial with
$s(\lambda)=\lambda^{p}$ for $p\in\\{1,2,4,6,8\\}$. The test accuracy
increases significantly as $p$ is larger than $1$, illustrating the benefits
of the transitivity of similarity.  Table 5: Test accuracy (%) of STKR-Prop
(SP) with inverse Laplacian (Lap), with polynomial $s(\lambda)=\lambda^{8}$
(poly) and with kernel PCA (topd) for inductive setting with different value
of $p_{\text{test}}{\in\\{0.01,0.05,0.1,0.2,0.3\\}.}$ Standard deviations are
given across ten random seeds.

Methods | $p_{\text{test}}$ | CS | CiteSeer | Computers | Cora | CoraFull | DBLP | Photo | Physics | PubMed
---|---|---|---|---|---|---|---|---|---|---
| $0.01$ | $78.42_{2.81}$ | $46.06_{6.97}$ | $77.15_{2.64}$ | $67.78_{7.62}$ | $53.30_{3.24}$ | $65.20_{4.92}$ | $84.87_{5.66}$ | $83.11_{5.09}$ | $70.36_{4.80}$
| $0.05$ | $77.93_{1.41}$ | $41.75_{4.82}$ | $77.42_{2.25}$ | $62.37_{3.66}$ | $51.63_{0.90}$ | $65.57_{2.52}$ | $84.90_{2.50}$ | $82.72_{4.26}$ | $67.81_{3.56}$
SP-Lap | $0.1$ | $76.45_{1.17}$ | $39.97_{2.68}$ | $77.40_{1.88}$ | $59.74_{2.37}$ | $50.22_{0.75}$ | $65.34_{2.09}$ | $84.10_{1.84}$ | $82.02_{4.01}$ | $66.43_{3.62}$
| $0.2$ | $75.06_{1.01}$ | $35.50_{1.94}$ | $77.18_{2.03}$ | $55.10_{2.92}$ | $47.84_{0.79}$ | $63.24_{1.96}$ | $83.81_{1.23}$ | $81.33_{3.59}$ | $63.77_{3.36}$
| $0.3$ | $72.89_{0.95}$ | $30.92_{1.14}$ | $76.59_{1.71}$ | $50.22_{2.87}$ | $44.96_{0.77}$ | $60.44_{1.68}$ | $83.28_{1.11}$ | $80.27_{3.45}$ | $60.25_{2.75}$
| $0.01$ | ${79.13}_{3.35}$ | ${44.55}_{9.15}$ | ${71.97}_{4.13}$ | ${65.19}_{9.11}$ | ${51.98}_{3.88}$ | ${64.52}_{4.05}$ | ${78.42}_{7.80}$ | ${84.68}_{4.83}$ | ${70.76}_{4.28}$
| $0.05$ | ${78.74}_{1.42}$ | ${40.36}_{5.51}$ | ${73.04}_{1.80}$ | ${61.85}_{4.15}$ | ${50.21}_{1.69}$ | ${64.64}_{2.07}$ | ${79.03}_{4.61}$ | ${84.05}_{3.99}$ | ${67.68}_{2.91}$
SP-poly | $0.1$ | ${77.51}_{1.03}$ | ${38.58}_{2.90}$ | ${73.10}_{1.58}$ | ${58.56}_{2.59}$ | ${49.06}_{0.90}$ | ${64.21}_{1.93}$ | ${78.59}_{4.49}$ | ${83.13}_{3.69}$ | ${66.08}_{2.96}$
| $0.2$ | ${75.74}_{1.02}$ | ${33.65}_{1.78}$ | ${72.70}_{1.84}$ | ${53.11}_{2.39}$ | ${46.53}_{0.79}$ | ${61.89}_{2.03}$ | ${78.82}_{3.05}$ | ${82.36}_{3.27}$ | ${62.97}_{3.10}$
| $0.3$ | ${73.35}_{0.76}$ | ${28.98}_{1.21}$ | ${72.35}_{1.60}$ | ${47.99}_{2.62}$ | ${43.42}_{0.78}$ | ${59.55}_{2.02}$ | ${78.20}_{2.73}$ | ${81.08}_{3.25}$ | ${59.32}_{2.57}$
| $0.01$ | $79.13_{3.35}$ | $41.52_{6.71}$ | $80.80_{3.28}$ | $63.70_{6.00}$ | $47.41_{3.39}$ | $63.16_{3.41}$ | $85.53_{5.68}$ | $82.44_{3.88}$ | $64.31_{4.95}$
| $0.05$ | $78.37_{1.58}$ | $40.00_{5.14}$ | $80.17_{2.30}$ | $61.70_{3.53}$ | $47.17_{1.63}$ | $62.79_{3.36}$ | $85.47_{2.07}$ | $82.26_{1.88}$ | $62.79_{3.28}$
SP-topd | $0.1$ | $77.17_{1.02}$ | $38.67_{4.17}$ | $79.35_{2.57}$ | $58.81_{3.26}$ | $45.22_{0.89}$ | $61.51_{2.60}$ | $84.85_{1.70}$ | $80.59_{1.86}$ | $61.75_{2.26}$
| $0.2$ | $75.61_{0.64}$ | $35.10_{2.64}$ | $79.00_{2.02}$ | $55.51_{4.21}$ | $42.31_{0.91}$ | $60.30_{2.60}$ | $84.63_{1.45}$ | $80.15_{1.86}$ | $59.60_{3.22}$
| $0.3$ | $72.59_{0.70}$ | $32.92_{1.92}$ | $78.09_{1.27}$ | $51.71_{4.39}$ | $38.62_{0.79}$ | $59.18_{2.29}$ | $83.91_{1.69}$ | $79.07_{2.33}$ | $57.50_{2.50}$

Finally, we provide an ablation study about the effect of $\eta$ in inverse
Laplacian on the performance of SP-Lap. Recall that for inverse Laplacian we
have $s^{-1}(\lambda)=\lambda^{-1}-\eta$. Our observation is that when $\eta$
is very close to $0$, the performance is low; once it is bounded away from
$0$, the performance is fairly consistent, and gets slightly better with a
larger $\eta$. Only on dataset CS do we observe a significant performance
boost as $\eta$ increases.

Figure 3: Test accuracy of SP-Lap with different values of $\eta$. The test
accuracy is fairly consistent as long as $\eta$ is not too close to 0, and
gets slightly better with a larger $\eta$. All reported performances are
averaged across ten random seeds.


# Towards Goal, Feasibility, and Diversity-Oriented Deep Generative Models in
Design

Lyle Regenwetter  Deparment of Mechanical Engineering
Massachussetts Institute of Technology
<EMAIL_ADDRESS>Faez Ahmed  Deparment of Mechanical Engineering
Massachussetts Institute of Technology
<EMAIL_ADDRESS>
##  I abstract

Deep Generative Machine Learning Models (DGMs) have been growing in popularity
across the design community thanks to their ability to learn and mimic complex
data distributions. DGMs are conventionally trained to minimize statistical
divergence between the distribution over generated data and distribution over
the dataset on which they are trained. While sufficient for the task of
generating “realistic” fake data, this objective is typically insufficient for
design synthesis tasks. Instead, design problems typically call for adherence
to design requirements, such as performance targets and constraints. Advancing
DGMs in engineering design requires new training objectives which promote
engineering design objectives. In this paper, we present the first Deep
Generative Model that simultaneously optimizes for performance, feasibility,
diversity, and target achievement. We benchmark performance of the proposed
method against several Deep Generative Models over eight evaluation metrics
that focus on feasibility, diversity, and satisfaction of design performance
targets. Methods are tested on a challenging multi-objective bicycle frame
design problem with skewed, multimodal data of different datatypes. The
proposed framework was found to outperform all Deep Generative Models in six
of eight metrics.

##  II Introduction

Automatically creating innovative designs that outperform all existing
solutions and meet complex real-world engineering constraints is the holy
grail of data-driven engineering design. This is an incredibly demanding task
and current design automation tools remain insufficient for full autonomy in
product design. Recently, Deep Generative Models (DGMs) have emerged as a
viable means to bridge the gap to this overarching design automation goal.
DGMs, such as Generative Adversarial Networks and Variational Autoencoders,
are typically trained to minimize the statistical divergence (or maximize
similarity) between distributions of generated samples and the underlying data
distribution. In engineering design, design objectives and constraints make
statistical similarity metrics insufficient and sometimes inappropriate.
Despite this, an overwhelming majority of research in engineering design
continues to optimize and evaluate methods using statistical similarity. We
believe the continuation of this practice is rooted in two central challenges.
Firstly, appropriate metrics to evaluate DGMs on engineering objectives such
as design performance, feasibility, and achievement of design requirements are
poorly established. Secondly, researchers lack effective methods to build
these auxiliary objectives into training procedures and instead fall back upon
the established structural similarity as the central training mechanism. This
paper presents our proposed solution to the aforementioned challenges. Our key
contributions are summarized as follows:

  1. 1.

We introduce the Design Target Achievement Index (DTAI), a differentiable loss
function which allows Deep Generative Models to prioritize, meet, and exceed
multi-objective performance targets specified by a designer.

  2. 2.

We introduce the first Deep Generative Model that simultaneously optimizes for
design performance, diversity, feasibility, and target satisfaction. We
demonstrate that our specialized loss function yields significant performance
improvements, such as increasing the average proportion of design targets met
by 45% and the proportion of feasible designs by 30% versus state-of-the-art
tabular generation methods.

  3. 3.

We demonstrate that the proposed framework outperforms GANs, Conditional
Tabular GANs, and Multi-Objective Performance-aware Diverse GANs in six
evaluation metrics tested.

##  III Review of Deep Generative Models in Engineering Design

In a recent review of Deep Generative Models (DGMs), Regenwetter et al. [1]
discuss the application of DGMs across engineering design fields and analyze
key limitations in the current state-of-the-art in DGM methodology. For a more
detailed review and discussion, we refer the reader to [1]. The authors
suggest that successfully addressing several key challenges will be essential
in the continued development of DGMs for engineering design. Four of these
challenges are design performance, design novelty, more robust design
representation methods, and targeted inverse design.

Design performance (quality) may be comprised of many diverse (and sometimes
competing) objectives, such as weight, cost, aerodynamics, etc. Several
approaches to incorporate design performance into DGMs have been proposed: 1)
Building performance-estimating objectives into the training function [2, 3];
2) Iteratively training the DGM on datasets augmented with high-performing
generated designs [4, 5]; 3) Optimizing latent vectors using a fitting
surrogate model [6, 7]. Despite this, existing DGMs in engineering design lack
any mechanism to condition design generation toward a specific set of
designer-specified performance targets. Our proposed framework uses an
auxiliary loss (approach #1) that considers performance, target achievement,
diversity, and feasibility of generated designs in a single aggregate score.

##  IV Methodology

To construct a loss function that considers performance, target achievement,
diversity, and feasibility, we first propose an aggregate performance score
that considers a design’s adherence to designer-specified design performance
targets. We then augment this score with a feasibility likelihood for a
feasibility-weighted performance score. Finally, we scale these feasibility-
weighted performance scores with diversity scores and compute a final loss
using a Determinantal Point Process, as proposed in [2]. This loss is appended
to the loss function of a Deep Generative Model. In our testing, we use a
Generative Adversarial Network. The overall pipeline is shown in Figure 1.
Below, we discuss how the various scores are calculated.

Figure 1: Proposed Performance, Feasibility, and Diversity-Aware DGM

###  IV-A Aggregate Performance Score

To quantify how well a design adheres to designer-specified performance
targets, we propose a novel training loss called the Design Target Achievement
Index (DTAI) in [8]. We provide an overview of the loss here, but refer
readers to the original paper for more details. Consider a design, $i$, and
its performance $p_{i,k}$ with respect to a particular performance target,
$t_{k}$, for $k\in\\{1...T\\}$ where $T$ is the number of design objectives
(i.e. weight, safety factor, etc.). In any given objective, $k$, we desire our
design’s performance to exceed the performance target: $p_{i,k}\geq t_{k}$.
When our design’s performance exceeds the target, we have
$r_{i,k}=\frac{p_{i,k}}{t_{k}}\geq 1$. We propose the following piecewise
scoring function to compute an individual target achievement score, $s_{i,k}$
in terms of $r_{i,k}$. This function is parameterized by two tuning factors,
$\alpha_{k}$ and $\beta_{k}$, which adjust the steepness of the curve
(importance of the objective) and the decay once the target is exceeded (how
valuable improvement beyond the target is for this objective). Figure 2 shows
the effect of adjusting $\alpha_{k}$ and $\beta_{k}$.

$s_{i,k}=\begin{cases}\alpha_{k}(1-r_{i,k})&r_{i,k}\leq 1\\\
\frac{\alpha_{k}}{\beta_{k}}(1-e^{\beta_{k}(1-r_{i,k})})&r_{i,k}>1\end{cases}$
(1)

Figure 2: The $\alpha$ parameter adjusts the steepness of the Design Target
Achievement Index (DTAI) curve, while the $\beta$ parameter adjusts how
steeply it falls off after the target is exceeded.

The individual scores $s_{i,k}$ for each objective are summed into an
aggregate score, then scaled by the minimum and maximum values for the sum,
$s_{min}$ and $s_{max}$, which can be easily derived. This final result is our
proposed Design Target Achievement Index, $s_{DTAI}$.

$s_{DTAI,i}=\frac{(\sum_{k=1}^{n}s_{i,k})-s_{min}}{s_{max}-s_{min}}$ (2)
$s_{min}=-\sum_{k=1}^{T}\alpha_{k},\,\,\,s_{max}=\sum_{k=1}^{T}\frac{\alpha_{k}}{\beta_{k}}$
(3)

DTAI has many desirable properties: DTAI’s derivative with respect to an
individual objective is large when a design is currently underperforming the
objective’s performance target but exponentially decays as the design
outperforms the target. DTAI is differentiable across the entire space of
possible performance and constraint values and its derivative is continuous.
Both DTAI and its derivative are bounded. DTAI’s computational cost scales
linearly with the number of design objectives. Finally, DTAI’s $\alpha$ and
$\beta$ parameters enable easy and precise customization by the designer.

Since DTAI is used as a trianing loss, performance estimates must be
differentiable. In the example application, we pretrain a supervised regressor
to estimate performance for generated designs.

###  IV-B Feasibility-Weighted Performance Scores

DGMs in engineering design often struggle with physical infeasibility of
generated designs (conflicting geometry, negative distances, etc.). Just as we
train a surrogate model to predict performance of generated designs, we can
also predict their feasibility using a pretrained supervised classifier. Given
predicted feasibility likelihood for a generated design, we multiply its
aggregate performance score with its feasibility likelihood for a feasibility-
weighted performance score.

###  IV-C Diversity, Feasibility, and Performance Loss

Chen & Ahmed [2] propose a method to incorporate performance and diversity
into DGM training using a weighted similarity matrix calculated with a
similarity kernel and a Determinantal Point Process (DPP). We borrow the
proposed approach, calculating a similarity matrix, which we scale using
feasibility-weighted performance scores and a hyperparameter that modulates
the imporatnce of diversity versus performance. The final diversity,
feasibility, and performance loss is calculated using a DPP and appended to
the DGM’s standard training loss.

##  V Experimental Results

###  V-A Dataset

For this study, we select the recently-introduced FRAMED dataset [9], which
consists of 4500 community-designed bicycle frame models [10], parameterized
over 37 design variables (tube dimensions, frame material, etc). The FRAMED
dataset provides a set of ten structural performance measures for each frame
(weight, deflections, etc.). For testing, we select a demanding set of
performance targets equal to the $75^{th}$ percentile performance scores from
the dataset in each objective.

###  V-B Benchmark Models

We benchmark our proposed framework against several baselines. The simplest of
these are random sampling from the dataset and random interpolation between
dataset models. We also benchmark a vanilla GAN and a Conditional Tabular GAN
(CTGAN) proposed in [11], which do not consider performance, diversity,
feasibility or target achievement. Finally, we benchmark a Multi-Objective
Performance-Aware Diverse GAN (MO-PaDGAN), as proposed in [3], which considers
performance and diversity, but not feasibility or target achievement. When
introduced, MO-PaDGAN improved multi-objective performance for aerodynamic
synthesis by 186% compared to a standard GAN, and thus constitutes a strong
model for comparison.

###  V-C Results

Table I shows the results of our testing. All in all, the proposed framework
achieves superior performance in all evaluation metrics except diversity over
all other Deep Generative Models tested. While diversity scores are modest,
diversity can be prioritized using the diversity modulation hyperparameter, if
desired. The framework boasts a $95.9\%$ feasibility rate among generated
designs over average the average $72.7\%$ across the baseline DGMs.
Furthermore, it attains an average of $69.8\%$ of design targets as compared
to an average of $33.8\%$ across baseline DGMs. Figure 3 presents violin plots
of the distribution of Design Target Achievement Index and Target Success Rate
over the space of generated designs for baseline methods. A continuous
distribution is approximated over the 250 designs generated by each method
using a Kernel Density Estimate (KDE). The proposed framework is shown to
consistently outperform competing methods across distributions of generated
samples in target achievement and aggregate performance.

TABLE I: Deep Generative Models scored on the six proposed evaluation metrics.
Models from left to right: Randomly sampled design subsets from the FRAMED
dataset (Dataset), Random Interpolation between FRAMED designs
(Interpolation), Vanilla GAN (GAN), Conditional Tabular GAN (CTGAN), Proposed
PaDGAN with DTAI and auxiliary Geometric Feasibility Classifier (Proposed)

| Dataset | Interpolation |  | GAN
---
(2014)
| CTGAN
---
(2019)
| MO-PaDGAN
---
(2020)
Proposed (2022)
Mean Target Success Rate (TSR) (%) | 24 | 31.3 | 28.6 | 24.4 | 48.4 | 69.8
Feasibility Rate (GFR) (%) | 100 | 100 | 65.2 | 65.7 | 87.1 | 95.9
Mean Design Target Achievement Index (DTAI) | 0.53 | 0.58 | 0.71 | 0.52 | 0.69 | 0.79
Mean Minimum Target Ratio (MTR) | 0.32 | 0.37 | 0.41 | 0.32 | 0.42 | 0.43
Hypervolume (HV) *10^-7 | 4.81 | 4 | 3.04 | 3.54 | 2.95 | 3.82
Mean Design Novelty (DN) | 0 | 7.17 | 8.3 | 8.02 | 9.94 | 9.96
Mean Design Space Diversity | 8.6 | 13.28 | 10.08 | 14.12 | 7.11 | 9.48
Mean Performance Space Diversity (PSD) | 3.8 | 3.4 | 2.71 | 3.95 | 2.62 | 2.71

Figure 3: Violin plots demonstrate that the distribution of designs
synthesized the proposed method tend toward significantly higher performance
and target success rate compared to distributions of designs synthesized by
baseline models.

###  V-D Ablation Study

The ablation study shown in Table II contrasts the proposed PaDGAN with DTAI
and auxiliary classifier against variants without the classifier (-CLF) and
using MO-PaDGAN’s random objective weighting instead of DTAI (-DTAI). We note
that the configuration without the classifier and using MO-PaDGAN’s random
objective weighting is equivalent to the previous state-of-the-art MO-PaDGAN
(-DTAI, -CLF). We outperform Mo-PaDGAN in every metric tested, with
significant improvements in feasibility (95.9% from 87.1%), DTAI (0.79 from
0.69), Target Success Rate (TSR) (69.8% from 48.4%), and Hypervolume
($3.82E-7$ from $2.95E-7$).

TABLE II: Ablation Study Contrasting Proposed PaDGAN with DTAI training loss
and auxiliary classifier against PaDGAN without DTAI (-DTAI), without the
auxiliary classifier (-CLF), and MO-PaDGAN (-DTAI, -CLF).

| Proposed | -DTAI | -CLF | -DTAI, -CLF
---|---|---|---|---
Mean Target Success Rate (%) | 69.8 | 67.7 | 51.4 | 48.4
Feasibility Rate (%) | 95.9 | 82.5 | 83.2 | 87.1
Mean Minimum Target Ratio | 0.43 | 0.51 | 0.46 | 0.42
Mean Design Target Achievement Index (DTAI) | 0.79 | 0.80 | 0.72 | 0.69
Hypervolume *10^(-7) | 3.82 | 3.82 | 3.40 | 2.95
Mean Design Novelty | 9.96 | 9.90 | 10.52 | 9.94
Mean Design Space Diversity | 9.48 | 6.21 | 5.80 | 7.11
Mean Performance Space Diversity | 2.71 | 2.24 | 2.44 | 2.62

##  VI Conclusion

We introduce a novel differentiable scoring metric called Design Target
Achievement Index (DTAI) which allows Deep Generative Models to prioritize,
meet, and exceed multi-objective performance targets. We augment a
Performance-Augmented Diverse GAN with our DTAI objective and demonstrate
significantly improved performance in design generation. We then further
augment this PaDGAN with an auxiliary classifier to encourage the generation
of feasible results. To benchmark our method, we evaluate a variety of Deep
Generative Models, including the Multi-Objective PaDGAN, and specialized
tabular generation algorithm, CTGAN. Methods are tested on a challenging
bicycle frame design problem with 10 performance objectives. The proposed
PaDGAN with DTAI loss and auxiliary classifier outperforms baseline DGMs in
every evaluation metric and further outperforms other PaDGAN variants in
ablation studies. All in all, this work establishes a novel Deep Generative
Framework that actively optimizes performance, diversity, feasibility, and
target satisfaction to establish a new state-of-the-art in design generation
using Deep Generative Models.

##  VII Acknowledgments

We would like to thank Amin Heyrani Nobari for creating the Tensorflow 2.x
version of PaDGAN which we modified to generate our results. We also
acknowledge MathWorks for supporting this research.

## References

  * [1] L. Regenwetter, A. H. Nobari, and F. Ahmed, “Deep generative models in engineering design: A review,” _arXiv preprint arXiv:2110.10863_ , 2021.
  * [2] W. Chen and F. Ahmed, “PaDGAN: Learning to generate high-quality novel designs,” _Journal of Mechanical Design_ , vol. 143, no. 3, p. 031703, 2021\.
  * [3] ——, “MO-PaDGAN: Reparameterizing engineering designs for augmented multi-objective optimization,” _Applied Soft Computing_ , vol. 113, p. 107909, 2021.
  * [4] S. Oh, Y. Jung, S. Kim, I. Lee, and N. Kang, “Deep generative design: Integration of topology optimization and generative models,” _Journal of Mechanical Design_ , vol. 141, no. 11, 2019.
  * [5] D. Shu, J. Cunningham, G. Stump, S. W. Miller, M. A. Yukish, T. W. Simpson, and C. S. Tucker, “3d design using generative adversarial networks and physics-based validation,” _Journal of Mechanical Design_ , vol. 142, no. 7, p. 071701, 2020.
  * [6] S. Rawat and M. H. Shen, “Application of adversarial networks for 3d structural topology optimization,” SAE Technical Paper, Tech. Rep., 2019.
  * [7] T. Guo, D. J. Lohan, R. Cang, M. Y. Ren, and J. T. Allison, “An indirect design representation for topology optimization using variational autoencoder and style transfer,” in _2018 AIAA/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference_ , 2018, p. 0804.
  * [8] L. Regenwetter and F. Ahmed, “Design target achievement index: A differentiable metric to enhance deep generative models in multi-objective inverse design,” _arXiv preprint arXiv:2205.03005_ , 2022.
  * [9] L. Regenwetter, C. Weaver, and F. Ahmed, “FRAMED: Data-driven structural performance analysis of community-designed bicycle frames,” _arXiv preprint arXiv:2201.10459_ , 2022.
  * [10] L. Regenwetter, B. Curry, and F. Ahmed, “BIKED: A Dataset for Computational Bicycle Design With Machine Learning Benchmarks,” _Journal of Mechanical Design_ , vol. 144, no. 3, 10 2021, 031706. [Online]. Available: https://doi.org/10.1115/1.4052585
  * [11] L. Xu, M. Skoularidou, A. Cuesta-Infante, and K. Veeramachaneni, “Modeling tabular data using conditional gan,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.


New Strongly Regular Graphs Found via Local Search for Partial Difference Sets

Andrew C. Brady111University of Richmond, VA<EMAIL_ADDRESS>
Abstract Strongly regular graphs (SRGs) are highly symmetric combinatorial
objects, with connections to many areas of mathematics including finite
fields, finite geometries, and number theory. One can construct an SRG via the
Cayley Graph of a regular partial difference set (PDS). Local search is a
common class of search algorithm that iteratively adjusts a state to (locally)
minimize an error function. In this work, we use local search to find PDSs. We
found PDSs with 62 different parameter values in 1254 nonisomorphic groups of
orders at most 147. Many of these PDSs replicate known results. In two cases,
(144,52,16,20) and (147,66,25,33), the PDSs found give the first known
construction of SRGs with these parameters. In some other cases, the SRG was
already known but a PDS in that group was unknown. This work also corroborates
the existence of (64,18,2,6) PDSs in precisely 73 groups of order 64.

Keywords Partial Difference Set, Strongly Regular Graph, Local Search

##  1 Introduction

A graph is strongly regular if every vertex has degree $k$, every pair of
adjacent vertices has $\lambda$ common neighbors, and every pair of non-
adjacent vertices has $\mu$ common neighbors, for some
$k,\lambda,\mu\in\mathbb{Z}$. Some strongly regular graphs (SRGs) are
constructed from finite fields or finite geometries [6].

In this paper, we require that the SRG has a regular automorphism group. Let
$G$ be a group under multiplication and $1\in G$ be the identity of the group.
A subset $D\subset G$ is a partial difference set (PDS) if the set of
differences $\\{d_{1}d_{2}^{-1}|d_{1},d_{2}\in D\\}$ contains $\lambda$ copies
of every nonidentity element in $D$ and $\mu$ copies of every nonidentity
element not in $D$. PDSs are generalizations of difference sets and can be
used to create projective 2-weight error correcting codes [7]. Ma (1994) gives
a nice survey of PDSs and how they relate to many other geometric and
combinatorial objects [12]. Defining $D^{(-1)}:=\\{d^{-1}|d\in D\\}$, a
regular PDS is a subset $D\subset G$ such that D is a PDS, $1\not\in D$, and
$D=D^{(-1)}$. In this work, we require that our PDSs be regular, and
henceforth refer to regular PDSs as simply PDSs. Partial difference sets have
the additional interesting property that their Cayley Graph is strongly
regular [8]. Thus, by finding PDSs, we get an SRG for free. However, PDSs are
difficult to find because the search space is so large: naively, to find all
PDSs with parameters $(n,k,\lambda,\mu)$ in a group $G$ of order $n$ would
require checking all ${n\choose k}$ sets of size $k$. PDSs in nonabelian
groups are especially difficult to find, because many mathematical techniques
for finding PDSs function best in abelian groups. We attack the problem of
finding PDSs in any group using local search. Because local search is such a
flexible method, the techniques used in this paper could be adapted to search
for other types of combinatorial objects.

Local search is a class of search techniques that iteratively change a state
in order to minimize an error function. Metaphorically, if the error function
is a snowy mountain range, local search is choosing some starting location (a
state), then sledding down a hill (iterative improvement) to a valley (local
minimum). Advantages of local search include low space usage (because only the
current state is stored) and fast search speed. However, because local search
uses iterative improvement, local search can only find local minima of the
error function, so there is no guarantee of solution optimality. For more
information on local search, see chapter 4 of Russell and Norvig’s classic
textbook [16].

The main result of this paper is the following theorem:

######  Theorem 1.

There exist (144,52,16,20) and (147,66,25,33) SRGs.

###### Proof.

We show existence by explicit construction. In 1 we give PDSs with the desired
parameters. These PDSs are verifiable in GAP, C++, or by hand. As the Cayley
Graph of a PDS is strongly regular, we have constructed the desired SRGs. ∎

This paper is organized as follows. In Section 2, we discuss other approaches
to finding PDSs. In Section 3, we elaborate on the details of the local
search. In Section 4, we discuss the new PDSs found. In Section 5, we discuss
limitations and future directions of this work. Tables are displayed at the
end of the paper.

##  2 Related Work

To find new PDSs, one can rely on mathematical constructions or computational
search. Originally, most constructions of SRGs from PDSs came as consequences
of results from finite fields, finite geometries, projective codes, and other
mathematical structures [12]. The underlying group in this case would often be
abelian. More recently, Polhill, Davis, Smith, and Swartz (2023) constructed
genuinely nonabelian PDS families, which are PDS families in nonabelian groups
without a corresponding family in abelian groups [15]. They also recently
(2023) constructed PDS families in nonabelian groups by adapting techniques
used to construct PDSs in abelian groups [8].

On the computational side, for example, AbuGhneim, Peifer, and Smith (2019)
used computer search to construct all $(96,20,4,4)$ and $(96,19,2,4)$ PDSs
[1]. Peifer (2019) constructed difference sets in many small groups [14].
Jørgenson and Klin (2003) found various PDSs in groups of order 100 with the
aid of computational tools [11]. Brady (2022) exhaustively searched many
groups of order 64 for Negative Latin Square Type PDSs with dimensions
$(64,18,2,6)$ [4]. Previous computational searches have typically implemented
some theoretical mathematical restriction in order to reduce the search space
to find results exhaustively. The results in this paper are unusual in that no
restrictions are imposed on the target group: thus, this work is far more
flexible than prior research. To the author’s knowledge, local search has
never been used in published research to look for PDSs.

##  3 Methods

A state in our local search will be a single set $D$ of $k$ elements, and a
move will consist of replacing one element in $D$ (one swap). The local search
will be a basic hill climb, that moves to its first seen neighbor with lower
error. A single trial consists of choosing 1 initial starting state and
iteratively updating the state until convergence. To choose a swap, a random
element in $G\backslash\\{1\\}$ is chosen to replace a random element in $D$
(for $(n-1)k$ total possible swaps); however, the swap is automatically
invalid if the swap inserts an element already in $D$. We define convergence
to be $\alpha$ swaps in a row being invalid or failing to improve $D$, for
some fixed $\alpha$ we choose. Though most of our runs used $\alpha=(n-1)k-1$,
we recommend setting $\alpha=(n-1)k$, so that all neighbors of a state are
checked before the search gives up on a trial.

In the group ring $\mathbb{Z}[G]$, from our definition of PDS, it follows that
a subset $D$ of a group $G$ is a PDS with parameters
$(n:=|G|,k:=|D|,\lambda,\mu)$ if and only if we have that

$D:=\sum_{d\in D}d,G:=\sum_{g\in G}g,D^{2}=k(1)+\lambda
D+\mu(G\backslash(\\{1\\}\cup D)).$

For an element $\sum_{g\in G}c_{g}g\in\mathbb{Z}[G]$, define $l_{2}(\sum_{g\in
G}c_{g}g):=\sum_{g\in G}|c_{g}|^{2}$ and define
$\textrm{Diff}(D):=D^{2}-k(1)-\lambda D-\mu(G\backslash(\\{1\\}\cup D))$. We
define our error function to be

$e(D):=l_{2}(\textrm{Diff}(D)).$

Note that a set $D$ is an PDS iff $e(D)=0$. Also note that computing e(D)
without prior knowledge of $D^{2}$ takes $O(k^{2}+n)$ time, whereas updating
e(D) after changing a single element of D takes $O(k)$ time. Thus choosing a
swap as our state transition significantly speeds up our local search.

The convolution tables (also known as multiplication or group tables) for the
groups searched were generated with GAP [10]. For small group generation and
indexing we use the SmallGrp package [2]. These tables were then fed into C++,
where the search was implemented. The searches were performed in C++ because
C++ is a fast language. Randomness was generated using std::mt19937, a
Mersenne Twister.

Local search can be easily parallelized because it consists of many
independent tasks. If many groups and parameter sets are being searched, as in
4.2, one can run different groups on separate processors. If only one group is
being searched, as in 4.3, then independent trials can be run on separate
processors. The parallelized code was written with parlay, a C++ library for
writing parallel code [3]. Parlay was chosen for its simplicity and
effectiveness.

Runs were performed on two machines: the author’s laptop (Macbook Pro 2019,
32GB Memory, 2.6 GHz 6-Core Intel Core i7, Sonoma) and on Spydur, University
of Richmond’s HPC environment [13]. On Spydur, runs were performed on “basic”
nodes, which each contain 52 Xeon cores and 384GB of memory. Runs were
scheduled with SLURM; sequential runs were given 1 core and parallel runs were
typically given 40 cores.

##  4 Results

###  4.1 Recall of Local Search

What is the recall of local search using $N$ trials? That is, how many groups
with a known PDS will yield at least 1 PDS when doing $N$ trials of local
search? Dr. Ken Smith, in currently unpublished work, found exhaustively,
using a very different method, that precisely 73 groups of the 267
nonisomorphic groups of order 64 had (64,18,2,6) PDSs. As a proof of concept,
we repeated this search using local search with 10,000 trials. We found a PDS
in 73 groups, meaning that we got 100% recall in this case. These results
agree with Brady (2022) [4], which exhaustively found that, among groups with
SmallGrp Id 55-266 of order 64, exactly 49 had (64,18,2,6) PDSs. Thus, even
though local search is by nature not exhaustive, in small cases it can suggest
nonexistence of some PDSs.

###  4.2 New PDSs Found

All SRG dimensions with $n\leq 144$ were searched for PDSs in every group, as
well as SRG dimensions with $145\leq n\leq 215$ or $218\leq n\leq 238$, where
the existence of an SRG was unknown according to Brouwer’s table [5]. See
Table 2 for the maximum number of trials of local search run for each
parameter set. For each parameter set and group, trials were run until a PDS
was found or the maximum number of trials ran without finding a PDS. Thus, the
vast majority of trials were spent searching for PDSs in groups where they
likely do not exist. For example, only 130 trials were needed to generate a
(147,66,25,33) PDS in SmallGroup(147,4), but 43218 trials were spent failing
to find a (147,66,25,33) PDS in SmallGroup(147,5).

In total, PDSs with 62 different parameter values were found in 1254
nonisomorphic groups. Many of these PDSs replicate known results, but some are
new. See Table 1 for new SRGs found with this search and their associated PDSs
(the SRG is constructed by taking the Cayley graph of the given PDS). The
existence of the SRGs in Table 1 was open [5]. From De Winter, Kamischke, and
Wang we know that the (144,52,16,20) PDSs are genuinely nonabelian [9]. From
Theorem 3.4 in Ma’s PDS survey [12], we know that the (147,66,25,33) PDSs are
genuinely nonabelian.

Please refer to the Github (https://github.com/42ABC/PDS_local/) for the
complete list of PDSs, which includes PDSs with parameters (81,32,13,12),
(81,40,19,20), (125,28,3,7), (125,52,15,26), (125,62,30,31), (144,55,22,20),
and (144,66,30,30). Please note that PDSs in the source code are zero-indexed
(C++ style), whereas PDSs included in the paper are 1-indexed (GAP-style).
Thus, to load any PDS in the repository into GAP, 1 must be added to every
element.

###  4.3 PDS found in EA(512)

Running $111100$ trials, three (512,70,6,10) PDSs were found in the elementary
abelian group of order 512. Although these PDSs were already known, the fact
that local search could even find a PDS of size 512 demonstrates that local
search can function on larger group sizes. However, the fact that so much many
trials were needed to find a PDS in EA(512), arguably the easiest group of
order 512 to search, suggests that better versions of local search are needed
to handle this scale.

##  5 Conclusions, Future Work, and Acknowledgements

In this project, we used local search to find PDSs in many small groups, some
of which are new. Two of the new PDSs are used to construct SRGs listed as
open in Brouwer’s tables [5]. Additionally, these PDSs will serve as useful
large examples to researchers, to help them understand the structure of PDSs.

This work has two main limitations. First, because local search is not
exhaustive, we cannot use this method to determine nonexistence of a PDS in a
particular group. Consequently, determining when to stop a run can be
difficult, because running more trials will not yield a PDS if a PDS does not
exist in that group. Second, the PDSs found are necessarily a mix of new and
already known PDSs. It is difficult to know which are new and which are not
because there is not an equivalent of Brouwer’s table [5] for PDSs.

This paper managed to find interesting results simply by computer search,
without incorporating mathematical knowledge into the search. Thus, if
mathematical knowledge was incorporated, the search could become even more
effective. One way to do this would be to do local search on a search space
already reduced by character theory. Another way would be to do local search
with a starting set mathematically close to a PDS. Another idea is to fix a
set of linking difference sets and do local search on the coset
representatives attached to these difference sets, in an effort to find a
large PDS, since certain PDSs can be broken down into difference sets. A
simple modification would be to force inverses to be swapped in/out together
(because $D=D^{(-1)}$).

It is worth highlighting that local search is a highly flexible method. Thus,
the ideas in this paper can be easily adapted to find difference sets,
relative difference sets, partial difference sets in general (instead of
PDSs), or any other combinatorial object where an error is easily defined.

Acknowledgements. Thank you to Drs. James Davis, Eric Swartz, Ken Smith, and
John Polhill for providing advice on what groups to search, verifying the new
SRGs found, and helping to edit the paper draft. Thank you to Drs. Ken Smith
and Ryan Kaliszewski for the incidence matrix and convolution table code used
in this work. Thank you to the University of Richmond for the computing
resources (Spydur) on which runs were performed and to George Flanagin for
information about Spydur and SLURM. This paper started as a final project for
Dr. Joonsuk Park’s AI course; I would like to thank Dr. Park for making the
assignment so open-ended that I could have the time to pursue this interesting
line of research.

Declaration of Interest. The author reports there are no competing interests
to declare.

## References

  * [1] O. A. AbuGhneim, D. Peifer, and K. W. Smith.  All $(96,20,4)$ difference sets and related structures, 2019.
  * [2] H. U. Besche, B. Eick, E. O’Brien, and GAP Team.  SmallGrp, the gap small groups library, Version 1.4.1.  https://gap-packages.github.io/smallgrp/, Sep 2019.  GAP package.
  * [3] G. Blelloch, D. Anderson, and L. Dhulipala.  Parlaylib - a toolkit for parallel algorithms on shared-memory multicore machines.  In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’20, page 507–509, New York, NY, USA, 2020\. Association for Computing Machinery.
  * [4] A. C. Brady.  Negative latin square type partial difference sets in nonabelian groups of order 64.  Finite Fields and their Applications, 81:102044, 2022.
  * [5] A. E. Brouwer.  Parameters of strongly regular graphs.  https://www.win.tue.nl/~aeb/graphs/srg/srgtab1-50.html.
  * [6] A. E. Brouwer and H. Van Maldeghem.  Strongly Regular Graphs.  Cambridge University Press, 2022.
  * [7] R. Calderbank and W. M. Kantor.  The geometry of two-weight codes.  Bulletin of the London Mathematical Society, 18(2):97–122, 1986\.
  * [8] J. A. Davis, J. Polhill, K. W. Smith, and E. Swartz.  Nonabelian partial difference sets constructed using abelian techniques, 2023.  https://doi.org/10.48550/arXiv.2307.15648.
  * [9] S. De Winter, E. Kamischke, and Z. Wang.  Automorphisms of strongly regular graphs with applications to partial difference sets.  Designs, Codes and Cryptography, 79, 2016.
  * [10] The GAP Group.  GAP – Groups, Algorithms, and Programming, Version 4.11.1, 2021\.
  * [11] L.K. Jørgenson and M. Klin.  Switching of edges in strongly regular graphs i: A family of partial difference sets on 100 vertices.  Electron. J. Combin., 10(R17), 2003.
  * [12] S. L. Ma.  A survey of partial difference sets.  Designs, Codes, and Cryptography, 4, 1994.
  * [13] University of Richmond.  Spydur and spiderweb.  https://data.richmond.edu/About-HPC-at-UR/index.html.
  * [14] D. Peifer.  DifSets, an algorithm for enumerating all difference sets in a group, Version 2.3.1.  https://dylanpeifer.github.io/difsets, Sep 2019.  Refereed GAP package.
  * [15] J. Polhill, J. A. Davis, K. W. Smith, and E. Swartz.  Genuinely nonabelian partial difference sets.  Journal of Combinatorial Designs, 32(7):351–370, 2024.
  * [16] S. Russell and P. Norvig.  Artificial Intelligence: A Modern Approach, Third Edition.  Prentice Hall, 2010.  See Chapter 4, p.120-125.

(144,52,16,20) |  SmallGrp(144,68): [2, 3, 5, 8, 10, 14, 17, 18, 22, 23, 32, 33, 43, 44, 45, 46, 47, 50, 54, 56, 57, 60, 61, 63, 68, 70, 71, 73, 75, 77, 79, 80, 81, 82, 85, 87, 91, 92, 94, 100, 105, 106, 108, 111, 113, 117, 126, 139, 140, 141, 142, 144]
---|---
|  SmallGrp(144,126): [2, 3, 5, 8, 9, 15, 16, 19, 21, 22, 23, 25, 29, 30, 31,
35, 39, 40, 44, 45, 47, 48, 51, 52, 53, 54, 55, 56, 60, 67, 71, 74, 77, 86,
89, 90, 97, 98, 101, 103, 108, 111, 112, 118, 121, 127, 128, 136, 139, 140,
142, 143]
(147, 66, 25, 33) |  SmallGrp(147,3): [2, 3, 4, 5, 8, 10, 11, 12, 14, 16, 19, 20, 25, 27, 28, 29, 30, 31, 33, 37, 38, 39, 40, 41, 42, 45, 46, 52, 53, 55, 57, 58, 64, 66, 67, 70, 71, 79, 82, 87, 88, 89, 93, 94, 103, 104, 105, 107, 108, 111, 112, 113, 116, 117, 126, 127, 128, 129, 130, 131, 133, 134, 135, 142, 145, 147]
|  SmallGrp(147,4): [3, 4, 6, 7, 8, 9, 11, 15, 16, 18, 20, 22, 23, 25, 26, 27,
32, 33, 35, 41, 42, 43, 45, 49, 50, 51, 52, 54, 56, 58, 62, 63, 64, 66, 72,
74, 77, 80, 81, 85, 86, 88, 89, 90, 91, 97, 98, 104, 111, 112, 113, 115, 116,
120, 121, 122, 123, 124, 125, 131, 132, 133, 136, 138, 141, 143]
Table 1: New SRGs found and their associated PDSs. Group size | # Trials
---|---
$n<144$ | $5n^{2}$
$n=144,k<34$ | $n^{2}$
$n=144,k\geq 34$ | $n^{2},2n^{2},2n^{2}$
$145\leq n<162$, SRG unknown | $2n^{2}$
$162\leq n<186$, SRG unknown | $2n^{2},2n^{2}$
$186\leq n<239,n\not\in\\{216,217\\}$, SRG unknown | $2n^{2}$
Table 2: Maximum number of trials of local search ran on each parameter set.
The number of trials was chosen to scale based on the group order, because
larger groups have a larger search space. In the $n=144,k\geq 34$ case, for
example, three searches were run: one with $n^{2}$ trials, and two with
$2n^{2}$ trials.