Although Generative Flow Networks (GFlowNets) are designed to capture multiple modes of a reward function, they often suffer from mode collapse in practice, getting trapped in early-discovered modes and requiring prolonged training to find diverse solutions. Existing exploration techniques often rely on heuristic novelty signals. We propose Loss-Guided GFlowNets (LGGFN), a novel approach where an auxiliary GFlowNet's exploration is directly driven by the main GFlowNet's training loss. By prioritizing trajectories where the main model exhibits high loss, LGGFN focuses sampling on poorly understood regions of the state space. This targeted exploration significantly accelerates the discovery of diverse, high-reward samples. Empirically, across diverse benchmarks including grid environments, structured sequence generation, Bayesian structure learning, and biological sequence design, LGGFN consistently outperforms baselines in exploration efficiency and sample diversity. For instance, on a challenging sequence generation task, it discovered over 40 times more unique valid modes while simultaneously reducing the exploration error metric by approximately 99%.

In this paper, we present the Federated Upper Confidence Bound Value Iteration algorithm ($\texttt{Fed-UCBVI}$), a novel extension of the $\texttt{UCBVI}$ algorithm (Azar et al., 2017) tailored for the federated learning framework. We prove that the regret of $\texttt{Fed-UCBVI}$ scales as $\tilde O(\sqrt{H^3 |S| |A| T / M})$, with a small additional term due to heterogeneity, where $|S|$ is the number of states, $|A|$ is the number of actions, $H$ is the episode length, $M$ is the number of agents, and $T$ is the number of episodes. Notably, in the single-agent setting, this upper bound matches the minimax lower bound up to polylogarithmic factors, while in the multi-agent scenario, $\texttt{Fed-UCBVI}$ has linear speed-up. To conduct our analysis, we introduce a new measure of heterogeneity, which may hold independent theoretical interest. Furthermore, we show that, unlike existing federated reinforcement learning approaches, $\texttt{Fed-UCBVI}$’s communication complexity only marginally increases with the number of agents.

In this paper, we present a novel analysis of $\texttt{FedAvg}$ with constant step size, relying on the Markov property of the underlying process. We demonstrate that the global iterates of the algorithm converge to a stationary distribution and analyze its resulting bias and variance relative to the problem’s solution. We provide a first-order bias expansion in both homogeneous and heterogeneous settings. Interestingly, this bias decomposes into two distinct components: one that depends solely on stochastic gradient noise and another on client heterogeneity. Finally, we introduce a new algorithm based on the Richardson-Romberg extrapolation technique to mitigate this bias.

Synchronous federated learning (FL) scales poorly with the number of clients due to the straggler effect. Algorithms like FedAsync and GeneralizedFedAsync address this limitation by enabling asynchronous communication between clients and the central server. In this work, we rely on stochastic modeling and analysis to better understand the impact of design choices in asynchronous FL algorithms, such as the concurrency level and routing probabilities, and we leverage this knowledge to optimize loss. Compared to most existing studies, we account for the joint impact of heterogeneous and variable service speeds and heterogeneous datasets at the clients. We characterize in particular a fundamental trade-off for optimizing asynchronous FL: minimizing gradient estimation errors by avoiding model parameter staleness, while also speeding up the system by increasing the throughput of model updates. Our two main contributions can be summarized as follows. First, we prove a discrete variant of Little’s law to derive a closed-form expression for relative delay, a metric that quantifies staleness. This allows us to efficiently minimize the average loss per model update, which has been the gold standard in literature to date, using the upper-bound of Leconte et al. as a proxy. Second, we observe that naively optimizing this metric drastically slows down the system by overemphasizing staleness at the expense of throughput. This motivates us to introduce an alternative metric that also accounts for speed, for which we derive a tractable upper-bound that can be minimized numerically. Extensive numerical results show these optimizations enhance accuracy by 10% to 30%.

There are various measures of predictive uncertainty in the literature, but their relationships to each other remain unclear. This paper uses a decomposition of statistical pointwise risk into components associated with different sources of predictive uncertainty: namely, aleatoric uncertainty (inherent data variability) and epistemic uncertainty (model-related uncertainty). Together with Bayesian methods applied as approximations, we build a framework that allows one to generate different predictive uncertainty measures. We validate measures, derived from our framework on image datasets by evaluating its performance in detecting out-of-distribution and misclassified instances using the AUROC metric. The experimental results confirm that the measures derived from our framework are useful for the considered downstream tasks.

Diffusion models have recently shown considerable potential in solving Bayesian inverse problems when used as priors. However, sampling from the resulting denoising posterior distributions remains a challenge as it involves intractable terms. To tackle this issue, state-of-the-art approaches formulate the problem as that of sampling from a surrogate diffusion model targeting the posterior and decompose its scores into two terms: the prior score and an intractable guidance term. While the former is replaced by the pre-trained score of the considered diffusion model, the guidance term has to be estimated. In this paper, we propose a novel approach that utilises a decomposition of the transitions which, in contrast to previous methods, allows a trade-off between the complexity of the intractable guidance term and that of the prior transitions. We validate the proposed approach through extensive experiments on linear and nonlinear inverse problems, including challenging cases with latent diffusion models as priors, and demonstrate its effectiveness in reconstructing electrocardiogram (ECG) from partial measurements for accurate cardiac diagnosis.

We develop a new method for generating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution $\textup{P}_{Y \mid X}$. Existing methods, such as conformalized quantile regression and probabilistic conformal prediction, usually provide only a marginal coverage guarantee. In contrast, our approach extends these frameworks to achieve approximately conditional coverage, which is crucial for many practical applications. Our prediction sets adapt to the behavior of the predictive distribution, making them effective even under high heteroscedasticity. While exact conditional guarantees are infeasible without assumptions on the underlying data distribution, we derive non-asymptotic bounds that depend on the total variation distance of the conditional distribution and its estimate. Using extensive simulations, we show that our method consistently outperforms existing approaches in terms of conditional coverage, leading to more reliable statistical inference in a variety of applications.

We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works suggested to combine the Polyak-Ruppert averaging procedure with the Richardson-Romberg extrapolation to reduce the asymptotic bias of SGD at the expense of a mild increase of the variance. We significantly extend previous results by providing an expansion of the mean-squared error of the resulting estimator with respect to the number of iterations $n$. We show that the root mean-squared error can be decomposed into the sum of two terms: a leading one of order $\mathcal{O}(n^{-1/2})$ with explicit dependence on a minimax-optimal asymptotic covariance matrix, and a second-order term of order $\mathcal{O}(n^{-3/4})$, where the power $3/4$ is best known. We also extend this result to the higher-order moment bounds. Our analysis relies on the properties of the SGD iterates viewed as a time-homogeneous Markov chain. In particular, we establish that this chain is geometrically ergodic with respect to a suitably defined weighted Wasserstein semimetric.

The framework of uncoupled online learning in multiplayer games has made significant progress in recent years. In particular, the development of time-varying games has considerably expanded its modeling capabilities. However, current regret bounds quickly become vacuous when the game undergoes significant variations over time, even when these variations are easy to predict. Intuitively, the ability of players to forecast future payoffs should lead to tighter guarantees, yet existing approaches fail to incorporate this aspect. This work aims to fill this gap by introducing a novel prediction-aware framework for time-varying games, where agents can forecast future payoffs and adapt their strategies accordingly. In this framework, payoffs depend on an underlying state of nature that agents predict in an online manner. To leverage these predictions, we propose the POMWU algorithm, a contextual extension of the optimistic Multiplicative Weight Update algorithm, for which we establish theoretical guarantees on social welfare and convergence to equilibrium. Our results demonstrate that, under bounded prediction errors, the proposed framework achieves performance comparable to the static setting. Finally, we empirically demonstrate the effectiveness of POMWU in a traffic routing experiment.

Denoising diffusion models have driven significant progress in the field of Bayesian inverse problems. Recent approaches use pre-trained diffusion models as priors to solve a wide range of such problems, only leveraging inference-time compute and thereby eliminating the need to retrain task-specific models on the same dataset. To approximate the posterior of a Bayesian inverse problem, a diffusion model samples from a sequence of intermediate posterior distributions, each with an intractable likelihood function. This work proposes a novel mixture approximation of these intermediate distributions. Since direct gradient-based sampling of these mixtures is infeasible due to intractable terms, we propose a practical method based on Gibbs sampling. We validate our approach through extensive experiments on image inverse problems, utilizing both pixel- and latent-space diffusion priors, as well as on source separation with an audio diffusion model. The code is available at https://www.github.com/badr-moufad/mgdm.

This paper proposes a novel analysis for the Scaffold algorithm, a popular method for dealing with data heterogeneity in federated learning. While its convergence in deterministic settings—where local control variates mitigate client drift—is well established, the impact of stochastic gradient updates on its performance is less understood. To address this problem, we first show that its global parameters and control variates define a Markov chain that converges to a stationary distribution in the Wasserstein distance. Leveraging this result, we prove that Scaffold achieves linear speed-up in the number of clients up to higher-order terms in the step size. Nevertheless, our analysis reveals that Scaffold retains a higher-order bias, similar to FedAvg, that does not decrease as the number of clients increases. This highlights opportunities for developing improved stochastic federated learning algorithms.

We introduce Mean Field Trust Region Policy Optimization (MF-TRPO), a novel algorithm designed to compute approximate Nash equilibria for ergodic Mean Field Games (MFGs) in finite state-action spaces. Building on the well-established performance of TRPO in the reinforcement learning (RL) setting, we extend its methodology to the MFG framework, leveraging its stability and robustness in policy optimization. Under standard assumptions in the MFG literature, we provide a rigorous analysis of MF-TRPO, establishing theoretical guarantees on its convergence. Our results cover both the exact formulation of the algorithm and its sample-based counterpart, where we derive high-probability guarantees and finite sample complexity. This work advances MFG optimization by bridging RL techniques with mean-field decision-making, offering a theoretically grounded approach to solving complex multi-agent problems.

We present a new method for generating confidence sets within the split conformal prediction framework. Our method performs a trainable transformation of any given conformity score to improve conditional coverage while ensuring exact marginal coverage. The transformation is based on an estimate of the conditional quantile of conformity scores. The resulting method is particularly beneficial for constructing adaptive confidence sets in multi-output problems where standard conformal quantile regression approaches have limited applicability. We develop a theoretical bound that captures the influence of the accuracy of the quantile estimate on the approximate conditional validity, unlike classical bounds for conformal prediction methods that only offer marginal coverage. We experimentally show that our method is highly adaptive to the local data structure and outperforms existing methods in terms of conditional coverage, improving the reliability of statistical inference in various applications.

