BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Eric Moulines

Eric Moulines appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.STStatistics TheoryMachine LearningMethodologymath.PRComputationmath.OCApplicationsArtificial IntelligenceOther Computer ScienceComputational Engineering, Finance, and ScienceInformation Theorymath.ITq-fin.TR

Catalog footprint

What is connected

48works
14topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

48 published item(s)

preprint2026arXiv

Bayesian Rain Field Reconstruction using Commercial Microwave Links and Diffusion Model Priors

Commercial Microwave Links (CMLs) offer dense spatial coverage for rainfall sensing but produce path-integrated measurements that make accurate ground-level reconstruction challenging. Existing methods typically oversimplify CMLs as point sensors and neglect line integration relating rainfall to signal attenuation, resulting in degraded performance under heterogeneous precipitation. In this work, we view rain field reconstruction as a Bayesian inverse problem with Diffusion Models (DMs) as high-fidelity spatial priors. We show that diffusion models better preserve key rainfall statistics compared to censored Gaussian processes. Framing rainfall estimation as a Bayesian inverse problem with a DM prior enables training-free posterior sampling using a broad family of methods, including Plug-and-Play, Sequential Monte Carlo, and Replica Exchange methods. Experiments on synthetic and real-world datasets demonstrate consistent improvements over established CML-based reconstruction baselines.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA). Our results provide the first federated Gaussian approximations for LSA that explicitly capture communication-computation trade-offs and heterogeneity-aware error terms, quantifying the effects of local step size, number of local updates, and heterogeneity on convergence rates. We present results for both (i) constant step size regime and (ii) decreasing step size with an increasing number of local iterations, recovering the recent rates of Bonnerjee et al. [2025] as a special case. As a primary application of our results, we develop an online multiplier bootstrap procedure for inference on the last iterate, which avoids explicit estimation of the asymptotic covariance matrix, and obtain non-asymptotic validity guarantees for this procedure.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

On Gaussian approximation for entropy-regularized Q-learning with function approximation

In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak--Ruppert averaged iterates generated by entropy-regularized asynchronous Q-learning with linear function approximation and a polynomial stepsize $k^{-ω}$, $ω\in (1/2,1)$. Assuming that the sequence of observed triples $(s_k,a_k,s_{k+1})_{k \geq 0}$ forms a uniformly geometrically ergodic Markov chain, and under suitable regularity conditions for the projected soft Bellman equation, we establish a Gaussian approximation bound in the convex distance with rate of order $n^{-1/4}$, up to polylogarithmic factors in $n$, where $n$ is the number of samples used by the algorithm. To obtain this result, we combine a linearization of the soft Bellman recursion with a Gaussian approximation for the leading martingale term. Finally, we derive high-order moment bounds for the algorithm's last iterate, which might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2026arXiv

Policy Gradient Methods for Non-Markovian Reinforcement Learning

We study policy gradient methods for reinforcement learning in non-Markovian decision processes (NMDPs), where observations and rewards depend on the entire interaction history. To handle this dependence, the agent maintains an internal state that is recursively updated to provide a compact summary of past observations and actions. In contrast to approaches that treat the agent state dynamics as fixed or learn it via predictive objectives, we propose a reward-centric formulation that jointly optimizes the agent state dynamics and the control policy to maximize the expected cumulative reward. To this end, we consider a class of Agent State-Markov (ASM) policies, comprising an agent state dynamics and a control policy that maps the agent state to actions. We establish a novel policy gradient theorem for ASM policies, extending the classical policy gradient results from the Markovian setting to episodic and infinite-horizon discounted NMDPs. Building on this gradient expression, we propose the Agent State-Markov Policy Gradient (ASMPG) algorithm, which leverages the recursive structure of the agent state dynamics for efficient optimization. We establish finite-time and almost sure convergence guarantees, and empirically demonstrate that, on a range of non-Markovian tasks, ASMPG outperforms baselines that learn state representations via predictive objectives.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

State and parameter learning with PaRIS particle Gibbs

Non-linear state-space models, also known as general hidden Markov models, are ubiquitous in statistical machine learning, being the most classical generative models for serial data and sequences in general. The particle-based, rapid incremental smoother PaRIS is a sequential Monte Carlo (SMC) technique allowing for efficient online approximation of expectations of additive functionals under the smoothing distribution in these models. Such expectations appear naturally in several learning contexts, such as likelihood estimation (MLE) and Markov score climbing (MSC). PARIS has linear computational complexity, limited memory requirements and comes with non-asymptotic bounds, convergence results and stability guarantees. Still, being based on self-normalised importance sampling, the PaRIS estimator is biased. Our first contribution is to design a novel additive smoothing algorithm, the Parisian particle Gibbs PPG sampler, which can be viewed as a PaRIS algorithm driven by conditional SMC moves, resulting in bias-reduced estimates of the targeted quantities. We substantiate the PPG algorithm with theoretical results, including new bounds on bias and variance as well as deviation inequalities. Our second contribution is to apply PPG in a learning framework, covering MLE and MSC as special examples. In this context, we establish, under standard assumptions, non-asymptotic bounds highlighting the value of bias reduction and the implicit Rao--Blackwellization of PPG. These are the first non-asymptotic results of this kind in this setting. We illustrate our theoretical results with numerical experiments supporting our claims.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

