Search

We study the convex hull membership (CHM) problem in the pure exploration setting where one aims to efficiently and accurately determine if a given point lies in the convex hull of means of a finite set of distributions. We give a complete characterization of the sample complexity of the CHM problem in the one-dimensional case. We present the first asymptotically optimal algorithm called Thompson-CHM, whose modular design consists of a stopping rule and a sampling rule. In addition, we extend the algorithm to settings that generalize several important problems in the multi-armed bandit literature. Furthermore, we discuss the extension of Thompson-CHM to higher dimensions. Finally, we provide numerical experiments to demonstrate the empirical behavior of the algorithm matches our theoretical results for realistic time horizons.

Accurate channel estimation is critical to the performance of orthogonal frequency-division multiplexing (OFDM) underwater acoustic (UWA) communications, especially under multiple-input multiple-output (MIMO) scenarios. In this paper, we explore Vector Approximate Message Passing (VAMP) coupled with Expected Maximum (EM) to obtain channel estimation (CE) for MIMO OFDM UWA communications. The EM-VAMP-CE scheme is developed by employing a Bernoulli-Gaussian (BG) prior distribution for the channel impulse response, and hyperparameters of the BG prior distribution are learned via the EM algorithm. Performance of the EM-VAMP-CE is evaluated through both synthesized data and real data collected in two at-sea UWA communication experiments. It is shown the EM-VAMP-CE achieves better performance-complexity tradeoff compared with existing channel estimation methods., Comment: Journal:IEEE Journal of Oceanic Engineering(Date of Submission:2022-06-25)

Learning-based approaches to modeling crowd motion have become increasingly successful but require training and evaluation on large datasets, coupled with complex model selection and parameter tuning. To circumvent this tremendously time-consuming process, we propose a novel scoring method, which characterizes generalization of models trained on source crowd scenarios and applied to target crowd scenarios using a training-free, model-agnostic Interaction + Diversity Quantification score, ISDQ. The Interaction component aims to characterize the difficulty of scenario domains, while the diversity of a scenario domain is captured in the Diversity score. Both scores can be computed in a computation tractable manner. Our experimental results validate the efficacy of the proposed method on several simulated and real-world (source,target) generalization tasks, demonstrating its potential to select optimal domain pairs before training and testing a model.

Being able to efficiently and accurately select the top-$k$ elements with differential privacy is an integral component of various private data analysis tasks. In this paper, we present the oneshot Laplace mechanism, which generalizes the well-known Report Noisy Max mechanism to reporting noisy top-$k$ elements. We show that the oneshot Laplace mechanism with a noise level of $\widetilde{O}(\sqrt{k}/\eps)$ is approximately differentially private. Compared to the previous peeling approach of running Report Noisy Max $k$ times, the oneshot Laplace mechanism only adds noises and computes the top $k$ elements once, hence much more efficient for large $k$. In addition, our proof of privacy relies on a novel coupling technique that bypasses the use of composition theorems. Finally, we present a novel application of efficient top-$k$ selection in the classical problem of ranking from pairwise comparisons., Comment: Accepted to ICML 2021

We analyze a secure two-hop mixed radio frequency (RF) and underwater wireless optical communication (UWOC) system using a fixed-gain amplify-and-forward (AF) relay. The UWOC channel is modeled using a unified mixture exponential-generalized Gamma distribution to consider the combined effects of air bubbles and temperature gradients on transmission characteristics. Both legitimate and eavesdropping RF channels are modeled using flexible $\alpha-\mu$ distributions. Specifically, we first derive both the probability density function (PDF) and cumulative distribution function (CDF) of the received signal-to-noise ratio (SNR) of the mixed RF and UWOC system. Based on the PDF and CDF expressions, we derive the closed-form expressions for the tight lower bound of the secrecy outage probability (SOP) and the probability of non-zero secrecy capacity (PNZ), which are both expressed in terms bivariate Fox's $H$-function. To utilize these analytical expressions, we derive asymptotic expressions of SOP and PNZ using only elementary functions. Also, we use asymptotic expressions to determine the optimal transmitting power to maximize energy efficiency. Further, we thoroughly investigate the effect of levels of air bubbles and temperature gradients in the UWOC channel, and study nonlinear characteristics of the transmission medium and the number of multipath clusters of the RF channel on the secrecy performance. Finally, all analyses are validated using Monte Carlo simulation.

