$$$$

Scalable Approaches to Self-Supervised Learning using Spectral Analysis

Reading Group – Wednesday April 5th 2023

By Ross Viljoen and Vincent Dutordoir

Abstract

Learning the principal eigenfunctions of an operator is a fundamental problem in various machine learning tasks, from representation learning to Gaussian processes. However, traditional non-parametric solutions suffer from scalability issues –- rendering them impractical on large datasets.

This reading group will discuss parametric approaches to approximating eigendecompositions using neural networks. In particular, Spectral Inference Networks (SpIN) offer a scalable method for approximating eigenfunctions of symmetric operators on high-dimensional function spaces using bi-level optimization methods and gradient masking (Pfau et al., 2019).

A recent improvement on SpIN, called NeuralEF, focuses on approximating eigenfunction expansions of kernels (Deng et al., 2022a). The method is applied to modern neural-network based kernels (GP-NN and NTK) as well as scaling up the linearised Laplace approximation for deep networks (Deng et al., 2022a). Finally, self-supervised learning can be expressed in terms of approximating a contrastive kernel, which allows NeuralEF to learn structured representations (Deng et al., 2022b).

References

David Pfau, Stig Petersen, Ashish Agarwal, David G. T. Barrett,and Kimberly L. Stachenfeld. "Spectral inference networks: Unifying deep and spectral learning." ICLR (2019).

Zhijie Deng, Jiaxin Shi, and Jun Zhu. "NeuralEF: Deconstructing kernels by deep neural networks." ICML (2022a).

Zhijie Deng, Jiaxin Shi, Hao Zhang, Peng Cui, Cewu Lu, Jun Zhu. "Neural Eigenfunctions Are Structured Representation Learners." arXiv preprint arXiv:2210.12637 (2022b).

---

Introduction

Spectral methods are ubiquitous:

• mathematics: spectral theorem (diagonalisation of compact, self-adjoint operators)
• physics: Solving PDEs (e.g., heat, wave, Schrödinger equations) in frequency domain (i.e. using spectral metin frequency domain (i.e. using spectral methods).
• Machine learning:
  • Kernels on manifold use the eigenbasis w.r.t. to the Laplace-Beltrami operator
    ${\mathrm{\Delta }}_{\mathcal{M}}$.
  • Spectral Mixture Kernels
  • Fourier Neural Operators

Machine Learning	Physics/Engineering

Topic of today's reading group

Find non-linear embedding of data on low-dimensional manifold.

A well known algorithm is Principle Component Analysis.

1. Construct Gram for all pair of points
   
   $$k(\mathbf{X},\mathbf{X})\in {\mathbb{R}}^{N\times N}$$
2. Each eigenvector
   $\mathit{u}$ contains a one-dimensional embedding for each point
   $x_n$.

Scales cubically and quadratically with

$N$ for compute and memory. What to do with new data?

Overview of reading group

This reading group will cover three papers in chronological order that build on each other.

1. Pfau et al. (2019). "Spectral inference networks: Unifying deep and spectral learning."
   • Introduces the problem and formulates the problem of finding embeddings (i.e. eigenfunctions) as an optimization problem.
   • Focus is not necessarily on kernel operators.
2. Deng et al. (2022). "NeuralEF: Deconstructing kernels by deep neural networks."
   • Improve upon SpIN algorithm (more computationally efficient and simpler).
   • Apply the method to popular DNN-inspired kernels.
3. Deng et al. (2022). Neural Eigenfunctions Are Structured Representation Learners
   • A final final improvement on the core algorithm with applications in self-supervised learning.

Spectral decomposition as Optimization

Eigenvectors of a matrix are defined as

$\mathbf{A}\mathit{u}=\lambda \mathit{u}$ for some scalar

$\lambda$, called the eigenvalue.

Let

$\mathbf{A}$ be symmetric then, the eigenvector corresponding to the largest eigenvalue is the solution of

$$\underset{\mathit{u}}{max}{\mathit{u}}^{\mathrm{\top }}\mathbf{A}\mathit{u}\text{s.t.}{\mathit{u}}^{\mathrm{\top }}\mathit{u}=1$$

Proof (sketch)

• $\mathbf{A}$ is symmetric and real, therfore
  $\mathbf{A}=\mathbf{V}\mathbf{\Lambda }{\mathbf{V}}^{\mathrm{\top }}$, where
  $\mathit{V}$ is a orthonormal basis:
  ${\mathbf{V}}^{\mathrm{\top }}\mathbf{V}=\mathbf{I}$ and
  $\mathbf{\Lambda }=\text{diag}({\lambda }_1,\dots ,{\lambda }_n)$ with
  ${\lambda }_1>{\lambda }_2>\dots >{\lambda }_n$.
• Let
  $\mathit{u}=\mathbf{V}\mathit{\alpha }=\sum {\alpha }_i{\mathit{v}}_i$

Rewriting the objective:

$$\begin{array}{rl}{\mathit{u}}^{\mathrm{\top }}\mathbf{A}\mathit{u}& ={\mathit{\alpha }}^{\mathrm{\top }}{\mathbf{V}}^{\mathrm{\top }}\mathbf{V}\mathbf{\Lambda }{\mathbf{V}}^{\mathrm{\top }}\mathbf{V}\mathit{\alpha }\\ & =\mathrm{Tr}(\mathit{\alpha }{\mathit{\alpha }}^{\mathrm{\top }}\mathbf{\Lambda })\\ & ={\sum }_i{\alpha }_i^2{\lambda }_i\end{array}$$

Now adding a Lagrange multiplier

$\ell$ for the constaint (which can be rewritten as

$\Vert \mathit{\alpha }{\Vert }_2^2=1$) gives

$${\sum }_i{\alpha }_i^2{\lambda }_i+\ell (\Vert \mathit{\alpha }{\Vert }_2^2-1)$$
which can be solved by setting the derivative w.r.t.

$\mathit{\alpha }$ and

$\ell$ to zero. This gives

$${\alpha }_1=1\text{and}{\alpha }_{\ne 1}=0.$$

The constrained optimisation objective from above, is equivalent (up to a scaling factor) to

$$\underset{\mathit{u}}{max}\frac{{\mathit{u}}^{\mathrm{\top }}\mathbf{A}\mathit{u}}{{\mathit{u}}^{\mathrm{\top }}\mathit{u}}$$
because we normalize the vector to lie on the unit hypersphere:

$\frac{\mathit{u}}{\sqrt{{\mathit{u}}^{\mathrm{\top }}\mathit{u}}}\in {\mathcal{S}}^d$. This expression is known as the Rayleigh quotient and equals the eigenvalue corresponding to the eigenvector at its maximum.

To compute the top N eigenvectors

$\mathbf{U}=({\mathit{u}}_1,\dots ,{\mathit{u}}_N)$, we can solve a sequence of maximization problems greedily:

$${\mathit{u}}_i=\text{arg}\underset{\mathit{u}}{max}\frac{{\mathit{u}}^{\mathrm{\top }}\mathbf{A}\mathit{u}}{{\mathit{u}}^{\mathrm{\top }}\mathit{u}}\text{s.t.}{\mathit{u}}_1^{\mathrm{\top }}\mathit{u}=0,\dots ,{\mathit{u}}_{i-1}^{\mathrm{\top }}\mathit{u}=0.$$

If we drop the orthogonality constraint we can formulate this as a single unconstrained objective

$$\text{arg}\underset{\mathbf{U}}{max}\mathrm{Tr}[({\mathbf{U}}^{\mathrm{\top }}\mathbf{U}{)}^{-1}{\mathbf{U}}^{\mathrm{\top }}\mathbf{A}\mathbf{U}]$$
Following a similar derivation as above, the maximum is given by

$\sum _{i=1}^N{\lambda }_i$ (the largest

$N$ eigenvalues). However, without the orthogonality constaint

${\mathit{u}}_i^{\mathrm{\top }}{\mathit{u}}_j=0$ for

$i\ne j$,

$\mathbf{U}$ will simply span the same subspace as the true eigenfunctions.

Remark. The objective is invariant to right multiplications (i.e. linear combination of the basis).

Proof. Set

$\tilde{\mathbf{U}}=\mathbf{U}\mathbf{W}$ and show that the objective has the same optimum for

$\tilde{\mathbf{U}}$ as for

$\mathbf{U}$.

The above derivation can be used to optimize for the eigenvectors in (kernel) PCA where

$\mathbf{A}=\mathbf{X}{\mathbf{X}}^{\mathrm{\top }}$ or

$\mathbf{A}=k(\mathbf{X},\mathbf{X})$ for

$\mathbf{X}\in {\mathbb{R}}^{N\times D}$ a feature matrix.

An embedding for a new datapoint can be found by interpolating the eigenfunctions:

$$\mathit{u}=\sum _{n=1}^{N}k(x_n,x){\mathit{u}}_n$$
which scales

$\mathcal{O}(N)$.

Spectral Inference Networks (SpIN) overcomes these limitations by using a parametric form for the embeddings.

From eigenvectors to eigenfunctions

Suppose that instead of a matrix

$\mathbf{A}$ we have a symmetric (not necessarily positive definite) kernel

$k(x,x)$ where

$x$ and

$x^{\prime }$ are in some measurable space

$\mathrm{\Omega }$, which can be either continuous or discrete.

Define inner product on

$\mathrm{\Omega }$ w.r.t. to input density

$p(x)$ as

$$⟨f,g⟩={\int }_{\mathrm{\Omega }}f(x)g(x)p(x)\mathrm{d}x={\mathbb{E}}_{x\sim p}[f(x)g(x)]$$
and a kernel operator

$\mathcal{K}$ as

$$\mathcal{K}f=⟨k(x,\cdot ),f⟩=\int k(x,x^{\prime })f(x^{\prime })p(x^{\prime })\mathrm{d}{x}^{\prime }={\mathbb{E}}_{x^{\prime }\sim p}[k(x,x^{\prime })f(x^{\prime })]$$

we are interested in finding the top

$N$ eigenfunctions

$u:\mathrm{\Omega }\to \mathbb{R}$ of the operator

$\mathcal{K}$, for which hold

$$(\mathcal{K}u)(x)=\int k(x^{\prime },x)u(x^{\prime })p(x^{\prime })\mathrm{d}{x}^{\prime }=\lambda u(x)\text{and}⟨u_i,u_j⟩={\delta }_{ij}.$$

In vector space

In vector space we could cast the problem of spectral decomposition to an optimization problem using the following objective:

$$\begin{gathered} \underset{\mathbf{U}}{max}\mathrm{Tr}[({\mathbf{U}}^{\mathrm{\top }}\mathbf{U}{)}^{-1}{\mathbf{U}}^{\mathrm{\top }}\mathbf{A}\mathbf{U}]⟺\underset{\mathbf{U} \\ {\mathbf{U}}^{\mathrm{\top }}\mathbf{U}=\mathbf{I}}{max}\mathrm{Tr}[{\mathbf{U}}^{\mathrm{\top }}\mathbf{A}\mathbf{U}] \end{gathered}$$

In function space

The analogue of this in function space looks like this:

Let

$\mathit{u}:\mathcal{X}\to {\mathbb{R}}^N$ represent the N eigenfunctions (or a linear combination thereof, which means that they share the same span).

$$\begin{array}{rl}\underset{\mathit{u}}{max}& \mathrm{Tr}[{\mathbb{E}}_x[\mathit{u}(x){\mathit{u}}^{\mathrm{\top }}(x){]}^{-1}{\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime })\mathit{u}(x)\mathit{u}(x^{\prime })]]\\ & ⟺\underset{\mathit{u}}{max}\mathrm{Tr}[{\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime })\mathit{u}(x)\mathit{u}(x^{\prime })]]\text{ s.t. }{\mathbb{E}}_x[\mathit{u}(x){\mathit{u}}^{\mathrm{\top }}(x)]=\mathbf{I}\end{array}$$