BR-SNIS: Bias Reduced Self-Normalized Importance Sampling

Importance Sampling (IS) is a method for approximating expectations under a target distribution using independent samples from a proposal distribution and the associated importance weights. In many applications, the target distribution is known only up to a normalization constant, in which case self-normalized IS (SNIS) can be used. While the use of self-normalization can have a positive effect on the dispersion of the estimator, it introduces bias. In this work, we propose a new method, BR-SNIS, whose complexity is essentially the same as that of SNIS and which significantly reduces bias without increasing the variance. This method is a wrapper in the sense that it uses the same proposal samples and importance weights as SNIS, but makes clever use of iterated sampling--importance resampling (ISIR) to form a bias-reduced version of the estimator. We furnish the proposed algorithm with rigorous theoretical results, including new bias, variance and high-probability bounds, and these are illustrated by numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Diffusion bridges vector quantized Variational AutoEncoders

Vector Quantized-Variational AutoEncoders (VQ-VAE) are generative models based on discrete latent representations of the data, where inputs are mapped to a finite set of learned embeddings.To generate new samples, an autoregressive prior distribution over the discrete states must be trained separately. This prior is generally very complex and leads to slow generation. In this work, we propose a new model to train the prior and the encoder/decoder networks simultaneously. We build a diffusion bridge between a continuous coded vector and a non-informative prior distribution. The latent discrete states are then given as random functions of these continuous vectors. We show that our model is competitive with the autoregressive prior on the mini-Imagenet and CIFAR dataset and is efficient in both optimization and sampling. Our framework also extends the standard VQ-VAE and enables end-to-end training.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses

We propose the Bayes-UCBVI algorithm for reinforcement learning in tabular, stage-dependent, episodic Markov decision process: a natural extension of the Bayes-UCB algorithm by Kaufmann et al. (2012) for multi-armed bandits. Our method uses the quantile of a Q-value function posterior as upper confidence bound on the optimal Q-value function. For Bayes-UCBVI, we prove a regret bound of order $\widetilde{O}(\sqrt{H^3SAT})$ where $H$ is the length of one episode, $S$ is the number of states, $A$ the number of actions, $T$ the number of episodes, that matches the lower-bound of $Ω(\sqrt{H^3SAT})$ up to poly-$\log$ terms in $H,S,A,T$ for a large enough $T$. To the best of our knowledge, this is the first algorithm that obtains an optimal dependence on the horizon $H$ (and $S$) without the need for an involved Bernstein-like bonus or noise. Crucial to our analysis is a new fine-grained anti-concentration bound for a weighted Dirichlet sum that can be of independent interest. We then explain how Bayes-UCBVI can be easily extended beyond the tabular setting, exhibiting a strong link between our algorithm and Bayesian bootstrap (Rubin, 1981).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning

The objective of Federated Learning (FL) is to perform statistical inference for data which are decentralised and stored locally on networked clients. FL raises many constraints which include privacy and data ownership, communication overhead, statistical heterogeneity, and partial client participation. In this paper, we address these problems in the framework of the Bayesian paradigm. To this end, we propose a novel federated Markov Chain Monte Carlo algorithm, referred to as Quantised Langevin Stochastic Dynamics which may be seen as an extension to the FL setting of Stochastic Gradient Langevin Dynamics, which handles the communication bottleneck using gradient compression. To improve performance, we then introduce variance reduction techniques, which lead to two improved versions coined \texttt{QLSD}$^{\star}$ and \texttt{QLSD}$^{++}$. We give both non-asymptotic and asymptotic convergence guarantees for the proposed algorithms. We illustrate their performances using various Bayesian Federated Learning benchmarks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Variational Inference of overparameterized Bayesian Neural Networks: a theoretical and empirical study

This paper studies the Variational Inference (VI) used for training Bayesian Neural Networks (BNN) in the overparameterized regime, i.e., when the number of neurons tends to infinity. More specifically, we consider overparameterized two-layer BNN and point out a critical issue in the mean-field VI training. This problem arises from the decomposition of the lower bound on the evidence (ELBO) into two terms: one corresponding to the likelihood function of the model and the second to the Kullback-Leibler (KL) divergence between the prior distribution and the variational posterior. In particular, we show both theoretically and empirically that there is a trade-off between these two terms in the overparameterized regime only when the KL is appropriately re-scaled with respect to the ratio between the the number of observations and neurons. We also illustrate our theoretical results with numerical experiments that highlight the critical choice of this ratio.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning

