OpenRaiser/Intern-Atlas huggingface dataset:
Generalization in Transfer Learning
Venue: arXiv cs.LG 2021
Year: 2021

Agents trained with deep reinforcement learning algorithms are capable of performing highly complex tasks including locomotion in continuous environments. We investigate transferring the learning acquired in one task to a set of previously unseen tasks. Generalization and overfitting in deep reinforcement learning are not commonly addressed in current transfer learning research. Conducting a comparative analysis without an intermediate regularization step results in underperforming benchmarks and inaccurate algorithm comparisons due to rudimentary assessments. In this study, we propose regularization techniques in deep reinforcement learning for continuous control through the application of sample elimination, early stopping and maximum entropy regularized adversarial learning. First, the importance of the inclusion of training iteration number to the hyperparameters in deep transfer reinforcement learning will be discussed. Because source task performance is not indicative of the generalization capacity of the algorithm, we start by acknowledging the training iteration number as a hyperparameter. In line with this, we introduce an additional step of resorting to earlier snapshots of policy parameters to prevent overfitting to the source task. Then, to generate robust policies, we discard the samples that lead to overfitting via a method we call strict clipping. Furthermore, we increase the generalization capacity in widely used transfer learning benchmarks by using maximum entropy regularization, different critic methods, and curriculum learning in an adversarial setup. Subsequently, we propose maximum entropy adversarial reinforcement learning to increase the domain randomization. Finally, we evaluate the robustness of these methods on simulated robots in target environments where the morphology of the robot, gravity, and tangential friction coefficient of the environment are altered.
DeepObfusCode: Source Code Obfuscation Through Sequence-to-Sequence Networks
Venue: arXiv cs.CR 2021
Year: 2021

The paper explores a novel methodology in source code obfuscation through the application of text-based recurrent neural network (RNN) encoder-decoder models in ciphertext generation and key generation. Sequence-to-sequence models are incorporated into the model architecture to generate obfuscated code, generate the deobfuscation key, and live execution. Quantitative benchmark comparison to existing obfuscation methods indicate significant improvement in stealth and execution cost for the proposed solution, and experiments regarding the model's properties yield positive results regarding its character variation, dissimilarity to the original codebase, and consistent length of obfuscated code.
Coexistence of Age and Throughput Optimizing Networks: A Spectrum Sharing Game
Venue: arXiv cs.GT 2021
Year: 2021

We investigate the coexistence of an age optimizing network (AON) and a throughput optimizing network (TON) that share a common spectrum band. We consider two modes of long run coexistence: (a) networks compete with each other for spectrum access, causing them to interfere and (b) networks cooperate to achieve non-interfering access. To model competition, we define a non-cooperative stage game parameterized by the average age of the AON at the beginning of the stage, derive its mixed strategy Nash equilibrium (MSNE), and analyze the evolution of age and throughput over an infinitely repeated game in which each network plays the MSNE at every stage. Cooperation uses a coordination device that performs a coin toss during each stage to select the network that must access the medium. Networks use the grim trigger punishment strategy, reverting to playing the MSNE every stage forever if the other disobeys the device. We determine if there exists a subgame perfect equilibrium, i.e., the networks obey the device forever as they find cooperation beneficial. We show that networks choose to cooperate only when they consist of a sufficiently small number of nodes, otherwise they prefer to disobey the device and compete.
Fast explicit dynamics finite element algorithm for transient heat transfer
Venue: arXiv cs.CE 2021
Year: 2021

This paper presents a novel methodology for fast simulation and analysis of transient heat transfer. The proposed methodology is suitable for real-time applications owing to (i) establishing the solution method from the viewpoint of computationally efficient explicit dynamics, (ii) proposing an element-level thermal load computation to eliminate the need for assembling global thermal stiffness, leading to (iii) an explicit formulation of nodal temperature computation to eliminate the need for iterations anywhere in the algorithm, (iv) pre-computing the constant matrices and simulation parameters to facilitate online calculation, and (v) utilising computationally efficient finite elements to efficiently obtain thermal responses in the spatial domain, all of which lead to a significant reduction in computation time for fast run-time simulation. The proposed fast explicit dynamics finite element algorithm (FED-FEM) employs nonlinear thermal material properties, such as temperature-dependent thermal conductivity and specific heat capacity, and nonlinear thermal boundary conditions, such as heat convection and radiation, to account for nonlinear characteristics of transient heat transfer. Simulations and comparison analyses demonstrate that not only can the proposed methodology handle isotropic, orthotropic, anisotropic and temperature-dependent thermal properties but also satisfy the standard patch tests and achieve good agreement with those of the commercial finite element analysis packages for numerical accuracy, for 3-D heat conduction, convection, radiation, and thermal gradient concentration problems. Furthermore, the proposed FED-FEM algorithm is computationally efficient and only consumes a small computation time, capable of achieving real-time computational performance, leading to a novel methodology suitable for real-time simulation and analysis of transient heat transfer.
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Venue: arXiv cs.DS 2021
Year: 2021

