OpenRaiser/Intern-Atlas huggingface dataset:
Training Recommender Systems at Scale: Communication-Efficient Model and Data Parallelism
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we consider hybrid parallelism -- a paradigm that employs both Data Parallelism (DP) and Model Parallelism (MP) -- to scale distributed training of large recommendation models. We propose a compression framework called Dynamic Communication Thresholding (DCT) for communication-efficient hybrid training. DCT filters the entities to be communicated across the network through a simple hard-thresholding function, allowing only the most relevant information to pass through. For communication efficient DP, DCT compresses the parameter gradients sent to the parameter server during model synchronization. The threshold is updated only once every few thousand iterations to reduce the computational overhead of compression. For communication efficient MP, DCT incorporates a novel technique to compress the activations and gradients sent across the network during the forward and backward propagation, respectively. This is done by identifying and updating only the most relevant neurons of the neural network for each training sample in the data. We evaluate DCT on publicly available natural language processing and recommender models and datasets, as well as recommendation systems used in production at Facebook. DCT reduces communication by at least $100\times$ and $20\times$ during DP and MP, respectively. The algorithm has been deployed in production, and it improves end-to-end training time for a state-of-the-art industrial recommender model by 37\%, without any loss in performance.
Average-reward model-free reinforcement learning: a systematic review and literature mapping
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning is important part of artificial intelligence. In this paper, we review model-free reinforcement learning that utilizes the average reward optimality criterion in the infinite horizon setting. Motivated by the solo survey by Mahadevan (1996a), we provide an updated review of work in this area and extend it to cover policy-iteration and function approximation methods (in addition to the value-iteration and tabular counterparts). We present a comprehensive literature mapping. We also identify and discuss opportunities for future work.
Planning with Learned Dynamics: Probabilistic Guarantees on Safety and Reachability via Lipschitz Constants
Venue: arXiv cs.RO 2021
Year: 2021

We present a method for feedback motion planning of systems with unknown dynamics which provides probabilistic guarantees on safety, reachability, and goal stability. To find a domain in which a learned control-affine approximation of the true dynamics can be trusted, we estimate the Lipschitz constant of the difference between the true and learned dynamics, and ensure the estimate is valid with a given probability. Provided the system has at least as many controls as states, we also derive existence conditions for a one-step feedback law which can keep the real system within a small bound of a nominal trajectory planned with the learned dynamics. Our method imposes the feedback law existence as a constraint in a sampling-based planner, which returns a feedback policy around a nominal plan ensuring that, if the Lipschitz constant estimate is valid, the true system is safe during plan execution, reaches the goal, and is ultimately invariant in a small set about the goal. We demonstrate our approach by planning using learned models of a 6D quadrotor and a 7DOF Kuka arm. We show that a baseline which plans using the same learned dynamics without considering the error bound or the existence of the feedback law can fail to stabilize around the plan and become unsafe.
Bayesian Neural Networks with Soft Evidence
Venue: arXiv cs.LG 2021
Year: 2021

Bayes's rule deals with hard evidence, that is, we can calculate the probability of event $A$ occuring given that event $B$ has occurred. Soft evidence, on the other hand, involves a degree of uncertainty about whether event $B$ has actually occurred or not. Jeffrey's rule of conditioning provides a way to update beliefs in the case of soft evidence. We provide a framework to learn a probability distribution on the weights of a neural network trained using soft evidence by way of two simple algorithms for approximating Jeffrey conditionalization. We propose an experimental protocol for benchmarking these algorithms on empirical datasets and find that Jeffrey based methods are competitive or better in terms of accuracy yet show improvements in calibration metrics upwards of 20% in some cases, even when the data contains mislabeled points.
Pattern Formation by Robots with Inaccurate Movements
Venue: arXiv cs.DC 2021
Year: 2021

\textsc{Arbitrary Pattern Formation} is a fundamental problem in autonomous mobile robot systems. The problem asks to design a distributed algorithm that moves a team of autonomous, anonymous and identical mobile robots to form any arbitrary pattern $F$ given as input. In this paper, we study the problem for robots whose movements can be inaccurate. Our movement model assumes errors in both direction and extent of the intended movement. Forming the given pattern exactly is not possible in this setting. So we require that the robots must form a configuration which is close to the given pattern $F$. We call this the \textsc{Approximate Arbitrary Pattern Formation} problem. We show that with no agreement in coordinate system, the problem is unsolvable, even by fully synchronous robots, if the initial configuration 1) has rotational symmetry and there is no robot at the center of rotation or 2) has reflectional symmetry and there is no robot on the reflection axis. From all other initial configurations, we solve the problem by 1) oblivious, silent and semi-synchronous robots and 2) oblivious, asynchronous robots that can communicate using externally visible lights.
RobustBench: a standardized adversarial robustness benchmark
Venue: arXiv cs.LG 2021
Year: 2021

