OpenRaiser/Intern-Atlas huggingface dataset:
Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
Venue: arXiv cs.LG 2021
Year: 2021

Episodic reinforcement learning and contextual bandits are two widely studied sequential decision-making problems. Episodic reinforcement learning generalizes contextual bandits and is often perceived to be more difficult due to long planning horizon and unknown state-dependent transitions. The current paper shows that the long planning horizon and the unknown state-dependent transitions (at most) pose little additional difficulty on sample complexity. We consider the episodic reinforcement learning with $S$ states, $A$ actions, planning horizon $H$, total reward bounded by $1$, and the agent plays for $K$ episodes. We propose a new algorithm, \textbf{M}onotonic \textbf{V}alue \textbf{P}ropagation (MVP), which relies on a new Bernstein-type bonus. Compared to existing bonus constructions, the new bonus is tighter since it is based on a well-designed monotonic value function. In particular, the \emph{constants} in the bonus should be subtly setting to ensure optimism and monotonicity. We show MVP enjoys an $O\left(\left(\sqrt{SAK} + S^2A\right) \poly\log \left(SAHK\right)\right)$ regret, approaching the $Ω\left(\sqrt{SAK}\right)$ lower bound of \emph{contextual bandits} up to logarithmic terms. Notably, this result 1) \emph{exponentially} improves the state-of-the-art polynomial-time algorithms by Dann et al. [2019] and Zanette et al. [2019] in terms of the dependency on $H$, and 2) \emph{exponentially} improves the running time in [Wang et al. 2020] and significantly improves the dependency on $S$, $A$ and $K$ in sample complexity.
Apollo: An Adaptive Parameter-wise Diagonal Quasi-Newton Method for Nonconvex Stochastic Optimization
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we introduce Apollo, a quasi-Newton method for nonconvex stochastic optimization, which dynamically incorporates the curvature of the loss function by approximating the Hessian via a diagonal matrix. Importantly, the update and storage of the diagonal approximation of Hessian is as efficient as adaptive first-order optimization methods with linear complexity for both time and memory. To handle nonconvexity, we replace the Hessian with its rectified absolute value, which is guaranteed to be positive-definite. Experiments on three tasks of vision and language show that Apollo achieves significant improvements over other stochastic optimization methods, including SGD and variants of Adam, in term of both convergence speed and generalization performance. The implementation of the algorithm is available at https://github.com/XuezheMax/apollo.
GraphITE: Estimating Individual Effects of Graph-structured Treatments
Venue: arXiv cs.LG 2021
Year: 2021

Outcome estimation of treatments for target individuals is an important foundation for decision making based on causal relations. Most existing outcome estimation methods deal with binary or multiple-choice treatments; however, in some applications, the number of treatments can be significantly large, while the treatments themselves have rich information. In this study, we considered one important instance of such cases: the outcome estimation problem of graph-structured treatments such as drugs. Owing to the large number of possible treatments, the counterfactual nature of observational data that appears in conventional treatment effect estimation becomes more of a concern for this problem. Our proposed method, GraphITE (pronounced "graphite") learns the representations of graph-structured treatments using graph neural networks while mitigating observation biases using Hilbert-Schmidt Independence Criterion regularization, which increases the independence of the representations of the targets and treatments. Experiments on two real-world datasets show that GraphITE outperforms baselines, especially in cases with a large number of treatments.
Compact 200 line MATLAB code for inverse design in photonics by topology optimization: tutorial
Venue: arXiv cs.MS 2021
Year: 2021

We provide a compact 200 line MATLAB code demonstrating how topology optimization (TopOpt) as an inverse design tool may be used in photonics, targeting the design of two-dimensional dielectric metalenses and a metallic reflector as examples. The physics model is solved using the finite element method, and the code utilizes MATLAB's fmincon algorithm to solve the optimization problem. In addition to presenting the code itself, we briefly discuss a number of extensions and provide the code required to implement some of these. Finally, we demonstrate the superiority of using a gradient-based method compared to a genetic-algorithm-based method (using MATLAB's ga algorithm) for solving inverse design problems in photonics. The MATLAB software is freely available in the paper and may be downloaded from https://www.topopt.mek.dtu.dk.
Multi-hop Attention Graph Neural Network
Venue: arXiv cs.LG 2021
Year: 2021

