# The Power of Online Learning in Stochastic Network Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2014.

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

- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [A Brain-Inspired Low-Dimensional Computing Classifier for Inference on Tiny Devices](https://mlsanity.com/paper/2203.04894/) (2022)
- [Learning-Assisted Algorithm Unrolling for Online Optimization with Budget Constraints](https://mlsanity.com/paper/2212.01689/) (2022)

## Abstract (arXiv)

In this paper, we investigate the power of online learning in stochastic network optimization with unknown system statistics it a priori. We are interested in understanding how information and learning can be efficiently incorporated into system control techniques, and what are the fundamental benefits of doing so. We propose two Online Learning-Aided Control techniques, mathttOLAC and mathttOLAC2, that explicitly utilize the past system information in current system control via a learning procedure called dual learning. We prove strong performance guarantees of the proposed algorithms: mathttOLAC and mathttOLAC2 achieve the near-optimal [O(ε), O([log(1/ε)]2)] utility-delay tradeoff and mathttOLAC2 possesses an O(ε-2/3) convergence time. mathttOLAC and mathttOLAC2 are probably the first algorithms that simultaneously possess explicit near-optimal delay guarantee and sub-linear convergence time. Simulation results also confirm the superior performance of the proposed algorithms in practice. To the best of our knowledge, our attempt is the first to explicitly incorporate online learning into stochastic network optimization and to demonstrate its power in both theory and practice.