05. Probability and Statistics Background — Uncertain Evaluations and Data-Driven Objectives

// BACKGROUND 5/6 — random variable, distribution, expectation, variance, sampling, regression

Optimization does not handle only deterministic problems. Probability and statistics are needed when data contains noise, the objective is estimated through sampling, or simulation results are uncertain.

Random variables

A random variable is a function that turns experimental outcomes into numbers. In optimization, the objective may itself be a random variable:

$$F(x,\xi).$$

Here $x$ is the variable we choose, while $\xi$ is randomness originating from data or the environment.

Distributions

A distribution describes what values a random variable takes and how often. Even noise with the same mean changes the stability of an optimization method depending on whether it is Gaussian or heavy-tailed.

For example, absolute loss may be more robust than squared loss for data with many outliers.

Expectation and variance

Expectation is the long-run average:

$$\mathbb{E}[X].$$

Variance is fluctuation around the mean:

$$\mathrm{Var}(X)=\mathbb{E}\left[(X-\mathbb{E}[X])^2\right].$$

Stochastic optimization usually minimizes an expected objective:

$$\min_x \mathbb{E}_{\xi}[F(x,\xi)].$$

Sampling

If the expectation is not known exactly, approximate it with a sample mean:

$$\mathbb{E}_{\xi}[F(x,\xi)]\approx \frac{1}{N}\sum_{i=1}^{N}F(x,\xi_i).$$

SGD uses a minibatch sample gradient rather than the gradient over all data. Its iterations are noisy as a result, but the computational cost is low.

Regression

Regression estimates a relationship between inputs and outputs:

$$\min_{\theta}\sum_{i=1}^{n}(y_i-f_\theta(x_i))^2.$$

From an optimization perspective, the parameter $\theta$ is the decision variable and the loss is the objective function. In expensive optimization, a regression model may also serve as a surrogate model.

Connections to the existing probability documents

• Random variables and distributions are covered in more detail in Probability Spaces and Random Variables.
• For expectation and variance, see Expectation, Moments, and Characteristic Functions.
• Sampling and the CLT connect to Law of Large Numbers, Central Limit Theorem, and Stability.

Next: Engineering Modeling