Search

Parallelisation in Bayesian optimisation is a common strategy but faces several challenges: the need for flexibility in acquisition functions and kernel choices, flexibility dealing with discrete and continuous variables simultaneously, model misspecification, and lastly fast massive parallelisation. To address these challenges, we introduce a versatile and modular framework for batch Bayesian optimisation via probabilistic lifting with kernel quadrature, called SOBER, which we present as a Python library based on GPyTorch/BoTorch. Our framework offers the following unique benefits: (1) Versatility in downstream tasks under a unified approach. (2) A gradient-free sampler, which does not require the gradient of acquisition functions, offering domain-agnostic sampling (e.g., discrete and mixed variables, non-Euclidean space). (3) Flexibility in domain prior distribution. (4) Adaptive batch size (autonomous determination of the optimal batch size). (5) Robustness against a misspecified reproducing kernel Hilbert space. (6) Natural stopping criterion., Comment: This work is the journal extension of the workshop paper (arXiv:2301.11832) and AISTATS paper (arXiv:2306.05843). 48 pages, 11 figures

Reward evaluation of episodes becomes a bottleneck in a broad range of reinforcement learning tasks. Our aim in this paper is to select a small but representative subset of a large batch of episodes, only on which we actually compute rewards for more efficient policy gradient iterations. We build a Gaussian process modeling of discounted returns or rewards to derive a positive definite kernel on the space of episodes, run an ``episodic" kernel quadrature method to compress the information of sample episodes, and pass the reduced episodes to the policy network for gradient updates. We present the theoretical background of this procedure as well as its numerical illustrations in MuJoCo tasks., Comment: 18 pages, 2 figures

Active learning parallelization is widely used, but typically relies on fixing the batch size throughout experimentation. This fixed approach is inefficient because of a dynamic trade-off between cost and speed -- larger batches are more costly, smaller batches lead to slower wall-clock run-times -- and the trade-off may change over the run (larger batches are often preferable earlier). To address this trade-off, we propose a novel Probabilistic Numerics framework that adaptively changes batch sizes. By framing batch selection as a quadrature task, our integration-error-aware algorithm facilitates the automatic tuning of batch sizes to meet predefined quadrature precision objectives, akin to how typical optimizers terminate based on convergence thresholds. This approach obviates the necessity for exhaustive searches across all potential batch sizes. We also extend this to scenarios with constrained active learning and constrained optimization, interpreting constraint violations as reductions in the precision requirement, to subsequently adapt batch construction. Through extensive experiments, we demonstrate that our approach significantly enhances learning efficiency and flexibility in diverse Bayesian batch active learning and Bayesian optimization applications., Comment: Accepted at AISTATS 2024. 33 pages, 6 figures

A significant challenge in the field of quantum machine learning (QML) is to establish applications of quantum computation to accelerate common tasks in machine learning such as those for neural networks. Ridgelet transform has been a fundamental mathematical tool in the theoretical studies of neural networks, but the practical applicability of ridgelet transform to conducting learning tasks was limited since its numerical implementation by conventional classical computation requires an exponential runtime $\exp(O(D))$ as data dimension $D$ increases. To address this problem, we develop a quantum ridgelet transform (QRT), which implements the ridgelet transform of a quantum state within a linear runtime $O(D)$ of quantum computation. As an application, we also show that one can use QRT as a fundamental subroutine for QML to efficiently find a sparse trainable subnetwork of large shallow wide neural networks without conducting large-scale optimization of the original network. This application discovers an efficient way in this regime to demonstrate the lottery ticket hypothesis on finding such a sparse trainable neural network. These results open an avenue of QML for accelerating learning tasks with commonly used classical neural networks., Comment: 27 pages, 4 figures

Batch Bayesian optimisation and Bayesian quadrature have been shown to be sample-efficient methods of performing optimisation and quadrature where expensive-to-evaluate objective functions can be queried in parallel. However, current methods do not scale to large batch sizes -- a frequent desideratum in practice (e.g. drug discovery or simulation-based inference). We present a novel algorithm, SOBER, which permits scalable and diversified batch global optimisation and quadrature with arbitrary acquisition functions and kernels over discrete and mixed spaces. The key to our approach is to reformulate batch selection for global optimisation as a quadrature problem, which relaxes acquisition function maximisation (non-convex) to kernel recombination (convex). Bridging global optimisation and quadrature can efficiently solve both tasks by balancing the merits of exploitative Bayesian optimisation and explorative Bayesian quadrature. We show that SOBER outperforms 11 competitive baselines on 12 synthetic and diverse real-world tasks., Comment: 34 pages, 12 figures

We analyze the Nystr\"om approximation of a positive definite kernel associated with a probability measure. We first prove an improved error bound for the conventional Nystr\"om 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\"om 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., Comment: 22 pages, ICML 2023 camera-ready version. Typos fixed

