Ask or search anything...

Many applications in machine learning involve data represented as probability distributions. The emergence of such data requires radically novel techniques to design tractable gradient flows on probability distributions over this type of (infinite-dimensional) objects. For instance, being able to flow labeled datasets is a core task for applications ranging from domain adaptation to transfer learning or dataset distillation. In this setting, we propose to represent each class by the associated conditional distribution of features, and to model the dataset as a mixture distribution supported on these classes (which are themselves probability distributions), meaning that labeled datasets can be seen as probability distributions over probability distributions. We endow this space with a metric structure from optimal transport, namely the Wasserstein over Wasserstein (WoW) distance, derive a differential structure on this space, and define WoW gradient flows. The latter enables to design dynamics over this space that decrease a given objective functional. We apply our framework to transfer learning and dataset distillation tasks, leveraging our gradient flow construction as well as novel tractable functionals that take the form of Maximum Mean Discrepancies with Sliced-Wasserstein based kernels between probability distributions.

Several emerging post-Bayesian methods target a probability distribution for which an entropy-regularised variational objective is minimised. This increased flexibility introduces a computational challenge, as one loses access to an explicit unnormalised density for the target. To mitigate this difficulty, we introduce a novel measure of suboptimality called 'gradient discrepancy', and in particular a 'kernel' gradient discrepancy (KGD) that can be explicitly computed. In the standard Bayesian context, KGD coincides with the kernel Stein discrepancy (KSD), and we obtain a novel characterisation of KSD as measuring the size of a variational gradient. Outside this familiar setting, KGD enables novel sampling algorithms to be developed and compared, even when unnormalised densities cannot be obtained. To illustrate this point several novel algorithms are proposed and studied, including a natural generalisation of Stein variational gradient descent, with applications to mean-field neural networks and predictively oriented posteriors presented. On the theoretical side, our principal contribution is to establish sufficient conditions for desirable properties of KGD, such as continuity and convergence control.

Designing categorical kernels is a major challenge for Gaussian process regression with continuous and categorical inputs. Despite previous studies, it is difficult to identify a preferred method, either because the evaluation metrics, the optimization procedure, or the datasets change depending on the study. In particular, reproducible code is rarely available. The aim of this paper is to provide a reproducible comparative study of all existing categorical kernels on many of the test cases investigated so far. We also propose new evaluation metrics inspired by the optimization community, which provide quantitative rankings of the methods across several tasks. From our results on datasets which exhibit a group structure on the levels of categorical inputs, it appears that nested kernels methods clearly outperform all competitors. When the group structure is unknown or when there is no prior knowledge of such a structure, we propose a new clustering-based strategy using target encodings of categorical variables. We show that on a large panel of datasets, which do not necessarily have a known group structure, this estimation strategy still outperforms other approaches while maintaining low computational cost.

Geometric tempering is a popular approach to sampling from challenging multi-modal probability distributions by instead sampling from a sequence of distributions which interpolate, using the geometric mean, between an easier proposal distribution and the target distribution. In this paper, we theoretically investigate the soundness of this approach when the sampling algorithm is Langevin dynamics, proving both upper and lower bounds. Our upper bounds are the first analysis in the literature under functional inequalities. They assert the convergence of tempered Langevin in continuous and discrete-time, and their minimization leads to closed-form optimal tempering schedules for some pairs of proposal and target distributions. Our lower bounds demonstrate a simple case where the geometric tempering takes exponential time, and further reveal that the geometric tempering can suffer from poor functional inequalities and slow convergence, even when the target distribution is well-conditioned. Overall, our results indicate that geometric tempering may not help, and can even be harmful for convergence.

Best Arm Identification (BAI) algorithms are deployed in data-sensitive applications, such as adaptive clinical trials or user studies. Driven by the privacy concerns of these applications, we study the problem of fixed-confidence BAI under global Differential Privacy (DP) for Bernoulli distributions. While numerous asymptotically optimal BAI algorithms exist in the non-private setting, a significant gap remains between the best lower and upper bounds in the global DP setting. This work reduces this gap to a small multiplicative constant, for any privacy budget $\epsilon$. First, we provide a tighter lower bound on the expected sample complexity of any $\delta$-correct and $\epsilon$-global DP strategy. Our lower bound replaces the Kullback-Leibler (KL) divergence in the transportation cost used by the non-private characteristic time with a new information-theoretic quantity that optimally trades off between the KL divergence and the Total Variation distance scaled by $\epsilon$. Second, we introduce a stopping rule based on these transportation costs and a private estimator of the means computed using an arm-dependent geometric batching. En route to proving the correctness of our stopping rule, we derive concentration results of independent interest for the Laplace distribution and for the sum of Bernoulli and Laplace distributions. Third, we propose a Top Two sampling rule based on these transportation costs. For any budget $\epsilon$, we show an asymptotic upper bound on its expected sample complexity that matches our lower bound to a multiplicative constant smaller than $8$. Our algorithm outperforms existing $\delta$-correct and $\epsilon$-global DP BAI algorithms for different values of $\epsilon$.

