title: How can a Cognitive Radar Mask its Cognition?

abstract: We study how a cognitive radar can mask (hide) its cognitive ability from an adversarial jamming device. Specifically, if the radar optimally adapts its waveform based on adversarial target maneuvers (probes), how should the radar choose its waveform parameters (response) so that its utility function cannot be recovered by the adversary. This paper abstracts the radar's cognition masking problem in terms of the spectra (eigenvalues) of the state and observation noise covariance matrices, and embeds the algebraic Riccati equation into an economics-based utility maximization setup. Given an observed sequence of radar responses, the adversary tests for utility maximization behavior of the radar and estimates its utility function that rationalizes the radar's responses. In turn, the radar deliberately chooses sub-optimal responses so that its utility function almost fails the utility maximization test, and hence, its cognitive ability is masked from the adversary. We illustrate the performance of our cognition masking scheme via simple numerical examples. Our approach in this paper is based on revealed preference theory in microeconomics for identifying rationality.


title: On coupling epoch for renewal times

abstract: The ability to estimate the rate of convergence for the distributions of regenerative processes is in great demand. These processes are often encountered in queuing theory and in related problems. In some papers on regenerative processes, the coupling method and subsequent estimation of the convergence rate is used. In the presented small publication, we describe a general approach to using the coupling method for regenerative processes - both in the case of a polynomial and an exponential rate of convergence.


title: MAAD: A Model and Dataset for "Attended Awareness" in Driving

abstract: We propose a computational model to estimate a person's attended awareness of their environment. We define attended awareness to be those parts of a potentially dynamic scene which a person has attended to in recent history and which they are still likely to be physically aware of. Our model takes as input scene information in the form of a video and noisy gaze estimates, and outputs visual saliency, a refined gaze estimate, and an estimate of the person's attended awareness. In order to test our model, we capture a new dataset with a high-precision gaze tracker including 24.5 hours of gaze sequences from 23 subjects attending to videos of driving scenes. The dataset also contains third-party annotations of the subjects' attended awareness based on observations of their scan path. Our results show that our model is able to reasonably estimate attended awareness in a controlled setting, and in the future could potentially be extended to real egocentric driving data to help enable more effective ahead-of-time warnings in safety systems and thereby augment driver performance. We also demonstrate our model's effectiveness on the tasks of saliency, gaze calibration, and denoising, using both our dataset and an existing saliency dataset. We make our model and dataset available at https://github.com/ToyotaResearchInstitute/att-aware/.


title: Deep Active Learning by Leveraging Training Dynamics

abstract: Active learning theories and methods have been extensively studied in classical statistical learning settings. However, deep active learning, i.e., active learning with deep learning models, is usually based on empirical criteria without solid theoretical justification, thus suffering from heavy doubts when some of those fail to provide benefits in real applications. In this paper, by exploring the connection between the generalization performance and the training dynamics, we propose a theory-driven deep active learning method (dynamicAL) which selects samples to maximize training dynamics. In particular, we prove that the convergence speed of training and the generalization performance are positively correlated under the ultra-wide condition and show that maximizing the training dynamics leads to better generalization performance. Furthermore, to scale up to large deep neural networks and data sets, we introduce two relaxations for the subset selection problem and reduce the time complexity from polynomial to constant. Empirical results show that dynamicAL not only outperforms the other baselines consistently but also scales well on large deep learning models. We hope our work would inspire more attempts on bridging the theoretical findings of deep networks and practical impacts of deep active learning in real applications.


title: The elastic origins of tail asymmetry

abstract: Based on a multisector general equilibrium framework, we show that the sectoral elasticity of substitution plays the key role in the evolution of asymmetric tails of macroeconomic fluctuations and the establishment of robustness against productivity shocks. Non-unitary elasticity of substitution renders a nonlinear Domar aggregation, where normal sectoral productivity shocks translate into non-normal aggregated shocks with variable expected output growth. We empirically estimate 100 sectoral elasticities of substitution, using the time-series linked input-output tables for Japan, and find that the production economy is elastic overall, relative to Cobb-Douglas with unitary elasticity. Along with the previous assessment of an inelastic production economy for the US, the contrasting tail asymmetry of the distribution of aggregated shocks between the US and Japan is explained. Moreover, robustness of an economy is assessed by the expected output growth, the level of which is led by the sectoral elasticities of substitution, under zero mean productivity shocks.


title: Enabling Large-Reach TLBs for High-Throughput Processors by Exploiting Memory Subregion Contiguity

abstract: Accelerators, like GPUs, have become a trend to deliver future performance desire, and sharing the same virtual memory space between CPUs and GPUs is increasingly adopted to simplify programming. However, address translation, which is the key factor of virtual memory, is becoming the bottleneck of performance for GPUs. In GPUs, a single TLB miss can stall hundreds of threads due to the SIMT execute model, degrading performance dramatically. Through real system analysis, we observe that the OS shows an advanced contiguity (e.g., hundreds of contiguous pages), and more large memory regions with advanced contiguity tend to be allocated with the increase of working sets. Leveraging the observation, we propose MESC to improve the translation efficiency for GPUs. The key idea of MESC is to divide each large page frame (2MB size) in virtual memory space into memory subregions with fixed size (i.e., 64 4KB pages), and store the contiguity information of subregions and large page frames in L2PTEs. With MESC, address translations of up to 512 pages can be coalesced into single TLB entry, without the needs of changing memory allocation policy (i.e., demand paging) and the support of large pages. In the experimental results, MESC achieves 77.2% performance improvement and 76.4% reduction in dynamic translation energy for translation-sensitive workloads.


title: Deep Learning and Spectral Embedding for Graph Partitioning

abstract: We present a graph bisection and partitioning algorithm based on graph neural networks. For each node in the graph, the network outputs probabilities for each of the partitions. The graph neural network consists of two modules: an embedding phase and a partitioning phase. The embedding phase is trained first by minimizing a loss function inspired by spectral graph theory. The partitioning module is trained through a loss function that corresponds to the expected value of the normalized cut. Both parts of the neural network rely on SAGE convolutional layers and graph coarsening using heavy edge matching. The multilevel structure of the neural network is inspired by the multigrid algorithm. Our approach generalizes very well to bigger graphs and has partition quality comparable to METIS, Scotch and spectral partitioning, with shorter runtime compared to METIS and spectral partitioning.


title: KAM theory for active scalar equations

abstract: In this paper, we establish the existence of time quasi-periodic solutions to generalized surface quasi-geostrophic equation $({\rm gSQG})_\alpha$ in the patch form close to Rankine vortices. We show that invariant tori survive when the order $\alpha$ of the singular operator belongs to a Cantor set contained in $(0,\frac12)$ with almost full Lebesgue measure. The proof is based on several techniques from KAM theory, pseudo-differential calculus together with Nash-Moser scheme in the spirit of the recent works \cite{Baldi-Berti2018,Berti-Bolle15}. One key novelty here is a refined Egorov type theorem established through a new approach based on the kernel dynamics together with some hidden T\"opliz structures.


title: GradSign: Model Performance Inference with Theoretical Insights

abstract: A key challenge in neural architecture search (NAS) is quickly inferring the predictive performance of a broad spectrum of networks to discover statistically accurate and computationally efficient ones. We refer to this task as model performance inference (MPI). The current practice for efficient MPI is gradient-based methods that leverage the gradients of a network at initialization to infer its performance. However, existing gradient-based methods rely only on heuristic metrics and lack the necessary theoretical foundations to consolidate their designs. We propose GradSign, an accurate, simple, and flexible metric for model performance inference with theoretical insights. The key idea behind GradSign is a quantity {\Psi} to analyze the optimization landscape of different networks at the granularity of individual training samples. Theoretically, we show that both the network's training and true population losses are proportionally upper-bounded by {\Psi} under reasonable assumptions. In addition, we design GradSign, an accurate and simple approximation of {\Psi} using the gradients of a network evaluated at a random initialization state. Evaluation on seven NAS benchmarks across three training datasets shows that GradSign generalizes well to real-world networks and consistently outperforms state-of-the-art gradient-based methods for MPI evaluated by Spearman's {\rho} and Kendall's Tau. Additionally, we integrate GradSign into four existing NAS algorithms and show that the GradSign-assisted NAS algorithms outperform their vanilla counterparts by improving the accuracies of best-discovered networks by up to 0.3%, 1.1%, and 1.0% on three real-world tasks.


title: Numerical Overcurrent Relay: A Digitizing Element Testing Automation and Simulation Based on Wavelet Transform

abstract: In todays modern technology and fast growth in electrical power supply, the need for precise protection relays has become a major issue in the power distribution system. That is, to ensure a safe operation at all levels of generation, distribution, and consumer load, the power relay should perform at the highest level of accuracy. Therefore, this work will investigate the enhancement of the Overcurrent Numerical Relay in terms of the quality of digitized incoming analog current waveform prior to numerical relay decision. However, as it is an expensive process of testing the digitizing element of numerical overcurrent relay, Analog to Digital Converter, this newly proposed method of combing test automation by LabView and advanced waveform analysis algorithms by Wavelet transform will be applied to enhance the testing process, reduce data compiling complexity, and decrease cost. In addition, the testing simulation will be presented using Matlab software to verify the testing result. As a result, with a bank of filters, denoising, and decomposition structures, Wavelet transform can provide promising results in testing and verifying the accuracy of numerical relay digitizing process along with automation process to increase the possibility of improving numerical relay digitizer testing reliability with lower cost.


title: Convolutional Deep Denoising Autoencoders for Radio Astronomical Images

