OpenRaiser/Intern-Atlas huggingface dataset:
Understanding Neural Networks and Individual Neuron Importance via Information-Ordered Cumulative Ablation
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we investigate the use of three information-theoretic quantities -- entropy, mutual information with the class variable, and a class selectivity measure based on Kullback-Leibler divergence -- to understand and study the behavior of already trained fully-connected feed-forward neural networks. We analyze the connection between these information-theoretic quantities and classification performance on the test set by cumulatively ablating neurons in networks trained on MNIST, FashionMNIST, and CIFAR-10. Our results parallel those recently published by Morcos et al., indicating that class selectivity is not a good indicator for classification performance. However, looking at individual layers separately, both mutual information and class selectivity are positively correlated with classification performance, at least for networks with ReLU activation functions. We provide explanations for this phenomenon and conclude that it is ill-advised to compare the proposed information-theoretic quantities across layers. Furthermore, we show that cumulative ablation of neurons with ascending or descending information-theoretic quantities can be used to formulate hypotheses regarding the joint behavior of multiple neurons, such as redundancy and synergy, with comparably low computational cost. We also draw connections to the information bottleneck theory for neural networks.
NAIS-Net: Stable Deep Networks from Non-Autonomous Differential Equations
Venue: arXiv cs.NE 2021
Year: 2021

This paper introduces Non-Autonomous Input-Output Stable Network(NAIS-Net), a very deep architecture where each stacked processing block is derived from a time-invariant non-autonomous dynamical system. Non-autonomy is implemented by skip connections from the block input to each of the unrolled processing stages and allows stability to be enforced so that blocks can be unrolled adaptively to a pattern-dependent processing depth. NAIS-Net induces non-trivial, Lipschitz input-output maps, even for an infinite unroll length. We prove that the network is globally asymptotically stable so that for every initial condition there is exactly one input-dependent equilibrium assuming $tanh$ units, and incrementally stable for ReL units. An efficient implementation that enforces the stability under derived conditions for both fully-connected and convolutional layers is also presented. Experimental results show how NAIS-Net exhibits stability in practice, yielding a significant reduction in generalization gap compared to ResNets.
Maximum Integer Flows in Directed Planar Graphs with Multiple Sources and Sinks and Vertex Capacities
Venue: arXiv cs.DS 2021
Year: 2021

We consider the problem of finding maximum flows in planar graphs with capacities on both vertices and edges and with multiple sources and sinks. We present three algorithms when the capacities are integers. The first algorithm runs in $O(n \log^3 n + kn)$ time when all capacities are bounded, where $n$ is the number of vertices in the graph and $k$ is the number of terminals. This algorithm is the first to solve the vertex-disjoint paths problem in near-linear time when $k$ is bounded but larger than 2. The second algorithm runs in $O(k^2(k^3 + Δ) n \text{ polylog} (nU))$ time, where $U$ is the largest finite capacity of a single vertex and $Δ$ is the maximum degree of a vertex. Finally, when $k=3$, we present an algorithm that runs in $O(n \log n)$ time; this algorithm works even when the capacities are arbitrary reals. Our algorithms improve on the fastest previously known algorithms when $k$ and $Δ$ are small and $U$ is bounded by a polynomial in $n$. Prior to this result, the fastest algorithms ran in $O(n^2 / \log n)$ time for real capacities and $O(n^{3/2} \log n \log U)$ for integer capacities.
How Private Are Commonly-Used Voting Rules?
Venue: arXiv cs.CR 2021
Year: 2021

