  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 $\Omega(1/T)$ converse is known. The current paper improves the
converse to $\Omega(\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$.