In this paper we derive non-asymptotic Berry–Esseen bounds for Polyak–Ruppert averaged iterates of the Linear Stochastic Approximation (LSA) algorithm driven by the Markovian noise. Our analysis yields $O(n^{-1/4})$ convergence rates to the Gaussian limit in the Kolmogorov distance. We further establish the non-asymptotic validity of a multiplier block bootstrap procedure for constructing the confidence intervals, guaranteeing consistent inference under Markovian sampling. Our work provides the first non-asymptotic guarantees on the rate of convergence of bootstrap-based confidence intervals for stochastic approximation with Markov noise. Moreover, we recover the classical rate of order $\mathcal{O}(n^{-1/8})$ up to logarithmic factors for estimating the asymptotic variance of the iterates of the LSA algorithm.

We study asynchronous federated learning mechanisms with nodes having potentially different computational speeds. In such an environment, each node is allowed to work on models with potential delays and contribute to updates to the central server at its own pace. Existing analyses of such algorithms typically depend on intractable quantities such as the maximum node delay and do not consider the underlying queuing dynamics of the system. In this paper, we propose a non-uniform sampling scheme for the central server that allows for lower delays with better complexity, taking into account the closed Jackson network structure of the associated computational graph. Our experiments clearly show a significant improvement of our method over current state-of-the-art asynchronous algorithms on image classification problems.

Conformal prediction (CP) stands out as a robust framework for uncertainty quantification, which is crucial for ensuring the reliability of predictions. However, common CP methods heavily rely on the data exchangeability, a condition often violated in practice. Existing approaches for tackling non-exchangeability lead to methods that are not computable beyond the simplest examples. In this work, we introduce a new efficient approach to CP that produces provably valid confidence sets for fairly general non-exchangeable data distributions. We illustrate the general theory with applications to the challenging setting of federated learning under data heterogeneity between agents. Our method allows constructing provably valid personalized prediction sets for agents in a fully federated way. The effectiveness of the proposed method is demonstrated in a series of experiments on real-world datasets.

In this paper we consider the problem of obtaining sharp bounds for the performance of temporal difference (TD) methods with linear function approximation for policy evaluation in discounted Markov decision processes. We show that a simple algorithm with a universal and instance-independent step size together with Polyak-Ruppert tail averaging is sufficient to obtain near-optimal variance and bias terms. We also provide the respective sample complexity bounds. Our proof technique is based on refined error bounds for linear stochastic approximation together with the novel stability result for the product of random matrices that arise from the TD-type recurrence.

In this paper, we propose a novel centralized Asynchronous Federated Learning (FL) framework, FAVANO for training Deep Neural Networks (DNNs) in resource-constrained environments. Despite its popularity, "classical" federated learning faces the increasingly difficult task of scaling synchronous communication over large wireless networks. Moreover, clients typically have different computing resources and therefore computing speed, which can lead to a significant bias (in favor of "fast" clients) when the updates are asynchronous. Therefore, practical deployment of FL requires to handle users with strongly varying computing speed in communication/resource constrained setting. Experimental results show that the FAVANO algorithm outperforms current methods on standard benchmarks.

Ill-posed linear inverse problems arise frequently in various applications, from computational photography to medical imaging. A recent line of research exploits Bayesian inference with informative priors to handle the ill-posedness of such problems. Amongst such priors, score-based generative models (SGM) have recently been successfully applied to several different inverse problems. In this study, we exploit the particular structure of the prior defined by the SGM to define a sequence of intermediate linear inverse problems. As the noise level decreases, the posteriors of these inverse problems get closer to the target posterior of the original inverse problem. To sample from this sequence of posteriors, we propose the use of Sequential Monte Carlo (SMC) methods. The proposed algorithm, \algo, is shown to be theoretically grounded and we provide numerical simulations showing that it outperforms competing baselines when dealing with ill-posed inverse problems in a Bayesian setting.

Incorporating expert demonstrations has empirically helped to improve the sample efficiency of reinforcement learning (RL). This paper quantifies theoretically to what extent this extra information reduces RL's sample complexity. In particular, we study the demonstration-regularized reinforcement learning framework that leverages the expert demonstrations by $\mathrm{KL}$-regularization for a policy learned by behavior cloning. Our findings reveal that using $N^{\mathrm{E}}$ expert demonstrations enables the identification of an optimal policy at a sample complexity of order $\widetilde{\mathcal{O}}(\mathrm{Poly}(S,A,H)/(\varepsilon^2 N^{\mathrm{E}}))$ in finite and $\widetilde{\mathcal{O}}(\mathrm{Poly}(d,H)/(\varepsilon^2 N^{\mathrm{E}}))$ in linear Markov decision processes, where $\varepsilon$is the target precision, $H$ the horizon, $A$ the number of action, $S$ the number of states in the finite case and $d$ the dimension of the feature space in the linear case. As a by-product, we provide tight convergence guarantees for the behavior cloning procedure under general assumptions on the policy classes. Additionally, we establish that demonstration-regularized methods are provably efficient for reinforcement learning from human feedback (RLHF). In this respect, we provide theoretical evidence showing the benefits of KL-regularization for RLHF in tabular and linear MDPs. Interestingly, we avoid pessimism injection by employing computationally feasible regularization to handle reward estimation uncertainty, thus setting our approach apart from the prior works.

Variational inference (VI) is a popular approach in Bayesian inference, that looks for the best approximation of the posterior distribution within a parametric family, minimizing a loss that is (typically) the reverse Kullback-Leibler (KL) divergence. Despite its empirical success, the theoretical properties of VI have only recently received attention, and is restricted to the Gaussian case. This research paper aims to contribute to the theoretical study of VI in the non-Gaussian case by investigating the setting of Mixture of Gaussians with fixed covariance. In this view, VI over this specific family can be casted as the minimization of a Mollified relative entropy, i.e. the KL between the convolution (with respect to a Gaussian kernel) of an atomic measure supported on Diracs, where the support of the atomic measure correspond to the localization of the Gaussian components, and the target distribution. Hence, solving variational inference is equivalent to optimizing the positions of the Diracs (the particles), which can be done through gradient descent and takes the form of an interacting particle system. We study two sources of error in variational inference in this context. The first is an optimization result that is a descent lemma establishing that the algorithm decreases the objective at each iteration. The second is an approximation error that upper bounds the mollified relative entropy between an optimal finite mixture and the target distribution.

This work considers a repeated principal-agent bandit game, where the principal can only interact with her environment through the agent. The principal and the agent have misaligned objectives and the choice of action is only left to the agent. However, the principal can influence the agent's decisions by offering incentives which add up to his rewards. The principal aims to iteratively learn an incentive policy to maximize her own total utility. This framework extends usual bandit problems and is motivated by several practical applications, such as healthcare or ecological taxation, where traditionally used mechanism design theories often overlook the learning aspect of the problem. We present nearly optimal (with respect to a horizon $T$) learning algorithms for the principal's regret in both multi-armed and linear contextual settings. Finally, we support our theoretical guarantees through numerical experiments.

The use of object detection algorithms for the analysis of satellite imagery is increasing in various fields, including environment and defense, as they enable the automatic detection, recognition and localization of targets. Satellite images often exhibit significant variations, including differences in resolution and noise levels between different satellites. Additional distortions can be caused by factors such as the position of the satellite and the specific area being scanned, resulting in changes in tangential distortion, brightness and saturation. Depending on the severity, these variations can affect the visual clarity of objects in the images and thus impair the effectiveness of object detection algorithms. This study therefore investigates the effects of such fluctuations on the performance of 3 categories of object recognition algorithms - YOLO, FASTER-RCNN and RT-DETR - by applying the principle of adversarial attacks to the inference phase of the algorithms. This experiment makes it possible to uncover the weaknesses of the algorithms facing different degrees of 5 types of satellite images noises. The case study presented is based on the automatic detection of three types of oil and gas infrastructure: compressor, tank and well in the Permian Basin (USA).

Electrocardiogram (ECG) signals provide essential information about the heart's condition and are widely used for diagnosing cardiovascular diseases. The morphology of a single heartbeat over the available leads is a primary biosignal for monitoring cardiac conditions. However, analyzing heartbeat morphology can be challenging due to noise and artifacts, missing leads, and a lack of annotated data. Generative models, such as denoising diffusion generative models (DDMs), have proven successful in generating complex data. We introduce $\texttt{BeatDiff}$, a light-weight DDM tailored for the morphology of multiple leads heartbeats. We then show that many important ECG downstream tasks can be formulated as conditional generation methods in a Bayesian inverse problem framework using $\texttt{BeatDiff}$ as priors. We propose $\texttt{EM-BeatDiff}$, an Expectation-Maximization algorithm, to solve this conditional generation tasks without fine-tuning. We illustrate our results with several tasks, such as removal of ECG noise and artifacts (baseline wander, electrode motion), reconstruction of a 12-lead ECG from a single lead (useful for ECG reconstruction of smartwatch experiments), and unsupervised explainable anomaly detection. Numerical experiments show that the combination of $\texttt{BeatDiff}$ and $\texttt{EM-BeatDiff}$ outperforms SOTA methods for the problems considered in this work.

We introduce a novel class of generative models based on piecewise deterministic Markov processes (PDMPs), a family of non-diffusive stochastic processes consisting of deterministic motion and random jumps at random times. Similarly to diffusions, such Markov processes admit time reversals that turn out to be PDMPs as well. We apply this observation to three PDMPs considered in the literature: the Zig-Zag process, Bouncy Particle Sampler, and Randomised Hamiltonian Monte Carlo. For these three particular instances, we show that the jump rates and kernels of the corresponding time reversals admit explicit expressions depending on some conditional densities of the PDMP under consideration before and after a jump. Based on these results, we propose efficient training procedures to learn these characteristics and consider methods to approximately simulate the reverse process. Finally, we provide bounds in the total variation distance between the data distribution and the resulting distribution of our model in the case where the base distribution is the standard $d$-dimensional Gaussian distribution. Promising numerical simulations support further investigations into this class of models.

Collaborative learning offers a promising avenue for leveraging decentralized data. However, collaboration in groups of strategic learners is not a given. In this work, we consider strategic agents who wish to train a model together but have sampling distributions of different quality. The collaboration is organized by a benevolent aggregator who gathers samples so as to maximize total welfare, but is unaware of data quality. This setting allows us to shed light on the deleterious effect of adverse selection in collaborative learning. More precisely, we demonstrate that when data quality indices are private, the coalition may undergo a phenomenon known as unravelling, wherein it shrinks up to the point that it becomes empty or solely comprised of the worst agent. We show how this issue can be addressed without making use of external transfers, by proposing a novel method inspired by probabilistic verification. This approach makes the grand coalition a Nash equilibrium with high probability despite information asymmetry, thereby breaking unravelling.

