summaries: This paper studies the problem of KL-regularized reinforcement learning for locomotion tasks, where the KL regularization penalizes deviations from expert demonstrations.  This work makes the observation that fitting expert demonstrations to a certain class of conditional neural density models (e.g. neural networks that output the parameters of a Gaussian distribution), results in policies whose variance collapses for states that are different enough from the expert data.   The paper argues that this collapse causes instabilities in learning KL-regularized policies: for Gaussian policies, the KL penalty grows quadratically to infinity as the expert policy variance goes to 0. To address this issue, the paper proposes to instead compute the KL penalty by fitting expert demonstrations to models that do not suffer from this collapse, in particular Gaussian Process regression models. Gaussian Process models result in variance that increases (depending on the choice of kernel) for states that are far enough from the expert data.  The paper provides some analysis on why the variance collapse affects the RL optimization process, experiments that  aim to show an empirical relationship between expert policy variance, KL penalty and magnitude of the policy gradients, and a comparison between various methods that use KL regularization with an expert policy.

summaries: The authors identify a problem with KL-based reinforcement learning from expert demonstrations. Poor out-of-sample variance predictions of NN expert policies ends up unreasonably penalizing RL exploration outside the expert data distribution, potentially causing numerical instability. To remedy this they propose to instead use non-parametric expert policies based on a scalable GP approach.

summaries: This paper presents a previously unrecognized pathology in KL-regularized RL with expert demonstrations. Specifically the commonly used parametric behavioral policies suffer from collapse of predictive variance at states far from the demonstrations. This collapse of variance hinders the algorithm’s ability to learn effectively. The authors then propose to use non-parametric behavioral policies and demonstrate its effectiveness in several control tasks.

summaries: The authors identify a potential failure in KL-regularized reinforcement learning in which small predictive variance of the target policy may lead to exploding gradients, possibly destabilizing gradient-based learning algorithms. The authors discuss an uncertainty collapse of parametric models under Maximum Likelihood estimation in OOD regions of the expert, resulting in the aforementioned pathology. Finally, they suggest to use non-parametric models of the behavior policy (in which uncertainty collapse is not present), showing improved performance on several continuous control benchmarks.

abstractText: KL-regularized reinforcement learning from expert demonstrations has proved successful in improving the sample efficiency of deep reinforcement learning algorithms, allowing them to be applied to challenging physical real-world tasks. However, we show that KL-regularized reinforcement learning with behavioral reference policies derived from expert demonstrations can suffer from pathological training dynamics that can lead to slow, unstable, and suboptimal online learning. We show empirically that the pathology occurs for commonly chosen behavioral policy classes and demonstrate its impact on sample efficiency and online policy performance. Finally, we show that the pathology can be remedied by non-parametric behavioral reference policies and that this allows KL-regularized reinforcement learning to significantly outperform state-of-the-art approaches on a variety of challenging locomotion and dexterous hand manipulation tasks.

authors:
Michael Bain
Claude Sammut

title: A framework for behavioural cloning

venue: In Machine Intelligence

authors:
Philip J Ball
Cong Lu
Jack Parker-Holder
Stephen Roberts

title: Augmented world models facilitate zero-shot dynamics generalization from a single offline environment

venue: Proceedings of the 38th International Conference on Machine Learning,

authors:
Abdeslam Boularias
Jens Kober
Jan Peters

title: Relative entropy inverse reinforcement learning

venue: In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,

authors:
Ivan Bratko
Tanja Urbancic
Claude Sammut

title: Behavioural cloning: phenomena, results and problems

venue: IFAC Proceedings Volumes,

authors:
Tim Brys
Anna Harutyunyan
Halit Bener Suay
Sonia Chernova
Matthew E Taylor
Ann Nowé

title: Reinforcement learning from demonstrations through shaping

venue: In Twenty-fourth International Joint Conference on Artificial Intelligence,

authors:
Catherine Cang
Aravind Rajeswaran
Pieter Abbeel
Michael Laskin

title: Behavioral priors and dynamics models: Improving performance and domain transfer in offline RL, 2021

authors:
Thomas Degris
Martha White
Richard S. Sutton

title: Off-policy actor-critic

venue: In Proceedings of the 29th International Coference on International Conference on Machine Learning,

authors:
Gabriel Dulac-Arnold
Daniel Mankowitz
Todd Hester

title: Challenges of real-world reinforcement learning

venue: arXiv preprint arXiv:1904.12901,

authors:
Sebastian Farquhar
Michael A. Osborne
Yarin Gal

title: Radial bayesian neural networks: Beyond discrete support in large-scale bayesian deep learning

venue: Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics,

authors:
Alexandre Galashov
Siddhant M. Jayakumar
Leonard Hasenclever
Dhruva Tirumala
Jonathan Schwarz
Guillaume Desjardins
Wojciech M. Czarnecki
Yee Whye Teh
Razvan Pascanu
Nicolas Heess

title: Information asymmetry in kl-regularized RL

venue: In 7th International Conference on Learning Representations,

authors:
Yang Gao
Huazhe Xu
Ji Lin
Fisher Yu
Sergey Levine
Trevor Darrell

title: Reinforcement learning from imperfect demonstrations

venue: arXiv preprint arXiv:1802.05313,

title: The theory of Tikhonov regularization for Fredholm equations

venue: Boston Pitman Publication,

authors:
Tuomas Haarnoja
Aurick Zhou
Kristian Hartikainen
George Tucker
Sehoon Ha
Jie Tan
Vikash Kumar
Henry Zhu
Abhishek Gupta
Pieter Abbeel
Sergey Levine

title: Soft actor-critic algorithms and applications, 2019

authors:
Leslie Pack Kaelbling
Michael L Littman
Andrew W Moore

title: Reinforcement learning: A survey

venue: Journal of artificial intelligence research,

authors:
Rahul Kidambi
Aravind Rajeswaran
Praneeth Netrapalli
Thorsten Joachims

title: MOReL: Model-based offline reinforcement learning

authors:
Vijay R Konda
John N Tsitsiklis

title: Actor-critic algorithms. In Advances in neural information processing systems, pages 1008–1014

authors:
George Konidaris
Scott Kuindersma
Roderic Grupen
Andrew Barto

title: Robot learning from demonstration by constructing skill trees

venue: The International Journal of Robotics Research,

authors:
Aviral Kumar
Justin Fu
Matthew Soh
George Tucker
Sergey Levine

title: Stabilizing off-policy Q-learning via bootstrapping error reduction

venue: In Advances in Neural Information Processing Systems

authors:
Balaji Lakshminarayanan
Alexander Pritzel
Charles Blundell

title: Simple and scalable predictive uncertainty estimation using deep ensembles

venue: Advances in Neural Information Processing Systems

title: Reinforcement learning and control as probabilistic inference: Tutorial and review, 2018

authors:
Timothy P. Lillicrap
Jonathan J. Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

venue: In ICLR (Poster),

authors:
Cong Lu
Philip J. Ball
Jack Parker-Holder
Michael A. Osborne
Stephen J. Roberts

title: Revisiting design choices in model-based offline reinforcement learning, 2021

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin A. Riedmiller

title: Playing atari with deep reinforcement learning

title: Machine learning: A Probabilistic Perspective

authors:
A. Nair
B. McGrew
M. Andrychowicz
W. Zaremba
P. Abbeel

title: Overcoming exploration in reinforcement learning with demonstrations

venue: IEEE International Conference on Robotics and Automation (ICRA),

authors:
Ashvin Nair
Murtaza Dalal
Abhishek Gupta
Sergey Levine

title: Accelerating online reinforcement learning with offline datasets, 2020

authors:
Nicolás Navarro-Guerrero
Cornelius Weber
Pascal Schroeter
Stefan Wermter

title: Real-world reinforcement learning for autonomous humanoid robot docking

venue: Robotics and Autonomous Systems,

authors:
Andrew Y. Ng
Stuart J. Russell

title: Algorithms for inverse reinforcement learning

venue: In Proceedings of the Seventeenth International Conference on Machine Learning,

authors:
Aldo Pacchiano
Jack Parker-Holder
Yunhao Tang
Krzysztof Choromanski
Anna Choromanska
Michael Jordan

title: Learning to score behaviors for guided policy optimization

venue: Proceedings of the 37th International Conference on Machine Learning,

authors:
Xue Bin Peng
Aviral Kumar
Grace Zhang
Sergey Levine

title: Advantage-weighted regression: Simple and scalable off-policy reinforcement learning, 2019

authors:
Jan Peters
Sethu Vijayakumar
Stefan Schaal

title: Natural actor-critic

venue: In European Conference on Machine Learning,

authors:
Joaquin Quiñonero Candela
Carl Edward Rasmussen

title: A unifying view of sparse approximate Gaussian process regression

venue: J. Mach. Learn. Res.,

authors:
Aravind Rajeswaran
Vikash Kumar
Abhishek Gupta
Giulia Vezzani
John Schulman
Emanuel Todorov
Sergey Levine

venue: In Proceedings of Robotics: Science and Systems (RSS),

title: Learning complex dexterous manipulation with deep reinforcement learning and demonstrations, 2018

authors:
Carl Edward Rasmussen
Christopher K.I. Williams

title: Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning)

authors:
Konrad Rawlik
Marc Toussaint
Sethu Vijayakumar

title: On stochastic optimal control and reinforcement learning by approximate inference

venue: Proceedings of Robotics: Science and Systems VIII,

authors:
Michael T Rosenstein
Andrew G Barto
Jennie Si
Andy Barto
Warren Powell

title: Supervised actor-critic reinforcement learning. Learning and Approximate Dynamic Programming: Scaling

venue: Up to the Real World,

authors:
Tim G.J. Rudner
Zonghao Chen
Yarin Gal

title: Rethinking function-space variational inference in Bayesian neural networks

venue: In Third Symposium on Advances in Approximate Bayesian Inference,

authors:
Tim G.J. Rudner
Vitchyr H. Pong
Rowan McAllister
Yarin Gal
Sergey Levine

title: Outcomedriven reinforcement learning via variational inference

