OpenRaiser/Intern-Atlas huggingface dataset:
The Rate of Convergence of Variation-Constrained Deep Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Multi-layer feedforward networks have been used to approximate a wide range of nonlinear functions. An important and fundamental problem is to understand the learnability of a network model through its statistical risk, or the expected prediction error on future data. To the best of our knowledge, the rate of convergence of neural networks shown by existing works is bounded by at most the order of $n^{-1/4}$ for a sample size of $n$. In this paper, we show that a class of variation-constrained neural networks, with arbitrary width, can achieve near-parametric rate $n^{-1/2+δ}$ for an arbitrarily small positive constant $δ$. It is equivalent to $n^{-1 +2δ}$ under the mean squared error. This rate is also observed by numerical experiments. The result indicates that the neural function space needed for approximating smooth functions may not be as large as what is often perceived. Our result also provides insight to the phenomena that deep neural networks do not easily suffer from overfitting when the number of neurons and learning parameters rapidly grow with $n$ or even surpass $n$. We also discuss the rate of convergence regarding other network parameters, including the input dimension, network layer, and coefficient norm.
A General Lotto game with asymmetric budget uncertainty
Venue: arXiv cs.GT 2022
Year: 2022

The General Lotto game is a popular variant of the famous Colonel Blotto game, in which two opposing players allocate limited resources over many battlefields. In this paper, we consider incomplete and asymmetric information formulations regarding the resource budgets of the players. In particular, one of the player's resource budget is common knowledge while the other player's is private. We provide complete equilibrium characterizations in the scenario where the private resource budget is drawn from an arbitrary Bernoulli distribution. We then show that these characterizations can be used to analyze a multi-stage resource assignment problem where a commander must decide how to assign resources to sub-colonels that compete against opponents in separate General Lotto games. While optimal deterministic assignments have been characterized in the literature, we broaden the context by deriving optimal (Bernoulli) randomized assignments, which induce asymmetric information General Lotto games to be played. We demonstrate that randomizing can offer a four-fold improvement in the commander's performance over deterministic assignments.
Imitation Learning: Progress, Taxonomies and Challenges
Venue: arXiv cs.LG 2022
Year: 2022

Imitation learning aims to extract knowledge from human experts' demonstrations or artificially created agents in order to replicate their behaviors. Its success has been demonstrated in areas such as video games, autonomous driving, robotic simulations and object manipulation. However, this replicating process could be problematic, such as the performance is highly dependent on the demonstration quality, and most trained agents are limited to perform well in task-specific environments. In this survey, we provide a systematic review on imitation learning. We first introduce the background knowledge from development history and preliminaries, followed by presenting different taxonomies within Imitation Learning and key milestones of the field. We then detail challenges in learning strategies and present research opportunities with learning policy from suboptimal demonstration, voice instructions and other associated optimization schemes.
Massive MIMO with Radio Stripes for Indoor Wireless Energy Transfer
Venue: arXiv cs.IT 2022
Year: 2022

Radio frequency wireless energy transfer (WET) is a promising solution for powering autonomous Internet of Things (IoT) deployments. In this work, we leverage energy beamforming for powering multiple user equipments (UEs) with stringent energy harvesting (EH) demands in an indoor distributed massive multiple-input multiple-output system. Based on semi-definite programming, successive convex approximation (SCA), and maximum ratio transmission (MRT) techniques, we derive optimal and sub-optimal precoders aimed at minimizing the radio stripes' transmit power while exploiting information of the power transfer efficiency of the EH circuits at the UEs. Moreover, we propose an analytical framework to assess and control the electromagnetic field (EMF) radiation exposure in the considered indoor scenario. Numerical results show that i) the EMF radiation exposure can be more easily controlled at higher frequencies at the cost of a higher transmit power consumption, ii) training is not a very critical factor for the considered indoor system, iii) MRT/SCA-based precoders are particularly appealing when serving a small number of UEs, thus, especially suitable for implementation in a time domain multiple access (TDMA) scheduling framework, and iv) TDMA is more efficient than spatial domain multiple access (SDMA) when serving a relatively small number of UEs. Results suggest that additional boosting performance strategies are needed to increase the overall system efficiency, thus making the technology viable in practice.
Distributed coloring and the local structure of unit-disk graphs
Venue: arXiv cs.DC 2022
Year: 2022

Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph $G$ with at most $4ω(G)$ colors, where $ω(G)$ is the clique number of $G$. This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph $G$ with at most $5.68ω(G)+1$ colors in $O(\log^* n)$ rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4ω(G)$, which would imply the existence of a $O(\log n)$ round algorithm coloring any unit-disk graph $G$ with (approximately) $4ω(G)$ colors in the LOCAL model. We provide partial results towards this conjecture using Fourier-analytical tools.
Transformer Meets Convolution: A Bilateral Awareness Network for Semantic Segmentation of Very Fine Resolution Urban Scene Images
Venue: arXiv cs.CV 2022
Year: 2022