Recent advancements in solving Bayesian inverse problems have spotlighted denoising diffusion models (DDMs) as effective priors. Although these have great potential, DDM priors yield complex posterior distributions that are challenging to sample from. Existing approaches to posterior sampling in this context address this problem either by retraining model-specific components, leading to stiff and cumbersome methods, or by introducing approximations with uncontrolled errors that affect the accuracy of the produced samples. We present an innovative framework, divide-and-conquer posterior sampling, which leverages the inherent structure of DDMs to construct a sequence of intermediate posteriors that guide the produced samples to the target posterior. Our method significantly reduces the approximation error associated with current techniques without the need for retraining. We demonstrate the versatility and effectiveness of our approach for a wide range of Bayesian inverse problems. The code is available at \url{https://github.com/Badr-MOUFAD/dcps}

In this paper, we analyze the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local training with agent heterogeneity. We show that the communication complexity of FedLSA scales polynomially with the inverse of the desired accuracy ϵ. To overcome this, we propose SCAFFLSA a new variant of FedLSA that uses control variates to correct for client drift, and establish its sample and communication complexities. We show that for statistically heterogeneous agents, its communication complexity scales logarithmically with the desired accuracy, similar to Scaffnew. An important finding is that, compared to the existing results for Scaffnew, the sample complexity scales with the inverse of the number of agents, a property referred to as linear speed-up. Achieving this linear speed-up requires completely new theoretical arguments. We apply the proposed method to federated temporal difference learning with linear function approximation and analyze the corresponding complexity improvements.

In this paper, we obtain the Berry–Esseen bound for multivariate normal approximation for the Polyak-Ruppert averaged iterates of the linear stochastic approximation (LSA) algorithm with decreasing step size. Moreover, we prove the non-asymptotic validity of the confidence intervals for parameter estimation with LSA based on multiplier bootstrap. This procedure updates the LSA estimate together with a set of randomly perturbed LSA estimates upon the arrival of subsequent observations. We illustrate our findings in the setting of temporal difference learning with linear function approximation.

In Economics, the concept of externality refers to any indirect effect resulting from an interaction between players and affecting a third party without compensation. Most of the models within which externality has been studied assume that agents have perfect knowledge of their environment and preferences. This is a major hindrance to the practical implementation of many proposed solutions. To adress this issue, we consider a two-players bandit game setting where the actions of one of the player affect the other one. Building upon this setup, we extend the Coase theorem [Coase, 2013], which suggests that the optimal approach for maximizing the social welfare in the presence of externality is to establish property rights, i.e., enabling transfers and bargaining between the players. Nonetheless, this fundamental result relies on the assumption that bargainers possess perfect knowledge of the underlying game. We first demonstrate that in the absence of property rights in the considered online scenario, the social welfare breaks down. We then provide a policy for the players, which allows them to learn a bargaining strategy which maximizes the total welfare, recovering the Coase theorem under uncertainty.

In this work we undertake a thorough study of the non-asymptotic properties of the vanilla generative adversarial networks (GANs). We prove an oracle inequality for the Jensen-Shannon (JS) divergence between the underlying density $\mathsf{p}^*$ and the GAN estimate with a significantly better statistical error term compared to the previously known results. The advantage of our bound becomes clear in application to nonparametric density estimation. We show that the JS-divergence between the GAN estimate and $\mathsf{p}^*$ decays as fast as $(\log{n}/n)^{2\beta/(2\beta + d)}$, where $n$ is the sample size and $\beta$ determines the smoothness of $\mathsf{p}^*$. This rate of convergence coincides (up to logarithmic factors) with minimax optimal for the considered class of densities.

In this paper, we develop a new algorithm, Annealed Skewed SGD - AskewSGD - for training deep neural networks (DNNs) with quantized weights. First, we formulate the training of quantized neural networks (QNNs) as a smoothed sequence of interval-constrained optimization problems. Then, we propose a new first-order stochastic method, AskewSGD, to solve each constrained optimization subproblem. Unlike algorithms with active sets and feasible directions, AskewSGD avoids projections or optimization under the entire feasible set and allows iterates that are infeasible. The numerical complexity of AskewSGD is comparable to existing approaches for training QNNs, such as the straight-through gradient estimator used in BinaryConnect, or other state of the art methods (ProxQuant, LUQ). We establish convergence guarantees for AskewSGD (under general assumptions for the objective function). Experimental results show that the AskewSGD algorithm performs better than or on par with state of the art methods in classical benchmarks.

This paper focuses on Bayesian inference in a federated learning context (FL). While several distributed MCMC algorithms have been proposed, few consider the specific limitations of FL such as communication bottlenecks and statistical heterogeneity. Recently, Federated Averaging Langevin Dynamics (FALD) was introduced, which extends the Federated Averaging algorithm to Bayesian inference. We obtain a novel tight non-asymptotic upper bound on the Wasserstein distance to the global posterior for FALD. This bound highlights the effects of statistical heterogeneity, which causes a drift in the local updates that negatively impacts convergence. We propose a new algorithm VR-FALD* that uses control variates to correct the client drift. We establish non-asymptotic bounds showing that VR-FALD* is not affected by statistical heterogeneity. Finally, we illustrate our results on several FL benchmarks for Bayesian inference.

We provide a rigorous analysis of training by variational inference (VI) of Bayesian neural networks in the two-layer and infinite-width case. We consider a regression problem with a regularized evidence lower bound (ELBO) which is decomposed into the expected log-likelihood of the data and the Kullback-Leibler (KL) divergence between the a priori distribution and the variational posterior. With an appropriate weighting of the KL, we prove a law of large numbers for three different training schemes: (i) the idealized case with exact estimation of a multiple Gaussian integral from the reparametrization trick, (ii) a minibatch scheme using Monte Carlo sampling, commonly known as Bayes by Backprop, and (iii) a new and computationally cheaper algorithm which we introduce as Minimal VI. An important result is that all methods converge to the same mean-field limit. Finally, we illustrate our results numerically and discuss the need for the derivation of a central limit theorem.

We consider the problem of minimizing a non-convex function over a smooth manifold M. We propose a novel algorithm, the Orthogonal Directions Constrained Gradient Method (ODCGM), which only requires computing a projection onto a vector space. ODCGM is infeasible but the iterates are constantly pulled towards the manifold, ensuring the convergence of ODCGM towards M. ODCGM is much simpler to implement than the classical methods which require the computation of a retraction. Moreover, we show that ODCGM exhibits the near-optimal oracle complexities O(1/ε^{-2}) and O(1/ε^{-4}) in the deterministic and stochastic cases, respectively. Furthermore, we establish that, under an appropriate choice of the projection metric, our method recovers the landing algorithm of Ablin and Peyré (2022), a recently introduced algorithm for optimization over the Stiefel manifold. As a result, we significantly extend the analysis of Ablin and Peyré (2022), establishingnear-optimal rates both in deterministic and stochastic frameworks. Finally, we perform numerical experiments, which shows the efficiency of ODCGM in a high-dimensional setting.

Non-linear state-space models, also known as general hidden Markov models (HMM), are ubiquitous in statistical machine learning, being the most classical generative models for serial data and sequences. Learning in HMM, either via Maximum Likelihood Estimation (MLE) or Markov Score Climbing (MSC) requires the estimation of the- smoothing expectation of some additive functionals. Controlling the bias and the variance of this estimation is crucial to establish the convergence of learning algorithms. Our first contribution is to design a novel additive smoothing algorithm, the Parisian particle Gibbs (PPG) sampler, which can be viewed as a PaRIS (Olsson, Westerborn 2017) 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. We then establish, in the learning context, and 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.

Transport maps can ease the sampling of distributions with non-trivial geometries by transforming them into distributions that are easier to handle. The potential of this approach has risen with the development of Normalizing Flows (NF) which are maps parameterized with deep neural networks trained to push a reference distribution towards a target. NF-enhanced samplers recently proposed blend (Markov chain) Monte Carlo methods with either (i) proposal draws from the flow or (ii) a flow-based reparametrization. In both cases, the quality of the learned transport conditions performance. The present work clarifies for the first time the relative strengths and weaknesses of these two approaches. Our study concludes that multimodal targets can be reliably handled with flow-based proposals up to moderately high dimensions. In contrast, methods relying on reparametrization struggle with multimodality but are more robust otherwise in high-dimensional settings and under poor training. To further illustrate the influence of target-proposal adequacy, we also derive a new quantitative bound for the mixing time of the Independent Metropolis-Hastings sampler.

In reinforcement learning, the credit assignment problem is to distinguish luck from skill, that is, separate the inherent randomness in the environment from the controllable effects of the agent’s actions. This paper proposes two novel algorithms, Quantile Credit Assignment (QCA) and Hindsight QCA (HQCA), which incorporate distributional value estimation to perform credit assignment. QCA uses a network that predicts the quantiles of the return distribution, whereas HQCA additionally incorporates information about the future. Both QCA and HQCA have the appealing interpretation of leveraging an estimate of the quantile level of the return (interpreted as the level of "luck") in order to derive a "luck-dependent" baseline for policy gradient methods. We show theoretically that this approach gives an unbiased policy gradient estimate that can yield significant variance reductions over a standard value estimate baseline. QCA and HQCA significantly outperform prior state-of-the-art methods on a range of extremely difficult credit assignment problems.

Federated Learning (FL) is a machine learning framework where many clients collaboratively train models while keeping the training data decentralized. Despite recent advances in FL, the uncertainty quantification topic (UQ) remains partially addressed. Among UQ methods, conformal prediction (CP) approaches provides distribution-free guarantees under minimal assumptions. We develop a new federated conformal prediction method based on quantile regression and take into account privacy constraints. This method takes advantage of importance weighting to effectively address the label shift between agents and provides theoretical guarantees for both valid coverage of the prediction sets and differential privacy. Extensive experimental studies demonstrate that this method outperforms current competitors.

We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. In this work, we study the maximum entropy exploration problem of two different types. The first type is visitation entropy maximization previously considered by Hazan et al. (2019) in the discounted setting. For this type of exploration, we propose a game-theoretic algorithm that has $\widetilde{\mathcal{O}}(H^3S^2A/\varepsilon^2)$ sample complexity thus improving the $\varepsilon$-dependence upon existing results, where $S$ is a number of states, $A$ is a number of actions, $H$ is an episode length, and $\varepsilon$ is a desired accuracy. The second type of entropy we study is the trajectory entropy. This objective function is closely related to the entropy-regularized MDPs, and we propose a simple algorithm that has a sample complexity of order $\widetilde{\mathcal{O}}(\mathrm{poly}(S,A,H)/\varepsilon)$. Interestingly, it is the first theoretical result in RL literature that establishes the potential statistical advantage of regularized MDPs for exploration. Finally, we apply developed regularization techniques to reduce sample complexity of visitation entropy maximization to $\widetilde{\mathcal{O}}(H^2SA/\varepsilon^2)$, yielding a statistical separation between maximum entropy exploration and reward-free exploration.

This paper delves into stochastic optimization problems that involve Markovian noise. We present a unified approach for the theoretical analysis of first-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time of the underlying noise sequence, we use the randomized batching scheme, which is based on the multilevel Monte Carlo method. Moreover, our technique allows us to eliminate the limiting assumptions of previous research on Markov noise, such as the need for a bounded domain and uniformly bounded stochastic gradients. Our extension to variational inequalities under Markovian noise is original. Additionally, we provide lower bounds that match the oracle complexity of our method in the case of strongly convex optimization problems.

In this paper, we introduce Randomized Q-learning (RandQL), a novel randomized model-free algorithm for regret minimization in episodic Markov Decision Processes (MDPs). To the best of our knowledge, RandQL is the first tractable model-free posterior sampling-based algorithm. We analyze the performance of RandQL in both tabular and non-tabular metric space settings. In tabular MDPs, RandQL achieves a regret bound of order $\widetilde{\mathcal{O}}(\sqrt{H^{5}SAT})$, where $H$ is the planning horizon, $S$ is the number of states, $A$ is the number of actions, and $T$ is the number of episodes. For a metric state-action space, RandQL enjoys a regret bound of order $\widetilde{\mathcal{O}}(H^{5/2} T^{(d_z+1)/(d_z+2)})$, where $d_z$ denotes the zooming dimension. Notably, RandQL achieves optimistic exploration without using bonuses, relying instead on a novel idea of learning rate randomization. Our empirical study shows that RandQL outperforms existing approaches on baseline exploration environments.

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 QLSD$^\star$ and QLSD$^{++}$. We give both non-asymptotic and asymptotic convergence guarantees for the proposed algorithms. We illustrate their performances using various Bayesian Federated Learning benchmarks.

Many constrained, nonconvex and nonsmooth optimization problems can be tackled using the majorization-minimization (MM) method which alternates between constructing a surrogate func- tion which upper bounds the objective function, and then minimizing this surrogate. For problems which minimize a finite sum of functions, a stochastic version of the MM method selects a batch of functions at random at each iteration and optimizes the accumulated surrogate. However, in many cases of interest such as variational inference for latent variable models, the surrogate functions are expressed as an expectation. In this contribution, we propose a doubly stochastic MM method based on Monte Carlo approximation of these stochastic surrogates. We establish asymptotic and non-asymptotic convergence of our scheme in a constrained, nonconvex, nonsmooth optimization setting. We apply our new framework for inference of logistic regression model with missing data and for variational inference of Bayesian variants of LeNet-5 and Resnet-18 on benchmark datasets.

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.

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{\mathcal{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 $\Omega(\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 of 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).

Importance Sampling (IS) is a method for approximating expectations with respect to a target distribution using independent samples from a proposal distribution and the associated to importance weights. In many cases, the target distribution is known up to a normalization constant and self-normalized IS (SNIS) is then 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 SNIS and which significantly reduces bias. This method is a wrapper, in the sense that it uses the same proposal samples and importance weights but makes a clever use of iterated sampling-importance-resampling (i-SIR) to form a bias-reduced version of the estimator. We derive the proposed algorithm with rigorous theoretical results, including novel bias, variance, and high-probability bounds. We illustrate our findings with numerical examples.

Personalised federated learning (FL) aims at collaboratively learning a machine learning model tailored for each client. Albeit promising advances have been made in this direction, most of the existing approaches do not allow for uncertainty quantification which is crucial in many applications. In addition, personalisation in the cross-silo and cross-device setting still involves important issues, especially for new clients or those having a small number of observations. This paper aims at filling these gaps. To this end, we propose a novel methodology coined FedPop by recasting personalised FL into the population modeling paradigm where clients’ models involve fixed common population parameters and random effects, aiming at explaining data heterogeneity. To derive convergence guarantees for our scheme, we introduce a new class of federated stochastic optimisation algorithms that relies on Markov chain Monte Carlo methods. Compared to existing personalised FL methods, the proposed methodology has important benefits: it is robust to client drift, practical for inference on new clients, and above all, enables uncertainty quantification under mild computational and memory overheads. We provide nonasymptotic convergence guarantees for the proposed algorithms and illustrate their performances on various personalised federated learning tasks.

Recent works leveraging learning to enhance sampling have shown promising results, in particular by designing effective non-local moves and global proposals. However, learning accuracy is inevitably limited in regions where little data is available such as in the tails of distributions as well as in high-dimensional problems. In the present paper we study an Explore-Exploit Markov chain Monte Carlo strategy ($\operatorname{Ex^2MCMC}$) that combines local and global samplers showing that it enjoys the advantages of both approaches. We prove $V$-uniform geometric ergodicity of $\operatorname{Ex^2MCMC}$ without requiring a uniform adaptation of the global sampler to the target distribution. We also compute explicit bounds on the mixing rate of the Explore-Exploit strategy under realistic conditions. Moreover, we propose an adaptive version of the strategy ($\operatorname{FlEx^2MCMC}$) where a normalizing flow is trained while sampling to serve as a proposal for global moves. We illustrate the efficiency of $\operatorname{Ex^2MCMC}$ and its adaptive version on classical sampling benchmarks as well as in sampling high-dimensional distributions defined by Generative Adversarial Networks seen as Energy Based Models.

We consider reinforcement learning in an environment modeled by an episodic, tabular, step-dependent Markov decision process of horizon $H$ with $S$ states, and $A$ actions. The performance of an agent is measured by the regret after interacting with the environment for $T$ episodes. We propose an optimistic posterior sampling algorithm for reinforcement learning (OPSRL), a simple variant of posterior sampling that only needs a number of posterior samples logarithmic in $H$, $S$, $A$, and $T$ per state-action pair. For OPSRL we guarantee a high-probability regret bound of order at most $O(\sqrt{H^3SAT})$ ignoring $\text{poly}\log(HSAT)$ terms. The key novel technical ingredient is a new sharp anti-concentration inequality for linear forms of a Dirichlet random vector which may be of independent interest. Specifically, we extend the normal approximation-based lower bound for Beta distributions by Alfers and Dinges (1984) to Dirichlet distributions. Our bound matches the lower bound of order $\Omega(\sqrt{H^3SAT})$, thereby answering the open problems raised by Agrawal and Jia (2017) for the episodic setting.

This paper studies fixed step-size stochastic approximation (SA) schemes, including stochastic gradient schemes, in a Riemannian framework. It is motivated by several applications, where geodesics can be computed explicitly, and their use accelerates crude Euclidean methods. A fixed step-size scheme defines a family of time-homogeneous Markov chains, parametrized by the step-size. Here, using this formulation, non-asymptotic performance bounds are derived, under Lyapunov conditions. Then, for any step-size, the corresponding Markov chain is proved to admit a unique stationary distribution, and to be geometrically ergodic. This result gives rise to a family of stationary distributions indexed by the step-size, which is further shown to converge to a Dirac measure, concentrated at the solution of the problem at hand, as the step-size goes to $0$. Finally, the asymptotic rate of this convergence is established, through an asymptotic expansion of the bias, and a central limit theorem.

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.

The Expectation Maximization (EM) algorithm is a key reference for inference in latent variable models; unfortunately, its computational cost is prohibitive in the large scale learning setting. In this paper, we propose an extension of the Stochastic Path-Integrated Differential EstimatoR EM (SPIDER-EM) and derive complexity bounds for this novel algorithm, designed to solve smooth nonconvex finite-sum optimization problems. We show that it reaches the same state of the art complexity bounds as SPIDER-EM; and provide conditions for a linear rate of convergence. Numerical results support our findings.

Credit assignment in reinforcement learning is the problem of measuring an action’s influence on future rewards. In particular, this requires separating skill from luck, i.e. disentangling the effect of an action on rewards from that of external factors and subsequent actions. To achieve this, we adapt the notion of counterfactuals from causality theory to a model-free RL setup. The key idea is to condition value functions on future events, by learning to extract relevant information from a trajectory. We formulate a family of policy gradient algorithms that use these future-conditional value functions as baselines or critics, and show that they are provably low variance. To avoid the potential bias from conditioning on future information, we constrain the hindsight information to not contain information about the agent’s actions. We demonstrate the efficacy and validity of our algorithm on a number of illustrative and challenging problems.

Performing reliable Bayesian inference on a big data scale is becoming a keystone in the modern era of machine learning. A workhorse class of methods to achieve this task are Markov chain Monte Carlo (MCMC) algorithms and their design to handle distributed datasets has been the subject of many works. However, existing methods are not completely either reliable or computationally efficient. In this paper, we propose to fill this gap in the case where the dataset is partitioned and stored on computing nodes within a cluster under a master/slaves architecture. We derive a user-friendly centralised distributed MCMC algorithm with provable scaling in high-dimensional settings. We illustrate the relevance of the proposed methodology on both synthetic and real data experiments.

Variational auto-encoders (VAE) are popular deep latent variable models which are trained by maximizing an Evidence Lower Bound (ELBO). To obtain tighter ELBO and hence better variational approximations, it has been proposed to use importance sampling to get a lower variance estimate of the evidence. However, importance sampling is known to perform poorly in high dimensions. While it has been suggested many times in the literature to use more sophisticated algorithms such as Annealed Importance Sampling (AIS) and its Sequential Importance Sampling (SIS) extensions, the potential benefits brought by these advanced techniques have never been realized for VAE: the AIS estimate cannot be easily differentiated, while SIS requires the specification of carefully chosen backward Markov kernels. In this paper, we address both issues and demonstrate the performance of the resulting Monte Carlo VAEs on a variety of applications.

The Expectation Maximization (EM) algorithm is the default algorithm for inference in latent variable models. As in any other field of machine learning, applications of latent variable models to very large datasets make the use of advanced parallel and distributed architecture mandatory. This paper introduces FedEM, which is the first extension of the EM algorithm to the federated learning context. FedEM is a new communication efficient method, which handles partial participation of local devices, and is robust to heterogeneous distribution of the datasets. To alleviate the communication bottleneck, FedEM compresses appropriately defined complete data sufficient statistics. We also develop and analyze an extension of FedEM to further incorporate a variance reduction scheme. In all cases, we derive finite-time complexity bounds for smooth non-convex problems. Numerical results are presented to support our theoretical findings, as well as an application to federated missing values imputation for biodiversity monitoring.

This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. This family of methods arises in many machine learning tasks and is used to obtain approximate solutions of a linear system $\bar{A}\theta = \bar{b}$ for which $\bar{A}$ and $\bar{b}$ can only be accessed through random estimates $\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$. Our analysis is based on new results regarding moments and high probability bounds for products of matrices which are shown to be tight. We derive high probability bounds on the performance of LSA under weaker conditions on the sequence $\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$ than previous works. However, in contrast, we establish polynomial concentration bounds with order depending on the stepsize. We show that our conclusions cannot be improved without additional assumptions on the sequence of random matrices $\{{\bf A}_n: n \in \mathbb{N}^*\}$, and in particular that no Gaussian or exponential high probability bounds can hold. Finally, we pay a particular attention to establishing bounds with sharp order with respect to the number of iterations and the stepsize and whose leading terms contain the covariance matrices appearing in the central limit theorems.

Sampling from a complex distribution $\pi$ and approximating its intractable normalizing constant $\mathrm{Z}$ are challenging problems. In this paper, a novel family of importance samplers (IS) and Markov chain Monte Carlo (MCMC) samplers is derived. Given an invertible map $\mathrm{T}$, these schemes combine (with weights) elements from the forward and backward Orbits through points sampled from a proposal distribution $\rho$. The map $\mathrm{T}$ does not leave the target $\pi$ invariant, hence the name NEO, standing for Non-Equilibrium Orbits. NEO-IS provides unbiased estimators of the normalizing constant and self-normalized IS estimators of expectations under $\pi$ while NEO-MCMC combines multiple NEO-IS estimates of the normalizing constant and an iterated sampling-importance resampling mechanism to sample from $\pi$. For $\mathrm{T}$ chosen as a discrete-time integrator of a conformal Hamiltonian system, NEO-IS achieves state-of-the art performance on difficult benchmarks and NEO-MCMC is able to explore highly multimodal targets. Additionally, we provide detailed theoretical results for both methods. In particular, we show that NEO-MCMC is uniformly geometrically ergodic and establish explicit mixing time estimates under mild conditions.

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 $\Omega(1/k)$. A simple numerical experiment is presented to support our theory.

Can the parameters of a hidden Markov model (HMM) be estimated from a single sweep through the observations – and additionally, without being trapped at a local optimum in the likelihood surface? That is the premise of recent method of moments algorithms devised for HMMs. In these, correlations between consecutive pair- or triplet-wise observations are empirically estimated and used to compute estimates of the HMM parameters. Albeit computationally very attractive, the main drawback is that by restricting to only low-order correlations in the data, information is being neglected which results in a loss of accuracy (compared to standard maximum likelihood schemes). In this paper, we propose extending these methods (both pair- and triplet-based) by also including non-consecutive correlations in a way which does not significantly increase the computational cost (which scales linearly with the number of additional lags included). We prove strong consistency of the new methods, and demonstrate an improved performance in numerical experiments on both synthetic and real-world financial time-series datasets.

The Expectation Maximization (EM) algorithm is of key importance for inference in latent variable models including mixture of regressors and experts, missing observations. This paper introduces a novel EM algorithm, called {\tt SPIDER-EM}, for inference from a training set of size $n$, $n \gg 1$. At the core of our algorithm is an estimator of the full conditional expectation in the {\sf E}-step, adapted from the stochastic path integral differential estimator ({\tt SPIDER}) technique. We derive finite-time complexity bounds for smooth non-convex likelihood: we show that for convergence to an $\epsilon$-approximate stationary point, the complexity scales as $K_{Opt} (n,\epsilon )={\cal O}(\epsilon^{-1})$ and $K_{CE}( n,\epsilon ) = n+ \sqrt{n} {\cal O}( \epsilon^{-1} )$, where $K_{Opt}( n,\epsilon )$ and $K_{CE}(n, \epsilon )$ are respectively the number of {\sf M}-steps and the number of per-sample conditional expectations evaluations. This improves over the state-of-the-art algorithms. Numerical results support our findings.

Stochastic approximation (SA) is a key method used in statistical learning. Recently, its non-asymptotic convergence analysis has been considered in many papers. However, most of the prior analyses are made under restrictive assumptions such as unbiased gradient estimates and convex objective function, which significantly limit their applications to sophisticated tasks such as online and reinforcement learning. These restrictions are all essentially relaxed in this work. In particular, we analyze a general SA scheme to minimize a non-convex, smooth objective function. We consider update procedure whose drift term depends on a state-dependent Markov chain and the mean field is not necessarily of gradient type, covering approximate second-order method and allowing asymptotic bias for the one-step updates. We illustrate these settings with the online EM algorithm and the policy-gradient method for average reward maximization in reinforcement learning.

The EM algorithm is one of the most popular algorithm for inference in latent data models. The original formulation of the EM algorithm does not scale to large data set, because the whole data set is required at each iteration of the algorithm. To alleviate this problem, Neal and Hinton [1998] have proposed an incremental version of the EM (iEM) in which at each iteration the conditional expectation of the latent data (E-step) is updated only for a mini-batch of observations. Another approach has been proposed by Cappe and Moulines [2009] in which the E-step is replaced by a stochastic approximation step, closely related to stochastic gradient. In this paper, we analyze incremental and stochastic version of the EM algorithm as well as the variance reduced-version of [Chen et al., 2018] in a common unifying framework. We also introduce a new version incremental version, inspired by the SAGA algorithm by Defazio et al. [2014]. We establish non-asymptotic convergence bounds for global convergence. Numerical applications are presented in this article to illustrate our findings.

Stochastic Gradient Langevin Dynamics (SGLD) has emerged as a key MCMC algorithm for Bayesian learning from large scale datasets. While SGLD with decreasing step sizes converges weakly to the posterior distribution, the algorithm is often used with a constant step size in practice and has demonstrated spectacular successes in machine learning tasks. The current practice is to set the step size inversely proportional to N where N is the number of training samples. As N becomes large, we show that the SGLD algorithm has an invariant probability measure which significantly departs from the target posterior and behaves like as Stochastic Gradient Descent (SGD). This difference is inherently due to the high variance of the stochastic gradients. Several strategies have been suggested to reduce this effect; among them, SGLD Fixed Point (SGLDFP) uses carefully designed control variates to reduce the variance of the stochastic gradients. We show that SGLDFP gives approximate samples from the posterior distribution, with an accuracy comparable to the Langevin Monte Carlo (LMC) algorithm for a computational cost sublinear in the number of data points. We provide a detailed analysis of the Wasserstein distances between LMC, SGLD, SGLDFP and SGD and explicit expressions of the means and covariance matrices of their invariant distributions. Our findings are supported by limited numerical experiments.

Many applications of machine learning involve the analysis of large data frames -- matrices collecting heterogeneous measurements (binary, numerical, counts, etc.) across samples -- with missing values. Low-rank models, as studied by Udell et al. (2016), are popular in this framework for tasks such as visualization, clustering and missing value imputation. Yet, available methods with statistical guarantees and efficient optimization do not allow explicit modeling of main additive effects such as row and column, or covariate effects. In this paper, we introduce a low-rank interaction and sparse additive effects (LORIS) model which combines matrix regression on a dictionary and low-rank design, to estimate main effects and interactions simultaneously. We provide statistical guarantees in the form of upper bounds on the estimation error of both components. Then, we introduce a mixed coordinate gradient descent (MCGD) method which provably converges sub-linearly to an optimal solution and is computationally efficient for large scale data sets. We show on simulated and survey data that the method has a clear advantage over current practices.

Modern imaging methods rely strongly on Bayesian inference techniques to solve challenging imaging problems. Currently, the predominant Bayesian computation approach is convex optimization, 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 nonsmooth, a class of models that is central in imaging sciences. The methodology is based on a regularized unadjusted Langevin algorithm that exploits tools from convex analysis, namely, Moreau--Yoshida envelopes and proximal operators, to construct Markov chains with favorable 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 optimization algorithms. We provide a detailed theoretical analysis of the proposed methodology, including asymptotic and nonasymptotic 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.

This paper presents a detailed theoretical analysis of the Langevin Monte Carlo sampling algorithm recently introduced in Durmus et al. (Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreau, 2016) when applied to log-concave probability distributions that are restricted to a convex body $K$. This method relies on a regularisation procedure involving the Moreau-Yosida envelope of the indicator function associated with $K$. Explicit convergence bounds in total variation norm and in Wasserstein distance of order $1$ are established. In particular, we show that the complexity of this algorithm given a first order oracle is polynomial in the dimension of the state space. Finally, some numerical experiments are presented to compare our method with competing MCMC approaches from the literature.

Stochastic Gradient Markov Chain Monte Carlo (SG-MCMC) methods have become popular in modern data analysis problems due to their computational efficiency. Even though they have proved useful for many statistical models, the application of SG-MCMC to non-negative matrix factorization (NMF) models has not yet been extensively explored. In this study, we develop two parallel SG-MCMC algorithms for a broad range of NMF models. We exploit the conditional independence structure of the NMF models and utilize a stratified sub-sampling approach for enabling parallelization. We illustrate the proposed algorithms on an image restoration task and report encouraging results.

This paper proposes a fast and privacy preserving distributed algorithm for handling low-rank regression problems with nuclear norm constraint. Traditional projected gradient algorithms have high computation costs due to their projection steps when they are used to solve these problems. Our gossip-based algorithm, called the fast DeFW algorithm, overcomes this issue since it is projection-free. In particular, the algorithm incorporates a carefully designed decentralized power method step to reduce the complexity by distributed computation over network. Meanwhile, privacy is preserved as the agents do not exchange the private data, but only a random projection of them. We show that the fast DeFW algorithm converges for both convex and non-convex losses. As an application example, we consider the low-rank matrix completion problem and provide numerical results to support our findings.

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.

We propose distributed algorithms for high-dimensional sparse optimization. In many applications, the parameter is sparse but high-dimensional. This is pathological for existing distributed algorithms as the latter require an information exchange stage involving transmission of the full parameter, which may not be sparse during the intermediate steps of optimization. The novelty of this work is to develop communication efficient algorithms using the stochastic Frank-Wolfe (sFW) algorithm, where the gradient computation is inexact but controllable. For star network topology, we propose an algorithm with low communication cost and establishes its convergence. The proposed algorithm is then extended to perform decentralized optimization on general network topology. Numerical experiments are conducted to verify our findings.

We analyze the Lp-convergence of a previously proposed Girsanov theorem based particle filter for discretely observed stochastic differential equation (SDE) models. We prove the convergence of the algorithm with the number of particles tending to infinity by requiring a moment condition and a step-wise initial condition boundedness for the stochastic exponential process giving the likelihood ratio of the SDEs. The practical implications of the condition are illustrated with an Ornstein-Uhlenbeck model and with a non-linear Benes model.

Stochastic Gradient Markov Chain Monte Carlo (SG-MCMC) algorithms have become increasingly popular for Bayesian inference in large-scale applications. Even though these methods have proved useful in several scenarios, their performance is often limited by their bias. In this study, we propose a novel sampling algorithm that aims to reduce the bias of SG-MCMC while keeping the variance at a reasonable level. Our approach is based on a numerical sequence acceleration method, namely the Richardson-Romberg extrapolation, which simply boils down to running almost the same SG-MCMC algorithm twice in parallel with different step sizes. We illustrate our framework on the popular Stochastic Gradient Langevin Dynamics (SGLD) algorithm and propose a novel SG-MCMC algorithm referred to as Stochastic Gradient Richardson-Romberg Langevin Dynamics (SGRRLD). We provide formal theoretical analysis and show that SGRRLD is asymptotically consistent, satisfies a central limit theorem, and its non-asymptotic bias and the mean squared-error can be bounded. Our results show that SGRRLD attains higher rates of convergence than SGLD in both finite-time and asymptotically, and it achieves the theoretical accuracy of the methods that are based on higher-order integrators. We support our findings using both synthetic and real data experiments.

Coverage optimization is an important process for the operator, as it is a crucial prerequisite toward 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 user's equipments. In the 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 is extended to take into account that the location uncertainty proves to enhance the prediction accuracy while keeping a reasonable computational complexity.

These invited talks discuss the following: The sexy job in the next ten years will be statisticians; Fine Grained Visual Categorisation; Big Data Analytics vs Business Intelligence; The Rise of Open Big data & Analytics platform; Data Science for Social Good: How the Data Science Bowl Advanced the Field of Deep Learning and Ocean Science.

Coverage optimization is a crucial task for a radio network operator. An accurate coverage estimation is a key prerequisite for efficient coverage analysis and optimization. In this paper, we propose a coverage prediction method based on statistical modeling of the wireless environment. We build a Radio Environment Map by interpolating geo-located measurements using the Kriging spatial prediction technique. Moreover, as we perform Kriging on massive observation datasets obtained through field measurement campaigns, we use Fixed Rank Kriging, to reduce the complexity of the Kriging algorithm. We apply the FRK algorithm for Long Term Evolution (LTE) network coverage prediction. We consider as observation data, the coverage measurements obtained by operational drive tests in a rural area. Numerical results show that by using the FRK algorithm, we fulfill a good trade-off between computational complexity and prediction accuracy.

During the last decade a lot of effort has been spent on cellular network optimization to improve network capacity and end-user Quality of Service (QoS). Coverage analysis remains as one of the essential topics on which mobile operators still need innovation in terms of performance and cost. Manual coverage analysis is an inefficient and costly task. Radio Environment Maps (REMs) is an efficient coverage analysis solution for present-day cellular networks. REM concept consists of spatially interpolating geo-located measurements to build the whole coverage map using a spatial interpolation technique originating from geo-statistics. Kriging is such a powerful technique which results in high performance in terms of prediction quality. However, this method is costly in terms of computational complexity especially for large datasets: computational complexity of Kriging is O(n3) where n is the number of measurements. This paper proposes the application of a variant of Kriging, Fixed Rank Kriging (FRK), to coverage analysis in order to reduce the computational complexity of the spatial interpolation while keeping an acceptable prediction error.

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/\sqrt{n})$. 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 showing that they often outperform existing approaches.

Optimization of radio access networks is a challenge for cellular operators. With the deployment of new radio access technologies and advanced features, network optimization needs to be automated for performance improvement and OPerational EXpenditures (OPEX) reduction. In this paper, we propose a method for centralized self-optimization of pilot powers to perform load balancing between base stations. The proposed method uses a stochastic surrogate function to model the functional relationships between noisy Key Performance Indicators (KPIs) and network parameters, and subsequently performs optimization using a pattern search algorithm in a recursive manner. The method is applied to solve a high dimensional optimization problem of pilot power based load balancing in an LTE network. Results obtained using a flow level analytical network simulator show the advantages of the proposed recursive modeling and optimization approach as a promising solution in terms of robustness to noisy data and fast convergence to the optimum point for a high dimensional network optimization.

A major challenge to the successful operation and maintainability of LTE-A network is to address competing objectives such as improved capacity, reduced operational costs and complexity. In this paper we use a surrogate function to model the functional relationships between noisy Key Performance Indicators (KPIs) and Radio Resource Management (RRM) parameters and subsequently use a pattern search algorithm for optimization under constraints. The proposed methodology is applied to solve a self-optimization problem for eICIC in an LTE-A HetNet deployment. Results obtained using a system level simulator show promising results for faster convergence towards optimal network configuration.

Deployment of Long Term Evolution (LTE) amp; LTE- Advanced networks will be challenged by cost and complexity. Self Organizing Network (SON) functionalities promise significant improvement of the network in terms of reducing OPerational EXpenditure (OPEX) and performance improvement. In this paper, we propose a recursive automated optimization method which builds statistical models of the functional relationships between noisy Key Performance Indicators (KPIs) and network parameters; and performs stochastic optimization during the model building process. The proposed methodology is applied to a centralized intra-LTE Mobility Load Balancing (MLB) problem and its performance is evaluated through system level simulations. The results show that the proposed modeling and optimization approach is a promising solution for centralized intra-LTE MLB in terms of optimization performance and convergence under noisy data.

Existing computer simulations of aircraft infrared signature (IRS) do not account for dispersion induced by uncertainty on input data, such as aircraft aspect angles and meteorological conditions. As a result, they are of little use to estimate the detection performance of IR optronic systems; in this case, the scenario encompasses a lot of possible situations that must be indeed addressed, but cannot be singly simulated. In this paper, we focus on low-resolution infrared sensors and we propose a methodological approach for predicting simulated IRS dispersion of poorly known aircraft and performing aircraft detection on the resulting set of low-resolution infrared images. It is based on a sensitivity analysis, which identifies inputs that have negligible influence on the computed IRS and can be set at a constant value, on a quasi-Monte Carlo survey of the code output dispersion, and on a new detection test taking advantage of level sets estimation. This method is illustrated in a typical scenario, i.e., a daylight air-to-ground full-frontal attack by a generic combat aircraft flying at low altitude, over a database of 90,000 simulated aircraft images. Assuming a white noise or a fractional Brownian background model, detection performances are very promising.

This article provides a central limit theorem for a consistent estimator of the population eigenvalues of a class of sample covariance matrices. An exact expression as well as an empirical and asymptotically accurate approximation of the limiting variance is also derived. These results are applied in a cognitive radio context featuring an orthogonal-CDMA primary network and a secondary network whose objective is to maximise the coverage of secondary transmissions under low probability of interference with primary users.

We consider the minimization of a convex objective function defined on a Hilbert space, which is only available through unbiased estimates of its gradients. This problem includes standard machine learning algorithms such as kernel logistic regression and least-squares regression, and is commonly referred to as a stochastic approximation problem in the operations research community. We provide a non-asymptotic analysis of the convergence of two well-known algorithms, stochastic gradient descent (a.k.a.~Robbins-Monro algorithm) as well as a simple modification where iterates are averaged (a.k.a.~Polyak-Ruppert averaging). Our analysis suggests that a learning rate proportional to the inverse of the number of iterations, while leading to the optimal convergence rate in the strongly convex case, is not robust to the lack of strong convexity or the setting of the proportionality constant. This situation is remedied when using slower decays together with averaging, robustly leading to the optimal rate of convergence. We illustrate our theoretical results with simulations on synthetic and standard datasets.

In this paper we propose a Bayesian approach for estimating parameters of the radio propagation model, and an iterative Kriging interpolation algorithm for choosing the best candidate measurement to be retrieved into the Radio Environment Map (REM). We compare the performance with a random choice of the candidate measurement and show that our algorithm reduces the amount of measurement needed by 33%. The proposed algorithm has also the merit of being fast enough to be implemented in an online fashion for REMs with a grid size of 25m and for pedestrian mobile speeds.

This paper addresses the detection of a stochastic process in noise from a finite sample under various sampling schemes. We consider two hypotheses. The noise only hypothesis amounts to model the observations as a sample of a i.i.d. Gaussian random variables (noise only). The signal plus noise hypothesis models the observations as the samples of a continuous time stationary Gaussian process (the signal) taken at known but random time-instants and corrupted with an additive noise. Two binary tests are considered, depending on which assumptions is retained as the null hypothesis. Assuming that the signal is a linear combination of the solution of a multidimensional stochastic differential equation (SDE), it is shown that the minimum Type II error probability decreases exponentially in the number of samples when the False Alarm probability is fixed. This behavior is described by error exponents that are completely characterized. It turns out that they are related to the asymptotic behavior of the Kalman Filter in random stationary environment, which is studied in this paper. Finally, numerical illustrations of our claims are provided in the context of sensor networks.

We propose a new method, based on level sets, to detect aircraft on low resolution infrared images. Aircraft correspond to hot temperatures at the sensor level. Hence it is natural to rely on a test that considers the hottest pixels in the sensed image. If these pixels are close, they are likely to come from a target (i.e., an aircraft); otherwise they belong to the clutter. Instead of manually testing the neighborhood of each hot pixel, we use level sets; this is the first contribution of the paper (corresponding to eq. 2). The other contribution is the calibration of the resulting test. The method is implemented and tested over a database containing 45 604 simulated aircraft images and provides 98.5% of correct detections.

This paper deals with the detection of a continuous random process described by an Ornstein-Uhlenbeck (O-U) stochastic differential equation. Randomly spaced sensors or equivalently a random time sampler which deliver noisy samples of the process are used for this detection. Two types of tests are considered: either H0 refers to the presence of the noisy O-U process or H0 refers to the sole presence of noise. For any fixed false alarm probability, it is shown that the type II error probability decreases to zero exponentially in the number of samples. The exponents, which do not depend on the false alarm probability, are characterized. This work completes former contributions that consider noiseless O-U process with a random sampling or noisy O-U processes with a regular sampling.

This paper presents an online tuning approach for the ad-hoc reinforcement learning algorithms which are used for solving the exploitation-exploration dilemma of the opportunistic spectrum access, in dynamic environments. These algorithms originate from a well-known problem in computer science: the multi-armed bandit (MAB) problem and they have provided evidence to be viable solutions for the detection and exploration of white spaces in opportunistic spectrum access. Previous work (A. Ben Hadj Alaya-Feki et al., 2008) has shown that the reinforcement learning solutions of the MAB problem are very sensitive to the statistical properties of the wireless medium access and therefore need careful tuning according to the dynamic variations of the wireless environment. This paper deals with the online tuning of those algorithms by proposing and assessing two different approaches: 1-a meta learning approach where a second learner (meta learner) is used to learn the parameters of the base learner, and 2-the Exp3 algorithm that has been previously proposed for dynamical tuning of MAB parameters in other contexts. The simulation results obtained on an IEEE 802.11medium access scenario show that one of the proposed meta-learning methods, namely the change point detection method, achieves much better performance compared to the other methods.

We introduce a kernel-based method for change-point analysis within a sequence of temporal observations. Change-point analysis of an (unlabelled) sample of observations consists in, first, testing whether a change in the distribution occurs within the sample, and second, if a change occurs, estimating the change-point instant after which the distribution of the observations switches from one distribution to another different distribution. We propose a test statistics based upon the maximum kernel Fisher discriminant ratio as a measure of homogeneity between segments. We derive its limiting distribution under the null hypothesis (no change occurs), and establish the consistency under the alternative hypothesis (a change occurs). This allows to build a statistical hypothesis testing procedure for testing the presence of change-point, with a prescribed false-alarm probability and detection probability tending to one in the large-sample setting. If a change actually occurs, the test statistics also yields an estimator of the change-point location. Promising experimental results in temporal segmentation of mental tasks from BCI data and pop song indexation are presented.

This paper introduces interference cartography, a simple and effective concept that helps detect, identify and use spectrum opportunities in a secondary spectrum usage context. Interference cartography combines measurements performed by different network entities (mobile terminals, base stations, access points) with the geo-location information and applies simple and effective spatial interpolation techniques to achieve a map which indicates the level of interference experienced at each mesh over the area of interest. Using this information, a secondary network can detect the presence of a primary network (or of other secondary networks) and can use spectrum opportunities without causing harmful interference to them. As an example, a reliable spatial interpolation technique, kriging, is applied to interference data obtained from a radio network simulator. Obtained results demonstrate that interference cartography is a promising concept that can enhance the performance of secondary spectrum usage.

Opportunistic spectrum access (OSA) is a hot topic in cognitive radio context. The main challenge of the OSA is to define improved spectral usage schemes, through the utilization of frequency holes in licensed bands. The multi armed bandit (MAB) is a reinforcement learning technique that can provide the secondary user with the adequate rules, in order to perform simultaneously 1) the exploitation of its external environment and 2) the exploration of the accumulated knowledge by transmitting in the identified white spaces. However, the MAB is sensitive to the non-stationarity of the channels' statistical characteristics. Thus, in this paper, we address an offline sensitivity study to optimize the parameter tuning in the used MAB allocation strategies. Also, we propose a semi dynamic parameter tuning scheme to achieve an online update of the MAB parameters. This adaptive MAB solution enhances the performance of the secondary user in dynamic environments.

