Incremental Stochastic Subgradient Algorithms for Convex Optimization

This paper studies the effect of stochastic errors on two constrained incremental subgradient algorithms. The incremental subgradient algorithms are viewed as decentralized network optimization algorithms as applied to minimize a sum of functions, when each component function is known only to a particular agent of a distributed network. First, the standard cyclic incremental subgradient algorithm is studied. In this, the agents form a ring structure and pass the iterate in a cycle. When there are stochastic errors in the subgradient evaluations, sufficient conditions on the moments of the stochastic errors are obtained that guarantee almost sure convergence when a diminishing step-size is used. In addition, almost sure bounds on the algorithm's performance with a constant step-size are also obtained. Next, the Markov randomized incremental subgradient method is studied. This is a noncyclic version of the incremental algorithm where the sequence of computing agents is modeled as a time nonhomogeneous Markov chain. Such a model is appropriate for mobile networks, as the network topology changes across time in these networks. Convergence results and error bounds for the Markov randomized method in the presence of stochastic errors for diminishing and constant step-sizes are obtained.

• Publication year

  2008

• Venue

  SIAM Journal on Optimization

• Publication date

  2008-06-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/080726380arXiv 0806.1092
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The effect of deterministic noise in subgradient methods

  2010cited by this paper
• Convergence Speed in Distributed Consensus and Averaging

  2009cited by this paper
• Distributed Subgradient Methods for Multi-Agent Optimization

  2009cited by this paper
• Computation as estimation: Estimation-theoretic IC design improves robustness and reduces power consumption

  2008cited by this paper
• Distributed and Recursive Parameter Estimation in Parametrized Linear State-Space Models

  2008cited by this paper
• Constrained Consensus and Optimization in Multi-Agent Networks

  2008cited by this paper
• Distributed average consensus with least-mean-square deviation

  2007cited by this paper
• Hilbert-Valued Perturbed Subgradient Algorithms

  2007cited by this paper
• Stochastic Incremental Gradient Descent for Estimation in Sensor Networks

  2007cited by this paper
• On distributed averaging algorithms and quantization effects

  2007cited by this paper
• A simple peer-to-peer algorithm for distributed optimization in sensor networks

  2007cited by this paper
• A Convergent Incremental Gradient Method with a Constant Step Size

  2007cited by this paper
• Joint congestion control, routing, and MAC for stability and fairness in wireless networks

  2006cited by this paper
• Approximate distributed Kalman filtering in sensor networks with quantifiable performance

  2005cited by this paper
• Quantized incremental algorithms for distributed optimization

  2005cited by this paper
• Distributed learning in wireless sensor networks

  2005cited by this paper
• Coordination of Groups of Mobile Autonomous Agents

  2004cited by this paper
• Convex Analysis and Optimization

  2003cited by this paper
• Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization

  2003cited by this paper
• Coordination of groups of mobile autonomous agents using nearest neighbor rules

  2002cited by this paper
• Convergen e Rate of In remental Subgradient Algorithms

  2000cited by this paper
• Gradient Convergence in Gradient methods with Errors

  1999cited by this paper
• Incremental subgradient methods for nondifferentiable optimization

  1999cited by this paper
• Optimization flow control—I: basic algorithm and convergence

  1999cited by this paper
• Asynchronous Stochastic Approximations

  1998cited by this paper
• Incremental Gradient Algorithms with Stepsizes Bounded Away from Zero

  1998cited by this paper
• Error Stability Properties of Generalized Gradient-Type Algorithms

  1998cited by this paper
• Analysis of an approximate gradient projection method with applications to the backpropagation algorithm

  1994cited by this paper
• Convergence properties of backpropagation for neural nets via theory of stochastic gradient methods. Part 1

  1994cited by this paper
• Parallel and distributed computation

  1989cited by this paper
• Introduction to optimization

  1987cited by this paper
• Asymptotic agreement and convergence of asynchronous stochastic algorithms

  1986cited by this paper
• Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms

  1984cited by this paper
• Problems in decentralized decision making and computation

  1984cited by this paper
• Convergence and asymptotic agreement in distributed decision problems

  1982cited by this paper
• wchastic. approximation methods for constrained and unconstrained systems

  1978cited by this paper
• Stochastic Programming Methods

  1976cited by this paper
• Stochastic Estimation of the Maximum of a Regression Function

  1952cited by this paper
• A Stochastic Approximation Method

  1951cited by this paper
• and as an in

  year unknowncited by this paper

• Distributed Optimization for Uncertain Euler-Lagrange Systems with Inequality Constraints

  2025cites this paper
• Non-Stationary Gradient Descent for Optimal Auto-Scaling in Serverless Platforms

  2025cites this paper
