OpenRaiser/Intern-Atlas huggingface dataset:
Performance of Large Aperture UCCA Arrays in a 5G User Dense Network
Venue: arXiv cs.IT 2022
Year: 2022

The transmitted signals in the fifth generation (5G) wireless networks suffer from significant path loss due to the use of higher frequencies in Sub-6 GHz and millimeter-wave (mmWave) bands. Inter-user interference in an ultra-dense network offers additional challenges to provide a high data rate. Therefore, it is desirable to generate narrow beams to extend the coverage of a 5G network by increasing antenna gain and improve its capacity by reducing the inter-user interference. This fact leads us to address the use of large aperture uniform concentric circular antenna (UCCA) arrays for 5G beamforming in massive multiple-input-multiple-output (MIMO) technology. Our analysis demonstrates that a UCCA with a larger antenna element spacing is capable of generating a significantly narrower beam with a moderate side-lobe level than a rectangular planar antenna (RPA) array while operating with the same number of antenna elements. This capability of the UCCA is analyzed to discover the performance gain of a 5G network.
Efficient Analog CAM Design
Venue: arXiv cs.AR 2022
Year: 2022

Content Addressable Memories (CAMs) are considered a key-enabler for in-memory computing (IMC). IMC shows order of magnitude improvement in energy efficiency and throughput compared to traditional computing techniques. Recently, analog CAMs (aCAMs) were proposed as a means to improve storage density and energy efficiency. In this work, we propose two new aCAM cells to improve data encoding and robustness as compared to existing aCAM cells. We propose a methodology to choose the margin and interval width for data encoding. In addition, we perform a comprehensive comparison against prior work in terms of the number of intervals, noise sensitivity, dynamic range, energy, latency, area, and probability of failure.
Linear Run Time of Persistent Homology Computation with GPU Parallelization
Venue: arXiv cs.DC 2022
Year: 2022

Persistent homology is a crucial invariant that is used in many areas to understand data. The $O(N^4)$ run time is a hindrance to its use on most large datasets. We give a parallelization method to utilize multi-core machines and clusters. We implement the computation of the $0^{th}$ persistent homology with OpenMP parallelization and observe a 1.75 fold performance increase by using 2 threads on a dual core machine. We also benchmark the computation using larger numbers of threads and show that the thread computational overhead decreases performance. With GPU parallelization, we analytically and empirically decrease the run time scaling from $O(N^4)$ to $O(N^3)$ and even $O(N^2)$ where $N$ is the number of data points, for a large enough GPU. Next, we analytically show run time scaling $O(N)$ for an even larger GPU.
Beyond Time Complexity: Data Movement Complexity Analysis for Matrix Multiplication
Venue: arXiv cs.DS 2022
Year: 2022

Data movement is becoming the dominant contributor to the time and energy costs of computation across a wide range of application domains. However, time complexity is inadequate to analyze data movement. This work expands upon Data Movement Distance, a recently proposed framework for memory-aware algorithm analysis, by 1) demonstrating that its assumptions conform with microarchitectural trends, 2) applying it to six variants of matrix multiplication, and 3) showing it to be capable of asymptotically differentiating algorithms with the same time complexity but different memory behavior, as well as locality optimized vs. non-optimized versions of the same algorithm. In doing so, we attempt to bridge theory and practice by combining the operation count analysis used by asymptotic time complexity with per-operation data movement cost resulting from hierarchical memory structure. Additionally, this paper derives the first fully precise, fully analytical form of recursive matrix multiplication's miss ratio curve on LRU caching systems. Our results indicate that the Data Movement Distance framework is a powerful tool going forward for engineers and algorithm designers to understand the algorithmic implications of hierarchical memory.
Structured Pruning is All You Need for Pruning CNNs at Initialization
Venue: arXiv cs.CV 2022
Year: 2022

Pruning is a popular technique for reducing the model size and computational cost of convolutional neural networks (CNNs). However, a slow retraining or fine-tuning procedure is often required to recover the accuracy loss caused by pruning. Recently, a new research direction on weight pruning, pruning-at-initialization (PAI), is proposed to directly prune CNNs before training so that fine-tuning or retraining can be avoided. While PAI has shown promising results in reducing the model size, existing approaches rely on fine-grained weight pruning which requires unstructured sparse matrix computation, making it difficult to achieve real speedup in practice unless the sparsity is very high. This work is the first to show that fine-grained weight pruning is in fact not necessary for PAI. Instead, the layerwise compression ratio is the main critical factor to determine the accuracy of a CNN model pruned at initialization. Based on this key observation, we propose PreCropping, a structured hardware-efficient model compression scheme. PreCropping directly compresses the model at the channel level following the layerwise compression ratio. Compared to weight pruning, the proposed scheme is regular and dense in both storage and computation without sacrificing accuracy. In addition, since PreCropping compresses CNNs at initialization, the computational and memory costs of CNNs are reduced for both training and inference on commodity hardware. We empirically demonstrate our approaches on several modern CNN architectures, including ResNet, ShuffleNet, and MobileNet for both CIFAR-10 and ImageNet.
Target Network and Truncation Overcome The Deadly Triad in $Q$-Learning
Venue: arXiv cs.LG 2022
Year: 2022