As a research community, we are still lacking a systematic understanding of the progress on adversarial robustness which often makes it hard to identify the most promising ideas in training robust models. A key challenge in benchmarking robustness is that its evaluation is often error-prone leading to robustness overestimation. Our goal is to establish a standardized benchmark of adversarial robustness, which as accurately as possible reflects the robustness of the considered models within a reasonable computational budget. To this end, we start by considering the image classification task and introduce restrictions (possibly loosened in the future) on the allowed models. We evaluate adversarial robustness with AutoAttack, an ensemble of white- and black-box attacks, which was recently shown in a large-scale study to improve almost all robustness evaluations compared to the original publications. To prevent overadaptation of new defenses to AutoAttack, we welcome external evaluations based on adaptive attacks, especially where AutoAttack flags a potential overestimation of robustness. Our leaderboard, hosted at https://robustbench.github.io/, contains evaluations of 120+ models and aims at reflecting the current state of the art in image classification on a set of well-defined tasks in $\ell_\infty$- and $\ell_2$-threat models and on common corruptions, with possible extensions in the future. Additionally, we open-source the library https://github.com/RobustBench/robustbench that provides unified access to 80+ robust models to facilitate their downstream applications. Finally, based on the collected models, we analyze the impact of robustness on the performance on distribution shifts, calibration, out-of-distribution detection, fairness, privacy leakage, smoothness, and transferability.
Spread of Tweets in Climate Discussions
Venue: arXiv cs.SI 2021
Year: 2021

Characterising the spreading of ideas within echo chambers is essential for understanding polarisation. In this paper, we explore the characteristics of popular and viral content in climate change discussions on Twitter around the 2019 announcement of the Nobel Peace Prize, where we find the retweet network of users to be polarised into two well-separated groups of activists and sceptics. Operationalising popularity as the number of retweets and virality as the spreading probability inferred using an independent cascade model, we find that the viral themes echo and differ from the popular themes in interesting ways. Most importantly, we find that the most viral themes in the two groups reflect different types of bonds that tie the community together, yet both function to enhance ingroup connections while repulsing outgroup engagement. With this, our study sheds light, from an information spreading perspective, on the formation and upkeep of echo chambers in climate discussions.
What breach? Measuring online awareness of security incidents by studying real-world browsing behavior
Venue: arXiv cs.CR 2021
Year: 2021

Awareness about security and privacy risks is important for developing good security habits. Learning about real-world security incidents and data breaches can alert people to the ways in which their information is vulnerable online, thus playing a significant role in encouraging safe security behavior. This paper examines 1) how often people read about security incidents online, 2) of those people, whether and to what extent they follow up with an action, e.g., by trying to read more about the incident, and 3) what influences the likelihood that they will read about an incident and take some action. We study this by quantitatively examining real-world internet-browsing data from 303 participants. Our findings present a bleak view of awareness of security incidents. Only 16% of participants visited any web pages related to six widely publicized large-scale security incidents; few read about one even when an incident was likely to have affected them (e.g., the Equifax breach almost universally affected people with Equifax credit reports). We further found that more severe incidents as well as articles that constructively spoke about the incident inspired more action. We conclude with recommendations for specific future research and for enabling useful security incident information to reach more people.
Robust & Asymptotically Locally Optimal UAV-Trajectory Generation Based on Spline Subdivision
Venue: arXiv cs.RO 2021
Year: 2021

Generating locally optimal UAV-trajectories is challenging due to the non-convex constraints of collision avoidance and actuation limits. We present the first local, optimization-based UAV-trajectory generator that simultaneously guarantees the validity and asymptotic optimality for known environments. \textit{Validity:} Given a feasible initial guess, our algorithm guarantees the satisfaction of all constraints throughout the process of optimization. \textit{Asymptotic Optimality:} We use an asymptotic exact piecewise approximation of the trajectory with an automatically adjustable resolution of its discretization. The trajectory converges under refinement to the first-order stationary point of the exact non-convex programming problem. Our method has additional practical advantages including joint optimality in terms of trajectory and time-allocation, and robustness to challenging environments as demonstrated in our experiments.
Object Permanence Through Audio-Visual Representations
Venue: arXiv cs.RO 2021
Year: 2021