Differential privacy has been widely applied to provide privacy guarantees by adding random noise to the function output. However, it inevitably fails in many high-stakes voting scenarios, where voting rules are required to be deterministic. In this work, we present the first framework for answering the question: "How private are commonly-used voting rules?" Our answers are two-fold. First, we show that deterministic voting rules provide sufficient privacy in the sense of distributional differential privacy (DDP). We show that assuming the adversarial observer has uncertainty about individual votes, even publishing the histogram of votes achieves good DDP. Second, we introduce the notion of exact privacy to compare the privacy preserved in various commonly-studied voting rules, and obtain dichotomy theorems of exact DDP within a large subset of voting rules called generalized scoring rules.
Multi-UAV Cooperative Trajectory for Servicing Dynamic Demands and Charging Battery
Venue: arXiv cs.NI 2021
Year: 2021

Unmanned Aerial Vehicle (UAV) technology is a promising solution for providing high-quality mobile services to ground users, where a UAV with limited service coverage travels among multiple geographical user locations (e.g., hotspots) for servicing their demands locally. How to dynamically determine a UAV swarm's cooperative path planning to best meet many users' spatio-temporally distributed demands is an important question but is unaddressed in the literature. To our best knowledge, this paper is the first to design and analyze cooperative path planning algorithms of a large UAV swarm for optimally servicing many spatial locations, where ground users' demands are released dynamically in the long time horizon. Regarding a single UAV's path planning design, we manage to substantially simplify the traditional dynamic program and propose an optimal algorithm of low computation complexity, which is only polynomial with respect to both the numbers of spatial locations and user demands. After coordinating a large number $K$ of UAVs, this simplified dynamic optimization problem becomes intractable and we alternatively present a fast iterative cooperation algorithm with provable approximation ratio $1-(1-\frac{1}{K})^{K}$ in the worst case, which is proved to obviously outperform the traditional approach of partitioning UAVs to serve different location clusters separately. To relax UAVs' battery capacity limit for sustainable service provisioning, we further allow UAVs to travel to charging stations in the mean time and thus jointly design UAVs' path planning over users' locations and charging stations. Despite of the problem difficulty, for the optimal solution, we successfully transform the problem to an integer linear program by creating novel directed acyclic graph of the UAV-state transition diagram, and propose an iterative algorithm with constant approximation ratio.
Semantic Network Interpretation
Venue: arXiv cs.CV 2021
Year: 2021

Network interpretation as an effort to reveal the features learned by a network remains largely visualization-based. In this paper, our goal is to tackle semantic network interpretation at both filter and decision level. For filter-level interpretation, we represent the concepts a filter encodes with a probability distribution of visual attributes. The decision-level interpretation is achieved by textual summarization that generates an explanatory sentence containing clues behind a network's decision. A Bayesian inference algorithm is proposed to automatically associate filters and network decisions with visual attributes. Human study confirms that the semantic interpretation is a beneficial alternative or complement to visualization methods. We demonstrate the crucial role that semantic network interpretation can play in understanding a network's failure patterns. More importantly, semantic network interpretation enables a better understanding of the correlation between a model's performance and its distribution metrics like filter selectivity and concept sparseness.
Towards Understanding Acceleration Tradeoff between Momentum and Asynchrony in Nonconvex Stochastic Optimization
Venue: arXiv cs.LG 2021
Year: 2021

Asynchronous momentum stochastic gradient descent algorithms (Async-MSGD) is one of the most popular algorithms in distributed machine learning. However, its convergence properties for these complicated nonconvex problems is still largely unknown, because of the current technical limit. Therefore, in this paper, we propose to analyze the algorithm through a simpler but nontrivial nonconvex problem - streaming PCA, which helps us to understand Aync-MSGD better even for more general problems. Specifically, we establish the asymptotic rate of convergence of Async-MSGD for streaming PCA by diffusion approximation. Our results indicate a fundamental tradeoff between asynchrony and momentum: To ensure convergence and acceleration through asynchrony, we have to reduce the momentum (compared with Sync-MSGD). To the best of our knowledge, this is the first theoretical attempt on understanding Async-MSGD for distributed nonconvex stochastic optimization. Numerical experiments on both streaming PCA and training deep neural networks are provided to support our findings for Async-MSGD.
Droplet: Decentralized Authorization and Access Control for Encrypted Data Streams
Venue: arXiv cs.CR 2021
Year: 2021

