2019/11/17 by Eduard Gorbunov, Gorbunov, Eduard, Darina Dvinskikh +3
Computer Science · Engineering · #Distributed Control Multi-Agent Systems #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1911.07363
openalex publication_date 2019/11/17 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We consider stochastic convex optimization problems with affine constraints\nand develop several methods using either primal or dual approach to solve it.\nIn the primal case, we use a special penalization technique to make the initial\nproblem more convenient for using optimization methods. We propose algorithms\nto solve it based on Similar Triangles Method with Inexact Proximal Step for\nthe convex smooth and strongly convex smooth objective functions and methods\nbased on Gradient Sliding algorithm to solve the same problems in the\nnon-smooth case. We prove the convergence guarantees in the smooth convex case\nwith deterministic first-order oracle.\n We propose and analyze three novel methods to handle stochastic convex\noptimization problems with affine constraints: SPDSTM, R-RRMA-AC-SA2, and\nSSTMsc. All methods use stochastic dual oracle. SPDSTM is the stochastic\nprimal-dual modification of STM and it is applied for the dual problem when the\nprimal functional is strongly convex and Lipschitz continuous on some ball. We\nextend the result from Dvinskikh & Gasnikov (2019) for this method to the case\nwhen only biased stochastic oracle is available. R-RRMA-AC-SA2 is an\naccelerated stochastic method based on the restarts of RRMA-AC-SA2 from\nFoster et al. (2019) and SSTMsc is just stochastic STM for strongly convex\nproblems. Both methods are applied to the dual problem when the primal\nfunctional is strongly convex, smooth, and Lipschitz continuous on some ball\nand use stochastic dual first-order oracle. We develop convergence analysis for\nthese methods for unbiased and biased oracles respectively.\n Finally, we apply all the aforementioned results and approaches to solve the\ndecentralized distributed optimization problem and discuss the optimality of\nthe obtained results in terms of communication rounds and the number of oracle\ncalls per node.\n