Can I read Optimal Convergence and Adaptation for Utility Optimal Opportunistic Scheduling on EtoBox?

Optimal Convergence and Adaptation for Utility Optimal Opportunistic Scheduling by Neely, Michael J. is a scholarly article available to read on EtoBox.

What is Optimal Convergence and Adaptation for Utility Optimal Opportunistic Scheduling about?

This paper considers the fundamental convergence time for opportunistic scheduling over time-varying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within $\epsilon$ of optimality, for any desired $\epsilon>0$, with convergence and adaptation times of $O(1/\epsilon^2)$. This paper shows that if the utility function is concave and smooth, then $O(\log(1/\epsilon)/\epsilon)$ convergence time is possible via an existing stochastic variation on the Frank-Wolfe algorithm, called the RUN algorithm. Next, a converse result is proven to show it is impossible for any algorithm to have convergence time better than $O(1/\epsilon)$, provided the algorithm has no a-priori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic Frank-Wolfe with a fixed stepsize yields improved $O(1/\epsilon^2)$ adaptation time, but convergence time increases to $O(1/\epsilon^2)$, similar to exi

Author

Neely, Michael J.

Published

2017

Language

EN