A Extra Notations

Here we introduce a few more notations. In this section we provide the details of the subroutines used in the training algorithm for Frugal ML . There are 3 steps for solving problem 3.3. T o solve Problem 3.2, let us first denote C.1 Helpful Lemmas W e first provide some useful lemmas throughout this section. Lemma 4. Suppose the linear optimization problem max Lemma 5. Let F (w) be the optimal value of the linear optimization problem max Thus, the objective value must be smaller than the optimal one, i.e., Given the expected accuracy and cost provided by Lemma 2, the problem 3.1 becomes Let us first consider the expected accuracy .