$Q$-learning with function approximation is one of the most empirically successful while theoretically mysterious reinforcement learning (RL) algorithms, and was identified in Sutton (1999) as one of the most important theoretical open problems in the RL community. Even in the basic linear function approximation setting, there are well-known divergent examples. In this work, we show that \textit{target network} and \textit{truncation} together are enough to provably stabilize $Q$-learning with linear function approximation, and we establish the finite-sample guarantees. The result implies an $O(ε^{-2})$ sample complexity up to a function approximation error. Moreover, our results do not require strong assumptions or modifying the problem parameters as in existing literature.
Tightly Coupled Optimization-based GPS-Visual-Inertial Odometry with Online Calibration and Initialization
Venue: arXiv cs.RO 2022
Year: 2022

In this paper, we present a tightly coupled optimization-based GPS-Visual-Inertial odometry system to solve the trajectory drift of the visual-inertial odometry especially over long-term runs. Visual reprojection residuals, IMU residuals, and GPS measurement residuals are jointly minimized within a local bundle adjustment, in which we apply GPS measurements and IMU preintegration used for the IMU residuals to formulate a novel GPS residual. To improve the efficiency and robustness of the system, we propose a fast reference frames initialization method and an online calibration method for GPS-IMU extrinsic and time offset. In addition, we further test the performance and convergence of our online calibration method. Experimental results on EuRoC datasets show that our method consistently outperforms other tightly coupled and loosely coupled approaches. Meanwhile, this system has been validated on KAIST datasets, which proves that our system can work well in the case of visual or GPS failure.
EsDNN: Deep Neural Network based Multivariate Workload Prediction Approach in Cloud Environment
Venue: arXiv cs.DC 2022
Year: 2022

Cloud computing has been regarded as a successful paradigm for IT industry by providing benefits for both service providers and customers. In spite of the advantages, cloud computing also suffers from distinct challenges, and one of them is the inefficient resource provisioning for dynamic workloads. Accurate workload predictions for cloud computing can support efficient resource provisioning and avoid resource wastage. However, due to the high-dimensional and high-variable features of cloud workloads, it is difficult to predict the workloads effectively and accurately. The current dominant work for cloud workload prediction is based on regression approaches or recurrent neural networks, which fail to capture the long-term variance of workloads. To address the challenges and overcome the limitations of existing works, we proposed an efficient supervised learning-based Deep Neural Network (esDNN}) approach for cloud workload prediction. Firstly, we utilize a sliding window to convert the multivariate data into supervised learning time series that allow deep learning for processing. Then we apply a revised Gated Recurrent Unit (GRU) to achieve accurate prediction. To show the effectiveness of esDNN, we also conduct comprehensive experiments based on realistic traces derived from Alibaba and Google cloud data centers. The experimental results demonstrate that esDNN can accurately and efficiently predict cloud workloads. Compared with the state-of-the-art baselines, esDNN can reduce the mean square errors significantly, e.g. 15% than the approach using GRU only. We also apply esDNN for machines auto-scaling, which illustrates that esDNN can reduce the number of active hosts efficiently, thus the costs of service providers can be optimized.
Federated and Generalized Person Re-identification through Domain and Feature Hallucinating
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we study the problem of federated domain generalization (FedDG) for person re-identification (re-ID), which aims to learn a generalized model with multiple decentralized labeled source domains. An empirical method (FedAvg) trains local models individually and averages them to obtain the global model for further local fine-tuning or deploying in unseen target domains. One drawback of FedAvg is neglecting the data distributions of other clients during local training, making the local model overfit local data and producing a poorly-generalized global model. To solve this problem, we propose a novel method, called "Domain and Feature Hallucinating (DFH)", to produce diverse features for learning generalized local and global models. Specifically, after each model aggregation process, we share the Domain-level Feature Statistics (DFS) among different clients without violating data privacy. During local training, the DFS are used to synthesize novel domain statistics with the proposed domain hallucinating, which is achieved by re-weighting DFS with random weights. Then, we propose feature hallucinating to diversify local features by scaling and shifting them to the distribution of the obtained novel domain. The synthesized novel features retain the original pair-wise similarities, enabling us to utilize them to optimize the model in a supervised manner. Extensive experiments verify that the proposed DFH can effectively improve the generalization ability of the global model. Our method achieves the state-of-the-art performance for FedDG on four large-scale re-ID benchmarks.
Pareto Optimization or Cascaded Weighted Sum: A Comparison of Concepts
Venue: arXiv cs.NE 2022
Year: 2022

