Search

Current progress in artificial intelligence is centered around so-called large language models that consist of neural networks processing long sequences of high-dimensional vectors called tokens. Statistical physics provides powerful tools to study the functioning of learning with neural networks and has played a recognized role in the development of modern machine learning. The statistical physics approach relies on simplified and analytically tractable models of data. However, simple tractable models for long sequences of high-dimensional tokens are largely underexplored. Inspired by the crucial role models such as the single-layer teacher-student perceptron (aka generalized linear regression) played in the theory of fully connected neural networks, in this paper, we introduce and study the bilinear sequence regression (BSR) as one of the most basic models for sequences of tokens. We note that modern architectures naturally subsume the BSR model due to the skip connections. Building on recent methodological progress, we compute the Bayes-optimal generalization error for the model in the limit of long sequences of high-dimensional tokens, and provide a message-passing algorithm that matches this performance. We quantify the improvement that optimal learning brings with respect to vectorizing the sequence of tokens and learning via simple linear regression. We also unveil surprising properties of the gradient descent algorithms in the BSR model.

Given a sequence of $d \times d$ symmetric matrices $\{\mathbf{W}_i\}_{i=1}^n$, and a margin $\Delta > 0$, we investigate whether it is possible to find signs $(\epsilon_1, \dots, \epsilon_n) \in \{\pm 1\}^n$ such that the operator norm of the signed sum satisfies $\|\sum_{i=1}^n \epsilon_i \mathbf{W}_i\|_\mathrm{op} \leq \Delta$. Kunisky and Zhang (2023) recently introduced a random version of this problem, where the matrices $\{\mathbf{W}_i\}_{i=1}^n$ are drawn from the Gaussian orthogonal ensemble. This model can be seen as a random variant of the celebrated Matrix Spencer conjecture and as a matrix-valued analog of the symmetric binary perceptron in statistical physics. In this work, we establish a satisfiability transition in this problem as $n, d \to \infty$ with $n / d^2 \to \tau > 0$. Our contributions are twofold. First, we prove that the expected number of solutions with margin $\Delta=\kappa \sqrt{n}$ has a sharp threshold at a critical $\tau_1(\kappa)$: for $\tau < \tau_1(\kappa)$ the problem is typically unsatisfiable, while for $\tau > \tau_1(\kappa)$ the average number of solutions becomes exponentially large. Second, combining a second-moment method with recent results from Altschuler (2023) on margin concentration in perceptron-type problems, we identify a second threshold $\tau_2(\kappa)$, such that for $\tau>\tau_2(\kappa)$ the problem admits solutions with high probability. In particular, we establish for the first time that a system of $n = \Theta(d^2)$ Gaussian random matrices can be balanced so that the spectrum of the resulting matrix macroscopically shrinks compared to the typical semicircle law. Our proofs rely on deriving concentration inequalities and large deviation properties for the law of correlated Gaussian matrices under spectral norm constraints, extending results in the literature and offering insights of independent interest., Comment: 29 pages, 2 figures

Generating realistic and diverse layouts of furnished indoor 3D scenes unlocks multiple interactive applications impacting a wide range of industries. The inherent complexity of object interactions, the limited amount of available data and the requirement to fulfill spatial constraints all make generative modeling for 3D scene synthesis and arrangement challenging. Current methods address these challenges autoregressively or by using off-the-shelf diffusion objectives by simultaneously predicting all attributes without 3D reasoning considerations. In this paper, we introduce DeBaRA, a score-based model specifically tailored for precise, controllable and flexible arrangement generation in a bounded environment. We argue that the most critical component of a scene synthesis system is to accurately establish the size and position of various objects within a restricted area. Based on this insight, we propose a lightweight conditional score-based model designed with 3D spatial awareness at its core. We demonstrate that by focusing on spatial attributes of objects, a single trained DeBaRA model can be leveraged at test time to perform several downstream applications such as scene synthesis, completion and re-arrangement. Further, we introduce a novel Self Score Evaluation procedure so it can be optimally employed alongside external LLM models. We evaluate our approach through extensive experiments and demonstrate significant improvement upon state-of-the-art approaches in a range of scenarios., Comment: NeurIPS 2024