This paper studies the exponential stability of random matrix products driven by a general (possibly unbounded) state space Markov chain. It is a cornerstone in the analysis of stochastic algorithms in machine learning (e.g. for parameter tracking in online learning or reinforcement learning). The existing results impose strong conditions such as uniform boundedness of the matrix-valued functions and uniform ergodicity of the Markov chains. Our main contribution is an exponential stability result for the $p$-th moment of random matrix product, provided that (i) the underlying Markov chain satisfies a super-Lyapunov drift condition, (ii) the growth of the matrix-valued functions is controlled by an appropriately defined function (related to the drift condition). Using this result, we give finite-time $p$-th moment bounds for constant and decreasing stepsize linear stochastic approximation schemes with Markovian noise on general state space. We illustrate these findings for linear value-function estimation in reinforcement learning. We provide finite-time $p$-th moment bound for various members of temporal difference (TD) family of algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise

Linear two-timescale stochastic approximation (SA) scheme is an important class of algorithms which has become popular in reinforcement learning (RL), particularly for the policy evaluation problem. Recently, a number of works have been devoted to establishing the finite time analysis of the scheme, especially under the Markovian (non-i.i.d.) noise settings that are ubiquitous in practice. In this paper, we provide a finite-time analysis for linear two timescale SA. Our bounds show that there is no discrepancy in the convergence rate between Markovian and martingale noise, only the constants are affected by the mixing time of the Markov chain. With an appropriate step size schedule, the transient term in the expected error bound is $o(1/k^c)$ and the steady-state term is ${\cal O}(1/k)$, where $c>1$ and $k$ is the iteration number. Furthermore, we present an asymptotic expansion of the expected error with a matching lower bound of $Ω(1/k)$. A simple numerical experiment is presented to support our theory.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

MetFlow: A New Efficient Method for Bridging the Gap between Markov Chain Monte Carlo and Variational Inference

In this contribution, we propose a new computationally efficient method to combine Variational Inference (VI) with Markov Chain Monte Carlo (MCMC). This approach can be used with generic MCMC kernels, but is especially well suited to \textit{MetFlow}, a novel family of MCMC algorithms we introduce, in which proposals are obtained using Normalizing Flows. The marginal distribution produced by such MCMC algorithms is a mixture of flow-based distributions, thus drastically increasing the expressivity of the variational family. Unlike previous methods following this direction, our approach is amenable to the reparametrization trick and does not rely on computationally expensive reverse kernels. Extensive numerical experiments show clear computational and performance improvements over state-of-the-art methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On stability of a class of filters for non-linear stochastic systems

This article develops a comprehensive framework for stability analysis of a broad class of commonly used continuous and discrete time-filters for stochastic dynamic systems with non-linear state dynamics and linear measurements under certain strong assumptions. The class of filters encompasses the extended and unscented Kalman filters and most other Gaussian assumed density filters and their numerical integration approximations. The stability results are in the form of time-uniform mean square bounds and exponential concentration inequalities for the filtering error. In contrast to existing results, it is not always necessary for the model to be exponentially stable or fully observed. We review three classes of models that can be rigorously shown to satisfy the stringent assumptions of the stability theorems. Numerical experiments using synthetic data validate the derived error bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convergence of Markovian Stochastic Approximation with discontinuous dynamics

This paper is devoted to the convergence analysis of stochastic approximation algorithms of the form $θ\_{n+1} = θ\_n + γ\_{n+1} H\_{θ\_n}(X\_{n+1})$ where $\{θ\_nn, n \geq 0\}$ is a $R^d$-valued sequence, $\{γ, n \geq 0\}$ is a deterministic step-size sequence and $\{X\_n, n \geq 0\}$ is a controlled Markov chain. We study the convergence under weak assumptions on smoothness-in-$θ$ of the function $θ\mapsto H\_θ(x)$. It is usually assumed that this function is continuous for any $x$; in this work, we relax this condition. Our results are illustrated by considering stochastic approximation algorithms for (adaptive) quantile estimation and a penalized version of the vector quantization.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreau

Modern imaging methods rely strongly on Bayesian inference techniques to solve challenging imaging problems. Currently, the predominant Bayesian computation approach is convex optimisation, which scales very efficiently to high dimensional image models and delivers accurate point estimation results. However, in order to perform more complex analyses, for example image uncertainty quantification or model selection, it is necessary to use more computationally intensive Bayesian computation techniques such as Markov chain Monte Carlo methods. This paper presents a new and highly efficient Markov chain Monte Carlo methodology to perform Bayesian computation for high dimensional models that are log-concave and non-smooth, a class of models that is central in imaging sciences. The methodology is based on a regularised unadjusted Langevin algorithm that exploits tools from convex analysis, namely Moreau-Yoshida envelopes and proximal operators, to construct Markov chains with favourable convergence properties. In addition to scaling efficiently to high dimensions, the method is straightforward to apply to models that are currently solved by using proximal optimisation algorithms. We provide a detailed theoretical analysis of the proposed methodology, including asymptotic and non-asymptotic convergence results with easily verifiable conditions, and explicit bounds on the convergence rates. The proposed methodology is demonstrated with four experiments related to image deconvolution and tomographic reconstruction with total-variation and $\ell_1$ priors, where we conduct a range of challenging Bayesian analyses related to uncertainty quantification, hypothesis testing, and model selection in the absence of ground truth.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fixed Rank Kriging for Cellular Coverage Analysis

