# Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 55 references that are in the map.
- First posted on arXiv 24 Sep 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [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)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [Online Learning with Inexact Proximal Online Gradient Descent Algorithms](https://mlsanity.com/paper/1806.00202/) (2018)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Multi-scale exploration of convex functions and bandit convex optimization](https://mlsanity.com/paper/1507.06580/) (2015)
- [A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control](https://mlsanity.com/paper/2006.10820/) (2020)
- [Zeroth Order Nonconvex Multi-Agent Optimization over Networks](https://mlsanity.com/paper/1710.09997/) (2017)
- [Zeroth-Order Algorithms for Stochastic Distributed Nonconvex Optimization](https://mlsanity.com/paper/2106.02958/) (2021)
- [Distributed Bandit Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1912.03719/) (2019)
- [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)
- [Distributed Randomized Gradient-Free Mirror Descent Algorithm for Constrained Optimization](https://mlsanity.com/paper/1903.04157/) (2019)
- [Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems](https://mlsanity.com/paper/1812.00613/) (2018)
- [An Incentive-Based Online Optimization Framework for Distribution Grids](https://mlsanity.com/paper/1705.01482/) (2017)
- [Linear Convergence of First- and Zeroth-Order Primal-Dual Algorithms for Distributed Nonconvex Optimization](https://mlsanity.com/paper/1912.12110/) (2019)
- [Quantized Distributed Online Projection-free Convex Optimization](https://mlsanity.com/paper/2302.13559/) (2023)
- [Randomized Gradient-Free Distributed Online Optimization via a Dynamic Regret Analysis](https://mlsanity.com/paper/1903.07106/) (2019)
- [Asynchronous Zeroth-Order Distributed Optimization with Residual Feedback](https://mlsanity.com/paper/2109.13866/) (2021)

## Abstract (arXiv)

This paper considers the distributed online bandit optimization problem with nonconvex loss functions over a time-varying digraph. This problem can be viewed as a repeated game between a group of online players and an adversary. At each round, each player selects a decision from the constraint set, and then the adversary assigns an arbitrary, possibly nonconvex, loss function to this player. Only the loss value at the current round, rather than the entire loss function or any other information (e.g. gradient), is privately revealed to the player. Players aim to minimize a sequence of global loss functions, which are the sum of local losses. We observe that traditional multi-point bandit algorithms are unsuitable for online optimization, where the data for the loss function are not all a priori, while the one-point bandit algorithms suffer from poor regret guarantees. To address these issues, we propose a novel one-point residual feedback distributed online algorithm. This algorithm estimates the gradient using residuals from two points, effectively reducing the regret bound while maintaining O(1) sampling complexity per iteration. We employ a rigorous metric, dynamic regret, to evaluate the algorithm's performance. By appropriately selecting the step size and smoothing parameters, we demonstrate that the expected dynamic regret of our algorithm is comparable to existing algorithms that use two-point feedback, provided the deviation in the objective function sequence and the path length of the minimization grows sublinearly. Finally, we validate the effectiveness of the proposed algorithm through numerical simulations.