@inproceedings{7437, abstract = {Most of today's distributed machine learning systems assume reliable networks: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the delivery of the message. At the same time, recent work exhibits the impressive tolerance of machine learning algorithms to errors or noise arising from relaxed communication or synchronization. In this paper, we connect these two trends, and consider the following question: Can we design machine learning systems that are tolerant to network unreliability during training? With this motivation, we focus on a theoretical problem of independent interest-given a standard distributed parameter server architecture, if every communication between the worker and the server has a non-zero probability p of being dropped, does there exist an algorithm that still converges, and at what speed? The technical contribution of this paper is a novel theoretical analysis proving that distributed learning over unreliable network can achieve comparable convergence rate to centralized or distributed learning over reliable networks. Further, we prove that the influence of the packet drop rate diminishes with the growth of the number of parameter servers. We map this theoretical result onto a real-world scenario, training deep neural networks over an unreliable network layer, and conduct network simulation to validate the system improvement by allowing the networks to be unreliable.}, author = {Yu, Chen and Tang, Hanlin and Renggli, Cedric and Kassing, Simon and Singla, Ankit and Alistarh, Dan-Adrian and Zhang, Ce and Liu, Ji}, booktitle = {36th International Conference on Machine Learning, ICML 2019}, isbn = {9781510886988}, location = {Long Beach, CA, United States}, pages = {12481--12512}, publisher = {IMLS}, title = {{Distributed learning over unreliable networks}}, volume = {2019-June}, year = {2019}, } @article{7451, abstract = {We prove that the observable telegraph signal accompanying the bistability in the photon-blockade-breakdown regime of the driven and lossy Jaynes–Cummings model is the finite-size precursor of what in the thermodynamic limit is a genuine first-order phase transition. We construct a finite-size scaling of the system parameters to a well-defined thermodynamic limit, in which the system remains the same microscopic system, but the telegraph signal becomes macroscopic both in its timescale and intensity. The existence of such a finite-size scaling completes and justifies the classification of the photon-blockade-breakdown effect as a first-order dissipative quantum phase transition.}, author = {Vukics, A. and Dombi, A. and Fink, Johannes M and Domokos, P.}, issn = {2521-327X}, journal = {Quantum}, publisher = {Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften}, title = {{Finite-size scaling of the photon-blockade breakdown dissipative quantum phase transition}}, doi = {10.22331/q-2019-06-03-150}, volume = {3}, year = {2019}, } @inbook{7453, abstract = {We illustrate the ingredients of the state-of-the-art of model-based approach for the formal design and verification of cyber-physical systems. To capture the interaction between a discrete controller and its continuously evolving environment, we use the formal models of timed and hybrid automata. We explain the steps of modeling and verification in the tools Uppaal and SpaceEx using a case study based on a dual-chamber implantable pacemaker monitoring a human heart. We show how to design a model as a composition of components, how to construct models at varying levels of detail, how to establish that one model is an abstraction of another, how to specify correctness requirements using temporal logic, and how to verify that a model satisfies a logical requirement.}, author = {Alur, Rajeev and Giacobbe, Mirco and Henzinger, Thomas A and Larsen, Kim G. and Mikučionis, Marius}, booktitle = {Computing and Software Science}, editor = {Steffen, Bernhard and Woeginger, Gerhard}, isbn = {9783319919072}, issn = {0302-9743}, pages = {452--477}, publisher = {Springer Nature}, title = {{Continuous-time models for system design and analysis}}, doi = {10.1007/978-3-319-91908-9_22}, volume = {10000}, year = {2019}, } @inproceedings{7468, abstract = {We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation of the original energy minimization problem using a multi plane block-coordinate Frank-Wolfe method that takes advantage of the specific structure of the Lagrangean decomposition. We show empirically that our method outperforms state-of-the-art Lagrangean decomposition based algorithms on some challenging Markov Random Field, multi-label discrete tomography and graph matching problems.}, author = {Swoboda, Paul and Kolmogorov, Vladimir}, booktitle = {Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition}, isbn = {9781728132938}, issn = {10636919}, location = {Long Beach, CA, United States}, publisher = {IEEE}, title = {{Map inference via block-coordinate Frank-Wolfe algorithm}}, doi = {10.1109/CVPR.2019.01140}, volume = {2019-June}, year = {2019}, } @inproceedings{7479, abstract = {Multi-exit architectures, in which a stack of processing layers is interleaved with early output layers, allow the processing of a test example to stop early and thus save computation time and/or energy. In this work, we propose a new training procedure for multi-exit architectures based on the principle of knowledge distillation. The method encourage searly exits to mimic later, more accurate exits, by matching their output probabilities. Experiments on CIFAR100 and ImageNet show that distillation-based training significantly improves the accuracy of early exits while maintaining state-of-the-art accuracy for late ones. The method is particularly beneficial when training data is limited and it allows a straightforward extension to semi-supervised learning,i.e. making use of unlabeled data at training time. Moreover, it takes only afew lines to implement and incurs almost no computational overhead at training time, and none at all at test time.}, author = {Bui Thi Mai, Phuong and Lampert, Christoph}, booktitle = {IEEE International Conference on Computer Vision}, isbn = {9781728148038}, issn = {15505499}, location = {Seoul, Korea}, pages = {1355--1364}, publisher = {IEEE}, title = {{Distillation-based training for multi-exit architectures}}, doi = {10.1109/ICCV.2019.00144}, volume = {2019-October}, year = {2019}, } @inbook{7513, abstract = {Social insects (i.e., ants, termites and the social bees and wasps) protect their colonies from disease using a combination of individual immunity and collectively performed defenses, termed social immunity. The first line of social immune defense is sanitary care, which is performed by colony members to protect their pathogen-exposed nestmates from developing an infection. If sanitary care fails and an infection becomes established, a second line of social immune defense is deployed to stop disease transmission within the colony and to protect the valuable queens, which together with the males are the reproductive individuals of the colony. Insect colonies are separated into these reproductive individuals and the sterile worker force, forming a superorganismal reproductive unit reminiscent of the differentiated germline and soma in a multicellular organism. Ultimately, the social immune response preserves the germline of the superorganism insect colony and increases overall fitness of the colony in case of disease. }, author = {Cremer, Sylvia and Kutzer, Megan}, booktitle = {Encyclopedia of Animal Behavior}, editor = {Choe, Jae}, isbn = {9780128132517}, pages = {747--755}, publisher = {Elsevier}, title = {{Social immunity}}, doi = {10.1016/B978-0-12-809633-8.90721-0}, year = {2019}, } @unpublished{7524, abstract = {We prove a lower bound for the free energy (per unit volume) of the two-dimensional Bose gas in the thermodynamic limit. We show that the free energy at density $\rho$ and inverse temperature $\beta$ differs from the one of the non-interacting system by the correction term $4 \pi \rho^2 |\ln a^2 \rho|^{-1} (2 - [1 - \beta_{\mathrm{c}}/\beta]_+^2)$. Here $a$ is the scattering length of the interaction potential, $[\cdot]_+ = \max\{ 0, \cdot \}$ and $\beta_{\mathrm{c}}$ is the inverse Berezinskii--Kosterlitz--Thouless critical temperature for superfluidity. The result is valid in the dilute limit $a^2\rho \ll 1$ and if $\beta \rho \gtrsim 1$.}, author = {Deuchert, Andreas and Mayer, Simon and Seiringer, Robert}, booktitle = {arXiv:1910.03372}, pages = {61}, publisher = {ArXiv}, title = {{The free energy of the two-dimensional dilute Bose gas. I. Lower bound}}, year = {2019}, } @inproceedings{7542, abstract = {We present a novel class of convolutional neural networks (CNNs) for set functions,i.e., data indexed with the powerset of a finite set. The convolutions are derivedas linear, shift-equivariant functions for various notions of shifts on set functions.The framework is fundamentally different from graph convolutions based on theLaplacian, as it provides not one but several basic shifts, one for each element inthe ground set. Prototypical experiments with several set function classificationtasks on synthetic datasets and on datasets derived from real-world hypergraphsdemonstrate the potential of our new powerset CNNs.}, author = {Wendler, Chris and Alistarh, Dan-Adrian and Püschel, Markus}, issn = {1049-5258}, location = {Vancouver, Canada}, pages = {927--938}, publisher = {Neural Information Processing Systems Foundation}, title = {{Powerset convolutional neural networks}}, volume = {32}, year = {2019}, } @article{7550, abstract = {We consider an optimal control problem for an abstract nonlinear dissipative evolution equation. The differential constraint is penalized by augmenting the target functional by a nonnegative global-in-time functional which is null-minimized in the evolution equation is satisfied. Different variational settings are presented, leading to the convergence of the penalization method for gradient flows, noncyclic and semimonotone flows, doubly nonlinear evolutions, and GENERIC systems. }, author = {Portinale, Lorenzo and Stefanelli, Ulisse}, issn = {1343-4373}, journal = {Advances in Mathematical Sciences and Applications}, number = {2}, pages = {425--447}, publisher = {Gakko Tosho}, title = {{Penalization via global functionals of optimal-control problems for dissipative evolution}}, volume = {28}, year = {2019}, } @unpublished{7552, abstract = {There is increasing evidence that protein binding to specific sites along DNA can activate the reading out of genetic information without coming into direct physical contact with the gene. There also is evidence that these distant but interacting sites are embedded in a liquid droplet of proteins which condenses out of the surrounding solution. We argue that droplet-mediated interactions can account for crucial features of gene regulation only if the droplet is poised at a non-generic point in its phase diagram. We explore a minimal model that embodies this idea, show that this model has a natural mechanism for self-tuning, and suggest direct experimental tests. }, author = {Bialek, William and Gregor, Thomas and Tkačik, Gašper}, booktitle = {arXiv:1912.08579}, pages = {5}, publisher = {ArXiv}, title = {{Action at a distance in transcriptional regulation}}, year = {2019}, } @inproceedings{7576, abstract = {We present the results of a friendly competition for formal verification of continuous and hybrid systems with nonlinear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this year, 6 tools Ariadne, CORA, DynIbex, Flow*, Isabelle/HOL, and JuliaReach (in alphabetic order) participated. They are applied to solve reachability analysis problems on four benchmark problems, one of them with hybrid dynamics. We do not rank the tools based on the results, but show the current status and discover the potential advantages of different tools.}, author = {Immler, Fabian and Althoff, Matthias and Benet, Luis and Chapoutot, Alexandre and Chen, Xin and Forets, Marcelo and Geretti, Luca and Kochdumper, Niklas and Sanders, David P. and Schilling, Christian}, booktitle = {EPiC Series in Computing}, issn = {23987340}, location = {Montreal, Canada}, pages = {41--61}, publisher = {EasyChair Publications}, title = {{ARCH-COMP19 Category Report: Continuous and hybrid systems with nonlinear dynamics}}, doi = {10.29007/m75b}, volume = {61}, year = {2019}, } @inproceedings{7606, abstract = {We derive a tight lower bound on equivocation (conditional entropy), or equivalently a tight upper bound on mutual information between a signal variable and channel outputs. The bound is in terms of the joint distribution of the signals and maximum a posteriori decodes (most probable signals given channel output). As part of our derivation, we describe the key properties of the distribution of signals, channel outputs and decodes, that minimizes equivocation and maximizes mutual information. This work addresses a problem in data analysis, where mutual information between signals and decodes is sometimes used to lower bound the mutual information between signals and channel outputs. Our result provides a corresponding upper bound.}, author = {Hledik, Michal and Sokolowski, Thomas R and Tkačik, Gašper}, booktitle = {IEEE Information Theory Workshop, ITW 2019}, isbn = {9781538669006}, location = {Visby, Sweden}, publisher = {IEEE}, title = {{A tight upper bound on mutual information}}, doi = {10.1109/ITW44776.2019.8989292}, year = {2019}, } @inproceedings{7639, abstract = {Deep neural networks (DNNs) have become increasingly important due to their excellent empirical performance on a wide range of problems. However, regularization is generally achieved by indirect means, largely due to the complex set of functions defined by a network and the difficulty in measuring function complexity. There exists no method in the literature for additive regularization based on a norm of the function, as is classically considered in statistical learning theory. In this work, we study the tractability of function norms for deep neural networks with ReLU activations. We provide, to the best of our knowledge, the first proof in the literature of the NP-hardness of computing function norms of DNNs of 3 or more layers. We also highlight a fundamental difference between shallow and deep networks. In the light on these results, we propose a new regularization strategy based on approximate function norms, and show its efficiency on a segmentation task with a DNN.}, author = {Rannen-Triki, Amal and Berman, Maxim and Kolmogorov, Vladimir and Blaschko, Matthew B.}, booktitle = {Proceedings of the 2019 International Conference on Computer Vision Workshop}, isbn = {9781728150239}, location = {Seoul, South Korea}, publisher = {IEEE}, title = {{Function norms for neural networks}}, doi = {10.1109/ICCVW.2019.00097}, year = {2019}, } @inproceedings{7640, abstract = {We propose a new model for detecting visual relationships, such as "person riding motorcycle" or "bottle on table". This task is an important step towards comprehensive structured mage understanding, going beyond detecting individual objects. Our main novelty is a Box Attention mechanism that allows to model pairwise interactions between objects using standard object detection pipelines. The resulting model is conceptually clean, expressive and relies on well-justified training and prediction procedures. Moreover, unlike previously proposed approaches, our model does not introduce any additional complex components or hyperparameters on top of those already required by the underlying detection model. We conduct an experimental evaluation on two datasets, V-COCO and Open Images, demonstrating strong quantitative and qualitative results.}, author = {Kolesnikov, Alexander and Kuznetsova, Alina and Lampert, Christoph and Ferrari, Vittorio}, booktitle = {Proceedings of the 2019 International Conference on Computer Vision Workshop}, isbn = {9781728150239}, location = {Seoul, South Korea}, publisher = {IEEE}, title = {{Detecting visual relationships using box attention}}, doi = {10.1109/ICCVW.2019.00217}, year = {2019}, } @unpublished{7950, abstract = {The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.}, author = {Biniaz, Ahmad and Jain, Kshitij and Lubiw, Anna and Masárová, Zuzana and Miltzow, Tillmann and Mondal, Debajyoti and Naredla, Anurag Murty and Tkadlec, Josef and Turcotte, Alexi}, booktitle = {arXiv}, title = {{Token swapping on trees}}, year = {2019}, } @article{8, abstract = {Despite their different origins, Drosophila glia and hemocytes are related cell populations that provide an immune function. Drosophila hemocytes patrol the body cavity and act as macrophages outside the nervous system whereas glia originate from the neuroepithelium and provide the scavenger population of the nervous system. Drosophila glia are hence the functional orthologs of vertebrate microglia, even though the latter are cells of immune origin that subsequently move into the brain during development. Interestingly, the Drosophila immune cells within (glia) and outside the nervous system (hemocytes) require the same transcription factor Glide/Gcm for their development. This raises the issue of how do glia specifically differentiate in the nervous system and hemocytes in the procephalic mesoderm. The Repo homeodomain transcription factor and pan-glial direct target of Glide/Gcm is known to ensure glial terminal differentiation. Here we show that Repo also takes center stage in the process that discriminates between glia and hemocytes. First, Repo expression is repressed in the hemocyte anlagen by mesoderm-specific factors. Second, Repo ectopic activation in the procephalic mesoderm is sufficient to repress the expression of hemocyte-specific genes. Third, the lack of Repo triggers the expression of hemocyte markers in glia. Thus, a complex network of tissue-specific cues biases the potential of Glide/Gcm. These data allow us to revise the concept of fate determinants and help us understand the bases of cell specification. Both sexes were analyzed.SIGNIFICANCE STATEMENTDistinct cell types often require the same pioneer transcription factor, raising the issue of how does one factor trigger different fates. In Drosophila, glia and hemocytes provide a scavenger activity within and outside the nervous system, respectively. While they both require the Glide/Gcm transcription factor, glia originate from the ectoderm, hemocytes from the mesoderm. Here we show that tissue-specific factors inhibit the gliogenic potential of Glide/Gcm in the mesoderm by repressing the expression of the homeodomain protein Repo, a major glial-specific target of Glide/Gcm. Repo expression in turn inhibits the expression of hemocyte-specific genes in the nervous system. These cell-specific networks secure the establishment of the glial fate only in the nervous system and allow cell diversification.}, author = {Trébuchet, Guillaume and Cattenoz, Pierre B and Zsámboki, János and Mazaud, David and Siekhaus, Daria E and Fanto, Manolis and Giangrande, Angela}, journal = {Journal of Neuroscience}, number = {2}, pages = {238--255}, publisher = {Society for Neuroscience}, title = {{The Repo homeodomain transcription factor suppresses hematopoiesis in Drosophila and preserves the glial fate}}, doi = {10.1523/JNEUROSCI.1059-18.2018}, volume = {39}, year = {2019}, } @article{80, abstract = {We consider an interacting, dilute Bose gas trapped in a harmonic potential at a positive temperature. The system is analyzed in a combination of a thermodynamic and a Gross–Pitaevskii (GP) limit where the trap frequency ω, the temperature T, and the particle number N are related by N∼ (T/ ω) 3→ ∞ while the scattering length is so small that the interaction energy per particle around the center of the trap is of the same order of magnitude as the spectral gap in the trap. We prove that the difference between the canonical free energy of the interacting gas and the one of the noninteracting system can be obtained by minimizing the GP energy functional. We also prove Bose–Einstein condensation in the following sense: The one-particle density matrix of any approximate minimizer of the canonical free energy functional is to leading order given by that of the noninteracting gas but with the free condensate wavefunction replaced by the GP minimizer.}, author = {Deuchert, Andreas and Seiringer, Robert and Yngvason, Jakob}, journal = {Communications in Mathematical Physics}, number = {2}, pages = {723--776}, publisher = {Springer}, title = {{Bose–Einstein condensation in a dilute, trapped gas at positive temperature}}, doi = {10.1007/s00220-018-3239-0}, volume = {368}, year = {2019}, } @inproceedings{8175, abstract = {We study edge asymptotics of poissonized Plancherel-type measures on skew Young diagrams (integer partitions). These measures can be seen as generalizations of those studied by Baik--Deift--Johansson and Baik--Rains in resolving Ulam's problem on longest increasing subsequences of random permutations and the last passage percolation (corner growth) discrete versions thereof. Moreover they interpolate between said measures and the uniform measure on partitions. In the new KPZ-like 1/3 exponent edge scaling limit with logarithmic corrections, we find new probability distributions generalizing the classical Tracy--Widom GUE, GOE and GSE distributions from the theory of random matrices.}, author = {Betea, Dan and Bouttier, Jérémie and Nejjar, Peter and Vuletíc, Mirjana}, booktitle = {Proceedings on the 31st International Conference on Formal Power Series and Algebraic Combinatorics}, location = {Ljubljana, Slovenia}, publisher = {Formal Power Series and Algebraic Combinatorics}, title = {{New edge asymptotics of skew Young diagrams via free boundaries}}, year = {2019}, } @unpublished{8182, abstract = {Suppose that $n\neq p^k$ and $n\neq 2p^k$ for all $k$ and all primes $p$. We prove that for any Hausdorff compactum $X$ with a free action of the symmetric group $\mathfrak S_n$ there exists an $\mathfrak S_n$-equivariant map $X \to {\mathbb R}^n$ whose image avoids the diagonal $\{(x,x\dots,x)\in {\mathbb R}^n|x\in {\mathbb R}\}$. Previously, the special cases of this statement for certain $X$ were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of $\mathfrak S_n$-equivariant maps from the boundary $\partial\Delta^{n-1}$ of $(n-1)$-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser's conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem.}, author = {Avvakumov, Sergey and Kudrya, Sergey}, booktitle = {arXiv}, publisher = {arXiv}, title = {{Vanishing of all equivariant obstructions and the mapping degree}}, year = {2019}, } @unpublished{8184, abstract = {Denote by ∆N the N-dimensional simplex. A map f : ∆N → Rd is an almost r-embedding if fσ1∩. . .∩fσr = ∅ whenever σ1, . . . , σr are pairwise disjoint faces. A counterexample to the topological Tverberg conjecture asserts that if r is not a prime power and d ≥ 2r + 1, then there is an almost r-embedding ∆(d+1)(r−1) → Rd. This was improved by Blagojevi´c–Frick–Ziegler using a simple construction of higher-dimensional counterexamples by taking k-fold join power of lower-dimensional ones. We improve this further (for d large compared to r): If r is not a prime power and N := (d+ 1)r−r l d + 2 r + 1 m−2, then there is an almost r-embedding ∆N → Rd. For the r-fold van Kampen–Flores conjecture we also produce counterexamples which are stronger than previously known. Our proof is based on generalizations of the Mabillard–Wagner theorem on construction of almost r-embeddings from equivariant maps, and of the Ozaydin theorem on existence of equivariant maps. }, author = {Avvakumov, Sergey and Karasev, R. and Skopenkov, A.}, booktitle = {arXiv}, publisher = {arXiv}, title = {{Stronger counterexamples to the topological Tverberg conjecture}}, year = {2019}, }