Combinatorial dimensions play an important role in the theory of machine learning.

There are many natural models for noise.

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. Summary: This paper proposes boosting algorithms and analyze them from an online learning perspective. First, they propose a boosting algorithm based on the update of the online mirror descent(MABoost). Then they show a smooth version of MABoost, i.e., a variant of MABoost which creates only smooth distributions over examples. Further, they propose sparse or lazy versions of MABoost and show their convergence proofs.

The realizable-to-agnostic transformation (Beimel et al., 2015; Alon et al., 2020) provides a general mechanism to convert a private learner in the realizable setting (where the examples are labeled by some function in the concept class) to a private learner in the agnostic setting (where no assumptions are imposed on the data). Specifically, for any concept class $\mathcal{C}$ and error parameter $α$, a private realizable learner for $\mathcal{C}$ can be transformed into a private agnostic learner while only increasing the sample complexity by $\widetilde{O}(\mathrm{VC}(\mathcal{C})/α^2)$, which is essentially tight assuming a constant privacy parameter $\varepsilon = Θ(1)$. However, when $\varepsilon$ can be arbitrary, one has to apply the standard privacy-amplification-by-subsampling technique (Kasiviswanathan et al., 2011), resulting in a suboptimal extra sample complexity of $\widetilde{O}(\mathrm{VC}(\mathcal{C})/α^2\varepsilon)$ that involves a $1/\varepsilon$ factor. In this work, we give an improved construction that eliminates the dependence on $\varepsilon$, thereby achieving a near-optimal extra sample complexity of $\widetilde{O}(\mathrm{VC}(\mathcal{C})/α^2)$ for any $\varepsilon\le 1$. Moreover, our result reveals that in private agnostic learning, the privacy cost is only significant for the realizable part. We also leverage our technique to obtain a nearly tight sample complexity bound for the private prediction problem, resolving an open question posed by Dwork and Feldman (2018) and Dagan and Feldman (2020).

We thank all the reviewers for the time reading our paper! W e plan to include that if the paper gets in. We're afraid R2 has misunderstood our work. Our main contribution is to show "can Neu ral Net works learn some Generally, our work is not about "there exist learning methods Our main contribution is to show that "Neural Networks can be better learners than kernels (esp. This was not known at all in the distribution-free setting, which we have emphasized in the introduction. For [37], its separation works only when the solution (i.e., the network weights) corresponds to a "max-margin This is not necessarily efficiently learnable.

This paper develops a general approach, rooted in statistical learning theory, to learning an approximately revenue-maximizing auction from data. We introduce t -level auctions to interpolate between simple auctions, such as welfare maximization with reserve prices, and optimal auctions, thereby balancing the competing demands of expressivity and simplicity. We prove that such auctions have small representation error, in the sense that for every product distribution F over bidders' valuations, there exists a t -level auction with small t and expected revenue close to optimal. We show that the set of t -level auctions has modest pseudo-dimension (for polynomial t) and therefore leads to small learning error. One consequence of our results is that, in arbitrary single-parameter settings, one can learn a mechanism with expected revenue arbitrarily close to optimal from a polynomial number of samples.

Algorithmic machine teaching studies the interaction between a teacher and a learner where the teacher selects labeled examples aiming at teaching a target hypothesis.

This paper establishes a statistical versus computational trade-off for solving a basic high-dimensional machine learning problem via a basic convex relaxation method. Specifically, we consider the Sparse Principal Component Analysis (Sparse PCA) problem, and the family of Sum-of-Squares (SoS, aka Lasserre/Parillo) convex relaxations.

Sloan (1988), Cohen (1997), and was most recently highlighted in Avrim Blum's In this work, we focus on learning halfspaces with Massart noise [MN06]: Definition 1.1 A learning algorithm is given i.i.d. The question is whether a polynomial time algorithm exists.