abstract: We apply a Machine Learning technique known as Convolutional Denoising Autoencoder to denoise synthetic images of state-of-the-art radio telescopes, with the goal of detecting the faint, diffused radio sources predicted to characterise the radio cosmic web. In our application, denoising is intended to address both the reduction of random instrumental noise and the minimisation of additional spurious artefacts like the sidelobes, resulting from the aperture synthesis technique. The effectiveness and the accuracy of the method are analysed for different kinds of corrupted input images, together with its computational performance. Specific attention has been devoted to create realistic mock observations for the training, exploiting the outcomes of cosmological numerical simulations, to generate images corresponding to LOFAR HBA 8 hours observations at 150 MHz. Our autoencoder can effectively denoise complex images identifying and extracting faint objects at the limits of the instrumental sensitivity. The method can efficiently scale on large datasets, exploiting high performance computing solutions, in a fully automated way (i.e. no human supervision is required after training). It can accurately perform image segmentation, identifying low brightness outskirts of diffused sources, proving to be a viable solution for detecting challenging extended objects hidden in noisy radio observations.


title: SAGAN: Adversarial Spatial-asymmetric Attention for Noisy Nona-Bayer Reconstruction

abstract: Nona-Bayer colour filter array (CFA) pattern is considered one of the most viable alternatives to traditional Bayer patterns. Despite the substantial advantages, such non-Bayer CFA patterns are susceptible to produce visual artefacts while reconstructing RGB images from noisy sensor data. This study addresses the challenges of learning RGB image reconstruction from noisy Nona-Bayer CFA comprehensively. We propose a novel spatial-asymmetric attention module to jointly learn bi-direction transformation and large-kernel global attention to reduce the visual artefacts. We combine our proposed module with adversarial learning to produce plausible images from Nona-Bayer CFA. The feasibility of the proposed method has been verified and compared with the state-of-the-art image reconstruction method. The experiments reveal that the proposed method can reconstruct RGB images from noisy Nona-Bayer CFA without producing any visually disturbing artefacts. Also, it can outperform the state-of-the-art image reconstruction method in both qualitative and quantitative comparison. Code available: https://github.com/sharif-apu/SAGAN_BMVC21.


title: Learning Cloth Folding Tasks with Refined Flow Based Spatio-Temporal Graphs

abstract: Cloth folding is a widespread domestic task that is seemingly performed by humans but which is highly challenging for autonomous robots to execute due to the highly deformable nature of textiles; It is hard to engineer and learn manipulation pipelines to efficiently execute it. In this paper, we propose a new solution for robotic cloth folding (using a standard folding board) via learning from demonstrations. Our demonstration video encoding is based on a high-level abstraction, namely, a refined optical flow-based spatiotemporal graph, as opposed to a low-level encoding such as image pixels. By constructing a new spatiotemporal graph with an advanced visual corresponding descriptor, the policy learning can focus on key points and relations with a 3D spatial configuration, which allows to quickly generalize across different environments. To further boost the policy searching, we combine optical flow and static motion saliency maps to discriminate the dominant motions for better handling the system dynamics in real-time, which aligns with the attentional motion mechanism that dominates the human imitation process. To validate the proposed approach, we analyze the manual folding procedure and developed a custom-made end-effector to efficiently interact with the folding board. Multiple experiments on a real robotic platform were conducted to validate the effectiveness and robustness of the proposed method.


title: When heart beats differently in depression: a review of HRV measures

abstract: Background and Objective: The connection between depression and autonomous nervous system (ANS) is well documented in scientific literature. Heart rate variability (HRV) is a rich source of information for studying the dynamics of this relation. Disturbed heart dynamics in depression seriously increases mortality risk. Technical sciences help improve early detection and monitoring and offer more accurate management of treatment. Based on advances in computational power, information theory, complex systems dynamics, and nonlinear analysis applied to physiological complexity, we can now turn to novel biomarkers extracted from electrophysiological signals. This work is a cross-sectional analysis with methodological commentary of application of nonlinear measures of HRV related to depression. Methods: We systematically searched online for papers exploring the connection of depression and HRV, using both conventional and nonlinear analysis. We scrutinized chosen publications and methodologically analyzed and compared them. Results: Sixty-seven publications on the connection of HRV measures and depression meeting our inclusion criteria are selected. The effectiveness of the applied methods of electrocardiogram (ECG) analysis are compared and discussed in the light of detection and prevention of depression-related cardiac diseases. Conclusions: It is clear that aberrated ANS dynamics can be detected via ECG analysis, where nonlinear measures show to be more sensitive and accurate than standard time and spectral ones. With the portable ECG devices and cloud-based telehealth applications, monitoring of outpatients could be done anytime anywhere. We appeal for early screening for cardiovascular abnormalities in depressive patients to prevent possible deleterious events.


title: Self-Learned Kernel Low Rank Approach TO Accelerated High Resolution 3D Diffusion MRI

abstract: Diffusion Magnetic Resonance Imaging (dMRI) is a promising method to analyze the subtle changes in the tissue structure. However, the lengthy acquisition time is a major limitation in the clinical application of dMRI. Different image acquisition techniques such as parallel imaging, compressed sensing, has shortened the prolonged acquisition time but creating high-resolution 3D dMRI slices still requires a significant amount of time. In this study, we have shown that high-resolution 3D dMRI can be reconstructed from the highly undersampled k-space and q-space data using a Kernel LowRank method. Our proposed method has outperformed the conventional CS methods in terms of both image quality and diffusion maps constructed from the diffusion-weighted images


title: Sums of random polynomials with differing degrees

abstract: Let $\mu$ and $\nu$ be probability measures in the complex plane, and let $p$ and $q$ be independent random polynomials of degree $n$, whose roots are chosen independently from $\mu$ and $\nu$, respectively. Under assumptions on the measures $\mu$ and $\nu$, the limiting distribution for the zeros of the sum $p+q$ was by computed by Reddy and the third author [J. Math. Anal. Appl. 495 (2021) 124719] as $n \to \infty$. In this paper, we generalize and extend this result to the case where $p$ and $q$ have different degrees. In this case, the logarithmic potential of the limiting distribution is given by the pointwise maximum of the logarithmic potentials of $\mu$ and $\nu$, scaled by the limiting ratio of the degrees of $p$ and $q$. Additionally, our approach provides a complete description of the limiting distribution for the zeros of $p + q$ for any pair of measures $\mu$ and $\nu$, with different limiting behavior shown in the case when at least one of the measures fails to have a logarithmic moment.


title: Large time well posedness for a Dirac--Klein-Gordon system

abstract: In this paper we prove well posedness for a system coupling a nonlinear Dirac with a Klein-Gordon equation that represents a toy model for the Helium atom with relativistic corrections: the wave function of the electrons interacts with an electric field generated by a nucleus with a given charge density. One of the main ingredients we need is a new family of Strichartz estimates for time dependent perturbations of the Dirac equation: these represent a result of independent interest.


title: A stretched exponential-based approach for the magnetic properties of spin glasses

abstract: The spin glasses show intriguing characteristic features that are not well understood yet, as for instance its aging, rejuvenation and memory effects. Here a model based on a stretched exponential decay of its magnetization is proposed, which can describe the main magnetic features of spin glasses observed in experiments as the time-decay of thermoremament magnetization, the relaxation of zero field cooled magnetization, the ac and dc magnetization as a function of temperature and others. In principle, the here proposed model could be adapted to describe other glassy systems.


title: Learning velocity model for complex media with deep convolutional neural networks

abstract: The paper considers the problem of velocity model acquisition for a complex media based on boundary measurements. The acoustic model is used to describe the media. We used an open-source dataset of velocity distributions to compare the presented results with the previous works directly. Forward modeling is performed using the grid-characteristic numerical method. The inverse problem is solved using deep convolutional neural networks. Modifications for a baseline UNet architecture are proposed to improve both structural similarity index measure quantitative correspondence of the velocity profiles with the ground truth. We evaluate our enhancements and demonstrate the statistical significance of the results.


title: Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits

abstract: We study the Pareto frontier of two archetypal objectives in multi-armed bandits, namely, regret minimization (RM) and best arm identification (BAI) with a fixed horizon. It is folklore that the balance between exploitation and exploration is crucial for both RM and BAI, but exploration is more critical in achieving the optimal performance for the latter objective. To this end, we design and analyze the BoBW-lil'UCB$(\gamma)$ algorithm. Complementarily, by establishing lower bounds on the regret achievable by any algorithm with a given BAI failure probability, we show that (i) no algorithm can simultaneously perform optimally for both the RM and BAI objectives, and (ii) BoBW-lil'UCB$(\gamma)$ achieves order-wise optimal performance for RM or BAI under different values of $\gamma$. Our work elucidates the trade-off more precisely by showing how the constants in previous works depend on certain hardness parameters. Finally, we show that BoBW-lil'UCB outperforms a close competitor UCB$_\alpha$ (Degenne et al., 2019) in terms of the time complexity and the regret on diverse datasets such as MovieLens and Published Kinase Inhibitor Set.


title: Protonium annihilation densities in a unitary coupled channel model

abstract: We consider a unitary coupled channel model to describe the low energy proton-antiproton scattering and the lower Coulomb-like protonium states. The existence of deeper quasi-bound states of nuclear nature is found to be a consequence of the experimental data. The properties of these states as well as the protonium annihilation densities are described and the difference with respect to the optical models description are manifested.


title: Black holes

abstract: Black holes are defined as a region in spacetime where gravity is so strong that particles and electromagnetic radiation cannot escape. According to their mass, they are classified into three types: stellar-mass black holes, intermediate-mass black holes, and supermassive black holes. This entry describes how to weight and detect these three types of black holes, summarizes key research findings such as the universality of black hole accretion and black hole-galaxy co-evolution, and gives an outlook to what the next generation of observational facilities will provide.


title: Star-shaped acceptability indexes

abstract: We propose the star-shaped acceptability indexes as generalizations of both the approaches of Cherny and Madan (2009) and Rosazza Gianin and Sgarra (2013) in the same vein as star-shaped risk measures generalize both the classes of coherent and convex risk measures in Castagnoli et al. (2022). We characterize acceptability indexes through star-shaped risk measures, star-shaped acceptance sets, and as the minimum of a family of quasi-concave acceptability indexes. Further, we introduce concrete examples under our approach linked to Value at Risk, risk-adjusted reward on capital, reward-based gain-loss ratio, monotone reward-deviation ratio, and robust acceptability indexes.


title: Learning Continuous Chaotic Attractors with a Reservoir Computer

