Беломестный Денис Витальевич

Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation

2024 · PREPRINT · en

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 technique 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. More precisely, we show that the mean-squared error can be decomposed into the sum of two terms: a leading one of order $n^{-1/2}$ with explicit dependence on a minimax-optimal asymptotic covariance matrix, and a second-order term of order $n^{-3/4}$ where the power 3/4 can not be improved in general. We also extend this result to the p-th moment bound keeping optimal scaling of the remainders with respect to n. 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.

Simultaneous approximation of a smooth function and its derivatives by deep neural networks with piecewise-polynomial activations

2023 · ARTICLE · en

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 deep neural network to approximate any Hölder smooth function up to a given approximation error in Hölder norms in such a way that all weights of this neural network are bounded by 1. The latter feature is essential to control generalization errors in many statistical and machine learning applications.

Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms

2023 · ARTICLE · en

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 density of a weighted Dirichlet sum. This representation allows us to obtain a Gaussian-like approximation for the sum distribution using geometry and complex analysis methods. Our results generalize similar bounds for the Beta distribution obtained in the seminal paper Alfers and Dinges [1984]. Additionally, our results can be considered a sharp non-asymptotic version of the inverse of Sanov's theorem studied by Ganesh and O'Connell [1999] in the Bayesian setting. Based on these results, we derive new deviation bounds for the Dirichlet process posterior means with application to Bayesian bootstrap. Finally, we apply our estimates to the analysis of the Multinomial Thompson Sampling (TS) algorithm in multi-armed bandits and significantly sharpen the existing regret bounds by making them independent of the size of the arms distribution support.

Semiparametric estimation of McKean–Vlasov SDEs

2023 · ARTICLE · en

In this paper we study the problem of semiparametric estimation for a class of McKean–Vlasov stochastic differential equations. Our aim is to estimate the drift coefficient of a MV-SDE based on observations of the corresponding particle system. We propose a semiparametric estimation procedure and derive the rates of convergence for the resulting estimator. We further prove that the obtained rates are essentially optimal in the minimax sense.

Weak solutions to gamma-driven stochastic differential equations

2023 · ARTICLE · en

We study a stochastic differential equation driven by a gamma process, for which we give results on the existence of weak solutions under conditions on the volatility function. To that end we provide results on the density process between the laws of solutions with different volatility functions.

Foundations of Modern Statistics: Festschrift in Honor of Vladimir Spokoiny, Berlin, Germany, November 6–8, 2019, Moscow, Russia, November 30, 2019

2023 · BOOK · en

This book contains contributions from the participants of the international conference “Foundations of Modern Statistics” which took place at Weierstrass Institute for Applied Analysis and Stochastics (WIAS), Berlin, during November 6–8, 2019, and at Higher School of Economics (HSE University), Moscow, during November 30, 2019. The events were organized in honor of Professor Vladimir Spokoiny on the occasion of his 60th birthday. Vladimir Spokoiny has pioneered the field of adaptive statistical inference and contributed to a variety of its applications. His more than 30 years of research in the field of mathematical statistics had a great influence on the development of the mathematical theory of statistics to its present state. It has inspired many young researchers to start their research in this exciting field of mathematics. The papers contained in this book reflect the broad field of interests of Vladimir Spokoiny: optimal rates and non-asymptotic bounds in nonparametrics, Bayes approaches from a frequentist point of view, optimization, signal processing, and statistical theory motivated by models in applied fields. Materials prepared by famous scientists contain original scientific results, which makes the publication valuable for researchers working in these fields. The book concludes by a conversation of Vladimir Spokoiny with Markus Reiβ and Enno Mammen. This interview gives some background on the life of Vladimir Spokoiny and his many scientific interests and motivations.

Fast Rates for Maximum Entropy Exploration

2023 · CHAPTER · en

Model-free Posterior Sampling via Learning Rate Randomization

2023 · CHAPTER · en

Variance reduction for additive functionals of Markov chains via martingale representations

2022 · ARTICLE · en

In this paper, we propose an efficient variance reduction approach for additive functionals of Markov chains relying on a novel discrete-time martingale representation. Our approach is fully non-asymptotic and does not require the knowledge of the stationary distribution (and even any type of ergodicity) or specific structure of the underlying density. By rigorously analyzing the convergence properties of the proposed algorithm, we show that its cost-to-variance product is indeed smaller than one of the naive algorithms. The numerical performance of the new method is illustrated for the Langevin-type Markov chain Monte Carlo (MCMC) methods.

Empirical Variance Minimization with Applications in Variance Reduction and Optimal Control

2022 · ARTICLE · en

We study the problem of empirical minimization for variance-type functionals over functional classes. Sharp non-asymptotic bounds for the excess variance are derived under mild conditions. In particular, it is shown that under some restrictions imposed on the functional class fast convergence rates can be achieved including the optimal non-parametric rates for expressive classes in the non-Donsker regime under some additional assumptions. Our main applications include variance reduction and optimal control.