To simplify notation

$$\mathbf{\Sigma }={\mathbb{E}}_x[\mathit{u}(x){\mathit{u}}^{\mathrm{\top }}(x)]\text{and}\mathbf{\Pi }={\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime })\mathit{u}(x)\mathit{u}(x^{\prime })]$$
which gives, parameterizing the eigenfunctions using a neural net with parameters

$\theta$, the following objective:

$$\mathcal{L}(\theta )=\underset{{\mathit{u}}_{\theta }}{max}\mathrm{Tr}\left[{\mathbf{\Sigma }}^{-1}\mathbf{\Pi }\right]$$

Problems

• The objective is invariant to linear tsransformation of the features
  $\mathit{u}(x)$, optimizing it will only give a function that spans the top eigenfunctions of
  $\mathcal{K}$. There is also no ordering (i.e. first eigenfunction corresponds to largest
• Minibatch estimations of
  $\mathcal{L}$ do not lead to unbiased estimates of the gradients. We can not use traditional SGD.

Ordering through gradient masking

The objective is invariant to linear transformation of the output. The solution only spans the top eigenfunctions…

We can use the invariance of trace to cyclic permutation to rewrite the objective.
Let

$\mathbf{\Sigma }=\mathbf{L}{\mathbf{L}}^{\mathrm{\top }}$, then the objective can be rewritten

$$\mathrm{Tr}\left({\mathbf{\Sigma }}^{-1}\mathbf{\Pi }\right)=\mathrm{Tr}\left({\mathbf{L}}^{-1}\mathbf{\Pi }{\mathbf{L}}^{-\mathrm{\top }}\right)=\mathrm{Tr}\mathbf{\Lambda }=\sum {\lambda }_i$$

where we used a shorthand

$\mathbf{\Lambda }\triangleq {\mathbf{L}}^{-1}\mathbf{\Pi }{\mathbf{L}}^{-\mathrm{\top }}$. This matrix has the convenient property that the upper left

$n\times n$ block only depends on the first

$n$ eigenfunctions.

By zero-ing out the gradient from higher to lower eigenvalues we can impose an ordering. Summarized in the following claim (in the appendix):

proof by induction.

Forward	Backward

The 'masked' gradient can be written down in closed-form:

where

$\mathbf{\Sigma }={\mathbf{L}}^{\mathrm{\top }}\mathbf{L}$.

Bi-level optimization

In SGD we use stochastic gradient estimates

$\tilde{\mathit{g}}$ which typically are unbiased:

$$\mathbb{E}[\tilde{\mathit{g}}]={\mathrm{\nabla }}_{\theta }\mathcal{L}$$

The objective expression is a nonlinear function of multiple expectations, so naively replacing

$\mathbf{\Sigma },\mathbf{\Pi }$ and their gradients with empirical estimates will be biased.

Reframe objective as bi-level optimization, in which

$\mathbf{\Sigma }$ and

$\mathbf{\Pi }$ are estimated as well as

$\theta$.

Bilevel stochastic optimization is the problem of simultaneously solving two coupled minimization.

Traditional optimization

$$\underset{x}{max}f(x)\text{s.t.}g(x)\le 0.$$

Formally, a bilevel optimization problem reads:

$$\underset{x\in \mathcal{X},y}{min}F(x,y)\text{s.t.}G(x,y)\le 0,\text{ and }y\in S(x)$$
where

$S(x)$ is the set of optimal solutions of the x-parameterized problem

$$S(x)=\text{arg}\underset{y\in \mathcal{Y}}{min}f(x,y)$$

Bi-level optimization the objective depends on the 'decision' of another actor whose decision depends on our action…

Example: Toll Setting
Consider a network of highways that is operated by the government. The government wants to maximize its revenues by choosing the optimal toll setting for the highways. However, the government can maximize its revenues only by taking the highway users' problem into account. For any given tax structure the highway users solve their own optimization problem, where they minimize their traveling costs by deciding between utilizing the highways or an alternative route

Bilevel stochastic problems are common in machine learning and include actor-critic methods, generative adversarial networks and imitation learning. SpIN relies on a classic result from 1997 "Vivek S Borkar. Stochastic approximation with two time scales". It boils down to having a second objective which is solved using a different (slower) learning rate

$$\underset{\mathbf{\Sigma },{\mathrm{\nabla }}_{\theta }\mathbf{\Sigma }}{min}\Vert \mathbf{\Sigma }-{\overline{\mathbf{\Sigma }}}_t{\Vert }^2+\Vert {\mathrm{\nabla }}_{\theta }\mathbf{\Sigma }-\overline{{\mathrm{\nabla }}_{\theta }{\mathbf{\Sigma }}_t}{\Vert }^2$$
where

${\overline{\mathbf{\Sigma }}}_t$ and

${\overline{{\mathrm{\nabla }}_{\theta }\mathbf{\Sigma }}}_t$ are moving averages.

SpIN Algorithm

1. Minimizes the objective end-to-end by stochastic optimization
   
   $$\mathrm{Tr}[{\mathbb{E}}_x[\mathit{u}(x){\mathit{u}}^{\mathrm{\top }}(x){]}^{-1}{\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime })\mathit{u}(x)\mathit{u}(x^{\prime })]]$$