abstract: Neural systems are well known for their ability to learn and store information as memories. Even more impressive is their ability to abstract these memories to create complex internal representations, enabling advanced functions such as the spatial manipulation of mental representations. While recurrent neural networks (RNNs) are capable of representing complex information, the exact mechanisms of how dynamical neural systems perform abstraction are still not well-understood, thereby hindering the development of more advanced functions. Here, we train a 1000-neuron RNN -- a reservoir computer (RC) -- to abstract a continuous dynamical attractor memory from isolated examples of dynamical attractor memories. Further, we explain the abstraction mechanism with new theory. By training the RC on isolated and shifted examples of either stable limit cycles or chaotic Lorenz attractors, the RC learns a continuum of attractors, as quantified by an extra Lyapunov exponent equal to zero. We propose a theoretical mechanism of this abstraction by combining ideas from differentiable generalized synchronization and feedback dynamics. Our results quantify abstraction in simple neural systems, enabling us to design artificial RNNs for abstraction, and leading us towards a neural basis of abstraction.


title: Sampling based Computation of Viability Domain to Prevent Safety Violations by Attackers

abstract: This paper studies the security of cyber-physical systems under attacks. Our goal is to design system parameters, such as a set of initial conditions and input bounds so that it is secure by design. To this end, we propose new sufficient conditions to guarantee the safety of a system under adversarial actuator attacks. Using these conditions, we propose a computationally efficient sampling-based method to verify whether a set is a viability domain for a general class of nonlinear systems. In particular, we devise a method of checking a modified barrier function condition on a finite set of points to assess whether a set can be rendered forward invariant. Then, we propose an iterative algorithm to compute the set of initial conditions and input constraint set to limit what an adversary can do if it compromises the vulnerable inputs. Finally, we utilize a Quadratic Program approach for online control synthesis.


title: Hydra: A System for Large Multi-Model Deep Learning

abstract: Scaling up model depth and size is now a common approach to raise accuracy in many deep learning (DL) applications, as evidenced by the widespread success of multi-billion or even trillion parameter models in natural language processing (NLP) research. Despite success in DL research and at major technology companies, broader practical adoption of such large models among domain scientists and businesses is still bottlenecked by GPU memory limits, high training costs, and low GPU availability, even on public clouds. Model selection needs further compound these resource challenges: users often need to compare dozens of models with different hyper-parameters or neural architectures to suit their specific task and dataset. In this paper, we present Hydra, a system designed to tackle such challenges by enabling out-of-the-box scaling for multi-large-model DL workloads on even commodity GPUs in a resource-efficient manner. Hydra is the first approach to holistically optimize the execution of multi-model workloads for large DL models. We do this by adapting prior "model-parallel" execution schemes to work with scalable parameter offloading across the memory hierarchy and further hybridizing this approach with task-parallel job scheduling techniques. Hydra decouples scalability of model parameters from parallelism of execution, thus enabling DL users to train even a 6-billion parameter model on a single commodity GPU. It also fully exploits the speedup potential of task parallelism in multi-GPU setups, yielding near-linear strong scaling and making rigorous model selection perhaps more practical for such models. We evaluate end-to-end performance by fine-tuning GPT-2 for language modeling. We find that Hydra offers between 50% and 100% higher training throughput than even the best settings of state-of-the-art industrial frameworks such as DeepSpeed and GPipe for multi-large-model training.


title: Towards Robust Waveform-Based Acoustic Models

abstract: We study the problem of learning robust acoustic models in adverse environments, characterized by a significant mismatch between training and test conditions. This problem is of paramount importance for the deployment of speech recognition systems that need to perform well in unseen environments. First, we characterize data augmentation theoretically as an instance of vicinal risk minimization, which aims at improving risk estimates during training by replacing the delta functions that define the empirical density over the input space with an approximation of the marginal population density in the vicinity of the training samples. More specifically, we assume that local neighborhoods centered at training samples can be approximated using a mixture of Gaussians, and demonstrate theoretically that this can incorporate robust inductive bias into the learning process. We then specify the individual mixture components implicitly via data augmentation schemes, designed to address common sources of spurious correlations in acoustic models. To avoid potential confounding effects on robustness due to information loss, which has been associated with standard feature extraction techniques (e.g., FBANK and MFCC features), we focus on the waveform-based setting. Our empirical results show that the approach can generalize to unseen noise conditions, with 150% relative improvement in out-of-distribution generalization compared to training using the standard risk minimization principle. Moreover, the results demonstrate competitive performance relative to models learned using a training sample designed to match the acoustic conditions characteristic of test utterances.


title: The SpECTRE Cauchy-characteristic evolution system for rapid, precise waveform extraction

abstract: We give full details regarding the new Cauchy-characteristic evolution (CCE) system in SpECTRE. The implementation is built to provide streamlined flexibility for either extracting waveforms during the process of a SpECTRE binary compact object simulation, or as a standalone module for extracting waveforms from worldtube data provided by another code base. Using our recently presented improved analytic formulation, the CCE system is free of pure-gauge logarithms that would spoil the spectral convergence of the scheme. It gracefully extracts all five Weyl scalars, in addition to the news and the strain. The SpECTRE CCE system makes significant improvements on previous implementations in modularity, ease of use, and speed of computation.


title: DPC: Unsupervised Deep Point Correspondence via Cross and Self Construction

abstract: We present a new method for real-time non-rigid dense correspondence between point clouds based on structured shape construction. Our method, termed Deep Point Correspondence (DPC), requires a fraction of the training data compared to previous techniques and presents better generalization capabilities. Until now, two main approaches have been suggested for the dense correspondence problem. The first is a spectral-based approach that obtains great results on synthetic datasets but requires mesh connectivity of the shapes and long inference processing time while being unstable in real-world scenarios. The second is a spatial approach that uses an encoder-decoder framework to regress an ordered point cloud for the matching alignment from an irregular input. Unfortunately, the decoder brings considerable disadvantages, as it requires a large amount of training data and struggles to generalize well in cross-dataset evaluations. DPC's novelty lies in its lack of a decoder component. Instead, we use latent similarity and the input coordinates themselves to construct the point cloud and determine correspondence, replacing the coordinate regression done by the decoder. Extensive experiments show that our construction scheme leads to a performance boost in comparison to recent state-of-the-art correspondence methods. Our code is publicly available at https://github.com/dvirginz/DPC.


title: Conceptual Modeling and Artificial Intelligence: Mutual Benefits from Complementary Worlds

abstract: Conceptual modeling (CM) applies abstraction to reduce the complexity of a system under study (e.g., an excerpt of reality). As a result of the conceptual modeling process a human interpretable, formalized representation (i.e., a conceptual model) is derived which enables understanding and communication among humans, and processing by machines. Artificial Intelligence (AI) algorithms are also applied to complex realities (regularly represented by vast amounts of data) to identify patterns or to classify entities in the data. Aside from the commonalities of both approaches, a significant difference can be observed by looking at the results. While conceptual models are comprehensible, reproducible, and explicit knowledge representations, AI techniques are capable of efficiently deriving an output from a given input while acting as a black box. AI solutions often lack comprehensiveness and reproducibility. Even the developers of AI systems can't explain why a certain output is derived. In the Conceptual Modeling meets Artificial Intelligence (CMAI) workshop, we are interested in tackling the intersection of the two, thus far, mostly isolated approached disciplines of CM and AI. The workshop embraces the assumption, that manifold mutual benefits can be realized by i) investigating what Conceptual Modeling (CM) can contribute to AI, and ii) the other way around, what Artificial Intelligence (AI) can contribute to CM.


title: Symmetry break in a scalar field theory in a $(1 + 1)$-spacetime

abstract: We consider in this work a relativistic scalar field theory in a $(1+1)$-Minkowski spacetime for a class of periodic potentials. These potentials exhibit solutions known as kinks and antikinks with topological charges, energy density, and mass dependent on the potential's parameters. We break the symmetry from a vacuum expectation value ($vev$) zero for a non-zero $vev$, which means that the supersymmetry (SUSY) has spontaneously broken.


title: Partial Hierarchical Pose Graph Optimization for SLAM

abstract: In this paper we consider a hierarchical pose graph optimization (HPGO) for Simultaneous Localization and Mapping (SLAM). We propose a fast incremental procedure for building hierarchy levels in pose graphs. We study the properties of this procedure and show that our solution delivers high execution speed, high reduction rate and good flexibility. We propose a way to do partial hierarchical optimization and compare it to other optimization modes. We show that given a comparatively large amount of poses, partial HPGO gives a 10x speed up comparing to the original optimization, not sacrificing the quality.


title: Is the twin prime conjecture independent of Peano Arithmetic?

abstract: We show that there is an arithmetical formula F such that ZF proves that F is independent of PA and yet, unlike other arithmetical independent statements, the truth value of F cannot at present be established in ZF or in any other trusted metatheory. In fact we can choose an example of such a formula F such that ZF proves that F is equivalent to the twin prime conjecture.


title: The complex timeless emergence of time in quantum gravity

abstract: We present the arguments suggesting that time is emergent in quantum gravity and discuss extensively, but without any technical detail, the many aspects that can be involved in such emergence. We refer to both the physical issues that need to be tackled, by quantum gravity formalisms, to realize concretely this emergent picture of time, and the conceptual challenges that have to be addressed in parallel to achieve a proper understanding of it.


title: Local Advantage Actor-Critic for Robust Multi-Agent Deep Reinforcement Learning

abstract: Policy gradient methods have become popular in multi-agent reinforcement learning, but they suffer from high variance due to the presence of environmental stochasticity and exploring agents (i.e., non-stationarity), which is potentially worsened by the difficulty in credit assignment. As a result, there is a need for a method that is not only capable of efficiently solving the above two problems but also robust enough to solve a variety of tasks. To this end, we propose a new multi-agent policy gradient method, called Robust Local Advantage (ROLA) Actor-Critic. ROLA allows each agent to learn an individual action-value function as a local critic as well as ameliorating environment non-stationarity via a novel centralized training approach based on a centralized critic. By using this local critic, each agent calculates a baseline to reduce variance on its policy gradient estimation, which results in an expected advantage action-value over other agents' choices that implicitly improves credit assignment. We evaluate ROLA across diverse benchmarks and show its robustness and effectiveness over a number of state-of-the-art multi-agent policy gradient algorithms.


