# An Online Convex Optimization Approach to Dynamic Network Resource Allocation

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jan 2017.

## Built on by (most cited first, 30 of 42)

- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Safe Online Convex Optimization with Unknown Linear Safety Constraints](https://mlsanity.com/paper/2111.07430/) (2021)
- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [Joint Online Learning and Decision-making via Dual Mirror Descent](https://mlsanity.com/paper/2104.09750/) (2021)
- [Online Caching with Optimistic Learning](https://mlsanity.com/paper/2202.10590/) (2022)
- [Online Learning under Adversarial Nonlinear Constraints](https://mlsanity.com/paper/2306.03655/) (2023)
- [Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries](https://mlsanity.com/paper/2504.00461/) (2025)
- [Online Sequential Decision-Making with Unknown Delays](https://mlsanity.com/paper/2402.07703/) (2024)
- [Lazy Lagrangians with Predictions for Online Learning](https://mlsanity.com/paper/2201.02890/) (2022)
- [Best of Many Worlds Guarantees for Online Learning with Knapsacks](https://mlsanity.com/paper/2202.13710/) (2022)
- [Online Learning for Traffic Routing under Unknown Preferences](https://mlsanity.com/paper/2203.17150/) (2022)
- [Online Caching with no Regret: Optimistic Learning via Recommendations](https://mlsanity.com/paper/2204.09345/) (2022)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Decentralized Multi-Task Stochastic Optimization With Compressed Communications](https://mlsanity.com/paper/2112.12373/) (2021)
- [Monotone Individual Fairness](https://mlsanity.com/paper/2403.06812/) (2024)
- [Delay-Tolerant Constrained OCO with Application to Network Resource Allocation](https://mlsanity.com/paper/2105.04005/) (2021)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Long-term Fairness For Real-time Decision Making: A Constrained Online Optimization Approach](https://mlsanity.com/paper/2401.02552/) (2024)
- [Risk-averse Learning with Non-Stationary Distributions](https://mlsanity.com/paper/2404.02988/) (2024)
- [Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint](https://mlsanity.com/paper/2412.10703/) (2024)
- [Online Optimization for Randomized Network Resource Allocation with Long-Term Constraints](https://mlsanity.com/paper/2305.15558/) (2023)
- [Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints](https://mlsanity.com/paper/2403.05786/) (2024)
- [Safety in the Face of Adversity: Achieving Zero Constraint Violation in Online Learning with Slowly Changing Constraints](https://mlsanity.com/paper/2505.00398/) (2025)
- [A Modular Algorithm for Non-Stationary Online Convex-Concave Optimization](https://mlsanity.com/paper/2509.07901/) (2025)
- [Penalised FTRL With Time-Varying Constraints](https://mlsanity.com/paper/2204.02197/) (2022)
- [No-regret learning for repeated non-cooperative games with lossy bandits](https://mlsanity.com/paper/2205.06968/) (2022)
- [Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization](https://mlsanity.com/paper/2205.09571/) (2022)

## Abstract (arXiv)

Existing approaches to online convex optimization (OCO) make sequential one-slot-ahead decisions, which lead to (possibly adversarial) losses that drive subsequent decision iterates. Their performance is evaluated by the so-called regret that measures the difference of losses between the online solution and the best yet fixed overall solution in hindsight. The present paper deals with online convex optimization involving adversarial loss functions and adversarial constraints, where the constraints are revealed after making decisions, and can be tolerable to instantaneous violations but must be satisfied in the long term. Performance of an online algorithm in this setting is assessed by: i) the difference of its losses relative to the best dynamic solution with one-slot-ahead information of the loss function and the constraint (that is here termed dynamic regret); and, ii) the accumulated amount of constraint violations (that is here termed dynamic fit). In this context, a modified online saddle-point (MOSP) scheme is developed, and proved to simultaneously yield sub-linear dynamic regret and fit, provided that the accumulated variations of per-slot minimizers and constraints are sub-linearly growing with time. MOSP is also applied to the dynamic network resource allocation task, and it is compared with the well-known stochastic dual gradient method. Under various scenarios, numerical experiments demonstrate the performance gain of MOSP relative to the state-of-the-art.