Search

In many large-scale classification problems, classes are organized in a known hierarchy, typically represented as a tree expressing the inclusion of classes in superclasses. We introduce a loss for this type of supervised hierarchical classification. It utilizes the knowledge of the hierarchy to assign each example not only to a class but also to all encompassing superclasses. Applicable to any feedforward architecture with a softmax output layer, this loss is a proper scoring rule, in that its expectation is minimized by the true posterior class probabilities. This property allows us to simultaneously pursue consistent classification objectives between superclasses and fine-grained classes, and eliminates the need for a performance trade-off between different granularities. We conduct an experimental study on three reference benchmarks, in which we vary the size of the training sets to cover a diverse set of learning scenarios. Our approach does not entail any significant additional computational cost compared with the loss of cross-entropy. It improves accuracy and reduces the number of coarse errors, with predicted labels that are distant from ground-truth labels in the tree.

In this work we analyse the small-time reachability properties of a nonlinear parabolic equation, by means of a bilinear control, posed on a torus of arbitrary dimension $d$. Under a saturation hypothesis on the control operators, we show the small-time approximate controllability between states sharing the same sign. Moreover, in the one-dimensional case $d=1$, we combine this property with a local exact controllability result, and prove the small-time exact controllability of any positive states towards the ground state of the evolution operator.

Generative modeling aims at producing new datapoints whose statistical properties resemble the ones in a training dataset. In recent years, there has been a burst of machine learning techniques and settings that can achieve this goal with remarkable performances. In most of these settings, one uses the training dataset in conjunction with noise, which is added as a source of statistical variability and is essential for the generative task. Here, we explore the idea of using internal chaotic dynamics in high-dimensional chaotic systems as a way to generate new datapoints from a training dataset. We show that simple learning rules can achieve this goal within a set of vanilla architectures and characterize the quality of the generated datapoints through standard accuracy measures.

The purpose of this manuscript is to review my recent activity on three main research topics. The first concerns the nature of low temperature amorphous solids and their relation with the spin glass transition in a magnetic field. This is the subject of the first chapter where I discuss a new model, the KHGPS model, which allows to make some progress. In the second chapter I review a second research line that concerns the study of the rigidity/jamming transitions in particle system models and their relation to constraint satisfaction and optimization problems in high dimension. Finally in the last chapter I review my activity on the problem of the dynamics of learning algorithms in high-dimensional inference and supervised learning problems., Comment: HDR manuscript

Stochastic Gradient Descent (SGD) is an out-of-equilibrium algorithm used extensively to train artificial neural networks. However very little is known on to what extent SGD is crucial for to the success of this technology and, in particular, how much it is effective in optimizing high-dimensional non-convex cost functions as compared to other optimization algorithms such as Gradient Descent (GD). In this work we leverage dynamical mean field theory to benchmark its performances in the high-dimensional limit. To do that, we consider the problem of recovering a hidden high-dimensional non-linearly encrypted signal, a prototype high-dimensional non-convex hard optimization problem. We compare the performances of SGD to GD and we show that SGD largely outperforms GD for sufficiently small batch sizes. In particular, a power law fit of the relaxation time of these algorithms shows that the recovery threshold for SGD with small batch size is smaller than the corresponding one of GD., Comment: 5 pages + appendix. 3 figures

By exploiting the modular RISC-V ISA this paper presents the customization of instruction set with posit\textsuperscript{\texttrademark} arithmetic instructions to provide improved numerical accuracy, well-defined behavior and increased range of representable numbers while keeping the flexibility and benefits of open-source ISA, like no licensing and royalty fee and community development. In this work we present the design, implementation and integration into the low-power Ibex RISC-V core of a full posit processing unit capable to directly implement in hardware the four arithmetic operations (add, sub, mul, div and fma), the inversion, the float-to-posit and posit-to-float conversions. We evaluate speed, power and area of this unit (that we have called Full Posit Processing Unit). The FPPU has been prototyped on Alveo and Kintex FPGAs, and its impact on the metrics of the full-RISC-V core have been evaluated, showing that we can provide real number processing capabilities to the mentioned core with an increase in area limited to $7\%$ for 8-bit posits and to $15\%$ for 16-bit posits. Finally we present tests one the use of posits for deep neural networks with different network models and datasets, showing minimal drop in accuracy when using 16-bit posits instead of 32-bit IEEE floats.

