Gradient and Projection Free Distributed Online Min-Max Resource Optimization
This addresses resource optimization in large-scale distributed networks, such as bandwidth allocation in online machine learning, but is incremental as it builds on existing online optimization strategies.
The paper tackles distributed online min-max resource allocation without prior knowledge of time-varying cost functions, proposing a gradient- and projection-free algorithm (DORA) that reduces computation overhead and demonstrates performance advantages in reducing wall-clock time over existing methods.
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.