20 November 2019 in Scientific Reports
Identifying the minimal number of parameters needed to describe a dataset is a challenging problem known in the literature as intrinsic dimension estimation. All the existing intrinsic dimension estimators are not reliable whenever the dataset is locally undersampled, and this is at the core of the so called curse of dimensionality. Here we introduce a new intrinsic dimension estimator that leverages on simple properties of the tangent space of a manifold and extends the usual correlation integral estimator to alleviate the extreme undersampling problem. Based on this insight, we explore a multiscale generalization of the algorithm that is capable of (i) identifying multiple dimensionalities in a dataset, and (ii) providing accurate estimates of the intrinsic dimension of extremely curved manifolds. We test the method on manifolds generated from global transformations of high-contrast images, relevant for invariant object recognition and considered a challenge for state-of-the-art intrinsic dimension estimators.
14 September 2020 in Physical Review E
The traditional approach of statistical physics to supervised learning routinely assumes unrealistic generative models for the data: Usually inputs are independent random variables, uncorrelated with their labels. Only recently, statistical physicists started to explore more complex forms of data, such as equally labeled points lying on (possibly low-dimensional) object manifolds. Here we provide a bridge between this recently established research area and the framework of statistical learning theory, a branch of mathematics devoted to inference in machine learning. The overarching motivation is the inadequacy of the classic rigorous results in explaining the remarkable generalization properties of deep learning. We propose a way to integrate physical models of data into statistical learning theory and address, with both combinatorial and statistical mechanics methods, the computation of the Vapnik-Chervonenkis entropy, which counts the number of different binary classifications compatible with the loss class. As a proof of concept, we focus on kernel machines and on two simple realizations of data structure introduced in recent physics literature: -dimensional simplexes with prescribed geometric relations and spherical manifolds (equivalent to margin classification). Entropy, contrary to what happens for unstructured data, is nonmonotonic in the sample size, in contrast with the rigorous bounds. Moreover, data structure induces a transition beyond the storage capacity, which we advocate as a proxy of the nonmonotonicity, and ultimately a cue of low generalization error. The identification of a synaptic volume vanishing at the transition allows a quantification of the impact of data structure within replica theory, applicable in cases where combinatorial methods are not available, as we demonstrate for margin learning.
14 July 2020 in Physical Review E
Many machine learning algorithms used for dimensional reduction and manifold learning leverage on the computation of the nearest neighbors to each point of a data set to perform their tasks. These proximity relations define a so-called geometric graph, where two nodes are linked if they are sufficiently close to each other. Random geometric graphs, where the positions of nodes are randomly generated in a subset of , offer a null model to study typical properties of data sets and of machine learning algorithms. Up to now, most of the literature focused on the characterization of low-dimensional random geometric graphs whereas typical data sets of interest in machine learning live in high-dimensional spaces (). In this work, we consider the infinite dimensions limit of hard and soft random geometric graphs and we show how to compute the average number of subgraphs of given finite size , e.g., the average number of cliques. This analysis highlights that local observables display different behaviors depending on the chosen ensemble: soft random geometric graphs with continuous activation functions converge to the naive infinite-dimensional limit provided by Erdös-Rényi graphs, whereas hard random geometric graphs can show systematic deviations from it. We present numerical evidence that our analytical results, exact in infinite dimensions, provide a good approximation also for dimension .
14 January 2020 in Journal of Physics A: Mathematical and Theoretical
We consider models of assignment for random N blue points and N red points on an interval of length 2 N , in which the cost for connecting a blue point in x to a red point in y is the concave function | x − y |
p
, for 0 < p < 1. Contrarily to the convex case p > 1, where the optimal matching is trivially determined, here the optimization is non-trivial. The purpose of this paper is to introduce a special configuration, that we call the Dyck matching , and to study its statistical properties. We compute exactly the average cost, in the asymptotic limit of large N , together with the first subleading correction. The scaling is remarkable: it is of order N for , order for , and for , and it is universal for a wide class of models. We conjecture that the average cost of the Dyck matching has the same scaling in N as the cost of the optimal matching, and we produce numerical data in support of this conjecture. We hope to produce a proof of this claim in future work.
19 June 2017 in Physical Review B
Many bosonic (fermionic) fractional quantum Hall states, such as Laughlin, Moore-Read, and Read-Rezayi wave functions, belong to a special class of orthogonal polynomials: the Jack polynomials (times a Vandermonde determinant). This fundamental observation allows one to point out two different recurrence relations for the coefficients of the permanent (Slater) decomposition of the bosonic (fermionic) states. Here we provide an explicit Fock space representation for these wave functions by introducing a two-body squeezing operator which represents them as a Jastrow operator applied to reference states, which are, in general, simple periodic one-dimensional patterns. Remarkably, this operator representation is the same for bosons and fermions, and the different nature of the two recurrence relations is an outcome of particle statistics.
3 May 2021 in Physical Review Letters
We provide strong evidence that the effective spin-spin interaction in a multimodal confocal optical cavity gives rise to a self-induced glassy phase, which emerges exclusively from the peculiar Euclidean correlations and is not related to the presence of disorder as in standard spin glasses. As recently shown, this spin-spin effective interaction is both nonlocal and nontranslational invariant, and randomness in the atoms’ positions produces a spin glass phase. Here we consider the simplest feasible disorder-free setting, where atoms form a one-dimensional regular chain and we study the thermodynamics of the resulting effective Ising model. We present extensive results showing that the system has a low-temperature glassy phase. The model depends on the adimensional parameter , being a lattice spacing and an interaction length scale. Notably, for rational values of , the number of metastable states at low temperature grows exponentially with and the problem of finding the ground state rapidly becomes computationally intractable, suggesting that the system develops high-energy barriers and ergodicity breaking occurs.