2. Performs the optimization over a parametric function class such as deep neural networks.
3. Uses the modified gradient (masking) to impose an ordering on the learned features
4. Uses bilevel optimization to overcome the bias introduced by finite batch sizes

Problems:

• Need to cholesky decompose
  $\mathbf{\Sigma }$ in every iteration
• Need to track Jacobian
  ${\mathrm{\nabla }}_{\theta }\mathbf{\Sigma }$

---

Kernel methods

Kernel methods project data into a high-dimensional feature space

$\mathcal{H}$ to enable linear manipulation of nonlinear data. In other words, let

$\varphi :\mathcal{X}\to \mathcal{H}$ be the feature map, then

$k:\mathcal{X}\times \mathcal{X}\to \mathbb{R}$ linearly depends on the feature representations of the inputs

$$k(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$$
Often we don't know

$\mathcal{H}$ (it is typically infinite dimensional). The subtlety is that we can leverage the "kernel trick" to bypass the need of specifying

$\mathcal{H}$ explicitly.

There is a rich family of kernels.

Classic kernels: Squared Exponential, Matérn Family, Linear, Polynomial, etc. They may easily fail when processing real-world data like images and texts due to inadequate expressive power and the curse of dimensionality.

Modern kernel have been developed on the inductive biases of NN architectures, such as the NTK and NN-GP (discussed briefly by Ross and the topic of next week's reading group).

Kernel approximations

An idea to scale up kernel methods is to approximate the kernel with the inner product of some explicit vector representations of the data

$$k(x,x^{\prime })\approx \mathit{\nu }(x{)}^{\mathrm{\top }}\mathit{\nu }(x^{\prime }),$$
where

$\mathit{\nu }:\mathcal{X}\to {\mathbb{R}}^R$. There are two broad approaches…

Bochner's theorem

Bochner's theorem: a stationary kernels is psd if it is the Fourier transform of a positive measure

$S(\omega )$ (power spectrum):

$$\begin{array}{rl}k(x-y)& =\int S(\omega )\exp (i\omega r)\mathrm{d}\omega \\ & \approx \frac{1}{R}\sum \exp (i{\omega }_r(x-y)){\omega }_r\sim S(\omega )\\ & ={\left[\begin{array}{c}\frac{1}{\sqrt{R}}\exp (i{\omega }_{1}x)\\ \frac{1}{\sqrt{R}}\exp (i{\omega }_{2}x)\\ ⋮\\ \frac{1}{\sqrt{R}}\exp (i{\omega }_{R}x)\end{array}\right]}^{\mathrm{\top }}\left[\begin{array}{c}\frac{1}{\sqrt{R}}\exp (i{\omega }_{1}y)\\ \frac{1}{\sqrt{R}}\exp (i{\omega }_{2}y)\\ ⋮\\ \frac{1}{\sqrt{R}}\exp (i{\omega }_{R}y)\end{array}\right]\end{array}$$

• Can only be used for stationary kernel
• Scales exponentially bad with dimension

Mercer decompsition

A kernel

$k$ has a kernel operator

$\mathcal{K}$ and we are interested in finding it's eigenfunctions.

Eigenfunctions

$u:\mathrm{\Omega }\to \mathbb{R}$ of the operator

$\mathcal{K}$ obey

$$(\mathcal{K}u)(x)=\int k(x^{\prime },x)u(x^{\prime })p(x^{\prime })\mathrm{d}{x}^{\prime }=\lambda u(x)\text{and}⟨u_i,u_j⟩={\delta }_{ij}.$$

Using the eigenfunctions corresponding to non-zero eigenvalues

$k$ has the representation

$$k(x,x^{\prime })={\sum }_i{\lambda }_i{u}_i(x)u_i(x^{\prime }).$$

Nyström approximation

We can use the data

$\mathbf{X}=\{x_n{\}}_{n=1}^N$ to obtain an MCMC estimate of the top R eigenfunctions by taking the eigenvectors of

$k(\mathbf{X},\mathbf{X})$.

$$\{{\hat{\lambda }}_i,({\hat{u}}_i(x_1),\dots ,{\hat{u}}_i(x_N)){\}}_{i=1}^R$$

Nystrom methods approximate the eigenfunctions for out-of-sample points

$x$ as:

$${\hat{u}}_i(x)=\frac{1}{N}{\sum }_{n}k(x,x_n){\hat{u}}_i(x_n)$$

which approximates the kernel

$$k(x,x^{\prime })\approx \sum _{i=1}^R{\hat{\lambda }}_i{\hat{u}}_i(x){\hat{u}}_i(x^{\prime })$$

Unlike RFFs, Nyström method can be applied to approximate any positive-definite kernel. Yet, it is non-trivial to scale it up.

• the matrix eigendecomposition is costly for even medium sized training data.
• evaluating the eigenfuction at a new location entails evaluating
  $k$ for N times, which is unaffordable when coping with the modern kernels specified by deep architectures.

NeuralEF (Deng et al., 2022a)

Back to the SpIN objective:

$$\begin{array}{rl}\underset{\mathit{u}}{max}& \mathrm{Tr}[{\mathbb{E}}_x[\mathit{u}(x){\mathit{u}}^{\mathrm{\top }}(x){]}^{-1}{\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime })\mathit{u}(x)\mathit{u}(x^{\prime })]]\end{array}$$