Self-attention mechanism in graph neural networks (GNNs) led to state-of-the-art performance on many graph representation learning tasks. Currently, at every layer, attention is computed between connected pairs of nodes and depends solely on the representation of the two nodes. However, such attention mechanism does not account for nodes that are not directly connected but provide important network context. Here we propose Multi-hop Attention Graph Neural Network (MAGNA), a principled way to incorporate multi-hop context information into every layer of attention computation. MAGNA diffuses the attention scores across the network, which increases the receptive field for every layer of the GNN. Unlike previous approaches, MAGNA uses a diffusion prior on attention values, to efficiently account for all paths between the pair of disconnected nodes. We demonstrate in theory and experiments that MAGNA captures large-scale structural information in every layer, and has a low-pass effect that eliminates noisy high-frequency information from graph data. Experimental results on node classification as well as the knowledge graph completion benchmarks show that MAGNA achieves state-of-the-art results: MAGNA achieves up to 5.7 percent relative error reduction over the previous state-of-the-art on Cora, Citeseer, and Pubmed. MAGNA also obtains the best performance on a large-scale Open Graph Benchmark dataset. On knowledge graph completion MAGNA advances state-of-the-art on WN18RR and FB15k-237 across four different performance metrics.
Explainable Deep Reinforcement Learning for UAV Autonomous Navigation
Venue: arXiv cs.RO 2021
Year: 2021

Autonomous navigation in unknown complex environment is still a hard problem, especially for small Unmanned Aerial Vehicles (UAVs) with limited computation resources. In this paper, a neural network-based reactive controller is proposed for a quadrotor to fly autonomously in unknown outdoor environment. The navigation controller makes use of only current sensor data to generate the control signal without any optimization or configuration space searching, which reduces both memory and computation requirement. The navigation problem is modelled as a Markov Decision Process (MDP) and solved using deep reinforcement learning (DRL) method. Specifically, to get better understanding of the trained network, some model explanation methods are proposed. Based on the feature attribution, each decision making result during flight is explained using both visual and texture explanation. Moreover, some global analysis are also provided for experts to evaluate and improve the trained neural network. The simulation results illustrated the proposed method can make useful and reasonable explanation for the trained model, which is beneficial for both non-expert users and controller designer. Finally, the real world tests shown the proposed controller can navigate the quadrotor to goal position successfully and the reactive controller performs much faster than some conventional approach under the same computation resource.
Uncovering Feature Interdependencies in High-Noise Environments with Stepwise Lookahead Decision Forests
Venue: arXiv cs.LG 2021
Year: 2021

Conventionally, random forests are built from "greedy" decision trees which each consider only one split at a time during their construction. The sub-optimality of greedy implementation has been well-known, yet mainstream adoption of more sophisticated tree building algorithms has been lacking. We examine under what circumstances an implementation of less greedy decision trees actually yields outperformance. To this end, a "stepwise lookahead" variation of the random forest algorithm is presented for its ability to better uncover binary feature interdependencies. In contrast to the greedy approach, the decision trees included in this random forest algorithm, each simultaneously consider three split nodes in tiers of depth two. It is demonstrated on synthetic data and financial price time series that the lookahead version significantly outperforms the greedy one when (a) certain non-linear relationships between feature-pairs are present and (b) if the signal-to-noise ratio is particularly low. A long-short trading strategy for copper futures is then backtested by training both greedy and stepwise lookahead random forests to predict the signs of daily price returns. The resulting superior performance of the lookahead algorithm is at least partially explained by the presence of "XOR-like" relationships between long-term and short-term technical indicators. More generally, across all examined datasets, when no such relationships between features are present, performance across random forests is similar. Given its enhanced ability to understand the feature-interdependencies present in complex systems, this lookahead variation is a useful extension to the toolkit of data scientists, in particular for financial machine learning, where conditions (a) and (b) are typically met.
Dissected 3D CNNs: Temporal Skip Connections for Efficient Online Video Processing
Venue: arXiv cs.CV 2021
Year: 2021

Convolutional Neural Networks with 3D kernels (3D-CNNs) currently achieve state-of-the-art results in video recognition tasks due to their supremacy in extracting spatiotemporal features within video frames. There have been many successful 3D-CNN architectures surpassing the state-of-the-art results successively. However, nearly all of them are designed to operate offline creating several serious handicaps during online operation. Firstly, conventional 3D-CNNs are not dynamic since their output features represent the complete input clip instead of the most recent frame in the clip. Secondly, they are not temporal resolution-preserving due to their inherent temporal downsampling. Lastly, 3D-CNNs are constrained to be used with fixed temporal input size limiting their flexibility. In order to address these drawbacks, we propose dissected 3D-CNNs, where the intermediate volumes of the network are dissected and propagated over depth (time) dimension for future calculations, substantially reducing the number of computations at online operation. For action classification, the dissected version of ResNet models performs 77-90% fewer computations at online operation while achieving ~5% better classification accuracy on the Kinetics-600 dataset than conventional 3D-ResNet models. Moreover, the advantages of dissected 3D-CNNs are demonstrated by deploying our approach onto several vision tasks, which consistently improved the performance.
Efficient texture-aware multi-GAN for image inpainting
Venue: arXiv cs.CV 2021
Year: 2021

