OpenRaiser/Intern-Atlas huggingface dataset:
Location Information Assisted Beamforming Design for Reconfigurable Intelligent Surface Aided Communication Systems
Venue: arXiv cs.IT 2022
Year: 2022

In reconfigurable intelligent surface (RIS) aided millimeter-wave (mmWave) communication systems, in order to overcome the limitation of the conventional channel state information (CSI) acquisition techniques, this paper proposes a location information assisted beamforming design without the requirement of the conventional channel training process. First, we establish the geometrical relation between the channel model and the user location, based on which we derive an approximate CSI error bound based on the user location error by means of Taylor approximation, triangle and power mean inequalities, and semidefinite relaxation (SDR). Second, for combating the uncertainty of the location error, we formulate a worst-case robust beamforming optimization problem. To solve the problem efficiently, we develop a novel iterative algorithm by utilizing various optimization tools such as Lagrange multiplier, matrix inversion lemma, SDR, as well as branch-and-bound (BnB). Additionally, we provide sufficient conditions for the SDR to output rank-one solutions, and modify the BnB algorithm to acquire the phase shift solution under an arbitrary constraint of possible phase shift values. Finally, we analyse the algorithm convergence and complexity, and carry out simulations to validate the theoretical derivation of the CSI error bound and the robustness of the proposed algorithm. Compared with the existing non-robust approach and the robust beamforming techniques based on S-procedure and penalty convex-concave procedure (CCP), our method can converge more quickly and achieve better performance in terms of the worst-case signal-to-noise ratio (SNR) at the receiver.
NYU-VPR: Long-Term Visual Place Recognition Benchmark with View Direction and Data Anonymization Influences
Venue: arXiv cs.CV 2022
Year: 2022

Visual place recognition (VPR) is critical in not only localization and mapping for autonomous driving vehicles, but also in assistive navigation for the visually impaired population. To enable a long-term VPR system on a large scale, several challenges need to be addressed. First, different applications could require different image view directions, such as front views for self-driving cars while side views for the low vision people. Second, VPR in metropolitan scenes can often cause privacy concerns due to the imaging of pedestrian and vehicle identity information, calling for the need for data anonymization before VPR queries and database construction. Both factors could lead to VPR performance variations that are not well understood yet. To study their influences, we present the NYU-VPR dataset that contains more than 200,000 images over a 2km by 2km area near the New York University campus, taken within the whole year of 2016. We present benchmark results on several popular VPR algorithms showing that side views are significantly more challenging for current VPR methods while the influence of data anonymization is almost negligible, together with our hypothetical explanations and in-depth analysis.
Fairness Concepts for Indivisible Items with Externalities
Venue: arXiv cs.GT 2022
Year: 2022

We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives values from items that are assigned to other agents. We propose several new fairness concepts. We extend the well-studied envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) to this setting, and we propose a new fairness concept called general fair share (GFS). We undertake a detailed study and present algorithms for finding fair allocations.
Continuation of Famous Art with AI: A Conditional Adversarial Network Inpainting Approach
Venue: arXiv cs.CV 2022
Year: 2022

Much of the state-of-the-art in image synthesis inspired by real artwork are either entirely generative by filtered random noise or inspired by the transfer of style. This work explores the application of image inpainting to continue famous artworks and produce generative art with a Conditional GAN. During the training stage of the process, the borders of images are cropped, leaving only the centre. An inpainting GAN is then tasked with learning to reconstruct the original image from the centre crop by way of minimising both adversarial and absolute difference losses, which are analysed by both their Fréchet Inception Distances and manual observations which are presented. Once the network is trained, images are then resized rather than cropped and presented as input to the generator. Following the learning process, the generator then creates new images by continuing from the edges of the original piece. Three experiments are performed with datasets of 4766 landscape paintings (impressionism and romanticism), 1167 Ukiyo-e works from the Japanese Edo period, and 4968 abstract artworks. Results show that geometry and texture (including canvas and paint) as well as scenery such as sky, clouds, water, land (including hills and mountains), grass, and flowers are implemented by the generator when extending real artworks. In the Ukiyo-e experiments, it was observed that features such as written text were generated even in cases where the original image did not have any, due to the presence of an unpainted border within the input image.
A Primer on the Statistical Relation between Wireless Ultra-Reliability and Location Estimation
Venue: arXiv cs.IT 2022
Year: 2022