Density ratio estimation in high dimensions can be reframed as integrating a certain quantity, the time score, over probability paths which interpolate between the two densities. In practice, the time score has to be estimated based on samples from the two densities. However, existing methods for this problem remain computationally expensive and can yield inaccurate estimates. Inspired by recent advances in generative modeling, we introduce a novel framework for time score estimation, based on a conditioning variable. Choosing the conditioning variable judiciously enables a closed-form objective function. We demonstrate that, compared to previous approaches, our approach results in faster learning of the time score and competitive or better estimation accuracies of the density ratio on challenging tasks. Furthermore, we establish theoretical guarantees on the error of the estimated density ratio.

Variational inference (VI) is a popular approach in Bayesian inference, that looks for the best approximation of the posterior distribution within a parametric family, minimizing a loss that is typically the (reverse) Kullback-Leibler (KL) divergence. In this paper, we focus on the following parametric family: mixtures of isotropic Gaussians (i.e., with diagonal covariance matrices proportional to the identity) and uniform weights. We develop a variational framework and provide efficient algorithms suited for this family. In contrast with mixtures of Gaussian with generic covariance matrices, this choice presents a balance between accurate approximations of multimodal Bayesian posteriors, while being memory and computationally efficient. Our algorithms implement gradient descent on the location of the mixture components (the modes of the Gaussians), and either (an entropic) Mirror or Bures descent on their variance parameters. We illustrate the performance of our algorithms on numerical experiments.

We introduce a (de)-regularization of the Maximum Mean Discrepancy (DrMMD) and its Wasserstein gradient flow. Existing gradient flows that transport samples from source distribution to target distribution with only target samples, either lack tractable numerical implementation ($f$-divergence flows) or require strong assumptions, and modifications such as noise injection, to ensure convergence (Maximum Mean Discrepancy flows). In contrast, DrMMD flow can simultaneously (i) guarantee near-global convergence for a broad class of targets in both continuous and discrete time, and (ii) be implemented in closed form using only samples. The former is achieved by leveraging the connection between the DrMMD and the $\chi^2$-divergence, while the latter comes by treating DrMMD as MMD with a de-regularized kernel. Our numerical scheme uses an adaptive de-regularization schedule throughout the flow to optimally trade off between discretization errors and deviations from the $\chi^2$ regime. The potential application of the DrMMD flow is demonstrated across several numerical experiments, including a large-scale setting of training student/teacher networks.

The carrier generation in insulators subjected to strong electric fields is characterized by the Landau-Zener formula for the tunneling probability with a nonperturbative exponent. Despite its long history with diverse applications and extensions, study of nonequilibrium steady states and associated current response in the presence of the generated carriers has been mainly limited to numerical simulations so far. Here, we develop a framework to calculate the nonequilibrium Green's function of generic insulating systems under a DC electric field, in the presence of a fermionic reservoir. Using asymptotic expansion techniques, we derive a semi-quantitative formula for the Green's function with nonperturbative contribution. This formalism enables us to calculate dissipative current response of the nonequilibrium steady state, which turns out to be not simply characterized by the intraband current proportional to the tunneling probability. We also apply the present formalism to noncentrosymmetric insulators, and propose nonreciprocal charge and spin transport peculiar to tunneling electrons.

The Bethe-Hessian matrix, introduced by Saade, Krzakala, and Zdeborová (2014), is a Hermitian matrix designed for applying spectral clustering algorithms to sparse networks. Rather than employing a non-symmetric and high-dimensional non-backtracking operator, a spectral method based on the Bethe-Hessian matrix is conjectured to also reach the Kesten-Stigum detection threshold in the sparse stochastic block model (SBM). We provide the first rigorous analysis of the Bethe-Hessian spectral method in the SBM under both the bounded expected degree and the growing degree regimes. Specifically, we demonstrate that: (i) When the expected degree $d\geq 2$, the number of negative outliers of the Bethe-Hessian matrix can consistently estimate the number of blocks above the Kesten-Stigum threshold, thus confirming a conjecture from Saade, Krzakala, and Zdeborová (2014) for $d\geq 2$. (ii) For sufficiently large $d$, its eigenvectors can be used to achieve weak recovery. (iii) As $d\to\infty$, we establish the concentration of the locations of its negative outlier eigenvalues, and weak consistency can be achieved via a spectral method based on the Bethe-Hessian matrix.

