# Efficient Sampling from Time-Varying Log-Concave Distributions

arXiv: https://arxiv.org/abs/1309.5977 · HTML: https://mlsanity.com/paper/1309.5977/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2013.

## Built on by (most cited first, 7 of 7)

- [First- and Second-Order Bounds for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2305.00832/) (2023)
- [Embedded training of neural-network sub-grid-scale turbulence models](https://mlsanity.com/paper/2105.01030/) (2021)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Damped Online Newton Step for Portfolio Selection](https://mlsanity.com/paper/2202.07574/) (2022)
- [Sampling from Log-Concave Distributions with Infinity-Distance Guarantees](https://mlsanity.com/paper/2111.04089/) (2021)
- [Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk](https://mlsanity.com/paper/2206.09384/) (2022)
- [Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers](https://mlsanity.com/paper/2409.04320/) (2024)

## Abstract (arXiv)

We propose a computationally efficient random walk on a convex body which rapidly mixes and closely tracks a time-varying log-concave distribution. We develop general theoretical guarantees on the required number of steps; this number can be calculated on the fly according to the distance from and the shape of the next distribution. We then illustrate the technique on several examples. Within the context of exponential families, the proposed method produces samples from a posterior distribution which is updated as data arrive in a streaming fashion. The sampling technique can be used to track time-varying truncated distributions, as well as to obtain samples from a changing mixture model, fitted in a streaming fashion to data. In the setting of linear optimization, the proposed method has oracle complexity with best known dependence on the dimension for certain geometries. In the context of online learning and repeated games, the algorithm is an efficient method for implementing no-regret mixture forecasting strategies. Remarkably, in some of these examples, only one step of the random walk is needed to track the next distribution.