Location information is often used as a proxy to infer the performance of a wireless communication link. Using a very simple model, this letter unveils a basic statistical relation between the location estimation uncertainty and wireless link reliability. First, a Cramér-Rao bound for the localization error is derived. Then, wireless link reliability is characterized by how likely the outage probability is to be above a target threshold. We show that the reliability is sensitive to location errors, especially when the channel statistics are also sensitive to the location. Finally, we highlight the difficulty of choosing a rate that meets target reliability while accounting for the location uncertainty.
Towards a Systematic Survey for Carbon Neutral Data Centers
Venue: arXiv cs.CY 2022
Year: 2022

Data centers are carbon-intensive enterprises due to their massive energy consumption, and it is estimated that data center industry will account for 8\% of global carbon emissions by 2030. However, both technological and policy instruments for reducing or even neutralizing data center carbon emissions have not been thoroughly investigated. To bridge this gap, this survey paper proposes a roadmap towards carbon-neutral data centers that takes into account both policy instruments and technological methodologies. We begin by presenting the carbon footprint of data centers, as well as some insights into the major sources of carbon emissions. Following that, carbon neutrality plans for major global cloud providers are discussed to summarize current industrial efforts in this direction. In what follows, we introduce the carbon market as a policy instrument to explain how to offset data center carbon emissions in a cost-efficient manner. On the technological front, we propose achieving carbon-neutral data centers by increasing renewable energy penetration, improving energy efficiency, and boosting energy circulation simultaneously. A comprehensive review of existing technologies on these three topics is elaborated subsequently. Based on this, a multi-pronged approach towards carbon neutrality is envisioned and a digital twin-powered industrial artificial intelligence (AI) framework is proposed to make this solution a reality. Furthermore, three key scientific challenges for putting such a framework in place are discussed. Finally, several applications for this framework are presented to demonstrate its enormous potential.
Energon: Towards Efficient Acceleration of Transformers Using Dynamic Sparse Attention
Venue: arXiv cs.AR 2022
Year: 2022

In recent years, transformer models have revolutionized Natural Language Processing (NLP) and shown promising performance on Computer Vision (CV) tasks. Despite their effectiveness, transformers' attention operations are hard to accelerate due to the complicated data movement and quadratic computational complexity, prohibiting the real-time inference on resource-constrained edge-computing platforms. To tackle this challenge, we propose Energon, an algorithm-architecture co-design approach that accelerates various transformers using dynamic sparse attention. With the observation that attention results only depend on a few important query-key pairs, we propose a Mix-Precision Multi-Round Filtering (MP-MRF) algorithm to dynamically identify such pairs at runtime. We adopt low bitwidth in each filtering round and only use high-precision tensors in the attention stage to reduce overall complexity. By this means, we significantly mitigate the computational cost with negligible accuracy loss. To enable such an algorithm with lower latency and better energy efficiency, we also propose an Energon co-processor architecture. Elaborated pipelines and specialized optimizations jointly boost the performance and reduce power consumption. Extensive experiments on both NLP and CV benchmarks demonstrate that Energon achieves $168\times$ and $8.7\times$ geo-mean speedup and up to $10^4\times$ and $10^3\times$ energy reduction compared with Intel Xeon 5220 CPU and NVIDIA V100 GPU. Compared to state-of-the-art attention accelerators SpAtten and $A^3$, Energon also achieves $1.7\times, 1.25\times$ speedup and $1.6 \times, 1.5\times $ higher energy efficiency.
Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees
Venue: arXiv cs.NE 2022
Year: 2022

Given a ground set of items, the result diversification problem aims to select a subset with high "quality" and "diversity" while satisfying some constraints. It arises in various real-world artificial intelligence applications, such as web-based search, document summarization and feature selection, and also has applications in other areas, e.g., computational geometry, databases, finance and operations research. Previous algorithms are mainly based on greedy or local search. In this paper, we propose to reformulate the result diversification problem as a bi-objective maximization problem, and solve it by a multi-objective evolutionary algorithm (EA), i.e., the GSEMO. We theoretically prove that the GSEMO can achieve the (asymptotically) optimal theoretical guarantees under both static and dynamic environments. For cardinality constraints, the GSEMO can achieve the optimal polynomial-time approximation ratio, $1/2$. For more general matroid constraints, the GSEMO can achieve an asymptotically optimal polynomial-time approximation ratio, $1/2-ε/(4n)$, where $ε>0$ and $n$ is the size of the ground set of items. Furthermore, when the objective function (i.e., a linear combination of quality and diversity) changes dynamically, the GSEMO can maintain this approximation ratio in polynomial running time, addressing the open question proposed by Borodin. This also theoretically shows the superiority of EAs over local search for solving dynamic optimization problems for the first time, and discloses the robustness of the mutation operator of EAs against dynamic changes. Experiments on the applications of web-based search, multi-label feature selection and document summarization show the superior performance of the GSEMO over the state-of-the-art algorithms (i.e., the greedy algorithm and local search) under both static and dynamic environments.
ifMixup: Interpolating Graph Pair to Regularize Graph Classification
Venue: arXiv cs.LG 2022
Year: 2022