We analyze the secrecy performance of a two-hop mixed radio frequency (RF)/underwater wireless optical communication (UWOC) system using a decode-and-forward (DF) relay. All RF and UWOC links are modeled by the $\alpha-\mu$ and exponential-generalized Gamma distributions, respectively. We first derive the expressions of the secrecy outage probability (SOP) in exact closed-form, which are subsequently used to derive asymptotic expressions at high SNR that only includes simple functions for further insight. Moreover, based on the asymptotic expression, we can determine the optimal transmit power for a wide variety of RF and UWOC channel conditions. All analyses are validated using Monte Carlo simulation.

Underwater wireless optical communication is one of the critical technologies for buoy-based high-speed cross-sea surface communication, where the communication nodes are vertically deployed. Due to the vertically inhomogeneous nature of the underwater environment, seawater is usually vertically divided into multiple layers with different parameters that reflect the real environment. In this work, we consider a generalized UWOC channel model that contains$N$ layers. To capture the effects of air bubbles and temperature gradients on channel statistics, we model each layer by a mixture Exponential-Generalized Gamma(EGG) distribution. We derive the PDF and CDF of the end-to-end SNR in exact closed-form. Then, unified BER and outage expressions using OOK and BPSK are also derived. The performance and behavior of common vertical underwater optical communication scenarios are thoroughly analyzed through the appropriate selection of parameters. All the derived expressions are verified via Monte Carlo simulations., Comment: 12 pages, 4 figures

Crowd simulation, the study of the movement of multiple agents in complex environments, presents a unique application domain for machine learning. One challenge in crowd simulation is to imitate the movement of expert agents in highly dense crowds. An imitation model could substitute an expert agent if the model behaves as good as the expert. This will bring many exciting applications. However, we believe no prior studies have considered the critical question of how training data and training methods affect imitators when these models are applied to novel scenarios. In this work, a general imitation model is represented by applying either the Behavior Cloning (BC) training method or a more sophisticated Generative Adversarial Imitation Learning (GAIL) method, on three typical types of data domains: standard benchmarks for evaluating crowd models, random sampling of state-action pairs, and egocentric scenarios that capture local interactions. Simulated results suggest that (i) simpler training methods are overall better than more complex training methods, (ii) training samples with diverse agent-agent and agent-obstacle interactions are beneficial for reducing collisions when the trained models are applied to new scenarios. We additionally evaluated our models in their ability to imitate real world crowd trajectories observed from surveillance videos. Our findings indicate that models trained on representative scenarios generalize to new, unseen situations observed in real human crowds., Comment: 12 pages, MIG 2019 - ACM SIGGRAPH Conference on Motion, Interaction and Games

Trajectory interpolation, the process of filling-in the gaps and removing noise from observed agent trajectories, is an essential task for the motion inference in multi-agent setting. A desired trajectory interpolation method should be robust to noise, changes in environments or agent densities, while also being yielding realistic group movement behaviors. Such realistic behaviors are, however, challenging to model as they require avoidance of agent-agent or agent-environment collisions and, at the same time, seek computational efficiency. In this paper, we propose a novel framework composed of data-driven priors (local, global or combined) and an efficient optimization strategy for multi-agent trajectory interpolation. The data-driven priors implicitly encode the dependencies of movements of multiple agents and the collision-avoiding desiderata, enabling elimination of costly pairwise collision constraints and resulting in reduced computational complexity and often improved estimation. Various combinations of priors and optimization algorithms are evaluated in comprehensive simulated experiments. Our experimental results reveal important insights, including the significance of the global flow prior and the lesser-than-expected influence of data-driven collision priors., Comment: 11 pages including supplementary, 6 figures in total, 6 tables in total, 1 algorithm