title: Lectures on Lagrangian torus fibrations

abstract: This is a book aimed at graduate students and researchers in symplectic geometry, based on a course I taught in 2019. The primary message is that the base of a Lagrangian torus fibration inherits an integral affine structure, which you can use to "read off" a lot of interesting geometry of the total space. Topics covered include: action-angle coordinates, symplectic reduction, toric manifolds, visible and tropical Lagrangians, almost toric systems, Milnor fibres of cyclic quotient singularities, mutation of polygons, non-toric blow-up, an almost toric view on Lisca's classification of fillings of lens spaces, resolutions of cusp singularities, Markov triples and Vianna tori. The book ends with a short list of open problems. Throughout there is an emphasis on examples and there are some exercises with solutions.


title: Parker Solar Probe detects solar radio bursts related with a behind-the-limb active region

abstract: The interpretation of solar radio bursts observed by Parker Solar Probe (PSP) in the encounter phase plays a key role in understanding intrinsic properties of the emission mechanism in the solar corona. Lower time-frequency resolution of the PSP receiver can be overcome by simultaneous ground-based observations using more advanced antennas and receivers. In this paper we present such observations for which the active active region 12765, begetter of type III, J, and U solar bursts, was within sight of ground-based instruments and behind the solar limb of the PSP spacecraft. We used a subarray of the Giant Ukrainian Radio Telescope (GURT) to get the spectral properties of radio bursts at the frequency range of 8-80 MHz, as well as the PSP radio instruments with a bandwidth of 10.5 kHz - 19.2 MHz, during solar observations on June 5, 2020. We directly detected the radio events initiated by the active region behind the solar limb of the PSP spacecraft, using special conditions in the solar corona, due to the absence of active regions from the PSP side. Following the generation mechanism of solar radio emission, we refined the density model for the solar corona above the active region 12765 responsible for the radio bursts. Based on the PSP spacecraft position near the Sun and delays of radio waves between space- and ground-based records, we found the corresponding radio responses on the PSP spectrogram. The absence of sunspots from the PSP side contributes to the propagation of radio waves from a dense loop of the Sun to quiet regions with low densities, through which PSP instruments can detect the radiation.


title: Modelling Behaviour Change using Cognitive Agent Simulations

abstract: In health psychology, Behaviour Change Theories(BCTs) play an important role in modelling human goal achievement in adverse environments. Some of these theories use concepts that are also used in computational modelling of cognition and affect in AI. Examples include dual-process architecture and models of motivation. It is therefore important to ask whether some BCTs can be computationally implemented as cognitive agents in a way that builds on existing AI research in cognitive architecture. This paper presents work-in-progress research to apply selected behaviour change theories to simulated agents, so that an agent is acting according to the theory while attempting to complete a task in a challenging scenario. Two behaviour change theories are selected as examples (CEOS and PRIME). The research is focusing on complex agent architectures required for self-determined goal achievement in adverse circumstances where the action is difficult to maintain (e.g. healthy eating at office parties). Such simulations are useful because they can provide new insights into human behaviour change and improve conceptual precision. In addition, they can act as a rapid-prototyping environment for technology development. High-level descriptive simulations also provide an opportunity for transparency and participatory design, which is important for user ownership of the behaviour change process.


title: Renormalization Scheme Dependence of $\beta$-Functions In Lorentz-Violating Quantum Field Theory

abstract: Effective quantum field theories that allow for the possibility of Lorentz symmetry violation can sometimes also include redundancies of description in their Lagrangians. Explicit calculations in a Lorentz-violating generalization of Yukawa theory show that when this kind of redundancy exists, different renormalization schemes may lead to different expressions for the renormalization group $\beta$-functions, even at only one-loop order. However, the renormalization group scaling of physically observable quantities appears not to share this kind of scheme dependence.


title: Tropical fans and normal complexes

abstract: Associated to any divisor in the Chow ring of a simplicial tropical fan, we construct a family of polytopal complexes, called normal complexes, which we propose as an analogue of the well-studied notion of normal polytopes from the setting of complete fans. We describe certain closed convex polyhedral cones of divisors for which the "volume" of each divisor in the cone - that is, the degree of its top power - is equal to the volume of the associated normal complexes. For the Bergman fan of any matroid with building set, we prove that there exists an open family of such cones of divisors with nonempty interiors. We view the theory of normal complexes developed in this paper as a polytopal model underlying the combinatorial Hodge theory pioneered by Adiprasito, Huh, and Katz.


title: Minding non-collapsibility of odds ratios when recalibrating risk prediction models

abstract: In clinical prediction modeling, model updating refers to the practice of modifying a prediction model before it is used in a new setting. In the context of logistic regression for a binary outcome, one of the simplest updating methods is a fixed odds-ratio transformation of predicted risks to improve calibration-in-the-large. Previous authors have proposed equations for calculating this odds-ratio based on the discrepancy between the prevalence in the original and the new population, or between the average of predicted and observed risks. We show that this method fails to consider the non-collapsibility of odds-ratio. Consequently, it under-corrects predicted risks, especially when predicted risks are more dispersed (i.e., for models with good discrimination). We suggest an approximate equation for recovering the conditional odds-ratio from the mean and variance of predicted risks. Brief simulations and a case study show that this approach reduces under-correction, sometimes substantially. R code for implementation is provided.


title: Equivariant Finite Normalizing Flows

abstract: Generative modeling seeks to uncover the underlying factors that give rise to observed data that can often be modeled as the natural symmetries that manifest themselves through invariances and equivariances to certain transformation laws. However, current approaches to representing these symmetries are couched in the formalism of continuous normalizing flows that require the construction of equivariant vector fields -- inhibiting their simple application to conventional higher dimensional generative modelling domains like natural images. In this paper, we focus on building equivariant normalizing flows using discrete layers. We first theoretically prove the existence of an equivariant map for compact groups whose actions are on compact spaces. We further introduce three new equivariant flows: $G$-Residual Flows, $G$-Coupling Flows, and $G$-Inverse Autoregressive Flows that elevate classical Residual, Coupling, and Inverse Autoregressive Flows with equivariant maps to a prescribed group $G$. Our construction of $G$-Residual Flows are also universal, in the sense that we prove an $G$-equivariant diffeomorphism can be exactly mapped by a $G$-residual flow. Finally, we complement our theoretical insights with demonstrative experiments -- for the first time -- on image datasets like CIFAR-10 and show $G$-Equivariant Finite Normalizing flows lead to increased data efficiency, faster convergence, and improved likelihood estimates.


title: Challenges Porting a C++ Template-Metaprogramming Abstraction Layer to Directive-based Offloading

abstract: HPC systems employ a growing variety of compute accelerators with different architectures and from different vendors. Large scientific applications are required to run efficiently across these systems but need to retain a single code-base in order to not stifle development. Directive-based offloading programming models set out to provide the required portability, but, to existing codes, they themselves represent yet another API to port to. Here, we present our approach of porting the GPU-accelerated particle-in-cell code PIConGPU to OpenACC and OpenMP target by adding two new backends to its existing C++-template metaprogramming-based offloading abstraction layer alpaka and avoiding other modifications to the application code. We introduce our approach in the face of conflicts between requirements and available features in the standards as well as practical hurdles posed by immature compiler support.


title: The Dark $Z'$ and Sterile Neutrinos Behind Current Anomalies

abstract: We show how, in the $B-L$ extension of the SM (BLSM) with an Inverse Seesaw (IS) mechanism for neutrino mass generation, a light $Z'$ state with moderate couplings to SM objects, hence `dark' in its nature, can be associated, in conjunction with light sterile neutrinos, to some present day data anomalies, such as the anomalous magnetic moment of the muon as well as a possible signal indicating the existence of sterile neutrinos in neutrino beam experiments.


title: Defining an Affine Partition Algebra

abstract: We define an affine partition algebra by generators and relations and prove a variety of basic results regarding this new algebra analogous to those of other affine diagram algebras. In particular we show that it extends the Schur-Weyl duality between the symmetric group and the partition algebra. We also relate it to the affine partition category recently defined by J. Brundan and M. Vargas. Moreover, we show that this affine partition category is a full monoidal subcategory of the Heisenberg category.


title: Learning UI Navigation through Demonstrations composed of Macro Actions

abstract: We have developed a framework to reliably build agents capable of UI navigation. The state space is simplified from raw-pixels to a set of UI elements extracted from screen understanding, such as OCR and icon detection. The action space is restricted to the UI elements plus a few global actions. Actions can be customized for tasks and each action is a sequence of basic operations conditioned on status checks. With such a design, we are able to train DQfD and BC agents with a small number of demonstration episodes. We propose demo augmentation that significantly reduces the required number of human demonstrations. We made a customization of DQfD to allow demos collected on screenshots to facilitate the demo coverage of rare cases. Demos are only collected for the failed cases during the evaluation of the previous version of the agent. With 10s of iterations looping over evaluation, demo collection, and training, the agent reaches a 98.7\% success rate on the search task in an environment of 80+ apps and websites where initial states and viewing parameters are randomized.


title: LEO Satellites in 5G and Beyond Networks: A Review from a Standardization Perspective

abstract: Low Earth Orbit (LEO) Satellite Network (SatNet) with their mega-constellations are expected to play a key role in providing ubiquitous Internet and communications services in the future. LEO SatNets will provide wide-area coverage and support service availability, continuity, and scalability. To support the integration of SatNets and terrestrial Fifth Generation (5G)networks and beyond, the satellite communication industry has become increasingly involved with the 3rd Generation Partnership Project (3GPP) standardization activities for 5G. In this work, we review the 3GPP standardization activities for the integration of SatNets in 5G and beyond. The 3GPP use cases of SatNets are highlighted and potential requirements to realize them are summarized as well. The impacted areas of New Radio(NR) are discussed with some potential solutions. The foreseen requirements for the management and orchestration of SatNets within 5G are described. Future standardization directions are discussed to support the full integration of SatNets in SixthGeneration (6G) with the goal of ubiquitous global connectivity.


