More Like this

1. Inferring Sparse Preference Lists from Partial Information

   https://doi.org/10.1287/stsy.2019.0060  

   Farias, Vivek; Jagabathula, Srikanth; Shah, Devavrat (December 2020, Stochastic Systems)

   null (Ed.)

   Probability distributions over rankings are crucial for the modeling and design of a wide range of practical systems. In this work, we pursue a nonparametric approach that seeks to learn a distribution over rankings (aka the ranking model) that is consistent with the observed data and has the sparsest possible support (i.e., the smallest number of rankings with nonzero probability mass). We focus on first-order marginal data, which comprise information on the probability that item i is ranked at position j, for all possible item and position pairs. The observed data may be noisy. Finding the sparsest approximation requires brute force search in the worst case. To address this issue, we restrict our search to, what we dub, the signature family, and show that the sparsest model within the signature family can be found computationally efficiently compared with the brute force approach. We then establish that the signature family provides good approximations to popular ranking model classes, such as the multinomial logit and the exponential family classes, with support size that is small relative to the dimension of the observed data. We test our methods on two data sets: the ranked election data set from the American Psychological Association and the preference ordering data on 10 different sushi varieties. 

   more » « less
2. Data Augmentation MCMC for Bayesian Inference from Privatized Data

   Ju, Nianqiao; Awan, Jordan; Gong, Ruobin; Rao, Vinayak (December 2022, Advances in neural information processing systems)

   Koyejo, Sanmi; Mohamed, Shakir (Ed.)

   Differentially private mechanisms protect privacy by introducing additional randomness into the data. Restricting access to only the privatized data makes it challenging to perform valid statistical inference on parameters underlying the confidential data. Specifically, the likelihood function of the privatized data requires integrating over the large space of confidential databases and is typically intractable. For Bayesian analysis, this results in a posterior distribution that is doubly intractable, rendering traditional MCMC techniques inapplicable. We propose an MCMC framework to perform Bayesian inference from the privatized data, which is applicable to a wide range of statistical models and privacy mechanisms. Our MCMC algorithm augments the model parameters with the unobserved confidential data, and alternately updates each one conditional on the other. For the potentially challenging step of updating the confidential data, we propose a generic approach that exploits the privacy guarantee of the mechanism to ensure efficiency. In particular, we give results on the computational complexity, acceptance rate, and mixing properties of our MCMC. We illustrate the efficacy and applicability of our methods on a na\"ive-Bayes log-linear model as well as on a linear regression model. 

   more » « less
3. A Method for Detecting Atmospheric Lagrangian Coherent Structures Using a Single Fixed-Wing Unmanned Aircraft System

   https://doi.org/10.3390/s19071607  

   Nolan, Peter; McClelland, Hunter; Woolsey, Craig; Ross, Shane (April 2019, Sensors)

   The transport of material through the atmosphere is an issue with wide ranging implications for fields as diverse as agriculture, aviation, and human health. Due to the unsteady nature of the atmosphere, predicting how material will be transported via the Earth’s wind field is challenging. Lagrangian diagnostics, such as Lagrangian coherent structures (LCSs), have been used to discover the most significant regions of material collection or dispersion. However, Lagrangian diagnostics can be time-consuming to calculate and often rely on weather forecasts that may not be completely accurate. Recently, Eulerian diagnostics have been developed which can provide indications of LCS and have computational advantages over their Lagrangian counterparts. In this paper, a methodology is developed for estimating local Eulerian diagnostics from wind velocity data measured by a single fixed-wing unmanned aircraft system (UAS) flying in a circular arc. Using a simulation environment, driven by realistic atmospheric velocity data from the North American Mesoscale (NAM) model, it is shown that the Eulerian diagnostic estimates from UAS measurements approximate the true local Eulerian diagnostics and also predict the passage of LCSs. This methodology requires only a single flying UAS, making it easier and more affordable to implement in the field than existing alternatives, such as multiple UASs and Dopler LiDAR measurements. Our method is general enough to be applied to calculate the gradient of any scalar field. 

   more » « less
4. Data Augmentation MCMC for Bayesian Inference from Privatized Data

   Ju, Nianqiao; Awan, Jordan; Gong, Ruobin; Rao, Vinayak (January 2022, Advances in neural information processing systems)

   Koyejo, S.; Mohamed, S.; Agarwal, A.; Belgrave, D.; Cho, K.; Oh, A. (Ed.)

   Differentially private mechanisms protect privacy by introducing additional randomness into the data. Restricting access to only the privatized data makes it challenging to perform valid statistical inference on parameters underlying the confidential data. Specifically, the likelihood function of the privatized data requires integrating over the large space of confidential databases and is typically intractable. For Bayesian analysis, this results in a posterior distribution that is doubly intractable, rendering traditional MCMC techniques inapplicable. We propose an MCMC framework to perform Bayesian inference from the privatized data, which is applicable to a wide range of statistical models and privacy mechanisms. Our MCMC algorithm augments the model parameters with the unobserved confidential data, and alternately updates each one conditional on the other. For the potentially challenging step of updating the confidential data, we propose a generic approach that exploits the privacy guarantee of the mechanism to ensure efficiency. We give results on the computational complexity, acceptance rate, and mixing properties of our MCMC. We illustrate the efficacy and applicability of our methods on a naive-Bayes log-linear model and on a linear regression model. 

   more » « less
5. Improving sampling accuracy of stochastic gradient MCMC methods via non-uniform subsampling of gradients

   https://doi.org/10.3934/dcdss.2021157  

   Li, Ruilin; Wang, Xin; Zha, Hongyuan; Tao, Molei (January 2021, Discrete & Continuous Dynamical Systems - S)

   Many Markov Chain Monte Carlo (MCMC) methods leverage gradient information of the potential function of target distribution to explore sample space efficiently. However, computing gradients can often be computationally expensive for large scale applications, such as those in contemporary machine learning. Stochastic Gradient (SG-)MCMC methods approximate gradients by stochastic ones, commonly via uniformly subsampled data points, and achieve improved computational efficiency, however at the price of introducing sampling error. We propose a non-uniform subsampling scheme to improve the sampling accuracy. The proposed exponentially weighted stochastic gradient (EWSG) is designed so that a non-uniform-SG-MCMC method mimics the statistical behavior of a batch-gradient-MCMC method, and hence the inaccuracy due to SG approximation is reduced. EWSG differs from classical variance reduction (VR) techniques as it focuses on the entire distribution instead of just the variance; nevertheless, its reduced local variance is also proved. EWSG can also be viewed as an extension of the importance sampling idea, successful for stochastic-gradient-based optimizations, to sampling tasks. In our practical implementation of EWSG, the non-uniform subsampling is performed efficiently via a Metropolis-Hastings chain on the data index, which is coupled to the MCMC algorithm. Numerical experiments are provided, not only to demonstrate EWSG's effectiveness, but also to guide hyperparameter choices, and validate our non-asymptotic global error bound despite of approximations in the implementation. Notably, while statistical accuracy is improved, convergence speed can be comparable to the uniform version, which renders EWSG a practical alternative to VR (but EWSG and VR can be combined too). 

   more » « less