OpenRaiser/Intern-Atlas huggingface dataset:
Non-Terrestrial Networks in the 6G Era: Challenges and Opportunities
Venue: arXiv cs.NI 2021
Year: 2021

Many organizations recognize non-terrestrial networks (NTNs) as a key component to provide cost-effective and high-capacity connectivity in future 6th generation (6G) wireless networks. Despite this premise, there are still many questions to be answered for proper network design, including those associated to latency and coverage constraints. In this paper, after reviewing research activities on NTNs, we present the characteristics and enabling technologies of NTNs in the 6G landscape and shed light on the challenges in the field that are still open for future research. As a case study, we evaluate the performance of an NTN scenario in which aerial/space vehicles use millimeter wave (mmWave) frequencies to provide access connectivity to on-the-ground mobile terminals as a function of different networking configurations.
There and Back Again: Unraveling the Variational Auto-Encoder
Venue: arXiv cs.LG 2021
Year: 2021

We prove that the evidence lower bound (ELBO) employed by variational auto-encoders (VAEs) admits non-trivial solutions having constant posterior variances under certain mild conditions, removing the need to learn variances in the encoder. The proof follows from an unexpected journey through an array of topics: the closed form optimal decoder for Gaussian VAEs, a proof that the decoder is always smooth, a proof that the ELBO at its stationary points is equal to the exact log evidence, and the posterior variance is merely part of a stochastic estimator of the decoder Hessian. The penalty incurred from using a constant posterior variance is small under mild conditions, and otherwise discourages large variations in the decoder Hessian. From here we derive a simplified formulation of the ELBO as an expectation over a batch, which we call the Batch Information Lower Bound (BILBO). Despite the use of Gaussians, our analysis is broadly applicable -- it extends to any likelihood function that induces a Riemannian metric. Regarding learned likelihoods, we show that the ELBO is optimal in the limit as the likelihood variances approach zero, where it is equivalent to the change of variables formulation employed in normalizing flow networks. Standard optimization procedures are unstable in this limit, so we propose a bounded Gaussian likelihood that is invariant to the scale of the data using a measure of the aggregate information in a batch, which we call Bounded Aggregate Information Sampling (BAGGINS). Combining the two formulations, we construct VAE networks with only half the outputs of ordinary VAEs (no learned variances), yielding improved ELBO scores and scale invariance in experiments. As we perform our analyses irrespective of any particular network architecture, our reformulations may apply to any VAE implementation.
Online Reinforcement Learning of Optimal Threshold Policies for Markov Decision Processes
Venue: arXiv cs.LG 2021
Year: 2021

To overcome the curses of dimensionality and modeling of Dynamic Programming (DP) methods to solve Markov Decision Process (MDP) problems, Reinforcement Learning (RL) methods are adopted in practice. Contrary to traditional RL algorithms which do not consider the structural properties of the optimal policy, we propose a structure-aware learning algorithm to exploit the ordered multi-threshold structure of the optimal policy, if any. We prove the asymptotic convergence of the proposed algorithm to the optimal policy. Due to the reduction in the policy space, the proposed algorithm provides remarkable improvements in storage and computational complexities over classical RL algorithms. Simulation results establish that the proposed algorithm converges faster than other RL algorithms.
Direct and indirect reinforcement learning
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning (RL) algorithms have been successfully applied to a range of challenging sequential decision making and control tasks. In this paper, we classify RL into direct and indirect RL according to how they seek the optimal policy of the Markov decision process problem. The former solves the optimal policy by directly maximizing an objective function using gradient descent methods, in which the objective function is usually the expectation of accumulative future rewards. The latter indirectly finds the optimal policy by solving the Bellman equation, which is the sufficient and necessary condition from Bellman's principle of optimality. We study policy gradient forms of direct and indirect RL and show that both of them can derive the actor-critic architecture and can be unified into a policy gradient with the approximate value function and the stationary state distribution, revealing the equivalence of direct and indirect RL. We employ a Gridworld task to verify the influence of different forms of policy gradient, suggesting their differences and relationships experimentally. Finally, we classify current mainstream RL algorithms using the direct and indirect taxonomy, together with other ones including value-based and policy-based, model-based and model-free.
A Replication Strategy for Mobile Opportunistic Networks based on Utility Clustering
Venue: arXiv cs.NI 2021
Year: 2021