Can we instead enforce an ordering directly in the optimisation objective such that the gradient masking becomes unnecessary?

Characterise the spectral decomposition as an asymmetric maximisation problem:

$$\begin{array}{r}\underset{{\hat{u}}_j}{max}{\mathrm{\Pi }}_{jj}\text{s.t.}{\mathrm{\Sigma }}_{jj}=1,{\mathrm{\Pi }}_{ij}=0,\mathrm{\forall }i<j\end{array}$$

where:

$$\begin{array}{r}{\mathrm{\Sigma }}_{jj}={\mathbb{E}}_x[{\hat{u}}_j(x){\hat{u}}_j(x)]\text{and}{\mathrm{\Pi }}_{ij}={\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime }){\hat{u}}_i(x){\hat{u}}_j(x^{\prime })]\end{array}$$

The claim is that the pairs

$({\mathrm{\Pi }}_{jj},{\hat{u}}_j)$ will converge to the true eigenpairs

$({\lambda }_j,u_j)$, ordered such that

${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_k$.

Proof

For

$j=1$, there is no orthogonality constraint, so the problem is the eigenfunction version of finding the largest eigenvector by maximisation:

$$\begin{array}{rl}{\mathrm{\Pi }}_{11}& ={\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime }){\hat{u}}_1(x){\hat{u}}_1(x^{\prime })]\\ & ={\mathbb{E}}_{x,x^{\prime }}[(\sum _{j\ge 1}{\lambda }_j{u}_j(x)u_j(x^{\prime })){\hat{u}}_1(x){\hat{u}}_1(x^{\prime })]({\text{Mercer's th}}^{\mathrm{m}})\\ & =\sum _{j\ge 1}{\lambda }_j{\mathbb{E}}_{x,x^{\prime }}[u_j(x)u_j(x^{\prime }){\hat{u}}_1(x){\hat{u}}_1(x^{\prime })]\\ & =\sum _{j\ge 1}{\lambda }_j{\mathbb{E}}_x[u_j(x){\hat{u}}_1(x)]{\mathbb{E}}_{x^{\prime }}[u_j(x^{\prime }){\hat{u}}_1(x^{\prime })]\\ & =\sum _{j\ge 1}{\lambda }_j⟨u_j,{\hat{u}}_1{⟩}^2\end{array}$$

but, since

$\{u_j\}$ form an orthonormal basis, we can write

${\hat{u}}_1=\sum _{l\ge 1}{w}_l{u}_l$, so

$$\begin{array}{rl}{\mathrm{\Pi }}_{11}& =\sum _{j\ge 1}{\lambda }_j⟨u_j,\sum _{l\ge 1}{w}_l{u}_l{⟩}^2\\ & =\sum _{j\ge 1}{\lambda }_j{w}_j^2\end{array}$$

Recalling the constraint:

$$\begin{array}{r}{\mathrm{\Sigma }}_{11}={\mathbb{E}}_x[{\hat{u}}_1(x){\hat{u}}_1(x)]=⟨{\hat{u}}_1,{\hat{u}}_1⟩=\sum _{j\ge 1}{w}_j^2=1,\end{array}$$

the objective must be maximised by taking

$w_1=1$ and

$w_j=0,j>1$. Therefore, the optimum is found when

${\hat{u}}_1=u_1$.

For

$j=2$, we now have the additional orthogonality constraint:

$$\begin{array}{rl}{\mathrm{\Pi }}_{12}& ={\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime }){\hat{u}}_1(x){\hat{u}}_2(x^{\prime })]\\ & ={\mathbb{E}}_{x,x^{\prime }}[k(x,x^{\prime })u_1(x){\hat{u}}_2(x^{\prime })]\\ & =\sum _{j\ge 1}{\lambda }_j⟨u_j,u_1⟩⟨u_j,{\hat{u}}_2⟩\\ & ={\lambda }_1⟨u_1,{\hat{u}}_2⟩\\ & =0\end{array}$$

So, for

$j=2$ we end up solving the same maximisation problem as for

$j=1$, but restricted to the orthogonal subspace of

$u_1$. Repeating the same logic for

$j>2$ completes the proof.

In practice, turn the orthogonality constraints into penalties:

$$\begin{array}{r}\underset{u_j}{max}{\mathrm{\Pi }}_{jj}-\sum _{i<j}\frac{{\mathrm{\Pi }}_{ij}^2}{{\mathrm{\Pi }}_{ii}}\text{s.t.}{\mathrm{\Sigma }}_{jj}=1,\mathrm{\forall }i<j\end{array}$$

Where the scaling factor of

${\mathrm{\Pi }}_{ii}$ is introduced into the denominator so that the two terms are on the same scale.

This objective is derived from a recent reinterpretation of PCA as a multi-player game in Gemp, Ian, et al. (2020) "Eigengame: PCA as a nash equilibrium." It can be seen as a function-space version of the same approach.

Minibatching

At each optimisation step,

${\mathrm{\Pi }}_{ij}$ is estimated by Monte Carlo integration with a minibatch of samples

$\mathbf{X}=\{x_b{\}}_{b=1}^B$:

$$\begin{array}{rl}{\tilde{\mathrm{\Pi }}}_{ij}& =\frac{1}{B^2}\sum _{b=1}^B\sum _{b^{\prime }=1}^B[k(x_b,x_{b^{\prime }}){\hat{u}}_i(x_b){\hat{u}}_j(x_{b^{\prime }})]\\ & =\frac{1}{B^2}{{\mathit{u}}_i^{\mathbf{X}}}^{\mathrm{\top }}{\mathbf{K}}_{\mathbf{X},\mathbf{X}}{\mathit{u}}_j^{\mathbf{X}}\end{array}$$

where

${\mathit{u}}_j^{\mathbf{X}}={[u_j(x_1),\dots ,u_j(x_B)]}^{\mathrm{\top }}\in {\mathbb{R}}^B$ is the concatenated output of

$u_j$ on the minibatch.

Tracking

${\tilde{\mathrm{\Pi }}}_{jj}$ with an exponential moving average (EMA) gives an estimate of

${\lambda }_j$.

Note: Minibatching will not give an unbiased estimate of the gradients of the objective. There is no discussion of this in the paper, but it appears that –- for large enough minibatch sizes –- this is not a problem in practice.

Batchnorm

Of course, there is still another constraint to satisfy, normalisation:

${\mathrm{\Sigma }}_{jj}=1$. In the minibatch setting, this is estimated as

${\hat{\mathrm{\Sigma }}}_{jj}=\frac{1}{B}{{\mathit{u}}_j^{\mathbf{X}}}^{\mathrm{\top }}{\mathit{u}}_j^{\mathbf{X}}$, so we want to have

$$\Vert {\mathit{u}}_j^{\mathbf{X}}{\Vert }_2^2\approx B$$
This is enforced by adding an L2 batch normalisation layer to the end of each neural net:

$${\mathit{u}}_j^{\mathbf{X}}=\frac{{\mathit{h}}_j^{\mathbf{X}}}{\Vert {\mathit{h}}_j^{\mathbf{X}}{\Vert }_2}\cdot B$$

where

${\mathit{h}}_j^{\mathbf{X}}$ is the output of the penultimate layer for the minibatch

$\mathbf{X}$.

The Training Loss and Gradients

After all the setup above, the training loss on a minibatch becomes:

$$\begin{array}{rl}\underset{{\theta }_1,\dots ,{\theta }_k}{min}\ell & =-\frac{1}{B^2}\sum _{j=1}^k({{\mathit{u}}_j^{\mathbf{X}}}^{\mathrm{\top }}{\mathbf{K}}_{\mathbf{X},\mathbf{X}}{\mathit{u}}_j^{\mathbf{X}}-\sum _{i=1}^{j-1}\frac{(\mathrm{sg}({{\mathit{u}}_i^{\mathbf{X}}}^{\mathrm{\top }}){\mathbf{K}}_{\mathbf{X},\mathbf{X}}{\mathit{u}}_j^{\mathbf{X}}{)}^2}{\mathrm{sg}({{\mathit{u}}_i^{\mathbf{X}}}^{\mathrm{\top }}{\mathbf{K}}_{\mathbf{X},\mathbf{X}}{\mathit{u}}_i^{\mathbf{X}})})\end{array}$$

where

$\mathrm{sg}$ denotes the "stop gradient" operation. Its gradient with respect to each network's parameters becomes:

$$\begin{array}{rl}{\mathrm{\nabla }}_{{\theta }_j}\ell & =\frac{2}{B^2}{\mathbf{K}}_{\mathbf{X},\mathbf{X}}({\mathit{u}}_j^{\mathbf{X}}-\sum _{i=1}^{j-1}\frac{{{\mathit{u}}_i^{\mathbf{X}}}^{\mathrm{\top }}{\mathbf{K}}_{\mathbf{X},\mathbf{X}}{\mathit{u}}_j^{\mathbf{X}}}{{{\mathit{u}}_i^{\mathbf{X}}}^{\mathrm{\top }}{\mathbf{K}}_{\mathbf{X},\mathbf{X}}{\mathit{u}}_i^{\mathbf{X}}}{\mathit{u}}_j^{\mathbf{X}})\cdot {\mathrm{\nabla }}_{{\theta }_j}{\mathit{u}}_j^{\mathbf{X}}\end{array}$$

Notably, the term in the gradient within the brackets is exactly the (generalised) Gram-Schmidt orthogonalisation of

${\mathit{u}}_j^{\mathbf{X}}$ with respect to all

${\mathit{u}}_j^{\mathbf{X}}$ where

$i<j$.

Eigendecomposition of Modern NN Kernels

Let

$g(\cdot ,\theta ):\mathcal{X}\to {\mathbb{R}}^{N_{out}}$ denote a function represented by an NN with weights

$\theta \sim p(\theta )$. Then a Neural Network Gaussian Process (NNGP) kernel is defined as

$$k_{\mathrm{NNGP}}(x,x^{\prime })={\mathbb{E}}_{\theta \sim p(\theta )}[g(x,\theta )g(x,\theta {)}^{\mathrm{\top }}]$$
which can be computed analytically when the number of neurons in the layer goes to infinity. There are many classic papers who do this Neal (1998), Cho and Saul (2009), …

A Neural Tangent Kernel (NTK) is defined as

$$k_{\mathrm{NTK}}(x,x^{\prime })={\mathbb{E}}_{\theta \sim p(\theta )}[{\mathrm{\nabla }}_{\theta }g(x,\theta ){\mathrm{\nabla }}_{\theta }^{\mathrm{\top }}g(x,\theta )]$$

Topic of next week's reading group….

The NNGP and NTK kernels can be very expensive, or even analytically intractable to compute. A common approach is to estimate them by Monte Carlo sampling with finite width networks. This is straightforward for the NNGP:

$$k_{\mathrm{NNGP}}(x,x^{\prime })={\mathbb{E}}_{\theta \sim p(\theta )}[g(x,\theta )g(x,\theta {)}^{\mathrm{\top }}]\approx \frac{1}{S}\sum _{s=1}^{S}g(x,{\theta }_s)g(x,{\theta }_s{)}^{\mathrm{\top }}$$

The NTK is not so simple to estimate, as it involves the outer product of the Jacobian of the network. For large models, this is very expensive to compute and store exactly. Here we focus on estimating the "empirical NTK" of a finite network, given by

$$k_{\mathrm{NTK}}(x,x^{\prime })={\mathrm{\nabla }}_{\theta }g(x,\theta ){\mathrm{\nabla }}_{\theta }^{\mathrm{\top }}g(x,\theta ).$$

Observing that, for any

$p(\mathit{v})$ such that

${\mathbb{E}}_{\mathit{v}\sim p(\mathit{v})}\left[\mathit{v}{\mathit{v}}^{\mathrm{\top }}\right]$ =

${\mathbf{I}}_{dim(\theta )}$:

$$k_{\mathrm{NTK}}(x,x^{\prime })={\mathbb{E}}_{\mathit{v}\sim p(\mathit{v})}\left[({\mathrm{\nabla }}_{\theta }g(x,\theta )\mathit{v}){({\mathrm{\nabla }}_{\theta }g(x,\theta )\mathit{v})}^{\mathrm{\top }}\right]$$

Taking a Taylor expansion,

${\mathrm{\nabla }}_{\theta }g(x,\theta )\mathit{v}\approx (g(x,\theta +\epsilon \mathit{v})-g(x,\theta ))/\epsilon$, and

$$k_{\mathrm{NTK}}(x,x^{\prime })\approx \frac{1}{S}\sum _{s=1}^S\left[\left(\frac{g(x,\theta +\epsilon \mathit{v})-g(x,\theta )}{\epsilon }\right){\left(\frac{g(x,\theta +\epsilon \mathit{v})-g(x,\theta )}{\epsilon }\right)}^{\mathrm{\top }}\right].$$

Both of these approximations require

$S$ forward passes of the network with different parameter settings. To obtain good approximations in practice,

$S$ must be large (the authors use

$S=4000$). The hope is to be able to approximate this kernel with

$k\ll S$ eigenfunctions to significantly speed up evaluation at test time.

Scaling up the Linearised Laplace Approximation (LLA)

The LLA is a method to obtain predictive uncertainty estimates for neural networks trained by MAP. The approximate posterior in function space is given by:

$$\mathcal{GP}(f|g(x,{\mathit{\theta }}_{\mathrm{MAP}}),{\mathrm{\nabla }}_{\theta }g(x,{\mathit{\theta }}_{\mathrm{MAP}})\mathbf{\Sigma }{\mathrm{\nabla }}_{\theta }g(x,{\mathit{\theta }}_{\mathrm{MAP}}{)}^{\mathrm{\top }})$$

where

$\mathbf{\Sigma }$ is the inverse Gauss-Newton matrix (an approximation to the Hessian).

$\mathbf{\Sigma }$ has size

$\dim (\mathit{\theta })\times \dim (\mathit{\theta })$, so for a large network this is expensive to invert. It has the form

$$\begin{gathered} {\mathbf{\Sigma }}^{-1}=\sum _i{\mathrm{\nabla }}_{\theta }g(x_i,{\mathit{\theta }}_{\mathrm{MAP}}{)}^{\mathrm{\top }}{\mathbf{\Lambda }}_i{\mathrm{\nabla }}_{\theta }g(x_i,{\mathit{\theta }}_{\mathrm{MAP}})+\frac{1}{{\sigma }_0^2}{\mathbf{I}}_{\dim (\mathit{\theta })} \\ \mathrm{where}{\mathbf{\Lambda }}_i={\mathrm{\nabla }}_{\mathit{f}\mathit{f}}^2\log p(y_i|\mathit{f}){|}_{\mathit{g}=g(x_i|{\mathit{\theta }}_{\mathrm{MAP}})}\in {\mathbb{R}}^{N_{out}\times N_{out}} \end{gathered}$$

This covariance matrix can be approximated using the eigenfunction approximation to the NTK, but now evaluated at the MAP parameters:

$$\begin{gathered} k_{\mathrm{NTK}}(x,x^{\prime })={\mathrm{\nabla }}_{\theta }g(x,{\mathit{\theta }}_{\mathrm{MAP}}){\mathrm{\nabla }}_{\theta }^{\mathrm{\top }}g(x,{\mathit{\theta }}_{\mathrm{MAP}})\approx \mathit{\psi }(x_i{)}^{\mathrm{\top }}\mathit{\psi }(x_i) \\ \mathrm{where}\mathit{\psi }(x)=[\sqrt{{\hat{\lambda }}_1}{u}_1(x),\dots ,\sqrt{{\hat{\lambda }}_k}{u}_k(x)] \end{gathered}$$

The LLA posterior can now be approximated as:

$$\mathcal{GP}(f|g(x,{\mathit{\theta }}_{\mathrm{MAP}}),\mathit{\psi }(x){[\sum _i\mathit{\psi }(x_i{)}^{\mathrm{\top }}{\mathbf{\Lambda }}_i\mathit{\psi }(x_i)+\frac{1}{{\sigma }_0^2}{\mathbf{I}}_k]}^{-1}\mathit{\psi }(x{)}^{\mathrm{\top }})$$

where the matrix to be inverted now only has dimension

$k\times k$.

Compared to other scalable LLA methods, this method performs favourably on NLL and Expected Calibration Error (ECE):

Structured Representation Learning via Contrastive Learning (Deng et al., 2022b)

In contrastive learning, a clean data point

$\overline{\mathit{x}}$ is used to generate random augmentations according to some distribution

$p(\mathit{x}|\overline{\mathit{x}})$. The goal of contrastive learning is then to learn similar (in some sense) representations for augmentations which are generated from the same clean data point. One way of phrasing this problem is as learning a kernel function which measures similarity of data points according to the augmentation distribution

$p(\mathit{x}|\overline{\mathit{x}})$:

$$\begin{gathered} k(\mathit{x},{\mathit{x}}^{\mathbf{\prime }}):=\frac{p(\mathit{x},{\mathit{x}}^{\mathbf{\prime }})}{p(\mathit{x})p({\mathit{x}}^{\mathbf{\prime }})} \\ \mathrm{where}p(\mathit{x},{\mathit{x}}^{\mathbf{\prime }}):={\mathbb{E}}_{p_d(\overline{\mathit{x}})}[p(\mathit{x}|\overline{\mathit{x}})p({\mathit{x}}^{\mathbf{\prime }}|\overline{\mathit{x}})] \end{gathered}$$

and

$p_d(\overline{\mathit{x}})$ is the clean data distribution.

$p(\mathit{x})$ and

$p({\mathit{x}}^{\mathbf{\prime }})$ are the respective marginals of

$p(\mathit{x},{\mathit{x}}^{\mathbf{\prime }})$.

This kernel gives a measure of how likely is is that

$\mathit{x}$ and

${\mathit{x}}^{\mathbf{\prime }}$ were generated from the same clean data point.

Plugging this kernel into the eigenfunction loss:

$$\begin{array}{rl}{\mathrm{\Pi }}_{ij}& ={\mathbb{E}}_{p(\mathit{x})}{\mathbb{E}}_{p({\mathit{x}}^{\prime })}[k(\mathit{x},{\mathit{x}}^{\prime }){\hat{u}}_i(\mathit{x}){\hat{u}}_j({\mathit{x}}^{\prime })]\\ & ={\mathbb{E}}_{p(\mathit{x})}{\mathbb{E}}_{p({\mathit{x}}^{\prime })}[\frac{p(\mathit{x},{\mathit{x}}^{\mathbf{\prime }})}{p(\mathit{x})p({\mathit{x}}^{\mathbf{\prime }})}{\hat{u}}_i(\mathit{x}){\hat{u}}_j({\mathit{x}}^{\prime })]\\ & ={\mathbb{E}}_{p(\mathit{x},{\mathit{x}}^{\prime })}[{\hat{u}}_i(\mathit{x}){\hat{u}}_j({\mathit{x}}^{\prime })]\\ & \approx \frac{1}{b}\sum _{i=1}^b{\hat{u}}_i({\mathit{x}}_i){\hat{u}}_j({\mathit{x}}_i^{\prime })\end{array}$$

where

$x_i$ and

$x_i^{\prime }$ here are two independent samples generated from the same clean data point

${\overline{x}}_i$. This loss can then be optimised in exactly the same way as the standard NeuralEF.

A benefit of this approach is that the feature representations (eigenfunctions) are ordered in terms of importance. This means that they are well suited to be used as adaptive length codes. An application of this is in image retrieval where a shorter code can lead to much lower time and storage requirements for retrieval of the top

$M$ closest examples, while longer codes provide better accuracy when possible.