In this paper, we study a discrete-time analogue of a Hawkes process, modelled as a Poisson autoregressive process whose parameters depend on the past of the trajectory. The model is characterized to allow these parameters to take negative values, modelling inhibitory dynamics. More precisely, the model is the stochastic process $(\Tilde X_n)_{n\ge0}$ with parameters $a_1,\ldots,a_p \in \R$, $p\in\N$ and $\lambda > 0$, such that for all $n\ge p$, conditioned on $\Tilde X_0,\ldots,\Tilde X_{n-1}$, $\Tilde X_n$ is Poisson distributed with parameter \[ \left(a_1 \Tilde X_{n-1} + \cdots + a_p \Tilde X_{n-p} + \lambda \right)_+. \] This process can be seen as a discrete time Hawkes process with inhibition with a memory of length $p$. %This work is an extension of a prior work where we studied the specific case $p = 2$, for which we were able to classify the asymptotic behaviour of the process for the whole range of parameters, except for boundary cases. We first provide a sufficient condition for stability in the general case which is the analog of a condition for continuous time Hawkes processes from \cite{costa_renewal_2020}. We then focus on the case $p=3$, extending the results derived for the $p=2$ case in a previous work \cite{Costa_Maillard_Muraro_2024}. In particular, we show that the process may be stable even if one of the coefficients $a_i$ is much greater than one.

Microorganisms hosted in abiotic structures have led to engineered living materials that can grow, sense and adapt in ways that mimic biological systems. Although porous structures should favor colonization by microorganisms, they have not yet been exploited as abiotic scaffolds for the development of living materials. Here, we report porous ceramics that are colonized by bacteria to form an engineered living material with self-regulated and genetically programmable carbon capture and gas-sensing functionalities. The carbon capture capability is achieved using wild-type photosynthetic cyanobacteria, whereas the gas-sensing function is generated utilizing genetically engineered E. coli. Hierarchical porous clay is used as ceramic scaffold and evaluated in terms of bacterial growth, water uptake and mechanical properties. Using state-of-the-art chemical analysis techniques, we demonstrate the ability of the living porous ceramics to capture CO2 directly from the air and to metabolically turn minute amounts of a toxic gas into a benign scent detectable by humans.