authors:
Tim G.J. Rudner
Freddie Bickford Smith
Qixuan Feng
Yee Whye Teh
Yarin Gal

title: Continual learning via function-space variational inference

venue: In ICML Workshop on Theory and Foundations of Continual Learning

title: Learning from demonstration

authors:
John Schulman
Xi Chen
Pieter Abbeel

title: Equivalence between policy gradients and soft Q-learning

venue: arXiv preprint arXiv:1704.06440,

authors:
Noah Siegel
Jost Tobias Springenberg
Felix Berkenkamp
Abbas Abdolmaleki
Michael Neunert
Thomas Lampe
Roland Hafner
Nicolas Heess
Martin Riedmiller

title: Keep doing what worked: Behavior modelling priors for offline reinforcement learning

venue: In International Conference on Learning Representations,

authors:
Alex Smola
Arthur Gretton
Le Song
Bernhard Schölkopf

title: A hilbert space embedding for distributions

venue: Algorithmic Learning Theory,

authors:
Richard S. Sutton
Andrew G. Barto

title: Reinforcement Learning: An Introduction

title: Temporal difference learning and td-gammon

venue: Communications of the ACM,

title: Linearly-solvable markov decision problems

authors:
Joost van Amersfoort
Lewis Smith
Andrew Jesson
Oscar Key
Yarin Gal

title: Improving deterministic uncertainty estimation in deep learning for classification and regression, 2021

authors:
Ke Wang
Geoff Pleiss
Jacob Gardner
Stephen Tyree
Kilian Q Weinberger
Andrew Gordon Wilson

title: Exact Gaussian processes on a million data points

authors:
Yifan Wu
George Tucker
Ofir Nachum

title: Behavior regularized offline reinforcement learning

venue: arXiv preprint arXiv:1911.11361,

authors:
Tianhe Yu
Garrett Thomas
Lantao Yu
Stefano Ermon
James Y Zou
Sergey Levine
Chelsea Finn
Tengyu Ma

title: Mopo: Model-based offline policy optimization

authors:
Tianhe Yu
Aviral Kumar
Rafael Rafailov
Aravind Rajeswaran
Sergey Levine
Chelsea Finn

title: COMBO: Conservative offline model-based policy optimization, 2021

heading: 1 Introduction

text:
Reinforcement learning (RL) [15, 24, 46, 47] is a powerful paradigm for learning complex behaviors. Unfortunately, many modern reinforcement learning algorithms require agents to carry out millions of interactions with their environment to learn desirable behaviors, making them of limited use for a wide range of practical applications that cannot be simulated [8, 28]. This limitation has motivated the study of algorithms that can incorporate pre-collected offline data into the training process either fully offline or with online exploration to improve sample efficiency, performance, and reliability [2, 6, 16, 23, 52, 53]. An important and well-motivated subset of these methods consists of approaches for efficiently incorporating expert demonstrations into the learning process [5, 11, 18, 42].
Reinforcement learning with Kullback-Leibler (KL) regularization is a particularly successful approach for doing so [3, 27, 29, 31, 44, 51]. In KL-regularized reinforcement learning, the standard reinforcement learning objective is augmented by a Kullback-Leibler divergence term that penalizes dissimilarity between the online policy and a behavioral reference policy derived from expert demonstrations. The resulting regularized objective pulls the agent’s online policy towards the behavioral reference policy while also allowing it to improve upon the behavioral reference policy by exploring and interacting with the environment. Recent advances that leverage explicit or implicit KL-regularized objectives, such as BRAC [51], ABM [44], and AWAC [27], have shown that KLregularized reinforcement learning from expert demonstrations is able to significantly improve the sample efficiency of online training and reliably solve challenging environments previously unsolved by standard deep reinforcement learning algorithms.
∗Equal contribution. † Corresponding author: tim.rudner@cs.ox.ac.uk.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Contributions. In this paper, we show that despite some empirical success, KL-regularized reinforcement learning from expert demonstrations can suffer from previously unrecognized pathologies that lead to instability and sub-optimality in online learning. To summarize, our core contributions are as follows: • We illustrate empirically that commonly used classes of parametric behavioral policies experi-
ence a collapse in predictive variance about states away from the expert demonstrations. • We demonstrate theoretically and empirically that KL-regularized reinforcement learning al-
gorithms can suffer from pathological training dynamics in online learning when regularized against behavioral policies that exhibit such a collapse in predictive variance. • We show that the pathology can be remedied by non-parametric behavioral policies, whose
predictive variances are well-calibrated and guaranteed not to collapse about previously unseen states, and that fixing the pathology results in online policies that significantly outperform stateof-the-art approaches on a range of challenging locomotion and dexterous hand manipulation tasks.
The left panel of Figure 1 shows an example of the collapse in predictive variance away from the expert trajectories in parametric behavioral policies. In contrast, the right panel of Figure 1 shows the predictive variance of a non-parametric behavioral policy, which—unlike in the case of the parametric policy—increases off the expert trajectories. By avoiding the pathology, we obtain a stable and reliable approach to sample-efficient reinforcement learning, applicable to a wide range of reinforcement learning algorithms that leverage KL-regularized objectives.2

heading: 2 Background

text:
We consider the standard reinforcement learning setting where an agent interacts with a discounted Markov Decision Process (MDP) [46] given by a 5-tuple (S,A, p, r, γ), where S and A are the state and action spaces, p(· | st,at) are the transition dynamics, r(st,at) is the reward function, and γ is a discount factor. ρπ(τt) denotes the state–action trajectory distribution from time t induced by a policy π(· | st). The discounted return from time step t is given by R(τt) = ∑∞ k=t γ
kr(sk,ak) for t ∈ N0. The standard reinforcement learning objective to be maximized is the expected discounted return Jπ(τ0) = Eρπ(τ0)[R(τ0)] under the policy trajectory distribution.

heading: 2.1 Improving and Accelerating Online Training via Behavioral Cloning

text:
We consider settings where we have a set of expert demonstrations without reward, D0 = {(sn,an)}Nn=1 = {S̄, Ā}, which we would like to use to speed up and improve online learn-
2Code and visualizations of our results can be found at https://sites.google.com/view/nppac.
ing [5, 42]. A standard approach for turning expert trajectories into a policy is behavioral cloning [1, 4] which involves learning a mapping from states in the expert demonstrations to their corresponding actions, that is, π0 : S → A. As such, behavioral cloning does not assume or require access to a reward function and only involves learning a mapping from states to action in a supervised fashion.
Since expert demonstrations are costly to obtain and often only available in small number, behavioral cloning alone is typically insufficient for agents to learn good policies in complex environments and has to be complemented by a method that enables the learner to build on the cloned behavior by interacting with the environment. A particularly successful and popular class of algorithms used for incorporating behavioral policies into online training is KL-regularized reinforcement learning [10, 37, 43, 48].

heading: 2.2 KL-Regularized Objectives in Reinforcement Learning

text:
KL-regularized reinforcement learning modifies the standard reinforcement learning objective by augmenting the return with a negative KL divergence term from the learned policy π to a reference policy π0, given a temperature parameter α. The resulting discounted return from time step t ∈ N0 is then given by
R̃(τt) = ∞∑ k=t γk [ r(sk,ak)− αDKL(π(· | sk) ‖ π0(· | sk)) ] (1)
and the reinforcement learning objective becomes J̃π(τ0) = Eρπ(τ0)[R̃(τ0)]. When the reference policy π0 is given by a uniform distribution, we recover the entropy-regularized reinforcement learning objective used in Soft Actor–Critic (SAC) [13] up to an additive constant.
Under a uniform reference policy π0, the resulting objective encourages exploration, while also choosing high-reward actions. In contrast, when π0 is non-uniform, the agent is discouraged to explore areas of the state space S where the variance of π0(· | s) is low (i.e., more certain) and encouraged to explore areas of the state space where the variance of π0(· | s) is high. The KLregularized reinforcement learning objective can be optimized via policy–gradient and actor–critic algorithms.

heading: 2.3 KL-Regularized Actor–Critic

text:
An optimal policy π that maximizes the expected KL-augmented discounted return J̃π can be learned by directly optimizing the policy gradient ∇πJ̃π. However, this policy gradient estimator exhibits high variance, which can lead to unstable learning. Actor–critic algorithms [7, 17, 32, 38] attempt to reduce this variance by making use of the state value function V π(st) = Eρπ(τt)[R̃(τt) | st] or the state–action value function Qπ(st,at) = Eρπ(τt)[R̃(τt) | st,at] to stabilize training. Given a reference policy π0(at | st), the state value function can be shown to satisfy the modified Bellman equation
V π(st) =̇ Eat∼π(·|st)[Q π(st,at)]− αDKL ( π(· | st) ||π0(· | st) ) with a recursively defined Q-function
Qπ(st,at) =̇ r(st,at) + γ Est+1∼p(·|st,at)[V π(st+1)].
Instead of directly optimizing the objective function J̃π via the policy gradient, actor–critic methods alternate between policy evaluation and policy improvement [7, 13]:
Policy Evaluation. During the policy evaluation step, Qπθ (s,a), parameterized by parameters θ, is trained by minimizing the Bellman residual
JQ(θ) =̇ E(st,at)∼D [ (Qθ(st,at)− (r(st,at) + γEst+1∼p(·|st,at)[Vθ̄(st+1)]))2 ] , (2)
where D is a replay buffer and θ̄ is a stabilizing moving average of parameters. Policy Improvement. In the policy improvement step, the policy πφ, parameterized by parameters φ, is updated towards the exponential of the KL-augmented Q-function,
Jπ(φ) =̇ Est∼D [αDKL(πφ(· | st) ‖ π0(· | st))]− Est∼D [ Eat∼πφ(·|st) [Qθ(st,at)] ] , (3)
with states sampled from a replay buffer D and actions sampled from the parameterized online policy πφ. The following sections will focus on the policy improvement objective and how certain types of references policies can lead to pathologies when optimizing Jπ(φ) with respect to φ.

heading: 3 Identifying the Pathology