Dynamic replication is a wide-spread multi-copy routing approach for efficiently coping with the intermittent connectivity in mobile opportunistic networks. According to it, a node forwards a message replica to an encountered node based on a utility value that captures the latter's fitness for delivering the message to the destination. The popularity of the approach stems from its flexibility to effectively operate in networks with diverse characteristics without requiring special customization. Nonetheless, its drawback is the tendency to produce a high number of replicas that consume limited resources such as energy and storage. To tackle the problem we make the observation that network nodes can be grouped, based on their utility values, into clusters that portray different delivery capabilities. We exploit this finding to transform the basic forwarding strategy, which is to move a packet using nodes of increasing utility, and actually forward it through clusters of increasing delivery capability. The new strategy works in synergy with the basic dynamic replication algorithms and is fully configurable, in the sense that it can be used with virtually any utility function. We also extend our approach to work with two utility functions at the same time, a feature that is especially efficient in mobile networks that exhibit social characteristics. By conducting experiments in a wide set of real-life networks, we empirically show that our method is robust in reducing the overall number of replicas in networks with diverse connectivity characteristics without at the same time hindering delivery efficiency.
Attack-Resistant Federated Learning with Residual-based Reweighting
Venue: arXiv cs.LG 2021
Year: 2021

Federated learning has a variety of applications in multiple domains by utilizing private training data stored on different devices. However, the aggregation process in federated learning is highly vulnerable to adversarial attacks so that the global model may behave abnormally under attacks. To tackle this challenge, we present a novel aggregation algorithm with residual-based reweighting to defend federated learning. Our aggregation algorithm combines repeated median regression with the reweighting scheme in iteratively reweighted least squares. Our experiments show that our aggregation algorithm outperforms other alternative algorithms in the presence of label-flipping and backdoor attacks. We also provide theoretical analysis for our aggregation algorithm.
Terahertz Multi-User Massive MIMO with Intelligent Reflecting Surface: Beam Training and Hybrid Beamforming
Venue: arXiv cs.IT 2021
Year: 2021

Terahertz (THz) communications open a new frontier for the wireless network thanks to their dramatically wider available bandwidth compared to the current micro-wave and forthcoming millimeter-wave communications. However, due to the short length of THz waves, they also suffer from severe path attenuation and poor diffraction. To compensate the THz-induced propagation loss, this paper proposes to combine two promising techniques, viz., massive multiple input multiple output (MIMO) and intelligent reflecting surface (IRS), in THz multi-user communications, considering their significant beamforming and aperture gains. Nonetheless, channel estimation and low-cost beamforming turn out to be two main obstacles to realizing this combination, due to the passivity of IRS for sending/receiving pilot signals and the large-scale use of expensive RF chains in massive MIMO. In view of these limitations, this paper first develops a cooperative beam training scheme to facilitate the channel estimation with IRS. In particular, we design two different hierarchical codebooks for the proposed training procedure, which are able to balance between the robustness against noise and searching complexity. Based on the training results, we further propose two cost-efficient hybrid beamforming (HB) designs for both single-user and multi-user scenarios, respectively. Simulation results demonstrate that the proposed joint beam training and HB scheme is able to achieve close performance to the optimal fully digital beamforming (FDB) which is implemented even under perfect channel state information (CSI).
SESS: Self-Ensembling Semi-Supervised 3D Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

The performance of existing point cloud-based 3D object detection methods heavily relies on large-scale high-quality 3D annotations. However, such annotations are often tedious and expensive to collect. Semi-supervised learning is a good alternative to mitigate the data annotation issue, but has remained largely unexplored in 3D object detection. Inspired by the recent success of self-ensembling technique in semi-supervised image classification task, we propose SESS, a self-ensembling semi-supervised 3D object detection framework. Specifically, we design a thorough perturbation scheme to enhance generalization of the network on unlabeled and new unseen data. Furthermore, we propose three consistency losses to enforce the consistency between two sets of predicted 3D object proposals, to facilitate the learning of structure and semantic invariances of objects. Extensive experiments conducted on SUN RGB-D and ScanNet datasets demonstrate the effectiveness of SESS in both inductive and transductive semi-supervised 3D object detection. Our SESS achieves competitive performance compared to the state-of-the-art fully-supervised method by using only 50% labeled data. Our code is available at https://github.com/Na-Z/sess.
Properties of Unique Information
Venue: arXiv cs.IT 2021
Year: 2021

We study the measure of unique information $UI(T:X\setminus Y)$ defined by Bertschinger et al. (2014) within the framework of information decompositions. We study uniqueness and support of the solutions to the optimization problem underlying the definition of $UI$. We identify sufficient conditions for non-uniqueness of solutions with full support in terms of conditional independence constraints and in terms of the cardinalities of $T$, $X$ and $Y$. Our results are based on a reformulation of the first order conditions on the objective function as rank constraints on a matrix of conditional probabilities. These results help to speed up the computation of $UI(T:X\setminus Y)$, most notably when $T$ is binary. In the case that all variables are binary, we obtain a complete picture of where the optimizing probability distributions lie.
Haptic communication optimises joint decisions and affords implicit confidence sharing
Venue: arXiv cs.RO 2021
Year: 2021