We consider the problem of learning a target function corresponding to a single hidden layer neural network, with a quadratic activation function after the first layer, and random weights. We consider the asymptotic limit where the input dimension and the network width are proportionally large. Recent work [Cui & al '23] established that linear regression provides Bayes-optimal test error to learn such a function when the number of available samples is only linear in the dimension. That work stressed the open challenge of theoretically analyzing the optimal test error in the more interesting regime where the number of samples is quadratic in the dimension. In this paper, we solve this challenge for quadratic activations and derive a closed-form expression for the Bayes-optimal test error. We also provide an algorithm, that we call GAMP-RIE, which combines approximate message passing with rotationally invariant matrix denoising, and that asymptotically achieves the optimal performance. Technically, our result is enabled by establishing a link with recent works on optimal denoising of extensive-rank matrices and on the ellipsoid fitting problem. We further show empirically that, in the absence of noise, randomly-initialized gradient descent seems to sample the space of weights, leading to zero training loss, and averaging over initialization leads to a test error equal to the Bayes-optimal one., Comment: 47 pages

We consider the situation when a learner faces a set of unknown discrete distributions $(p_k)_{k\in \mathcal K}$ defined over a common alphabet $\mathcal X$, and can build for each distribution $p_k$ an individual high-probability confidence set thanks to $n_k$ observations sampled from $p_k$. The set $(p_k)_{k\in \mathcal K}$ is structured: each distribution $p_k$ is obtained from the same common, but unknown, distribution q via applying an unknown permutation to $\mathcal X$. We call this \emph{permutation-equivalence}. The goal is to build refined confidence sets \emph{exploiting} this structural property. Like other popular notions of structure (Lipschitz smoothness, Linearity, etc.) permutation-equivalence naturally appears in machine learning problems, and to benefit from its potential gain calls for a specific approach. We present a strategy to effectively exploit permutation-equivalence, and provide a finite-time high-probability bound on the size of the refined confidence sets output by the strategy. Since a refinement is not possible for too few observations in general, under mild technical assumptions, our finite-time analysis establish when the number of observations $(n_k)_{k\in \mathcal K}$ are large enough so that the output confidence sets improve over initial individual sets. We carefully characterize this event and the corresponding improvement. Further, our result implies that the size of confidence sets shrink at asymptotic rates of $O(1/\sqrt{\sum_{k\in \mathcal K} n_k})$ and $O(1/\max_{k\in K} n_{k})$, respectively for elements inside and outside the support of q, when the size of each individual confidence set shrinks at respective rates of $O(1/\sqrt{n_k})$ and $O(1/n_k)$. We illustrate the practical benefit of exploiting permutation equivalence on a reinforcement learning task.

Monte-Carlo Tree Search (MCTS) is a widely-used strategy for online planning that combines Monte-Carlo sampling with forward tree search. Its success relies on the Upper Confidence bound for Trees (UCT) algorithm, an extension of the UCB method for multi-arm bandits. However, the theoretical foundation of UCT is incomplete due to an error in the logarithmic bonus term for action selection, leading to the development of Fixed-Depth-MCTS with a polynomial exploration bonus to balance exploration and exploitation~\citep{shah2022journal}. Both UCT and Fixed-Depth-MCTS suffer from biased value estimation: the weighted sum underestimates the optimal value, while the maximum valuation overestimates it~\citep{coulom2006efficient}. The power mean estimator offers a balanced solution, lying between the average and maximum values. Power-UCT~\citep{dam2019generalized} incorporates this estimator for more accurate value estimates but its theoretical analysis remains incomplete. This paper introduces Stochastic-Power-UCT, an MCTS algorithm using the power mean estimator and tailored for stochastic MDPs. We analyze its polynomial convergence in estimating root node values and show that it shares the same convergence rate of $\mathcal{O}(n^{-1/2})$, with $n$ is the number of visited trajectories, as Fixed-Depth-MCTS, with the latter being a special case of the former. Our theoretical results are validated with empirical tests across various stochastic MDP environments., Comment: UAI 2024 conference

A major impediment to the advancement of sign language translation (SLT) is data scarcity. Much of the sign language data currently available on the web cannot be used for training supervised models due to the lack of aligned captions. Furthermore, scaling SLT using large-scale web-scraped datasets bears privacy risks due to the presence of biometric information, which the responsible development of SLT technologies should account for. In this work, we propose a two-stage framework for privacy-aware SLT at scale that addresses both of these issues. We introduce SSVP-SLT, which leverages self-supervised video pretraining on anonymized and unannotated videos, followed by supervised SLT finetuning on a curated parallel dataset. SSVP-SLT achieves state-of-the-art finetuned and zero-shot gloss-free SLT performance on the How2Sign dataset, outperforming the strongest respective baselines by over 3 BLEU-4. Based on controlled experiments, we further discuss the advantages and limitations of self-supervised pretraining and anonymization via facial obfuscation for SLT., Comment: ACL 2024

The CREM is a Gaussian process indexed by a binary tree of depth $T$, introduced by Derrida and Spohn, then Bovier and Kurkova as a toy model of a spin glass. Addario-Berry and the second author have established the existence of an algorithmic hardness threshold $x_*$ in the CREM: finding a state of energy lower than $-xT$ is possible in polynomial time if $xx_*$, with high probability. In this article, we are interested in the nature of the transition from polynomial to exponential complexity near the algorithmic hardness threshold. We do this by studying in detail the performance of a certain beam-search algorithm of beam width $N=N(T)$ depending on $T$. The algorithm turns out to be essentially equivalent to the time-inhomogeneous version of the so-called $N$-particle branching Brownian motion ($N$-BBM), which has seen a lot of interest in the last two decades. We prove the existence of three regimes: a subcritical regime when $\log N(T)\ll T^{1/3}$, a critical regime when $\log N(T)\asymp T^{1/3}$ and a supercritical regime when $\log N(T)\gg T^{1/3}$. In the subcritical regime, the output of the algorithm, i.e. the maximal displacement of the $N$-BBM, behaves asymptotically as predicted by a generalization of the so-called Brunet-Derrida correction for the classical (homogeneous) $N$-BBM, In the supercritical regime, the output of the algorithm is subject to two phenomena: on the one hand it begins to grow very slowly (logarithmically) in terms of $N$; and on the other hand its dependency in the parameter $\sigma(\cdot)$ governing the time-inhomogeneity becomes more intricate. The critical regime interpolates continuously between the two other regimes, with the appearance of explicit formulae involving Airy functions, building on results on branching random walks by Mallein., Comment: 73 pages, 3 figures

We present a signal-foreground separation algorithm for filtering observational data to extract spectral distortions of the cosmic microwave background (CMB). Our linear method, called the least response method (LRM), is based on the idea of simultaneously minimizing the response to all possible foregrounds with poorly defined spectral shapes and random noise while maintaining a constant response to the signal of interest. This idea was introduced in detail in our previous paper. Here, we have expanded our analysis by taking into consideration all the main foregrounds. We draw a detailed comparison between our approach and the moment internal linear combination method, which is a modification of the internal linear combination technique previously used for CMB anisotropy maps. We demonstrate advantages of LRM and evaluate the prospects for measuring various types of spectral distortions. Besides, we show that LRM suggests the possibility of its improvements if we use an iterative approach with sequential separation and partial subtraction of foreground components from the observed signal. In addition, we estimate the optimal temperature that the telescope's optical system should have in order to detect the chemical type $\mu$ distortions. We present a design of an instrument where, according to our estimates, the optimal contrast between its thermal emission and the CMB allows us to measure such distortions., Comment: 13 pages, 6 figures

Large-scale automatic speech translation systems today lack key features that help machine-mediated communication feel seamless when compared to human-to-human dialogue. In this work, we introduce a family of models that enable end-to-end expressive and multilingual translations in a streaming fashion. First, we contribute an improved version of the massively multilingual and multimodal SeamlessM4T model-SeamlessM4T v2. This newer model, incorporating an updated UnitY2 framework, was trained on more low-resource language data. SeamlessM4T v2 provides the foundation on which our next two models are initiated. SeamlessExpressive enables translation that preserves vocal styles and prosody. Compared to previous efforts in expressive speech research, our work addresses certain underexplored aspects of prosody, such as speech rate and pauses, while also preserving the style of one's voice. As for SeamlessStreaming, our model leverages the Efficient Monotonic Multihead Attention mechanism to generate low-latency target translations without waiting for complete source utterances. As the first of its kind, SeamlessStreaming enables simultaneous speech-to-speech/text translation for multiple source and target languages. To ensure that our models can be used safely and responsibly, we implemented the first known red-teaming effort for multimodal machine translation, a system for the detection and mitigation of added toxicity, a systematic evaluation of gender bias, and an inaudible localized watermarking mechanism designed to dampen the impact of deepfakes. Consequently, we bring major components from SeamlessExpressive and SeamlessStreaming together to form Seamless, the first publicly available system that unlocks expressive cross-lingual communication in real-time. The contributions to this work are publicly released and accessible at https://github.com/facebookresearch/seamless_communication

Dependently typed proof assistant rely crucially on definitional equality, which relates types and terms that are automatically identified in the underlying type theory. This paper extends type theory with definitional functor laws, equations satisfied propositionally by a large class of container-like type constructors $F : \mathrm{Type} \to \mathrm{Type}$, equipped with a $\mathrm{map}_{F} : (A \to B) \to F\,A \to F\,B$, such as lists or trees. Promoting these equations to definitional ones strengthens the theory, enabling slicker proofs and more automation for functorial type constructors. This extension is used to modularly justify a structural form of coercive subtyping, propagating subtyping through type formers in a map-like fashion. We show that the resulting notion of coercive subtyping, thanks to the extra definitional equations, is equivalent to a natural and implicit form of subsumptive subtyping. The key result of decidability of type-checking in a dependent type system with functor laws for lists has been entirely mechanized in Coq. This is the extended version of the work with the same name published at ESOP'24.

We present an extensive mechanization of the meta-theory of Martin-L\"of Type Theory (MLTT) in the Coq proof assistant. Our development builds on pre-existing work in Agda to show not only the decidability of conversion, but also the decidability of type checking, using an approach guided by bidirectional type checking. From our proof of decidability, we obtain a certified and executable type checker for a full-fledged version of MLTT with support for $\Pi$, $\Sigma$, $\mathbb{N}$, and identity types, and one universe. Furthermore, our development does not rely on impredicativity, induction-recursion or any axiom beyond MLTT with a schema for indexed inductive types and a handful of predicative universes, narrowing the gap between the object theory and the meta-theory to a mere difference in universes. Finally, we explain our formalization choices, geared towards a modular development relying on Coq's features, e.g. meta-programming facilities provided by tactics and universe polymorphism.

This paper is a plea for diagonals and telescopers of rational, or algebraic, functions using creative telescoping, in a computer algebra experimental mathematics learn-by-examples approach. We show that diagonals of rational functions (and this is also the case with diagonals of algebraic functions) are left invariant when one performs an infinite set of birational transformations on the rational functions. These invariance results generalize to telescopers. We cast light on the almost systematic property of homomorphism to their adjoint of the telescopers of rational, or algebraic, functions. We shed some light on the reason why the telescopers, annihilating the diagonals of rational functions of the form P/Q^k and 1/Q, are homomorphic. For telescopers with solutions (periods) corresponding to integration over non-vanishing cycles, we have a slight generalization of this result. We introduce some challenging examples of generalization of diagonals of rational functions, like diagonals of transcendental functions, yielding simple $_2F_1$ hypergeometric functions associated with elliptic curves, or (differentially algebraic) lambda-extension of correlation of the Ising model., Comment: 48 pages

We consider the problem $(\rm P)$ of exactly fitting an ellipsoid (centered at $0$) to $n$ standard Gaussian random vectors in $\mathbb{R}^d$, as $n, d \to \infty$ with $n / d^2 \to \alpha > 0$. This problem is conjectured to undergo a sharp transition: with high probability, $(\rm P)$ has a solution if $\alpha < 1/4$, while $(\rm P)$ has no solutions if $\alpha > 1/4$. So far, only a trivial bound $\alpha > 1/2$ is known to imply the absence of solutions, while the sharpest results on the positive side assume $\alpha \leq \eta$ (for $\eta > 0$ a small constant) to prove that $(\rm P)$ is solvable. In this work we study universality between this problem and a so-called "Gaussian equivalent", for which the same transition can be rigorously analyzed. Our main results are twofold. On the positive side, we prove that if $\alpha < 1/4$, there exist an ellipsoid fitting all the points up to a small error, and that the lengths of its principal axes are bounded above and below. On the other hand, for $\alpha > 1/4$, we show that achieving small fitting error is not possible if the length of the ellipsoid's shortest axis does not approach $0$ as $d \to \infty$ (and in particular there does not exist any ellipsoid fit whose shortest axis length is bounded away from $0$ as $d \to \infty$). To the best of our knowledge, our work is the first rigorous result characterizing the expected phase transition in ellipsoid fitting at $\alpha = 1/4$. In a companion non-rigorous work, the first author and D. Kunisky give a general analysis of ellipsoid fitting using the replica method of statistical physics, which inspired the present work., Comment: 45 pages

We consider the problem of fitting a centered ellipsoid to $n$ standard Gaussian random vectors in $\mathbb{R}^d$, as $n, d \to \infty$ with $n/d^2 \to \alpha > 0$. It has been conjectured that this problem is, with high probability, satisfiable (SAT; that is, there exists an ellipsoid passing through all $n$ points) for $\alpha < 1/4$, and unsatisfiable (UNSAT) for $\alpha > 1/4$. In this work we give a precise analytical argument, based on the non-rigorous replica method of statistical physics, that indeed predicts a SAT/UNSAT transition at $\alpha = 1/4$, as well as the shape of a typical fitting ellipsoid in the SAT phase (i.e., the lengths of its principal axes). Besides the replica method, our main tool is the dilute limit of extensive-rank "HCIZ integrals" of random matrix theory. We further study different explicit algorithmic constructions of the matrix characterizing the ellipsoid. In particular, we show that a procedure based on minimizing its nuclear norm yields a solution in the whole SAT phase. Finally, we characterize the SAT/UNSAT transition for ellipsoid fitting of a large class of rotationally-invariant random vectors. Our work suggests mathematically rigorous ways to analyze fitting ellipsoids to random vectors, which is the topic of a companion work., Comment: 41 pages. Update to match the published version

We consider branching Brownian motion in which initially there is one particle at $x$, particles produce a random number of offspring with mean $m+1$ at the time of branching events, and each particle branches at rate $\beta = 1/2m$. Particles independently move according to Brownian motion with drift $-1$ and are killed at the origin. It is well-known that this process eventually dies out with positive probability. We condition this process to survive for an unusually large time $t$ and study the behavior of the process at small times $s \ll t$ using a spine decomposition. We show, in particular, that the time when a particle gets furthest from the origin is of the order $t^{5/6}$.

We investigate the regret-minimisation problem in a multi-armed bandit setting with arbitrary corruptions. Similar to the classical setup, the agent receives rewards generated independently from the distribution of the arm chosen at each time. However, these rewards are not directly observed. Instead, with a fixed $\varepsilon\in (0,\frac{1}{2})$, the agent observes a sample from the chosen arm's distribution with probability $1-\varepsilon$, or from an arbitrary corruption distribution with probability $\varepsilon$. Importantly, we impose no assumptions on these corruption distributions, which can be unbounded. In this setting, accommodating potentially unbounded corruptions, we establish a problem-dependent lower bound on regret for a given family of arm distributions. We introduce CRIMED, an asymptotically-optimal algorithm that achieves the exact lower bound on regret for bandits with Gaussian distributions with known variance. Additionally, we provide a finite-sample analysis of CRIMED's regret performance. Notably, CRIMED can effectively handle corruptions with $\varepsilon$ values as high as $\frac{1}{2}$. Furthermore, we develop a tight concentration result for medians in the presence of arbitrary corruptions, even with $\varepsilon$ values up to $\frac{1}{2}$, which may be of independent interest. We also discuss an extension of the algorithm for handling misspecification in Gaussian model., Comment: 50 pages; 4 figures

This paper introduces a novel backup strategy for Monte-Carlo Tree Search (MCTS) designed for highly stochastic and partially observable Markov decision processes. We adopt a probabilistic approach, modeling both value and action-value nodes as Gaussian distributions. We introduce a novel backup operator that computes value nodes as the Wasserstein barycenter of their action-value children nodes; thus, propagating the uncertainty of the estimate across the tree to the root node. We study our novel backup operator when using a novel combination of $L^1$-Wasserstein barycenter with $\alpha$-divergence, by drawing a notable connection to the generalized mean backup operator. We complement our probabilistic backup operator with two sampling strategies, based on optimistic selection and Thompson sampling, obtaining our Wasserstein MCTS algorithm. We provide theoretical guarantees of asymptotic convergence to the optimal policy, and an empirical evaluation on several stochastic and partially observable environments, where our approach outperforms well-known related baselines.

What does it take to create the Babel Fish, a tool that can help individuals translate speech between any two languages? While recent breakthroughs in text-based models have pushed machine translation coverage beyond 200 languages, unified speech-to-speech translation models have yet to achieve similar strides. More specifically, conventional speech-to-speech translation systems rely on cascaded systems that perform translation progressively, putting high-performing unified systems out of reach. To address these gaps, we introduce SeamlessM4T, a single model that supports speech-to-speech translation, speech-to-text translation, text-to-speech translation, text-to-text translation, and automatic speech recognition for up to 100 languages. To build this, we used 1 million hours of open speech audio data to learn self-supervised speech representations with w2v-BERT 2.0. Subsequently, we created a multimodal corpus of automatically aligned speech translations. Filtered and combined with human-labeled and pseudo-labeled data, we developed the first multilingual system capable of translating from and into English for both speech and text. On FLEURS, SeamlessM4T sets a new standard for translations into multiple target languages, achieving an improvement of 20% BLEU over the previous SOTA in direct speech-to-text translation. Compared to strong cascaded models, SeamlessM4T improves the quality of into-English translation by 1.3 BLEU points in speech-to-text and by 2.6 ASR-BLEU points in speech-to-speech. Tested for robustness, our system performs better against background noises and speaker variations in speech-to-text tasks compared to the current SOTA model. Critically, we evaluated SeamlessM4T on gender bias and added toxicity to assess translation safety. Finally, all contributions in this work are open-sourced and accessible at https://github.com/facebookresearch/seamless_communication

(Abridged) Massive stars can determine the evolution of molecular clouds with their strong ultraviolet (UV) radiation fields. Moreover, UV radiation is relevant in setting the thermal gas pressure in star-forming clouds, whose influence can extend from the rims of molecular clouds to entire star-forming galaxies. Probing the fundamental structure of nearby molecular clouds is therefore crucial to understand how massive stars shape their surrounding medium and how fast molecular clouds are destroyed, specifically at their UV-illuminated edges, where models predict an intermediate zone of neutral atomic gas between the molecular cloud and the surrounding ionized gas whose size is directly related to the exposed physical conditions. We present the highest angular resolution (~$0.5$", corresponding to $207$ au) and velocity-resolved images of the molecular gas emission in the Horsehead nebula, using CO J=3-2 and HCO$^+$ J=4-3 observations with ALMA. We find that CO and HCO$^+$ are present at the edge of the cloud, very close to the ionization (H$^+$/H) and dissociation fronts (H/H$_2$), suggesting a very thin layer of neutral atomic gas (<$650$ au) and a small amount of CO-dark gas ($A_V=0.006-0.26$ mag) for stellar UV illumination conditions typical of molecular clouds in the Milky Way. The new ALMA observations reveal a web of molecular gas filaments with an estimated thermal gas pressure of $P_{\mathrm{th}} = (2.3 - 4.0) \times 10^6$ K cm$^{-3}$, and the presence of a steep density gradient at the cloud edge that can be well explained by stationary isobaric PDR models with pressures consistent with our estimations. However, in the HII region and PDR interface, we find $P_{\mathrm{th,PDR}} > P_{\mathrm{th,HII}}$, suggesting the gas is slightly compressed. Therefore, dynamical effects cannot be completely ruled out and even higher angular observations will be needed to unveil their role., Comment: 15 pages, 1 table, 9 figures; Accepted for publication in A&A

The discovery of patterns associated with diagnosis, prognosis, and therapy response in digital pathology images often requires intractable labeling of large quantities of histological objects. Here we release an open-source labeling tool, PatchSorter, which integrates deep learning with an intuitive web interface. Using >100,000 objects, we demonstrate a >7x improvement in labels per second over unaided labeling, with minimal impact on labeling accuracy, thus enabling high-throughput labeling of large datasets., Comment: The submission includes 15 pages, 8 figures, 1 table, and 30 references. It is a new submission

We consider the problem $(\mathrm{P})$ of fitting $n$ standard Gaussian random vectors in $\mathbb{R}^d$ to the boundary of a centered ellipsoid, as $n, d \to \infty$. This problem is conjectured to have a sharp feasibility transition: for any $\varepsilon > 0$, if $n \leq (1 - \varepsilon) d^2 / 4$ then $(\mathrm{P})$ has a solution with high probability, while $(\mathrm{P})$ has no solutions with high probability if $n \geq (1 + \varepsilon) d^2 /4$. So far, only a trivial bound $n \geq d^2 / 2$ is known on the negative side, while the best results on the positive side assume $n \leq d^2 / \mathrm{polylog}(d)$. In this work, we improve over previous approaches using a key result of Bartl & Mendelson (2022) on the concentration of Gram matrices of random vectors under mild assumptions on their tail behavior. This allows us to give a simple proof that $(\mathrm{P})$ is feasible with high probability when $n \leq d^2 / C$, for a (possibly large) constant $C > 0$., Comment: 17 pages; Update (v2) to match the published version

Recently, the scientific community has questioned the statistical reproducibility of many empirical results, especially in the field of machine learning. To solve this reproducibility crisis, we propose a theoretically sound methodology to compare the overall performance of multiple algorithms with stochastic returns. We exemplify our methodology in Deep RL. Indeed, the performance of one execution of a Deep RL algorithm is random. Therefore, several independent executions are needed to accurately evaluate the overall performance. When comparing several RL algorithms, a major question is how many executions must be made and how can we ensure that the results of such a comparison are theoretically sound. When comparing several algorithms at once, the error of each comparison may accumulate and must be taken into account with a multiple tests procedure to preserve low error guarantees. We introduce AdaStop, a new statistical test based on multiple group sequential tests. When comparing algorithms, AdaStop adapts the number of executions to stop as early as possible while ensuring that we have enough information to distinguish algorithms that perform better than the others in a statistical significant way. We prove theoretically and empirically that AdaStop has a low probability of making a (family-wise) error. Finally, we illustrate the effectiveness of AdaStop in multiple Deep RL use-cases, including toy examples and challenging Mujoco environments. AdaStop is the first statistical test fitted to this sort of comparisons: AdaStop is both a significant contribution to statistics, and a major contribution to computational studies performed in reinforcement learning and in other domains. To summarize our contribution, we introduce AdaStop, a formally grounded statistical tool to let anyone answer the practical question: ``Is my algorithm the new state-of-the-art?''.