This paper presents Droplet, a decentralized data access control service. Droplet enables data owners to securely and selectively share their encrypted data while guaranteeing data confidentiality in the presence of unauthorized parties and compromised data servers. Droplet's contribution lies in coupling two key ideas: (i) a cryptographically-enforced access control construction for encrypted data streams which enables users to define fine-grained stream-specific access policies, and (ii) a decentralized authorization service that serves user-defined access policies. In this paper, we present Droplet's design, the reference implementation of Droplet, and the experimental results of three case-study applications deployed with Droplet: Fitbit activity tracker, Ava health tracker, and ECOviz smart meter dashboard, demonstrating Droplet's applicability for secure sharing of IoT streams.
Fast Approximate Natural Gradient Descent in a Kronecker-factored Eigenbasis
Venue: arXiv cs.LG 2021
Year: 2021

Optimization algorithms that leverage gradient covariance information, such as variants of natural gradient descent (Amari, 1998), offer the prospect of yielding more effective descent directions. For models with many parameters, the covariance matrix they are based on becomes gigantic, making them inapplicable in their original form. This has motivated research into both simple diagonal approximations and more sophisticated factored approximations such as KFAC (Heskes, 2000; Martens & Grosse, 2015; Grosse & Martens, 2016). In the present work we draw inspiration from both to propose a novel approximation that is provably better than KFAC and amendable to cheap partial updates. It consists in tracking a diagonal variance, not in parameter coordinates, but in a Kronecker-factored eigenbasis, in which the diagonal approximation is likely to be more effective. Experiments show improvements over KFAC in optimization speed for several deep network architectures.
Introducing the Robot Security Framework (RSF), a standardized methodology to perform security assessments in robotics
Venue: arXiv cs.CR 2021
Year: 2021

Robots have gained relevance in society, increasingly performing critical tasks. Nonetheless, robot security is being underestimated. Robotics security is a complex landscape, which often requires a cross-disciplinar perspective to which classical security lags behind. To address this issue, we present the Robot Security Framework (RSF), a methodology to perform systematic security assessments in robots. We propose, adapt and develop specific terminology and provide guidelines to enable a holistic security assessment following four main layers (Physical, Network, Firmware and Application). We argue that modern robotics should regard as equally relevant internal and external communication security. Finally, we advocate against "security by obscurity". We conclude that the field of security in robotics deserves further research efforts.
Social Networks through the Prism of Cognition
Venue: arXiv cs.SI 2021
Year: 2021

Human relations are driven by social events-people interact, exchange information, share knowledge and emotions, and gather news from mass media. These events leave traces in human memory, the strength of which depends on cognitive factors such as emotions or attention span. Each trace continuously weakens over time unless another related event activity strengthens it. Here, we introduce a novel cognition-driven social network (CogSNet) model that accounts for cognitive aspects of social perception. The model explicitly represents each social interaction as a trace in human memory with its corresponding dynamics. The strength of the trace is the only measure of the influence that the interactions had on a person. For validation, we apply our model to NetSense data on social interactions among university students. The results show that CogSNet significantly improves the quality of modeling of human interactions in social networks.
On decision regions of narrow deep neural networks
Venue: arXiv cs.LG 2021
Year: 2021

We show that for neural network functions that have width less or equal to the input dimension all connected components of decision regions are unbounded. The result holds for continuous and strictly monotonic activation functions as well as for the ReLU activation function. This complements recent results on approximation capabilities by [Hanin 2017 Approximating] and connectivity of decision regions by [Nguyen 2018 Neural] for such narrow neural networks. Our results are illustrated by means of numerical experiments.
A PTAS for $\ell_p$-Low Rank Approximation
Venue: arXiv cs.DS 2021
Year: 2021