We consider a recently proposed model to understand the rigidity transition in confluent tissues and we derive the dynamical mean field theory (DMFT) equations that describes several types of dynamics of the model in the thermodynamic limit: gradient descent, thermal Langevin noise and active drive. In particular we focus on gradient descent dynamics and we integrate numerically the corresponding DMFT equations. In this case we show that gradient descent is blind to the zero temperature replica symmetry breaking (RSB) transition point. This means that, even if the Gibbs measure in the zero temperature limit displays RSB, this algorithm is able to find its way to a zero energy configuration. We include a discussion on possible extensions of the DMFT derivation to study problems rooted in high-dimensional regression and optimization via the square loss function., Comment: 20 pages, 6 figures, Submission to SciPost

In many complex systems, elementary units live in a chaotic environment and need to adapt their strategies to perform a task, by extracting information from the environment and controlling the feedback loop on it. One of the main example of systems of this kind is provided by recurrent neural networks. In this case, recurrent connections between neurons drive chaotic behavior and when learning takes place, the response of the system to a perturbation should take into account also its feedback on the dynamics of the network itself. In this work, we consider an abstract model of a high-dimensional chaotic system as a paradigmatic model and study its dynamics. We study the model under two particular settings: Hebbian driving and FORCE training. In the first case, we show that Hebbian driving can be used to tune the level of chaos in the dynamics and this reproduces some results recently obtained in the study of more biologically realistic models of recurrent neural networks. In the latter case, we show that the dynamical system can be trained to reproduce simple periodic functions. To do this, we consider the FORCE algorithm -- originally developed to train recurrent neural networks -- and adapt it to our high-dimensional chaotic system. We show that this algorithm drives the dynamics close to an asymptotic attractor the larger the training time. All our results are valid in the thermodynamic limit thanks to an exact analysis of the dynamics through dynamical mean field theory., Comment: 22 pages, 8 figures

The role of uncertainty in data management has become more prominent than ever before, especially because of the growing importance of machine learning-driven applications that produce large uncertain databases. A well-known approach to querying such databases is to blend rule-based reasoning with uncertainty. However, techniques proposed so far struggle with large databases. In this paper, we address this problem by presenting a new technique for probabilistic reasoning that exploits Trigger Graphs (TGs) -- a notion recently introduced for the non-probabilistic setting. The intuition is that TGs can effectively store a probabilistic model by avoiding an explicit materialization of the lineage and by grouping together similar derivations of the same fact. Firstly, we show how TGs can be adapted to support the possible world semantics. Then, we describe techniques for efficiently computing a probabilistic model, and formally establish the correctness of our approach. We also present an extensive empirical evaluation using a prototype called LTGs. Our comparison against other leading engines shows that LTGs is not only faster, even against approximate reasoning techniques, but can also reason over probabilistic databases that existing engines cannot scale to.

We study the exact controllability of the evolution equation \begin{equation*} u'(t)+Au(t)+p(t)Bu(t)=0 \end{equation*} where $A$ is a nonnegative self-adjoint operator on a Hilbert space $X$ and $B$ is an unbounded linear operator on $X$, which is dominated by the square root of $A$. The control action is bilinear and only of scalar-input form, meaning that the control is the scalar function $p$, which is assumed to depend only on time. Furthermore, we only consider square-integrable controls. Our main result is the local exact controllability of the above equation to the ground state solution, that is, the evolution through time, of the first eigenfunction of $A$, as initial data. The analogous problem (in a more general form) was addressed in our previous paper [Exact controllablity to eigensolutions for evolution equations of parabolic type via bilinear control, Alabau-Boussouira F., Cannarsa P. and Urbani C., Nonlinear Diff. Eq. Appl. (2022)] for a bounded operator $B$. The current extension to unbounded operators allows for many more applications, including the Fokker-Planck equation in one space dimension, and a larger class of control actions., Comment: 39 pages

