2017/01/07 by Pavel Dvurechensky, Dvurechensky, Pavel, Alexander Gasnikov +3
Computer Science · Decision Sciences · Engineering · Mathematics · #90C15 #90C25 #Complexity and Algorithms in Graphs #FOS: Mathematics #G.1.6 #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1701.01830
openalex publication_date 2017/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider convex stochastic optimization problems under different\nassumptions on the properties of available stochastic subgradient. It is known\nthat, if the value of the objective function is available, one can obtain, in\nparallel, several independent approximate solutions in terms of the objective\nresidual expectation. Then, choosing the solution with the minimum function\nvalue, one can control the probability of large deviation of the objective\nresidual. On the contrary, in this short paper, we address the situation, when\nthe value of the objective function is unavailable or is too expensive to\ncalculate. Under "`light-tail"' assumption for stochastic subgradient and in\ngeneral case with moderate large deviation probability, we show that\nparallelization combined with averaging gives bounds for probability of large\ndeviation similar to a serial method. Thus, in these cases, one can benefit\nfrom parallel computations and reduce the computational time without loss in\nthe solution quality.\n