On Regularizing Rademacher Observation Losses
It has recently been shown that supervised learning linear classifiers with two of the most popular losses, the logistic and square loss, is equivalent to optimizing an equivalent loss over sufficient statistics about the class: Rademacher observations (rados). It has also been shown that learning over rados brings solutions to two prominent problems for which the state of the art of learning from examples can be comparatively inferior and in fact less convenient: (i) protecting and learning from private examples, (ii) learning from distributed datasets without entity resolution. Bis repetita placent: the two proofs of equivalence are different and rely on specific properties of the corresponding losses, so whether these can be unified and generalized inevitably comes to mind. This is our first contribution: we show how they can be fit into the same theory for the equivalence between example and rado losses. As a second contribution, we show that the generalization unveils a surprising new connection to regularized learning, and in particular a sufficient condition under which regularizing the loss over examples is equivalent to regularizing the rados (i.e. the data) in the equivalent rado loss, in such a way that an efficient algorithm for one regularized rado loss may be as efficient when changing the regularizer. This is our third contribution: we give a formal boosting algorithm for the regularized exponential rado-loss which boost with any of the ridge, lasso, SLOPE, ∞ , or elastic net regularizer, using the same master routine for all. Because the regularized exponential rado-loss is the equivalent of the regularized logistic loss over examples we obtain the first efficient proxy to the minimization of the regularized logistic loss over examples using such a wide spectrum of regularizers. Experiments with a readily available code display that regularization significantly improves rado-based learning and compares favourably with example-based learning.
The paper makes contributions involving Rademacher observations (previously dubbed "rados"), and their relationship to regularization. It shows that the compression of the dataset's information into the set of rados has a regularizing effect, defines rado-losses which are of special importance in the theory, and demonstrates they hold practical value.
The technical contribution of this paper is clear - I recommend acceptance because of the potential value. The theorems apply only to the four losses mentioned, and I was not able to go through the proofs in full detail so I have some doubts about how they would generalize to efficient algorithms otherwise; however, I had more significant doubts after reading the original Nock et al. 2015 paper, and clearly the theory has grown since then. It is indeed interesting that the new boosting algorithm can be implemented as efficiently as the standard ones, but I view this as a side consequence of the formulation and have therefore focused on the remainder in my evaluation.   There are several places in the paper with typos (e.g. line 101, 217), and the material can get dense for a general machine learning audience, though it is mathematically clean and precise. E.g., the discussion of the affinely generated functions in Sec. 2 would be much clearer if re-ordered, so that the motivation for the definitions and choices is clear (e.g. rados represent powersets, so the powerset indexing would clear up significantly). For similar reasons I suggest defining (1) and (2) as a different script letter instead of L, due to Eqs. (11,12) and the possible confusion with losses.  Following from the paper are several interesting and open questions with possible connections to other areas of machine learning. I am interested in the connection to the two-player game formulation, because it suggests different parametrizations of the problem by choosing the z's differently for other learning settings. The z's are currently chosen in a similar way to the boosting game, this conflation of information happens due to linear constraints on the z_i's (weak learning assumption), so they are chosen in this setting with benefits. But the results in Sec. 2 are general and there are other similar game-theoretic formulations in areas like (e.g. online) learning. Are there other ways of condensing the data, besides rados, that are similarly beneficial for those problems?