Given a probability measure $\mu$ on a set $\mathcal{X}$ and a vector-valued function $\varphi$, a common problem is to construct a discrete probability measure on $\mathcal{X}$ such that the push-forward of these two probability measures under $\varphi$ is the same. This construction is at the heart of numerical integration methods that run under various names such as quadrature, cubature, or recombination. A natural approach is to sample points from $\mu$ until their convex hull of their image under $\varphi$ includes the mean of $\varphi$. Here we analyze the computational complexity of this approach when $\varphi$ exhibits a graded structure by using so-called hypercontractivity. The resulting theorem not only covers the classical cubature case of multivariate polynomials, but also integration on pathspace, as well as kernel quadrature for product measures., Comment: 20 pages

Calculation of Bayesian posteriors and model evidences typically requires numerical integration. Bayesian quadrature (BQ), a surrogate-model-based approach to numerical integration, is capable of superb sample efficiency, but its lack of parallelisation has hindered its practical applications. In this work, we propose a parallelised (batch) BQ method, employing techniques from kernel quadrature, that possesses an empirically exponential convergence rate. Additionally, just as with Nested Sampling, our method permits simultaneous inference of both posteriors and model evidence. Samples from our BQ surrogate model are re-selected to give a sparse set of samples, via a kernel recombination algorithm, requiring negligible additional time to increase the batch size. Empirically, we find that our approach significantly outperforms the sampling efficiency of both state-of-the-art BQ techniques and Nested Sampling in various real-world datasets, including lithium-ion battery analytics., Comment: 38 pages, 6 figures

We study kernel quadrature rules with convex weights. Our approach combines the spectral properties of the kernel with recombination results about point measures. This results in effective algorithms that construct convex quadrature rules using only access to i.i.d. samples from the underlying measure and evaluation of the kernel and that result in a small worst-case error. In addition to our theoretical results and the benefits resulting from convex weights, our experiments indicate that this construction can compete with the optimal bounds in well-known examples., Comment: 29 pages, NeurIPS 2022 camera-ready version

For a $d$-dimensional random vector $X$, let $p_{n, X}(\theta)$ be the probability that the convex hull of $n$ independent copies of $X$ contains a given point $\theta$. We provide several sharp inequalities regarding $p_{n, X}(\theta)$ and $N_X(\theta)$ denoting the smallest $n$ for which $p_{n, X}(\theta)\ge1/2$. As a main result, we derive the totally general inequality $1/2 \le \alpha_X(\theta)N_X(\theta)\le 3d + 1$, where $\alpha_X(\theta)$ (a.k.a. the Tukey depth) is the minimum probability that $X$ is in a fixed closed halfspace containing the point $\theta$. We also show several applications of our general results: one is a moment-based bound on $N_X(\mathbb{E}[X])$, which is an important quantity in randomized approaches to cubature construction or measure reduction problem. Another application is the determination of the canonical convex body included in a random convex polytope given by independent copies of $X$, where our combinatorial approach allows us to generalize existing results in random matrix community significantly., Comment: 34 pages

In this paper, we investigate application of mathematical optimization to construction of a cubature formula on Wiener space, which is a weak approximation method of stochastic differential equations introduced by Lyons and Victoir (Cubature on Wiener Space, Proc. R. Soc. Lond. A 460, 169--198). After giving a brief review of the cubature theory on Wiener space, we show that a cubature formula of general dimension and degree can be obtained through a Monte Carlo sampling and linear programming. This paper also includes an extension of stochastic Tchakaloff's theorem, which technically yields the proof of our primary result., Comment: 25 pages

In numerical integration, cubature methods are effective, especially when the integrands can be well-approximated by known test functions, such as polynomials. However, the construction of cubature formulas has not generally been known, and existing examples only represent the particular domains of integrands, such as hypercubes and spheres. In this study, we show that cubature formulas can be constructed for probability measures provided that we have an i.i.d. sampler from the measure and the mean values of given test functions. Moreover, the proposed method also works as a means of data compression, even if sufficient prior information of the measure is not available., Comment: 10 pages

We investigate the approximation formulas that were proposed by Tanaka & Sugihara (2019), in weighted Hardy spaces, which are analytic function spaces with certain asymptotic decay. Under the criterion of minimum worst error of $n$-point approximation formulas, we demonstrate that the formulas are nearly optimal. We also obtain the upper bounds of the approximation errors that coincide with the existing heuristic bounds in asymptotic order by duality theorem for the minimization problem of potential energy., Comment: 17 pages