This paper presents a use case scenario of IEEE P1900.4 standard designed to achieve temporal opportunistic spectrum access within IEEE802.11 bands. This offers a flexible framework that allows better utilization of radio resources and thus increases spectral efficiency. In this work, we propose a complete framework including scenario description with IEEE P1900.4 and ad-hoc reinforcement techniques for efficient opportunistic spectrum access. Thus, we propose to use the multi armed bandit approach at the terminal side. Results prove this method to achieve overall good results in performing opportunistic access within IEEE802.11 bands.

In this paper we consider the localization of a mobile station (MS) in time division multiple access (TDMA) based communication systems. We use joint angle and delay measurements of the emitted signals, impinging on an antenna array at different base stations (BSs). Contrary to previously reported work, our technique takes into account not only the measurement noise, but also multipath propagation and possible BSs reporting only non line of sight (NLOS) measurements. Data are processed using the maximum likelihood (ML) approach based on an implementation of the Expectation Maximization (EM) algorithm. We illustrate the proposed approach using simulated data.

We propose to test for the homogeneity of two samples by using Kernel Fisher discriminant Analysis. This provides us with a consistent nonparametric test statistic, for which we derive the asymptotic distribution under the null hypothesis. We give experimental evidence of the relevance of our method on both artificial and real datasets.

