Reviews: Learning SMaLL Predictors

Summary of paper: The paper addresses the problem of learning in resource constrained setting using multiple linear predictors (max of linear predictors like DNF). The problem of learning k-DNFs (a subset of multiple linear predictord) is known to be hard however to solve this non-convex problem, they use various relaxations to formulate this as a minmax saddle point objective which they solve using standard mirror-prox algorithm. The paper then goes on to show that the approach is fruitful in practice through experiments. Comments for authors: In the introduction (line 28-31), you seem to sugest that you can solve the problem of k-DNFs however you do not actually give any guarantees for the final learnt hypothesis that your algorithm outputs, please make that clear. Requiring a different weight vector for each positive example, this seems very costly and potentially avoidable.