Deep learning has been applied to various tasks in the field of machine learning and has shown superiority to other common procedures such as kernel methods. To provide a better theoretical understanding of the reasons for its success, we discuss the performance of deep learning and other methods on a nonparametric regression problem with a Gaussian noise. Whereas existing theoretical studies of deep learning have been based mainly on mathematical theories of well-known function classes such as H\"{o}lder and Besov classes, we focus on function classes with discontinuity and sparsity, which are those naturally assumed in practice. To highlight the effectiveness of deep learning, we compare deep learning with a class of linear estimators representative of a class of shallow estimators. It is shown that the minimax risk of a linear estimator on the convex hull of a target function class does not differ from that of the original target function class. This results in the suboptimality of linear methods over a simple but non-convex function class, on which deep learning can attain nearly the minimax-optimal rate. In addition to this extreme case, we consider function classes with sparse wavelet coefficients. On these function classes, deep learning also attains the minimax rate up to log factors of the sample size, and linear methods are still suboptimal if the assumed sparsity is strong. We also point out that the parameter sharing of deep neural networks can remarkably reduce the complexity of the model in our setting., Comment: 33 pages

The Carrington storm (September 1/2, 1859) is one of the largest magnetic storms ever observed and it has caused global auroral displays in low-latitude areas, together with a series of multiple magnetic storms during August 28 and September 4, 1859. In this study, we revisit contemporary auroral observation records to extract information on their elevation angle, color, and direction to investigate this stormy interval in detail. We first examine their equatorward boundary of "auroral emission with multiple colors" based on descriptions of elevation angle and color. We find that their locations were 36.5 deg ILAT on August 28/29 and 32.7 deg ILAT on September 1/2, suggesting that trapped electrons moved to, at least, L~1.55 and L~1.41, respectively. The equatorward boundary of "purely red emission" was likely located at 30.8 deg ILAT on September 1/2. If "purely red emission" was a stable auroral red arc, it would suggest that trapped protons moved to, at least, L~1.36. This reconstruction with observed auroral emission regions provides conservative estimations of magnetic storm intensities. We compare the auroral records with magnetic observations. We confirm that multiple magnetic storms occurred during this stormy interval, and that the equatorward expansion of the auroral oval is consistent with the timing of magnetic disturbances. It is possible that the August 28/29 interplanetary coronal mass ejections (ICMEs) cleared out the interplanetary medium, making the ICMEs for the Carrington storm on September 1/2 more geoeffective., Comment: Main Text 28 pages, References 11 pages, and Appendix 3 pages with 5 figures. The data table will be shown in the record version. This paper was accepted for publication in the Astrophysical Journal on 2018 September 26

Aims. Historical records provide evidence of extreme magnetic storms with equatorward auroral extensions before the epoch of systematic magnetic observations. One significant magnetic storm occurred on February 15, 1730. We scale this magnetic storm with auroral extension and contextualise it based on contemporary solar activity. Methods. We examined historical records in East Asia and computed the magnetic latitude (MLAT) of observational sites to scale magnetic storms. We also compared them with auroral records in Southern Europe. We examined contemporary sunspot observations to reconstruct detailed solar activity between 1729 and 1731. Results. We show 29 auroral records in East Asian historical documents and 37 sunspot observations. Conclusions. These records show that the auroral displays were visible at least down to 25.8{\deg} MLAT throughout East Asia. In comparison with contemporary European records, we show that the boundary of the auroral display closest to the equator surpassed 45.1{\deg} MLAT and possibly came down to 31.5{\deg} MLAT in its maximum phase, with considerable brightness. Contemporary sunspot records show an active phase in the first half of 1730 during the declining phase of the solar cycle. This magnetic storm was at least as intense as the magnetic storm in 1989, but less intense than the Carrington event., Comment: 30 pages, 5 figures, and 2 tables, accepted for publication in Astronomy & Astrophysics on 25 April 2018. The figures and transcriptions/translations of historical documents are partially omitted in this manuscript due to the condition of reproduction. They are available in the publisher version

The study of historical great geomagnetic storms is crucial for assessing the possible risks to the technological infrastructure of a modern society, caused by extreme space-weather events. The normal benchmark has been the great geomagnetic storm of September 1859, the so-called "Carrington Event". However, there are numerous records of another great geomagnetic storm in February 1872. This storm, about 12 years after the Carrington Event, resulted in comparable magnetic disturbances and auroral displays over large areas of the Earth. We have revisited this great geomagnetic storm in terms of the auroral and sunspot records in the historical documents from East Asia. In particular, we have surveyed the auroral records from East Asia and estimated the equatorward boundary of the auroral oval to be near 24.3 deg invariant latitude (ILAT), on the basis that the aurora was seen near the zenith at Shanghai (20 deg magnetic latitude, MLAT). These results confirm that this geomagnetic storm of February 1872 was as extreme as the Carrington Event, at least in terms of the equatorward motion of the auroral oval. Indeed, our results support the interpretation of the simultaneous auroral observations made at Bombay (10 deg MLAT). The East Asian auroral records have indicated extreme brightness, suggesting unusual precipitation of high-intensity, low-energy electrons during this geomagnetic storm. We have compared the duration of the East Asian auroral displays with magnetic observations in Bombay and found that the auroral displays occurred in the initial phase, main phase, and early recovery phase of the magnetic storm., Comment: 28 pages, 5 figures, accepted for publication in the Astrophysical Journal on 31 May 2018