It is now over a decade since the pioneering contribution of Gordon (1993), which is commonly regarded as the first instance of modern sequential Monte Carlo (SMC) approaches. Initially focussed on applications to tracking and vision, these techniques are now very widespread and have had a significant impact in virtually all areas of signal and image processing concerned with Bayesian dynamical models. This paper is intended to serve both as an introduction to SMC algorithms for nonspecialists and as a reference to recent contributions in domains where the techniques are still under significant development, including smoothing, estimation of fixed parameters and use of SMC methods beyond the standard filtering contexts.

We propose a new recursive EM (REM) algorithm that can be used whenever the complete-data model associated to the observed data belongs to an exponential family of distributions. The main characteristic of our approach is to use a stochastic approximation algorithm to approximate the conditional expectation of the complete-data sufficient statistic rather than the unknown parameter itself. Compared to existing approaches, the new algorithm requires no analytical gradient or Hessian computation, it deals with parameter constraints straightforwardly and the resulting estimate can be shown to be Fisher-efficient in general settings. This approach is illustrated on the classic direction of arrival (DOA) model

In this paper, we consider the localization of a source from quantized measurements of time of arrivals (TOA) or time difference of arrivals (TDOA). Applications include, as particular examples, acoustic source localization from a network of microphones under communication constraints, and the localization of a base station using a geolocalized mobile station using tuning advance measurements. We use a maximum likelihood approach, based on an efficient implementation of the EM algorithm. Contrary to previously reported work, our technique takes into account not only the measurement noise, but also the presence of outliers (for example, non line of sight propagation) and the quantization. We illustrate our findings using simulated data and real field measurements

