# Gradient and Projection Free Distributed Online Min-Max Resource Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 7 Dec 2021.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Federated Learning over Wireless Fading Channels](https://mlsanity.com/paper/1907.09769/) (2019)
- [Non-stationary Stochastic Optimization](https://mlsanity.com/paper/1307.5449/) (2013)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Federated Learning for Wireless Communications: Motivation, Opportunities and Challenges](https://mlsanity.com/paper/1908.06847/) (2019)
- [Improved Dynamic Regret for Non-degenerate Functions](https://mlsanity.com/paper/1608.03933/) (2016)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Gradient-free Online Learning in Games with Delayed Rewards](https://mlsanity.com/paper/2006.10911/) (2020)
- [A Distributed Online Convex Optimization Algorithm with Improved Dynamic Regret](https://mlsanity.com/paper/1911.05050/) (2019)
- [Online non-convex optimization with imperfect feedback](https://mlsanity.com/paper/2010.08496/) (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 Online Convex Optimization with an Aggregative Variable](https://mlsanity.com/paper/2007.06844/) (2020)
- [Zeroth-order non-convex learning via hierarchical dual averaging](https://mlsanity.com/paper/2109.05829/) (2021)
- [A duality-based approach for distributed min-max optimization](https://mlsanity.com/paper/1611.09168/) (2016)
- [Online learning for min-max discrete problems](https://mlsanity.com/paper/1907.05944/) (2019)

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

- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)

## Abstract (arXiv)

We consider distributed online min-max resource allocation with a set of parallel agents and a parameter server. Our goal is to minimize the pointwise maximum over a set of time-varying and decreasing cost functions, without a priori information about these functions. We propose a novel online algorithm, termed Distributed Online resource Re-Allocation (DORA), where non-stragglers learn to relinquish resource and share resource with stragglers. A notable feature of DORA is that it does not require gradient calculation or projection operation, unlike most existing online optimization strategies. This allows it to substantially reduce the computation overhead in large-scale and distributed networks. We analyze the worst-case performance of DORA and derive an upper bound on its dynamic regret for non-convex functions. We further consider an application to the bandwidth allocation problem in distributed online machine learning. Our numerical study demonstrates the efficacy of the proposed solution and its performance advantage over gradient- and/or projection-based resource allocation algorithms in reducing wall-clock time.