@inproceedings{10325, abstract = {Since the inception of Bitcoin, a plethora of distributed ledgers differing in design and purpose has been created. While by design, blockchains provide no means to securely communicate with external systems, numerous attempts towards trustless cross-chain communication have been proposed over the years. Today, cross-chain communication (CCC) plays a fundamental role in cryptocurrency exchanges, scalability efforts via sharding, extension of existing systems through sidechains, and bootstrapping of new blockchains. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence in their correctness and composability. We provide the first systematic exposition of cross-chain communication protocols. We formalize the underlying research problem and show that CCC is impossible without a trusted third party, contrary to common beliefs in the blockchain community. With this result in mind, we develop a framework to design new and evaluate existing CCC protocols, focusing on the inherent trust assumptions thereof, and derive a classification covering the field of cross-chain communication to date. We conclude by discussing open challenges for CCC research and the implications of interoperability on the security and privacy of blockchains.}, author = {Zamyatin, Alexei and Al-Bassam, Mustafa and Zindros, Dionysis and Kokoris Kogias, Eleftherios and Moreno-Sanchez, Pedro and Kiayias, Aggelos and Knottenbelt, William J.}, booktitle = {25th International Conference on Financial Cryptography and Data Security}, isbn = {9-783-6626-4330-3}, issn = {1611-3349}, location = {Virtual}, pages = {3--36}, publisher = {Springer Nature}, title = {{SoK: Communication across distributed ledgers}}, doi = {10.1007/978-3-662-64331-0_1}, volume = {12675 }, year = {2021}, } @inproceedings{10599, abstract = {A two-part successive syndrome-check decoding of polar codes is proposed with the first part successively refining the received codeword and the second part checking its syndrome. A new formulation of the successive-cancellation (SC) decoding algorithm is presented that allows for successively refining the received codeword by comparing the log-likelihood ratio value of a frozen bit with its predefined value. The syndrome of the refined received codeword is then checked for possible errors. In case there are no errors, the decoding process is terminated. Otherwise, the decoder continues to refine the received codeword. The proposed method is extended to the case of SC list (SCL) decoding by terminating the decoding process when the syndrome of the best candidate in the list indicates no errors. Simulation results show that the proposed method reduces the time-complexity of SC and SCL decoders and their fast variants, especially at high signal-to-noise ratios.}, author = {Hashemi, Seyyed Ali and Mondelli, Marco and Cioffi, John and Goldsmith, Andrea}, booktitle = {Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers}, isbn = {9781665458283}, issn = {1058-6393}, location = {Virtual, Pacific Grove, CA, United States}, pages = {943--947}, publisher = {IEEE}, title = {{Successive syndrome-check decoding of polar codes}}, doi = {10.1109/IEEECONF53345.2021.9723394}, volume = {2021-October}, year = {2021}, } @inproceedings{10597, abstract = {We thank Emmanuel Abbe and Min Ye for providing us the implementation of RPA decoding. D. Fathollahi and M. Mondelli are partially supported by the 2019 Lopez-Loreta Prize. N. Farsad is supported by Discovery Grant from the Natural Sciences and Engineering Research Council of Canada (NSERC) and Canada Foundation for Innovation (CFI), John R. Evans Leader Fund. S. A. Hashemi is supported by a Postdoctoral Fellowship from NSERC.}, author = {Fathollahi, Dorsa and Farsad, Nariman and Hashemi, Seyyed Ali and Mondelli, Marco}, booktitle = {2021 IEEE International Symposium on Information Theory}, isbn = {978-1-5386-8210-4}, location = {Virtual, Melbourne, Australia}, pages = {1082--1087}, publisher = {IEEE}, title = {{Sparse multi-decoder recursive projection aggregation for Reed-Muller codes}}, doi = {10.1109/isit45174.2021.9517887}, year = {2021}, } @inproceedings{10002, abstract = {We present a faster symbolic algorithm for the following central problem in probabilistic verification: Compute the maximal end-component (MEC) decomposition of Markov decision processes (MDPs). This problem generalizes the SCC decomposition problem of graphs and closed recurrent sets of Markov chains. The model of symbolic algorithms is widely used in formal verification and model-checking, where access to the input model is restricted to only symbolic operations (e.g., basic set operations and computation of one-step neighborhood). For an input MDP with n vertices and m edges, the classical symbolic algorithm from the 1990s for the MEC decomposition requires O(n2) symbolic operations and O(1) symbolic space. The only other symbolic algorithm for the MEC decomposition requires O(nm−−√) symbolic operations and O(m−−√) symbolic space. A main open question is whether the worst-case O(n2) bound for symbolic operations can be beaten. We present a symbolic algorithm that requires O˜(n1.5) symbolic operations and O˜(n−−√) symbolic space. Moreover, the parametrization of our algorithm provides a trade-off between symbolic operations and symbolic space: for all 0<ϵ≤1/2 the symbolic algorithm requires O˜(n2−ϵ) symbolic operations and O˜(nϵ) symbolic space ( O˜ hides poly-logarithmic factors). Using our techniques we present faster algorithms for computing the almost-sure winning regions of ω -regular objectives for MDPs. We consider the canonical parity objectives for ω -regular objectives, and for parity objectives with d -priorities we present an algorithm that computes the almost-sure winning region with O˜(n2−ϵ) symbolic operations and O˜(nϵ) symbolic space, for all 0<ϵ≤1/2 .}, author = {Chatterjee, Krishnendu and Dvorak, Wolfgang and Henzinger, Monika H and Svozil, Alexander}, booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science}, isbn = {978-1-6654-4896-3}, issn = {1043-6871}, keywords = {Computer science, Computational modeling, Markov processes, Probabilistic logic, Formal verification, Game Theory}, location = {Rome, Italy}, pages = {1--13}, publisher = {IEEE}, title = {{Symbolic time and space tradeoffs for probabilistic verification}}, doi = {10.1109/LICS52264.2021.9470739}, year = {2021}, } @inproceedings{9356, abstract = {In runtime verification, a monitor watches a trace of a system and, if possible, decides after observing each finite prefix whether or not the unknown infinite trace satisfies a given specification. We generalize the theory of runtime verification to monitors that attempt to estimate numerical values of quantitative trace properties (instead of attempting to conclude boolean values of trace specifications), such as maximal or average response time along a trace. Quantitative monitors are approximate: with every finite prefix, they can improve their estimate of the infinite trace's unknown property value. Consequently, quantitative monitors can be compared with regard to a precision-cost trade-off: better approximations of the property value require more monitor resources, such as states (in the case of finite-state monitors) or registers, and additional resources yield better approximations. We introduce a formal framework for quantitative and approximate monitoring, show how it conservatively generalizes the classical boolean setting for monitoring, and give several precision-cost trade-offs for monitors. For example, we prove that there are quantitative properties for which every additional register improves monitoring precision.}, author = {Henzinger, Thomas A and Sarac, Naci E}, booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science}, location = {Online}, publisher = {IEEE}, title = {{Quantitative and approximate monitoring}}, doi = {10.1109/LICS52264.2021.9470547}, year = {2021}, } @inproceedings{10004, abstract = {Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science}, isbn = {978-1-6654-4896-3}, issn = {1043-6871}, keywords = {Computer science, Heuristic algorithms, Memory management, Automata, Markov processes, Probability distribution, Complexity theory}, location = {Rome, Italy}, pages = {1--13}, publisher = {IEEE}, title = {{Stochastic processes with expected stopping time}}, doi = {10.1109/LICS52264.2021.9470595}, year = {2021}, } @article{9828, abstract = {Amplitude demodulation is a classical operation used in signal processing. For a long time, its effective applications in practice have been limited to narrowband signals. In this work, we generalize amplitude demodulation to wideband signals. We pose demodulation as a recovery problem of an oversampled corrupted signal and introduce special iterative schemes belonging to the family of alternating projection algorithms to solve it. Sensibly chosen structural assumptions on the demodulation outputs allow us to reveal the high inferential accuracy of the method over a rich set of relevant signals. This new approach surpasses current state-of-the-art demodulation techniques apt to wideband signals in computational efficiency by up to many orders of magnitude with no sacrifice in quality. Such performance opens the door for applications of the amplitude demodulation procedure in new contexts. In particular, the new method makes online and large-scale offline data processing feasible, including the calculation of modulator-carrier pairs in higher dimensions and poor sampling conditions, independent of the signal bandwidth. We illustrate the utility and specifics of applications of the new method in practice by using natural speech and synthetic signals.}, author = {Gabrielaitis, Mantas}, issn = {1941-0476}, journal = {IEEE Transactions on Signal Processing}, pages = {4039 -- 4054}, publisher = {IEEE}, title = {{Fast and accurate amplitude demodulation of wideband signals}}, doi = {10.1109/TSP.2021.3087899}, volume = {69}, year = {2021}, } @inproceedings{10053, abstract = {This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements P that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is O(N1−1 μ+NPlog2log2NP), where N is the block length of the code and μ is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where P=N2 , the latency of SSC decoding is O(N1−1/μ) , which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where P=1 , the latency of SSC decoding scales as O(Nlog2log2N) . The multiplicative constant is also calculated: we show that the latency of SSC decoding when P=1 is given by (2+o(1))Nlog2log2N . Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P=N1/μ . The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.}, author = {Hashemi, Seyyed Ali and Mondelli, Marco and Fazeli, Arman and Vardy, Alexander and Cioffi, John and Goldsmith, Andrea}, booktitle = {2021 IEEE International Symposium on Information Theory}, isbn = {978-1-5386-8210-4}, issn = {2157-8095}, location = {Melbourne, Australia}, pages = {2369--2374}, publisher = {IEEE}, title = {{Parallelism versus latency in simplified successive-cancellation decoding of polar codes}}, doi = {10.1109/ISIT45174.2021.9518153}, year = {2021}, } @article{22584, abstract = {Higher temperatures in urban areas expose a large fraction of the human population to potentially dangerous heat stress. Green spaces are promoted worldwide as local and city-scale cooling strategies but the amount, type, and functioning of vegetation in cities lack quantification and their interaction with urban climate in different settings remains a matter of debate. Here we use state-of-the-art remote sensing data from 145 city clusters to disentangle the drivers of surface urban heat islands (SUHI) intensity and quantify urban-rural differences in vegetation cover, species composition, and evaporative cooling. We show that nighttime SUHIs are affected mostly by abiotic factors, while daytime SUHIs are highly correlated with vegetation characteristics and the wetness of the background climate. Magnitude and seasonality of daytime SUHIs are controlled by urban-rural differences in plant transpiration and leaf area, which explain the dependence of SUHIs on wetness conditions. Leaf area differences are caused primarily by changes in vegetation type and a loss of in-city forested areas, highlighting the importance of maintaining “natural reserves” as a sustainable heat mitigation policy.}, author = {Paschalis, Athanasios and Chakraborty, TC and Fatichi, Simone and Meili, Naika and Manoli, Gabriele}, issn = {2576-604X}, journal = {AGU Advances}, number = {2}, publisher = {American Geophysical Union}, title = {{Urban forests as main regulator of the evaporative cooling effect in cities}}, doi = {10.1029/2020av000303}, volume = {2}, year = {2021}, } @article{10738, abstract = {We prove an adiabatic theorem for the Landau–Pekar equations. This allows us to derive new results on the accuracy of their use as effective equations for the time evolution generated by the Fröhlich Hamiltonian with large coupling constant α. In particular, we show that the time evolution of Pekar product states with coherent phonon field and the electron being trapped by the phonons is well approximated by the Landau–Pekar equations until times short compared to α2.}, author = {Leopold, Nikolai K and Rademacher, Simone Anna Elvira and Schlein, Benjamin and Seiringer, Robert}, issn = {1948-206X}, journal = {Analysis and PDE}, number = {7}, pages = {2079--2100}, publisher = {Mathematical Sciences Publishers}, title = {{The Landau–Pekar equations: Adiabatic theorem and accuracy}}, doi = {10.2140/APDE.2021.14.2079}, volume = {14}, year = {2021}, } @article{9226, abstract = {Half a century after Lewis Wolpert's seminal conceptual advance on how cellular fates distribute in space, we provide a brief historical perspective on how the concept of positional information emerged and influenced the field of developmental biology and beyond. We focus on a modern interpretation of this concept in terms of information theory, largely centered on its application to cell specification in the early Drosophila embryo. We argue that a true physical variable (position) is encoded in local concentrations of patterning molecules, that this mapping is stochastic, and that the processes by which positions and corresponding cell fates are determined based on these concentrations need to take such stochasticity into account. With this approach, we shift the focus from biological mechanisms, molecules, genes and pathways to quantitative systems-level questions: where does positional information reside, how it is transformed and accessed during development, and what fundamental limits it is subject to?}, author = {Tkačik, Gašper and Gregor, Thomas}, issn = {1477-9129}, journal = {Development}, number = {2}, publisher = {Company of Biologists}, title = {{The many bits of positional information}}, doi = {10.1242/dev.176065}, volume = {148}, year = {2021}, } @article{15262, abstract = {The Hunchback (Hb) transcription factor is crucial for anterior-posterior patterning of the Drosophila embryo. The maternal hb mRNA acts as a paradigm for translational regulation due to its repression in the posterior of the embryo. However, little is known about the translatability of zygotically transcribed hb mRNAs. Here, we adapt the SunTag system, developed for imaging translation at single-mRNA resolution in tissue culture cells, to the Drosophila embryo to study the translation dynamics of zygotic hb mRNAs. Using single-molecule imaging in fixed and live embryos, we provide evidence for translational repression of zygotic SunTag-hb mRNAs. Whereas the proportion of SunTag-hb mRNAs translated is initially uniform, translation declines from the anterior over time until it becomes restricted to a posterior band in the expression domain. We discuss how regulated hb mRNA translation may help establish the sharp Hb expression boundary, which is a model for precision and noise during developmental patterning. Overall, our data show how use of the SunTag method on fixed and live embryos is a powerful combination for elucidating spatiotemporal regulation of mRNA translation in Drosophila.}, author = {Vinter, Daisy J. and Hoppe, Caroline and Minchington, Thomas and Sutcliffe, Catherine and Ashe, Hilary L.}, issn = {1477-9129}, journal = {Development}, keywords = {Developmental Biology, Molecular Biology}, number = {18}, publisher = {Company of Biologists}, title = {{Dynamics of hunchback translation in real-time and at single-mRNA resolution in the Drosophila embryo}}, doi = {10.1242/dev.196121}, volume = {148}, year = {2021}, } @article{10000, abstract = {Inhibition or targeted deletion of histone deacetylase 3 (HDAC3) is neuroprotective in a variety neurodegenerative conditions, including retinal ganglion cells (RGCs) after acute optic nerve damage. Consistent with this, induced HDAC3 expression in cultured cells shows selective toxicity to neurons. Despite an established role for HDAC3 in neuronal pathology, little is known regarding the mechanism of this pathology.}, author = {Schmitt, Heather M. and Fehrman, Rachel L. and Maes, Margaret E and Yang, Huan and Guo, Lian Wang and Schlamp, Cassandra L. and Pelzel, Heather R. and Nickells, Robert W.}, issn = {1552-5783}, journal = {Investigative Ophthalmology & Visual Science}, number = {10}, publisher = {Association for Research in Vision and Ophthalmology}, title = {{Increased susceptibility and intrinsic apoptotic signaling in neurons by induced HDAC3 expression}}, doi = {10.1167/IOVS.62.10.14}, volume = {62}, year = {2021}, } @article{9047, abstract = {This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is O(N1−1/μ) , where N is the block length and μ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate 0 or 1.}, author = {Mondelli, Marco and Hashemi, Seyyed Ali and Cioffi, John M. and Goldsmith, Andrea}, issn = {1558-2248}, journal = {IEEE Transactions on Wireless Communications}, number = {1}, pages = {18--27}, publisher = {IEEE}, title = {{Sublinear latency for simplified successive cancellation decoding of polar codes}}, doi = {10.1109/TWC.2020.3022922}, volume = {20}, year = {2021}, } @article{15267, abstract = {We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in undirected networks with n nodes and diameter D, randomized broadcasting requires Ω(D log n/D + log2 n) rounds, assuming that uninformed nodes are not allowed to communicate (until they are informed). Only very recently, Haeupler and Wajc (PODC'2016) showed that this bound can be improved for the model with spontaneous transmissions, providing an O(D log n log log n/log D + logO(1) n)-time broadcasting algorithm. In this article, we give a new and faster algorithm that completes broadcasting in O(D log n/log D + logO(1) n) time, succeeding with high probability. This yields the first optimal O(D)-time broadcasting algorithm whenever n is polynomial in D. Furthermore, our approach can be applied to design a new leader election algorithm that matches the performance of our broadcasting algorithm. Previously, all fast randomized leader election algorithms have used broadcasting as a subroutine and their complexity has been asymptotically strictly larger than the complexity of broadcasting. In particular, the fastest previously known randomized leader election algorithm of Ghaffari and Haeupler (SODA'2013) requires O(D log n/D min {log log n, log n/D} + logO(1) n)-time, succeeding with high probability. Our new algorithm again requires O(D log n/log D + logO(1) n) time, also succeeding with high probability.}, author = {Czumaj, Artur and Davies, Peter}, issn = {1557-735X}, journal = {Journal of the ACM}, keywords = {Artificial Intelligence, Hardware and Architecture, Information Systems, Control and Systems Engineering, Software}, number = {2}, publisher = {ACM}, title = {{Exploiting spontaneous transmissions for broadcasting and leader election in radio networks}}, doi = {10.1145/3446383}, volume = {68}, year = {2021}, } @article{10575, abstract = {The choice of the boundary conditions in mechanical problems has to reflect the interaction of the considered material with the surface. Still the assumption of the no-slip condition is preferred in order to avoid boundary terms in the analysis and slipping effects are usually overlooked. Besides the “static slip models”, there are phenomena that are not accurately described by them, e.g. at the moment when the slip changes rapidly, the wall shear stress and the slip can exhibit a sudden overshoot and subsequent relaxation. When these effects become significant, the so-called dynamic slip phenomenon occurs. We develop a mathematical analysis of Navier–Stokes-like problems with a dynamic slip boundary condition, which requires a proper generalization of the Gelfand triplet and the corresponding function space setting.}, author = {Abbatiello, Anna and Bulíček, Miroslav and Maringová, Erika}, issn = {1793-6314}, journal = {Mathematical Models and Methods in Applied Sciences}, number = {11}, pages = {2165--2212}, publisher = {World Scientific Publishing}, title = {{On the dynamic slip boundary condition for Navier-Stokes-like problems}}, doi = {10.1142/S0218202521500470}, volume = {31}, year = {2021}, } @article{10005, abstract = {We study systems of nonlinear partial differential equations of parabolic type, in which the elliptic operator is replaced by the first-order divergence operator acting on a flux function, which is related to the spatial gradient of the unknown through an additional implicit equation. This setting, broad enough in terms of applications, significantly expands the paradigm of nonlinear parabolic problems. Formulating four conditions concerning the form of the implicit equation, we first show that these conditions describe a maximal monotone p-coercive graph. We then establish the global-in-time and large-data existence of a (weak) solution and its uniqueness. To this end, we adopt and significantly generalize Minty’s method of monotone mappings. A unified theory, containing several novel tools, is developed in a way to be tractable from the point of view of numerical approximations.}, author = {Bulíček, Miroslav and Maringová, Erika and Málek, Josef}, issn = {1793-6314}, journal = {Mathematical Models and Methods in Applied Sciences}, keywords = {Nonlinear parabolic systems, implicit constitutive theory, weak solutions, existence, uniqueness}, number = {09}, publisher = {World Scientific Publishing}, title = {{On nonlinear problems of parabolic type with implicit constitutive equations involving flux}}, doi = {10.1142/S0218202521500457}, volume = {31}, year = {2021}, } @inproceedings{10665, abstract = {Formal verification of neural networks is an active topic of research, and recent advances have significantly increased the size of the networks that verification tools can handle. However, most methods are designed for verification of an idealized model of the actual network which works over real arithmetic and ignores rounding imprecisions. This idealization is in stark contrast to network quantization, which is a technique that trades numerical precision for computational efficiency and is, therefore, often applied in practice. Neglecting rounding errors of such low-bit quantized neural networks has been shown to lead to wrong conclusions about the network’s correctness. Thus, the desired approach for verifying quantized neural networks would be one that takes these rounding errors into account. In this paper, we show that verifying the bitexact implementation of quantized neural networks with bitvector specifications is PSPACE-hard, even though verifying idealized real-valued networks and satisfiability of bit-vector specifications alone are each in NP. Furthermore, we explore several practical heuristics toward closing the complexity gap between idealized and bit-exact verification. In particular, we propose three techniques for making SMT-based verification of quantized neural networks more scalable. Our experiments demonstrate that our proposed methods allow a speedup of up to three orders of magnitude over existing approaches.}, author = {Henzinger, Thomas A and Lechner, Mathias and Zikelic, Dorde}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, isbn = {978-1-57735-866-4}, issn = {2374-3468}, location = {Virtual}, number = {5A}, pages = {3787--3795}, publisher = {AAAI Press}, title = {{Scalable verification of quantized neural networks}}, doi = {10.1609/aaai.v35i5.16496}, volume = {35}, year = {2021}, } @inproceedings{10671, abstract = {We introduce a new class of time-continuous recurrent neural network models. Instead of declaring a learning system’s dynamics by implicit nonlinearities, we construct networks of linear first-order dynamical systems modulated via nonlinear interlinked gates. The resulting models represent dynamical systems with varying (i.e., liquid) time-constants coupled to their hidden state, with outputs being computed by numerical differential equation solvers. These neural networks exhibit stable and bounded behavior, yield superior expressivity within the family of neural ordinary differential equations, and give rise to improved performance on time-series prediction tasks. To demonstrate these properties, we first take a theoretical approach to find bounds over their dynamics, and compute their expressive power by the trajectory length measure in a latent trajectory space. We then conduct a series of time-series prediction experiments to manifest the approximation capability of Liquid Time-Constant Networks (LTCs) compared to classical and modern RNNs.}, author = {Hasani, Ramin and Lechner, Mathias and Amini, Alexander and Rus, Daniela and Grosu, Radu}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, isbn = {978-1-57735-866-4}, issn = {2374-3468}, location = {Virtual}, number = {9}, pages = {7657--7666}, publisher = {AAAI Press}, title = {{Liquid time-constant networks}}, doi = {10.1609/aaai.v35i9.16936}, volume = {35}, year = {2021}, } @inproceedings{11436, abstract = {Asynchronous distributed algorithms are a popular way to reduce synchronization costs in large-scale optimization, and in particular for neural network training. However, for nonsmooth and nonconvex objectives, few convergence guarantees exist beyond cases where closed-form proximal operator solutions are available. As training most popular deep neural networks corresponds to optimizing nonsmooth and nonconvex objectives, there is a pressing need for such convergence guarantees. In this paper, we analyze for the first time the convergence of stochastic asynchronous optimization for this general class of objectives. In particular, we focus on stochastic subgradient methods allowing for block variable partitioning, where the shared model is asynchronously updated by concurrent processes. To this end, we use a probabilistic model which captures key features of real asynchronous scheduling between concurrent processes. Under this model, we establish convergence with probability one to an invariant set for stochastic subgradient methods with momentum. From a practical perspective, one issue with the family of algorithms that we consider is that they are not efficiently supported by machine learning frameworks, which mostly focus on distributed data-parallel strategies. To address this, we propose a new implementation strategy for shared-memory based training of deep neural networks for a partitioned but shared model in single- and multi-GPU settings. Based on this implementation, we achieve on average1.2x speed-up in comparison to state-of-the-art training methods for popular image classification tasks, without compromising accuracy.}, author = {Kungurtsev, Vyacheslav and Egan, Malcolm and Chatterjee, Bapi and Alistarh, Dan-Adrian}, booktitle = {35th AAAI Conference on Artificial Intelligence, AAAI 2021}, isbn = {9781713835974}, issn = {2374-3468}, location = {Virtual, Online}, number = {9B}, pages = {8209--8216}, publisher = {AAAI Press}, title = {{Asynchronous optimization methods for efficient training of deep neural networks with guarantees}}, doi = {10.1609/aaai.v35i9.16999}, volume = {35}, year = {2021}, }