# Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization

arXiv: https://arxiv.org/abs/2404.13669 · HTML: https://mlsanity.com/paper/2404.13669/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 33 references that are in the map.
- First posted on arXiv 21 Apr 2024.

## Builds on (most cited first, 16 of 16)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Data-Driven Robust Optimization](https://mlsanity.com/paper/1401.0212/) (2013)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization](https://mlsanity.com/paper/1709.02490/) (2017)
- [Adaptive Sequential Stochastic Optimization](https://mlsanity.com/paper/1610.01970/) (2016)
- [Distributed Optimization for Smart Cyber-Physical Networks](https://mlsanity.com/paper/1906.10760/) (2019)
- [Distributed Personalized Gradient Tracking with Convex Parametric Models](https://mlsanity.com/paper/2008.04363/) (2020)
- [Distributed Coupled Multi-Agent Stochastic Optimization](https://mlsanity.com/paper/1712.08817/) (2017)
- [On the solution of stochastic optimization and variational problems in imperfect information regimes](https://mlsanity.com/paper/1402.1457/) (2014)
- [On the resolution of misspecified convex optimization and monotone variational inequality problems](https://mlsanity.com/paper/1408.5532/) (2014)
- [Initialization-free Distributed Algorithms for Optimal Resource Allocation with Feasibility Constraints and its Application to Economic Dispatch of Power Systems](https://mlsanity.com/paper/1510.08579/) (2015)
- [On the analysis of inexact augmented Lagrangian schemes for misspecified conic convex programs](https://mlsanity.com/paper/1608.01879/) (2016)
- [Distributed Stochastic Optimization under Imperfect Information](https://mlsanity.com/paper/1509.03925/) (2015)
- [Stochastic Adaptive Linear Quadratic Differential Games](https://mlsanity.com/paper/2204.08869/) (2022)
- [A Unified Framework for Continuous-time Unconstrained Distributed Optimization](https://mlsanity.com/paper/2211.04358/) (2022)
- [Distributed Control for Spatial Self-Organization of Multi-Agent Swarms](https://mlsanity.com/paper/1705.03109/) (2017)

## Abstract (arXiv)

We consider an n agents distributed optimization problem with imperfect information characterized in a parametric sense, where the unknown parameter can be solved by a distinct distributed parameter learning problem. Though each agent only has access to its local parameter learning and computational problem, they mean to collaboratively minimize the average of their local cost functions. To address the special optimization problem, we propose a coupled distributed stochastic approximation algorithm, in which every agent updates the current beliefs of its unknown parameter and decision variable by stochastic approximation method; and then averages the beliefs and decision variables of its neighbors over network in consensus protocol. Our interest lies in the convergence analysis of this algorithm. We quantitatively characterize the factors that affect the algorithm performance, and prove that the mean-squared error of the decision variable is bounded by O(frac1nk)+Oleft(frac1√n(1-ρw)right)frac1k1.5+Obig(frac1(1-ρw)2 big)frac1k2, where k is the iteration count and (1-ρw) is the spectral gap of the network weighted adjacency matrix. It reveals that the network connectivity characterized by (1-ρw) only influences the high order of convergence rate, while the domain rate still acts the same as the centralized algorithm. In addition, we analyze that the transient iteration needed for reaching its dominant rate O(frac1nk) is O(fracn(1-ρw)2). Numerical experiments are carried out to demonstrate the theoretical results by taking different CPUs as agents, which is more applicable to real-world distributed scenarios.