Coverage planning and optimization is one of the most crucial tasks for a radio network operator. Efficient coverage optimization requires accurate coverage estimation. This estimation relies on geo-located field measurements which are gathered today during highly expensive drive tests (DT); and will be reported in the near future by users' mobile devices thanks to the 3GPP Minimizing Drive Tests (MDT) feature~\cite{3GPPproposal}. This feature consists in an automatic reporting of the radio measurements associated with the geographic location of the user's mobile device. Such a solution is still costly in terms of battery consumption and signaling overhead. Therefore, predicting the coverage on a location where no measurements are available remains a key and challenging task. This paper describes a powerful tool that gives an accurate coverage prediction on the whole area of interest: it builds a coverage map by spatially interpolating geo-located measurements using the Kriging technique. The paper focuses on the reduction of the computational complexity of the Kriging algorithm by applying Fixed Rank Kriging (FRK). The performance evaluation of the FRK algorithm both on simulated measurements and real field measurements shows a good trade-off between prediction efficiency and computational complexity. In order to go a step further towards the operational application of the proposed algorithm, a multicellular use-case is studied. Simulation results show a good performance in terms of coverage prediction and detection of the best serving cell.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm

In this paper, we study a method to sample from a target distribution $π$ over $\mathbb{R}^d$ having a positive density with respect to the Lebesgue measure, known up to a normalisation factor. This method is based on the Euler discretization of the overdamped Langevin stochastic differential equation associated with $π$. For both constant and decreasing step sizes in the Euler discretization, we obtain non-asymptotic bounds for the convergence to the target distribution $π$ in total variation distance. A particular attention is paid to the dependency on the dimension $d$, to demonstrate the applicability of this method in the high dimensional setting. These bounds improve and extend the results of (Dalalyan 2014).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Nonparametric estimation of mark's distribution of an exponential Shot-noise process

In this paper, we consider a nonlinear inverse problem occurring in nuclear science. Gamma rays randomly hit a semiconductor detector which produces an impulse response of electric current. Because the sampling period of the measured current is larger than the mean inter arrival time of photons, the impulse responses associated to different gamma rays can overlap: this phenomenon is known as pileup. In this work, it is assumed that the impulse response is an exponentially decaying function. We propose a novel method to infer the distribution of gamma photon energies from the indirect measurements obtained from the detector. This technique is based on a formula linking the characteristic function of the photon density to a function involving the characteristic function and its derivative of the observations. We establish that our estimator converges to the mark density in uniform norm at a logarithmic rate. A limited Monte-Carlo experiment is provided to support our findings.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On perturbed proximal gradient algorithms

We study a version of the proximal gradient algorithm for which the gradient is intractable and is approximated by Monte Carlo methods (and in particular Markov Chain Monte Carlo). We derive conditions on the step size and the Monte Carlo batch size under which convergence is guaranteed: both increasing batch size and constant batch size are considered. We also derive non-asymptotic bounds for an averaged version. Our results cover both the cases of biased and unbiased Monte Carlo approximation. To support our findings, we discuss the inference of a sparse generalized linear model with random effect and the problem of learning the edge structure and parameters of sparse undirected graphical models.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Online Frank-Wolfe Algorithms for Convex and Non-convex Optimizations

In this paper, the online variants of the classical Frank-Wolfe algorithm are considered. We consider minimizing the regret with a stochastic cost. The online algorithms only require simple iterative updates and a non-adaptive step size rule, in contrast to the hybrid schemes commonly considered in the literature. Several new results are derived for convex and non-convex losses. With a strongly convex stochastic cost and when the optimal solution lies in the interior of the constraint set or the constraint set is a polytope, the regret bound and anytime optimality are shown to be ${\cal O}( \log^3 T / T )$ and ${\cal O}( \log^2 T / T)$, respectively, where $T$ is the number of rounds played. These results are based on an improved analysis on the stochastic Frank-Wolfe algorithms. Moreover, the online algorithms are shown to converge even when the loss is non-convex, i.e., the algorithms find a stationary point to the time-varying/stochastic loss at a rate of ${\cal O}(\sqrt{1/T})$. Numerical experiments on realistic data sets are presented to support our theoretical claims.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the two-filter approximations of marginal smoothing distributions in general state space models

A prevalent problem in general state space models is the approximation of the smoothing distribution of a state conditional on the observations from the past, the present, and the future. The aim of this paper is to provide a rigorous analysis of such approximations of smoothed distributions provided by the two-filter algorithms. We extend the results available for the approximation of smoothing distributions to these two-filter approaches which combine a forward filter approximating the filtering distributions with a backward information filter approximating a quantity proportional to the posterior distribution of the state given future observations.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online EM for Functional Data

