More Like this

1. Bridging Breiman's Brook: From Algorithmic Modeling to Statistical Learning

   https://doi.org/10.1353/obs.2021.0027.  

   Mentch, Lucas; Hooker, Giles (July 2021, Observational studies)

   null (Ed.)

   In 2001, Leo Breiman wrote of a divide between "data modeling" and "algorithmic modeling" cultures. Twenty years later this division feels far more ephemeral, both in terms of assigning individuals to camps, and in terms of intellectual boundaries. We argue that this is largely due to the "data modelers" incorporating algorithmic methods into their toolbox, particularly driven by recent developments in the statistical understanding of Breiman's own Random Forest methods. While this can be simplistically described as "Breiman won", these same developments also expose the limitations of the prediction-first philosophy that he espoused, making careful statistical analysis all the more important. This paper outlines these exciting recent developments in the random forest literature which, in our view, occurred as a result of a necessary blending of the two ways of thinking Breiman originally described. We also ask what areas statistics and statisticians might currently overlook. 

   more » « less
2. Computability in infinite Galois theory and algorithmically random algebraic fields

   https://doi.org/10.1112/jlms.70017  

   Calvert, Wesley; Harizanov, Valentina; Shlapentokh, Alexandra (November 2024, Journal of the London Mathematical Society)

   Abstract We introduce a notion of algorithmic randomness for algebraic fields. We prove the existence of a continuum of algebraic extensions of that are random according to our definition. We show that there are noncomputable algebraic fields which are not random. We also partially characterize the index set, relative to an oracle, of the set of random algebraic fields computable relative to that oracle. In order to carry out this investigation of randomness for fields, we develop computability in the context of the infinite Galois theory (where the relevant Galois groups are uncountable), including definitions of computable and computably enumerable Galois groups and computability of Haar measure on the Galois groups. 

   more » « less
3. Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size Inputs

   Murphy, R; Srinivasan, B; Rao, V; Riberio, B. (January 2019, International Conference on Learning Representations (ICLR 2019))

   We consider a simple and overarching representation for permutation-invariant functions of sequences (or multiset functions). Our approach, which we call Janossy pooling, expresses a permutation-invariant function as the average of a permutation-sensitive function applied to all reorderings of the input sequence. This allows us to leverage the rich and mature literature on permutation-sensitive functions to construct novel and flexible permutation-invariant functions. If car- ried out naively, Janossy pooling can be computationally prohibitive. To allow computational tractability, we consider three kinds of approximations: canonical orderings of sequences, functions with k-order interactions, and stochastic opti- mization algorithms with random permutations. Our framework unifies a variety of existing work in the literature, and suggests possible modeling and algorithmic extensions. We explore a few in our experiments, which demonstrate improved performance over current state-of-the-art methods. 

   more » « less
4. Shearing in some simple rank one theories

   https://doi.org/10.1007/s11856-023-2547-z  

   Malliaris, M; Shelah, S (November 2023, Israel Journal of Mathematics)

   Dividing asks about inconsistency along indiscernible sequences. In order to study the finer structure of simple theories without much dividing, the authors recently introduced shearing, which essentially asks about inconsistency along generalized indiscernible sequences. Here we characterize the shearing of the random graph. We then use shearing to distinguish between the random graph and the theories $$T_{n,k}$$, the higher-order analogues of the triangle-free random graph. It follows that shearing is distinct from dividing in simple unstable theories, and distinguishes meaningfully between classes of simple unstable rank one theories. The paper begins with an overview of shearing, and includes open questions. 

   more » « less
5. Quasi-static fading MAC with many users and finite payload

   https://doi.org/10.1109/ISIT.2019.8849781  

   Kowshik, S; Polyanskiy, Y. (July 2019, IEEE Int. Symp. Inf. Theory (ISIT))

   Consider a (multiple-access) wireless communication system where users are connected to a unique base station over a shared-spectrum radio links. Each user has a fixed number k of bits to send to the base station, and his signal gets attenuated by a random channel gain (quasi-static fading). In this paper we consider the many-user asymptotics of Chen-Chen-Guo’2017, where the number of users grows linearly with the blocklength. In addition, we adopt a per-user probability of error criterion of Polyanskiy’2017 (as opposed to classical joint-error probability criterion). Under these two settings we derive bounds on the optimal required energy-perbit for reliable multi-access communication. We confirm the curious behaviour (previously observed for non-fading MAC) of the possibility of perfect multi-user interference cancellation for user densities below a critical threshold. Further we demonstrate the suboptimality of standard solutions such as orthogonalization (i.e., TDMA/FDMA) and treating interference as noise (i.e. pseudo-random CDMA without multi-user detection). 

   more » « less