Search

We analyze the Nyström approximation of a positive definite kernel associated with a probability measure. We first prove an improved error bound for the conventional Nyström approximation with i.i.d. sampling and singular-value decomposition in the continuous regime; the proof techniques are borrowed from statistical learning theory. We further introduce a refined selection of subspaces in Nyström approximation with theoretical guarantees that is applicable to non-i.i.d. landmark points. Finally, we discuss their application to convex kernel quadrature and give novel theoretical guarantees as well as numerical observations., 22 pages, ICML 2023 camera-ready version. Typos fixed

The signature of a rectifiable path is a tensor series in the tensor algebra whose coefficients are definite iterated integrals of the path. The signature characterises the path up to a generalised form of reparametrisation. It is a classical result of K. T. Chen that the log-signature (the logarithm of the signature) is a Lie series. A Lie series is polynomial if it has finite degree. We show that the log-signature is polynomial if and only if the path is a straight line up to reparametrisation. Consequently, the log-signature of a rectifiable path either has degree one or infinite support. Though our result pertains to rectifiable paths, the proof uses results from rough path theory, in particular that the signature characterises a rough path up to reparametrisation., Comment: 11 pages

This paper focuses on representation learning for dynamic graphs with temporal interactions. A fundamental issue is that both the graph structure and the nodes own their own dynamics, and their blending induces intractable complexity in the temporal evolution over graphs. Drawing inspiration from the recent process of physical dynamic models in deep neural networks, we propose Graph Neural Controlled Differential Equation (GN-CDE) model, a generic differential model for dynamic graphs that characterise the continuously dynamic evolution of node embedding trajectories with a neural network parameterised vector field and the derivatives of interactions w.r.t. time. Our framework exhibits several desirable characteristics, including the ability to express dynamics on evolving graphs without integration by segments, the capability to calibrate trajectories with subsequent data, and robustness to missing observations. Empirical evaluation on a range of dynamic graph representation learning tasks demonstrates the superiority of our proposed approach compared to the baselines., Comment: 13 pages, 3 figures

Neural differential equations may be trained by backpropagating gradients via the adjoint method, which is another differential equation typically solved using an adaptive-step-size numerical differential equation solver. A proposed step is accepted if its error, \emph{relative to some norm}, is sufficiently small; else it is rejected, the step is shrunk, and the process is repeated. Here, we demonstrate that the particular structure of the adjoint equations makes the usual choices of norm (such as $L^2$) unnecessarily stringent. By replacing it with a more appropriate (semi)norm, fewer steps are unnecessarily rejected and the backpropagation is made faster. This requires only minor code modifications. Experiments on a wide range of tasks -- including time series, generative modeling, and physical control -- demonstrate a median improvement of 40% fewer function evaluations. On some problems we see as much as 62% fewer function evaluations, so that the overall training time is roughly halved., Comment: Published at ICML 2021

Neural controlled differential equations (CDEs) are the continuous-time analogue of recurrent neural networks, as Neural ODEs are to residual networks, and offer a memory-efficient continuous-time way to model functions of potentially irregular time series. Existing methods for computing the forward pass of a Neural CDE involve embedding the incoming time series into path space, often via interpolation, and using evaluations of this path to drive the hidden state. Here, we use rough path theory to extend this formulation. Instead of directly embedding into path space, we instead represent the input signal over small time intervals through its \textit{log-signature}, which are statistics describing how the signal drives a CDE. This is the approach for solving \textit{rough differential equations} (RDEs), and correspondingly we describe our main contribution as the introduction of Neural RDEs. This extension has a purpose: by generalising the Neural CDE approach to a broader class of driving signals, we demonstrate particular advantages for tackling long time series. In this regime, we demonstrate efficacy on problems of length up to 17k observations and observe significant training speed-ups, improvements in model performance, and reduced memory requirements compared to existing approaches., Comment: Published at ICML 2021

We introduce features for massive data streams. These stream features can be thought of as "ordered moments" and generalize stream sketches from "moments of order one" to "ordered moments of arbitrary order". In analogy to classic moments, they have theoretical guarantees such as universality that are important for learning algorithms.

We present a new pathwise approximation scheme for stochastic differential equations driven by multidimensional Brownian motion which does not require the simulation of L\'{e}vy area and has a Wasserstein convergence rate better than the Euler scheme's strong error rate of $O(\sqrt{h})$, where $h$ is the step-size. By using rough path theory we avoid imposing any non-degenerate H\"{o}rmander or ellipticity assumptions on the vector fields of the SDE, in contrast to the similar papers of Alfonsi, Davie, and Malliavin et al. The scheme is based on the log-ODE method with the L\'{e}vy area increments replaced by Gaussian approximations with the same covariance structure. The Wasserstein coupling is achieved by making small changes to the argument of Davie, the latter being an extension of the Koml\'{o}s-Major-Tusn\'{a}dy Theorem. We prove that the convergence of the scheme in the Wasserstein metric is of the order $O(h^{1-2/\gamma-\varepsilon})$ when the vector fields are $\gamma$-Lipschitz in the sense of Stein.

We embed the rough integration in a larger geometrical/algebraic framework of integrating one-forms against group-valued paths, and reduce the rough integral to an inhomogeneous analogue of the classical Young integral. We define dominated paths as integrals of one-forms, and demonstrate that they are stable under basic operations., Comment: 34 pages. Improved presentation and simplified proof

