skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, June 13 until 2:00 AM ET on Friday, June 14 due to maintenance. We apologize for the inconvenience.


Title: Geometry-informed irreversible perturbations for accelerated convergence of Langevin dynamics
Abstract

We introduce a novel geometry-informed irreversible perturbation that accelerates convergence of the Langevin algorithm for Bayesian computation. It is well documented that there exist perturbations to the Langevin dynamics that preserve its invariant measure while accelerating its convergence. Irreversible perturbations and reversible perturbations (such as Riemannian manifold Langevin dynamics (RMLD)) have separately been shown to improve the performance of Langevin samplers. We consider these two perturbations simultaneously by presenting a novel form of irreversible perturbation for RMLD that is informed by the underlying geometry. Through numerical examples, we show that this new irreversible perturbation can improve estimation performance over irreversible perturbations that do not take the geometry into account. Moreover we demonstrate that irreversible perturbations generally can be implemented in conjunction with the stochastic gradient version of the Langevin algorithm. Lastly, while continuous-time irreversible perturbations cannot impair the performance of a Langevin estimator, the situation can sometimes be more complicated when discretization is considered. To this end, we describe a discrete-time example in which irreversibility increases both the bias and variance of the resulting estimator.

 
more » « less
Award ID(s):
2107856
NSF-PAR ID:
10372163
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Statistics and Computing
Volume:
32
Issue:
5
ISSN:
0960-3174
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Stochastic Gradient Langevin Dynamics (SGLD) have been widely used for Bayesian sampling from certain probability distributions, incorporating derivatives of the log-posterior. With the derivative evaluation of the log-posterior distribution, SGLD methods generate samples from the distribution through performing as a thermostats dynamics that traverses over gradient flows of the log-posterior with certainly controllable perturbation. Even when the density is not known, existing solutions still can first learn the kernel density models from the given datasets, then produce new samples using the SGLD over the kernel density derivatives. In this work, instead of exploring new samples from kernel spaces, a novel SGLD sampler, namely, Randomized Measurement Langevin Dynamics (RMLD) is proposed to sample the high-dimensional sparse representations from the spectral domain of a given dataset. Specifically, given a random measurement matrix for sparse coding, RMLD first derives a novel likelihood evaluator of the probability distribution from the loss function of LASSO, then samples from the high-dimensional distribution using stochastic Langevin dynamics with derivatives of the logarithm likelihood and Metropolis–Hastings sampling. In addition, new samples in low-dimensional measuring spaces can be regenerated using the sampled high-dimensional vectors and the measurement matrix. The algorithm analysis shows that RMLD indeed projects a given dataset into a high-dimensional Gaussian distribution with Laplacian prior, then draw new sparse representation from the dataset through performing SGLD over the distribution. Extensive experiments have been conducted to evaluate the proposed algorithm using real-world datasets. The performance comparisons on three real-world applications demonstrate the superior performance of RMLD beyond baseline methods. 
    more » « less
  2. The human sensorimotor system can adapt to various changes in the environmental dynamics by updating motor commands to improve performance after repeated exposure to the same task. However, the characteristics and mechanisms of the adaptation process remain unknown for dexterous manipulation, a unique motor task in which the body physically interacts with the environment with multiple effectors, i.e., digits, in parallel. We addressed this gap by using robotic manipulanda to investigate the changes in the digit force coordination following mechanical perturbation of an object held by tripod grasps. As the participants gradually adapted to lifting the object under perturbations, we quantified two components of digit force coordination. One is the direction-specific manipulation moment that directly counteracts the perturbation, whereas the other one is the direction-independent internal moment that supports the stability and stiffness of the grasp. We found that trial-to-trial improvement of task performance was associated with increased manipulation moment and a gradual decrease of the internal moment. These two moments were characterized by different rates of adaptation. We also examined how these two force coordination components respond to changes in perturbation directions. Importantly, we found that the manipulation moment was sensitive to the extent of repetitive exposure to the previous context that has an opposite perturbation direction, whereas the internal moment did not. However, the internal moment was sensitive to whether the postchange perturbation direction was previously experienced. Our results reveal, for the first time, that two distinct processes underlie the adaptation of multidigit force coordination for dexterous manipulation. NEW & NOTEWORTHY Changes in digit force coordination in multidigit object manipulation were quantified with a novel experimental design in which human participants adapted to mechanical perturbations applied to the object. Our results show that the adaptation of digit force coordination can be characterized by two distinct components that operate at different timescales. We further show that these two components respond to changes in perturbation direction differently. 
    more » « less
  3. null (Ed.)
    Stochastic gradient descent with momentum (SGDm) is one of the most popular optimization algorithms in deep learning. While there is a rich theory of SGDm for convex problems, the theory is considerably less developed in the context of deep learning where the problem is non-convex and the gradient noise might exhibit a heavy-tailed behavior, as empirically observed in recent studies. In this study, we consider a \emph{continuous-time} variant of SGDm, known as the underdamped Langevin dynamics (ULD), and investigate its asymptotic properties under heavy-tailed perturbations. Supported by recent studies from statistical physics, we argue both theoretically and empirically that the heavy-tails of such perturbations can result in a bias even when the step-size is small, in the sense that \emph{the optima of stationary distribution} of the dynamics might not match \emph{the optima of the cost function to be optimized}. As a remedy, we develop a novel framework, which we coin as \emph{fractional} ULD (FULD), and prove that FULD targets the so-called Gibbs distribution, whose optima exactly match the optima of the original cost. We observe that the Euler discretization of FULD has noteworthy algorithmic similarities with \emph{natural gradient} methods and \emph{gradient clipping}, bringing a new perspective on understanding their role in deep learning. We support our theory with experiments conducted on a synthetic model and neural networks. 
    more » « less
  4. Weather, winds, thermals, and turbulence pose an ever-present challenge to small UAS. These challenges become magnified in rough terrain and especially within urban canyons. As the industry moves towards Beyond Visual Line of Sight (BVLOS) and fully autonomous operations, resilience to weather perturbations will be key. As the human decision-maker is removed from the in-situ environment, producing control systems that are robust will be paramount to the preservation of any Airspace System. Safety requirements and regulations require quantifiable performance metrics to guarantee a safe aerial environment with ever- increasing traffic. In this regards, the effect of wind and weather disturbances on a UAS and its ability to reject these disturbances present some unique concerns. Currently, drone manufacturers and operators rely on outdoor testing during windy days (or in windy locations) and onboard logging to evaluate and improve the flight worthiness, reliability and perturbation rejection capability of their vehicles. Waiting for the desired weather or travelling to a windier location is cost- and time-inefficient. Moreover, the conditions found on outdoor test sites are difficult to quantify and repeatability is non-existent. To address this situation, a novel testing methodology is proposed, combining artificial wind generation thanks to a multi-fan array wind generator (windshaper), coherent GNSS signal generation and accurate tracking of the test subject thanks to motion capture cameras. In this environment, the drone being tested can fly freely, follow missions and experience wind perturbations whilst staying in a modest indoor volume. By coordinating the windshaper, the motion tracking feedback and the position emulated by the GNSS signal generator with the drone’s mission profile, it was demonstrated that outdoor flight conditions can be reliably recreated in a controlled and repeatable environment. Specifically, thanks to real-time update of the position simulated by the GNSS signal generator, it was possible to demonstrate that the drone’s perception of the situation is similar to a corresponding mission being executed outdoor. In this work, the drone was subjected to three distinct flight cases: (1) hover in 2 m s−1 wind, (2) forward flight at 2 m s−1 without wind and (3) forward flight at 2 m s−1 with 2 m s−1 headwind. In each case, it could be demonstrated that by using indoor GNSS signal simulation and wind generation, the drone displays the characteristics of a 20 m move forward, while actually staying stationary in the test volume, within ±1 m. Further development of this methodology opens the door for fully integrated hardware-in- the-loop simulation of drone flight operations. 
    more » « less
  5. Chiappa, Silvia ; Calandra, Roberto (Ed.)
    Langevin Monte Carlo (LMC) is an iterative algorithm used to generate samples from a distribution that is known only up to a normalizing constant. The nonasymptotic dependence of its mixing time on the dimension and target accuracy is understood mainly in the setting of smooth (gradient-Lipschitz) log-densities, a serious limitation for applications in machine learning. In this paper, we remove this limitation, providing polynomial-time convergence guarantees for a variant of LMC in the setting of nonsmooth log-concave distributions. At a high level, our results follow by leveraging the implicit smoothing of the log-density that comes from a small Gaussian perturbation that we add to the iterates of the algorithm and controlling the bias and variance that are induced by this perturbation. 
    more » « less