Objective function for stochastic optimization

Question

Stochastic Optimization problems in general deals with random variables in the 'loss function'.

Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we usually have,

\begin{equation} \min_{x} \parallel Ax-b \parallel_2^2 \end{equation}

With some uncertainty or possible variations in the data matrix A, it is natural to use the expected value of the objective function $\parallel Ax-b \parallel_2^2$:

\begin{equation} \min_{x} E\left( \parallel Ax-b \parallel_2^2 \right) \end{equation}

How is the above objective function different from the following objective function- \begin{equation} E\left( \min_{x} \parallel Ax-b \parallel_2^2 \right) \end{equation}

Certainly, for the basic objective function, first objective has a closed form compared the second objective. But, why aren't we dealing with the second objective in general ?

Which is more precise ?

Answer 1

First, notice that the first objective is a minimization problem, who's solution is a vector $x$, while the second is merely a number.

The objective $\min_{x} E\left( \parallel Ax-b \parallel_2^2 \right)$ asks for the vector $x$ which best explains the data.

If $A$ is stochastic, it still looks for the best $x$ which, on average, is the best one.

The lower objective asks for "What's the expected error of the best $x$, in hindsight ", i.e. after we fix $A$, take the minimum over all $x$'s, and ask what's the error. (more formally, for different $A$ values there are different "best" $x$s, so the each time take the best one for computing the error).

Since we are usually interested in finding the feature vector $x$ which explains the data, and not the expected error of the best $x$ after $A$ is fixed, the first stochastic objective makes more sense. The only reason I can think of as why would someone be interested in the second is for competitive-analysis like proofs (i.e. what's the gap between the best $x$ prior to knowing $A$ and the best one afterwards).