Semantic segmentation from very fine resolution (VFR) urban scene images plays a significant role in several application scenarios including autonomous driving, land cover classification, and urban planning, etc. However, the tremendous details contained in the VFR image, especially the considerable variations in scale and appearance of objects, severely limit the potential of the existing deep learning approaches. Addressing such issues represents a promising research field in the remote sensing community, which paves the way for scene-level landscape pattern analysis and decision making. In this paper, we propose a Bilateral Awareness Network which contains a dependency path and a texture path to fully capture the long-range relationships and fine-grained details in VFR images. Specifically, the dependency path is conducted based on the ResT, a novel Transformer backbone with memory-efficient multi-head self-attention, while the texture path is built on the stacked convolution operation. Besides, using the linear attention mechanism, a feature aggregation module is designed to effectively fuse the dependency features and texture features. Extensive experiments conducted on the three large-scale urban scene image segmentation datasets, i.e., ISPRS Vaihingen dataset, ISPRS Potsdam dataset, and UAVid dataset, demonstrate the effectiveness of our BANet. Specifically, a 64.6% mIoU is achieved on the UAVid dataset. Code is available at https://github.com/WangLibo1995/GeoSeg.
Teacher Model Fingerprinting Attacks Against Transfer Learning
Venue: arXiv cs.CR 2022
Year: 2022

Transfer learning has become a common solution to address training data scarcity in practice. It trains a specified student model by reusing or fine-tuning early layers of a well-trained teacher model that is usually publicly available. However, besides utility improvement, the transferred public knowledge also brings potential threats to model confidentiality, and even further raises other security and privacy issues. In this paper, we present the first comprehensive investigation of the teacher model exposure threat in the transfer learning context, aiming to gain a deeper insight into the tension between public knowledge and model confidentiality. To this end, we propose a teacher model fingerprinting attack to infer the origin of a student model, i.e., the teacher model it transfers from. Specifically, we propose a novel optimization-based method to carefully generate queries to probe the student model to realize our attack. Unlike existing model reverse engineering approaches, our proposed fingerprinting method neither relies on fine-grained model outputs, e.g., posteriors, nor auxiliary information of the model architecture or training dataset. We systematically evaluate the effectiveness of our proposed attack. The empirical results demonstrate that our attack can accurately identify the model origin with few probing queries. Moreover, we show that the proposed attack can serve as a stepping stone to facilitating other attacks against machine learning models, such as model stealing.
Physics perception in sloshing scenes with guaranteed thermodynamic consistency
Venue: arXiv cs.CV 2022
Year: 2022

Physics perception very often faces the problem that only limited data or partial measurements on the scene are available. In this work, we propose a strategy to learn the full state of sloshing liquids from measurements of the free surface. Our approach is based on recurrent neural networks (RNN) that project the limited information available to a reduced-order manifold so as to not only reconstruct the unknown information, but also to be capable of performing fluid reasoning about future scenarios in real time. To obtain physically consistent predictions, we train deep neural networks on the reduced-order manifold that, through the employ of inductive biases, ensure the fulfillment of the principles of thermodynamics. RNNs learn from history the required hidden information to correlate the limited information with the latent space where the simulation occurs. Finally, a decoder returns data back to the high-dimensional manifold, so as to provide the user with insightful information in the form of augmented reality. This algorithm is connected to a computer vision system to test the performance of the proposed methodology with real information, resulting in a system capable of understanding and predicting future states of the observed fluid in real-time.
CEAZ: Accelerating Parallel I/O via Hardware-Algorithm Co-Designed Adaptive Lossy Compression
Venue: arXiv cs.DC 2022
Year: 2022