Encoding logical qubits with surface codes and performing multi-qubit logical operations with lattice surgery is one of the most promising approaches to demonstrate fault-tolerant quantum computing. Thus, a method to efficiently schedule a sequence of lattice-surgery operations is vital for high-performance fault-tolerant quantum computing. A possible strategy to improve the throughput of lattice-surgery operations is splitting a large instruction into several small instructions such as Bell state preparation and measurements and executing a part of them in advance. However, scheduling methods to fully utilize this idea have yet to be explored. In this paper, we propose a fast and high-performance scheduling algorithm for lattice-surgery instructions leveraging this strategy. We achieved this by converting the scheduling problem of lattice-surgery instructions to a graph problem of embedding 3D paths into a 3D lattice, which enables us to explore efficient scheduling by solving path search problems in the 3D lattice. Based on this reduction, we propose a method to solve the path-finding problems, Dijkstra projection. We numerically show that this method reduced the execution time of benchmark programs generated from quantum phase estimation algorithms by 2.7 times compared with a naive method based on greedy algorithms. Our study establishes the relation between the lattice-surgery scheduling and graph search problems, which leads to further theoretical analysis on compiler optimization of fault-tolerant quantum computing.

We discuss some fundamental properties of the XXZ spin chain, which are important in the algebraic Bethe-ansatz derivation for the multiple-integral representations of the spin-s XXZ correlation function with an arbitrary product of elementary matrices. For instance, we construct Hermitian conjugate vectors in the massless regime and introduce the spin-s Hermitian elementary matrices.

We derive exactly scalar products and form factors for integrable higher-spin XXZ chains through the algebraic Bethe-ansatz method. Here spin values are arbitrary and different spins can be mixed. We show the affine quantum-group symmetry, $U_q(\hat{sl_2})$, for the monodromy matrix of the XXZ spin chain, and then obtain the exact expressions. Furthermore, through the quantum-group symmetry we explicitly derive the diagonalized forms of the $B$ and $C$ operators in the $F$-basis for the spin-1/2 XXZ spin chain, which was conjectured in the algebraic Bethe-ansatz calculation of the XXZ correlation functions. The results should be fundamental in studying form factors and correlation functions systematically for various solvable models associated with the integrable XXZ spin chains.

We study reinforcement learning (RL) with transition look-ahead, where the agent may observe which states would be visited upon playing any sequence of $\ell$ actions before deciding its course of action. While such predictive information can drastically improve the achievable performance, we show that using this information optimally comes at a potentially prohibitive computational cost. Specifically, we prove that optimal planning with one-step look-ahead ($\ell=1$) can be solved in polynomial time through a novel linear programming formulation. In contrast, for $\ell \geq 2$, the problem becomes NP-hard. Our results delineate a precise boundary between tractable and intractable cases for the problem of planning with transition look-ahead in reinforcement learning.

Radical pairs (also known as spin qubit pairs, electron-hole pairs) are transient reaction intermediates that are found and utilised in all areas of science. Radical pair spin dynamics simulations including all nuclear spins have been a computational barrier due to exponential scaling memory requirements. We address this issue with a tensor network method for accurately simulating the full open quantum dynamics of radical pair systems, explicitly accounting for hyperfine interactions with up to 30 nuclear spins with additional benchmarking including 60 nuclei. By employing the matrix product state (MPS) and matrix product density operator (MPDO) representations, we mitigate the exponential scaling of Hilbert and Liouville spaces typically encountered in full quantum non-Markovian treatments. We demonstrate the power of these methods with biologically relevant flavin-tryptophan radical pair systems, where we investigate electron hopping processes between multiple radical pairs using Lindblad jump operators. These simulations precisely capture anisotropic spin dynamics, clearly identifying orientational dependence of the magnetic field, which enhances or diminishes the spin-selective product yield. These directional sensitivities highlight the critical dependence of the nuclear environment and underscore the necessity of fully quantum treatments in spin biophysics, offering critical insights into avian magnetoreception mechanisms. This work provides a robust computational framework applicable to a broad range of scientific realms, which include spin chemistry, quantum biology, and spintronics.

We study the relaxation processes of the infinitely long-range interaction model (the Husimi-Temperley model) near the spinodal point. We propose a unified finite-size scaling function near the spinodal point, including the metastable region, the spinodal point, and the unstable region. We explicitly adopt the Glauber dynamics, derive a master equation for the probability distribution of the total magnetization, and perform the so-called van Kampen Omega expansion (an expansion in terms of the inverse of the systems size), which leads to a Fokker-Planck equation. We analyze the scaling properties of the Fokker-Planck equation and confirm the obtained scaling plot by direct numerical solution of the original master equation, and by kinetic Monte Carlo simulation of the stochastic decay process.

The log transformation is widely used in linear regression, mainly because coefficients are interpretable as proportional effects. Yet this practice has fundamental limitations, most notably that the log is undefined at zero, creating an identification problem. We propose a new estimator, iterated OLS (iOLS), which targets the normalized average treatment effect, preserving the percentage-change interpretation while addressing these limitations. Our procedure is the theoretically justified analogue of the ad-hoc log(1+Y) transformation and delivers a consistent and asymptotically normal estimator of the parameters of the exponential conditional mean model. iOLS is computationally efficient, globally convergent, and free of the incidental-parameter bias, while extending naturally to endogenous regressors through iterated 2SLS. We illustrate the methods with simulations and revisit three influential publications.