Parallel algorithms and probability of large deviation for stochastic convex optimization problems

DOI10.1134/S1995423918010044MaRDI QIDQ4636855zbMATH OpenOpenAlexWikidataFDO

Authors Pavel Dvurechensky, A. A. Lagunovskaya, Alexander V. Gasnikov

Publication date 20 April 2018

Published in Numerical Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.01830

zbMATH Keywords

mirror descentparallel algorithmprobability of large deviationstochastic convex optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Convex programming (90C25)

Abstract: 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. Under "`light-tail"' assumption for stochastic subgradient and in general case with moderate large deviation probability, we show that parallelization combined with averaging gives bounds for probability of large deviation similar to a serial method. Thus, in these cases, one can benefit from parallel computations and reduce the computational time without loss in the solution quality.

Recommendations

• Parallel subgradient methods for convex optimization.
• Lower bounds for parallel and randomized convex optimization
• Stochastic approximation algorithms for parallel and distributed processing
• On the rates of convergence of parallelized averaged stochastic gradient algorithms
• Parallel stochastic Newton method

Cited in

(7)

• Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
• Joint robustness on noise and Lyapunov functions for parallel stochastic approximation algorithms
• Parallel distributed-memory simplex for large-scale stochastic LP problems
• scientific article; zbMATH DE number 761259 (Why is no real title available?)
• Lower bounds for parallel and randomized convex optimization
• An accelerated method for derivative-free smooth stochastic convex optimization
• Composite optimization for the resource allocation problem

This page was built for publication: Parallel algorithms and probability of large deviation for stochastic convex optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636855)