We consider the problem of pile-ups occurring in gamma spectrometry signals for HPGe detectors. The temporal signal is transformed in a sequence of busy and idle periods, each busy period being characterized by its duration and its associated energy. We present an estimator to correct the pile-up phenomenon, based on an analytical formula. Applications on simulations and real spectrometrical signals are presented, which show good adequation between what we wish to retrieve and the estimation

This paper highlights some fundamental issues involved in the study of large-scale dynamical systems. Two particular topics are discussed in some detail, one dealing with the management of active sensors via partially observable Markov decision processes, and the other dealing with the modeling, recognition and tracking of multi-function radars in an electronic warfare environment.

Many signal processing applications reduce to solving combinatorial optimization problems. Semidefinite programming (SDP) has been shown to be a very promising approach to combinatorial optimization, where SDP serves as a tractable convex relaxation of NP-hard problems. We present a nonlinear programming algorithm for solving SDP, based on a change of variables that replaces the symmetrical, positive semidefinite variable X in SDP with a rectangular variable R according to X=RR/sup T/. Very encouraging results are obtained to solve even large-scale combinatorial optimization programs, as the one arising in multiuser detection for code division multiple access (CDMA) systems.

We consider semiparametric fractional exponential (FEXP) estimators of the memory parameter d for a potentially nonstationary linear long-memory time series with smooth additive trend. We use differencing to annihilate the trend, followed by tapering to handle the potential non-invertibility of the differenced series. We propose a method of pooling the tapered periodogram which leads to more efficient estimators of d than existing pooled, tapered estimators. We establish asymptotic normality of the estimator. Finally, we consider minimax rate-optimality and feasible nearly rate-optimal estimators. Some simulations are presented to illustrate our findings.

