@inproceedings{14198, abstract = {High-dimensional time series are common in many domains. Since human cognition is not optimized to work well in high-dimensional spaces, these areas could benefit from interpretable low-dimensional representations. However, most representation learning algorithms for time series data are difficult to interpret. This is due to non-intuitive mappings from data features to salient properties of the representation and non-smoothness over time. To address this problem, we propose a new representation learning framework building on ideas from interpretable discrete dimensionality reduction and deep generative modeling. This framework allows us to learn discrete representations of time series, which give rise to smooth and interpretable embeddings with superior clustering performance. We introduce a new way to overcome the non-differentiability in discrete representation learning and present a gradient-based version of the traditional self-organizing map algorithm that is more performant than the original. Furthermore, to allow for a probabilistic interpretation of our method, we integrate a Markov model in the representation space. This model uncovers the temporal transition structure, improves clustering performance even further and provides additional explanatory insights as well as a natural representation of uncertainty. We evaluate our model in terms of clustering performance and interpretability on static (Fashion-)MNIST data, a time series of linearly interpolated (Fashion-)MNIST images, a chaotic Lorenz attractor system with two macro states, as well as on a challenging real world medical time series application on the eICU data set. Our learned representations compare favorably with competitor methods and facilitate downstream tasks on the real world data.}, author = {Fortuin, Vincent and Hüser, Matthias and Locatello, Francesco and Strathmann, Heiko and Rätsch, Gunnar}, booktitle = {International Conference on Learning Representations}, location = {New Orleans, LA, United States}, title = {{SOM-VAE: Interpretable discrete representation learning on time series}}, year = {2018}, } @inproceedings{142, abstract = {We address the problem of analyzing the reachable set of a polynomial nonlinear continuous system by over-approximating the flowpipe of its dynamics. The common approach to tackle this problem is to perform a numerical integration over a given time horizon based on Taylor expansion and interval arithmetic. However, this method results to be very conservative when there is a large difference in speed between trajectories as time progresses. In this paper, we propose to use combinations of barrier functions, which we call piecewise barrier tube (PBT), to over-approximate flowpipe. The basic idea of PBT is that for each segment of a flowpipe, a coarse box which is big enough to contain the segment is constructed using sampled simulation and then in the box we compute by linear programming a set of barrier functions (called barrier tube or BT for short) which work together to form a tube surrounding the flowpipe. The benefit of using PBT is that (1) BT is independent of time and hence can avoid being stretched and deformed by time; and (2) a small number of BTs can form a tight over-approximation for the flowpipe, which means that the computation required to decide whether the BTs intersect the unsafe set can be reduced significantly. We implemented a prototype called PBTS in C++. Experiments on some benchmark systems show that our approach is effective.}, author = {Kong, Hui and Bartocci, Ezio and Henzinger, Thomas A}, location = {Oxford, United Kingdom}, pages = {449 -- 467}, publisher = {Springer}, title = {{Reachable set over-approximation for nonlinear systems using piecewise barrier tubes}}, doi = {10.1007/978-3-319-96145-3_24}, volume = {10981}, year = {2018}, } @inproceedings{14201, abstract = {Variational inference is a popular technique to approximate a possibly intractable Bayesian posterior with a more tractable one. Recently, boosting variational inference has been proposed as a new paradigm to approximate the posterior by a mixture of densities by greedily adding components to the mixture. However, as is the case with many other variational inference algorithms, its theoretical properties have not been studied. In the present work, we study the convergence properties of this approach from a modern optimization viewpoint by establishing connections to the classic Frank-Wolfe algorithm. Our analyses yields novel theoretical insights regarding the sufficient conditions for convergence, explicit rates, and algorithmic simplifications. Since a lot of focus in previous works for variational inference has been on tractability, our work is especially important as a much needed attempt to bridge the gap between probabilistic models and their corresponding theoretical properties.}, author = {Locatello, Francesco and Khanna, Rajiv and Ghosh, Joydeep and Rätsch, Gunnar}, booktitle = {Proceedings of the 21st International Conference on Artificial Intelligence and Statistics}, location = {Playa Blanca, Lanzarote}, pages = {464--472}, publisher = {ML Research Press}, title = {{Boosting variational inference: An optimization perspective}}, volume = {84}, year = {2018}, } @inproceedings{14202, abstract = {Approximating a probability density in a tractable manner is a central task in Bayesian statistics. Variational Inference (VI) is a popular technique that achieves tractability by choosing a relatively simple variational family. Borrowing ideas from the classic boosting framework, recent approaches attempt to \emph{boost} VI by replacing the selection of a single density with a greedily constructed mixture of densities. In order to guarantee convergence, previous works impose stringent assumptions that require significant effort for practitioners. Specifically, they require a custom implementation of the greedy step (called the LMO) for every probabilistic model with respect to an unnatural variational family of truncated distributions. Our work fixes these issues with novel theoretical and algorithmic insights. On the theoretical side, we show that boosting VI satisfies a relaxed smoothness assumption which is sufficient for the convergence of the functional Frank-Wolfe (FW) algorithm. Furthermore, we rephrase the LMO problem and propose to maximize the Residual ELBO (RELBO) which replaces the standard ELBO optimization in VI. These theoretical enhancements allow for black box implementation of the boosting subroutine. Finally, we present a stopping criterion drawn from the duality gap in the classic FW analyses and exhaustive experiments to illustrate the usefulness of our theoretical and algorithmic contributions.}, author = {Locatello, Francesco and Dresdner, Gideon and Khanna, Rajiv and Valera, Isabel and Rätsch, Gunnar}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781510884472}, issn = {1049-5258}, location = {Montreal, Canada}, publisher = {Neural Information Processing Systems Foundation}, title = {{Boosting black box variational inference}}, volume = {31}, year = {2018}, } @inproceedings{14203, abstract = {We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines smoothing and homotopy techniques under the CGM framework, and provably achieves the optimal O(1/k−−√) convergence rate. We demonstrate that the same rate holds if the linear subproblems are solved approximately with additive or multiplicative error. In contrast with the relevant work, we are able to characterize the convergence when the non-smooth term is an indicator function. Specific applications of our framework include the non-smooth minimization, semidefinite programming, and minimization with linear inclusion constraints over a compact domain. Numerical evidence demonstrates the benefits of our framework.}, author = {Yurtsever, Alp and Fercoq, Olivier and Locatello, Francesco and Cevher, Volkan}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, location = {Stockholm, Sweden}, pages = {5727--5736}, publisher = {ML Research Press}, title = {{A conditional gradient framework for composite convex minimization with applications to semidefinite programming}}, volume = {80}, year = {2018}, } @inproceedings{14204, abstract = {Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection between the two algorithms, we present a unified analysis of both, providing affine invariant sublinear O(1/t) rates on smooth objectives and linear convergence on strongly convex objectives. As a byproduct of our affine invariant analysis of matching pursuit, our rates for steepest coordinate descent are the tightest known. Furthermore, we show the first accelerated convergence rate O(1/t2) for matching pursuit and steepest coordinate descent on convex objectives.}, author = {Locatello, Francesco and Raj, Anant and Karimireddy, Sai Praneeth and Rätsch, Gunnar and Schölkopf, Bernhard and Stich, Sebastian U. and Jaggi, Martin}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3198--3207}, publisher = {ML Research Press}, title = {{On matching pursuit and coordinate descent}}, volume = {80}, year = {2018}, } @inproceedings{14224, abstract = {Clustering is a cornerstone of unsupervised learning which can be thought as disentangling multiple generative mechanisms underlying the data. In this paper we introduce an algorithmic framework to train mixtures of implicit generative models which we particularize for variational autoencoders. Relying on an additional set of discriminators, we propose a competitive procedure in which the models only need to approximate the portion of the data distribution from which they can produce realistic samples. As a byproduct, each model is simpler to train, and a clustering interpretation arises naturally from the partitioning of the training points among the models. We empirically show that our approach splits the training distribution in a reasonable way and increases the quality of the generated samples.}, author = {Locatello, Francesco and Vincent, Damien and Tolstikhin, Ilya and Ratsch, Gunnar and Gelly, Sylvain and Scholkopf, Bernhard}, booktitle = {6th International Conference on Learning Representations}, location = {Vancouver, Canada}, title = {{Clustering meets implicit generative models}}, year = {2018}, } @inproceedings{143, abstract = {Vector Addition Systems with States (VASS) provide a well-known and fundamental model for the analysis of concurrent processes, parameterized systems, and are also used as abstract models of programs in resource bound analysis. In this paper we study the problem of obtaining asymptotic bounds on the termination time of a given VASS. In particular, we focus on the practically important case of obtaining polynomial bounds on termination time. Our main contributions are as follows: First, we present a polynomial-time algorithm for deciding whether a given VASS has a linear asymptotic complexity. We also show that if the complexity of a VASS is not linear, it is at least quadratic. Second, we classify VASS according to quantitative properties of their cycles. We show that certain singularities in these properties are the key reason for non-polynomial asymptotic complexity of VASS. In absence of singularities, we show that the asymptotic complexity is always polynomial and of the form Θ(nk), for some integer k d, where d is the dimension of the VASS. We present a polynomial-time algorithm computing the optimal k. For general VASS, the same algorithm, which is based on a complete technique for the construction of ranking functions in VASS, produces a valid lower bound, i.e., a k such that the termination complexity is (nk). Our results are based on new insights into the geometry of VASS dynamics, which hold the potential for further applicability to VASS analysis.}, author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Kučera, Antonín and Novotny, Petr and Velan, Dominik and Zuleger, Florian}, isbn = {978-1-4503-5583-4}, location = {Oxford, United Kingdom}, pages = {185 -- 194}, publisher = {IEEE}, title = {{Efficient algorithms for asymptotic bounds on termination time in VASS}}, doi = {10.1145/3209108.3209191}, volume = {F138033}, year = {2018}, } @unpublished{14327, abstract = {A common assumption in causal modeling posits that the data is generated by a set of independent mechanisms, and algorithms should aim to recover this structure. Standard unsupervised learning, however, is often concerned with training a single model to capture the overall distribution or aspects thereof. Inspired by clustering approaches, we consider mixtures of implicit generative models that ``disentangle'' the independent generative mechanisms underlying the data. Relying on an additional set of discriminators, we propose a competitive training procedure in which the models only need to capture the portion of the data distribution from which they can produce realistic samples. As a by-product, each model is simpler and faster to train. We empirically show that our approach splits the training distribution in a sensible way and increases the quality of the generated samples.}, author = {Locatello, Francesco and Vincent, Damien and Tolstikhin, Ilya and Rätsch, Gunnar and Gelly, Sylvain and Schölkopf, Bernhard}, booktitle = {arXiv}, title = {{Competitive training of mixtures of independent deep generative models}}, doi = {10.48550/arXiv.1804.11130}, year = {2018}, } @inproceedings{144, abstract = {The task of a monitor is to watch, at run-time, the execution of a reactive system, and signal the occurrence of a safety violation in the observed sequence of events. While finite-state monitors have been studied extensively, in practice, monitoring software also makes use of unbounded memory. We define a model of automata equipped with integer-valued registers which can execute only a bounded number of instructions between consecutive events, and thus can form the theoretical basis for the study of infinite-state monitors. We classify these register monitors according to the number k of available registers, and the type of register instructions. In stark contrast to the theory of computability for register machines, we prove that for every k 1, monitors with k + 1 counters (with instruction set 〈+1, =〉) are strictly more expressive than monitors with k counters. We also show that adder monitors (with instruction set 〈1, +, =〉) are strictly more expressive than counter monitors, but are complete for monitoring all computable safety -languages for k = 6. Real-time monitors are further required to signal the occurrence of a safety violation as soon as it occurs. The expressiveness hierarchy for counter monitors carries over to real-time monitors. We then show that 2 adders cannot simulate 3 counters in real-time. Finally, we show that real-time adder monitors with inequalities are as expressive as real-time Turing machines.}, author = {Ferrere, Thomas and Henzinger, Thomas A and Saraç, Ege}, location = {Oxford, UK}, pages = {394 -- 403}, publisher = {IEEE}, title = {{A theory of register monitors}}, doi = {10.1145/3209108.3209194}, volume = {Part F138033}, year = {2018}, } @article{145, abstract = {Aged proteins can become hazardous to cellular function, by accumulating molecular damage. This implies that cells should preferentially rely on newly produced ones. We tested this hypothesis in cultured hippocampal neurons, focusing on synaptic transmission. We found that newly synthesized vesicle proteins were incorporated in the actively recycling pool of vesicles responsible for all neurotransmitter release during physiological activity. We observed this for the calcium sensor Synaptotagmin 1, for the neurotransmitter transporter VGAT, and for the fusion protein VAMP2 (Synaptobrevin 2). Metabolic labeling of proteins and visualization by secondary ion mass spectrometry enabled us to query the entire protein makeup of the actively recycling vesicles, which we found to be younger than that of non-recycling vesicles. The young vesicle proteins remained in use for up to ~ 24 h, during which they participated in recycling a few hundred times. They were afterward reluctant to release and were degraded after an additional ~ 24–48 h. We suggest that the recycling pool of synaptic vesicles relies on newly synthesized proteins, while the inactive reserve pool contains older proteins.}, author = {Truckenbrodt, Sven M and Viplav, Abhiyan and Jähne, Sebsatian and Vogts, Angela and Denker, Annette and Wildhagen, Hanna and Fornasiero, Eugenio and Rizzoli, Silvio}, issn = {0261-4189}, journal = {The EMBO Journal}, number = {15}, publisher = {Wiley}, title = {{Newly produced synaptic vesicle proteins are preferentially used in synaptic transmission}}, doi = {10.15252/embj.201798044}, volume = {37}, year = {2018}, } @article{146, abstract = {The root cap protects the stem cell niche of angiosperm roots from damage. In Arabidopsis, lateral root cap (LRC) cells covering the meristematic zone are regularly lost through programmed cell death, while the outermost layer of the root cap covering the tip is repeatedly sloughed. Efficient coordination with stem cells producing new layers is needed to maintain a constant size of the cap. We present a signalling pair, the peptide IDA-LIKE1 (IDL1) and its receptor HAESA-LIKE2 (HSL2), mediating such communication. Live imaging over several days characterized this process from initial fractures in LRC cell files to full separation of a layer. Enhanced expression of IDL1 in the separating root cap layers resulted in increased frequency of sloughing, balanced with generation of new layers in a HSL2-dependent manner. Transcriptome analyses linked IDL1-HSL2 signalling to the transcription factors BEARSKIN1/2 and genes associated with programmed cell death. Mutations in either IDL1 or HSL2 slowed down cell division, maturation and separation. Thus, IDL1-HSL2 signalling potentiates dynamic regulation of the homeostatic balance between stem cell division and sloughing activity.}, author = {Shi, Chun Lin and Von Wangenheim, Daniel and Herrmann, Ullrich and Wildhagen, Mari and Kulik, Ivan and Kopf, Andreas and Ishida, Takashi and Olsson, Vilde and Anker, Mari Kristine and Albert, Markus and Butenko, Melinka A and Felix, Georg and Sawa, Shinichiro and Claassen, Manfred and Friml, Jirí and Aalen, Reidunn B}, journal = {Nature Plants}, number = {8}, pages = {596 -- 604}, publisher = {Nature Publishing Group}, title = {{The dynamics of root cap sloughing in Arabidopsis is regulated by peptide signalling}}, doi = {10.1038/s41477-018-0212-z}, volume = {4}, year = {2018}, } @article{147, abstract = {The trafficking of subcellular cargos in eukaryotic cells crucially depends on vesicle budding, a process mediated by ARF-GEFs (ADP-ribosylation factor guanine nucleotide exchange factors). In plants, ARF-GEFs play essential roles in endocytosis, vacuolar trafficking, recycling, secretion, and polar trafficking. Moreover, they are important for plant development, mainly through controlling the polar subcellular localization of PIN-FORMED (PIN) transporters of the plant hormone auxin. Here, using a chemical genetics screen in Arabidopsis thaliana, we identified Endosidin 4 (ES4), an inhibitor of eukaryotic ARF-GEFs. ES4 acts similarly to and synergistically with the established ARF-GEF inhibitor Brefeldin A and has broad effects on intracellular trafficking, including endocytosis, exocytosis, and vacuolar targeting. Additionally, Arabidopsis and yeast (Sacharomyces cerevisiae) mutants defective in ARF-GEF show altered sensitivity to ES4. ES4 interferes with the activation-based membrane association of the ARF1 GTPases, but not of their mutant variants that are activated independently of ARF-GEF activity. Biochemical approaches and docking simulations confirmed that ES4 specifically targets the SEC7 domain-containing ARF-GEFs. These observations collectively identify ES4 as a chemical tool enabling the study of ARF-GEF-mediated processes, including ARF-GEF-mediated plant development.}, author = {Kania, Urszula and Nodzyński, Tomasz and Lu, Qing and Hicks, Glenn R and Nerinckx, Wim and Mishev, Kiril and Peurois, Francois and Cherfils, Jacqueline and De, Rycke Riet Maria and Grones, Peter and Robert, Stéphanie and Russinova, Eugenia and Friml, Jirí}, issn = {1040-4651}, journal = {The Plant Cell}, number = {10}, pages = {2553 -- 2572}, publisher = {Oxford University Press}, title = {{The inhibitor Endosidin 4 targets SEC7 domain-type ARF GTPase exchange factors and interferes with sub cellular trafficking in eukaryotes}}, doi = {10.1105/tpc.18.00127}, volume = {30}, year = {2018}, } @article{18, abstract = {An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. We prove the existence of such superconcentrators with asymptotic density 25.3 (where the density is the number of edges divided by N). The previously best known densities were 28 [12] and 27.4136 [17].}, author = {Kolmogorov, Vladimir and Rolinek, Michal}, issn = {0381-7032}, journal = {Ars Combinatoria}, number = {10}, pages = {269 -- 304}, publisher = {Charles Babbage Research Centre}, title = {{Superconcentrators of density 25.3}}, volume = {141}, year = {2018}, } @article{180, abstract = {In this paper we define and study the classical Uniform Electron Gas (UEG), a system of infinitely many electrons whose density is constant everywhere in space. The UEG is defined differently from Jellium, which has a positive constant background but no constraint on the density. We prove that the UEG arises in Density Functional Theory in the limit of a slowly varying density, minimizing the indirect Coulomb energy. We also construct the quantum UEG and compare it to the classical UEG at low density.}, author = {Lewi, Mathieu and Lieb, Élliott and Seiringer, Robert}, issn = {2270-518X}, journal = {Journal de l'Ecole Polytechnique - Mathematiques}, pages = {79 -- 116}, publisher = {Ecole Polytechnique}, title = {{Statistical mechanics of the uniform electron gas}}, doi = {10.5802/jep.64}, volume = {5}, year = {2018}, } @article{181, abstract = {We consider large random matrices X with centered, independent entries but possibly di erent variances. We compute the normalized trace of f(X)g(X∗) for f, g functions analytic on the spectrum of X. We use these results to compute the long time asymptotics for systems of coupled di erential equations with random coe cients. We show that when the coupling is critical, the norm squared of the solution decays like t−1/2.}, author = {Erdös, László and Krüger, Torben H and Renfrew, David T}, journal = {SIAM Journal on Mathematical Analysis}, number = {3}, pages = {3271 -- 3290}, publisher = {Society for Industrial and Applied Mathematics }, title = {{Power law decay for systems of randomly coupled differential equations}}, doi = {10.1137/17M1143125}, volume = {50}, year = {2018}, } @inproceedings{182, abstract = {We describe a new algorithm for the parametric identification problem for signal temporal logic (STL), stated as follows. Given a densetime real-valued signal w and a parameterized temporal logic formula φ, compute the subset of the parameter space that renders the formula satisfied by the signal. Unlike previous solutions, which were based on search in the parameter space or quantifier elimination, our procedure works recursively on φ and computes the evolution over time of the set of valid parameter assignments. This procedure is similar to that of monitoring or computing the robustness of φ relative to w. Our implementation and experiments demonstrate that this approach can work well in practice.}, author = {Bakhirkin, Alexey and Ferrere, Thomas and Maler, Oded}, booktitle = {Proceedings of the 21st International Conference on Hybrid Systems}, isbn = {978-1-4503-5642-8 }, location = {Porto, Portugal}, pages = {177 -- 186}, publisher = {ACM}, title = {{Efficient parametric identification for STL}}, doi = {10.1145/3178126.3178132}, year = {2018}, } @inproceedings{183, abstract = {Fault-localization is considered to be a very tedious and time-consuming activity in the design of complex Cyber-Physical Systems (CPS). This laborious task essentially requires expert knowledge of the system in order to discover the cause of the fault. In this context, we propose a new procedure that AIDS designers in debugging Simulink/Stateflow hybrid system models, guided by Signal Temporal Logic (STL) specifications. The proposed method relies on three main ingredients: (1) a monitoring and a trace diagnostics procedure that checks whether a tested behavior satisfies or violates an STL specification, localizes time segments and interfaces variables contributing to the property violations; (2) a slicing procedure that maps these observable behavior segments to the internal states and transitions of the Simulink model; and (3) a spectrum-based fault-localization method that combines the previous analysis from multiple tests to identify the internal states and/or transitions that are the most likely to explain the fault. We demonstrate the applicability of our approach on two Simulink models from the automotive and the avionics domain.}, author = {Bartocci, Ezio and Ferrere, Thomas and Manjunath, Niveditha and Nickovic, Dejan}, location = {Porto, Portugal}, pages = {197 -- 206}, publisher = {Association for Computing Machinery}, title = {{Localizing faults in simulink/stateflow models with STL}}, doi = {10.1145/3178126.3178131}, year = {2018}, } @inproceedings{184, abstract = {We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.}, author = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli}, location = {Budapest, Hungary}, pages = {41:1 -- 41:16}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Shellability is NP-complete}}, doi = {10.4230/LIPIcs.SoCG.2018.41}, volume = {99}, year = {2018}, } @inproceedings{185, abstract = {We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.}, author = {Fulek, Radoslav and Kynčl, Jan}, isbn = {978-3-95977-066-8}, location = {Budapest, Hungary}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Hanani-Tutte for approximating maps of graphs}}, doi = {10.4230/LIPIcs.SoCG.2018.39}, volume = {99}, year = {2018}, }