OpenRaiser/Intern-Atlas huggingface dataset:
Analytical Composition of Differential Privacy via the Edgeworth Accountant
Venue: arXiv cs.CR 2022
Year: 2022

Many modern machine learning algorithms are composed of simple private algorithms; thus, an increasingly important problem is to efficiently compute the overall privacy loss under composition. In this study, we introduce the Edgeworth Accountant, an analytical approach to composing differential privacy guarantees of private algorithms. The Edgeworth Accountant starts by losslessly tracking the privacy loss under composition using the $f$-differential privacy framework, which allows us to express the privacy guarantees using privacy-loss log-likelihood ratios (PLLRs). As the name suggests, this accountant next uses the Edgeworth expansion to the upper and lower bounds the probability distribution of the sum of the PLLRs. Moreover, by relying on a technique for approximating complex distributions using simple ones, we demonstrate that the Edgeworth Accountant can be applied to the composition of any noise-addition mechanism. Owing to certain appealing features of the Edgeworth expansion, the $(ε, δ)$-differential privacy bounds offered by this accountant are non-asymptotic, with essentially no extra computational cost, as opposed to the prior approaches in, wherein the running times increase with the number of compositions. Finally, we demonstrate that our upper and lower $(ε, δ)$-differential privacy bounds are tight in federated analytics and certain regimes of training private deep learning models.
Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information
Venue: arXiv cs.LG 2022
Year: 2022

In real-world reinforcement learning applications the learner's observation space is ubiquitously high-dimensional with both relevant and irrelevant information about the task at hand. Learning from high-dimensional observations has been the subject of extensive investigation in supervised learning and statistics (e.g., via sparsity), but analogous issues in reinforcement learning are not well understood, even in finite state/action (tabular) domains. We introduce a new problem setting for reinforcement learning, the Exogenous Markov Decision Process (ExoMDP), in which the state space admits an (unknown) factorization into a small controllable (or, endogenous) component and a large irrelevant (or, exogenous) component; the exogenous component is independent of the learner's actions, but evolves in an arbitrary, temporally correlated fashion. We provide a new algorithm, ExoRL, which learns a near-optimal policy with sample complexity polynomial in the size of the endogenous component and nearly independent of the size of the exogenous component, thereby offering a doubly-exponential improvement over off-the-shelf algorithms. Our results highlight for the first time that sample-efficient reinforcement learning is possible in the presence of exogenous information, and provide a simple, user-friendly benchmark for investigation going forward.
Evaluating Aleatoric Uncertainty via Conditional Generative Models
Venue: arXiv cs.LG 2022
Year: 2022

Aleatoric uncertainty quantification seeks for distributional knowledge of random responses, which is important for reliability analysis and robustness improvement in machine learning applications. Previous research on aleatoric uncertainty estimation mainly targets closed-formed conditional densities or variances, which requires strong restrictions on the data distribution or dimensionality. To overcome these restrictions, we study conditional generative models for aleatoric uncertainty estimation. We introduce two metrics to measure the discrepancy between two conditional distributions that suit these models. Both metrics can be easily and unbiasedly computed via Monte Carlo simulation of the conditional generative models, thus facilitating their evaluation and training. We demonstrate numerically how our metrics provide correct measurements of conditional distributional discrepancies and can be used to train conditional models competitive against existing benchmarks.
Outage Analysis of Age-of-Information for Multi-Source Systems
Venue: arXiv cs.IT 2022
Year: 2022

Age of information (AoI) is an effective performance metric measuring the freshness of information and is popular for applications involving status update. Most of the existing works have adopted average AoI as the metric, which cannot provide strict performance guarantees. In this work, the outage probability of the peak AoI exceeding a given threshold is analyzed in a multi-source system under round robin scheduling. Two queueing disciplines are considered, namely the first-come-first-serve (FCFS) queue and the single packet queue. For FCFS, upper and lower bounds on the outage probability are derived which coincides asymptotically, characterizing its true scaling. For the single packet queue, an upper bound is derived whose effectiveness is validated by the simulation results. The analysis concretizes the common belief that single packet queueing has a better AoI performance than FCFS. Moreover, it also reveals that the two disciplines would have similar asymptotic performance when the inter-arrival time is much larger than the total transmission time.
Adversarial Noises Are Linearly Separable for (Nearly) Random Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Adversarial examples, which are usually generated for specific inputs with a specific model, are ubiquitous for neural networks. In this paper we unveil a surprising property of adversarial noises when they are put together, i.e., adversarial noises crafted by one-step gradient methods are linearly separable if equipped with the corresponding labels. We theoretically prove this property for a two-layer network with randomly initialized entries and the neural tangent kernel setup where the parameters are not far from initialization. The proof idea is to show the label information can be efficiently backpropagated to the input while keeping the linear separability. Our theory and experimental evidence further show that the linear classifier trained with the adversarial noises of the training data can well classify the adversarial noises of the test data, indicating that adversarial noises actually inject a distributional perturbation to the original data distribution. Furthermore, we empirically demonstrate that the adversarial noises may become less linearly separable when the above conditions are compromised while they are still much easier to classify than original features.
Distinct Angles in General Position
Venue: arXiv cs.CG 2022
Year: 2022