title: Zodiacal Exoplanets in Time (ZEIT) XII: A Directly-Imaged Planetary-Mass Companion to a Young Taurus M Dwarf Star

abstract: We report the discovery of a resolved (0".9) substellar companion to a member of the 1-5 Myr Taurus star-forming region. The host star (2M0437) is a single mid-M type ($T_{eff}\approx$3100K) dwarf with a position, space motion, and color-magnitude that support Taurus membership, and possible affiliation with a $\sim$2.5 Myr-old sub-group. A comparison with stellar models suggests a 2-5 Myr age and a mass of 0.15-0.18M$_{\odot}$. Although K2 detected quasi-periodic dimming from close-in circumstellar dust, the star lacks detectable excess infrared emission from a circumstellar disk and its H$\alpha$ emission is not commensurate with accretion. Astrometry based on three years of AO imaging shows that the companion (2M0437b) is co-moving, while photometry of two other sources at larger separation indicates they are likely heavily-reddened background stars. A comparison of the luminosity of 2M0437b with models suggests a mass of 3-5$M_{\rm jup}$, well below the deuterium burning limit, and an effective temperature of 1400-1500K, characteristic of a late L spectral type. The $H$-$K$ color is redder than the typical L dwarf, but comparable to other directly detected young planets, e.g. those around HR 8799. The discovery of a super-Jupiter around a very young, very low mass star challenges models of planet formation by either core accretion (which requires time) or disk instability (which requires mass). We also detected a second, co-moving, widely-separated (75") object which appears to be a heavily-extincted star. This is certainly a fellow member of this Taurus sub-group and statistically likely to be a bound companion.


title: Newton Polygons of Sums on Curves I: Local-to-Global Theorems

abstract: The purpose of this article is to study Newton polygons of certain abelian $L$-functions on curves. Let $X$ be a smooth affine curve over a finite field $\mathbb{F}_q$ and let $\rho:\pi_1(X) \to \mathbb{C}_p^\times$ be a finite character of order $p^n$. By previous work of the first author, the Newton polygon $\mathrm{NP}(\rho)$ lies above a `Hodge polygon' $\mathrm{HP}(\rho)$, which is defined using local ramification invariants of $\rho$. In this article we study the touching between these two polygons. We prove that $\mathrm{NP}(\rho)$ and $\mathrm{HP}(\rho)$ share a vertex if and only if a corresponding vertex is shared between the Newton and Hodge polygons of `local' $L$-functions associated to each ramified point of $\rho$. As a consequence, we determine a necessary and sufficient condition for the coincidence of $\mathrm{NP}(\rho)$ and $\mathrm{HP}(\rho)$.


title: Newton Polygons of Sums on Curves II: Variation in $p$-adic Families