We provide a theoretical framework of de-noising for UMTS TDD-like mobile radio communication systems. Based on the Bayesian approach, we show how to de-noise channel estimates provided by the training-based estimation procedure. The proposed schemes allow not only for eliminating major drawbacks of hard thresholding but also for a low complexity implementation.

Estimation of the spectral envelope (magnitude of the transfer function) of a filter driven by a periodic signal is a long-standing problem in speech and audio processing. Recently, there has been a renewed interest in this issue in connection with the rapid developments of processing techniques based on sinusoidal modeling. In this paper, we introduce a new performance criterion for spectral envelope fitting which is based on the statistical analysis of the behavior of the empirical sinusoidal magnitude estimates. We further show that penalization is an efficient approach to control the smoothness of the estimation envelope. In low-noise situations, the proposed method can be approximated by a two-step weighted least-squares procedure which also provides an interesting insight into the limitations of the previously proposed "discrete cepstrum" approach. A systematic simulation study confirms that the proposed methods perform significantly better than existing ones for high pitched and noisy signals.

We study the performance of a semi-blind subspace channel estimate in the particular context of the uplink of the UMTS time division duplexing (TDD) mode. The TDD mode of the third generation system UMTS is a multiuser DS-CDMA scheme of maximal spreading factor N=16. In the uplink, each slot corresponds to 2560 chips and the channel estimation is classically achieved by using a 512 training chips midamble. In this well defined context, we study the improvements (in terms of bit error rate) provided by a semi-blind channel estimation technique introduced in the context of the single user system of Gorokhov and Loubaton (see Proc. ICASSP, p.3905-3908, 1997) and studied in detail by Buchoux, Moulines, Cappe and Gorokhov (see SPAWC, 1999).

Blind channel estimation for periodic sequence DS-CDMA systems can be cast into the framework of "structured" blind estimation of multi-input/multi-output (MIMO) FIR systems, where the structure is imposed by the user's signatures. A possible approach to tackle this problem consists in looking for a structured solution to one of the so-called "blind" MIMO-FIR system identification techniques proposed previously. This is the approach undertaken, among others, by Wang and Poor (see IEEE Trans. on Communications, vol.46, no.1, p.92-103, 1998), who proposed an adaptation of the subspace method originally developed by Moulines et al. (see IEEE Trans. on Signal Processing, vol.43, no.2, p.516-25, 1995) for single-input multiple outputs (SIMO) FIR systems, and later extended by Abed-Meraim et al. (see IEEE Trans. on Information Theory, vol.43, no.2, p.499-511, 1997) to MIMO-FIR systems. In this article, we follow this approach to consider the particular blind forward channel estimation problem, and improve quite significantly the results presented by Wang and Poor.

Most second order single input multiple output (SIMO) identification algorithms identify the global impulse channel response, convolution of an emission filter and a propagation channel. This paper makes an explicit use of this channel structure in a second order algorithm. We present several structured methods exploiting more or less prior information on the emission filter. Proofs of convergence are provided, and simulations show that some knowledge based algorithms greatly improve over classical blind algorithms, even in the case where the knowledge is partial.

Hidden Markov models (HMMs) are used in many signal processing applications including speech recognition, blind equalization of digital communications channels, etc. The most widely used method for maximum likelihood estimation of HMM parameters is the forward-backward (or Baum-Welch) algorithm which is an early example of application of the expectation-maximization (EM) principle. In this contribution, an alternative fast-converging approach for maximum likelihood estimation of HMM parameters is described. This new techniques is based on the use of general purpose quasi-Newton optimization methods as well as on an efficient purely recursive algorithm for computing the log-likelihood and its derivative.

Harmonic plus noise models have been successfully applied to a broad range of speech processing applications, including, among others, low bit-rate speech coding, and speech restoration and transformation. In conventional methods, the frequencies, the relative phases and the amplitudes of the pitch-harmonic components are assumed to be piecewise constants over an analysis frame. This assumption is inadequate in segments where fast variations of these parameters may occur, e.g. phoneme-to-phoneme boundaries or speech onsets. In this paper, a time-varying model of the pitch-harmonic parameter is presented. It is based on a basis expansion technique, consisting in representing the time-varying functions as a linear combination of a fixed basis function. An estimation procedure for the parameters of this expansion is presented. Results are provided to demonstrate the effectiveness of this approach.