As robots perform manipulation tasks and interact with objects, it is probable that they accidentally drop objects (e.g., due to an inadequate grasp of an unfamiliar object) that subsequently bounce out of their visual fields. To enable robots to recover from such errors, we draw upon the concept of object permanence-objects remain in existence even when they are not being sensed (e.g., seen) directly. In particular, we developed a multimodal neural network model-using a partial, observed bounce trajectory and the audio resulting from drop impact as its inputs-to predict the full bounce trajectory and the end location of a dropped object. We empirically show that: 1) our multimodal method predicted end locations close in proximity (i.e., within the visual field of the robot's wrist camera) to the actual locations and 2) the robot was able to retrieve dropped objects by applying minimal vision-based pick-up adjustments. Additionally, we show that our method outperformed five comparison baselines in retrieving dropped objects. Our results contribute to enabling object permanence for robots and error recovery from object drops.
Towards an Automatic Analysis of CHO-K1 Suspension Growth in Microfluidic Single-cell Cultivation
Venue: arXiv cs.LG 2021
Year: 2021

Motivation: Innovative microfluidic systems carry the promise to greatly facilitate spatio-temporal analysis of single cells under well-defined environmental conditions, allowing novel insights into population heterogeneity and opening new opportunities for fundamental and applied biotechnology. Microfluidics experiments, however, are accompanied by vast amounts of data, such as time series of microscopic images, for which manual evaluation is infeasible due to the sheer number of samples. While classical image processing technologies do not lead to satisfactory results in this domain, modern deep learning technologies such as convolutional networks can be sufficiently versatile for diverse tasks, including automatic cell tracking and counting as well as the extraction of critical parameters, such as growth rate. However, for successful training, current supervised deep learning requires label information, such as the number or positions of cells for each image in a series; obtaining these annotations is very costly in this setting. Results: We propose a novel Machine Learning architecture together with a specialized training procedure, which allows us to infuse a deep neural network with human-powered abstraction on the level of data, leading to a high-performing regression model that requires only a very small amount of labeled data. Specifically, we train a generative model simultaneously on natural and synthetic data, so that it learns a shared representation, from which a target variable, such as the cell count, can be reliably estimated.
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Venue: arXiv cs.DS 2021
Year: 2021

Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. This paper develops fast dynamic algorithms for sparse spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. Under the popular OMv conjecture, we show that there can be no decremental or incremental algorithm that maintains an $n^{1+o(1)}$ edge (purely additive) $+n^δ$-emulator for any $δ<1/2$ with arbitrary polynomial preprocessing time and total update time $m^{1+o(1)}$. Also, under the Combinatorial $k$-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an $n^{1+o(1)}$ edge $(1+ε,n^{o(1)})$-spanner or emulator must either have preprocessing time $mn^{1-o(1)}$ or amortized update time $m^{1-o(1)}$. Both of our conditional lower bounds are tight. As the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the $m^{1-o(1)}$ update time for dense graphs. For any constant $ε\in (0,1]$, there is a fully dynamic algorithm with worst-case update time $O(n^{1.529})$ that whp maintains an $n^{1+o(1)}$ edge $(1+ε,n^{o(1)})$-spanner. Our new algebraic techniques and spanner algorithms allow us to also obtain (1) a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) with update and path query time $O(n^{1.9})$; (2) a fully dynamic $(1+ε)$-approximate APSP algorithm with update time $O(n^{1.529})$; (3) a fully dynamic algorithm for near-$2$-approximate Steiner tree maintenance.
Simulated Chats for Building Dialog Systems: Learning to Generate Conversations from Instructions
Venue: arXiv cs.CL 2021
Year: 2021

Popular dialog datasets such as MultiWOZ are created by providing crowd workers an instruction, expressed in natural language, that describes the task to be accomplished. Crowd workers play the role of a user and an agent to generate dialogs to accomplish tasks involving booking restaurant tables, calling a taxi etc. In this paper, we present a data creation strategy that uses the pre-trained language model, GPT2, to simulate the interaction between crowd workers by creating a user bot and an agent bot. We train the simulators using a smaller percentage of actual crowd-generated conversations and their corresponding instructions. We demonstrate that by using the simulated data, we achieve significant improvements in low-resource settings on two publicly available datasets - the MultiWOZ dataset and the Persona chat dataset.
Temporal blocking of finite-difference stencil operators with sparse "off-the-grid" sources
Venue: arXiv cs.DC 2021
Year: 2021