text: In this section, we investigate the effect of KL-regularization on the training dynamics. To do so, we first consider the properties of the KL divergence to identify a potential failure mode for KL-regularized reinforcement learning. Next, we consider parametric Gaussian behavioral reference policies commonly used in practice for continuous control tasks [13, 51] and show that for Gaussian behavioral reference policies with small predictive variance, the policy improvement objective suffers from exploding gradients with respect to the policy parameters φ. We confirm that this failure occurs empirically and demonstrate that it results in slow, unstable, and suboptimal online learning. Lastly, we show that various regularization techniques used for estimating behavioral policies are unable to prevent this failure and also lead to suboptimal online policies.

heading: 3.1 When Are KL-Regularized Reinforcement Learning Objectives Meaningful?

text:
We start by considering the properties of the KL divergence and discuss how these properties can lead to potential failure modes in KL-regularized objectives. A well-known property of KL-regularized objectives in the variational inference literature is the occurrence of singularities when the support of one distribution is not contained in the support of the other.
To illustrate this problem, we consider the case of Gaussian behavioral and online policies commonly used in practice. Mathematically, the KL divergence between two full Gaussian distributions is always finite and well-defined. Hence, we might hope KL-regularized reinforcement learning with Gaussian behavioral and online policies to be unaffected by the failure mode described above. However, the support of a Gaussian online policy πφ(· | st) will not be contained in the support of a behavioral reference policy π0(· | st) as the predictive variance σ20(st) tends to zero, and hence DKL(πφ(· | st) ‖ π0(· | st)) → ∞ as σ20(st) → 0. In other words, as the variance of a behavioral reference policy tends to zero and the behavioral distribution becomes degenerate, the KL divergence blows up to infinity [25]. While in practice, Gaussian behavioral policy would not operate in the limit of zero variance, the functional form of the KL divergence between (univariate) Gaussians,
DKL(πφ(· | st) ‖ π0(· | st)) ∝ log σ0(st)
σφ(st) + σ2φ(st) + (µφ(st)− µ0(st))2 2σ20(st) ,
implies a continuous, quadratic increase in the magnitude of the divergence as σ0(st) decreases, further exacerbated by a large difference in predictive means, |µφ(st)− µ0(st)|. As a result, for Gaussian behavioral reference policies π0(· | st) that assign very low probability to sets of points in sample space far away from the distribution’s mean µ0(st), computing the KL divergence can result in divergence values so large to cause numerical instabilities and arithmetic overflow. Hence, even for a suitably chosen behavioral reference policy class, vanishingly small behavioral reference policy predictive variances can cause the KL divergence to ‘blow up’ and cause numerical issues at evaluation points far away from states in the expert demonstrations.
One way to address this failure mode may be to lower-bound the output of the variance network (e.g., by adding a small constant bias). However, placing a floor on the predictive variance of the behavioral reference policy is not sufficient to encourage effective learning. While it would prevent the KL divergence from blowing up, it would also lead to poor gradient signals, as well-calibrated predictive variance estimates that increase on states far away from the expert trajectories are necessary to keep the KL penalty from pulling the predictive mean of the online policy towards poor behavioral reference policy predictive means on states off the expert trajectories. Another possible solution could be to use heavy-tailed behavioral reference policies distributions, for example, Laplace distributions, to avoid pathological training dynamics. However, in Appendix B.3 we show that Laplace behavioral reference policies also suffer from pathological training dynamics, albeit less severely.
In the following sections, we explain how an explosion in DKL(πφ(· | st) ‖ π0(· | st)) caused by small σ20(st) affects the gradients of Jπ(φ) in KL-regularized RL and discuss of how and why σ 2 0(st) may tend to zero in practice.

heading: 3.2 Exploding Gradients in KL-Regularized Reinforcement Learning Objectives

text:
To understand how small predictive variances in behavioral reference policies can affect—and possibly destabilize—online training in KL-regularized RL, we consider the contribution of the behavioral
reference policy’s variance to the gradient of the policy objective in Equation (3). Compared to entropy-regularized actor–critic methods (SAC, Haarnoja et al. [13]), which implicitly regularize against a uniform policy, the gradient estimator ∇̂φJπ(φ) in KL-regularized RL gains an extra scaling term ∇at log π0(at | st), the gradient of the prior log-density evaluated actions at ∼ πφ(· | s): Proposition 1 (Exploding Gradients in KL-Regularized RL). Let π0(· | s) be a Gaussian behavioral reference policy with mean µ0(st) and variance σ20(st), and let πφ(· | s) be an online policy with reparameterization at = fφ( t; st) and random vector t. The gradient of the policy loss with respect to the online policy’s parameters φ is then given by
∇̂φJπ(φ) = ( α∇at log πφ(at | st)− α∇at log π0(at | st) −∇atQ(st,at) ) ∇φfφ( t; st) + α∇φ log πφ(at | st)
(4)
with ∇at log π0(at | st) = −at−µ0(st)σ20(st) . For fixed |at − µ0(st)|, ∇at log π0(at|st) grows as O(σ−20 (st)); thus,
| ∇̂φJπ(φ) | → ∞ as σ20(st)→ 0 whenever ∇φfφ( t; st) 6= 0.
Proof. See Appendix A.1.
This result formalizes the intuition presented in Section 3.1 that a behavioral reference policy with a sufficiently small predictive variance may cause KL-regularized reinforcement learning to suffer from pathological training dynamics in gradient-based optimization. The smaller the behavioral reference policy’s predictive variance, the more sensitive the policy objective’s gradients will be to differences in the means of the online and behavioral reference policies. As a result, for behavioral reference policies with small predictive variance, the KL divergence will heavily penalize online policies whose predictive means diverge from the predictive means of the behavioral policy—even in regions of the state space away from the expert trajectory where the behavioral policy’s mean prediction is poor.

heading: 3.3 Predictive Uncertainty Collapse Under Parametric Policies

text:
The most commonly used method for estimating behavioral policies is maximum likelihood estimation (MLE) [44, 51], where we seek π0 =̇ πψ? with ψ? =̇ arg maxψ { E(s,a)∼D0 [log πψ(a | s)] } for a parametric behavioral policy πψ. In practice, πψ is often assumed to be Gaussian, πψ(· | s) = N (µψ(s),σ2ψ(s)), with µψ(s) and σ2ψ(s) parameterized by a neural network. While maximizing the likelihood of the expert trajectories under the behavioral policy is a sensible choice for behavioral cloning, the limited capacity of the neural network parameterization can produce unwanted behaviors in the resulting policy. The maximum likelihood objective ensures that the behavioral policy’s predictive mean reflects the expert’s actions and the predictive variance the (aleatoric) uncertainty inherent in the expert trajectories.
However, the maximum likelihood objective encourages parametric policies to use their model capacity toward fitting the expert demonstrations and reflecting the aleatoric uncertainty in the data. As a result, for states off the expert trajectories, the policy can become degenerate and collapse to point predictions instead of providing meaningful predictive variance estimates that reflect that the behavioral policy ought to be highly uncertain about its predictions in previously unseen regions of the state space. Similar behaviors are well-known in parametric probabilistic models and welldocumented in the approximate Bayesian inference literature [33, 39].
0 2 4 6 8 10 Epochs
10−3
10−1
σ 2 ψ (s
)
Validation Variance
Validation Log-Likelihood 0
2 log π ψ (Ā | S̄
)
tently decreases during training. As shown in Proposition 1, such a collapse in predictive variance can
result in pathological training dynamics in KL-regularized online learning—steering the online policy towards suboptimal trajectories in regions of the state space far away from the expert demonstrations and deteriorating performance.
Effect of regularization on uncertainty collapse. To prevent a collapse in the behavioral policy’s predictive variance, prior work proposed adding entropy or Tikhonov regularization to the MLE objective [51]. However, doing so does not succeed in preventing a collapse in predictive variance off the expert demonstration trajectories, as we show in Appendix A.3. Deep ensembles [20], whose predictive mean and variance are computed from the predictive means and variances of multiple Gaussian neural networks, are a widely used method for uncertainty quantification in regression settings. However, model ensembling can be costly and unreliable, as it requires training multiple neural networks from scratch and does not guarantee well-calibrated uncertainty estimates [39, 49]. We provide visualizations in Appendix B.5 which show that ensembling multiple neural network policies does not fully prevent a collapse in predictive variance.

heading: 3.4 Empirical Confirmation of Uncertainty Collapse

text:
To confirm Proposition 1 empirically and assess the effect of the collapse in predictive variance on the performance of KL-regularized RL, we perform an ablation study where we fix the predictive mean function of a behavioral policy to a mean function that attains 60% of the optimal performance and vary the magnitude of the policy’s predictive variance. Specifically, we set the behavioral policy’s predictive variance to different constant values in the set {1× 10−3, 5× 10−3, 1× 10−2} (following a similar implementation in Nair et al. [27]).3 The results of this experiment are shown in Figure 3, which shows the average returns, the KL divergence, and the average absolute gradients of the policy loss over training. The plots confirm that as the predictive variance of the offline behavioral policy tends to zero, the KL terms and average policy gradient magnitude explode as implied by Proposition 1, leading to unstable training and a collapse or dampening in average returns.
In other words, even for behavioral policies with accurate predictive means, smaller predictive variances slow down or even entirely prevent learning good behavioral policies. This observation confirms that the pathology identified in Proposition 1 occurs in practice and that it can have a significant impact on KL-regularized RL from expert demonstrations, calling into question the usefulness of KL regularization as a means for accelerating and improving online training. In Appendix B.1, we show that an analogous relationship exists for the gradients of the Q-function loss.
3We attempted to use smaller values, but the gradients grew too large and caused arithmetic overflow.

heading: 4 Fixing the Pathology

text: In order to address the collapse in predictive uncertainty for behavioral policies parameterized by a neural network trained via MLE, we specify a non-parametric behavioral policy whose predictive variance is guaranteed not to collapse about previously unseen states. Noting that KL-regularized RL with a behavioral policy can be viewed as approximate Bayesian inference with an empirical prior policy [13, 21, 40], we propose Non-Parametric Prior Actor–Critic (N-PPAC), an off-policy temporal difference algorithm for improved, accelerated, and stable online learning with behavioral policies.