In this paper, a perturbation expansion technique is introduced to decompose the tracking error of a general adaptive tracking algorithm in a linear regression model. This method allows to obtain the tracking error bound and also tight approximate expressions for the moments of the tracking error. These expressions allow to evaluate, both qualitatively and quantitatively, the impact of several factors on the tracking error performance which have been overlooked in previous contributions.

For speech recognition based on hidden Markov modeling, parameter-tying, which consists of constraining some of the parameters of the model to share the same value, has emerged as a standard practice. An original algorithm is proposed that makes it possible to jointly estimate both the shared model parameters and the tying characteristics, using the maximum likelihood criterion. The proposed algorithm is based on a previously introduced extension of the classic expectation-maximization (EM) framework. The convergence properties of this class of algorithms are analyzed in detail. The method is evaluated on an isolated word recognition task using hidden Markov models (HMMs) with Gaussian observation densities and tying at the state level. Finally, the extension of this method to the case of mixture observation densities with tying at the mixture component level is discussed.

Voice conversion, as considered in this paper, is defined as modifying the speech signal of one speaker (source speaker) so that it sounds as if it had been pronounced by a different speaker (target speaker). Our contribution includes the design of a new methodology for representing the relationship between two sets of spectral envelopes. The proposed method is based on the use of a Gaussian mixture model of the source speaker spectral envelopes. The conversion itself is represented by a continuous parametric function which takes into account the probabilistic classification provided by the mixture model. The parameters of the conversion function are estimated by least squares optimization on the training data. This conversion method is implemented in the context of the HNM (harmonic+noise model) system, which allows high-quality modifications of speech signals. Compared to earlier methods based on vector quantization, the proposed conversion scheme results in a much better match between the converted envelopes and the target envelopes. Evaluation by objective tests and formal listening tests shows that the proposed transform greatly improves the quality and naturalness of the converted speech signals compared with previous proposed conversion methods.

An approximate maximum likelihood method for blind source separation and deconvolution of noisy signal is proposed. This technique relies upon a data augmentation scheme, where the (unobserved) input are viewed as the missing data. In the technique described, the input signal distribution is modeled by a mixture of Gaussian distributions, enabling the use of explicit formula for computing the posterior density and conditional expectation and thus avoiding Monte-Carlo integrations. Because this technique is able to capture some salient features of the input signal distribution, it performs generally much better than third-order or fourth-order cumulant based techniques.

This paper introduces a Gaussianity test for causal invertible time series. It is based on a quadratic form in differences between sample means and expected values of certain finite memory nonlinear functions of the estimated innovation sequence. The test has, by construction, an interesting property: under reasonable assumptions on the regularity of the stationary process, it is asymptotically invariant with respect to the spectral density of the process. Monte-Carlo experiments are included to illustrate the proposed approach.

We present a new subspace-based method for blind identification of multichannel finite impulse response (FIR) systems. Instead of assuming spatially white additive noise as commonly used, we consider the case where the noise spatial covariance matrix is unknown. We show how a standard subspace method can be simply modified so that the channel estimate does not depend on the zero-lag correlation coefficient of the observation vector and, thus, is independent of the spatial covariance matrix of the additive noise.

The problem of blind identification of p-inputs/q-outputs FIR transfer functions is addressed. Existing subspace identification methods derived for p=1 are first reformulated. In particular, the links between the noise subspace of a certain covariance matrix of the output signals (on which subspace methods build on) and certain rational subspaces associated with the transfer function to be identified are elucidated. Based on these relations, we study the behavior of the subspace method in the case where the order of the transfer function is overestimated. Next, an asymptotic performance analysis of this estimation method is carried out. Consistency and asymptotical normality of the estimates is established. A closed-form expression for the asymptotic covariance of the estimates is given. Numerical simulations and investigations are presented to demonstrate the potential of the subspace method. Finally, we take advantage of our new reformulation to discuss the extension of the subspace method to the case p>1. We show where the difficulties lie, and we briefly indicate how to solve the corresponding problems. The possible connections with classical approaches for MA model estimations are also outlined.

Multipath propagation appears to be a typical limitation in mobile digital communications where it leads to severe intersymbol interference. The classical techniques to overcome this problem use either periodically sent training sequences or blind approaches. This paper addresses the blind identification of FIR multiple input multiple output (MIMO) transfer functions in the case where the number of inputs is strictly less than the number of outputs. We consider a second order identification providing signals extraction up to a regular instantaneous mixture matrix. A novel method of second order channel estimation is presented. Basically exploiting the simultaneous MA and AR nature of the observations, it displays however a considerable improvement as compared to the original linear prediction approach. Performance study and comparison with the existing approach is provided by computer simulations.

Blind identification of single-input multiple-output (SIMO) FIR systems based on second order statistics has attracted a lot of research efforts. We focus on subspace estimation procedures, which exploit the structure of the range space of certain matrix-valued statistics constructed by arranging in a prescribed order the covariance coefficients of the observations. General subspace identifiability results are obtained, based on the properties of minimal polynomial bases of rational subspaces. Several subspace estimation procedures are then derived. These estimators are all based on the (possibly weighted) least-square solution of an overdetermined system of linear equations and are thus well-suited for practical implementations.

Traditional spectral envelope estimation methods suffer from significant drawbacks in (high-pitched) voiced segments: spectral peaks tend to be biased toward pitch harmonics. To alleviate this drawback, discrete modeling techniques have been proposed. The discrete cepstrum method consists in fitting a spectral envelope parameterized by cepstrum coefficients to a discrete set of spectral points using a log-spectral distortion criterion. Unfortunately, this estimation problem is ill conditioned in many cases of interest. The article introduces a simple regularization technique that guarantees that the spectral envelope is well behaved. A modification of the basic regularization criterion is proposed in order to take into account a possible prior knowledge of the spectral tilt of the envelope.

Blind channel identification methods based on the oversampled channel output is a problem of theoretical and practical interest. It is first demonstrated that the subspace methods developed in Moulines are not robust to errors in the determination of the model order. An alternative solution is then proposed, based on a linear prediction approach. The effect of overestimating the channel order is investigated by simulations: it is demonstrated that the prediction error method is "robust" to over-determination.

The article deals with the problem of blind separation of an instantaneous linear mixture of mutually uncorrelated sources. A solution based on the joint diagonalisation of a set of whitened correlation matrices has been proposed, along with an efficient algorithm to solve it. A second order source separation technique exploiting the time coherence of the source signals is considered. Asymptotic performance analysis of the proposed method is performed. Several numerical simulations are presented to demonstrate the effectiveness of the proposed method and to validate the theoretical expression of the asymptotic performance index.>

A class of methods for identifying a single input/multiple output finite impulse response system (SIMO-FIR), from the outputs of the system only is presented. These methods rely on a minimal parametric representation of the system solution. They are based on the orthogonality between a 'signal' and a 'noise' subspaces. This is exploited to build quadratic forms whose minimization yields the desired estimates up to a scale factor. It is shown (by numerical simulations) that these methods provide significantly better (in terms of bias and variance) estimates than the method by Tong et al. (1991), while requiring about one half the number of computations. They are thus very attractive for applications, in particular, for narrowband TDMA channel equalization.>

The authors deal with frequency-domain (FD) adaptive identification with application to acoustic echo cancellation. Several proposed frequency-domain LMS algorithms are reviewed and unified in the common framework of fast convolution using the short-term Fourier transform. A more flexible identification scheme is then proposed, making it possible to independently control the delay and the adaptation rate. The theoretical proof of convergence of this new scheme is provided together with simulations demonstrating the efficiency of this method in both stationary and nonstationary environments.>

High-resolution direction finding algorithms using higher-order cumulants of the array data is addressed. Two fourth-order cumulant-based matrices are considered: the diagonal cumulant slice and the contracted quadricovariance. They are evaluated in the context of direction of arrival (DOA) estimation using subspace techniques. To this purpose, an original methodology is introduced to derive the closed form of asymptotical performance. This analysis is applied to the cumulant-based DOA estimation problem, establishing on a rational basis the domain of applicability of HOS in DOA estimation, which is larger than usually believed. It is also shown that the contracted quadricovariance outperforms the diagonal slice in all respects. Some numerical evaluations illustrate the results.>

Whereas speaker adaptation has received much attention for speech recognition few studies have been devoted to voice transformation for speech synthesis, despite the potential interests of such techniques. The authors propose a voice conversion system which combines the time-domain pitch synchronous overlap and add (TD-PSOLA) technique with a source-filter decomposition. The first technique allows prosodic modifications while the second enables spectral envelope transformations. Two approaches to learn spectral alteration are compared: the linear multivariate regression (LMR) and the dynamic frequency warping (DFW).>

The main features of the CNET diphone-based text-to-speech system for French language are described. The linguistic analysis works in three steps. First, a morphosyntactic analysis module assigns a grammatical value to each word in the text and transcribes it phonetically. A second module parses the text into hierarchical syntactico-prosodic groups. Finally, prosodic patterns are automatically assigned to each word by queries to a database of prosodic events. The phonetic and prosodic information serves as commands to the synthesis component. The synthesis component is based on diphone concatenation. A time-domain formulation of the pitch-synchronous overlap-add scheme (TD-PSOLA) is used to modify the speech prosody and to concatenate diphone waveforms. It is combined with a low bit-rate speech decoder to reduce the memory requirement for storing the diphone inventory. The system runs in real time on a PC equipped with a TMS320C25 DSP board and provides notably improved sound quality and naturalness in comparison to commercially available systems.>

A novel time-domain algorithm is presented for text-to-speech synthesis using diphone concatenation. The algorithm is based on the pitch-synchronous overlap-add (PSOLA) approach and is capable of good quality prosodic modifications of natural speech. The algorithm can be seen as a simplification of a previous algorithm combining the PSOLA approach and frequency-domain transformations. On the other hand, it appears as a generalization of previous time-domain methods that perform pitch synchronous cut-and-splice operations on the speech waveform. This algorithm is used in the CNET diphone synthesis multilingual system, actually supporting three languages: French, Italian, and German. The resulting speech has been tested on French and is judged of much better quality than for an LPC-based synthesizer.>

The authors present FFT synthesis algorithms for a French text-to-speech system based on diphone concatenation. FFT synthesis techniques are capable of producing high quality prosodic modifications of natural speech. Several approaches are presented to reduce the distortions due to diphone concatenation. They are based on appropriate manipulations of the phase spectrum, either by phase equalization across all the diphones, or by phase smoothing between successive diphones. The resulting speech is significantly better quality than with conventional LPC synthesis. An experiment to reduce the computational cost by performing all the FFTs off-line is described. The resulting speech is slightly degraded with respect to 'full' FFT synthesized speech, but it remains more natural in comparison with the LPC speech.>