University of Edinburgh

HiGHS is open-source optimization software for linear programming, mixed-integer programming, and quadratic programming. Created initially from research solvers written by Edinburgh PhD students, HiGHS attracted industrial funding that allowed further development, and saw it contribute to a REF 2021 Impact Case Study. Having been identified as a game-changer by the open-source energy systems planning community, the resulting crowdfunding campaign has received large donations that will allow the HiGHS project to expand and create further Impact.

This talk will give an insight into the state-of-the-art techniques underlying the linear programming solvers in HiGHS, with a particular focus on the challenge of solving sequences of linear systems of equations with remarkable properties. The means by which "gradware" created by PhD students has been transformed into software, generating income and Impact, will also be described. Independent benchmark results will be given to demonstrate that HiGHS is the world’s best open-source linear optimization software.

 

 We develop a probabilistic framework for analysing model-based reinforcement learning in the episodic setting. We then apply it to study finite-time horizon stochastic control problems with linear dynamics but unknown coefficients and convex, but possibly irregular, objective function. Using probabilistic representations, we study regularity of the associated cost functions and establish precise estimates for the performance gap between applying optimal feedback control derived from estimated and true model parameters. We identify conditions under which this performance gap is quadratic, improving the linear performance gap in recent work [X. Guo, A. Hu, and Y. Zhang, arXiv preprint, arXiv:2104.09311, (2021)], which matches the results obtained for stochastic linear-quadratic problems. Next, we propose a phase-based learning algorithm for which we show how to optimise exploration-exploitation trade-off and achieve sublinear regrets in high probability and expectation. When assumptions needed for the quadratic performance gap hold, the algorithm achieves an order (N‾‾√lnN) high probability regret, in the general case, and an order ((lnN)2) expected regret, in self-exploration case, over N episodes, matching the best possible results from the literature. The analysis requires novel concentration inequalities for correlated continuous-time observations, which we derive.

-----------------------------------------------------------------------
Dr Lukasz Szpruch

TBC

We consider spectral methods that uncover hidden structures in directed networks. We establish and exploit connections between node reordering via (a) minimizing an objective function and (b) maximizing the likelihood of a random graph model. We focus on two existing spectral approaches that build and analyse Laplacian-style matrices via the minimization of frustration and trophic incoherence. These algorithms aim to reveal directed periodic and linear hierarchies, respectively. We show that reordering nodes using the two algorithms, or mapping them onto a specified lattice, is associated with new classes of directed random graph models. Using this random graph setting, we are able to compare the two algorithms on a given network and quantify which structure is more likely to be present. We illustrate the approach on synthetic and real networks, and discuss practical implementation issues. This talk is based on a joint work with Desmond Higham and Konstantinos Zygalakis. 

Article link: https://royalsocietypublishing.org/doi/10.1098/rsos.211144

In this talk, we will consider multidimensional fast-slow dynamical systems in discrete-time with random initial conditions but otherwise completely deterministic dynamics. The question we will investigate is whether the slow variable converges in law to a stochastic process under a suitable scaling limit. We will be particularly interested in the case when the limiting dynamic is superdiffusive, i.e. it coincides in law with the solution of a Marcus SDE driven by a discontinuous stable Lévy process. Under certain assumptions, we will show that generically convergence does not hold in any Skorokhod topology but does hold in a generalisation of the Skorokhod strong M1 topology which we define using so-called path functions. Our methods are based on a combination of ergodic theory and ideas arising from (but not using) rough paths. We will finally show that our assumptions are satisfied for a class of intermittent maps of Pomeau-Manneville type. 

I will talk about the joint moments of characteristic polynomials of random unitary matrices and their derivatives. In joint work with Jon Keating and Jon Warren we establish the asymptotics of these quantities for general real values of the exponents as the size N of the matrix goes to infinity. This proves a conjecture of Hughes from 2001. In subsequent joint work with Benjamin Bedert, Mustafa Alper Gunes and Arun Soor we focus on the leading order coefficient in the asymptotics, we connect this to Painleve equations for general values of the exponents and obtain explicit expressions corresponding to the so-called classical solutions of these equations.

We present several Itô-Wentzell formulae on Wiener spaces for real-valued functionals random field of Itô type depending on measures. We distinguish the full- and marginal-measure flow cases. Derivatives with respect to the measure components are understood in the sense of Lions.
This talk is based on joint work with V. Platonov (U. of Edinburgh), see https://arxiv.org/abs/1910.01892.
 

Dimension reduction is an overarching theme in data science: we enjoy finding informative patterns, features or substructures in large, complex data sets. Within the field of network science, an important problem of this nature is to identify core-periphery structure. Given a network, our task is to assign each node to either the core or periphery. Core nodes should be strongly connected across the whole network whereas peripheral nodes should be strongly connected only to core nodes. More generally, we may wish to assign a non-negative value to each node, with a larger value indicating greater "coreness." This type of problem is related to, but distinct from, commumnity detection (finding clusters) and centrality assignment (finding key players), and it arises naturally in the study of networks in social science and finance. We derive and analyse a new iterative algorithm for detecting network core-periphery structure.

Using techniques in nonlinear Perron-Frobenius theory we prove global convergence to the unique solution of a relaxed version of a natural discrete optimization problem. On sparse networks, the cost of each iteration scales linearly with the number of nodes, making the algorithm feasible for large-scale problems. We give an alternative interpretation of the algorithm from the perspective of maximum likelihood reordering of a new logistic core--periphery random graph model. This viewpoint also gives a new basis for quantitatively judging a core--periphery detection algorithm. We illustrate the algorithm on a range of synthetic and real networks, and show that it offers advantages over the current state-of-the-art.

This is joint work with Francesco Tudisco (Strathclyde)

Neural networks are undoubtedly successful in practical applications. However complete mathematical theory of why and when machine learning algorithms based on neural networks work has been elusive. Although various representation theorems ensures the existence of the ``perfect’’ parameters of the network, it has not been proved that these perfect parameters can be (efficiently) approximated by conventional algorithms, such as the stochastic gradient descent. This problem is well known, since the arising optimisation problem is non-convex. In this talk we show how the optimization problem becomes convex in the mean field limit for one-hidden layer networks and certain deep neural networks. Moreover we present optimality criteria for the distribution of the network parameters and show that the nonlinear Langevin dynamics converges to this optimal distribution. This is joint work with Kaitong Hu, Zhenjie Ren and Lukasz Szpruch. 

Inertia-gravity waves (IGWs) are ubiquitous in the ocean and the atmosphere. Once generated (by tides, topography, convection and other processes), they propagate and scatter in the large-scale, geostrophically-balanced background flow. I will discuss models of this scattering which represent the background flow as a random field with known statistics. Without assumption of spatial scale separation between waves and flow, the scattering is described by a kinetic equation involving a scattering cross section determined by the energy spectrum of the flow. In the limit of small-scale waves, this equation reduces to a diffusion equation in wavenumber space. This predicts, in particular, IGW energy spectra scaling as k^{-2}, consistent with observations in the atmosphere and ocean, lending some support to recent claims that (sub)mesoscale spectra can be attributed to almost linear IGWs.  The theoretical predictions are checked against numerical simulations of the three-dimensional Boussinesq equations.
(Joint work with Miles Savva and Hossein Kafiabad.)