Market events such as order placement and order cancellation are examples of the complex and substantial flow of data that surrounds a modern financial engineer. New mathematical techniques, developed to describe the interactions of complex oscillatory systems (known as the theory of rough paths) provides new tools for analysing and describing these data streams and extracting the vital information. In this paper we illustrate how a very small number of coefficients obtained from the signature of financial data can be sufficient to classify this data for subtle underlying features and make useful predictions. This paper presents financial examples in which we learn from data and then proceed to classify fresh streams. The classification is based on features of streams that are specified through the coordinates of the signature of the path. At a mathematical level the signature is a faithful transform of a multidimensional time series. (Ben Hambly and Terry Lyons \cite{uniqueSig}), Hao Ni and Terry Lyons \cite{NiLyons} introduced the possibility of its use to understand financial data and pointed to the potential this approach has for machine learning and prediction. We evaluate and refine these theoretical suggestions against practical examples of interest and present a few motivating experiments which demonstrate information the signature can easily capture in a non-parametric way avoiding traditional statistical modelling of the data. In the first experiment we identify atypical market behaviour across standard 30-minute time buckets sampled from the WTI crude oil future market (NYMEX). The second and third experiments aim to characterise the market "impact" of and distinguish between parent orders generated by two different trade execution algorithms on the FTSE 100 Index futures market listed on NYSE Liffe.

The solution of rough differential equation, driven by the It�� signature of a continuous local martingale, exists uniquely a.s. when the vector field is Lip(��) for ��> 1, and coincides a.s. with the It�� signature of the solution of parallel stochastic differential equation. Moreover, the It�� solution can be recovered pathwisely by concatenating discounted Stratonovich solutions.

We develop a fundamental framework for and extend the theory of rough paths to Lipschitz-gamma manifolds.

We develop two methods to reconstruct a path of bounded variation from its signature. The first method gives a simple and explicit expression of any axis path in terms of its signature, but it does not apply directlty to more general ones. The second method, based on an approximation scheme, recovers any tree-reduced path from its signature as the limit of a uniformly convergent sequence of lattice paths.

These notes cover background material on trees which are used in the paper `On uniqueness of the signature of a path of variation and the reduced path group'., Comment: Background material for the paper `On uniqueness of the signature of a path of variation and the reduced path group'. Formerly an appendix to earlier versions of the paper

Accurate prediction of progression in subjects at risk of Alzheimer's disease is crucial for enrolling the right subjects in clinical trials. However, a prospective comparison of state-of-the-art algorithms for predicting disease onset and progression is currently lacking. We present the findings of "The Alzheimer's Disease Prediction Of Longitudinal Evolution" (TADPOLE) Challenge, which compared the performance of 92 algorithms from 33 international teams at predicting the future trajectory of 219 individuals at risk of Alzheimer's disease. Challenge participants were required to make a prediction, for each month of a 5-year future time period, of three key outcomes: clinical diagnosis, Alzheimer's Disease Assessment Scale Cognitive Subdomain (ADAS-Cog13), and total volume of the ventricles. The methods used by challenge participants included multivariate linear regression, machine learning methods such as support vector machines and deep neural networks, as well as disease progression models. No single submission was best at predicting all three outcomes. For clinical diagnosis and ventricle volume prediction, the best algorithms strongly outperform simple baselines in predictive ability. However, for ADAS-Cog13 no single submitted prediction method was significantly better than random guesswork. Two ensemble methods based on taking the mean and median over all predictions, obtained top scores on almost all tasks. Better than average performance at diagnosis prediction was generally associated with the additional inclusion of features from cerebrospinal fluid (CSF) samples and diffusion tensor imaging (DTI). On the other hand, better performance at ventricle volume prediction was associated with inclusion of summary statistics, such as the slope or maxima/minima of patient-specific biomarkers. On a limited, cross-sectional subset of the data emulating clinical trials, performance of the best algorithms at predicting clinical diagnosis decreased only slightly (2 percentage points) compared to the full longitudinal dataset. The submission system remains open via the website https://tadpole.grand-challenge.org, while TADPOLE SHARE (https://tadpole-share.github.io/) collates code for submissions. TADPOLE's unique results suggest that current prediction algorithms provide sufficient accuracy to exploit biomarkers related to clinical diagnosis and ventricle volume, for cohort refinement in clinical trials for Alzheimer's disease. However, results call into question the usage of cognitive test scores for patient selection and as a primary endpoint in clinical trials.

Educational researchers have long noted the apparent link between positive student attitudes and a student's desire to continue their study of particular subjects beyond the compulsory years of schooling, with much of the research motivated by concerns around declining student participation rates in high-school and university. However, unambiguously measuring students' attitudes is notoriously difficult. In addition, the question of which attitudes have the most significant effect on student intentions is not fully understood. This study was designed to address the gap in understanding between students' attitudes and their enrolment intentions by surveying a large cohort of Australian students at regular intervals during their first year of high-school (Year 7, aged 12-13 years). An innovative, new digital instrument was used to gather quantitative data about students' attitudes towards school subjects across seven constructs. Subject Attitude Profiles were then constructed for the disciplines of science, mathematics and design technologies and compared with each other and also with a Composite Attitude Profile for all school courses. We show that although students' attitudes to the STEM subjects vary widely, their attitudes generally decline over the first year of high-school with regard to a number of attitudinal constructs. We also show that the trends within these STEM disciplines are not identical and we therefore conclude that each discipline requires an individual response if students' attitudes are to be addressed. usc Refereed/Peer-reviewed