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 ?


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).

| cite | improve this answer | |
  • $\begingroup$ Great answer! I think I overlooked the fact that min function just returns a vector. Still new here but will upvote when I have enough points :) Thanks anyways $\endgroup$ – Ravi Feb 27 '14 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.