• Airflow Angles Estimation-Based Finite-Time Adaptive Neural Control for Aircraft at High-Angle-of-Attack Maneuvers

  2025cites this paper
• Robust Neural Dynamics for Distributed Time-Varying Optimization With Application to Multi-Robot Systems

  2025cites this paper
• Base Station Beam Scheduling for mmWave Networks With Full-Frequency Reuse

  2025cites this paper
• Primal-Dual Strategy (PDS) for Composite Optimization Over Directed graphs

  2024cites this paper
• Difference Between Cyclic and Distributed Approach in Stochastic Optimization for Multi-agent System

  2024cites this paper
• Stochastic optimization with arbitrary recurrent data sampling

  2024cites this paper
• Distributed Asynchronous Constrained Output Formation Optimal Tracking for Multiagent Systems With Intermittent Communications

  2024cites this paper
• The Entrapment Problem in Random Walk Decentralized Learning

  2024cites this paper
• Valid: a Validated Algorithm for Learning in Decentralized Networks with Possible Adversarial Presence

  2024cites this paper
• Lifelong Learning of Video Diffusion Models From a Single Video Stream

  2024cites this paper
• On the Decentralized Stochastic Gradient Descent With Markov Chain Sampling

  2023cites this paper
• On the Convergence of Stochastic Gradient Descent in Low-precision Number Formats

  2023cites this paper
• Distributed Stochastic Optimization with Gradient Tracking over Time- Varying Directed Networks

  2023cites this paper
• Finite-Time Analysis of Markov Gradient Descent

  2023influential citation
• A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning

  2023cites this paper
• Accelerating Level-Value Adjustment for the Polyak Stepsize

  2023cites this paper
• Mobilizing Personalized Federated Learning via Random Walk Stochastic ADMM

  2023cites this paper
• Finite-time convergence rates of distributed local stochastic approximation

  2023cites this paper
• Mobilizing Personalized Federated Learning in Infrastructure-Less and Heterogeneous Environments via Random Walk Stochastic ADMM

  2023cites this paper
• Distributed Nash equilibrium seeking over strongly connected switching networks

  2023cites this paper
• A sequential quadratic programming method for nonsmooth stochastic optimization with upper-C^2 objective

  2023cites this paper
• Stochastic subgradient algorithm for nonsmooth nonconvex optimization

  2023cites this paper
• Incremental quasi-Newton algorithms for solving a nonconvex, nonsmooth, finite-sum optimization problem

  2022cites this paper
• Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradients

  2022cites this paper
• Adaptive Random Walk Gradient Descent for Decentralized Optimization

  2022influential citation
• A principled framework for the design and analysis of token algorithms

  2022cites this paper
• Distributed Algorithm for Continuous-Type Bayesian Nash Equilibrium in Subnetwork Zero-Sum Games

  2022cites this paper
• Adapting to Mixing Time in Stochastic Optimization with Markovian Data

  2022cites this paper
• Introduction to Federated Learning

  2022cites this paper
• Adaptive algorithm for dependent infrastructure network restoration in an imperfect information sharing environment

  2022cites this paper
• Efficiency Ordering of Stochastic Gradient Descent

  2022cites this paper
• An indefinite proximal subgradient-based algorithm for nonsmooth composite optimization

  2022cites this paper
• Stability and Generalization for Markov Chain Stochastic Gradient Methods

  2022cites this paper
• A Multi-Token Coordinate Descent Method for Vertical Federated Learning

  2022cites this paper
• Inexact stochastic subgradient projection method for stochastic equilibrium problems with nonmonotone bifunctions: application to expected risk minimization in machine learning

  2021cites this paper
• Stochastic approximation with discontinuous dynamics, differential inclusions, and applications

  2021cites this paper
• A Markovian Incremental Stochastic Subgradient Algorithm

  2021influential citation
• A new Zeno-free event-triggered scheme for robust distributed optimal coordination

  2021cites this paper
• Distributed cooperative optimization for multiple heterogeneous Euler-Lagrangian systems under global equality and inequality constraints

  2021cites this paper
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise

  2021cites this paper
• Distributed Optimization

  2021cites this paper
• A Multi-Scale Method for Distributed Convex Optimization with Constraints

  2021cites this paper
• Continuous-time distributed optimization with strictly pseudoconvex objective functions

  2021cites this paper
• Finite-Time Convergence Rates of Decentralized Stochastic Approximation With Applications in Multi-Agent and Multi-Task Learning

  2020cites this paper
• Computation-Efficient Distributed Algorithm for Convex Optimization Over Time-Varying Networks With Limited Bandwidth Communication

  2020cites this paper
