Stochastic Optimization and Data Science

A. Avetisyan, D. Dvinskikh, A. Gasnikov, V. Temlyakov, N. Tupitsa, D. Turdakov · 2026

Read Stochastic Optimization and Data Science by A. Avetisyan, D. Dvinskikh, A. Gasnikov, V. Temlyakov, N. Tupitsa, D. Turdakov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16875.txt.

Introduction

Avetisyan's team motivates stochastic optimisation from statistics and learning, where the aim is to maximise likelihood or cut population risk. The short paper sketches two main routes to expectation minimisation: offline methods based on Monte Carlo sampling and sample-average approximation, and online stochastic approximation. It frames both routes as plain ways to solve the same class of expectation problems, giving a compact map of the field's two standard approaches for new readers.

Catalog record

CREATORA. Avetisyan, D. Dvinskikh, A. Gasnikov, V. Temlyakov, N. Tupitsa, D. Turdakov
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108976
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.16875

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stochastic Optimization and Data Science A. Avetisyan, D. Dvinskikh, A. Gasnikov, V. Temlyakov, N. Tupitsa, D. Turdakov Abstract Аннотация This paper aims to motivate stochastic optimization problems from a statistical perspective and a statistical learning perspective, where the goal is to maximize the log-likelihood or minimize the population risk. We briefly describe the two main approaches: offline (Monte Carlo / Sample Average Approximation) and online (Stochastic Approximation) approaches – to solve the expectation minimization problems. Ключевые слова: stochastic optimization, statistical learning, sample average approximation, stochastic approximation, empirical risk minimization, population risk minimization, maximum likelihood estimation, stochastic gradient methods, sample complexity, high-probability guarantees, Bayesian estimation, regularization 0 0 footnotetext: This work was supported by a grant, provided by the Ministry of Economic Development of the Russian Federation (agreement dated June 20, 2025 No. 139-15-2025-011, identifier 000000C313925P4G0002). 1 Introduction This survey is devoted to solving stochastic optimization problems. Such problems play a crucial role in modern data analysis. One could even go so far as to say that data analysis in its modern sense essentially involves deriving and solving corresponding stochastic optimization problems \min\limits_{x\in Q\subseteq\mathbb{R}^{n}}\left\{f(x):=\mathbb{E}_{\xi\sim{\cal D}}[f(x,\xi)]\right\}, (1.1) where function f is convex in x ( x\in Q, Q is a convex set), and \mathbb{E}_{\xi\sim{\cal D}}[f(x,\xi)] is the expectation of f with respect to random variable \xi with unknown distribution {\cal D} . The first part of this review explains how stochastic optimization problems arise in mathematical statistics and machine learning. Further, two alternative approaches are proposed for solving these stochastic optimization problems: offline Monte Carlo / Sample Average Approximation and online Stochastic Approximation approaches. Each approach for convex problem formulations is quite well developed. We notice that the crucial results in online setup were obtained in outstanding book 94 , see also 95 and in offline approach were obtained in the last two decades, see e.g., 129 ; 126 . The last part of the survey devoted to modern mathematically strong results that improve optimal rates from the previous parts under additional assumptions. 2 Motivation to stochastic optimization According to 128 , <<Optimization problems involving stochastic models occur in almost all areas of science and engineering, so diverse as telecommunication, medicine, or finance, to name just a few. This stimulates the interest in rigorous ways of formulating, analyzing, and solving such problems. Due to the presence of random parameters in the model, the theory combines concepts of the optimization theory, the theory of probability and statistics, and functional analysis. Moreover, in the recent years the theory and methods of stochastic programming have undergone major advances.>> This <<major advances>> are strongly stimulated by the explosion of interest in Data science problems. In the last decade, several good books have appeared on the relationship between Stochastic Optimization and Data Science 128 ; 125 ; 10 . In this section, we briefly describe the two main origins of stochastic optimization problems in Data Science: 1) Statistical origin ( maximum likelihood estimation ) and 2) Machine Learning origin ( stochastic gradient descent and regularized expected risk minimization ). 2.1 Statistical motivation We start with the simplest example. Let x^{\star}\in\mathbb{R} be an unknown scalar parameter, \eta\sim\mathcal{N}\left(0,\sigma^{2}\right) be Gaussian noise. Assume that we can measure \xi^{k}=x^{\star}+\eta^{k} , k=1,...,N , where \eta^{k} are i.i.d. (independent identically distributed as \eta ). The goal is to estimate x^{\star} from \left\{\xi^{k}\right\}_{k=1}^{N} . The main observation is the following: x^{\star} is a solution of the stochastic optimization problem \min\limits_{x\in\mathbb{R}}\mathbb{E}_{\xi}\left[f(x,\xi):=(\xi-x)^{2}\right], (2.1) where \xi\sim\mathcal{N}\left(x^{\star},\sigma^{2}\right) . Indeed, \mathbb{E}_{\xi}(\xi-x)^{2}=\mathbb{E}_{\xi}\xi^{2}-2x\mathbb{E}_{\xi}\xi+x^{2}=(x^{\star})^{2}+\sigma^{2}-2xx^{\star}+x^{2}=(x^{\star}-x)^{2}+\sigma^{2} attains minimum in x=x^{\star} . However, x^{\star} is unknown (and probably \sigma^{2} ). How problem ( 2.1 ) can be solved? Since \left\{\xi^{k}\right\}_{k=1}^{N} are available, the Monte Carlo approach can be employed. This approach consists in replacing problem ( 2.1 ) by its empirical version \min\limits_{x\in\mathbb{R}}\frac{1}{N}\sum_{k=1}^{N}(\xi^{k}-x)^{2}. (2.2) The solution to the problem ( 2.2 ) can be easily provided \bar{x}^{N}=\frac{1}{N}\sum_{k=1}^{N}\xi^{k}. (2.3) In statistics, this average is known as the sample mean , which is the best known (unbiased and with the smallest variance, see Theorem 1 below) estimate for the unknown parameter in the described parametric model, see Theorem 1 hereinafter. The solution ( 2.3 ) can be also obtained by the following online procedure ( x^{0}=0 ) x^{k+1}=x^{k}-\frac{1}{2k}\nabla_{x}f(x^{k},\xi^{k})=x^{k}-\frac{1}{k}(x^{k}-\xi^{k}),\qquad k=1,...,N, (2.4) where \nabla_{x}f(x,\cdot) is the gradient of f with respect to x . This procedure corresponds to the Stochastic Gradient Descent (SGD) for 2 -strongly convex in the \ell_{2} -norm stochastic optimization problem ( 2.1 ). A natural question arising here: by what scheme was f(x,\xi) selected in ( 2.1 )? Probably there are many ways to choose f(x,\xi) . If so, what is the <<best>> way to do it? Further, we briefly describe the basics of the maximum likelihood theory, which allows us to answer these questions. Assume that some random variable \xi depends on an unknown vector of parameters x^{\star}\in\mathbb{R}^{n} . Let p(x,\xi) be the probability (probability density function) that we observe \xi if the true vector of parameters is x\in\mathbb{R}^{n} . In the aforementioned example, n=1 and probability density function was p(x,\xi)=\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp\left\{-\frac{(\xi-x)^{2}}{2\sigma^{2}}\right\}. If i.i.d. samples \left\{\xi^{k}\right\}_{k=1}^{N} are available let us introduce the likelihood p\left(x,\left\{\xi^{k}\right\}_{k=1}^{N}\right)=\prod_{k=1}^{N}p(x,\xi^{k}). Perhaps, one of the most productive ideas in statistics is to estimate the true vector of parameters x^{\star} as a vector that maximizes likelihood p\left(x,\left\{\xi^{k}\right\}_{k=1}^{N}\right) . This problem can be equivalently reformulated as minimization of (normalized) negative log-likelihood \min\limits_{x\in\mathbb{R}^{n}}\left[-\frac{1}{N}\log p\left(x,\left\{\xi^{k}\right\}_{k=1}^{N}\right)=-\frac{1}{N}\sum_{k=1}^{N}\log p(x,\xi^{k})\right]. (2.5) This minimization problem can be considered as the empirical (sometimes called Monte Carlo ) version of the stochastic optimization problem \min\limits_{x\in\mathbb{R}^{n}}\mathbb{E}_{\xi}\left[-\log p(x,\xi)\right]. (2.6) In particular, for the aforementioned Gaussian model, problem ( 2.6 ) has the following form \min\limits_{x\in\mathbb{R}}\mathbb{E}_{\xi}\left[\frac{1}{2\sigma^{2}}(\xi-x)^{2}+\frac{1}{2}\log\left(2\pi\sigma^{2}\right)\right], which is equivalent to ( 2.1 ). Moreover, the observation that the true value of unknown vector of parameters x^{\star} is a solution of ( 2.6 ) holds in the general case, i.e., x^{\star}\in\text{Arg}\min\limits_{x\in\mathbb{R}^{n}}\mathbb{E}_{\xi}\left[-\log p(x,\xi)\right], where \text{Arg}\min means the set of all \arg\min . Indeed, 1) 1) 1) For certainty, here p(x,\xi) is assumed to be a probability density function. \mathbb{E}_{\xi}\left[-\log p(x,\xi)\right]=-\int p(x^{\star},\xi)\log p(x,\xi)d\xi\geqslant-\int p(x^{\star},\xi)\log p(x^{\star},\xi)d\xi since ( the Jensen’s inequality for the entropy) KL\left(p(x^{\star},\cdot),p(x,\cdot)\right)=\int p(x^{\star},\xi)\log\left(\frac{p(x^{\star},\xi)}{p(x,\xi)}\right)d\xi\geqslant 0 and KL\left(p(x^{\star},\cdot),p(x,\cdot)\right)=0 , when x=x^{\star} . Here KL is the Kullback-Leibler divergence. Thus, we explained that in the general case f(x,\xi):=-\log p(x,\xi) in ( 2.1 ) and the maximum likelihood approach is nothing more than the Monte Carlo approach for Stochastic optimization problem ( 2.6 ). Definitely the main gem of statistics is the theorem about asymptotic properties of the maximum likelihood estimation (MLE) (see also ( 2.5 ) – factor 1/N does not matter) \hat{x}_{MLE}^{N}=\arg\max\limits_{x\in\mathbb{R}^{n}}p\left(x,\left\{\xi^{k}\right\}_{k=1}^{N}\right)=\arg\min\limits_{x\in\mathbb{R}^{n}}\left[-\log p\left(x,\left\{\xi^{k}\right\}_{k=1}^{N}\right)\right]. (2.7) The next theorem presents an informal variant of this theorem. Theorem 1 Assume that p(x,\xi) is sufficiently smooth and the set \left\{\xi:p(x,\xi)>0\right\} does not depend on x . 2) 2) 2) This is satisfied for Gaussian noise model \xi=x+\eta , but is not satisfied if the noise \eta is uniformly distributed on [0,x] . We emphasis, that this assumption is informal. Then 1. for all unbiased statistics \tilde{x}^{N}\left(\left\{\xi^{k}\right\}_{k=1}^{N}\right) with finite second moment, the Rao--Cramer inequality holds 3) 3) 3) A\succcurlyeq B means that for all z\in\mathbb{R}^{n} \langle z,(A-B)z\rangle\geqslant 0 . \mathbb{E}_{\left\{\xi^{k}\right\}_{k=1}^{N}}\left[\left(\tilde{x}^{N}\left(\left\{\xi^{k}\right\}_{k=1}^{N}\right)-x^{\star}\right)\left(\tilde{x}^{N}\left(\left\{\xi^{k}\right\}_{k=1}^{N}\right)-x^{\star}\right)^{T}\right]\succcurlyeq\left[NI_{x^{\star}}\right]^{-1}, where I_{x^{\star}}=\mathbb{E}_{\xi}\left[\nabla_{x}\log p(x^{\star},\xi)\left(\nabla_{x}\log p(x^{\star},\xi)\right)^{T}\right] is the Fisher information matrix. 4) 4) 4) Note that KL\left(p(x^{\star},\cdot),p(x^{\star}+y,\cdot)\right)\simeq\frac{1}{2}\langle y,I_{x^{\star}}y\rangle . 2. MLE \hat{x}_{MLE}^{N}\left(\left\{\xi^{k}\right\}_{k=1}^{N}\right) (see ( 2.7 )) has asymptotically 5) 5) 5) Under assumption that N\to\infty .

Read the complete text