heading: 4.1 Non-Parametric Gaussian Processes Behavioral Policies

text:
Gaussian processes (GPs) [36] are models over functions defined by a mean m(·) and covariance function k(·, ·). When defined in terms of a non-parametric covariance function, that is, a covariance function constructed from infinitely many basis functions, we obtain a non-degenerate GP, which has sufficient capacity to prevent a collapse in predictive uncertainty away from the training data. Unlike parametric models, whose capacity is limited by their parameterization, a non-parametric model’s capacity increases with the amount of training data.
Considering a non-parametric GP behavioral policy, π0(· | s), with A | s ∼ π0(· | s) = GP ( m(s), k(s, s′) ) , (5)
we can obtain a non-degenerate posterior distribution over actions conditioned on the offline data D0 = {S̄, Ā} with actions sampled according to the
A | s,D0 ∼ π0(· | s,D0) = GP ( µ0(s),Σ0(s, s ′) ) , (6)
with
µ(s)=m(s) + k(s, S̄)k(S̄, S̄)−1(Ā−m(Ā)) and Σ(s, s′)=k(s, s′) + k(s, S̄)k(S̄, S̄)−1k(S̄, s′). To obtain this posterior distribution, we perform exact Bayesian inference, which naively scales as O(N3) in the number of training points N , but Wang et al. [50] show that exact inference in GP regression can be scaled to N > 1, 000, 000. Since expert demonstrations usually contain less than 100k datapoints, non-parametric GP behavioral policies are applicable to a wide array of real-world tasks. For an empirical evaluation of the time complexity of using a GP prior, see Section 5.5.
Figure 1 confirms that the non-parametric GP’s predictive variance is well-calibrated: It is small in magnitude in regions of the state space near the expert trajectories and large in magnitude in other regions of the state space. While actor–critic algorithms like SAC implicitly use a uniform prior to explore the state space, using a behavioral policy with a well-calibrated predictive variance has the benefit that in regions of the state space close to the expert demonstrations the online policy learns to match the expert, while elsewhere the predictive variance increases and encourages exploration.
Algorithmic details. In our experiments, we use a KL-regularized objective with a standard actor– critic implementation and Double DQN [14]. Pseudocode is provided in (Appendix C.1).

heading: 5 Empirical Evaluation

text:
We carry out a comparative empirical evaluation of our proposed approach vis-à-vis related methods that integrate offline data into online training. We provide a detailed description of the algorithms we compare against in Appendix A.4. We perform experiments on the MuJoCo benchmark suite and the substantially more challenging dexterous hand manipulation suite with sparse rewards.
We show that KL-regularized RL with a non-parametric behavioral reference policy can rapidly learn to solve difficult high-dimensional continuous control problems given only a small set of expert demonstrations and (often significantly) outperforms state-of-the-art methods, including ones that use offline reward information—which our approach does not require. Furthermore, we demonstrate that the GP behavioral policy’s predictive variance is crucial for KL-regularized objectives to learn good online policies from expert demonstrations. Finally, we perform ablation studies that illustrate that non-parametric GP behavioral reference policies also outperform parametric behavioral reference policies with improved uncertainty quantification, such as deep ensembles and Bayesian neural
networks (BNNs) with Monte Carlo dropout, and that the difference between non-parametric and parametric models is exacerbated the fewer expert demonstrations are available. We use the expert data from Nair et al. [27], every experiment uses six random seeds, and we use a fixed KL-temperature for each environment class. For further implementation details, see Appendix C.2.

heading: 5.1 Environments

text:
MuJoCo locomotion tasks. We evaluate N-PPAC on three representative tasks: “Ant-v2”, “HalfCheetah-v2”, and “Walker2d-v2”. For each task, we use 15 demonstration trajectories collected by a pre-trained expert, each containing 1,000 steps. The behavioral policy is specified as the posterior distribution of a GP with a squared exponential kernel, which is well-suited for modeling smooth functions.
Dexterous hand manipulation tasks. Real-world robot learning is a setting where human demonstration data is readily available, and many deep RL approaches fail to learn efficiently. We study this setting in a suite of challenging dexterous manipulation tasks [35] using a 28-DoF five-fingered simulated ADROIT hand. The tasks simulate challenges common to real-world settings with highdimensional action spaces, complex physics, and a large number of intermittent contact forces. We consider two tasks in particular: in-hand rotation of a pen to match a target and opening a door by unlatching and pulling a handle. We use binary rewards for task completion, which is significantly more challenging than the original setting considered in Rajeswaran et al. [35]. 25 expert demonstrations were provided for each task, each consisting of 200 environment steps which are not fully optimal but do successfully solve the task. The behavioral policy is specified as the posterior distribution of a GP with a Matérn kernel, which is more suitable for modeling non-smooth data.

heading: 5.2 Results

text:
On MuJoCo environments, KL-regularized RL with a non-parametric behavioral policy consistently outperforms all related methods across all three tasks, successfully accelerating learning from offline data, as shown in Figure 4. Most notably, it outperforms methods such as AWAC [27]—the previous state-of-the-art—which attempts to eschew the problem of learning behavioral policies but instead uses an implicit constraint. Our approach, N-PPAC, exhibits an increase in stability and higher returns compared to comparable methods such as ABM and BRAC that explicitly regularize the online policy against a parametric behavioral policy and plateau at suboptimal performance levels as they are being forced to copy poor actions from the behavioral policy away from the expert data. In contrast, using a non-parametric behavioral policy allows us to avoid such undesirable behavior.
On dexterous hand manipulation environments, KL-regularized RL with a non-parametric behavioral policy performs on par or outperforms all related methods on both tasks, as shown in Figure 5. Most notably, on the door opening task, it achieves a stable success rate of 90% within only 100,000 environment interactions For comparison, AWAC requires 4× as many environment interactions to
achieve the same performance and is significantly less stable, while most other methods fail to learn any meaningful behaviors.
Alternative divergence metrics underperform KL-regularization. KL-regularized RL with a non-parametric behavioral policy consistently outperforms methods that use alternative divergence metrics, as shown in the bottom plots of Figures 4 and 5.

heading: 5.3 Can the Pathology Be Fixed by Improved Parametric Uncertainty Quantification?

text:
line policy success rates. We consider the challenging “door-binary-v0” environment for this ablation study.
Parametric uncertainty quantification is insufficient. Figure 5 shows that parametric variance functions result in online policies that only achieve success rates of up to 20% and eventually deteriorate, whereas the non-parametric variance yields an online policy that achieves a success rate of nearly 100%. This finding shows that commonly used uncertainty quantification methods, such as deep ensembles or BNNs with Monte Carlo dropout, do not generate sufficiently well-calibrated uncertainty estimates to remedy the pathology, and better methods may be needed [9, 39, 41].
Lower-bounding the predictive variance does not remedy the pathology. The predictive variance of all MLE-based and ensemble behavioral reference policies in all experiments are bounded away from zero at a minimum value of ≈ 10−2. Hence, setting a floor on the variance is not sufficient to prevent pathological training dynamics. This result further demonstrates the importance of accurate predictive variance estimation in allowing the online policy to match expert actions in regions of the state space with low behavioral policy predictive variance and explore elsewhere.

heading: 5.4 Can a Single Expert Demonstration Be Sufficient to Accelerate Online Training?

text:
To assess the usefulness of nonparametric behavioral reference policies in settings where only few expert demonstrations are available, we investigate whether the difference in performance between online policies trained with non-parametric and parametric behavioral reference policies, respectively, is exacerbated the fewer expert demonstrations are available. To answer this question, we consider the “HalfCheetah-v2” environment and compare online policies trained with different behavioral reference
policies—non-parametric GPs, deep ensembles, and BNNs with Monte Carlo dropout—estimated either from 15 expert demonstrations (i.e., 15 state–action trajectories, containing 15,000 samples) or from a single expert demonstration (i.e., a single state–action trajectory, containing 1,000 samples).

heading: A single expert demonstration is sufficient for non-parametric behavioral reference policies.

text: Figure 7 shows the returns for online policies trained with behavioral reference policies estimated from the full dataset (top plot) and from only a single expert state–action trajectory (bottom plot). On the full dataset, we find that all three methods are competitive and improve on the prior stateof-the-art but that the GP behavioral policy leads to the highest return. Remarkably, non-parametric GP behavioral policies perform just as well with only a single expert demonstration as with all 15 (i.e., with 1,000 data points, instead of 15,000 data points). These results further emphasizes the usefulness of non-parametric behavioral policies when accelerating online training with expert demonstrations—even when only very few expert demonstrations are available.

heading: 5.5 Are Non-Parametric GP Behavioral Reference Policies Too Computationally Expensive?

text: Table 1 presents the time complexity of KL-regularized RL under non-parametric GP and parametric neural network behavioral reference policies, as measured by the average time elapsed per epoch on the “door-binary-v0” and “HalfCheetah-v2” environments. One epoch of online training on “doorbinary-v0” and “HalfCheetah-v2” requires computing the KL divergence over 1,000 mini-batches of size 256 and 1,024, respectively. The time complexity of evaluating the log-density of a GP behavioral reference policy—needed for computing gradients of the KL divergence during online training—scales quadratically in the number of training data points and linearly in the dimensionality of the state and action space, respectively. As can be seen in Table 1, non-parametric GP behavioral reference policies only lead to a modest increase in the time needed to complete one epoch of training while resulting in significantly improved performance as shown in Figures 4 and 5.

heading: 6 Conclusion