Group decisions can outperform the choices of the best individual group members. Previous research suggested that optimal group decisions require individuals to communicate explicitly (e.g., verbally) their confidence levels. Our study addresses the untested hypothesis that implicit communication using a sensorimotor channel -- haptic coupling -- may afford optimal group decisions, too. We report that haptically coupled dyads solve a perceptual discrimination task more accurately than their best individual members; and five times faster than dyads using explicit communication. Furthermore, our computational analyses indicate that the haptic channel affords implicit confidence sharing. We found that dyads take leadership over the choice and communicate their confidence in it by modulating both the timing and the force of their movements. Our findings may pave the way to negotiation technologies using fast sensorimotor communication to solve problems in groups.
Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems
Venue: arXiv cs.DC 2021
Year: 2021

Graph processing has become an important part of various areas of computing, including machine learning, medical applications, social network analysis, computational sciences, and others. A growing amount of the associated graph processing workloads are dynamic, with millions of edges added or removed per second. Graph streaming frameworks are specifically crafted to enable the processing of such highly dynamic workloads. Recent years have seen the development of many such frameworks. However, they differ in their general architectures (with key details such as the support for the concurrent execution of graph updates and queries, or the incorporated graph data organization), the types of updates and workloads allowed, and many others. To facilitate the understanding of this growing field, we provide the first analysis and taxonomy of dynamic and streaming graph processing. We focus on identifying the fundamental system designs and on understanding their support for concurrency, and for different graph updates as well as analytics workloads. We also crystallize the meaning of different concepts associated with streaming graph processing, such as dynamic, temporal, online, and time-evolving graphs, edge-centric processing, models for the maintenance of updates, and graph databases. Moreover, we provide a bridge with the very rich landscape of graph streaming theory by giving a broad overview of recent theoretical related advances, and by discussing which graph streaming models and settings could be helpful in developing more powerful streaming frameworks and designs. We also outline graph streaming workloads and research challenges.
Pontryagin Differentiable Programming: An End-to-End Learning and Control Framework
Venue: arXiv cs.LG 2021
Year: 2021

This paper develops a Pontryagin Differentiable Programming (PDP) methodology, which establishes a unified framework to solve a broad class of learning and control tasks. The PDP distinguishes from existing methods by two novel techniques: first, we differentiate through Pontryagin's Maximum Principle, and this allows to obtain the analytical derivative of a trajectory with respect to tunable parameters within an optimal control system, enabling end-to-end learning of dynamics, policies, or/and control objective functions; and second, we propose an auxiliary control system in the backward pass of the PDP framework, and the output of this auxiliary control system is the analytical derivative of the original system's trajectory with respect to the parameters, which can be iteratively solved using standard control tools. We investigate three learning modes of the PDP: inverse reinforcement learning, system identification, and control/planning. We demonstrate the capability of the PDP in each learning mode on different high-dimensional systems, including multi-link robot arm, 6-DoF maneuvering quadrotor, and 6-DoF rocket powered landing.
Nearly accurate solutions for Ising-like models using Maximal Entropy Random Walk
Venue: arXiv cs.IT 2021
Year: 2021

While one-dimensional Markov processes are well understood, going to higher dimensions there are only a few analytically solved Ising-like models, in practice requiring to use relatively costly, uncontrollable and inaccurate Monte-Carlo methods. There is discussed analytical approach for e.g. $width\times \infty$ approximation of lattice, also exploiting Hammersley-Clifford theorem to generate random Gibbs/Markov field through scanning line-by-line using local statistical model as in lossless image compression. While its conditional distributions could be found with Monte-Carlo methods, there is discussed use of Maximal Entropy Random Walk (MERW) to calculate them from approximation of lattice as infinite in one direction and finite in the remaining. Specifically, in the finite directions there is built alphabet of all patterns, then transition matrix containing energy for all pairs of such patterns is built, from its dominant eigenvector getting probability distribution of pairs of patterns in Boltzmann distribution of their infinite sequences, which can be translated into local statistical model for line-by-line scan. Such inexpensive models, requiring seconds on a laptop for attached implementation and directly providing probability distributions of patterns, were tested for mean entropy and energy per node, getting maximal $\approx 0.02$ error from analytical solution near critical point, which quickly improves to extremely accurate e.g. $\approx 10^{-10}$ error for $J\approx 0.2$.
Trajectory Forecasts in Unknown Environments Conditioned on Grid-Based Plans
Venue: arXiv cs.CV 2021
Year: 2021