A novel approach to perform unsupervised sequential learning for functional data is proposed. Our goal is to extract reference shapes (referred to as templates) from noisy, deformed and censored realizations of curves and images. Our model generalizes the Bayesian dense deformable template model (Allassonnière et al., 2007), a hierarchical model in which the template is the function to be estimated and the deformation is a nuisance, assumed to be random with a known prior distribution. The templates are estimated using a Monte Carlo version of the online Expectation-Maximization algorithm, extending the work from Cappé and Moulines (2009). Our sequential inference framework is significantly more computationally efficient than equivalent batch learning algorithms, especially when the missing data is high-dimensional. Some numerical illustrations on curve registration problem and templates extraction from images are provided to support our findings.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal scaling of the Random Walk Metropolis algorithm under Lp mean differentiability

This paper considers the optimal scaling problem for high-dimensional random walk Metropolis algorithms for densities which are differentiable in Lp mean but which may be irregular at some points (like the Laplace density for example) and/or are supported on an interval. Our main result is the weak convergence of the Markov chain (appropriately rescaled in time and space) to a Langevin diffusion process as the dimension d goes to infinity. Because the log-density might be non-differentiable, the limiting diffusion could be singular. The scaling limit is established under assumptions which are much weaker than the one used in the original derivation of [6]. This result has important practical implications for the use of random walk Metropolis algorithms in Bayesian frameworks based on sparsity inducing priors.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Spatial Prediction Under Location Uncertainty In Cellular Networks

Coverage optimization is an important process for the operator as it is a crucial prerequisite towards offering a satisfactory quality of service to the end-users. The first step of this process is coverage prediction, which can be performed by interpolating geo-located measurements reported to the network by mobile users' equipments. In previous works, we proposed a low complexity coverage prediction algorithm based on the adaptation of the Geo-statistics Fixed Rank Kriging (FRK) algorithm. We supposed that the geo-location information reported with the radio measurements was perfect, which is not the case in reality. In this paper, we study the impact of location uncertainty on the coverage prediction accuracy and we extend the previously proposed algorithm to include geo-location error in the prediction model. We validate the proposed algorithm using both simulated and real field measurements. The FRK extended to take into account the location uncertainty proves to enhance the prediction accuracy while keeping a reasonable computational complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A shrinkage-thresholding Metropolis adjusted Langevin algorithm for Bayesian variable selection

This paper introduces a new Markov Chain Monte Carlo method for Bayesian variable selection in high dimensional settings. The algorithm is a Hastings-Metropolis sampler with a proposal mechanism which combines a Metropolis Adjusted Langevin (MALA) step to propose local moves associated with a shrinkage-thresholding step allowing to propose new models. The geometric ergodicity of this new trans-dimensional Markov Chain Monte Carlo sampler is established. An extensive numerical experiment, on simulated and real data, is presented to illustrate the performance of the proposed algorithm in comparison with some more classical trans-dimensional algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Blocking Strategies and Stability of Particle Gibbs Samplers

Sampling from the conditional (or posterior) probability distribution of the latent states of a Hidden Markov Model, given the realization of the observed process, is a non-trivial problem in the context of Markov Chain Monte Carlo. To do this Andrieu et al. (2010) constructed a Markov kernel which leaves this conditional distribution invariant using a Particle Filter. From a practitioner's point of view, this Markov kernel attempts to mimic the act of sampling all the latent state variables as one block from the posterior distribution but for models where exact simulation is not possible. There are some recent theoretical results that establish the uniform ergodicity of this Markov kernel and that the mixing rate does not diminish provided the number of particles grows at least linearly with the number of latent states in the posterior. This gives rise to a cost, per application of the kernel, that is quadratic in the number of latent states which could be prohibitive for long observation sequences. We seek to answer an obvious but important question: is there a different implementation with a cost per-iteration that grows linearly with the number of latent states, but which is still stable in the sense that its mixing rate does not deteriorate? We address this problem using blocking strategies, which are easily parallelizable, and prove stability of the resulting sampler.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Subgeometric rates of convergence in Wasserstein distance for Markov chains

In this paper, we provide sufficient conditions for the existence of the invariant distribution and for subgeometric rates of convergence in Wasserstein distance for general state-space Markov chains which are (possibly) not irreducible. Compared to previous work, our approach is based on a purely probabilistic coupling construction which allows to retrieve rates of convergence matching those previously reported for convergence in total variation. Our results are applied to establish the subgeometric ergodicity in Wasserstein distance of non-linear autoregressive models and of the pre-conditioned Crank-Nicolson Markov chain Monte Carlo algorithm in Hilbert space.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Long-term stability of sequential Monte Carlo methods under verifiable conditions

This paper discusses particle filtering in general hidden Markov models (HMMs) and presents novel theoretical results on the long-term stability of bootstrap-type particle filters. More specifically, we establish that the asymptotic variance of the Monte Carlo estimates produced by the bootstrap filter is uniformly bounded in time. On the contrary to most previous results of this type, which in general presuppose that the state space of the hidden state process is compact (an assumption that is rarely satisfied in practice), our very mild assumptions are satisfied for a large class of HMMs with possibly noncompact state space. In addition, we derive a similar time uniform bound on the asymptotic $\mathsf{L}^p$ error. Importantly, our results hold for misspecified models; that is, we do not at all assume that the data entering into the particle filter originate from the model governing the dynamics of the particles or not even from an HMM.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Probabilistic low-rank matrix completion on finite alphabets