text:
We identified a previously unrecognized pathology in KL-regularized RL from expert demonstrations and showed that this pathology can significantly impede and even entirely prevent online learning. To remedy the pathology, we proposed the use of non-parametric behavioral reference policies, which we showed can significantly accelerate and improve online learning and yield online policies that (often significantly) outperform current state-of-the-art methods on challenging continuous control tasks. We hope that this work will encourage further research into better model classes for deep reinforcement learning algorithms, including and especially for reinforcement from image inputs.
Acknowledgments and Disclosure of Funding
We thank Ashvin Nair for sharing his code and results, as well as for providing helpful insights about the dexterous hand manipulation suite. We also thank Clare Lyle, Charline Le Lan, and Angelos Filos for detailed feedback on an early draft of this paper, Avi Singh for early discussions about behavioral cloning in entropy-regularized RL, and Tim Pearce for a useful discussion on the role of good models in RL. TGJR and CL are funded by the Engineering and Physical Sciences Research Council (EPSRC). TGJR is also funded by the Rhodes Trust and by a Qualcomm Innovation Fellowship. We gratefully acknowledge donations of computing resources by the Alan Turing Institute.

title: On Pathologies in KL-Regularized Reinforcement Learning from Expert Demonstrations


summaries: In this paper, the authors study the generalization error of kernel regression in a teacher-student scenario where the kernels are obtained as NTK of either one-hidden layer locally-connected NNs or convolutional NNs. They consider the teacher as a Gaussian random field of covariance the same kernel as the student kernel but with different parameters, and proceed to characterize the learning curve exponents. Based on a decomposition of the two kernels in orthonormal basis functions, they use recent (non-rigorous) statistical physics predictions to deduce an exponent that can be shown rigorously to be an upper bound in some cases. This exponent does not depend on the ambient dimension d, only on the patch size, and is the same for the two kernels. The authors deduce that locality is the important property that breaks the curse of dimensionality and notice that adding the invariance by translation only lower the prefactor.  Finally, using a Gaussian universality assumption and a recent framework, they prove a lower bound on the learning curve exponent.  They further check their predictions in numerical experiments on synthetic data.

summaries: # Post Rebuttal:  I partly accept the claims of the authors in the rebuttal and have decided to raise my score a little bit to reflect that. I still believe the paper would benefit greatly from clarifications. In particular, I advise the authors to incorporate the changes mentioned in their response to Remarks 1-2 in the rebuttal, as these strengthen the paper in my opinion. As for Remarks 3-4, I disagree with the authors' claim; my point that convolutional neural networks do not provide any benefit over other simpler hypothesis classes in the regime of lazy training still stands and I strongly encourage the authors to omit any reference to neural networks as motivation for studying the problem. I find this reference to be too artificial and somewhat forced.  Lastly, I would like to wish the authors the best of luck in the future.    # Original Review:  The paper studies the expected generalization error when learning in a teacher-student setting where the teacher is a Gaussian random field and the student is a kernel exhibiting a certain convolutional structure. It is shown that under strong assumptions the expected generalization error decays at a rate which does not depend on the input dimension but rather on the filter size of the student. Additionally, experiments are performed to corroborate the theoretical findings in the paper.

summaries: This paper studies the two elements of CNNS, 1. local patch; 2. translation-invariant. Under a teacher-student framework for kernel regression, the authors conclude that (under reasonable assumptions), it is the locality of CNNs that defeats the curse of dimensionality. The exponent $\beta$ in the learning curve (with respect to the sample size) is studied theoretically and empirically verified.

summaries: The authors proved that the generalization error for a CNN can be made independent of the data dimension under certain assumptions. They study the problem in a teacher-student framework and the test error proportional to $P^{-\beta}$ with P to be the training set and $\beta$ to be only dependent on the local kernel size of student network. The authors empirically validate this finding. Furthermore they showed that similar learning curve exponent achieved in the ridgeless case can be achieved in kernel ridge regression with decreasing ridge coefficient.

abstractText: Convolutional neural networks perform a local and translationally-invariant treatment of the data: quantifying which of these two aspects is central to their success remains a challenge. We study this problem within a teacher-student framework for kernel regression, using ‘convolutional’ kernels inspired by the neural tangent kernel of simple convolutional architectures of given filter size. Using heuristic methods from physics, we find in the ridgeless case that locality is key in determining the learning curve exponent β (that relates the test error t ∼ P−β to the size of the training set P ), whereas translational invariance is not. In particular, if the filter size of the teacher t is smaller than that of the student s, β is a function of s only and does not depend on the input dimension. We confirm our predictions on β empirically. We conclude by proving, under a natural universality assumption, that performing kernel regression with a ridge that decreases with the size of the training set leads to similar learning curve exponents to those we obtain in the ridgeless case.

authors:
Ulrike von Luxburg
Olivier Bousquet

title: Distance-based classification with lipschitz functions

venue: Journal of Machine Learning Research,

authors:
Joel Hestness
Sharan Narang
Newsha Ardalani
Gregory Diamos
Heewoo Jun
Hassan Kianinejad
Md Patwary
Mostofa Ali
Yang Yang
Yanqi Zhou

title: Deep learning scaling is predictable, empirically

venue: arXiv preprint arXiv:1712.00409,

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Advances in neural information processing systems,

authors:
Stefano Spigler
Mario Geiger
Matthieu Wyart

title: Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm

venue: Journal of Statistical Mechanics: Theory and Experiment,

title: Recognition-by-components: a theory of human image understanding

venue: Psychological review,

authors:
Tomaso Poggio
Hrushikesh Mhaskar
Lorenzo Rosasco
Brando Miranda
Qianli Liao

title: Why and when can deep-but not shallow-networks avoid the curse of dimensionality: a review

venue: International Journal of Automation and Computing,

authors:
Arturo Deza
Qianli Liao
Andrzej Banburski
Tomaso Poggio

title: Hierarchically compositional tasks and deep convolutional networks, 2020

title: On approximation in deep convolutional networks: a kernel perspective, 2021

title: Towards learning convolutions from scratch

venue: Advances in Neural Information Processing Systems,

title: Cognitron: A self-organizing multilayered neural network

venue: Biological cybernetics,

title: Generalization and network design strategies

venue: Connectionism in perspective,

authors:
Arthur Jacot
Franck Gabriel
Clément Hongler

title: Neural tangent kernel: Convergence and generalization in neural networks

venue: In Proceedings of the 32Nd International Conference on Neural Information Processing Systems,

authors:
Simon S. Du
Xiyu Zhai
Barnabas Poczos
Aarti Singh

title: Gradient descent provably optimizes over-parameterized neural networks

authors:
Jaehoon Lee
Lechao Xiao
Samuel Schoenholz
Yasaman Bahri
Roman Novak
Jascha Sohl- Dickstein
Jeffrey Pennington

title: Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent

venue: In Advances in Neural Information Processing Systems

authors:
Sanjeev Arora
Simon S Du
Wei Hu
Zhiyuan Li
Russ R Salakhutdinov
Ruosong Wang

title: On Exact Computation with an Infinitely Wide Neural Net

authors:
Lenaic Chizat
Edouard Oyallon
Francis Bach

title: On lazy training in differentiable programming

venue: In Advances in Neural Information Processing Systems,

authors:
Blake Bordelon
Abdulkadir Canatar
Cengiz Pehlevan

title: Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks

venue: In International Conference on Machine Learning,

authors:
Abdulkadir Canatar
Blake Bordelon
Cengiz Pehlevan

title: Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks

venue: Nature Communications,

authors:
Bruno Loureiro
Cédric Gerbelot
Hugo Cui
Sebastian Goldt
Florent Krzakala
Marc Mézard
Lenka Zdeborová

title: Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model

venue: arXiv preprint arXiv:2102.08127,

authors:
Charles A Micchelli
Grace Wahba

title: Design problems for optimal surface interpolation

venue: Technical report, WISCONSIN UNIV-MADISON DEPT OF STATISTICS,

authors:
Arthur Jacot
Berfin Simsek
Francesco Spadaro
Clement Hongler
Franck Gabriel

title: Kernel alignment risk estimator: Risk prediction from training data

authors:
Risi Kondor
Shubhendu Trivedi

title: On the generalization of equivariance and convolution in neural networks to the action of compact groups

authors:
H.H. Zhou
Y. Xiong
V. Singh

title: Building bayesian neural networks with blocks: On structure, interpretability and uncertainty

venue: arXiv preprint,

authors:
Tommaso Poggio
Andrzej Banburski
Qianli Liao

title: Theoretical issues in deep networks

venue: Proceedings of the National Academy of Sciences,

authors:
Eran Malach
Shai Shalev-Shwartz

title: Computational separation between convolutional and fully-connected networks

title: End-to-end kernel learning with supervised convolutional kernel networks

venue: arXiv preprint arXiv:1605.06265,

authors:
Alberto Bietti
Julien Mairal

title: On the inductive bias of neural tangent kernels

venue: arXiv preprint arXiv:1905.12173,

authors:
Song Mei
Theodor Misiakiewicz
Andrea Montanari

title: Learning with invariances in random features and kernel models, 2021

authors:
Motonobu Kanagawa
Philipp Hennig
Dino Sejdinovic
Bharath K Sriperumbudur

title: Gaussian processes and kernel methods: A review on connections and equivalences

venue: arXiv preprint arXiv:1807.02582,

title: Breaking the curse of dimensionality with convex neural networks

venue: The Journal of Machine Learning Research,

authors:
Jonas Paccolat
Stefano Spigler
Matthieu Wyart

title: How isotropic kernels perform on simple invariants

venue: Machine Learning: Science and Technology,

authors:
Amnon Geifman
Abhay Yadav
Yoni Kasten
Meirav Galun
David Jacobs
Basri Ronen

title: On the similarity between the laplace and neural tangent kernels

title: Bayesian Learning for Neural Networks

title: Computing with infinite networks. Advances in neural information processing systems, pages

authors:
Jaehoon Lee
Yasaman Bahri
Roman Novak
Samuel S Schoenholz
Jeffrey Pennington
Jascha Sohl-Dickstein

title: Deep neural networks as gaussian processes

venue: arXiv preprint arXiv:1711.00165,

authors:
Youngmin Cho
Lawrence Saul

title: Kernel methods for deep learning

authors:
Bernhard Scholkopf
Alexander J Smola

title: Learning with kernels: support vector machines, regularization, optimization, and beyond

venue: MIT press,

title: Asymptotic behavior of the eigenvalues of certain integral equations

venue: ii. Archive for Rational Mechanics and Analysis,

authors:
Marc Mézard
Giorgio Parisi
Miguel Virasoro