The Erdős distinct distance problem is a ubiquitous problem in discrete geometry. Somewhat less well known is Erdős' distinct angle problem, the problem of finding the minimum number of distinct angles between $n$ non-collinear points in the plane. Recent work has introduced bounds on a wide array of variants of this problem, inspired by similar variants in the distance setting. In this short note, we improve the best known upper bound for the minimum number of distinct angles formed by $n$ points in general position from $O(n^{\log_2(7)})$ to $O(n^2)$. Before this work, similar bounds relied on projections onto a generic plane from higher dimensional space. In this paper, we employ the geometric properties of a logarithmic spiral, sidestepping the need for a projection. We also apply this configuration to reduce the upper bound on the largest integer such that any set of $n$ points in general position has a subset of that size with all distinct angles. This bound is decreased from $O(n^{\log_2(7)/3})$ to $O(n^{1/2})$.
Hinted Dictionaries: Efficient Functional Ordered Sets and Maps
Venue: arXiv cs.PL 2022
Year: 2022

This article introduces hinted dictionaries for expressing efficient ordered sets and maps functionally. As opposed to the traditional ordered dictionaries with logarithmic operations, hinted dictionaries can achieve better performance by using cursor-like objects referred to as hints. Hinted dictionaries unify the interfaces of imperative ordered dictionaries (e.g., C++ maps) and functional ones (e.g., Adams' sets). We show that such dictionaries can use sorted arrays, unbalanced trees, and balanced trees as their underlying representations. Throughout the article, we use Scala to present the different components of hinted dictionaries. We also provide a C++ implementation to evaluate the effectiveness of hinted dictionaries. Hinted dictionaries provide superior performance for set-set operations in comparison with the standard library of C++. Also, they show a competitive performance in comparison with the SciPy library for sparse vector operations.
Interaction Design for VR Applications: Understanding Needs for University Curricula
Venue: arXiv cs.HC 2022
Year: 2022

As virtual reality (VR) is emerging in the tech sector, developers and designers are under pressure to create immersive experiences for their products. However, the current curricula from top institutions focus primarily on technical considerations for building VR applications, missing out on concerns and usability problems specific to VR interaction design. To better understand current needs, we examined the status quo of existing university pedagogies by carrying out a content analysis of undergraduate and graduate courses about VR and related areas offered in the major citadels of learning and conducting interviews with 7 industry experts. Our analysis reveals that the current teaching practices underemphasize design thinking, prototyping, and evaluation skills, while focusing on technical implementation. We recommend VR curricula should emphasize design principles and guidelines, offer training in prototyping and ideation, prioritize practical design exercises while providing industry insights, and encourage students to solve VR design problems beyond the classroom.
Segmentation Enhanced Lameness Detection in Dairy Cows from RGB and Depth Video
Venue: arXiv cs.CV 2022
Year: 2022

Cow lameness is a severe condition that affects the life cycle and life quality of dairy cows and results in considerable economic losses. Early lameness detection helps farmers address illnesses early and avoid negative effects caused by the degeneration of cows' condition. We collected a dataset of short clips of cows passing through a hallway exiting a milking station and annotated the degree of lameness of the cows. This paper explores the resulting dataset and provides a detailed description of the data collection process. Additionally, we proposed a lameness detection method that leverages pre-trained neural networks to extract discriminative features from videos and assign a binary score to each cow indicating its condition: "healthy" or "lame." We improve this approach by forcing the model to focus on the structure of the cow, which we achieve by substituting the RGB videos with binary segmentation masks predicted with a trained segmentation model. This work aims to encourage research and provide insights into the applicability of computer vision models for cow lameness detection on farms.
Deep kernelization for the Tree Bisection and Reconnnect (TBR) distance in phylogenetics
Venue: arXiv cs.DS 2022
Year: 2022

We describe a kernel of size 9k-8 for the NP-hard problem of computing the Tree Bisection and Reconnect (TBR) distance k between two unrooted binary phylogenetic trees. We achieve this by extending the existing portfolio of reduction rules with three novel new reduction rules. Two of the rules are based on the idea of topologically transforming the trees in a distance-preserving way in order to guarantee execution of earlier reduction rules. The third rule extends the local neighbourhood approach introduced in (Kelk and Linz, Annals of Combinatorics 24(3), 2020) to more global structures, allowing new situations to be identified when deletion of a leaf definitely reduces the TBR distance by one. The bound on the kernel size is tight up to an additive term. Our results also apply to the equivalent problem of computing a Maximum Agreement Forest (MAF) between two unrooted binary phylogenetic trees. We anticipate that our results will be more widely applicable for computing agreement-forest based dissimilarity measures.
Holistic Verification of Blockchain Consensus
Venue: arXiv cs.CR 2022
Year: 2022

Blockchain has recently attracted the attention of the industry due, in part, to its ability to automate asset transfers. It requires distributed participants to reach a consensus on a block despite the presence of malicious (a.k.a. Byzantine) participants. Malicious participants exploit regularly weaknesses of these blockchain consensus algorithms, with sometimes devastating consequences. In fact, these weaknesses are quite common and are well illustrated by the flaws in the hand-written proofs of existing blockchain consensus protocols [63]. Paradoxically, until now, no blockchain consensus has been holistically verified using model checking. In this paper, we remedy this paradox by model checking for the first time a blockchain consensus used in industry. We propose a holistic approach to verify the consensus algorithm of the Red Belly Blockchain [20], for any number $n$ of processes and any number $f<n/3$ of Byzantine processes. We decompose directly the algorithm pseudocode in two parts -- an inner broadcast algorithm and an outer decision algorithm -- each modelled as a threshold automaton [36], and we formalize their expected properties in linear-time temporal logic. We then automatically check the inner broadcasting algorithm, under a carefully identified fairness assumption. For the verification of the outer algorithm, we simplify the model of the inner algorithm by relying on its checked properties. Doing so, we formally verify not only the safety properties of the Red Belly Blockchain consensus but also its liveness in about 70 seconds.
Autonomous Drone Landing with Fiducial Markers and a Gimbal-Mounted Camera for Active Tracking
Venue: arXiv cs.RO 2022
Year: 2022

Precision landing is a remaining challenge in autonomous drone flight. Fiducial markers provide a computationally cheap way for a drone to locate a landing pad and autonomously execute precision landings. However, most work in this field depends on either rigidly-mounted or downward-facing cameras which restrict the drone's ability to detect the marker. We present a method of autonomous landing that uses a gimbal-mounted camera to quickly search for the landing pad by simply spinning in place while tilting the camera up and down, and to continually aim the camera at the landing pad during approach and landing. This method demonstrates successful search, tracking, and landing with 4 of 5 tested fiducial systems on a physical drone with no human intervention. Per fiducial system, we present the distributions of the distances from the drone to the center of the landing pad after each successful landing. We also show representative examples of flight trajectories, marker tracking performance, and control outputs for each channel during the landing. Finally, we discuss qualitative strengths and weaknesses underlying each system.
Temporal Logic Imitation: Learning Plan-Satisficing Motion Policies from Demonstrations
Venue: arXiv cs.RO 2022
Year: 2022

Learning from demonstration (LfD) has succeeded in tasks featuring a long time horizon. However, when the problem complexity also includes human-in-the-loop perturbations, state-of-the-art approaches do not guarantee the successful reproduction of a task. In this work, we identify the roots of this challenge as the failure of a learned continuous policy to satisfy the discrete plan implicit in the demonstration. By utilizing modes (rather than subgoals) as the discrete abstraction and motion policies with both mode invariance and goal reachability properties, we prove our learned continuous policy can simulate any discrete plan specified by a linear temporal logic (LTL) formula. Consequently, an imitator is robust to both task- and motion-level perturbations and guaranteed to achieve task success. Project page: https://yanweiw.github.io/tli/
POODLE: Improving Few-shot Learning via Penalizing Out-of-Distribution Samples
Venue: arXiv cs.LG 2022
Year: 2022

In this work, we propose to use out-of-distribution samples, i.e., unlabeled samples coming from outside the target classes, to improve few-shot learning. Specifically, we exploit the easily available out-of-distribution samples to drive the classifier to avoid irrelevant features by maximizing the distance from prototypes to out-of-distribution samples while minimizing that of in-distribution samples (i.e., support, query data). Our approach is simple to implement, agnostic to feature extractors, lightweight without any additional cost for pre-training, and applicable to both inductive and transductive settings. Extensive experiments on various standard benchmarks demonstrate that the proposed method consistently improves the performance of pretrained networks with different architectures.
Unsupervised Deep Discriminant Analysis Based Clustering
Venue: arXiv cs.LG 2022
Year: 2022

This work presents an unsupervised deep discriminant analysis for clustering. The method is based on deep neural networks and aims to minimize the intra-cluster discrepancy and maximize the inter-cluster discrepancy in an unsupervised manner. The method is able to project the data into a nonlinear low-dimensional latent space with compact and distinct distribution patterns such that the data clusters can be effectively identified. We further provide an extension of the method such that available graph information can be effectively exploited to improve the clustering performance. Extensive numerical results on image and non-image data with or without graph information demonstrate the effectiveness of the proposed methods.
Swan: A Neural Engine for Efficient DNN Training on Smartphone SoCs
Venue: arXiv cs.LG 2022
Year: 2022

The need to train DNN models on end-user devices (e.g., smartphones) is increasing with the need to improve data privacy and reduce communication overheads. Unlike datacenter servers with powerful CPUs and GPUs, modern smartphones consist of a diverse collection of specialized cores following a system-on-a-chip (SoC) architecture that together perform a variety of tasks. We observe that training DNNs on a smartphone SoC without carefully considering its resource constraints can not only lead to suboptimal training performance but significantly affect user experience as well. In this paper, we present Swan, a neural engine to optimize DNN training on smartphone SoCs without hurting user experience. Extensive large-scale evaluations show that Swan can improve performance by 1.2 - 23.3x over the state-of-the-art.
Gender and Robots: A Literature Review
Venue: arXiv cs.RO 2022
Year: 2022

Here, I ask what we can learn about how gender affects how people engage with robots. I review 46 empirical studies of social robots, published 2018 or earlier, which report on the gender of their participants or the perceived or intended gender of the robot, or both, and perform some analysis with respect to either participant or robot gender. From these studies, I find that robots are by default perceived as male, that robots absorb human gender stereotypes, and that men tend to engage with robots more than women. I highlight open questions about how such gender effects may be different in younger participants, and whether one should seek to match the gender of the robot to the gender of the participant to ensure positive interaction outcomes. I conclude by suggesting that future research should: include gender diverse participant pools, include non-binary participants, rely on self-identification for discerning gender rather than researcher perception, control for known covariates of gender, test for different study outcomes with respect to gender, and test whether the robot used was perceived as gendered by participants. I include an appendix with a narrative summary of gender-relevant findings from each of the 46 papers to aid in future literature reviews.
Strong Memory Lower Bounds for Learning Natural Models
Venue: arXiv cs.LG 2022
Year: 2022

We give lower bounds on the amount of memory required by one-pass streaming algorithms for solving several natural learning problems. In a setting where examples lie in $\{0,1\}^d$ and the optimal classifier can be encoded using $κ$ bits, we show that algorithms which learn using a near-minimal number of examples, $\tilde O(κ)$, must use $\tilde Ω( dκ)$ bits of space. Our space bounds match the dimension of the ambient space of the problem's natural parametrization, even when it is quadratic in the size of examples and the final classifier. For instance, in the setting of $d$-sparse linear classifiers over degree-2 polynomial features, for which $κ=Θ(d\log d)$, our space lower bound is $\tildeΩ(d^2)$. Our bounds degrade gracefully with the stream length $N$, generally having the form $\tildeΩ\left(dκ\cdot \fracκ{N}\right)$. Bounds of the form $Ω(dκ)$ were known for learning parity and other problems defined over finite fields. Bounds that apply in a narrow range of sample sizes are also known for linear regression. Ours are the first such bounds for problems of the type commonly seen in recent learning applications that apply for a large range of input sizes.
CLAP: Learning Audio Concepts From Natural Language Supervision
Venue: arXiv cs.SD 2022
Year: 2022

Mainstream Audio Analytics models are trained to learn under the paradigm of one class label to many recordings focusing on one task. Learning under such restricted supervision limits the flexibility of models because they require labeled audio for training and can only predict the predefined categories. Instead, we propose to learn audio concepts from natural language supervision. We call our approach Contrastive Language-Audio Pretraining (CLAP), which learns to connect language and audio by using two encoders and a contrastive learning to bring audio and text descriptions into a joint multimodal space. We trained CLAP with 128k audio and text pairs and evaluated it on 16 downstream tasks across 8 domains, such as Sound Event Classification, Music tasks, and Speech-related tasks. Although CLAP was trained with significantly less pairs than similar computer vision models, it establishes SoTA for Zero-Shot performance. Additionally, we evaluated CLAP in a supervised learning setup and achieve SoTA in 5 tasks. Hence, CLAP's Zero-Shot capability removes the need of training with class labels, enables flexible class prediction at inference time, and generalizes to multiple downstream tasks.
Trimmed Maximum Likelihood Estimation for Robust Learning in Generalized Linear Models
Venue: arXiv cs.LG 2022
Year: 2022

We study the problem of learning generalized linear models under adversarial corruptions. We analyze a classical heuristic called the iterative trimmed maximum likelihood estimator which is known to be effective against label corruptions in practice. Under label corruptions, we prove that this simple estimator achieves minimax near-optimal risk on a wide range of generalized linear models, including Gaussian regression, Poisson regression and Binomial regression. Finally, we extend the estimator to the more challenging setting of label and covariate corruptions and demonstrate its robustness and optimality in that setting as well.