论文标题
与机会性无线调度的收敛时间相反的结果
A Converse Result on Convergence Time for Opportunistic Wireless Scheduling
论文作者
论文摘要
本文证明了多用户无线系统（包括多个访问和广播系统）的随机网络实用程序最大化的不可能结果。每次插槽访问点都会观察到每个用户的当前频道状态，并有机会选择传输速率。假定通道状态向量是独立的，并且具有相同的分布，并具有未知的概率分布。目标是学会随着时间的推移做出决策，以最大程度地提高每个用户运行时间平均传输速率的凹入效用功能。最近，结果表明，随机的Frank-Wolfe算法将$ O（\ log（t）/t）$的错误收敛到实用程序，其中$ o（\ log（t）/t）$，其中$ t $是算法运行的时间。现有的$ω（1/t）$ converse是已知的。当前纸将交谈提高到$ω（\ log（t）/t）$，与已知的可实现结果相匹配。它通过构建一个特定的（简单）系统来做到这一点，没有算法可以实现更好的性能。该证明将机会性调度问题的新颖降低用于从独立和分布的样本中估算Bernoulli概率$ p $的问题。在此过程中，我们将遗憾的是伯诺利估计的遗憾，以表明，对于任何估计器，估计器的表现较差的估计值$ p \ in [0,1] $的集合至少$ 1/8 $。
This paper proves an impossibility result for stochastic network utility maximization for multi-user wireless systems, including multiple access and broadcast systems. Every time slot an access point observes the current channel states for each user and opportunistically selects a vector of transmission rates. Channel state vectors are assumed to be independent and identically distributed with an unknown probability distribution. The goal is to learn to make decisions over time that maximize a concave utility function of the running time average transmission rate of each user. Recently it was shown that a stochastic Frank-Wolfe algorithm converges to utility-optimality with an error of $O(\log(T)/T)$, where $T$ is the time the algorithm has been running. An existing $Ω(1/T)$ converse is known. The current paper improves the converse to $Ω(\log(T)/T)$, which matches the known achievability result. It does this by constructing a particular (simple) system for which no algorithm can achieve a better performance. The proof uses a novel reduction of the opportunistic scheduling problem to a problem of estimating a Bernoulli probability $p$ from independent and identically distributed samples. Along the way we refine a regret bound for Bernoulli estimation to show that, for any sequence of estimators, the set of values $p \in [0,1]$ under which the estimators perform poorly has measure at least $1/8$.