Canyon landscapes in high dimension can be described as manifolds of small, but extensive dimension, immersed in a higher dimensional ambient space and characterized by a zero potential energy on the manifold. Here we consider the problem of a quantum particle exploring a prototype of a high-dimensional random canyon landscape. We characterize the thermal partition function and show that around the point where the classical phase space has a satisfiability transition so that zero potential energy canyons disappear, moderate quantum fluctuations have a deleterious effect and induce glassy phases at temperature where classical thermal fluctuations alone would thermalize the system. Surprisingly we show that even when, classically, diffusion is expected to be unbounded in space, the interplay between quantum fluctuations and the randomness of the canyon landscape conspire to have a confining effect., Comment: 4 pages, 2 figures

Amorphous solids at low temperature display unusual features which have been escaped a clear and unified comprehension. In recent years a mean field theory of amorphous solids constructed in the limit of infinite spatial dimensions has been proposed. I will briefly review what is the outcome of this theory focusing the low temperature phase and discuss some perspectives to go beyond the mean field limit., Comment: To appear as a contribution to the edited volume "Spin Glass Theory & Far Beyond - Replica Symmetry Breaking after 40 Years", World Scientific

We study a two-layer energy balance model, that allows for vertical exchanges between a surface layer and the atmosphere. The evolution equations of the surface temperature and the atmospheric temperature are coupled by the emission of infrared radiation by one level, that emission being captured by the other layer, and the effect of all non radiative vertical exchanges of energy. Therefore, an essential parameter is the absorptivity of the atmosphere, denoted $\epsilon_a$. The value of $\epsilon_a$ depends critically on greenhouse gases: increasing concentrations of $CO_2$ and $CH_4$ lead to a more opaque atmosphere with higher values of $\epsilon_a$. First we prove that global existence of solutions of the system holds if and only if $\epsilon_a \in (0, 2)$, and blow up in finite time occurs if $\epsilon_a > 2$. (Note that the physical range of values for $\epsilon_a$ is $(0, 1]$.) Next, we explain the long time dynamics for $\epsilon_a \in (0, 2)$, and we prove that all solutions converge to some equilibrium point. Finally, motivated by the physical context, we study the dependence of the equilibrium points with respect to the involved parameters, and we prove in particular that the surface temperature increases with respect to $\epsilon_a$. This is the key mathematical manifestation of the greenhouse effect., Comment: 56 pages, 17 figues

Models of confluent tissues are built out of tessellations of the space (both in two and three dimensions) in which the cost function is constructed in such a way that individual cells try to optimize their volume and surface in order to reach a target shape. At zero temperature, many of these models exhibit a rigidity transition that separates two phases: a liquid phase and a solid (glassy) phase. This phenomenology is now well established but the theoretical understanding is still not complete. In this work we consider an exactly soluble mean field model for the rigidity transition which is based on an abstract mapping. We replace volume and surface functions by random non-linear functions of a large number of degrees of freedom forced to be on a compact phase space. We then seek for a configuration of the degrees of freedom such that these random non-linear functions all attain the same value. This target value is a control parameter and plays the role of the target cell shape in biological tissue models. Therefore we map the microscopic models of cells to a random continuous constraint satisfaction problem (CCSP) with equality constraints. We argue that at zero temperature, the rigidity transition corresponds to the satisfiability transition of the problem. We also characterize both the satisfiable (SAT) and unsatisfiable (UNSAT) phase. In the SAT phase, before reaching the rigidity transition, the zero temperature SAT landscape undergoes an RSB/ergodicity breaking transition of the same type as the Gardner transition in amorphous solids. By solving the RSB equations we compute the SAT/UNSAT threshold and the critical behavior around it. In the UNSAT phase we also compute the average shape index as a function of the target one and we compare the thermodynamical solution of the model with the results of the numerical greedy minimization of the corresponding cost function., Comment: 16 pages, 3 figures. Eq (17) and descendants corrected. Figures corrected