As HPC systems continue to grow to exascale, the amount of data that needs to be saved or transmitted is exploding. To this end, many previous works have studied using error-bounded lossy compressors to reduce the data size and improve the I/O performance. However, little work has been done for effectively offloading lossy compression onto FPGA-based SmartNICs to reduce the compression overhead. In this paper, we propose a hardware-algorithm codesign for an efficient and adaptive lossy compressor for scientific data on FPGAs (called CEAZ), which is the first lossy compressor that can achieve high compression ratios and throughputs simultaneously. Specifically, we propose an efficient Huffman coding approach that can adaptively update Huffman codewords online based on codewords generated offline, from a variety of representative scientific datasets. Moreover, we derive a theoretical analysis to support a precise control of compression ratio under an error-bounded compression mode, enabling accurate offline Huffman codewords generation. This also helps us create a fixed-ratio compression mode for consistent throughput. In addition, we develop an efficient compression pipeline by adopting cuSZ's dual-quantization algorithm to our hardware use cases. Finally, we evaluate CEAZ on five real-world datasets with both a single FPGA board and 128 nodes (to accelerate parallel I/O). Experiments show that CEAZ outperforms the second-best FPGA-based lossy compressor by 2.3X of throughput and 3.0X of ratio. It also improves MPI_File_write and MPI_Gather throughputs by up to 28.9X and 37.8X, respectively.
Bayesian Inference in High-Dimensional Time-Serieswith the Orthogonal Stochastic Linear Mixing Model
Venue: arXiv cs.LG 2022
Year: 2022

Many modern time-series datasets contain large numbers of output response variables sampled for prolonged periods of time. For example, in neuroscience, the activities of 100s-1000's of neurons are recorded during behaviors and in response to sensory stimuli. Multi-output Gaussian process models leverage the nonparametric nature of Gaussian processes to capture structure across multiple outputs. However, this class of models typically assumes that the correlations between the output response variables are invariant in the input space. Stochastic linear mixing models (SLMM) assume the mixture coefficients depend on input, making them more flexible and effective to capture complex output dependence. However, currently, the inference for SLMMs is intractable for large datasets, making them inapplicable to several modern time-series problems. In this paper, we propose a new regression framework, the orthogonal stochastic linear mixing model (OSLMM) that introduces an orthogonal constraint amongst the mixing coefficients. This constraint reduces the computational burden of inference while retaining the capability to handle complex output dependence. We provide Markov chain Monte Carlo inference procedures for both SLMM and OSLMM and demonstrate superior model scalability and reduced prediction error of OSLMM compared with state-of-the-art methods on several real-world applications. In neurophysiology recordings, we use the inferred latent functions for compact visualization of population responses to auditory stimuli, and demonstrate superior results compared to a competing method (GPFA). Together, these results demonstrate that OSLMM will be useful for the analysis of diverse, large-scale time-series datasets.
A direct Jacobian total Lagrangian explicit dynamics finite element algorithm for real-time simulation of hyperelastic materials
Venue: arXiv cs.CE 2022
Year: 2022

This paper presents a novel direct Jacobian total Lagrangian explicit dynamics (DJ-TLED) finite element algorithm for real-time nonlinear mechanics simulation. The nodal force contributions are expressed using only the Jacobian operator, instead of the deformation gradient tensor and finite deformation tensor, for fewer computational operations at run-time. Owing to this proposed Jacobian formulation, novel expressions are developed for strain invariants and constant components, which are also based on the Jacobian operator. Results show that the proposed DJ-TLED consumed between 0.70x and 0.88x CPU solution times compared to state-of-the-art TLED and achieved up to 121.72x and 94.26x speed improvements in tetrahedral and hexahedral meshes, respectively, using GPU acceleration. Compared to TLED, the most notable difference is that the notions of stress and strain are not explicitly visible in the proposed DJ-TLED but embedded implicitly in the formulation of nodal forces. Such a force formulation can be beneficial for fast deformation computation and can be particularly useful if the displacement field is of primary interest, which is demonstrated using a neurosurgical simulation of brain deformations for image-guided neurosurgery. The present work contributes towards a comprehensive DJ-TLED algorithm concerning isotropic and anisotropic hyperelastic constitutive models and GPU implementation. The source code is available at https://github.com/jinaojakezhang/DJTLED.
MAGE: Nearly Zero-Cost Virtual Memory for Secure Computation
Venue: arXiv cs.OS 2022
Year: 2022

Secure Computation (SC) is a family of cryptographic primitives for computing on encrypted data in single-party and multi-party settings. SC is being increasingly adopted by industry for a variety of applications. A significant obstacle to using SC for practical applications is the memory overhead of the underlying cryptography. We develop MAGE, an execution engine for SC that efficiently runs SC computations that do not fit in memory. We observe that, due to their intended security guarantees, SC schemes are inherently oblivious -- their memory access patterns are independent of the input data. Using this property, MAGE calculates the memory access pattern ahead of time and uses it to produce a memory management plan. This formulation of memory management, which we call memory programming, is a generalization of paging that allows MAGE to provide a highly efficient virtual memory abstraction for SC. MAGE outperforms the OS virtual memory system by up to an order of magnitude, and in many cases, runs SC computations that do not fit in memory at nearly the same speed as if the underlying machines had unbounded physical memory to fit the entire computation.
TENT: Tensorized Encoder Transformer for Temperature Forecasting
Venue: arXiv cs.LG 2022
Year: 2022