We present a simple and yet effective interpolation-based regularization technique, aiming to improve the generalization of Graph Neural Networks (GNNs) on supervised graph classification. We leverage Mixup, an effective regularizer for vision, where random sample pairs and their labels are interpolated to create synthetic images for training. Unlike images with grid-like coordinates, graphs have arbitrary structure and topology, which can be very sensitive to any modification that alters the graph's semantic meanings. This posts two unanswered questions for Mixup-like regularization schemes: Can we directly mix up a pair of graph inputs? If so, how well does such mixing strategy regularize the learning of GNNs? To answer these two questions, we propose ifMixup, which first adds dummy nodes to make two graphs have the same input size and then simultaneously performs linear interpolation between the aligned node feature vectors and the aligned edge representations of the two graphs. We empirically show that such simple mixing schema can effectively regularize the classification learning, resulting in superior predictive accuracy to popular graph augmentation and GNN methods.
Towards Federated Bayesian Network Structure Learning with Continuous Optimization
Venue: arXiv cs.LG 2022
Year: 2022

Traditionally, Bayesian network structure learning is often carried out at a central site, in which all data is gathered. However, in practice, data may be distributed across different parties (e.g., companies, devices) who intend to collectively learn a Bayesian network, but are not willing to disclose information related to their data owing to privacy or security concerns. In this work, we present a federated learning approach to estimate the structure of Bayesian network from data that is horizontally partitioned across different parties. We develop a distributed structure learning method based on continuous optimization, using the alternating direction method of multipliers (ADMM), such that only the model parameters have to be exchanged during the optimization process. We demonstrate the flexibility of our approach by adopting it for both linear and nonlinear cases. Experimental results on synthetic and real datasets show that it achieves an improved performance over the other methods, especially when there is a relatively large number of clients and each has a limited sample size.
BEV-SGD: Best Effort Voting SGD for Analog Aggregation Based Federated Learning against Byzantine Attackers
Venue: arXiv cs.LG 2022
Year: 2022

As a promising distributed learning technology, analog aggregation based federated learning over the air (FLOA) provides high communication efficiency and privacy provisioning under the edge computing paradigm. When all edge devices (workers) simultaneously upload their local updates to the parameter server (PS) through commonly shared time-frequency resources, the PS obtains the averaged update only rather than the individual local ones. While such a concurrent transmission and aggregation scheme reduces the latency and communication costs, it unfortunately renders FLOA vulnerable to Byzantine attacks. Aiming at Byzantine-resilient FLOA, this paper starts from analyzing the channel inversion (CI) mechanism that is widely used for power control in FLOA. Our theoretical analysis indicates that although CI can achieve good learning performance in the benign scenarios, it fails to work well with limited defensive capability against Byzantine attacks. Then, we propose a novel scheme called the best effort voting (BEV) power control policy that is integrated with stochastic gradient descent (SGD). Our BEV-SGD enhances the robustness of FLOA to Byzantine attacks, by allowing all the workers to send their local updates at their maximum transmit power. Under worst-case attacks, we derive the expected convergence rates of FLOA with CI and BEV power control policies, respectively. The rate comparison reveals that our BEV-SGD outperforms its counterpart with CI in terms of better convergence behavior, which is verified by experimental simulations.
On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game
Venue: arXiv cs.LG 2022
Year: 2022

To achieve sample efficiency in reinforcement learning (RL), it necessitates efficiently exploring the underlying environment. Under the offline setting, addressing the exploration challenge lies in collecting an offline dataset with sufficient coverage. Motivated by such a challenge, we study the reward-free RL problem, where an agent aims to thoroughly explore the environment without any pre-specified reward function. Then, given any extrinsic reward, the agent computes the policy via a planning algorithm with offline data collected in the exploration phase. Moreover, we tackle this problem under the context of function approximation, leveraging powerful function approximators. Specifically, we propose to explore via an optimistic variant of the value-iteration algorithm incorporating kernel and neural function approximations, where we adopt the associated exploration bonus as the exploration reward. Moreover, we design exploration and planning algorithms for both single-agent MDPs and zero-sum Markov games and prove that our methods can achieve $\widetilde{\mathcal{O}}(1 /\varepsilon^2)$ sample complexity for generating a $\varepsilon$-suboptimal policy or $\varepsilon$-approximate Nash equilibrium when given an arbitrary extrinsic reward. To the best of our knowledge, we establish the first provably efficient reward-free RL algorithm with kernel and neural function approximators.
Predicate and relation liftings for coalgebras with side effects: an application in coalgebraic modal logic
Venue: arXiv cs.LO 2022
Year: 2022