A number of recent works have studied algorithms for entrywise $\ell_p$-low rank approximation, namely, algorithms which given an $n \times d$ matrix $A$ (with $n \geq d$), output a rank-$k$ matrix $B$ minimizing $\|A-B\|_p^p=\sum_{i,j}|A_{i,j}-B_{i,j}|^p$ when $p > 0$; and $\|A-B\|_0=\sum_{i,j}[A_{i,j}\neq B_{i,j}]$ for $p=0$. On the algorithmic side, for $p \in (0,2)$, we give the first $(1+ε)$-approximation algorithm running in time $n^{\text{poly}(k/ε)}$. Further, for $p = 0$, we give the first almost-linear time approximation scheme for what we call the Generalized Binary $\ell_0$-Rank-$k$ problem. Our algorithm computes $(1+ε)$-approximation in time $(1/ε)^{2^{O(k)}/ε^{2}} \cdot nd^{1+o(1)}$. On the hardness of approximation side, for $p \in (1,2)$, assuming the Small Set Expansion Hypothesis and the Exponential Time Hypothesis (ETH), we show that there exists $δ:= δ(α) > 0$ such that the entrywise $\ell_p$-Rank-$k$ problem has no $α$-approximation algorithm running in time $2^{k^δ}$.
Safe Option-Critic: Learning Safety in the Option-Critic Architecture
Venue: arXiv cs.AI 2021
Year: 2021

Designing hierarchical reinforcement learning algorithms that exhibit safe behaviour is not only vital for practical applications but also, facilitates a better understanding of an agent's decisions. We tackle this problem in the options framework, a particular way to specify temporally abstract actions which allow an agent to use sub-policies with start and end conditions. We consider a behaviour as safe that avoids regions of state-space with high uncertainty in the outcomes of actions. We propose an optimization objective that learns safe options by encouraging the agent to visit states with higher behavioural consistency. The proposed objective results in a trade-off between maximizing the standard expected return and minimizing the effect of model uncertainty in the return. We propose a policy gradient algorithm to optimize the constrained objective function. We examine the quantitative and qualitative behaviour of the proposed approach in a tabular grid-world, continuous-state puddle-world, and three games from the Arcade Learning Environment: Ms.Pacman, Amidar, and Q*Bert. Our approach achieves a reduction in the variance of return, boosts performance in environments with intrinsic variability in the reward structure, and compares favorably both with primitive actions as well as with risk-neutral options.
Towards an open standard for assessing the severity of robot security vulnerabilities, the Robot Vulnerability Scoring System (RVSS)
Venue: arXiv cs.RO 2021
Year: 2021

Robots are typically not created with security as a main concern. Contrasting to typical IT systems, cyberphysical systems rely on security to handle safety aspects. In light of the former, classic scoring methods such as the Common Vulnerability Scoring System (CVSS) are not able to accurately capture the severity of robot vulnerabilities. The present research work focuses upon creating an open and free to access Robot Vulnerability Scoring System (RVSS) that considers major relevant issues in robotics including a) robot safety aspects, b) assessment of downstream implications of a given vulnerability, c) library and third-party scoring assessments and d) environmental variables, such as time since vulnerability disclosure or exposure on the web. Finally, an experimental evaluation of RVSS with contrast to CVSS is provided and discussed with focus on the robotics security landscape.
Fair allocation of combinations of indivisible goods and chores
Venue: arXiv cs.GT 2021
Year: 2021

We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are `goods' i.e., they yield positive utility for the agents. There is also some work where the items are `chores' that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e.g., fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.
Fairly Allocating Many Goods with Few Queries
Venue: arXiv cs.GT 2021
Year: 2021