In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph $G$ while edges are inserted and deleted from the graph. The first non-trivial algorithm for this problem was presented by Assadi, Onak, Schieber, and Solomon [STOC 2018] who obtained a deterministic fully dynamic MIS with $O(m^{3/4})$ update time. Later, this was independently improved by Du and Zhang and by Gupta and Khan [arXiv 2018] to $\tilde{O}(m^{2/3})$ update time. Du and Zhang [arXiv 2018] also presented a randomized algorithm against an oblivious adversary with $\tilde{O}(\sqrt{m})$ update time. The current state of art is by Assadi, Onak, Schieber, and Solomon [SODA 2019] who obtained randomized algorithms against oblivious adversary with $\tilde{O}(\sqrt{n})$ and $\tilde{O}(m^{1/3})$ update times. In this paper, we propose a dynamic randomized algorithm against oblivious adversary with expected worst-case update time of $O(\log^4n)$. As a direct corollary, one can apply the black-box reduction from a recent work by Bernstein, Forster, and Henzinger [SODA 2019] to achieve $O(\log^6n)$ worst-case update time with high probability. This is the first dynamic MIS algorithm with very fast update time of poly-log.
Extreme Low Resolution Activity Recognition with Confident Spatial-Temporal Attention Transfer
Venue: arXiv cs.CV 2021
Year: 2021

Activity recognition on extreme low-resolution videos, e.g., a resolution of 12*16 pixels, plays a vital role in far-view surveillance and privacy-preserving multimedia analysis. Low-resolution videos only contain limited information. Given the fact that one same activity may be represented by videos in both high resolution (HR) and extreme low resolution (eLR), it is worth studying to utilize the relevant HR data to improve the eLR activity recognition. In this work, we propose a novel Confident Spatial-Temporal Attention Transfer (CSTAT) for eLR activity recognition. CSTAT can acquire information from HR data by reducing the attention differences with a transfer-learning strategy. Besides, the credibility of the supervisory signal is also taken into consideration for a more confident transferring process. Experimental results on two well-known datasets, i.e., UCF101 and HMDB51, demonstrate that, the proposed method can effectively improve the accuracy of eLR activity recognition and achieve an accuracy of 59.23% on 12*16 videos in HMDB51, a state-of-the-art performance.
Estimating the potential for shared autonomous scooters
Venue: arXiv cs.CY 2021
Year: 2021

Recent technological developments have shown significant potential for transforming urban mobility. Considering first- and last-mile travel and short trips, the rapid adoption of dockless bike-share systems showed the possibility of disruptive change, while simultaneously presenting new challenges, such as fleet management or the use of public spaces. In this paper, we evaluate the operational characteristics of a new class of shared vehicles that are being actively developed in the industry: scooters with self-repositioning capabilities. We do this by adapting the methodology of shareability networks to a large-scale dataset of dockless bike-share usage, giving us estimates of ideal fleet size under varying assumptions of fleet operations. We show that the availability of self-repositioning capabilities can help achieve up to 10 times higher utilization of vehicles than possible in current bike-share systems. We show that actual benefits will highly depend on the availability of dedicated infrastructure, a key issue for scooter and bicycle use. Based on our results, we envision that technological advances can present an opportunity to rethink urban infrastructures and how transportation can be effectively organized in cities.
A Bayesian Approach to Direct and Inverse Abstract Argumentation Problems
Venue: arXiv cs.AI 2021
Year: 2021

This paper studies a fundamental mechanism of how to detect a conflict between arguments given sentiments regarding acceptability of the arguments. We introduce a concept of the inverse problem of the abstract argumentation to tackle the problem. Given noisy sets of acceptable arguments, it aims to find attack relations explaining the sets well in terms of acceptability semantics. It is the inverse of the direct problem corresponding to the traditional problem of the abstract argumentation that focuses on finding sets of acceptable arguments in terms of the semantics given an attack relation between the arguments. We give a probabilistic model handling both of the problems in a way that is faithful to the acceptability semantics. From a theoretical point of view, we show that a solution to both the direct and inverse problems is a special case of the probabilistic inference on the model. We discuss that the model provides a natural extension of the semantics to cope with uncertain attack relations distributed probabilistically. From en empirical point of view, we argue that it reasonably predicts individuals sentiments regarding acceptability of arguments. This paper contributes to lay the foundation for making acceptability semantics data-driven and to provide a way to tackle the knowledge acquisition bottleneck.
Rank and border rank of Kronecker powers of tensors and Strassen's laser method
Venue: arXiv cs.CC 2021
Year: 2021

