AutoML from Service Provider's Perspective: Multi-device, Multi-tenant
  Model Selection with GP-EI
  AutoML has become a popular service that is provided by most leading cloud
service providers today. In this paper, we focus on the AutoML problem from the
\emph{service provider's perspective}, motivated by the following practical
consideration: When an AutoML service needs to serve {\em multiple users} with
{\em multiple devices} at the same time, how can we allocate these devices to
users in an efficient way? We focus on GP-EI, one of the most popular
algorithms for automatic model selection and hyperparameter tuning, used by
systems such as Google Vizer. The technical contribution of this paper is the
first multi-device, multi-tenant algorithm for GP-EI that is aware of
\emph{multiple} computation devices and multiple users sharing the same set of
computation devices. Theoretically, given $N$ users and $M$ devices, we obtain
a regret bound of $O((\text{\bf {MIU}}(T,K) + M)\frac{N^2}{M})$, where
$\text{\bf {MIU}}(T,K)$ refers to the maximal incremental uncertainty up to
time $T$ for the covariance matrix $K$. Empirically, we evaluate our algorithm
on two applications of automatic model selection, and show that our algorithm
significantly outperforms the strategy of serving users independently.
Moreover, when multiple computation devices are available, we achieve
near-linear speedup when the number of users is much larger than the number of
devices.