Recent GAN-based (Generative adversarial networks) inpainting methods show remarkable improvements and generate plausible images using multi-stage networks or Contextual Attention Modules (CAM). However, these techniques increase the model complexity limiting their application in low-resource environments. Furthermore, they fail in generating high-resolution images with realistic texture details due to the GAN stability problem. Motivated by these observations, we propose a multi-GAN architecture improving both the performance and rendering efficiency. Our training schema optimizes the parameters of four progressive efficient generators and discriminators in an end-to-end manner. Filling in low-resolution images is less challenging for GANs due to the small dimensional space. Meanwhile, it guides higher resolution generators to learn the global structure consistency of the image. To constrain the inpainting task and ensure fine-grained textures, we adopt an LBP-based loss function to minimize the difference between the generated and the ground truth textures. We conduct our experiments on Places2 and CelebHQ datasets. Qualitative and quantitative results show that the proposed method not only performs favorably against state-of-the-art algorithms but also speeds up the inference time.
Channel Estimation for Reconfigurable Intelligent Surface-Assisted Wireless Communications Considering Doppler Effect
Venue: arXiv cs.IT 2021
Year: 2021

In wireless systems aided by reconfigurable intelligent surfaces (RISs), channel state information plays a pivotal role in achieving the performance gain of RISs. Mobility renders accurate channel estimation (CE) more challenging due to the Doppler effect. In this letter, we propose two practical wideband CE schemes incorporating Doppler shift adjustment (DSA) for multi-path and single-path propagation environments, respectively, for RIS-assisted communication with passive reflecting elements. For the multi-path scenario, ordinary CE is first executed assuming quasi-static channels, followed by DSA realized via joint RIS reflection pattern selection and transformations between frequency and time domains. The proposed CE necessitates only one more symbol incurring negligible extra overhead compared with the number of symbols required for the original CE. For the single-path case which is especially applicable to millimeter-wave and terahertz systems, a novel low-complexity CE method is devised capitalizing on the form of the array factors at the RIS. Simulation results demonstrate that the proposed algorithms yield high CE accuracy and achievable rate with low complexity, and outperform representative benchmark schemes.
Opinion dynamics on tie-decay networks
Venue: arXiv cs.SI 2021
Year: 2021

In social networks, interaction patterns typically change over time. We study opinion dynamics on tie-decay networks in which tie strength increases instantaneously when there is an interaction and decays exponentially between interactions. Specifically, we formulate continuous-time Laplacian dynamics and a discrete-time DeGroot model of opinion dynamics on these tie-decay networks, and we carry out numerical computations for the continuous-time Laplacian dynamics. We examine the speed of convergence by studying the spectral gaps of combinatorial Laplacian matrices of tie-decay networks. First, we compare the spectral gaps of the Laplacian matrices of tie-decay networks that we construct from empirical data with the spectral gaps for corresponding randomized and aggregate networks. We find that the spectral gaps for the empirical networks tend to be smaller than those for the randomized and aggregate networks. Second, we study the spectral gap as a function of the tie-decay rate and time. Intuitively, we expect small tie-decay rates to lead to fast convergence because the influence of each interaction between two nodes lasts longer for smaller decay rates. Moreover, as time progresses and more interactions occur, we expect eventual convergence. However, we demonstrate that the spectral gap need not decrease monotonically with respect to the decay rate or increase monotonically with respect to time. Our results highlight the importance of the interplay between the times that edges strengthen and decay in temporal networks.
Workflow Provenance in the Lifecycle of Scientific Machine Learning
Venue: arXiv cs.DB 2021
Year: 2021

Machine Learning (ML) has already fundamentally changed several businesses. More recently, it has also been profoundly impacting the computational science and engineering domains, like geoscience, climate science, and health science. In these domains, users need to perform comprehensive data analyses combining scientific data and ML models to provide for critical requirements, such as reproducibility, model explainability, and experiment data understanding. However, scientific ML is multidisciplinary, heterogeneous, and affected by the physical constraints of the domain, making such analyses even more challenging. In this work, we leverage workflow provenance techniques to build a holistic view to support the lifecycle of scientific ML. We contribute with (i) characterization of the lifecycle and taxonomy for data analyses; (ii) design principles to build this view, with a W3C PROV compliant data representation and a reference system architecture; and (iii) lessons learned after an evaluation in an Oil & Gas case using an HPC cluster with 393 nodes and 946 GPUs. The experiments show that the principles enable queries that integrate domain semantics with ML models while keeping low overhead (<1%), high scalability, and an order of magnitude of query acceleration under certain workloads against without our representation.
Linking Threat Tactics, Techniques, and Patterns with Defensive Weaknesses, Vulnerabilities and Affected Platform Configurations for Cyber Hunting
Venue: arXiv cs.CR 2021
Year: 2021