title: Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9

venue: World Scientific Publishing Company,

authors:
Marc Potters
Jean-Philippe Bouchaud

title: A First Course in Random Matrix Theory: For Physicists, Engineers and Data Scientists

authors:
Arthur Jacot
Berfin Simsek
Francesco Spadaro
Clément Hongler
Franck Gabriel

title: Implicit regularization of random feature models

heading: 1 Introduction

text:
Deep Convolutional Neural Networks (CNNs) are widely recognised as the engine of the latest successes of deep learning methods, yet such a success is surprising. Indeed, any supervised learning model suffers in principle from the curse of dimensionality: under minimal assumptions on the function to be learnt, achieving a fixed target generalisation error requires a number of training samples P which grows exponentially with the dimensionality d of input data [1], i.e. (P ) ∼ P−1/d. Nonetheless, empirical evidence shows that the curse of dimensionality is beaten in practice [2, 3, 4], with (P ) ∼ P−β , β 1/d. (1) CNNs, in particular, achieve excellent performances on high-dimensional tasks such as image classification on ImageNet with state-of-the-art architectures, for which β ≈ [0.3, 0.5] [2]. Natural data must then possess additional structures that make them learnable. A classical idea [5] ascribes the success of recognition systems to the compositionality of data, i.e. the fact that objects are made of features, themselves made of sub-features [6, 7, 8]. In this view, the locality of CNNs plays a key role for their performance, as supported by empirical observations [9]. Yet, there is no clear
∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
analytical understanding of the relationship between the compositionality of the data and learning curves.
In order to study this relationship quantitively, we introduce a teacher-student framework for kernel regression, where the function to be learnt takes one of the following two forms:
fLC(x) = ∑ i∈P gi(xi), f CN (x) = ∑ i∈P g(xi). (2)
Here, x is a d-dimensional input and xi denotes the i-th t-dimensional patch of x, xi = (xi, . . . , xi+t−1). i ranges in a subset P of {1, . . . , d}. The gi’s and g are random functions of t variables whose smoothness is controlled by some exponent αt. Such functions model the local nature of certain datasets and can be generated, for example, by randomly-initialised one-hidden-layer neural networks: fLC corresponds to a locally connected network (LCN) [10, 11], in which the input is split into lower-dimensional patches before being processed, whereas a network enforcing invariance with respect to shifts of the input patches via weight sharing can be described by fCN . In such cases t would be the filter size of the network. Our goal is to compute the asymptotic decay of the error of a student kernel performing regression on such data, and to relate the corresponding exponent β to the locality of the target function. The student kernel corresponds to a prior on the true function of the form described by Eq. (2), except that the filter size s and its prior αs on the smoothness of the g functions can differ from those of the target function. Such students include overparametrised one-hidden-layer neural networks operating in the lazy training regime [12, 13, 14, 15, 16].

heading: 1.1 Our contributions

text:
We consider a teacher-student framework for kernel regression, where the target function has one of the forms in Eq. (2), where the gi’s and g are Gaussian random fields of given covariance. Target functions are characterised by the dimensionality t of the g functions—the filter size—and a smoothness exponent αt, such that αt > 2n implies that typical target functions are at least n times differentiable. Kernel regression is performed by local or convolutional student kernels, having filter size s and a prior on the target smoothness characterised by another exponent αs> 0. Our main contributions follow:
◦ We use recent results based on the replica method of statistical physics on the generalisation error of kernel methods [17, 18, 19] to estimate the exponent β. We find that β = αt/s if t ≤ s and αt ≤ 2(αs + s). This approach is non-rigorous, but it can be proven if data are sampled on a lattice [4] and corresponds to a provable lower bound on the error when teacher and student are equal [20].
◦ In particular, we find the same exponent for students with a prior on the shift invariance of the target function and students without this prior, implying that the curse of dimensionality is beaten due to locality and not shift invariance.
◦ We confirm systematically our predictions by performing kernel ridgeless regression numerically for various t, s and embedding dimension d.
◦ We use the recent framework of [21] and a natural Gaussian universality assumption to prove a rigorous estimate of β in the case where the ridge decreases with the size of the training set. The estimate of β depends again on s and not on d, demonstrating that the curse of dimensionality can indeed be beaten by using local filters on such compositional data.

heading: 1.2 Related work

text:
Several recent works study the role of the compositional structure of data [6, 22, 23]. When such structure is hierarchical, deep convolutional networks can be much more expressive than shallow ones [6, 24, 7]. Concerning training, [25] shows that both convolutional and locally-connected networks can achieve a target generalisation error in polynomial time, whereas fully-connected networks cannot, for a class of functions which depend only on s consecutive bits of the d-dimensional input, with s=O(log d). In [8] the effects of the architecture’s locality are studied from a kernel perspective, using a class of deep convolutional kernels introduced in [26, 27] and characterising their Reproducing Kernel Hilbert Space (RKHS). In general, belonging to the RKHS ensures favourable bounds on performance and, for isotropic kernels, is a constraint on the function smoothness that becomes
stringent in large d. For local functions, the corresponding constraint on smoothness is governed by the filter size s and not d [8]. Lastly, a recent work shows that weight sharing, in the absence of locality, leads to a mild improvement of the generalisation error of shift-invariant kernels [28].
By contrast, our work focuses on computing non-trivial training curve exponents in a setup where the locality and shift-invariance priors of the kernel can differ from those of the class of functions being learnt. In our setup, the latter are in general not in the RKHS of the kernel2. Technically, our result that the size of the student filter s controls the learning curve (and not that of the teacher t) relates to the fact that kernels are not able to detect data anisotropy (the fact that the function depends only on a subset of the coordinates) in worst-case settings [30] nor in the typical case for Gaussian fields [31].

heading: 2 Setup

text:
Kernel ridge regression Kernel ridge regression is a method to learn a target function f∗ : Rd → R from P observations {(xµ, f∗(xµ))}Pµ=1, where the inputs xµ are i.i.d. random variables distributed according to a certain measure p ( ddx )
on Rd. Let K be a positive-definite kernel and H the corresponding Reproducing Kernel Hilbert Space (RKHS). The kernel ridge regression estimator f of the target function f∗ is defined as
f = argmin f∈H
{ 1
P P∑ µ=1 (f(xµ)− f∗(xµ))2 + λ ‖f‖2H
} , (3)
where ‖ · ‖H denotes the RKHS norm and λ is the ridge parameter. The limit λ→ 0+ is known as the ridgeless case and corresponds to the solution with minimum RKHS norm that interpolates the P observations. Eq. (3) is a convex optimisation problem, having the unique solution
f(x) = 1
P P∑ µ,ν=1 K(x,xµ)
(( 1
P KP + λIP )−1) µ,ν f∗(xν), (4)
where KP is the Gram matrix defined as (KP )µν = K(xµ,xν), and IP denotes the P -dimensional identity matrix. Our goal is to compute the generalisation error, which we define as the expectation of the mean squared error over the data distribution p ( ddx ) , averaged over an ensemble of target functions f∗, i.e (P ) = Ex,f∗ [ (f(x)− f∗(x))2 ] . (5)
The error depends on the number of samples P through the predictor of Eq. (4) and we refer to the graph of (P ) as learning curve.
Statistical mechanics of generalisation in kernel regression The theoretical understanding of generalisation is still an open problem. A few recent works [17, 21, 18] relate the generalisation error to the decomposition of the target function in the eigenbasis of the kernel. A positive-definite kernel K can indeed be written, by Mercer’s theorem, in terms of its eigenvalues {λρ} and eigenfunctions {φρ}:
K(x,y) = ∞∑ ρ=1 λρφρ(x)φρ(y), ∫ p ( ddy ) K(x,y)φρ(y) = λρφρ(x). (6)
In [17, 21, 18] it is shown that, when the target function can be written in terms of the kernel eigenbasis, f∗(x) = ∑ ρ cρφρ(x), (7)
the error can also be cast as a sum of modal contributions, = ∑ ρ ρ. The details of the general formulation are summarised in Appendix A. Here we present an intuitive limiting case, obtained in the ridgeless limit λ→ 0+, when λρ ∼ ρ−a for large ρ, and E[|cρ|2] ∼ ρ−b with 2a> b− 1, that is
(P ) ∼ ∑ ρ>P E[|cρ|2] ≡ B(P ), (8)
2A Gaussian field of covariance K is never in the RKHS of the kernel K, see e.g. [29].
with ∼ denoting asymptotic equivalence for large P . Eq. (8) indicates that, given P examples, the generalisation error can be estimated as the tail sum of the power in the target function past the first P modes of the kernel, which we denote as B(P ). Although the general modal decomposition cannot be proven rigorously in the ridgeless limit [21, 19], additional results are available when the target functions are Gaussian random fields with covariance specified by a teacher kernel:
◦ Eq. (8) can be proven rigorously [4] if teacher and student are isotropic kernels and the input points xµ are sampled on the lattice Zd, i.e. all the elements of each input sequence are integer multiples of an arbitrary unit;
◦ If teacher and student coincide then E[|cρ|2] equals the ρ-th eigenvalue λρ and (see e.g. [20]) (P ) ≥ B(P ), i.e. the estimate of Eq. (8) is a lower bound.

heading: 3 Kernels for local and convolutional teacher-student scenarios