According to the published papers and books since the turn of the century, Pareto optimization is the dominating assessment method for multi-objective nonlinear optimization problems treated by population-based optimizers like Evolutionary Algorithms. However, is it always the method of choice for real-world applications, where either more than four objectives have to be considered, or the same type of task is repeated again and again with only minor modifications, in an automated optimization or planning process? This paper presents a classification of application scenarios and compares the Pareto approach with an extended version of the weighted sum, called cascaded weighted sum, for the different scenarios. Its range of application within the field of multi-objective optimization is discussed as well as its strengths and weaknesses.
A Study of Preference and Comfort for Users Immersed in a Telepresence Robot
Venue: arXiv cs.HC 2022
Year: 2022

In this paper, we show that unwinding the rotations of a user immersed in a telepresence robot is preferred and may increase the feeling of presence or "being there". By immersive telepresence, we mean a scenario where a user wearing a head-mounted display embodies a mobile robot equipped with a 360° camera in another location, such that the user can move the robot and communicate with people around it. By unwinding the rotations, the user never perceives rotational motion through the head-mounted display while staying stationary, avoiding sensory mismatch which causes a major part of VR sickness. We performed a user study (N=32) on a Dolly mobile robot platform, mimicking an earlier similar study done in simulation. Unlike the simulated study, in this study there is no significant difference in the VR sickness suffered by the participants, or the condition they find more comfortable (unwinding or automatic rotations). However, participants still prefer the unwinding condition, and they judge it to render a stronger feeling of presence, a major piece in natural communication. We show that participants aboard a real telepresence robot perceive distances similarly suitable as in simulation, presenting further evidence on the applicability of VR as a research platform for robotics and human-robot interaction.
MetaFormer: A Unified Meta Framework for Fine-Grained Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Fine-Grained Visual Classification(FGVC) is the task that requires recognizing the objects belonging to multiple subordinate categories of a super-category. Recent state-of-the-art methods usually design sophisticated learning pipelines to tackle this task. However, visual information alone is often not sufficient to accurately differentiate between fine-grained visual categories. Nowadays, the meta-information (e.g., spatio-temporal prior, attribute, and text description) usually appears along with the images. This inspires us to ask the question: Is it possible to use a unified and simple framework to utilize various meta-information to assist in fine-grained identification? To answer this problem, we explore a unified and strong meta-framework(MetaFormer) for fine-grained visual classification. In practice, MetaFormer provides a simple yet effective approach to address the joint learning of vision and various meta-information. Moreover, MetaFormer also provides a strong baseline for FGVC without bells and whistles. Extensive experiments demonstrate that MetaFormer can effectively use various meta-information to improve the performance of fine-grained recognition. In a fair comparison, MetaFormer can outperform the current SotA approaches with only vision information on the iNaturalist2017 and iNaturalist2018 datasets. Adding meta-information, MetaFormer can exceed the current SotA approaches by 5.9% and 5.3%, respectively. Moreover, MetaFormer can achieve 92.3% and 92.7% on CUB-200-2011 and NABirds, which significantly outperforms the SotA approaches. The source code and pre-trained models are released athttps://github.com/dqshuai/MetaFormer.
Online List Labeling: Breaking the $\log^2n$ Barrier
Venue: arXiv cs.DS 2022
Year: 2022

The online list labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing set of $n$ items in an array of $m$ slots, while maintaining the invariant that the items appear in sorted order, and while minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. For the linear regime, where $m = (1 + Θ(1)) n$, an upper bound of $O(\log^2 n)$ on the relabeling cost has been known since 1981. A lower bound of $Ω(\log^2 n)$ is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains $Ω(\log n)$. The central open question in the field is whether $O(\log^2 n)$ is optimal for all algorithms. In this paper, we give a randomized data structure that achieves an expected relabeling cost of $O(\log^{3/2} n)$ per operation. More generally, if $m = (1 + \varepsilon) n$ for $\varepsilon = O(1)$, the expected relabeling cost becomes $O(\varepsilon^{-1} \log^{3/2} n)$. Our solution is history independent, meaning that the state of the data structure is independent of the order in which items are inserted/deleted. For history-independent data structures, we also prove a matching lower bound: for all $ε$ between $1 / n^{1/3}$ and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is $Θ(\varepsilon^{-1}\log^{3/2} n)$.
Don't Be So Dense: Sparse-to-Sparse GAN Training Without Sacrificing Performance
Venue: arXiv cs.CV 2022
Year: 2022

