A Markovian Incremental Stochastic Subgradient Algorithm

• 成果类型: Article
• 署名作者: Massambone, Rafael; Costa, Eduardo Fontoura; Helou, Elias Salomao
• 署名单位: Universidade de Sao Paulo
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3137274
• 发表日期: 2023
• 页码: 124-139
• 关键词: Incremental subgradient algorithms; optimization; optimization algorithms; randomized algorithms

摘要

In this article, a stochastic incremental subgradient algorithm for the minimization of a sum of convex functions is introduced. The method sequentially uses partial subgradient information, and the sequence of partial subgradients is determined by a general Markov chain. This makes it suitable to be used in networks, where the path of information flow is stochastically selected. We prove convergence of the algorithm to a weighted objective function, where the weights are given by the Cesaro limiting probability distribution of the Markov chain. Unlike previous works in the literature, the Cesaro limiting distribution is general (not necessarily uniform), allowing for general weighted objective functions and flexibility in the method.