text:
In this section we introduce convolutional and local kernels that will be used as teachers, i.e. to generate different ensembles of target functions f∗ with controlled smoothness and degree of locality, and as student kernels. We motivate our choice by considering one-hidden-layer neural networks with simple local and convolutional architectures. Because of the relationship between our kernels and the Neural Tangent Kernel [12] of the aforementioned architectures, our framework encompasses regression with simple overparametrised networks trained in the lazy regime [16]. For the sake of clarity we limit the discussion to inputs which are sequences in Rd, i.e. x= (x1, . . . , xd). Extension to higher-order tensorial inputs such as imagesX ∈ Rd×d is straightforward. To avoid dealing with the boundaries of the sequence we identify xi+d with xi for all i= 1, . . . , d. Definition 3.1 (one-hidden-layer CNN). A one-hidden-layer convolutional network with H hidden neurons and average pooling is defined as follows,
fCNN (x) = 1√ H H∑ h=1 ah 1 |P| ∑ i∈P σ(wh · xi), (9)
where x ∈ Rd is the input, H is the width, σ a nonlinear activation function, P ⊆ {1, . . . , d} is a set of patch indices and |P| its cardinality. For all i ∈ P , xi is an s-dimensional patch of x. For all h= 1, . . . ,H ,wh ∈ Rs is a filter with filter size s, ah ∈ R is a scalar weight. The dot · denotes the standard Euclidean scalar product.
In the network defined above, a d-dimensional input sequence x is first mapped to s-dimensional patches xi, which are ordered subsequences of the input. Comparing each patch to a filter wh and applying the activation function σ leads to a |P|-dimensional hidden representation which is equivariant for shifts of the input. The summation over the patch index i promotes this equivariance to full invariance, leading to a model which is both local and shift-invariant as fCN in Eq. (2). A model which is only local, as fLC in Eq. (2), can be obtained by lifting the constraint of weight-sharing, which forces, for each h= 1, . . . ,H , the same filter wh to apply to all patches xi. Definition 3.2 (one-hidden-layer LCN). In the notation of Definition 3.1, a one-hidden-layer locallyconnected network with H hidden neurons is defined as follows,
fLCN (x) = 1√ H H∑ h=1 1√ |P| ∑ i∈P ah,iσ(wh,i · xi), (10)
For all i ∈ P and h= 1, . . . ,H: xi is an s-dimensional patch of x, wh,i ∈ Rs is a filter with filter size s, ah,i ∈ R is a scalar weight.
Notice that the definition above reduces to that of a fully-connected network when the filter size is set to the input dimension, s= d, and P = {1}. With the target functions taking one of the two forms in Eq. (2), our framework contains the case where the observations are generated by neural networks such as (3.1) and (3.2). Let us now introduce the neural tangent kernels of such architectures. Definition 3.3 (Neural Tangent Kernel). Given a neural network function f(x;θ), where θ= (θ1, . . . , θN ) denotes the complete set of parameters and N the total number of parameters, the Neural Tangent Kernel (NTK) is defined as [12]
ΘN (x,y;θ) = N∑ n=1 ∂θnf(x,θ)∂θnf(y,θ), (11)
where ∂θn denotes partial derivation w.r.t. the n-th parameter θn.
For one-hidden-layer networks with random, O(1)-variance Gaussian initialisation of all the weights, and normalisation by √ H as in (3.1) and (3.2), the NTK converges to a deterministic limit Θ(x,y) as N ∝ H → ∞ [12]. Furthermore, training f(x,θ) − f(x,θ0), with θ0 denoting the network parameters at initialisation, under gradient descent on the mean squared error is equivalent to performing ridgeless regression with kernel Θ(x,y) [12]. The following lemmas relate the NTK of convolutional and local architectures acting on d-dimensional inputs to that of a fully-connected architecture acting on s-dimensional inputs. Both lemmas are proved in Appendix B. Lemma 3.1. Call ΘFC the NTK of a fully-connected network function acting on s-dimensional inputs and ΘCN the NTK of a convolutional network function (3.1) with filter size s acting on d-dimensional inputs. Then
ΘCN (x,y) = 1 |P|2 ∑ i,j∈P ΘFC(xi,yj) (12)
As the functions in Eq. (2), ΘCN is written as a combination of lower-dimensional constituent kernels ΘFC acting on patches, and the dimensionality of the constituent kernel coincides with the filter size of the corresponding network. This observation extends to local kernels, via Lemma 3.2. Call ΘLC the NTK of a locally-connected network function (3.2) with filter size s acting on d-dimensional inputs. Then
ΘLC(x,y) = 1 |P| ∑ i∈P ΘFC(xi,yi) (13)
Following the general structure of Eq. (12) and Eq. (13), we introduce convolutional (KCN ) and local (KLC) student and teacher kernels, defined as sums of lower-dimensional constituent kernels C,
KCN (x,y) = |P|−2 ∑ i,j∈P C(xi,yj), (14a)
KLC(x,y) = |P|−1 ∑ i∈P C(xi,yi). (14b)
The kernels in Eq. (14) are characterised by the dimensionality of the constituent kernel C, or filter size s (for the student, or t for the teacher) and the nonanalytic behaviour of C when the two arguments approach, i.e. C(xi,yj) ∼ ‖xi − yj‖αs (for the student, or ‖xi − yj‖αt for the teacher) plus analytic contributions, with αs/t 6= 2m for m ∈ N. Using the kernels in Eq. (14) as covariances allows us to generate random target functions with the desired degree of locality t (as in Eq. (2)), which can also be invariant for shifts of the patches. Having a student kernel as in Eq. (14) results in an estimator f also having the form displayed in Eq. (2), with a different filter size with respect to the target function. The α’s control the smoothness of these functions as, if α> 2n ∈ N, then the functions are at least n times differentiable in the mean-square sense.
A notable example of such constituent kernels is the NTK of ReLU networks ΘFC , which presents a cusp at the origin corresponding to αs = 1 [32]. In addition, in the H → ∞ limit, a network initialised with random weights converges to a Gaussian process [33, 34, 35]. For networks with ReLU activations, the covariance kernel of such process has nonanalytic behaviour with αt = 3 [36].

heading: 3.1 Mercer’s decomposition of local and convolutional kernels

text:
We now turn to describing how the eigendecomposition of the constituent kernel C induces an eigendecomposition of convolutional and local kernels. We work under the following assumptions,
i) The constituent kernel C(x,y) on Rs × Rs admits the following Mercer’s decomposition,
C(x,y) = ∞∑ ρ=1 λρφρ(x)φρ(y), (15)
with (ordered) eigenvalues λρ and eigenfunctions φρ such that, with p(s)(dsx) denoting the s-dimensional patch measure, φ1(x) = 1 ∀x and ∫ p(s)(dsx)φρ(x) = 0 for all ρ>1;
ii) Convolutional and local kernels from Eq. (14) have nonoverlapping patches, i.e. d is an integer multiple of s and P = {1 + n× s |n = 1, . . . , d/s} with |P|=d/s;
iii) The s-dimensional marginals on patches of the d-dimensional input measure p(d)(ddx) are all identical and equal to p(s)(dsx).
We stress here that the request of nonoverlapping patches in assumption ii) can be relaxed at the price of further assumptions, i.e. C(x,y) = C(x− y) and data distributed uniformly on the torus, so that C is diagonalised in Fourier space. The resulting eigendecompositions are qualitatively similar to those described in this section (details in Appendix C). Let us also remark that assumptions i) and iii)—together with all the assumptions on the data distribution that might follow—are technical in nature and required only to carry out the Mercer’s decomposition analytically. We believe that the main results of this paper hold under much more general conditions, namely the support of the distribution being truly d-dimensional—such that the distance between neighbouring points in a collection of P data points scales as P−1/d—and the distribution itself decaying rapidly away from the mean or having compact support. Our experiments, discussed in Section 5, support this hypothesis. Lemma 3.3 (Spectra of convolutional kernels). Let KCN be a convolutional kernel defined as in Eq. (14a), with a constituent kernel C satisfying assumptions i), ii) and iii) above. Then KCN admits the following Mercer’s decomposition,
KCN (x,y) = ∞∑ ρ=1 ΛρΦρ(x)Φρ(y), (16)
with eigenvalues and eigenfunctions
Λ1 = λ1, Φ1(x) = 1; Λρ = s
d λρ, Φρ(x) =
√ s
d ∑ i∈P φρ(xi) for ρ > 1. (17)
Lemma 3.4 (Spectra of local kernels). Let KLC be a local kernel defined as in Eq. (14b), with a constituent kernel C satisfying assumptions i), ii) and iii) above. Then KLC admits the following Mercer’s decomposition,
KLC(x,y) = Λ1Φ1(x) + ∞∑ ρ>1 ∑ i∈P Λρ,iΦρ,i(x)Φρ,i(y), (18)
with eigenvalues and eigenfunctions (∀i ∈ P)
Λ1 = λ1, Φ1(x) = 1; Λρ,i = s
d λρ, Φρ,i(x) = φρ(xi) for ρ > 1. (19)
Under assumptions i), ii) and iii) above, lemmas 3.3 and 3.4 follow from the definitions of convolutional and local kernels and the eigendecompositions of the constituents (see Appendix C for a proof of the lemmas and generalisation to kernels with overlapping patches). In the next section, we explore the consequences of these results for the asymptotics of learning curves.

heading: 4 Asymptotic learning curves for ridgeless regression