We investigate the query complexity of the fair allocation of indivisible goods. For two agents with arbitrary monotonic utilities, we design an algorithm that computes an allocation satisfying envy-freeness up to one good (EF1), a relaxation of envy-freeness, using a logarithmic number of queries. We show that the logarithmic query complexity bound also holds for three agents with additive utilities, and that a polylogarithmic bound holds for three agents with monotonic utilities. These results suggest that it is possible to fairly allocate goods in practice even when the number of goods is extremely large. By contrast, we prove that computing an allocation satisfying envy-freeness and another of its relaxations, envy-freeness up to any good (EFX), requires a linear number of queries even when there are only two agents with identical additive utilities.
Multitask Gaussian Process with Hierarchical Latent Interactions
Venue: arXiv cs.LG 2021
Year: 2021

Multitask Gaussian process (MTGP) is powerful for joint learning of multiple tasks with complicated correlation patterns. However, due to the assembling of additive independent latent functions, all current MTGPs including the salient linear model of coregionalization (LMC) and convolution frameworks cannot effectively represent and learn the hierarchical latent interactions between its latent functions. In this paper, we further investigate the interactions in LMC of MTGP and then propose a novel kernel representation of the hierarchical interactions, which ameliorates both the expressiveness and the interpretability of MTGP. Specifically, we express the interaction as a product of function interaction and coefficient interaction. The function interaction is modeled by using cross convolution of latent functions. The coefficient interaction between the LMCs is described as a cross coregionalization term. We validate that considering the interactions can promote knowledge transferring in MTGP and compare our approach with some state-of-the-art MTGPs on both synthetic- and real-world datasets.
On Linearly Precoded Rate Splitting for Gaussian MIMO Broadcast Channels
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we consider a general K-user Gaussian multiple-input multiple-output (MIMO) broadcast channel (BC). We assume that the channel state is deterministic and known to all the nodes. While the private-message capacity region is well known to be achievable with dirty paper coding (DPC), we are interested in the simpler linearly precoded transmission schemes. In particular, we focus on linear precoding schemes combined with rate-splitting (RS). First, we derive an achievable rate region with minimum mean square error (MMSE) precoding at the transmitter and joint decoding of the sub-messages at the receivers. Then, we study the achievable sum rate of this scheme and obtain two findings: 1) an analytically tractable upper bound on the sum rate that is shown numerically to be a close approximation, and 2) how to reduce the number of active streams -- crucial to the overall complexity -- while preserving the sum rate to within a constant loss. The latter results in two practical algorithms: a stream elimination algorithm and a stream ordering algorithm. Finally, we investigate the constant-gap optimality of linearly precoded RS with respect to the capacity. Our result reveals that, while the achievable rate of linear precoding alone can be arbitrarily far from the capacity, the introduction of RS can help achieve the capacity region to within a constant gap in the two-user case. Nevertheless, we prove that the RS scheme's constant-gap optimality does not extend to the three-user case. Specifically, we show, through a pathological example, that the gap between the sum rate and the sum capacity can be unbounded.
The Sample Complexity of Up-to-$\varepsilon$ Multi-Dimensional Revenue Maximization
Venue: arXiv cs.GT 2021
Year: 2021

We consider the sample complexity of revenue maximization for multiple bidders in unrestricted multi-dimensional settings. Specifically, we study the standard model of $n$ additive bidders whose values for $m$ heterogeneous items are drawn independently. For any such instance and any $\varepsilon>0$, we show that it is possible to learn an $\varepsilon$-Bayesian Incentive Compatible auction whose expected revenue is within $\varepsilon$ of the optimal $\varepsilon$-BIC auction from only polynomially many samples. Our fully nonparametric approach is based on ideas that hold quite generally, and completely sidestep the difficulty of characterizing optimal (or near-optimal) auctions for these settings. Therefore, our results easily extend to general multi-dimensional settings, including valuations that are not necessarily even subadditive, and arbitrary allocation constraints. For the cases of a single bidder and many goods, or a single parameter (good) and many bidders, our analysis yields exact incentive compatibility (and for the latter also computational efficiency). Although the single-parameter case is already well-understood, our corollary for this case extends slightly the state-of-the-art.