We study reasoning with existential rules to perform query answering over streams of data. On static databases, this problem has been widely studied, but its extension to rapidly changing data has not yet been considered. To bridge this gap, we extend LARS, a well-known framework for rule-based stream reasoning, to support existential rules. For that, we show how to translate LARS with existentials into a semantics-preserving set of existential rules. As query answering with such rules is undecidable in general, we describe how to leverage the temporal nature of streams and present suitable notions of acyclicity that ensure decidability., Comment: Accepted at KR 2022

We introduce a finite dimensional anharmonic soft spin glass in a field and show how it allows the construction a field theory at zero temperature and the corresponding loop expansion. The mean field level of the model coincides with a recently introduced fully connected model, the KHGPS model, and it has a spin glass transition in a field at zero temperature driven by the appearance of pseudogapped non-linear excitations. We analyze the zero temperature limit of the theory and the behavior of the bare masses and couplings on approaching the mean field zero temperature critical point. Focusing on the so called replicon sector of the field theory, we show that the bare mass corresponding to fluctuations in this sector is strictly positive at the transition in a certain region of control parameter space. At the same time the two relevant cubic coupling constants $g_1$ and $g_2$ show a non-analytic behavior in their bare values: approaching the critical point at zero temperature, $g_1\to \infty$ while $g_2\propto T$ with a prefactor diverging at the transition. Along the same lines we also develop the field theory to study the density of states of the model in finite dimension. We show that in the mean field limit the density of states converges to the one of the KHGPS model. However the construction allows a treatment of finite dimensional effects in perturbation theory., Comment: 13 pages

Stochastic Gradient Descent (SGD) is the workhorse algorithm of deep learning technology. At each step of the training phase, a mini batch of samples is drawn from the training dataset and the weights of the neural network are adjusted according to the performance on this specific subset of examples. The mini-batch sampling procedure introduces a stochastic dynamics to the gradient descent, with a non-trivial state-dependent noise. We characterize the stochasticity of SGD and a recently-introduced variant, \emph{persistent} SGD, in a prototypical neural network model. In the under-parametrized regime, where the final training error is positive, the SGD dynamics reaches a stationary state and we define an effective temperature from the fluctuation-dissipation theorem, computed from dynamical mean-field theory. We use the effective temperature to quantify the magnitude of the SGD noise as a function of the problem parameters. In the over-parametrized regime, where the training error vanishes, we measure the noise magnitude of SGD by computing the average distance between two replicas of the system with the same initialization and two different realizations of SGD noise. We find that the two noise measures behave similarly as a function of the problem parameters. Moreover, we observe that noisier algorithms lead to wider decision boundaries of the corresponding constraint satisfaction problem., Comment: 7 pages + appendix, 5 figures

We consider the linear degenerate wave equation, on the interval $(0, 1)$ $$ w_{tt} - (x^\alpha w_x)_x = p(t) \mu (x) w, $$ with bilinear control $p$ and Neumann boundary conditions. We study the controllability of this nonlinear control system, locally around a constant reference trajectory, the ground state. We prove that, generically with respect to $\mu$, any target close to the ground state in the $H^3\times H^2$ topology (suitably adapted to the underlying degenerate operator) is reachable in time $T > \frac{4}{2-\alpha}$, with controls in $L^2((0, T ),\mathbb R)$. Under some classical and generic assumption on $\mu$, we prove that there exists a threshold value for time, $T_0= \frac{4}{2-\alpha}$, such that the reachable set is: - a neighborhood of the ground state if $T>T_0$, - contained in a $C^1$-submanifold of infinite codimension if $T

