Parallel algorithms and probability of large deviation for stochastic optimization problems

Understand

We consider convex stochastic optimization problems under different assumptions on the properties of available stochastic subgradient.

• It is known that, if the value of the objective function is available, one can obtain, in parallel, several independent approximate solutions in terms of the objective residual expectation.
• Then, choosing the solution with the minimum function value, one can control the probability of large deviation of the objective residual.
• On the contrary, in this short paper, we address the situation, when the value of the objective function is unavailable or is too expensive to calculate.