A Markovian Incremental Stochastic Subgradient Algorithm

DOI10.1109/TAC.2021.3137274MaRDI QIDQ6137490zbMATH OpenOpenAlexFDO

Authors Rafael Massambone, Eduardo Fontoura Costa, Elias Salomão Helou

Publication date 4 September 2023

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Systems theory; control (93-XX)

Abstract: 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 Ces`aro limiting probability distribution of the Markov chain. Unlike previous works in the literature, the Ces`aro limiting distribution is general (not necessarily uniform), allowing for general weighted objective functions and flexibility in the method.

Recommendations

• Incremental stochastic subgradient algorithms for convex optimization
• Stochastic subgradient method for quasi-convex optimization problems
• Incremental subgradient methods for nondifferentiable optimization
• Inexact subgradient methods with applications in stochastic programming
• An optimal randomized incremental gradient method
• scientific article; zbMATH DE number 3887445
• A multistep stochastic ϵ-subgradient method of minimizing a convex function
• A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
• Incremental subgradient algorithms with dynamic step sizes for separable convex optimizations

Cited in

(2)

• Accelerated proximal gradient method for systems with unknown structure using Volterra series
• Global optimization for first order Markov random fields with submodular priors

This page was built for publication: A Markovian Incremental Stochastic Subgradient Algorithm

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