We prove that the border rank of the Kronecker square of the little Coppersmith-Winograd tensor $T_{cw,q}$ is the square of its border rank for $q > 2$ and that the border rank of its Kronecker cube is the cube of its border rank for $q > 4$. This answers questions raised implicitly in [Coppersmith-Winograd, 1990] and explicitly in [Bläser, 2013] and rules out the possibility of proving new upper bounds on the exponent of matrix multiplication using the square or cube of a little Coppersmith-Winograd tensor in this range. In the positive direction, we enlarge the list of explicit tensors potentially useful for Strassen's laser method, introducing a skew-symmetric version of the Coppersmith-Winograd tensor, $T_{skewcw,q}$. For $q = 2$, the Kronecker square of this tensor coincides with the $3\times 3$ determinant polynomial, $\det_3 \in \mathbb{C}^9\otimes \mathbb{C}^9\otimes \mathbb{C}^9$, regarded as a tensor. We show that this tensor could potentially be used to show that the exponent of matrix multiplication is two. We determine new upper bounds for the (Waring) rank and the (Waring) border rank of $\det_3$, exhibiting a strict submultiplicative behaviour for $T_{skewcw,2}$ which is promising for the laser method. We establish general results regarding border ranks of Kronecker powers of tensors, and make a detailed study of Kronecker squares of tensors in $\mathbb{C}^3\otimes \mathbb{C}^3\otimes \mathbb{C}^3$.
Model Based Planning with Energy Based Models
Venue: arXiv cs.LG 2021
Year: 2021

Model-based planning holds great promise for improving both sample efficiency and generalization in reinforcement learning (RL). We show that energy-based models (EBMs) are a promising class of models to use for model-based planning. EBMs naturally support inference of intermediate states given start and goal state distributions. We provide an online algorithm to train EBMs while interacting with the environment, and show that EBMs allow for significantly better online learning than corresponding feed-forward networks. We further show that EBMs support maximum entropy state inference and are able to generate diverse state space plans. We show that inference purely in state space - without planning actions - allows for better generalization to previously unseen obstacles in the environment and prevents the planner from exploiting the dynamics model by applying uncharacteristic action sequences. Finally, we show that online EBM training naturally leads to intentionally planned state exploration which performs significantly better than random exploration.
From Monolithic Systems to Microservices: An Assessment Framework
Venue: arXiv cs.SE 2021
Year: 2021

Context. Re-architecting monolithic systems with Microservices-based architecture is a common trend. Various companies are migrating to Microservices for different reasons. However, making such an important decision like re-architecting an entire system must be based on real facts and not only on gut feelings. Objective. The goal of this work is to propose an evidence-based decision support framework for companies that need to migrate to Microservices, based on the analysis of a set of characteristics and metrics they should collect before re-architecting their monolithic system. Method. We designed this study with a mixed-methods approach combining a Systematic Mapping Study with a survey done in the form of interviews with professionals to derive the assessment framework based on Grounded Theory. Results. We identified a set consisting of information and metrics that companies can use to decide whether to migrate to Microservices or not. The proposed assessment framework, based on the aforementioned metrics, could be useful for companies if they need to migrate to Microservices and do not want to run the risk of failing to consider some important information.
Chaitin's Omega and an Algorithmic Phase Transition
Venue: arXiv cs.CC 2021
Year: 2021

We consider the statistical mechanical ensemble of bit string histories that are computed by a universal Turing machine. The role of the energy is played by the program size. We show that this ensemble has a first-order phase transition at a critical temperature, at which the partition function equals Chaitin's halting probability $Ω$. This phase transition has curious properties: the free energy is continuous near the critical temperature, but almost jumps: it converges more slowly to its finite critical value than any computable function. At the critical temperature, the average size of the bit strings diverges. We define a non-universal Turing machine that approximates this behavior of the partition function in a computable way by a super-logarithmic singularity, and discuss its thermodynamic properties. We also discuss analogies and differences between Chaitin's Omega and the partition functions of a quantum mechanical particle, a spin model, random surfaces, and quantum Turing machines. For universal Turing machines, we conjecture that the ensemble of bit string histories at the critical temperature has a continuum formulation in terms of a string theory.
Bayesian Optimization for Iterative Learning
Venue: arXiv cs.LG 2021
Year: 2021