The task of reconstructing a matrix given a sample of observedentries is known as the matrix completion problem. It arises ina wide range of problems, including recommender systems, collaborativefiltering, dimensionality reduction, image processing, quantum physics or multi-class classificationto name a few. Most works have focused on recovering an unknown real-valued low-rankmatrix from randomly sub-sampling its entries.Here, we investigate the case where the observations take a finite number of values, corresponding for examples to ratings in recommender systems or labels in multi-class classification.We also consider a general sampling scheme (not necessarily uniform) over the matrix entries.The performance of a nuclear-norm penalized estimator is analyzed theoretically.More precisely, we derive bounds for the Kullback-Leibler divergence between the true and estimated distributions.In practice, we have also proposed an efficient algorithm based on lifted coordinate gradient descent in order to tacklepotentially high dimensional settings.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Uniform ergodicity of the Particle Gibbs sampler

The particle Gibbs (PG) sampler is a systematic way of using a particle filter within Markov chain Monte Carlo (MCMC). This results in an off-the-shelf Markov kernel on the space of state trajectories, which can be used to simulate from the full joint smoothing distribution for a state space model in an MCMC scheme. We show that the PG Markov kernel is uniformly ergodic under rather general assumptions, that we will carefully review and discuss. In particular, we provide an explicit rate of convergence which reveals that: (i) for fixed number of data points, the convergence rate can be made arbitrarily good by increasing the number of particles, and (ii) under general mixing assumptions, the convergence rate can be kept constant by increasing the number of particles superlinearly with the number of observations. We illustrate the applicability of our result by studying in detail two common state space models with non-compact state spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Adaptive Equi-Energy Sampler : Convergence and Illustration

Markov chain Monte Carlo (MCMC) methods allow to sample a distribution known up to a multiplicative constant. Classical MCMC samplers are known to have very poor mixing properties when sampling multimodal distributions. The Equi-Energy sampler is an interacting MCMC sampler proposed by Kou, Zhou and Wong in 2006 to sample difficult multimodal distributions. This algorithm runs several chains at different temperatures in parallel, and allow lower-tempered chains to jump to a state from a higher-tempered chain having an energy 'close' to that of the current state. A major drawback of this algorithm is that it depends on many design parameters and thus, requires a significant effort to tune these parameters. In this paper, we introduce an Adaptive Equi-Energy (AEE) sampler which automates the choice of the selection mecanism when jumping onto a state of the higher-temperature chain. We prove the ergodicity and a strong law of large numbers for AEE, and for the original Equi-Energy sampler as well. Finally, we apply our algorithm to motif sampling in DNA sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Asymptotic properties of the maximum likelihood estimation in misspecified hidden Markov models

Let $(Y_k)_{k\in \mathbb{Z}}$ be a stationary sequence on a probability space $(Ω,\mathcal{A},\mathbb{P})$ taking values in a standard Borel space $\mathsf{Y}$. Consider the associated maximum likelihood estimator with respect to a parametrized family of hidden Markov models such that the law of the observations $(Y_k)_{k\in \mathbb{Z}}$ is not assumed to be described by any of the hidden Markov models of this family. In this paper we investigate the consistency of this estimator in such misspecified models under mild assumptions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

We consider the stochastic approximation problem where a convex function has to be minimized, given only the knowledge of unbiased estimates of its gradients at certain points, a framework which includes machine learning methods based on the minimization of the empirical risk. We focus on problems without strong convexity, for which all previously known algorithms achieve a convergence rate for function values of O(1/n^{1/2}). We consider and analyze two algorithms that achieve a rate of O(1/n) for classical supervised learning problems. For least-squares regression, we show that averaged stochastic gradient descent with constant step-size achieves the desired rate. For logistic regression, this is achieved by a simple novel stochastic gradient algorithm that (a) constructs successive local quadratic approximations of the loss functions, while (b) preserving the same running time complexity as stochastic gradient descent. For these algorithms, we provide a non-asymptotic analysis of the generalization error (in expectation, and also in high probability for least-squares), and run extensive experiments on standard machine learning benchmarks showing that they often outperform existing approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On parallel implementation of Sequential Monte Carlo methods: the island particle model

The approximation of the Feynman-Kac semigroups by systems of interacting particles is a very active research field, with applications in many different areas. In this paper, we study the parallelization of such approximations. The total population of particles is divided into sub-populations, referred to as \emph{islands}. The particles within each island follow the usual selection / mutation dynamics. We show that the evolution of each island is also driven by a Feynman-Kac semigroup, whose transition and potential can be explicitly related to ones of the original problem. Therefore, the same genetic type approximation of the Feynman-Kac semi-group may be used at the island level; each island might undergo selection / mutation algorithm. We investigate the impact of the population size within each island and the number of islands, and study different type of interactions. We find conditions under which introducing interactions between islands is beneficial. The theoretical results are supported by some Monte Carlo experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Adaptive parallel tempering algorithm

