The target of @math -armed bandit problem is to find the global maximum of an unknown stochastic function @math , given a finite budget of @math evaluations. Recently, @math -armed bandits have been widely used in many situations. Many of these applications need to deal with large-scale data sets. To deal with these large-scale data sets, we study a distributed setting of @math -armed bandits, where @math players collaborate to find the maximum of the unknown function. We develop a novel anytime distributed @math -armed bandit algorithm. Compared with prior work on @math -armed bandits, our algorithm uses a quite different searching strategy so as to fit distributed learning scenarios. Our theoretical analysis shows that our distributed algorithm is @math times faster than the classical single-player algorithm. Moreover, the number of communication rounds of our algorithm is only logarithmic in @math . The numerical results show that our method can make effective use of every players to minimize the loss. Thus, our distributed approach is attractive and useful.
On the other hand, distributed stochastic optimization @cite_4 @cite_1 @cite_9 and distributed PAC models @cite_17 @cite_14 @cite_12 have also been intensively studied. Among them, proposed the distributed algorithm for multi-armed bandits. They studied two kinds of distributed algorithms for multi-armed bandits and discussed the tradeoff between the learning performance and the cost of communication. Inspired by their idea, we propose the distributed algorithm for the @math -armed bandit problem. In contrast to 's study in which the arm space is finite and discrete, our method is the first to study distributed @math -armed bandit problem in which the arm space could be any measurable space.
@cite_14 @cite_4 @cite_9 @cite_1 @cite_12 @cite_17
2952033860 2949469249 2130062883 2151390636
We analyze the convergence of gradient-based optimization algorithms that base their updates on delayed stochastic gradient information. The main application of our results is to the development of gradient-based distributed optimization algorithms where a master node performs parameter updates while worker nodes compute stochastic gradients based on local information in parallel, which may give rise to delays due to asynchrony. We take motivation from statistical problems where the size of the data is so large that it cannot fit on one computer; with the advent of huge datasets in biology, astronomy, and the internet, such problems are now common. Our main contribution is to show that for smooth stochastic problems, the delays are asymptotically negligible and we can achieve order-optimal convergence results. In application to distributed optimization, we develop procedures that overcome communication bottlenecks and synchronization requirements. We show @math -node architectures whose optimization error in stochastic problems---in spite of asynchronous delays---scales asymptotically as @math after @math iterations. This rate is known to be optimal for a distributed system with @math nodes even in the absence of delays. We additionally complement our theoretical results with numerical experiments on a statistical machine learning task. We study exploration in Multi-Armed Bandits in a setting where @math players collaborate in order to identify an @math -optimal arm. Our motivation comes from recent employment of bandit algorithms in computationally intensive, large-scale applications. Our results demonstrate a non-trivial tradeoff between the number of arm pulls required by each of the players, and the amount of communication between them. In particular, our main result shows that by allowing the @math players to communicate only once, they are able to learn @math times faster than a single player. That is, distributing learning to @math players gives rise to a factor @math parallel speed-up. We complement this result with a lower bound showing this is in general the best possible. On the other extreme, we present an algorithm that achieves the ideal factor @math speed-up in learning performance, with communication only logarithmic in @math . Online prediction methods are typically presented as serial algorithms running on a single processor. However, in the age of web-scale prediction problems, it is increasingly common to encounter situations where a single processor cannot keep up with the high rate at which inputs arrive. In this work, we present the distributed mini-batch algorithm, a method of converting many serial gradient-based online prediction algorithms into distributed algorithms. We prove a regret bound for this method that is asymptotically optimal for smooth convex loss functions and stochastic inputs. Moreover, our analysis explicitly takes into account communication latencies between nodes in the distributed environment. We show how our method can be used to solve the closely-related distributed stochastic optimization problem, achieving an asymptotically linear speed-up over multiple processors. Finally, we demonstrate the merits of our approach on a web-scale online prediction problem. We consider the problem of learning classifiers for labeled data that has been distributed across several nodes. Our goal is to find a single classifier, with small approximation error, across all datasets while minimizing the communication between nodes. This setting models real-world communication bottlenecks in the processing of massive distributed datasets. We present several very general sampling-based solutions as well as some two-way protocols which have a provable exponential speed-up over any one-way protocol. We focus on core problems for noiseless data distributed across two or more nodes. The techniques we introduce are reminiscent of active learning, but rather than actively probing labels, nodes actively communicate with each other, each node simultaneously learning the important data from another node.