We show that the \emph{stochastic gradient} bandit algorithm converges to a
\emph{globally optimal} policy at an $O(1/t)$ rate, even with a \emph{constant}
step size. Remarkably, global convergence of the stochastic gradient bandit
algorithm has not been previously established, even though it is an old
algorithm known to be applicable to bandits. The new result is achieved by
establishing two novel technical findings: first, the noise of the stochastic
updates in the gradient bandit algorithm satisfies a strong ``growth
condition'' property, where the variance diminishes whenever progress becomes
small, implying that additional noise control via diminishing step sizes is
unnecessary; second, a form of ``weak exploration'' is automatically achieved
through the stochastic gradient updates, since they prevent the action
probabilities from decaying faster than $O(1/t)$, thus ensuring that every
action is sampled infinitely often with probability $1$. These two findings can
be used to show that the stochastic gradient update is already ``sufficient''
for bandits in the sense that exploration versus exploitation is automatically
balanced in a manner that ensures almost sure convergence to a global optimum.
These novel theoretical findings are further verified by experimental results.

证明了随机梯度贪心算法以 $O (1/t)$ 的速率收敛到全局最优策略，即使使用恒定步长，同时通过实验证实了这些理论发现。

随机梯度在匹配问题中取得成功

Stochastic Gradient Succeeds for Bandits

The traditional vocoders have the advantages of high synthesis efficiency,
strong interpretability, and speech editability, while the neural vocoders have
the advantage of high synthesis quality. To combine the advantages of two
vocoders, inspired by the traditional deterministic plus stochastic model, this
paper proposes a novel neural vocoder named NeuralDPS which can retain high
speech quality and acquire high synthesis efficiency and noise controllability.
Firstly, this framework contains four modules: a deterministic source module, a
stochastic source module, a neural V/UV decision module and a neural filter
module. The input required by the vocoder is just the spectral parameter, which
avoids the error caused by estimating additional parameters, such as F0.
Secondly, to solve the problem that different frequency bands may have
different proportions of deterministic components and stochastic components, a
multiband excitation strategy is used to generate a more accurate excitation
signal and reduce the neural filter's burden. Thirdly, a method to control
noise components of speech is proposed. In this way, the signal-to-noise ratio
(SNR) of speech can be adjusted easily. Objective and subjective experimental
results show that our proposed NeuralDPS vocoder can obtain similar performance
with the WaveNet and it generates waveforms at least 280 times faster than the
WaveNet vocoder. It is also 28% faster than WaveGAN's synthesis efficiency on a
single CPU core. We have also verified through experiments that this method can
effectively control the noise components in the predicted speech and adjust the
SNR of speech. Examples of generated speech can be found at
this https URL.

本文提出了一种名为 NeuralDPS 的新型神经语音编码器，通过使用多带激励策略，控制噪声组分，调整语音的信噪比和扩大频带，该编码器可以在保持高语音质量的同时提高合成效率和降低噪声，达到与 WaveNet 相似的性能且至少比 WaveNet 合成速度快 280 倍。