Many public sources of cyber threat and vulnerability information exist to help defend cyber systems. This paper links MITRE's ATT&CK MATRIX of Tactics and Techniques, NIST's Common Weakness Enumerations (CWE), Common Vulnerabilities and Exposures (CVE), and Common Attack Pattern Enumeration and Classification list (CAPEC), to gain further insight from alerts, threats and vulnerabilities. We preserve all entries and relations of the sources, while enabling bi-directional, relational path tracing within an aggregate data graph called BRON. In one example, we use BRON to enhance the information derived from a list of the top 10 most frequently exploited CVEs. We identify attack patterns, tactics, and techniques that exploit these CVEs and also uncover a disparity in how much linked information exists for each of these CVEs. This prompts us to further inventory BRON's collection of sources to provide a view of the extent and range of the coverage and blind spots of public data sources.
Including Everyone, Everywhere: Understanding Opportunities and Challenges of Geographic Gender-Inclusion in OSS
Venue: arXiv cs.CY 2021
Year: 2021

The gender gap is a significant concern facing the software industry as the development becomes more geographically distributed. Widely shared reports indicate that gender differences may be specific to each region. However, how complete can these reports be with little to no research reflective of the Open Source Software (OSS) process and communities software is now commonly developed in? Our study presents a multi-region geographical analysis of gender inclusion on GitHub. This mixed-methods approach includes quantitatively investigating differences in gender inclusion in projects across geographic regions and investigate these trends over time using data from contributions to 21,456 project repositories. We also qualitatively understand the unique experiences of developers contributing to these projects through a survey that is strategically targeted to developers in various regions worldwide. Our findings indicate that gender diversity is low across all parts of the world, with no substantial difference across regions. However, there has been statistically significant improvement in diversity worldwide since 2014, with certain regions such as Africa improving at faster pace. We also find that most motivations and barriers to contributions (e.g., lack of resources to contribute and poor working environment) were shared across regions, however, some insightful differences, such as how to make projects more inclusive, did arise. From these findings, we derive and present implications for tools that can foster inclusion in open source software communities and empower contributions from everyone, everywhere.
Neural Thompson Sampling
Venue: arXiv cs.LG 2021
Year: 2021

Thompson Sampling (TS) is one of the most effective algorithms for solving contextual multi-armed bandit problems. In this paper, we propose a new algorithm, called Neural Thompson Sampling, which adapts deep neural networks for both exploration and exploitation. At the core of our algorithm is a novel posterior distribution of the reward, where its mean is the neural network approximator, and its variance is built upon the neural tangent features of the corresponding neural network. We prove that, provided the underlying reward function is bounded, the proposed algorithm is guaranteed to achieve a cumulative regret of $\mathcal{O}(T^{1/2})$, which matches the regret of other contextual bandit algorithms in terms of total round number $T$. Experimental comparisons with other benchmark bandit algorithms on various data sets corroborate our theory.
Rotated Ring, Radial and Depth Wise Separable Radial Convolutions
Venue: arXiv cs.CV 2021
Year: 2021

Simple image rotations significantly reduce the accuracy of deep neural networks. Moreover, training with all possible rotations increases the data set, which also increases the training duration. In this work, we address trainable rotation invariant convolutions as well as the construction of nets, since fully connected layers can only be rotation invariant with a one-dimensional input. On the one hand, we show that our approach is rotationally invariant for different models and on different public data sets. We also discuss the influence of purely rotational invariant features on accuracy. The rotationally adaptive convolution models presented in this work are more computationally intensive than normal convolution models. Therefore, we also present a depth wise separable approach with radial convolution. Link to CUDA code https://atreus.informatik.uni-tuebingen.de/seafile/d/8e2ab8c3fdd444e1a135/
Are Artificial Dendrites useful in NeuroEvolution?
Venue: arXiv cs.NE 2021
Year: 2021

The significant role of dendritic processing within neuronal networks has become increasingly clear. This letter explores the effects of including a simple dendrite-inspired mechanism into neuroevolution. The phenomenon of separate dendrite activation thresholds on connections is allowed to emerge under an evolutionary process. It is shown how such processing can be positively selected for, particularly for connections between the hidden and output layer, and increases performance.