Parallel tempering is a generic Markov chain Monte Carlo sampling method which allows good mixing with multimodal target distributions, where conventional Metropolis-Hastings algorithms often fail. The mixing properties of the sampler depend strongly on the choice of tuning parameters, such as the temperature schedule and the proposal distribution used for local exploration. We propose an adaptive algorithm which tunes both the temperature schedule and the parameters of the random-walk Metropolis kernel automatically. We prove the convergence of the adaptation and a strong law of large numbers for the algorithm. We illustrate the performance of our method with examples. Our empirical findings indicate that the algorithm can cope well with different kind of scenarios without prior tuning.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Ergodicity of observation-driven time series models and consistency of the maximum likelihood estimator

This paper deals with a general class of observation-driven time series models with a special focus on time series of counts. We provide conditions under which there exist strict-sense stationary and ergodic versions of such processes. The consistency of the maximum likelihood estimators is then derived for well- specified and misspecified models.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Price Jump Prediction in Limit Order Book

A limit order book provides information on available limit order prices and their volumes. Based on these quantities, we give an empirical result on the relationship between the bid-ask liquidity balance and trade sign and we show that liquidity balance on best bid/best ask is quite informative for predicting the future market order's direction. Moreover, we define price jump as a sell (buy) market order arrival which is executed at a price which is smaller (larger) than the best bid (best ask) price at the moment just after the precedent market order arrival. Features are then extracted related to limit order volumes, limit order price gaps, market order information and limit order event information. Logistic regression is applied to predict the price jump from the limit order book's feature. LASSO logistic regression is introduced to help us make variable selection from which we are capable to highlight the importance of different features in predicting the future price jump. In order to get rid of the intraday data seasonality, the analysis is based on two separated datasets: morning dataset and afternoon dataset. Based on an analysis on forty largest French stocks of CAC40, we find that trade sign and market order size as well as the liquidity on the best bid (best ask) are consistently informative for predicting the incoming price jump.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Sequential Monte Carlo smoothing for general state space hidden Markov models

Computing smoothing distributions, the distributions of one or more states conditional on past, present, and future observations is a recurring problem when operating on general hidden Markov models. The aim of this paper is to provide a foundation of particle-based approximation of such distributions and to analyze, in a common unifying framework, different schemes producing such approximations. In this setting, general convergence results, including exponential deviation inequalities and central limit theorems, are established. In particular, time uniform bounds on the marginal smoothing error are obtained under appropriate mixing conditions on the transition kernel of the latent chain. In addition, we propose an algorithm approximating the joint smoothing distribution at a cost that grows only linearly with the number of particles.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A central limit theorem for adaptive and interacting Markov chains

Adaptive and interacting Markov Chains Monte Carlo (MCMC) algorithms are a novel class of non-Markovian algorithms aimed at improving the simulation efficiency for complicated target distributions. In this paper, we study a general (non-Markovian) simulation framework covering both the adaptive and interacting MCMC algorithms. We establish a Central Limit Theorem for additive functionals of unbounded functions under a set of verifiable conditions, and identify the asymptotic variance. Our result extends all the results reported so far. An application to the interacting tempering algorithm (a simplified version of the equi-energy sampler) is presented to support our claims.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A simple variance inequality for U-statistics of a Markov chain with applications

We establish a simple variance inequality for U-statistics whose underlying sequence of random variables is an ergodic Markov Chain. The constants in this inequality are explicit and depend on computable bounds on the mixing rate of the Markov Chain. We apply this result to derive the strong law of large number for U-statistics of a Markov Chain under conditions which are close from being optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Consistency of the maximum likelihood estimator for general hidden Markov models

Consider a parametrized family of general hidden Markov models, where both the observed and unobserved components take values in a complete separable metric space. We prove that the maximum likelihood estimator (MLE) of the parameter is strongly consistent under a rather minimal set of assumptions. As special cases of our main result, we obtain consistency in a large class of nonlinear state space models, as well as general results on linear Gaussian state space models and finite state models. A novel aspect of our approach is an information-theoretic technique for proving identifiability, which does not require an explicit representation for the relative entropy rate. Our method of proof could therefore form a foundation for the investigation of MLE consistency in more general dependent and non-Markovian time series. Also of independent interest is a general concentration inequality for $V$-uniformly ergodic Markov chains.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Testing for homogeneity of variance in the wavelet domain