Reliable weather forecasting is of great importance in science, business, and society. The best performing data-driven models for weather prediction tasks rely on recurrent or convolutional neural networks, where some of which incorporate attention mechanisms. In this work, we introduce a novel model based on Transformer architecture for weather forecasting. The proposed Tensorial Encoder Transformer (TENT) model is equipped with tensorial attention and thus it exploits the spatiotemporal structure of weather data by processing it in multidimensional tensorial format. We show that compared to the classical encoder transformer, 3D convolutional neural networks, LSTM, and Convolutional LSTM, the proposed TENT model can better learn the underlying complex pattern of the weather data for the studied temperature prediction task. Experiments on two real-life weather datasets are performed. The datasets consist of historical measurements from weather stations in the USA, Canada and Europe. The first dataset contains hourly measurements of weather attributes for 30 cities in the USA and Canada from October 2012 to November 2017. The second dataset contains daily measurements of weather attributes of 18 cities across Europe from May 2005 to April 2020. Two attention scores are introduced based on the obtained tonsorial attention and are visualized in order to shed light on the decision-making process of our model and provide insight knowledge on the most important cities for the target cities.
Compositional Synthesis of Modular Systems (Full Version)
Venue: arXiv cs.LO 2022
Year: 2022

Given the advances in reactive synthesis, it is a natural next step to consider more complex multi-process systems. Distributed synthesis, however, is not yet scalable. Compositional approaches can be a game changer. Here, the challenge is to decompose a given specification of the global system behavior into requirements on the individual processes. In this paper, we introduce a compositional synthesis algorithm that, for each process, constructs, in addition to the implementation, a certificate that captures the necessary interface between the processes. The certificates then allow for constructing separate requirements for the individual processes. By bounding the size of the certificates, we can bias the synthesis procedure towards solutions that are desirable in the sense that the assumptions between the processes are small. Our experimental results show that our approach is much faster than standard methods for distributed synthesis as long as reasonably small certificates exist.
Optimal Spanners for Unit Ball Graphs in Doubling Metrics
Venue: arXiv cs.CG 2022
Year: 2022

Resolving an open question from 2006, we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple $\mathcal{O}(\log^*n)$-round distributed algorithm in the LOCAL model of computation, that given a unit ball graph $G$ with $n$ vertices and a positive constant $ε< 1$ finds a $(1+ε)$-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the best prior lightness bound, the algorithm of Damian, Pandit, and Pemmaraju, which runs in $\mathcal{O}(\log^*n)$ rounds in the LOCAL model, but has a $\mathcal{O}(\log Δ)$ bound on its lightness, where $Δ$ is the ratio of the length of the longest edge to the length of the shortest edge in the unit ball graph. Next, we adjust our algorithm to work in the CONGEST model, without changing its round complexity, hence proposing the first spanner construction for unit ball graphs in the CONGEST model of computation. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersections per node. Lastly, we provide experimental results that confirm our theoretical bounds, and show an efficient performance from our distributed algorithm compared to the best known centralized construction.
The cityseer Python package for pedestrian-scale network-based urban analysis
Venue: arXiv cs.SI 2022
Year: 2022

cityseer-api is a Python package consisting of computational tools for fine-grained street-network and land-use analysis, helpful in assessing the morphological precursors to vibrant neighbourhoods. It is underpinned by network-based methods developed specifically for urban analysis at the pedestrian scale. cityseer-api computes a variety of node and segment-based network centrality methods, land-use accessibility and mixed-use measures, and statistical aggregations. Accessibilities and aggregations are computed dynamically over the street-network while taking walking distance thresholds and the direction of approach into account, and can optionally incorporate spatial impedances and network decomposition to increase spatial precision. The use of Python facilitates compatibility with popular computational tools for network manipulation (NetworkX), geospatial topology (shapely), geospatial data state management (GeoPandas), and the NumPy stack of scientific packages. The provision of robust network cleaning tools aids the use of OpenStreetMap data for network analysis. Underlying loop-intensive algorithms are implemented in Numba JIT compiled code so that the methods scale efficiently to larger cities and regions. Online documentation is available from https://cityseer.benchmarkurbanism.com, and the Github repository is available at https://github.com/benchmark-urbanism/cityseer. Example notebooks are available at https://cityseer.benchmarkurbanism.com/examples/.