Partial differential equation on networks have been widely investigated in the last decades in view of their application to quantum mechanics (Schr\"odinger type equations) or to the analysis of flexible structures (wave type equations). Nevertheless, very few results are available for diffusive models despite an increasing demand arising from life sciences such as neurobiology. This paper analyzes the controllability properties of the heat equation on a compact network under the action of a single input bilinear control. By adapting a recent method due to [F.~Alabau-Boussouira, P.~Cannarsa and C.~Urbani, {\em Exact controllability to eigensolutions for evolution equations of parabolic type via bilinear control}, arXiv:1811.08806], an exact controllability result to the eigensolutions of the uncontrolled problem is obtained in this work. A crucial step has been the construction of a suitable biorthogonal family under a non-uniform gap condition of the eigenvalues of the Laplacian on a graph. Application to star graphs and tadpole graphs are included., Comment: 20 pages, 4 fugures

We study the problem of performing automatic stance classification on social media with neural architectures such as BERT. Although these architectures deliver impressive results, their level is not yet comparable to the one of humans and they might produce errors that have a significant impact on the downstream task (e.g., fact-checking). To improve the performance, we present a new neural architecture where the input also includes automatically generated negated perspectives over a given claim. The model is jointly learned to make simultaneously multiple predictions, which can be used either to improve the classification of the original perspective or to filter out doubtful predictions. In the first case, we propose a weakly supervised method for combining the predictions into a final one. In the second case, we show that using the confidence scores to remove doubtful predictions allows our method to achieve human-like performance over the retained information, which is still a sizable part of the original input., Comment: Accepted at EMNLP 2021

Tables in scientific papers contain a wealth of valuable knowledge for the scientific enterprise. To help the many of us who frequently consult this type of knowledge, we present Tab2Know, a new end-to-end system to build a Knowledge Base (KB) from tables in scientific papers. Tab2Know addresses the challenge of automatically interpreting the tables in papers and of disambiguating the entities that they contain. To solve these problems, we propose a pipeline that employs both statistical-based classifiers and logic-based reasoning. First, our pipeline applies weakly supervised classifiers to recognize the type of tables and columns, with the help of a data labeling system and an ontology specifically designed for our purpose. Then, logic-based reasoning is used to link equivalent entities (via sameAs links) in different tables. An empirical evaluation of our approach using a corpus of papers in the Computer Science domain has returned satisfactory performance. This suggests that ours is a promising step to create a large-scale KB of scientific knowledge., Comment: 17 pages, 4 figures, conference: The Semantic Web -- ISWC 2020

We investigate the properties of the glass phase of a recently introduced spin glass model of soft spins subjected to an anharmonic quartic local potential, which serves as a model of low temperature molecular or soft glasses. We solve the model using mean field theory and show that, at low temperatures, it is described by full replica symmetry breaking (fullRSB). As a consequence, at zero temperature the glass phase is marginally stable. We show that in this case, marginal stability comes from a combination of both soft linear excitations -- appearing in a gapless spectrum of the Hessian of linear excitations -- and pseudogapped non-linear excitations -- corresponding to nearly degenerate two level systems. Therefore, this model is a natural candidate to describe what happens in soft glasses, where quasi localized soft modes in the density of states appear together with non-linear modes triggering avalanches and conjectured to be essential to describe the universal low-temperature anomalies of glasses., Comment: main+appendix, 6 figures

We consider high dimensional random optimization problems where the dynamical variables are subjected to non-convex excluded volume constraints. We focus on the case in which the cost function is a simple quadratic cost and the excluded volume constraints are modeled by a perceptron constraint satisfaction problem. We show that depending on the density of constraints, one can have different situations. If the number of constraints is small, one typically has a phase where the ground state of the cost function is unique and sits on the boundary of the island of configurations allowed by the constraints. In this case, there is a hypostatic number of marginally satisfied constraints. If the number of constraints is increased one enters a glassy phase where the cost function has many local minima sitting again on the boundary of the regions of allowed configurations. At the phase transition point, the total number of marginally satisfied constraints becomes equal to the number of degrees of freedom in the problem and therefore we say that these minima are isostatic. We conjecture that by increasing further the constraints the system stays isostatic up to the point where the volume of available phase space shrinks to zero. We derive our results using the replica method and we also analyze a dynamical algorithm, the Karush-Kuhn-Tucker algorithm, through dynamical mean-field theory and we show how to recover the results of the replica approach in the replica symmetric phase., Comment: 7 pages, 3 figures

In a separable Hilbert space $X$, we study the controlled evolution equation \begin{equation*} u'(t)+Au(t)+p(t)Bu(t)=0, \end{equation*} where $A\geq-\sigma I$ ($\sigma\geq0$) is a self-adjoint linear operator, $B$ is a bounded linear operator on $X$, and $p\in L^2_{loc}(0,+\infty)$ is a bilinear control. We give sufficient conditions in order for the above nonlinear control system to be locally controllable to the $j$th eigensolution for any $j\geq1$. We also derive semi-global controllability results in large time and discuss applications to parabolic equations in low space dimension. Our method is constructive and all the constants involved in the main results can be explicitly computed., Comment: 29 pages, 2 figures

In this paper we investigate how gradient-based algorithms such as gradient descent, (multi-pass) stochastic gradient descent, its persistent variant, and the Langevin algorithm navigate non-convex loss-landscapes and which of them is able to reach the best generalization error at limited sample complexity. We consider the loss landscape of the high-dimensional phase retrieval problem as a prototypical highly non-convex example. We observe that for phase retrieval the stochastic variants of gradient descent are able to reach perfect generalization for regions of control parameters where the gradient descent algorithm is not. We apply dynamical mean-field theory from statistical physics to characterize analytically the full trajectories of these algorithms in their continuous-time limit, with a warm start, and for large system sizes. We further unveil several intriguing properties of the landscape and the algorithms such as that the gradient descent can obtain better generalization properties from less informed initializations., Comment: 28 pages, 11 figures

The optimization step in many machine learning problems rarely relies on vanilla gradient descent but it is common practice to use momentum-based accelerated methods. Despite these algorithms being widely applied to arbitrary loss functions, their behaviour in generically non-convex, high dimensional landscapes is poorly understood. In this work, we use dynamical mean field theory techniques to describe analytically the average dynamics of these methods in a prototypical non-convex model: the (spiked) matrix-tensor model. We derive a closed set of equations that describe the behaviour of heavy-ball momentum and Nesterov acceleration in the infinite dimensional limit. By numerical integration of these equations, we observe that these methods speed up the dynamics but do not improve the algorithmic threshold with respect to gradient descent in the spiked model., Comment: To appear in NeurIPS 2021

The chase is a well-established family of algorithms used to materialize Knowledge Bases (KBs), like Knowledge Graphs (KGs), to tackle important tasks like query answering under dependencies or data cleaning. A general problem of chase algorithms is that they might perform redundant computations. To counter this problem, we introduce the notion of Trigger Graphs (TGs), which guide the execution of the rules avoiding redundant computations. We present the results of an extensive theoretical and empirical study that seeks to answer when and how TGs can be computed and what are the benefits of TGs when applied over real-world KBs. Our results include introducing algorithms that compute (minimal) TGs. We implemented our approach in a new engine, and our experiments show that it can be significantly more efficient than the chase enabling us to materialize KBs with 17B facts in less than 40 min on commodity machines.

Mean field optimal control problems are a class of optimization problems that arise from optimal control when applied to the many body setting. In the noisy case one has a set of controllable stochastic processes and a cost function that is a functional of their trajectories. The goal of the optimization is to minimize this cost over the control variables. Here we consider the case in which we have $N$ stochastic processes, or agents, with the associated control variables, which interact in a disordered way so that the resulting cost function is random. The goal is to find the average minimal cost for $N\to \infty$, when a typical realization of the quenched random interactions is considered. We introduce a simple model and show how to perform a dimensional reduction from the infinite dimensional case to a set of one dimensional stochastic partial differential equations of the Hamilton-Jacobi-Bellman and Fokker-Planck type. The statistical properties of the corresponding stochastic terms must be computed self-consistently, as we show explicitly., Comment: 9 pages