26 citations · 134 across the 27 of their papers we have counts for
32 papers
Effective-dimension bounds in the central limit theorem for centered Euclidean balls
Alexey Naumov, Sergey Samsonov, Vladimir Spokoiny +1
We establish a nonasymptotic Gaussian approximation bound over centered Euclidean balls for sums of independent, not necessarily identically distributed, random vectors in \(\mathb…
Mathematical methods of reinforcement learning
Denis Belomestny, Alexander Gasnikov, Egor Gladin +5
Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin t…
First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities
Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova +3
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…
Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms
Denis Belomestny, Pierre Menard, Alexey Naumov +2
In this work, we derive sharp non-asymptotic deviation bounds for weighted sums of Dirichlet random variables. These bounds are based on a novel integral representation of the dens…
Theoretical guarantees for neural control variates in MCMC
Denis Belomestny, Artur Goldman, Alexey Naumov +1
In this paper, we propose a variance reduction approach for Markov chains based on additive control variates and the minimization of an appropriate estimate for the asymptotic vari…
Fast Rates for Maximum Entropy Exploration
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello +7
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 maxim…
Rosenthal-type inequalities for linear statistics of Markov chains
Alain Durmus, Eric Moulines, Alexey Naumov +2
In this paper, we establish novel concentration inequalities for additive functionals of geometrically ergodic Markov chains similar to Rosenthal inequalities for sums of independe…
Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello +6
We consider reinforcement learning in an environment modeled by an episodic, finite, stage-dependent Markov decision process of horizon with states, and actions. The pe…
Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation
Alain Durmus, Eric Moulines, Alexey Naumov +1
This paper provides a finite-time analysis of linear stochastic approximation (LSA) algorithms with fixed step size, a core method in statistics and machine learning. LSA is used t…
From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses
Daniil Tiapkin, Denis Belomestny, Eric Moulines +5
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 Kau…
Simultaneous approximation of a smooth function and its derivatives by deep neural networks with piecewise-polynomial activations
Denis Belomestny, Alexey Naumov, Nikita Puchkin +1
This paper investigates the approximation properties of deep neural networks with piecewise-polynomial activation functions. We derive the required depth, width, and sparsity of a…
Local-Global MCMC kernels: the best of both worlds
Sergey Samsonov, Evgeny Lagutin, Marylou Gabrié +3
Recent works leveraging learning to enhance sampling have shown promising results, in particular by designing effective non-local moves and global proposals. However, learning accu…
Probability and moment inequalities for additive functionals of geometrically ergodic Markov chains
Alain Durmus, Eric Moulines, Alexey Naumov +1
In this paper, we establish moment and Bernstein-type inequalities for additive functionals of geometrically ergodic Markov chains. These inequalities extend the corresponding ineq…
Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
Alain Durmus, Eric Moulines, Alexey Naumov +3
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…
Rates of convergence for density estimation with generative adversarial networks
Nikita Puchkin, Sergey Samsonov, Denis Belomestny +2
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-Shan…
On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning
Alain Durmus, Eric Moulines, Alexey Naumov +2
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 sto…
Two-sided inequalities for the density function's maximum of weighted sum of chi-square variables
Sergey G. Bobkov, Alexey A. Naumov, Vladimir V. Ulyanov
Two--sided bounds are constructed for a probability density function of a weighted sum of chi-square variables. Both cases of central and non-central chi-square variables are consi…
Variance reduction for dependent sequences with applications to Stochastic Gradient MCMC
D. Belomestny, L. Iosipoi, E. Moulines +2
In this paper we propose a novel and practical variance reduction approach for additive functionals of dependent sequences. Our approach combines the use of control variates with t…
Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
Maxim Kaledin, Eric Moulines, Alexey Naumov +2
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 e…
Variance reduction for Markov chains with application to MCMC
D. Belomestny, L. Iosipoi, E. Moulines +2
In this paper we propose a novel variance reduction approach for additive functionals of Markov chains based on minimization of an estimate for the asymptotic variance of these fun…
Local semicircle law under fourth moment condition
Friedrich Götze, Alexey Naumov, Alexander Tikhomirov
We consider a random symmetric matrix with upper triangular entries being independent random variables with mean zero and unit variance. Assuming tha…
Large ball probability, Gaussian comparison and anti-concentration
Friedrich Götze, Alexey Naumov, Vladimir Spokoiny +1
We derive tight non-asymptotic bounds for the Kolmogorov distance between the probabilities of two Gaussian elements to hit a ball in a Hilbert space. The key property of these bou…
On Local laws for non-Hermitian random matrices and their products
Friedrich Götze, Alexey Naumov, Alexander Tikhomirov
The aim of this paper is to prove a local version of the circular law for non-Hermitian random matrices and its generalization to the product of non-Hermitian random matrices under…
Bootstrap confidence sets for spectral projectors of sample covariance
Alexey Naumov, Vladimir Spokoiny, Vladimir Ulyanov
Let be i.i.d. sample in with zero mean and the covariance matrix . The problem of recovering the projector onto an eigenspace of $\m…