We address the problem of forecasting pedestrian and vehicle trajectories in unknown environments, conditioned on their past motion and scene structure. Trajectory forecasting is a challenging problem due to the large variation in scene structure and the multimodal distribution of future trajectories. Unlike prior approaches that directly learn one-to-many mappings from observed context to multiple future trajectories, we propose to condition trajectory forecasts on plans sampled from a grid based policy learned using maximum entropy inverse reinforcement learning (MaxEnt IRL). We reformulate MaxEnt IRL to allow the policy to jointly infer plausible agent goals, and paths to those goals on a coarse 2-D grid defined over the scene. We propose an attention based trajectory generator that generates continuous valued future trajectories conditioned on state sequences sampled from the MaxEnt policy. Quantitative and qualitative evaluation on the publicly available Stanford drone and NuScenes datasets shows that our model generates trajectories that are diverse, representing the multimodal predictive distribution, and precise, conforming to the underlying scene structure over long prediction horizons.
On Supergraphs Satisfying CMSO Properties
Venue: arXiv cs.LO 2021
Year: 2021

Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function $f$, there is an algorithm $\mathfrak{A}$ that takes as input a CMSO sentence $φ$, a positive integer $t$, and a connected graph $G$ of maximum degree at most $Δ$, and determines, in time $f(|φ|,t)\cdot 2^{O(Δ\cdot t)}\cdot |G|^{O(t)}$, whether $G$ has a supergraph $G'$ of treewidth at most $t$ such that $G'\models φ$. The algorithmic metatheorem described above sheds new light on certain unresolved questions within the framework of graph completion algorithms. In particular, using this metatheorem, we provide an explicit algorithm that determines, in time $f(d)\cdot 2^{O(Δ\cdot d)}\cdot |G|^{O(d)}$, whether a connected graph of maximum degree $Δ$ has a planar supergraph of diameter at most $d$. Additionally, we show that for each fixed $k$, the problem of determining whether $G$ has an $k$-outerplanar supergraph of diameter at most $d$ is strongly uniformly fixed parameter tractable with respect to the parameter $d$. This result can be generalized in two directions. First, the diameter parameter can be replaced by any contraction-closed effectively CMSO-definable parameter $\mathbf{p}$. Examples of such parameters are vertex-cover number, dominating number, and many other contraction-bidimensional parameters. In the second direction, the planarity requirement can be relaxed to bounded genus, and more generally, to bounded local treewidth.
High-parallelism Inception-like Spiking Neural Networks for Unsupervised Feature Learning
Venue: arXiv cs.NE 2021
Year: 2021

Spiking Neural Networks (SNNs) are brain-inspired, event-driven machine learning algorithms that have been widely recognized in producing ultra-high-energy-efficient hardware. Among existing SNNs, unsupervised SNNs based on synaptic plasticity, especially Spike-Timing-Dependent Plasticity (STDP), are considered to have great potential in imitating the learning process of the biological brain. Nevertheless, the existing STDP-based SNNs have limitations in constrained learning capability and/or slow learning speed. Most STDP-based SNNs adopted a slow-learning Fully-Connected (FC) architecture and used a sub-optimal vote-based scheme for spike decoding. In this paper, we overcome these limitations with: 1) a design of high-parallelism network architecture, inspired by the Inception module in Artificial Neural Networks (ANNs); 2) use of a Vote-for-All (VFA) decoding layer as a replacement to the standard vote-based spike decoding scheme, to reduce the information loss in spike decoding and, 3) a proposed adaptive repolarization (resetting) mechanism that accelerates SNNs' learning by enhancing spiking activities. Our experimental results on two established benchmark datasets (MNIST/EMNIST) show that our network architecture resulted in superior performance compared to the widely used FC architecture and a more advanced Locally-Connected (LC) architecture, and that our SNN achieved competitive results with state-of-the-art unsupervised SNNs (95.64%/80.11% accuracy on the MNIST/EMNISE dataset) while having superior learning efficiency and robustness against hardware damage. Our SNN achieved great classification accuracy with only hundreds of training iterations, and random destruction of large numbers of synapses or neurons only led to negligible performance degradation.
VC-dimensions of nondeterministic finite automata for words of equal length
Venue: arXiv cs.FL 2021
Year: 2021

Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$ denote the set of words of length $n$. We give a quadratic lower bound on the VC dimension of \[ NFA_2(q)\cap B_n = \{L\cap B_n \mid L \in NFA_2(q)\} \] as a function of $q$. Next, the work of Gruber and Holzer (2007) gives an upper bound for the nondeterministic state complexity of finite languages contained in $B_n$, which we strengthen using our methods. Finally, we give some theoretical and experimental results on the dependence on $n$ of the VC dimension and testing dimension of $NFA_2(q)\cap B_n$.