Deep Online Learning with Stochastic Constraints

In many real-world applications, one has to consider the minimization of several loss functions simultaneously, which is, of course, an impossible mission. Therefore, one objective is chosen as the primary function to minimize, leaving the others to be bound by predefined thresholds. For example, in online portfolio selection [5], the ultimate goal is to maximize the wealth of the investor while keeping the risk bounded by a user-defined constant. In the Neyman-Pearson (NP) classification (see, e.g., [22]), an extension of the classical binary classification, the goal is to learn a classifier achieving low type-II error whose type-I error is kept below a given threshold. Another example is the online job scheduling in distributed data centers (see, e.g., [14]), in which a job router receives job tasks and schedules them to different servers to fulfill the service. Each server purchases power (within its capacity) from its zone market, used for serving the assigned jobs. Electricity market prices can vary significantly across time and zones, and the goal is to minimize the electricity cost subject to the constraint that incoming jobs must be served in time. It is indeed possible to adjust any training algorithms capable of dealing with one objective loss to deal with multiple objectives by assigning a positive weight to each loss function. However, this modification turns out to be a difficult problem, especially in the case where one has to maintain the constraints below a given threshold online.