abstract: In this article we study the behavior of Newton polygons along $\mathbb{Z}_p$-towers of curves. Fix an ordinary curve $X$ over a finite field $\mathbb{F}_q$ of characteristic $p$. By a $\mathbb{Z}_p$-tower $X_\infty/X$ we mean a tower of covers $ \dots \to X_2 \to X_1 \to X$ with $\mathrm{Gal}(X_n/X) \cong \mathbb{Z}/p^n\mathbb{Z}$. We show that if the ramification along the tower is sufficiently moderate, then the slopes of the Newton polygon of $X_n$ are equidistributed in the interval $[0,1]$ as $n$ tends to $\infty$. Under a stronger congruence assumption on the ramification invariants, we completely determine the slopes of the Newton polygon of each curve. This is the first result towards `regularity' in Newton polygon behavior for $\mathbb{Z}_p$-towers over higher genus curves. We also obtain similar results for $\mathbb{Z}_p$-towers twisted by a generic tame character.


title: Dynamic Compressed Sensing of Unsteady Flows with a Mobile Robot

abstract: Large-scale environmental sensing with a finite number of mobile sensors is a challenging task that requires a lot of resources and time. This is especially true when features in the environment are spatiotemporally changing with unknown or partially known dynamics. Fortunately, these dynamic features often evolve in a low-dimensional space, making it possible to capture their dynamics sufficiently well with only one or several properly planned mobile sensors. This paper investigates the problem of dynamic compressed sensing of an unsteady flow field, which takes advantage of the inherently low dimensionality of the underlying flow dynamics to reduce number of waypoints for a mobile sensing robot. The optimal sensing waypoints are identified by an iterative compressed sensing algorithm that optimizes the flow reconstruction based on the proper orthogonal decomposition modes. An optimal sampling trajectory is then found to traverse these waypoints while minimizing the energy consumption, time, and flow reconstruction error. Simulation results in an unsteady double gyre flow field is presented to demonstrate the efficacy of the proposed algorithms. Experimental results with an indoor quadcopter are presented to show the feasibility of the resulting trajectory.


title: $L_p$-Steiner quermassintegrals

abstract: Inspired by an $L_p$ Steiner formula for the $L_p$ affine surface area proved by Tatarko and Werner, we define, in analogy to the classical Steiner formula, $L_p$-Steiner quermassintegrals. Special cases include the classical mixed volumes, the dual mixed volumes, the $L_p$ affine surface areas and the mixed $L_p$ affine surface areas. We investigate the properties of the $L_p$-Steiner quermassintegrals in a special class of convex bodies. In particular, we show that they are rotation and reflection invariant valuations in this class of convex bodies with a certain degree of homogeneity. Such valuations seem new and have not been observed before.


title: Formation of multiple flocks in a simple nonlocal aggregation model

abstract: We consider a family of interaction energies given by kernels having a ''well-barrier'' shape, and investigate how these kernels drive the formation of multiple flocks within a larger population. We use the dichotomy case of the concentration compactness principle to obtain an energy minimizer, even though minimizing sequences are expected to break apart into flocks which may move far away from one another.


title: Making existing software quantum safe: a case study on IBM Db2

abstract: The software engineering community is facing challenges from quantum computers (QCs). In the era of quantum computing, Shor's algorithm running on QCs can break asymmetric encryption algorithms that classical computers practically cannot. Though the exact date when QCs will become "dangerous" for practical problems is unknown, the consensus is that this future is near. Thus, the software engineering community needs to start making software ready for quantum attacks and ensure quantum safety proactively. We argue that the problem of evolving existing software to quantum-safe software is very similar to the Y2K bug. Thus, we leverage some best practices from the Y2K bug and propose our roadmap, called 7E, which gives developers a structured way to prepare for quantum attacks. It is intended to help developers start planning for the creation of new software and the evolution of cryptography in existing software. In this paper, we use a case study to validate the viability of 7E. Our software under study is the IBM Db2 database system. We upgrade the current cryptographic schemes to post-quantum cryptographic ones (using Kyber and Dilithium schemes) and report our findings and lessons learned. We show that the 7E roadmap effectively plans the evolution of existing software security features towards quantum safety, but it does require minor revisions. We incorporate our experience with IBM Db2 into the revised 7E roadmap. The U.S. Department of Commerce's National Institute of Standards and Technology is finalizing the post-quantum cryptographic standard. The software engineering community needs to start getting prepared for the quantum advantage era. We hope that our experiential study with IBM Db2 and the 7E roadmap will help the community prepare existing software for quantum attacks in a structured manner.


title: An Effective Attack Scenario Construction Model based on Attack Steps and Stages Identification

abstract: A Network Intrusion Detection System (NIDS) is a network security technology for detecting intruder attacks. However, it produces a great amount of low-level alerts which makes the analysis difficult, especially to construct the attack scenarios. Attack scenario construction (ASC) via Alert Correlation (AC) is important to reveal the strategy of attack in terms of steps and stages that need to be launched to make the attack successful. In most of the existing works, alerts are correlated by classifying the alerts based on the cause-effect relationship. However, the drawback of these works is the identification of false and incomplete correlations due to the infiltration of raw alerts. To address this problem, this work proposes an effective ASC model to discover the complete relationship among alerts. The model is successfully experimented using two types of datasets, which are DARPA 2000, and ISCX2012. The Completeness and Soundness of the proposed model are measured to evaluate the overall correlation effectiveness.


title: Polycyclic aromatic hydrocarbons and the ionized gas

abstract: We present a study for a sample of galaxies with active nuclei to characterize the main type of PAH molecules present in these objects and the local physical conditions of their irradiating sources, as well as the characteristics of the residing ionized gas, by combining optical and infrared data. Photoionization models were built with the {\sc CLOUDY} code to reproduce optical emission line ratios in combination with PAH intensity ratios. We find that the species containing 10 $-$ 82 carbon atoms are the most abundant in the sample. We suggest that family of species with only two or three fused rings of and a nitrogen hanging, such as small aromatic amides are important targets worthy of consideration in future experimental/theoretical as well as observational studies. We find that the AGN photoionization models reproduce most of the observational data in the log (6.2/11.3) versus log ([\ion{N}{ii}]$\lambda$6584/H$\alpha$) diagram with the optical to X-ray spectral index of $\alpha_{\rm ox}=-1.4$. The flux of small PAH, as well as the flux of ionized PAHs and PANH, decrease as the logarithm of the ionization parameter (log $U$) increases. The 6.2/11.3 PAH intensity ratio presents anti correlation between the oxygen abundance and log $U$, in the sense that the 6.2/11.3 ratio decreases as the oxygen abundance and log $U$ increases. Finally, we found that the ionization degree of PAH species increases with the decreasing of the 11.3/7.7 ratio and the log U, in agreement with the models proposed by Draine \& Li.


title: Finding Critical Scenarios for Automated Driving Systems: A Systematic Literature Review

abstract: Scenario-based approaches have been receiving a huge amount of attention in research and engineering of automated driving systems. Due to the complexity and uncertainty of the driving environment, and the complexity of the driving task itself, the number of possible driving scenarios that an ADS or ADAS may encounter is virtually infinite. Therefore it is essential to be able to reason about the identification of scenarios and in particular critical ones that may impose unacceptable risk if not considered. Critical scenarios are particularly important to support design, verification and validation efforts, and as a basis for a safety case. In this paper, we present the results of a systematic literature review in the context of autonomous driving. The main contributions are: (i) introducing a comprehensive taxonomy for critical scenario identification methods; (ii) giving an overview of the state-of-the-art research based on the taxonomy encompassing 86 papers between 2017 and 2020; and (iii) identifying open issues and directions for further research. The provided taxonomy comprises three main perspectives encompassing the problem definition (the why), the solution (the methods to derive scenarios), and the assessment of the established scenarios. In addition, we discuss open research issues considering the perspectives of coverage, practicability, and scenario space explosion.


title: Quantile Regression by Dyadic CART

abstract: In this paper we propose and study a version of the Dyadic Classification and Regression Trees (DCART) estimator from Donoho (1997) for (fixed design) quantile regression in general dimensions. We refer to this proposed estimator as the QDCART estimator. Just like the mean regression version, we show that a) a fast dynamic programming based algorithm with computational complexity $O(N \log N)$ exists for computing the QDCART estimator and b) an oracle risk bound (trading off squared error and a complexity parameter of the true signal) holds for the QDCART estimator. This oracle risk bound then allows us to demonstrate that the QDCART estimator enjoys adaptively rate optimal estimation guarantees for piecewise constant and bounded variation function classes. In contrast to existing results for the DCART estimator which requires subgaussianity of the error distribution, for our estimation guarantees to hold we do not need any restrictive tail decay assumptions on the error distribution. For instance, our results hold even when the error distribution has no first moment such as the Cauchy distribution. Apart from the Dyadic CART method, we also consider other variant methods such as the Optimal Regression Tree (ORT) estimator introduced in Chatterjee and Goswami (2019). In particular, we also extend the ORT estimator to the quantile setting and establish that it enjoys analogous guarantees. Thus, this paper extends the scope of these globally optimal regression tree based methodologies to be applicable for heavy tailed data. We then perform extensive numerical experiments on both simulated and real data which illustrate the usefulness of the proposed methods.


title: Barrel Instability in Binary Asteroids

abstract: Most close-in planetary satellites are in synchronous rotation, which is usually the stable end-point of tidal despinning. Saturn's moon Hyperion is a notable exception by having a chaotic rotation. Hyperion's dynamical state is a consequence of its high eccentricity and its highly prolate shape (Wisdom et al. 1984). As many binary asteroids also have elongated secondaries, chaotic rotation is expected for moons in eccentric binaries (\'Cuk and Nesvorn\'y, 2010), and a minority of asteroidal secondaries may be in that state (Pravec et al. 2016). The question of secondary rotation is also important for the action of the BYORP effect, which can quickly evolve orbits of synchronous (but not non-synchronous) secondaries (\'Cuk and Burns, 2005). Here we report results of a large set of short numerical simulations which indicate that, apart from synchronous and classic chaotic rotation, close-in irregularly-shaped asteroidal secondaries can occupy an additional, intermediate rotational state. In this ``barrel instability'' the secondary slowly rolls along its long axis, while the longest axis is staying largely aligned with the primary-secondary line. This behavior may be more difficult to detect through lightcurves than a fully chaotic rotation, but would likewise shut down BYORP. We show that the binary's eccentricity, separation measured in secondary's radii and the secondary's shape are all important for determining whether the system settles in synchronous rotation, chaotic tumbling, or barrel instability. We compare our results for synthetic asteroids with known binary pairs to determine which of these behaviors may be present in the Near-Earth Asteroid binary population.


title: Face Verification with Challenging Imposters and Diversified Demographics

abstract: Face verification aims to distinguish between genuine and imposter pairs of faces, which include the same or different identities, respectively. The performance reported in recent years gives the impression that the task is practically solved. Here, we revisit the problem and argue that existing evaluation datasets were built using two oversimplifying design choices. First, the usual identity selection to form imposter pairs is not challenging enough because, in practice, verification is needed to detect challenging imposters. Second, the underlying demographics of existing datasets are often insufficient to account for the wide diversity of facial characteristics of people from across the world. To mitigate these limitations, we introduce the $FaVCI2D$ dataset. Imposter pairs are challenging because they include visually similar faces selected from a large pool of demographically diversified identities. The dataset also includes metadata related to gender, country and age to facilitate fine-grained analysis of results. $FaVCI2D$ is generated from freely distributable resources. Experiments with state-of-the-art deep models that provide nearly 100\% performance on existing datasets show a significant performance drop for $FaVCI2D$, confirming our starting hypothesis. Equally important, we analyze legal and ethical challenges which appeared in recent years and hindered the development of face analysis research. We introduce a series of design choices which address these challenges and make the dataset constitution and usage more sustainable and fairer. $FaVCI2D$ is available at~\url{https://github.com/AIMultimediaLab/FaVCI2D-Face-Verification-with-Challenging-Imposters-and-Diversified-Demographics}.


title: Fast Strain Estimation and Frame Selection in Ultrasound Elastography using Machine Learning

abstract: Ultrasound Elastography aims to determine the mechanical properties of the tissue by monitoring tissue deformation due to internal or external forces. Tissue deformations are estimated from ultrasound radio frequency (RF) signals and are often referred to as time delay estimation (TDE). Given two RF frames I1 and I2, we can compute a displacement image which shows the change in the position of each sample in I1 to a new position in I2. Two important challenges in TDE include high computational complexity and the difficulty in choosing suitable RF frames. Selecting suitable frames is of high importance because many pairs of RF frames either do not have acceptable deformation for extracting informative strain images or are decorrelated and deformation cannot be reliably estimated. Herein, we introduce a method that learns 12 displacement modes in quasi-static elastography by performing Principal Component Analysis (PCA) on displacement fields of a large training database. In the inference stage, we use dynamic programming (DP) to compute an initial displacement estimate of around 1% of the samples, and then decompose this sparse displacement into a linear combination of the 12 displacement modes. Our method assumes that the displacement of the whole image could also be described by this linear combination of principal components. We then use the GLobal Ultrasound Elastography (GLUE) method to fine-tune the result yielding the exact displacement image. Our method, which we call PCA-GLUE, is more than 10 times faster than DP in calculating the initial displacement map while giving the same result. Our second contribution in this paper is determining the suitability of the frame pair I1 and I2 for strain estimation, which we achieve by using the weight vector that we calculated for PCA-GLUE as an input to a multi-layer perceptron (MLP) classifier.


title: Constructing Many Faces in Arrangements of Lines and Segments

abstract: We present new algorithms for computing many faces in arrangements of lines and segments. Given a set $S$ of $n$ lines (resp., segments) and a set $P$ of $m$ points in the plane, the problem is to compute the faces of the arrangements of $S$ that contain at least one point of $P$. For the line case, we give a deterministic algorithm of $O(m^{2/3}n^{2/3}\log^{2/3} (n/\sqrt{m})+(m+n)\log n)$ time. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of $\log^{2.22}n$ and improves the previously best randomized algorithm [Agarwal, Matou\v{s}ek, and Schwarzkopf, 1998] by a factor of $\log^{1/3}n$ in certain cases (e.g., when $m=\Theta(n)$). For the segment case, we present a deterministic algorithm of $O(n^{2/3}m^{2/3}\log n+\tau(n\alpha^2(n)+n\log m+m)\log n)$ time, where $\tau=\min\{\log m,\log (n/\sqrt{m})\}$ and $\alpha(n)$ is the inverse Ackermann function. This improves the previously best deterministic algorithm [Agarwal, 1990] by a factor of $\log^{2.11}n$ and improves the previously best randomized algorithm [Agarwal, Matou\v{s}ek, and Schwarzkopf, 1998] by a factor of $\log n$ in certain cases (e.g., when $m=\Theta(n)$). We also give a randomized algorithm of $O(m^{2/3}K^{1/3}\log n+\tau(n\alpha(n)+n\log m+m)\log n\log K)$ expected time, where $K$ is the number of intersections of all segments of $S$. In addition, we consider the query version of the problem, that is, preprocess $S$ to compute the face of the arrangement of $S$ that contains any query point. We present new results that improve the previous work for both the line and the segment cases.


title: Upper Bounds on Resolvent Degree via Sylvester's Obliteration Algorithm

abstract: For each $n$, let RD$(n)$ denote the minimum $d$ for which there exists a formula for the general polynomial of degree $n$ in algebraic functions of at most $d$ variables. In this paper, we recover an algorithm of Sylvester for determining non-zero solutions of systems of homogeneous polynomials, which we present from a modern algebro-geometric perspective. We then use this geometric algorithm to determine improved thresholds for upper bounds on RD$(n)$.


title: Blockchain and Federated Edge Learning for Privacy-Preserving Mobile Crowdsensing

abstract: Mobile crowdsensing (MCS) counting on the mobility of massive workers helps the requestor accomplish various sensing tasks with more flexibility and lower cost. However, for the conventional MCS, the large consumption of communication resources for raw data transmission and high requirements on data storage and computing capability hinder potential requestors with limited resources from using MCS. To facilitate the widespread application of MCS, we propose a novel MCS learning framework leveraging on blockchain technology and the new concept of edge intelligence based on federated learning (FL), which involves four major entities, including requestors, blockchain, edge servers and mobile devices as workers. Even though there exist several studies on blockchain-based MCS and blockchain-based FL, they cannot solve the essential challenges of MCS with respect to accommodating resource-constrained requestors or deal with the privacy concerns brought by the involvement of requestors and workers in the learning process. To fill the gaps, four main procedures, i.e., task publication, data sensing and submission, learning to return final results, and payment settlement and allocation, are designed to address major challenges brought by both internal and external threats, such as malicious edge servers and dishonest requestors. Specifically, a mechanism design based data submission rule is proposed to guarantee the data privacy of mobile devices being truthfully preserved at edge servers; consortium blockchain based FL is elaborated to secure the distributed learning process; and a cooperation-enforcing control strategy is devised to elicit full payment from the requestor. Extensive simulations are carried out to evaluate the performance of our designed schemes.


title: Variational Modeling of Paperboard Delamination Under Bending

abstract: We develop and analyze a variational model for multi-ply (i.e., multi-layered) paperboard. The model consists of a number of elastic sheets of a given thickness, which -- at the expense of an energy per unit area -- may delaminate. By providing an explicit construction for possible admissible deformations subject to boundary conditions that introduce a single bend, we discover a rich variety of energetic regimes. The regimes correspond to the experimentally observed: initial purely elastic response for small bending angle and the formation of a localized inelastic, delaminated hinge once the angle reaches a critical value. Our scaling upper bound then suggests the occurrence of several additional regimes as the angle increases. The upper bounds for the energy are partially matched by scaling lower bounds.


title: Scaling Blockchains: Can Committee-Based Consensus Help?

abstract: In the high-stakes race to develop more scalable blockchains, some platforms (Binance, Cosmos, EOS, TRON, etc.) have adopted committee-based consensus (CBC) protocols, whereby the blockchain's record-keeping rights are entrusted to a committee of elected block producers. In theory, the smaller the committee, the faster the blockchain can reach consensus and the more it can scale. What's less clear, is whether such protocols ensure that honest committees can be consistently elected, given blockchain users typically have limited information on who to vote for. We show that the approval voting mechanism underlying most CBC protocols is complex and can lead to intractable optimal voting strategies. We empirically characterize some simpler intuitive voting strategies that users tend to resort to in practice and prove that these nonetheless converge to optimality exponentially quickly in the number of voters. Exponential convergence ensures that despite its complexity, CBC exhibits robustness and has some efficiency advantages over more popular staked-weighted lottery protocols currently underlying many prominent blockchains such as Ethereum.

categories: cs.CR cs.GT cs.IT econ.GN math.IT q-fin.EC q-fin.TR


title: Addendum to "Bounded Isometries and Homogeneous Quotients", JGA 27 (2017), 56--64

abstract: An argument of Y. Nikonorov completes the proof of Theorem 2.5 in "Bounded Isometries and Homogeneous Quotients", JGA 27 (2017), 56--64 [arXiv:1502.04276].


title: Sudden appearance of a thick Dirichlet wall in a cavity

abstract: We investigate the vacuum properties of a massless scalar field theory in constrained spatial geometry, namely, the instantaneous appearance of a thick Dirichlet boundary inside a one-dimensional (1D) Dirichlet cavity and divides it into two parts. Our work presents the calculations for the energy density and particle number density created. The expression of the energy density is found to be dependent on the size nature of the appearing wall, more precisely, it depends on whether the length of the wall is rational or irrational.


title: Noise-Augmented Privacy-Preserving Empirical Risk Minimization with Dual-purpose Regularizer and Privacy Budget Retrieval and Recycling

abstract: We propose Noise-Augmented Privacy-Preserving Empirical Risk Minimization (NAPP-ERM) that solves ERM with differential privacy guarantees. Existing privacy-preserving ERM approaches may be subject to over-regularization with the employment of an l2 term to achieve strong convexity on top of the target regularization. NAPP-ERM improves over the current approaches and mitigates over-regularization by iteratively realizing target regularization through appropriately designed augmented data and delivering strong convexity via a single adaptively weighted dual-purpose l2 regularizer. When the target regularization is for variable selection, we propose a new regularizer that achieves both privacy and sparsity guarantees simultaneously. Finally, we propose a strategy to retrieve privacy budget when the strong convexity requirement is met, which can be returned to users such that the DP of ERM is guaranteed at a lower privacy cost than originally planned, or be recycled to the ERM optimization procedure to reduce the injected DP noise and improve the utility of DP-ERM. From an implementation perspective, NAPP-ERM can be achieved by optimizing a non-perturbed object function given noise-augmented data and can thus leverage existing tools for non-private ERM optimization. We illustrate through extensive experiments the mitigation effect of the over-regularization and private budget retrieval by NAPP-ERM on variable selection and prediction.


title: Algorithmic Thresholds for Refuting Random Polynomial Systems

abstract: Consider a system of $m$ polynomial equations $\{p_i(x) = b_i\}_{i \leq m}$ of degree $D\geq 2$ in $n$-dimensional variable $x \in \mathbb{R}^n$ such that each coefficient of every $p_i$ and $b_i$s are chosen at random and independently from some continuous distribution. We study the basic question of determining the smallest $m$ -- the algorithmic threshold -- for which efficient algorithms can find refutations (i.e. certificates of unsatisfiability) for such systems. This setting generalizes problems such as refuting random SAT instances, low-rank matrix sensing and certifying pseudo-randomness of Goldreich's candidate generators and generalizations. We show that for every $d \in \mathbb{N}$, the $(n+m)^{O(d)}$-time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever $m \geq O(n) \cdot (\frac{n}{d})^{D-1}$. We prove a lower bound in the restricted low-degree polynomial model of computation which suggests that this trade-off between SoS degree and the number of equations is nearly tight for all $d$. We also confirm the predictions of this lower bound in a limited setting by showing a lower bound on the canonical degree-$4$ sum-of-squares relaxation for refuting random quadratic polynomials. Together, our results provide evidence for an algorithmic threshold for the problem at $m \gtrsim \widetilde{O}(n) \cdot n^{(1-\delta)(D-1)}$ for $2^{n^{\delta}}$-time algorithms for all $\delta$.


title: Improving Transformers with Probabilistic Attention Keys

abstract: Multi-head attention is a driving force behind state-of-the-art transformers, which achieve remarkable performance across a variety of natural language processing (NLP) and computer vision tasks. It has been observed that for many applications, those attention heads learn redundant embedding, and most of them can be removed without degrading the performance of the model. Inspired by this observation, we propose Transformer with a Mixture of Gaussian Keys (Transformer-MGK), a novel transformer architecture that replaces redundant heads in transformers with a mixture of keys at each head. These mixtures of keys follow a Gaussian mixture model and allow each attention head to focus on different parts of the input sequence efficiently. Compared to its conventional transformer counterpart, Transformer-MGK accelerates training and inference, has fewer parameters, and requires fewer FLOPs to compute while achieving comparable or better accuracy across tasks. Transformer-MGK can also be easily extended to use with linear attention. We empirically demonstrate the advantage of Transformer-MGK in a range of practical applications, including language modeling and tasks that involve very long sequences. On the Wikitext-103 and Long Range Arena benchmark, Transformer-MGKs with 4 heads attain comparable or better performance to the baseline transformers with 8 heads.


title: An Acceleration Method Based on Deep Learning and Multilinear Feature Space

abstract: Computer vision plays a crucial role in Advanced Assistance Systems. Most computer vision systems are based on Deep Convolutional Neural Networks (deep CNN) architectures. However, the high computational resource to run a CNN algorithm is demanding. Therefore, the methods to speed up computation have become a relevant research issue. Even though several works on architecture reduction found in the literature have not yet been achieved satisfactory results for embedded real-time system applications. This paper presents an alternative approach based on the Multilinear Feature Space (MFS) method resorting to transfer learning from large CNN architectures. The proposed method uses CNNs to generate feature maps, although it does not work as complexity reduction approach. After the training process, the generated features maps are used to create vector feature space. We use this new vector space to make projections of any new sample to classify them. Our method, named AMFC, uses the transfer learning from pre-trained CNN to reduce the classification time of new sample image, with minimal accuracy loss. Our method uses the VGG-16 model as the base CNN architecture for experiments; however, the method works with any similar CNN model. Using the well-known Vehicle Image Database and the German Traffic Sign Recognition Benchmark, we compared the classification time of the original VGG-16 model with the AMFC method, and our method is, on average, 17 times faster. The fast classification time reduces the computational and memory demands in embedded applications requiring a large CNN architecture.


title: Quantum computation with charge-and-color permuting twists in qudit color codes

abstract: Twists are defects in the lattice which can be utilized to perform computations on encoded data. Twists have been studied in various classes of topological codes like qubit and qudit surface codes, qubit color codes and qubit subsystem color codes. They are known to exhibit projective non-Abelian statistics which is exploited to perform encoded gates. In this paper, we initiate the study of twists in qudit color codes over odd prime alphabet. To the best of our knowledge, this is the first study of twists in qudit color codes. Specifically, we present a systematic construction of twists in qudit color codes that permute both charge and color of the excitations. We also present a mapping between generalized Pauli operators and strings in the lattice. Making use of the construction, we give protocols to implement generalized Clifford gates using charge-and-color-permuting twists.


title: Self-force effects in post-Minkowskian scattering

abstract: We revisit the old problem of the self-force on a particle moving in a weak-field spacetime in the context of renewed interest in two-body gravitational scattering. We analytically calculate the scalar, electromagnetic, and gravitational self-force on a particle moving on a straight-line trajectory at a large distance from a Newtonian star, and use these results to find the associated correction to its motion. In the gravitational case we must also include the matter-mediated force, which acts at the same perturbative order as the gravitational self-force. We further augment the gravitational results with geodesic calculations at second order in the central body mass to determine the full, explicit solution to the two-body gravitational scattering problem at second post-Minkowskian order (2PM). We calculate the momentum transfer (which reproduces Westpfahl's old result), the change in mechanical angular momentum (which matches the radiative flux recently computed by Damour), and the change in mechanical mass moment (the time-space components of the angular momentum tensor), which has not previously appeared. Besides the new 2PM results of explicit trajectories and all conserved quantities, this work clarifies the role of gravitational self-force in PM scattering theory and provides a foundation for higher-order calculations.


title: Uniform subconvex bounds for Rankin-Selberg $L$-functions

abstract: Let $f$ be a Maass cusp form for $\rm SL_2(\mathbb{Z})$ with Laplace eigenvalue $1/4+\mu_f^2$, $\mu_f>0$. Let $g$ be an arbitrary but fixed holomorphic or Maass cusp form for $\rm SL_2(\mathbb{Z})$. In this paper, we establish the following uniform subconvexity bound for the Rankin-Selberg $L$-function $L(s,f\otimes g)$ $$ L\left(1/2+it,f\otimes g\right)\ll (\mu_f+|t|)^{9/10+\varepsilon}, $$ where the implied constant depends only on $\varepsilon$ and $g$.


title: GP-MOOD: A positive-preserving high-order finite volume method for hyperbolic conservation laws

abstract: We present an a posteriori shock-capturing finite volume method algorithm called GP-MOOD that solves a compressible hyperbolic conservative system at high-order solution accuracy (e.g., third-, fifth-, and seventh-order) in multiple spatial dimensions. The GP-MOOD method combines two methodologies, the polynomial-free spatial reconstruction methods of GP (Gaussian Process) and the a posteriori detection algorithms of MOOD (Multidimensional Optimal Order Detection). The spatial approximation of our GP-MOOD method uses GP's unlimited spatial reconstruction that builds upon our previous studies on GP reported in Reyes et al., Journal of Scientific Computing, 76 (2017) and Journal of Computational Physics, 381 (2019). This paper focuses on extending GP's flexible variability of spatial accuracy to an a posteriori detection formalism based on the MOOD approach. We show that GP's polynomial-free reconstruction provides a seamless pathway to the MOOD's order cascading formalism by utilizing GP's novel property of variable (2R+1)th-order spatial accuracy on a multidimensional GP stencil defined by the GP radius R, whose size is smaller than that of the standard polynomial MOOD methods. The resulting GP-MOOD method is a positivity-preserving method. We examine the numerical stability and accuracy of GP-MOOD on smooth and discontinuous flows in multiple spatial dimensions without resorting to any conventional, computationally expensive a priori nonlinear limiting mechanism to maintain numerical stability.

categories: math.NA astro-ph.HE cs.NA physics.comp-ph


title: Absolutely continuous and pure point spectra of discrete operators with sparse potentials

abstract: We consider the discrete Schr\"odinger operator $H=-\Delta+V$ with a sparse potential $V$ and find conditions guaranteeing either existence of wave operators for the pair $H$ and $H_0=-\Delta$, or presence of dense purely point spectrum of the operator $H$ on some interval $[\lambda_0,0]$ with $\lambda_0<0$.


title: A Learning-based Approach Towards Automated Tuning of SSD Configurations

abstract: Thanks to the mature manufacturing techniques, solid-state drives (SSDs) are highly customizable for applications today, which brings opportunities to further improve their storage performance and resource utilization. However, the SSD efficiency is usually determined by many hardware parameters, making it hard for developers to manually tune them and determine the optimal SSD configurations. In this paper, we present an automated learning-based framework, named LearnedSSD, that utilizes both supervised and unsupervised machine learning (ML) techniques to drive the tuning of hardware configurations for SSDs. LearnedSSD automatically extracts the unique access patterns of a new workload using its block I/O traces, maps the workload to previously workloads for utilizing the learned experiences, and recommends an optimal SSD configuration based on the validated storage performance. LearnedSSD accelerates the development of new SSD devices by automating the hard-ware parameter configurations and reducing the manual efforts. We develop LearnedSSD with simple yet effective learning algorithms that can run efficiently on multi-core CPUs. Given a target storage workload, our evaluation shows that LearnedSSD can always deliver an optimal SSD configuration for the target workload, and this configuration will not hurt the performance of non-target workloads.


title: Desingularization of the Sweeping Process Mapping

abstract: In [9], the celebrated K{\L}-inequality has been extended from definable functions $f:\mathbb{R}^{n}\rightarrow\mathbb{R} $ to definable multivalued maps $S:\mathbb{R}\rightrightarrows\mathbb{R}^{n}$, by establishing that the co-derivative mapping $D^{\ast}S$ admits a desingularization around every critical value. As was the case in the gradient dynamics, this desingularization yields a uniform control of the lengths of all bounded orbits of the corresponding sweeping process $-\dot{\gamma}(t)\in N_{S(t)}(\gamma(t))$. In this paper, working outside the framework of o-minimal geometry, we characterize the existence of a desingularization for the coderivative in terms of the behaviour of the sweeping process orbits and the integrability of the talweg function. These results are close in spirit with the ones in [3], where characterizations for the desingularization of the (sub)gradient of functions had been obtained.


title: Composite fermion mass enhancement and particle-hole symmetry of fractional quantum Hall states in the lowest Landau level under realistic conditions

abstract: Particle-hole symmetry breaking in the fractional quantum Hall effect has recently been studied both theoretically and experimentally with most works focusing on non-Abelian states in the second electronic Landau level. In this work, we theoretically investigate particle-hole symmetry breaking of incompressible fractional quantum Hall states in the lowest Landau level under the influence of the realistic effect of a finite magnetic field strength. A finite magnetic field induces Landau level and sub-band mixing which are known to break particle-hole symmetry at the level of the Hamiltonian. We analyze the Haldane pseudopotentials, energy spectra and energy gaps, and the wave functions themselves, under realistic conditions. We find that particle-hole symmetry is broken, as determined by energy gaps, between states related via particle-hole conjugation, however, we find that particle-hole symmetry is largely maintained as determined by the effective mass of composite fermions. Finally, we comment and make connection to recent experimental observations regarding particle-hole symmetry in the lowest Landau level fractional quantum Hall effect [Pan et al. Phys. Rev. Lett. 124, 156801 (2020)]


title: MG-GCN: Scalable Multi-GPU GCN Training Framework

abstract: Full batch training of Graph Convolutional Network (GCN) models is not feasible on a single GPU for large graphs containing tens of millions of vertices or more. Recent work has shown that, for the graphs used in the machine learning community, communication becomes a bottleneck and scaling is blocked outside of the single machine regime. Thus, we propose MG-GCN, a multi-GPU GCN training framework taking advantage of the high-speed communication links between the GPUs present in multi-GPU systems. MG-GCN employs multiple High-Performance Computing optimizations, including efficient re-use of memory buffers to reduce the memory footprint of training GNN models, as well as communication and computation overlap. These optimizations enable execution on larger datasets, that generally do not fit into memory of a single GPU in state-of-the-art implementations. Furthermore, they contribute to achieve superior speedup compared to the state-of-the-art. For example, MG-GCN achieves super-linear speedup with respect to DGL, on the Reddit graph on both DGX-1 (V100) and DGX-A100.


title: Classical-to-Quantum Transfer Learning for Spoken Command Recognition Based on Quantum Neural Networks

abstract: This work investigates an extension of transfer learning applied in machine learning algorithms to the emerging hybrid end-to-end quantum neural network (QNN) for spoken command recognition (SCR). Our QNN-based SCR system is composed of classical and quantum components: (1) the classical part mainly relies on a 1D convolutional neural network (CNN) to extract speech features; (2) the quantum part is built upon the variational quantum circuit with a few learnable parameters. Since it is inefficient to train the hybrid end-to-end QNN from scratch on a noisy intermediate-scale quantum (NISQ) device, we put forth a hybrid transfer learning algorithm that allows a pre-trained classical network to be transferred to the classical part of the hybrid QNN model. The pre-trained classical network is further modified and augmented through jointly fine-tuning with a variational quantum circuit (VQC). The hybrid transfer learning methodology is particularly attractive for the task of QNN-based SCR because low-dimensional classical features are expected to be encoded into quantum states. We assess the hybrid transfer learning algorithm applied to the hybrid classical-quantum QNN for SCR on the Google speech command dataset, and our classical simulation results suggest that the hybrid transfer learning can boost our baseline performance on the SCR task.


title: Tackling the Imbalance for GNNs

abstract: Different from deep neural networks for non-graph data classification, graph neural networks (GNNs) leverage the information exchange between nodes (or samples) when representing nodes. The category distribution shows an imbalance or even a highly-skewed trend on nearly all existing benchmark GNN data sets. The imbalanced distribution will cause misclassification of nodes in the minority classes, and even cause the classification performance on the entire data set to decrease. This study explores the effects of the imbalance problem on the performances of GNNs and proposes new methodologies to solve it. First, a node-level index, namely, the label difference index ($LDI$), is defined to quantitatively analyze the relationship between imbalance and misclassification. The less samples in a class, the higher the value of its average $LDI$; the higher the $LDI$ of a sample, the more likely the sample will be misclassified. We define a new loss and propose four new methods based on $LDI$. Experimental results indicate that the classification accuracies of the three among our proposed four new methods are better in both transductive and inductive settings. The $LDI$ can be applied to other GNNs.


title: Terminal Embeddings in Sublinear Time

abstract: Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a {\it terminal embedding} from one metric space $(X,d_X)$ to another $(Y,d_Y)$ with a set of designated terminals $T\subset X$. Such an embedding $f$ is said to have distortion $\rho\ge 1$ if $\rho$ is the smallest value such that there exists a constant $C>0$ satisfying \begin{equation*} \forall x\in T\ \forall q\in X,\ C d_X(x, q) \le d_Y(f(x), f(q)) \le C \rho d_X(x, q) . \end{equation*} When $X,Y$ are both Euclidean metrics with $Y$ being $m$-dimensional, recently (Narayanan, Nelson 2019), following work of (Mahabadi, Makarychev, Makarychev, Razenshteyn 2018), showed that distortion $1+\epsilon$ is achievable via such a terminal embedding with $m = O(\epsilon^{-2}\log n)$ for $n := |T|$. This generalizes the Johnson-Lindenstrauss lemma, which only preserves distances within $T$ and not to $T$ from the rest of space. The downside of prior work is that evaluating their embedding on some $q\in \mathbb{R}^d$ required solving a semidefinite program with $\Theta(n)$ constraints in~$m$ variables and thus required some superlinear $\mathrm{poly}(n)$ runtime. Our main contribution in this work is to give a new data structure for computing terminal embeddings. We show how to pre-process $T$ to obtain an almost linear-space data structure that supports computing the terminal embedding image of any $q\in\mathbb{R}^d$ in sublinear time $O^* (n^{1-\Theta(\epsilon^2)} + d)$. To accomplish this, we leverage tools developed in the context of approximate nearest neighbor search.