The danger of confusing long-range dependence with non-stationarity has been pointed out by many authors. Finding an answer to this difficult question is of importance to model time-series showing trend-like behavior, such as river run-off in hydrology, historical temperatures in the study of climates changes, or packet counts in network traffic engineering. The main goal of this paper is to develop a test procedure to detect the presence of non-stationarity for a class of processes whose $K$-th order difference is stationary. Contrary to most of the proposed methods, the test procedure has the same distribution for short-range and long-range dependence covariance stationary processes, which means that this test is able to detect the presence of non-stationarity for processes showing long-range dependence or which are unit root. The proposed test is formulated in the wavelet domain, where a change in the generalized spectral density results in a change in the variance of wavelet coefficients at one or several scales. Such tests have been already proposed in \cite{whitcher:2001}, but these authors do not have taken into account the dependence of the wavelet coefficients within scales and between scales. Therefore, the asymptotic distribution of the test they have proposed was erroneous; as a consequence, the level of the test under the null hypothesis of stationarity was wrong. In this contribution, we introduce two test procedures, both using an estimator of the variance of the scalogram at one or several scales. The asymptotic distribution of the test under the null is rigorously justified. The pointwise consistency of the test in the presence of a single jump in the general spectral density is also be presented. A limited Monte-Carlo experiment is performed to illustrate our findings.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Asymptotic properties of U-processes under long-range dependence

Let $(X_i)_{i\geq 1}$ be a stationary mean-zero Gaussian process with covariances $ρ(k)=\PE(X_{1}X_{k+1})$ satisfying: $ρ(0)=1$ and $ρ(k)=k^{-D} L(k)$ where $D$ is in $(0,1)$ and $L$ is slowly varying at infinity. Consider the $U$-process $\{U_n(r),\; r\in I\}$ defined as $$ U_n(r)=\frac{1}{n(n-1)}\sum_{1\leq i\neq j\leq n}\1_{\{G(X_i,X_j)\leq r\}}\; , $$ where $I$ is an interval included in $\rset$ and $G$ is a symmetric function. In this paper, we provide central and non-central limit theorems for $U_n$. They are used to derive the asymptotic behavior of the Hodges-Lehmann estimator, the Wilcoxon-signed rank statistic, the sample correlation integral and an associated scale estimator. The limiting distributions are expressed through multiple Wiener-Itô integrals.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Central limit theorem for the robust log-regression wavelet estimation of the memory parameter in the Gaussian semi-parametric context

In this paper, we study robust estimators of the memory parameter d of a (possibly) non stationary Gaussian time series with generalized spectral density f. This generalized spectral density is characterized by the memory parameter d and by a function f* which specifies the short-range dependence structure of the process. Our setting is semi-parametric since both f* and d are unknown and d is the only parameter of interest. The memory parameter d is estimated by regressing the logarithm of the estimated variance of the wavelet coefficients at different scales. The two estimators of d that we consider are based on robust estimators of the variance of the wavelet coefficients, namely the square of the scale estimator proposed by Rousseeuw and Croux (1993) and the median of the square of the wavelet coefficients. We establish a Central Limit Theorem for these robust estimators as well as for the estimator of d based on the classical estimator of the variance proposed by Moulines, Roueff and Taqqu (2007). Some Monte-Carlo experiments are presented to illustrate our claims and compare the performance of the different estimators. The properties of the three estimators are also compared on the Nile River data and the Internet traffic packet counts data. The theoretical results and the empirical evidence strongly suggest using the robust estimators as an alternative to estimate the memory parameter d of Gaussian time series.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Estimation of the autocovariance function with missing observations

We propose a novel estimator of the autocorrelation function in presence of missing observations. We establish the consistency, the asymptotic normality, and we derive deviation bounds for various classes of weakly dependent stationary time series, including causal or non causal models. In addition, we introduce a modified version periodogram defined from these autocorrelation estimators and derive asymptotic distribution of linear functionals of this estimator.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

High-Rate Quantization for the Neyman-Pearson Detection of Hidden Markov Processes

This paper investigates the decentralized detection of Hidden Markov Processes using the Neyman-Pearson test. We consider a network formed by a large number of distributed sensors. Sensors' observations are noisy snapshots of a Markov process to be detected. Each (real) observation is quantized on log2(N) bits before being transmitted to a fusion center which makes the final decision. For any false alarm level, it is shown that the miss probability of the Neyman-Pearson test converges to zero exponentially as the number of sensors tends to infinity. The error exponent is provided using recent results on Hidden Markov Models. In order to obtain informative expressions of the error exponent as a function of the quantization rule, we further investigate the case where the number N of quantization levels tends to infinity, following the approach developed in [Gupta & Hero, 2003]. In this regime, we provide the quantization rule maximizing the error exponent. Illustration of our results is provided in the case of the detection of a Gauss-Markov signal in noise. In terms of error exponent, the proposed quantization rule significantly outperforms the one proposed by [Gupta & Hero, 2003] for i.i.d. observations.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Comparison of Resampling Schemes for Particle Filtering

This contribution is devoted to the comparison of various resampling approaches that have been proposed in the literature on particle filtering. It is first shown using simple arguments that the so-called residual and stratified methods do yield an improvement over the basic multinomial resampling approach. A simple counter-example showing that this property does not hold true for systematic resampling is given. Finally, some results on the large-sample behavior of the simple bootstrap filter algorithm are given. In particular, a central limit theorem is established for the case where resampling is performed using the residual approach.

0 citations0 reviewsNo code linkedOpen access