• Distributed Linear Estimation Via a Roaming Token

  2020cites this paper
• Path-based incremental target level algorithm on Riemannian manifolds

  2020cites this paper
• Accelerated Convergence Algorithm for Distributed Constrained Optimization under Time-Varying General Directed Graphs

  2020cites this paper
• Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning

  2020cites this paper
• Achieving Linear Convergence of Distributed Optimization over Time-Varying Directed Networks with Column-Stochastic Weight Matrices

  2020cites this paper
• Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms

  2020cites this paper
• Randomized optimal consensus of multiagent systems based on a novel intermittent projected subgradient algorithm

  2020cites this paper
• Stochastic Fixed Point Optimization Algorithm for Classifier Ensemble

  2020cites this paper
• Privacy Amplification by Decentralization

  2020influential citation
• Distributed Average Tracking in Distributed Convex Optimization

  2020cites this paper
• Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness

  2020cites this paper
• Operator Sliding and Decentralized Optimization

  2020cites this paper
• A Sequential Gradient-Based Multiple Access for Distributed Learning over Fading Channels

  2019cites this paper
• Random Walk Gradient Descent for Decentralized Learning on Graphs

  2019cites this paper
• Walk Proximal Gradient: An Energy-Efficient Algorithm for Consensus Optimization

  2019cites this paper
• Recent advances in optimization and game theoretic control for networked systems

  2019cites this paper
• Incremental Methods for Weakly Convex Optimization

  2019cites this paper
• A Distributed Hybrid Event-Time-Driven Scheme for Optimization Over Sensor Networks

  2019cites this paper
• Multi-cluster distributed optimization via random sleep strategy

  2019cites this paper
• Decentralized Markov Chain Gradient Descent

  2019cites this paper
• On the Time-Varying Distributions of Online Stochastic Optimization

  2019cites this paper
• Communication Efficient Distributed Estimation Over Directed Random Graphs

  2019cites this paper
• Nash equilibrium computation in two-network zero-sum games: An incremental algorithm

  2019cites this paper
• A General Framework of Exact Primal-Dual First-Order Algorithms for Distributed Optimization ∗

  2019cites this paper
• Clustering with Distributed Data

  2019cites this paper
• Online Learning Over Dynamic Graphs via Distributed Proximal Gradient Algorithm

  2019cites this paper
• Hybrid Event-Time-Driven Communication and Network Optimization

  2019cites this paper
• On Analog Gradient Descent Learning Over Multiple Access Fading Channels

  2019cites this paper
• Parallel Stochastic Optimization Framework for Large-Scale Non-Convex Stochastic Problems

  2019cites this paper
• Communication efficient distributed weighted non-linear least squares estimation

  2018cites this paper
• On Markov Chain Gradient Descent

  2018influential citation
• Time Varying optimization via Inexact Proximal Online Gradient Descent

  2018cites this paper
• Distributed zero‐gradient‐sum algorithm for convex optimization with time‐varying communication delays and switching networks

  2018cites this paper
• Online Learning With Inexact Proximal Online Gradient Descent Algorithms

  2018cites this paper
• Linearly Convergent Asynchronous Distributed ADMM via Markov Sampling.

  2018cites this paper
• Geometrical convergence rate for distributed optimization with time-varying directed graphs and uncoordinated step-sizes

  2018cites this paper
• Exponential convergence rate of distributed optimisation for multi‐agent systems with constraints set over a directed graph

  2018cites this paper
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

  2018cites this paper
• Consensus in opinion dynamics as a repeated game

  2018cites this paper
• Markov chain block coordinate descent

  2018cites this paper
• Decentralized Asynchronous Stochastic Gradient Descent: Convergence Rate Analysis

  2018cites this paper
• Distributed optimization for multi-agent systems with constraints set and communication time-delay over a directed graph

  2018cites this paper
• CREDO: A Communication-Efficient Distributed Estimation Algorithm

  2018cites this paper
• String-averaging incremental stochastic subgradient algorithms

  2018influential citation
• Private Optimization on Networks

  2018cites this paper
• Privacy-Preserving Distributed Learning via Obfuscated Stochastic Gradients

  2018cites this paper
• Price Convergence under a Probabilistic Double Auction

  2018cites this paper
• A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

  2018cites this paper
• An Incremental Subgradient Method on Riemannian Manifolds

  2018cites this paper
• Price Convergence under a Probabilistic Double Auction

  2018influential citation
• A fixed-time optimal consensus algorithm over undirected networks

  2018cites this paper
• Local Prediction for Enhanced Convergence of Distributed Optimization Algorithms

  2018cites this paper
• Decentralized consensus optimization and resource allocation

  2018cites this paper