Generative adversarial networks (GANs) have received an upsurging interest since being proposed due to the high quality of the generated data. While achieving increasingly impressive results, the resource demands associated with the large model size hinders the usage of GANs in resource-limited scenarios. For inference, the existing model compression techniques can reduce the model complexity with comparable performance. However, the training efficiency of GANs has less been explored due to the fragile training process of GANs. In this paper, we, for the first time, explore the possibility of directly training sparse GAN from scratch without involving any dense or pre-training steps. Even more unconventionally, our proposed method enables directly training sparse unbalanced GANs with an extremely sparse generator from scratch. Instead of training full GANs, we start with sparse GANs and dynamically explore the parameter space spanned over the generator throughout training. Such a sparse-to-sparse training procedure enhances the capacity of the highly sparse generator progressively while sticking to a fixed small parameter budget with appealing training and inference efficiency gains. Extensive experiments with modern GAN architectures validate the effectiveness of our method. Our sparsified GANs, trained from scratch in one single run, are able to outperform the ones learned by expensive iterative pruning and re-training. Perhaps most importantly, we find instead of inheriting parameters from expensive pre-trained GANs, directly training sparse GANs from scratch can be a much more efficient solution. For example, only training with a 80% sparse generator and a 70% sparse discriminator, our method can achieve even better performance than the dense BigGAN.
pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores
Venue: arXiv cs.DS 2022
Year: 2022

We present parallel algorithms and data structures for three fundamental operations in Numerical Linear Algebra: (i) Gaussian and CountSketch random projections and their combination, (ii) computation of the Gram matrix and (iii) computation of the squared row norms of the product of two matrices, with a special focus on "tall-and-skinny" matrices, which arise in many applications. We provide a detailed analysis of the ubiquitous CountSketch transform and its combination with Gaussian random projections, accounting for memory requirements, computational complexity and workload balancing. We also demonstrate how these results can be applied to column subset selection, least squares regression and leverage scores computation. These tools have been implemented in pylspack, a publicly available Python package (https://github.com/IBM/pylspack) whose core is written in C++ and parallelized with OpenMP, and which is compatible with standard matrix data structures of SciPy and NumPy. Extensive numerical experiments indicate that the proposed algorithms scale well and significantly outperform existing libraries for tall-and-skinny matrices.
Virtual Reality Digital Twin and Environment for Troubleshooting Lunar-based Infrastructure Assembly Failures
Venue: arXiv cs.RO 2022
Year: 2022

Humans and robots will need to collaborate in order to create a sustainable human lunar presence by the end of the 2020s. This includes cases in which a human will be required to teleoperate an autonomous rover that has encountered an instrument assembly failure. To aid teleoperators in the troubleshooting process, we propose a virtual reality digital twin placed in a simulated environment. Here, the operator can virtually interact with a digital version of the rover and mechanical arm that uses the same controls and kinematic model. The user can also adopt the egocentric (a first person view through using stereoscopic passthrough) and exocentric (a third person view where the operator can virtually walk around the environment and rover as if they were on site) view. We also discuss our metrics for evaluating the differences between our digital and physical robot, as well as the experimental concept based on real and applicable missions, and future work that would compare our platform to traditional troubleshooting methods.
Double Choco is NP-complete
Venue: arXiv cs.CC 2022
Year: 2022

In the Nikoli pencil-and-paper game Double Choco, a puzzle consists of an m $\times$ n grid of cells of white or gray color, separated by dotted lines where each cell possibly contains an integer. The goal is to partition the grid into blocks by drawing solid lines over the dotted lines, where every block must contain a pair of areas of white and gray cells having the same form (size and shape). An integer indicates the number of cells of that color in the block. A block can contain any number of cells with the integer. We prove this puzzle NP-complete, establishing a Nikoli gap of 2 years.
A Multi-Document Coverage Reward for RELAXed Multi-Document Summarization
Venue: arXiv cs.CL 2022
Year: 2022

Multi-document summarization (MDS) has made significant progress in recent years, in part facilitated by the availability of new, dedicated datasets and capacious language models. However, a standing limitation of these models is that they are trained against limited references and with plain maximum-likelihood objectives. As for many other generative tasks, reinforcement learning (RL) offers the potential to improve the training of MDS models; yet, it requires a carefully-designed reward that can ensure appropriate leverage of both the reference summaries and the input documents. For this reason, in this paper we propose fine-tuning an MDS baseline with a reward that balances a reference-based metric such as ROUGE with coverage of the input documents. To implement the approach, we utilize RELAX (Grathwohl et al., 2018), a contemporary gradient estimator which is both low-variance and unbiased, and we fine-tune the baseline in a few-shot style for both stability and computational efficiency. Experimental results over the Multi-News and WCEP MDS datasets show significant improvements of up to +0.95 pp average ROUGE score and +3.17 pp METEOR score over the baseline, and competitive results with the literature. In addition, they show that the coverage of the input documents is increased, and evenly across all documents.