TY - JOUR AB - In the last few years, various communication compression techniques have emerged as an indispensable tool helping to alleviate the communication bottleneck in distributed learning. However, despite the fact biased compressors often show superior performance in practice when compared to the much more studied and understood unbiased compressors, very little is known about them. In this work we study three classes of biased compression operators, two of which are new, and their performance when applied to (stochastic) gradient descent and distributed (stochastic) gradient descent. We show for the first time that biased compressors can lead to linear convergence rates both in the single node and distributed settings. We prove that distributed compressed SGD method, employed with error feedback mechanism, enjoys the ergodic rate O(δLexp[−μKδL]+(C+δD)Kμ), where δ≥1 is a compression parameter which grows when more compression is applied, L and μ are the smoothness and strong convexity constants, C captures stochastic gradient noise (C=0 if full gradients are computed on each node) and D captures the variance of the gradients at the optimum (D=0 for over-parameterized models). Further, via a theoretical study of several synthetic and empirical distributions of communicated gradients, we shed light on why and by how much biased compressors outperform their unbiased variants. Finally, we propose several new biased compressors with promising theoretical guarantees and practical performance. AU - Beznosikov, Aleksandr AU - Horvath, Samuel AU - Richtarik, Peter AU - Safaryan, Mher ID - 14815 JF - Journal of Machine Learning Research TI - On biased compression for distributed learning VL - 24 ER - TY - CONF AB - In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the TOKEN SLIDING model. In this problem, a graph is provided along with its two dominating sets, which can be imagined as tokens placed on vertices. The objective is to find a shortest sequence of dominating sets that transforms one set into the other, with each set in the sequence resulting from sliding a single token in the previous set. While identifying any sequence has been well studied, our work presents the first polynomial algorithms for this optimization variant in the context of dominating sets. AU - Křišťan, Jan Matyáš AU - Svoboda, Jakub ID - 14456 SN - 0302-9743 T2 - 24th International Symposium on Fundamentals of Computation Theory TI - Shortest dominating set reconfiguration under token sliding VL - 14292 ER - TY - CONF AB - This paper explores a modular design architecture aimed at helping blockchains (and other SMR implementation) to scale to a very large number of processes. This comes in contrast to existing monolithic architectures that interleave transaction dissemination, ordering, and execution in a single functionality. To achieve this we first split the monolith to multiple layers which can use existing distributed computing primitives. The exact specifications of the data dissemination part are formally defined by the Proof of Availability & Retrieval (PoA &R) abstraction. Solutions to the PoA &R problem contain two related sub-protocols: one that “pushes” information into the network and another that “pulls” this information. Regarding the latter, there is a dearth of research literature which is rectified in this paper. We present a family of pulling sub-protocols and rigorously analyze them. Extensive simulations support the theoretical claims of efficiency and robustness in case of a very large number of players. Finally, actual implementation and deployment on a small number of machines (roughly the size of several industrial systems) demonstrates the viability of the architecture’s paradigm. AU - Cohen, Shir AU - Goren, Guy AU - Kokoris Kogias, Eleftherios AU - Sonnino, Alberto AU - Spiegelman, Alexander ID - 14829 SN - 0302-9743 T2 - 27th International Conference on Financial Cryptography and Data Security TI - Proof of availability and retrieval in a modular blockchain architecture VL - 13951 ER - TY - JOUR AB - Understanding complex living systems, which are fundamentally constrained by physical phenomena, requires combining experimental data with theoretical physical and mathematical models. To develop such models, collaborations between experimental cell biologists and theoreticians are increasingly important but these two groups often face challenges achieving mutual understanding. To help navigate these challenges, this Perspective discusses different modelling approaches, including bottom-up hypothesis-driven and top-down data-driven models, and highlights their strengths and applications. Using cell mechanics as an example, we explore the integration of specific physical models with experimental data from the molecular, cellular and tissue level up to multiscale input. We also emphasize the importance of constraining model complexity and outline strategies for crosstalk between experimental design and model development. Furthermore, we highlight how physical models can provide conceptual insights and produce unifying and generalizable frameworks for biological phenomena. Overall, this Perspective aims to promote fruitful collaborations that advance our understanding of complex biological systems. AU - Schwayer, Cornelia AU - Brückner, David ID - 14827 IS - 24 JF - Journal of Cell Science KW - Cell Biology SN - 0021-9533 TI - Connecting theory and experiment in cell and tissue mechanics VL - 136 ER - TY - CONF AB - We study the problem of learning controllers for discrete-time non-linear stochastic dynamical systems with formal reach-avoid guarantees. This work presents the first method for providing formal reach-avoid guarantees, which combine and generalize stability and safety guarantees, with a tolerable probability threshold p in [0,1] over the infinite time horizon. Our method leverages advances in machine learning literature and it represents formal certificates as neural networks. In particular, we learn a certificate in the form of a reach-avoid supermartingale (RASM), a novel notion that we introduce in this work. Our RASMs provide reachability and avoidance guarantees by imposing constraints on what can be viewed as a stochastic extension of level sets of Lyapunov functions for deterministic systems. Our approach solves several important problems -- it can be used to learn a control policy from scratch, to verify a reach-avoid specification for a fixed control policy, or to fine-tune a pre-trained policy if it does not satisfy the reach-avoid specification. We validate our approach on 3 stochastic non-linear reinforcement learning tasks. AU - Zikelic, Dorde AU - Lechner, Mathias AU - Henzinger, Thomas A AU - Chatterjee, Krishnendu ID - 14830 IS - 10 KW - General Medicine SN - 2159-5399 T2 - Proceedings of the 37th AAAI Conference on Artificial Intelligence TI - Learning control policies for stochastic systems with reach-avoid guarantees VL - 37 ER - TY - JOUR AB - Understanding the factors that have shaped the current distributions and diversity of species is a central and longstanding aim of evolutionary biology. The recent inclusion of genomic data into phylogeographic studies has dramatically improved our understanding in organisms where evolutionary relationships have been challenging to infer. We used whole-genome sequences to study the phylogeography of the intertidal snail Littorina saxatilis, which has successfully colonized and diversified across a broad range of coastal environments in the Northern Hemisphere amid repeated cycles of glaciation. Building on past studies based on short DNA sequences, we used genome-wide data to provide a clearer picture of the relationships among samples spanning most of the species natural range. Our results confirm the trans-Atlantic colonization of North America from Europe, and have allowed us to identify rough locations of glacial refugia and to infer likely routes of colonization within Europe. We also investigated the signals in different datasets to account for the effects of genomic architecture and non-neutral evolution, which provides new insights about diversification of four ecotypes of L. saxatilis (the crab, wave, barnacle, and brackish ecotypes) at different spatial scales. Overall, we provide a much clearer picture of the biogeography of L. saxatilis, providing a foundation for more detailed phylogenomic and demographic studies. AU - Stankowski, Sean AU - Zagrodzka, Zuzanna B AU - Galindo, Juan AU - Montaño-Rendón, Mauricio AU - Faria, Rui AU - Mikhailova, Natalia AU - Blakeslee, April M H AU - Arnason, Einar AU - Broquet, Thomas AU - Morales, Hernán E AU - Grahame, John W AU - Westram, Anja M AU - Johannesson, Kerstin AU - Butlin, Roger K ID - 14833 IS - 1 JF - Evolutionary Journal of the Linnean Society TI - Whole-genome phylogeography of the intertidal snail Littorina saxatilis VL - 2 ER - TY - JOUR AB - Catalysis, the acceleration of product formation by a substance that is left unchanged, typically results from multiple elementary processes, including diffusion of the reactants toward the catalyst, chemical steps, and release of the products. While efforts to design catalysts are often focused on accelerating the chemical reaction on the catalyst, catalysis is a global property of the catalytic cycle that involves all processes. These are controlled by both intrinsic parameters such as the composition and shape of the catalyst and extrinsic parameters such as the concentration of the chemical species at play. We examine here the conditions that catalysis imposes on the different steps of a reaction cycle and the respective role of intrinsic and extrinsic parameters of the system on the emergence of catalysis by using an approach based on first-passage times. We illustrate this approach for various decompositions of a catalytic cycle into elementary steps, including non-Markovian decompositions, which are useful when the presence and nature of intermediate states are a priori unknown. Our examples cover different types of reactions and clarify the constraints on elementary steps and the impact of species concentrations on catalysis. AU - Sakref, Yann AU - Muñoz Basagoiti, Maitane AU - Zeravcic, Zorana AU - Rivoire, Olivier ID - 14831 IS - 51 JF - The Journal of Physical Chemistry B KW - Materials Chemistry KW - Surfaces KW - Coatings and Films KW - Physical and Theoretical Chemistry SN - 1520-6106 TI - On kinetic constraints that catalysis imposes on elementary processes VL - 127 ER - TY - JOUR AB - Many cell functions require a concerted effort from multiple membrane proteins, for example, for signaling, cell division, and endocytosis. One contribution to their successful self-organization stems from the membrane deformations that these proteins induce. While the pairwise interaction potential of two membrane-deforming spheres has recently been measured, membrane-deformation-induced interactions have been predicted to be nonadditive, and hence their collective behavior cannot be deduced from this measurement. We here employ a colloidal model system consisting of adhesive spheres and giant unilamellar vesicles to test these predictions by measuring the interaction potential of the simplest case of three membrane-deforming, spherical particles. We quantify their interactions and arrangements and, for the first time, experimentally confirm and quantify the nonadditive nature of membrane-deformation-induced interactions. We furthermore conclude that there exist two favorable configurations on the membrane: (1) a linear and (2) a triangular arrangement of the three spheres. Using Monte Carlo simulations, we corroborate the experimentally observed energy minima and identify a lowering of the membrane deformation as the cause for the observed configurations. The high symmetry of the preferred arrangements for three particles suggests that arrangements of many membrane-deforming objects might follow simple rules. AU - Azadbakht, Ali AU - Meadowcroft, Billie AU - Majek, Juraj AU - Šarić, Anđela AU - Kraft, Daniela J. ID - 14844 JF - Biophysical Journal SN - 0006-3495 TI - Nonadditivity in interactions between three membrane-wrapped colloidal spheres ER - TY - GEN AB - Cover Page AU - Becker, Lea Marie AU - Berbon, Mélanie AU - Vallet, Alicia AU - Grelard, Axelle AU - Morvan, Estelle AU - Bardiaux, Benjamin AU - Lichtenecker, Roman AU - Ernst, Matthias AU - Loquet, Antoine AU - Schanda, Paul ID - 14861 IS - 19 KW - General Chemistry KW - Catalysis SN - 1433-7851 T2 - Angewandte Chemie International Edition TI - Cover Picture: The rigid core and flexible surface of amyloid fibrils probed by Magic‐Angle‐Spinning NMR spectroscopy of aromatic residues VL - 62 ER - TY - JOUR AB - We establish a precise three-term asymptotic expansion, with an optimal estimate of the error term, for the rightmost eigenvalue of an n×n random matrix with independent identically distributed complex entries as n tends to infinity. All terms in the expansion are universal. AU - Cipolloni, Giorgio AU - Erdös, László AU - Schröder, Dominik J AU - Xu, Yuanyuan ID - 14849 IS - 6 JF - The Annals of Probability KW - Statistics KW - Probability and Uncertainty KW - Statistics and Probability SN - 0091-1798 TI - On the rightmost eigenvalue of non-Hermitian random matrices VL - 51 ER -