Stencil kernels dominate a range of scientific applications, including seismic and medical imaging, image processing, and neural networks. Temporal blocking is a performance optimization that aims to reduce the required memory bandwidth of stencil computations by re-using data from the cache for multiple time steps. It has already been shown to be beneficial for this class of algorithms. However, applying temporal blocking to practical applications' stencils remains challenging. These computations often consist of sparsely located operators not aligned with the computational grid ("off-the-grid"). Our work is motivated by modeling problems in which source injections result in wavefields that must then be measured at receivers by interpolation from the grided wavefield. The resulting data dependencies make the adoption of temporal blocking much more challenging. We propose a methodology to inspect these data dependencies and reorder the computation, leading to performance gains in stencil codes where temporal blocking has not been applicable. We implement this novel scheme in the Devito domain-specific compiler toolchain. Devito implements a domain-specific language embedded in Python to generate optimized partial differential equation solvers using the finite-difference method from high-level symbolic problem definitions. We evaluate our scheme using isotropic acoustic, anisotropic acoustic, and isotropic elastic wave propagators of industrial significance. After auto-tuning, performance evaluation shows that this enables substantial performance improvement through temporal blocking over highly-optimized vectorized spatially-blocked code of up to 1.6x.
Optimal Index Assignment for Scalar Quantizers and M-PSK via a Discrete Convolution-Rearrangement Inequality
Venue: arXiv cs.IT 2021
Year: 2021

This paper investigates the problem of finding an optimal nonbinary index assignment from (M) quantization levels of a maximum entropy scalar quantizer to (M)-PSK symbols transmitted over a symmetric memoryless channel with additive noise following decreasing probability density function (such as the AWGN channel) so as to minimize the channel mean-squared distortion. The so-called zigzag mapping under maximum-likelihood (ML) decoding was known to be asymptotically optimal, but the problem of determining the optimal index assignment for any given signal-to-noise ratio (SNR) is still open. Based on a generalized version of the Hardy-Littlewood convolution-rearrangement inequality, we prove that the zigzag mapping under ML decoding is optimal for all SNRs. It is further proved that the same optimality results also hold under minimum mean-square-error (MMSE) decoding. Numerical results are presented to verify our optimality results and to demonstrate the performance gain of the optimal (M)-ary index assignment over the state-of-the-art binary counterpart for the case of (8)-PSK over the AWGN channel.
Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecification
Venue: arXiv cs.LG 2021
Year: 2021

Many real-world physical control systems are required to satisfy constraints upon deployment. Furthermore, real-world systems are often subject to effects such as non-stationarity, wear-and-tear, uncalibrated sensors and so on. Such effects effectively perturb the system dynamics and can cause a policy trained successfully in one domain to perform poorly when deployed to a perturbed version of the same domain. This can affect a policy's ability to maximize future rewards as well as the extent to which it satisfies constraints. We refer to this as constrained model misspecification. We present an algorithm that mitigates this form of misspecification, and showcase its performance in multiple simulated Mujoco tasks from the Real World Reinforcement Learning (RWRL) suite.
Algebraic Structures from Concurrent Constraint Programming Calculi for Distributed Information in Multi-Agent Systems
Venue: arXiv cs.MA 2021
Year: 2021

Spatial constraint systems (scs) are semantic structures for reasoning about spatial and epistemic information in concurrent systems. We develop the theory of scs to reason about the distributed information of potentially infinite groups. We characterize the notion of distributed information of a group of agents as the infimum of the set of join-preserving functions that represent the spaces of the agents in the group. We provide an alternative characterization of this notion as the greatest family of join-preserving functions that satisfy certain basic properties. For completely distributive lattices, we establish that distributed information of a group is the greatest information below all possible combinations of information in the spaces of the agents in the group that derive a given piece of information. We show compositionality results for these characterizations and conditions under which information that can be obtained by an infinite group can also be obtained by a finite group. Finally, we provide an application on mathematical morphology where dilations, one of its fundamental operations, define an scs on a powerset lattice. We show that distributed information represents a particular dilation in such scs.
RigidFusion: Robot Localisation and Mapping in Environments with Large Dynamic Rigid Objects
Venue: arXiv cs.RO 2021
Year: 2021

This work presents a novel RGB-D SLAM approach to simultaneously segment, track and reconstruct the static background and large dynamic rigid objects that can occlude major portions of the camera view. Previous approaches treat dynamic parts of a scene as outliers and are thus limited to a small amount of changes in the scene, or rely on prior information for all objects in the scene to enable robust camera tracking. Here, we propose to treat all dynamic parts as one rigid body and simultaneously segment and track both static and dynamic components. We, therefore, enable simultaneous localisation and reconstruction of both the static background and rigid dynamic components in environments where dynamic objects cause large occlusion. We evaluate our approach on multiple challenging scenes with large dynamic occlusion. The evaluation demonstrates that our approach achieves better motion segmentation, localisation and mapping without requiring prior knowledge of the dynamic object's shape and appearance.