We study coalgebraic modal logic to characterise behavioural equivalence in the presence of side effects, i.e., when coalgebras live in a (co)Kleisli or an Eilenberg-Moore category. Our aim is to develop a general framework based on indexed categories/fibrations that is common to the aforementioned categories. In particular, we show how the coalgebraic notion of behavioural equivalence arises from a relation lifting (a special kind of indexed morphism) and we give a general recipe to construct such liftings in the above three cases. Lastly, we apply this framework to derive logical characterisations for (weighted) language equivalence and conditional bisimilarity.
A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
Venue: arXiv cs.DC 2022
Year: 2022

We study the consensus decentralized optimization problem where the objective function is the average of $n$ agents private non-convex cost functions; moreover, the agents can only communicate to their neighbors on a given network topology. The stochastic learning setting is considered in this paper where each agent can only access a noisy estimate of its gradient. Many decentralized methods can solve such problem including EXTRA, Exact-Diffusion/D$^2$, and gradient-tracking. Unlike the famed DSGD algorithm, these methods have been shown to be robust to the heterogeneity across the local cost functions. However, the established convergence rates for these methods indicate that their sensitivity to the network topology is worse than DSGD. Such theoretical results imply that these methods can perform much worse than DSGD over sparse networks, which, however, contradicts empirical experiments where DSGD is observed to be more sensitive to the network topology. In this work, we study a general stochastic unified decentralized algorithm (SUDA) that includes the above methods as special cases. We establish the convergence of SUDA under both non-convex and the Polyak-Lojasiewicz condition settings. Our results provide improved network topology dependent bounds for these methods (such as Exact-Diffusion/D$^2$ and gradient-tracking) compared with existing literature. Moreover, our results show that these methods are often less sensitive to the network topology compared to DSGD, which agrees with numerical experiments.
Summ^N: A Multi-Stage Summarization Framework for Long Input Dialogues and Documents
Venue: arXiv cs.CL 2022
Year: 2022

Text summarization helps readers capture salient information from documents, news, interviews, and meetings. However, most state-of-the-art pretrained language models (LM) are unable to efficiently process long text for many summarization tasks. In this paper, we propose Summ$^N$, a simple, flexible, and effective multi-stage framework for input texts that are longer than the maximum context length of typical pretrained LMs. Summ$^N$ first splits the data samples and generates a coarse summary in multiple stages and then produces the final fine-grained summary based on it. Our framework can process input text of arbitrary length by adjusting the number of stages while keeping the LM input size fixed. Moreover, it can deal with both single-source documents and dialogues, and it can be used on top of different backbone abstractive summarization models. To the best of our knowledge, Summ$^N$ is the first multi-stage split-then-summarize framework for long input summarization. Our experiments demonstrate that Summ$^N$ outperforms previous state-of-the-art methods by improving ROUGE scores on three long meeting summarization datasets AMI, ICSI, and QMSum, two long TV series datasets from SummScreen, and a long document summarization dataset GovReport. Our data and code are available at https://github.com/psunlpgroup/Summ-N.
Collaboration Challenges in Building ML-Enabled Systems: Communication, Documentation, Engineering, and Process
Venue: arXiv cs.SE 2022
Year: 2022

The introduction of machine learning (ML) components in software projects has created the need for software engineers to collaborate with data scientists and other specialists. While collaboration can always be challenging, ML introduces additional challenges with its exploratory model development process, additional skills and knowledge needed, difficulties testing ML systems, need for continuous evolution and monitoring, and non-traditional quality requirements such as fairness and explainability. Through interviews with 45 practitioners from 28 organizations, we identified key collaboration challenges that teams face when building and deploying ML systems into production. We report on common collaboration points in the development of production ML systems for requirements, data, and integration, as well as corresponding team patterns and challenges. We find that most of these challenges center around communication, documentation, engineering, and process and collect recommendations to address these challenges.
Performance Analysis for Covert Communications Under Faster-than-Nyquist Signaling
Venue: arXiv cs.IT 2022
Year: 2022

In this letter, we analyze the performance of covert communications under faster-than-Nyquist (FTN) signaling in the Rayleigh block fading channel. Both Bayesian criterion- and Kullback-Leibler (KL) divergence-based covertness constraints are considered. Especially, for KL divergence-based one, we prove that both the maximum transmit power and covert rate under FTN signaling are higher than those under Nyquist signaling. Numerical results coincide with our analysis and validate the advantages of FTN signaling to realize covert data transmission.