The performance of deep (reinforcement) learning systems crucially depends on the choice of hyperparameters. Their tuning is notoriously expensive, typically requiring an iterative training process to run for numerous steps to convergence. Traditional tuning algorithms only consider the final performance of hyperparameters acquired after many expensive iterations and ignore intermediate information from earlier training steps. In this paper, we present a Bayesian optimization (BO) approach which exploits the iterative structure of learning algorithms for efficient hyperparameter tuning. We propose to learn an evaluation function compressing learning progress at any stage of the training process into a single numeric score according to both training success and stability. Our BO framework is then balancing the benefit of assessing a hyperparameter setting over additional training steps against their computation cost. We further increase model efficiency by selectively including scores from different training steps for any evaluated hyperparameter set. We demonstrate the efficiency of our algorithm by tuning hyperparameters for the training of deep reinforcement learning agents and convolutional neural networks. Our algorithm outperforms all existing baselines in identifying optimal hyperparameters in minimal time.
diffGrad: An Optimization Method for Convolutional Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Stochastic Gradient Decent (SGD) is one of the core techniques behind the success of deep neural networks. The gradient provides information on the direction in which a function has the steepest rate of change. The main problem with basic SGD is to change by equal sized steps for all parameters, irrespective of gradient behavior. Hence, an efficient way of deep network optimization is to make adaptive step sizes for each parameter. Recently, several attempts have been made to improve gradient descent methods such as AdaGrad, AdaDelta, RMSProp and Adam. These methods rely on the square roots of exponential moving averages of squared past gradients. Thus, these methods do not take advantage of local change in gradients. In this paper, a novel optimizer is proposed based on the difference between the present and the immediate past gradient (i.e., diffGrad). In the proposed diffGrad optimization technique, the step size is adjusted for each parameter in such a way that it should have a larger step size for faster gradient changing parameters and a lower step size for lower gradient changing parameters. The convergence analysis is done using the regret bound approach of online learning framework. Rigorous analysis is made in this paper over three synthetic complex non-convex functions. The image categorization experiments are also conducted over the CIFAR10 and CIFAR100 datasets to observe the performance of diffGrad with respect to the state-of-the-art optimizers such as SGDM, AdaGrad, AdaDelta, RMSProp, AMSGrad, and Adam. The residual unit (ResNet) based Convolutional Neural Networks (CNN) architecture is used in the experiments. The experiments show that diffGrad outperforms other optimizers. Also, we show that diffGrad performs uniformly well for training CNN using different activation functions. The source code is made publicly available at https://github.com/shivram1987/diffGrad.
Learning to Seek: Autonomous Source Seeking with Deep Reinforcement Learning Onboard a Nano Drone Microcontroller
Venue: arXiv cs.RO 2021
Year: 2021

We present fully autonomous source seeking onboard a highly constrained nano quadcopter, by contributing application-specific system and observation feature design to enable inference of a deep-RL policy onboard a nano quadcopter. Our deep-RL algorithm finds a high-performance solution to a challenging problem, even in presence of high noise levels and generalizes across real and simulation environments with different obstacle configurations. We verify our approach with simulation and in-field testing on a Bitcraze CrazyFlie using only the cheap and ubiquitous Cortex-M4 microcontroller unit. The results show that by end-to-end application-specific system design, our contribution consumes almost three times less additional power, as compared to competing learning-based navigation approach onboard a nano quadcopter. Thanks to our observation space, which we carefully design within the resource constraints, our solution achieves a 94% success rate in cluttered and randomized test environments, as compared to the previously achieved 80%. We also compare our strategy to a simple finite state machine (FSM), geared towards efficient exploration, and demonstrate that our policy is more robust and resilient at obstacle avoidance as well as up to 70% more efficient in source seeking. To this end, we contribute a cheap and lightweight end-to-end tiny robot learning (tinyRL) solution, running onboard a nano quadcopter, that proves to be robust and efficient in a challenging task using limited sensory input.
New results on quasi-subfield polynomials
Venue: arXiv cs.CR 2021
Year: 2021

Quasi-subfield polynomials were introduced by Huang et al. together with a new algorithm to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) over finite fields of small characteristic. In this paper we provide both new quasi-subfield polynomial families and a new theorem limiting their existence. Our results do not allow to derive any speedup for the new ECDLP algorithm compared to previous approaches.
Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems
Venue: arXiv cs.LG 2021
Year: 2021

Embedding representations power machine intelligence in many applications, including recommendation systems, but they are space intensive -- potentially occupying hundreds of gigabytes in large-scale settings. To help manage this outsized memory consumption, we explore mixed dimension embeddings, an embedding layer architecture in which a particular embedding vector's dimension scales with its query frequency. Through theoretical analysis and systematic experiments, we demonstrate that using mixed dimensions can drastically reduce the memory usage, while maintaining and even improving the ML performance. Empirically, we show that the proposed mixed dimension layers improve accuracy by 0.1% using half as many parameters or maintain it using 16X fewer parameters for click-through rate prediction task on the Criteo Kaggle dataset.