text:
In what follows, we consider explicitly translationally-invariant constituent kernels C(xi,xj) = C(xi − xj) and a d-dimensional data distribution p(ddx) which is uniform on the torus, so that all lower-dimensional marginals are also uniform on lower-dimensional tori. Under these conditions, all results of Section 3 can be extended to kernels with overlapping patches (P = {1, . . . , d}), so that the main results of this paper apply to nonoverlapping as well as overlapping-patches kernels. Furthermore, Mercer’s decomposition Eq. (15) can be written in Fourier space [37], with s-dimensional plane waves φ(s)k (x) = e
ik·x as eigenfunctions and the eigenvalues coinciding with the Fourier transform of C. Furthermore, for kernels with filter size s (or t) and positive smoothness exponent αs (or αt), the eigenvalues decay with a power −(s+αs) (or −(t+αt)) of the modulus of the wavevector k= √ k · k [38]. In this setting, we obtain our main result:
Theorem 4.1. Let KT be a d-dimensional convolutional kernel with a translationally-invariant t-dimensional constituent and leading nonanalyticity at the origin controlled by the exponent αt> 0. Let KS be a d-dimensional convolutional or local student kernel with a translationally-invariant s-dimensional constituent, and with a nonanalyticity at the origin controlled by the exponent αs> 0. Assume, in addition, that if the kernels have overlapping patches then s ≥ t, whereas if the kernels have nonoverlapping patches s is an integer multiple of t; and that data are uniformly distributed on a d-dimensional torus. Then, the following asymptotic equivalence holds in the limit P →∞,
B(P ) ∼ P−β , β = αt/s.
Theorem 4.1, together with Eq. (8) and the additional assumption αt≤ 2(αs+s), yields the following expression for the learning curves asymptotics,
(P ) ∼ P−β , β = αt/s. (20) As β is independent of the embedding dimension d, we conclude that the curse of dimensionality is beaten when a convolutional target is learnt with a convolutional or local kernel. In fact, Eq. (20) indicates that there is no asymptotic advantage in using a convolutional rather than local student when learning a convolutional task, confirming the picture that locality, not weight sharing, is the main source of the convolutional architecture’s performances [6]. In Appendix D we show that the generalization error of a local student learning convolutional teacher decays as
(P ) ∼ ( P
|P|
)−β , β = αt/s. (21)
Eq. (21) implies that including weight sharing only amounts to a rescaling of P by a factor |P|—the size of the translation group over patches—recovering the result obtained in [28]. Intuitively, a local student will need |P| times more points than a convolutional student to learn the target with comparable accuracy, since it has to learn the same local function in all the possible |P| locations. The predictions in Eq. (20) and Eq. (21) are confirmed empirically, as discussed in Section 5 and Appendix G. Let us mention in particular that, although our predictions are valid only asymptotically, they hold already in the range P ∼ 102 − 103, consistently with the number of training points typically used in applications.
Theorem 4.1 is proven in Appendix D and extended to the case of a local teacher and local student in Appendix E. Here we sketch the proof for the nonoverlapping case, which begins with the calculation of the variance of the coefficients of the target function in the student basis. By indexing the coefficients with the s-dimensional wavevectors k,
E[|ck|2] = ∫
[0,1]d ddxΦk(x) ∫ [0,1]d ddyΦk(y)E[f∗(x)f∗(y)]
= ∫ [0,1]d ddxΦk(x) ∫ [0,1]d ddyΦk(y)KT (x,y).
(22)
If the size of teacher and student coincide, s= t, teacher and student have the same eigenfunctions. Thus, using the eigenvalue equation Eq. (6) of the teacher yields E[|ck|2] ∼ k−(αt+t) = k−(αt+s). After ranking eigenvalues by k, with multiplicity ks−1 from all the wavevectors having the same modulus k, one has
B(P ) = ∑
{k|k>P 1/s} k−(αt+s) ∼
∫ ∞ P 1/s dkks−1k−(αt+s) ∼ P− αt s . (23)
When the filter size of the teacher t is lowered, some of the coefficients E[|ck|2] vanish. As the target function becomes a composition of t-dimensional constituents, the only non-zero coefficients are found for k’s which lie in some t-dimensional subspaces of the s-dimensional Fourier space. These subspaces correspond to the k having at most a patch of t consecutive non-vanishing components. In other words, E[|ck|2] is finite only if k is effectively t-dimensional and the integral on the right-hand side of Eq. (23) becomes t-dimensional, thus
B(P ) ∼ ∫ ∞ P 1/s dkkt−1k−(αt+t) ∼ P− αt s . (24)
If the teacher patches are not contained in the student ones, the target cannot be represented with a combination of student eigenfunctions, hence the error asymptotes to a finite value when P →∞.

heading: 5 Empirical learning curves for ridgeless regression

text:
This section investigates numerically the asymptotic behaviour of the learning curves for our teacherstudent framework. We consider different combinations of convolutional and local teachers and students with overlapping patches and Laplacian constituent kernels, i.e. C(xi − xj) = e−‖xi−xj‖. In order to test the robustness of our results to the data distribution, data are uniformly generated in the hypercube [0, 1]d (results in Fig. 1) or on a d-hypersphere (results in Appendix G). Fig. 1 shows learning curves for both convolutional (left panels) and local (right panels) students learning a convolutional target function. The results in the case of a local teacher are presented in Appendix G, and display no qualitative differences.
In the following, we always refer to Fig. 1. Panels A and B show that, with αt =αs = 1, our prediction β= 1/s holds independently of the embedding dimension d. Furthermore, notice that fixing the dimension d and the teacher filter size t, the generalisation errors of a convolutional and a local student with the same filter size differ only by a multiplicative constant independent of P . Indeed, the shift-invariant nature of the convolutional student only results in a pre-asymptotic correction to our estimate of the generalisation error B(P ). In Appendix G, we check that this multiplicative constant corresponds to rescaling P by the number of patches, as predicted in Section 4. Panels C and D show learning curves for several values of s and fixed t. The curse of dimensionality is recovered when the size of the student filters coincides with the input dimension, both for local and convolutional students. Finally, panels E and F show learning curves for fixed t and s being smaller than, equal to or larger than t. We stress that, when s< t the student kernel cannot reproduce the target function, hence the error does not decrease by increasing P . Further details on the experiments are provided in Appendix G, together with learning curves for data distributed uniformly on the unit sphere Sd−1 and for regression with the actual analytical and empirical NTKs of one-hidden-layer convolutional networks. It is worthwhile to notice that experiments are always in excellent agreement with our predictions, despite using data distributions that are out of the hypotheses of Theorem 4.1. Indeed, for regression with the actual NTK even the assumption of translationally-invariant constituents is violated. Moreover, we report the learning curves of local kernels on the CIFAR-10 dataset showing that smaller filter sizes correspond to faster decays even for real and anisotropic data distributions, in agreement with the picture emerging from our synthetic model.

heading: 6 Asymptotics of learning curves with decreasing ridge

text:
We now prove an upper bound for the exponent β implying that the curse of dimensionality is beaten by a local or convolutional kernel learning a convolutional target (as in Eq. (2)), using the framework developed in [21] and a natural universality assumption on the kernel eigenfunctions. It is worth noticing that this framework does not require the target function to be generated by a teacher kernel. Proofs are presented in Appendix F. Let D(Λ) denote the density of eigenvalues of the student kernel, D(Λ) = ∑ ρ δ(Λ− Λρ), with δ(x) denoting Dirac delta function. Having a random target function with coefficients cρ in the kernel eigenbasis having variance E[|cρ|2], one can define the following reduced density (with respect to the teacher):
DT (Λ) = ∑
{ρ|E[|cρ|2]>0}
δ(Λ− Λρ) (25)
DT (Λ) counts eigenvalues for which the target has a non-zero variance, such that:∑ ρ E[|cρ|2] = ∫ dΛDT (Λ)c2(Λ), (26)
where the function c(Λ) is defined by c2(Λρ) =E[|cρ|2] for all ρ such that E[|cρ|2]> 0. The following theorem then follows from the results of [21].
Theorem 6.1. Let us consider a positive-definite kernel K with eigenvalues Λρ, ∑ ρ Λρ <∞, and eigenfunctions Φρ learning a (random) target function f∗ in kernel ridge regression (Eq. (3)) with ridge λ from P observations f∗(xµ), with xµ ∈ Rd drawn from a certain probability distribution. Let us denote with DT (Λ) the reduced density of kernel eigenvalues with respect to the target and (λ, P ) the generalisation error and also assume that
i) For any P -tuple of indices ρ1, . . . , ρP , the vector (Φρ1(x 1), . . . ,ΦρP (x P )) is a Gaussian random vector;
ii) The target function can be written in the kernel eigenbasis with coefficients cρ and c2(Λρ) =E[|cρ|2], with DT (Λ) ∼ Λ−(1+r), c2(Λ) ∼ Λq asymptotically for small Λ and r > 0, r < q < r + 2;
Then the following equivalence holds in the joint P →∞ and λ→ 0 limit with 1/(λ √ P )→ 0:
(λ, P ) ∼ ∑
{ρ|Λρ<λ}
E[|cρ|2] = ∫ λ
0
dΛDT (Λ)c2(Λ). (27)
Note that the assumption i) of the theorem on the Gaussianity of the eigenbasis does not hold in our setup where the Φρ’s are plane waves. However, the random variables Φρ(xµ) have a probability density with compact support. It is thus natural to assume that a Gaussian universality assumption holds, i.e. that Theorem 6.1 applies to our problem. With this assumption, we obtain the following
Corollary 6.1.1. Performing kernel ridge regression in a teacher-student scenario with smoothness exponents αt (teacher) and αs (student), with ridge λ ∼ P−γ and 0<γ < 1/2, under the joint hypotheses of Theorem 4.1 and Theorem 6.1, the exponent governing the asymptotic scaling of the generalisation error with P is given by:
β = γ αt
αs + s , (28)
which does not vanish in the limit d→∞. Furthermore, Eq. (28) depends on s and not on t as the prediction of Eq. (20).

heading: 7 Conclusions and future work

text:
Our work shows that, even in large dimension d, a function can be learnt efficiently if it can be expressed as a sum of constituent functions each depending on a smaller number of variables t, by performing regression with a kernel that entails such a compositional structure with s-dimensional constituents. The learning curve exponent is then independent of d and governed by s if s ≥ t, optimal for s= t and null if s< t.
In the context of image classification, this result relates to the “Bag of Words” viewpoint. Consider for example two-dimensional images consisting of M features of t adjacent pixels, and that different classes correspond to distinct subsets of (possibly shared) features. If features can be located anywhere, then data lie on a 2M -dimensional manifold. On the one hand, we expect a one-hiddenlayer convolutional network with filter size s≥ t to learn well with a learning curve exponent governed by s and independent of M . On the other hand, a fully-connected network would suffer from the curse of dimensionality for large M .
Our work does not consider that the compositional structure of real data is hierarchical, with large features that consist of smaller sub-features. It is intuitively clear that depth and locality taken together are well-suited for such data structure [8, 6]. Extending the present teacher-student framework to this case would offer valuable quantitative insights into the question of how many data are required to learn such tasks.

heading: Acknowledgements

text: We thank Alberto Bietti, Stefano Spigler, Antonio Sclocchi, Leonardo Petrini, Mario Geiger, and Umberto Maria Tomasini for helpful discussions. This work was supported by a grant from the Simons Foundation (#454953 Matthieu Wyart).

title: Locality defeats the curse of dimensionality in convolutional teacher-student scenarios