# Distributed Online Non-convex Optimization with Composite Regret

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 40 references that are in the map.
- First posted on arXiv 21 Sep 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Collaborative Deep Learning in Fixed Topology Networks](https://mlsanity.com/paper/1706.07880/) (2017)
- [On Nonconvex Decentralized Gradient Descent](https://mlsanity.com/paper/1608.05766/) (2016)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [Online Non-Convex Learning: Following the Perturbed Leader is Optimal](https://mlsanity.com/paper/1903.08110/) (2019)
- [DADAM: A Consensus-based Distributed Adaptive Gradient Method for Online Optimization](https://mlsanity.com/paper/1901.09109/) (2019)
- [Efficient Regret Minimization in Non-Convex Games](https://mlsanity.com/paper/1708.00075/) (2017)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Learning in Non-convex Games with an Optimization Oracle](https://mlsanity.com/paper/1810.07362/) (2018)
- [Balancing Communication and Computation in Distributed Optimization](https://mlsanity.com/paper/1709.02999/) (2017)
- [Online Distributed Optimization on Dynamic Networks](https://mlsanity.com/paper/1412.7215/) (2014)
- [A Distributed Online Convex Optimization Algorithm with Improved Dynamic Regret](https://mlsanity.com/paper/1911.05050/) (2019)
- [Distributed Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/1912.09705/) (2019)
- [Distributed Mirror Descent for Online Composite Optimization](https://mlsanity.com/paper/2004.00837/) (2020)
- [Distributed Online Optimization for Multi-Agent Networks with Coupled Inequality Constraints](https://mlsanity.com/paper/1805.05573/) (2018)
- [On Distributed Online Convex Optimization with Sublinear Dynamic Regret and Fit](https://mlsanity.com/paper/2001.03166/) (2020)
- [Distributed and Inexact Proximal Gradient Method for Online Convex Optimization](https://mlsanity.com/paper/2001.00870/) (2020)
- [Online convex optimization and no-regret learning: Algorithms, guarantees and applications](https://mlsanity.com/paper/1804.04529/) (2018)
- [Decentralized Online Learning: Take Benefits from Others' Data without Sharing Your Own to Track Global Trend](https://mlsanity.com/paper/1901.10593/) (2019)
- [Distributed Constrained Online Learning](https://mlsanity.com/paper/1903.06310/) (2019)
- [Decentralized Online Learning for Noncooperative Games in Dynamic Environments](https://mlsanity.com/paper/2105.06200/) (2021)
- [Decentralized Nash Equilibria Learning for Online Game with Bandit Feedback](https://mlsanity.com/paper/2204.09467/) (2022)
- [A Distributed Stochastic Gradient Tracking Method](https://mlsanity.com/paper/1803.07741/) (2018)
- [A Local Regret in Nonconvex Online Learning](https://mlsanity.com/paper/1811.05095/) (2018)
- [On the Sublinear Regret of Distributed Primal-Dual Algorithms for Online Constrained Optimization](https://mlsanity.com/paper/1705.11128/) (2017)

## Built on by (most cited first, 2 of 2)

- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [Differentially Private Online Federated Learning with Correlated Noise](https://mlsanity.com/paper/2403.16542/) (2024)

## Abstract (arXiv)

Regret has been widely adopted as the metric of choice for evaluating the performance of online optimization algorithms for distributed, multi-agent systems. However, data/model variations associated with agents can significantly impact decisions and requires consensus among agents. Moreover, most existing works have focused on developing approaches for (either strongly or non-strongly) convex losses, and very few results have been obtained regarding regret bounds in distributed online optimization for general non-convex losses. To address these two issues, we propose a novel composite regret with a new network regret-based metric to evaluate distributed online optimization algorithms. We concretely define static and dynamic forms of the composite regret. By leveraging the dynamic form of our composite regret, we develop a consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses, and it provably shows a sublinear behavior relating to a regularity term for the path variation of the optimizer. For general non-convex losses, we first shed light on the regret for the setting of distributed online non-convex learning based on recent advances such that no deterministic algorithm can achieve the sublinear regret. We then develop the distributed online non-convex optimization with composite regret (DINOCO) without access to the gradients, depending on an offline optimization oracle. DINOCO is shown to achieve sublinear regret; to our knowledge, this is the first regret bound for general distributed online non-convex learning.