Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with agnostic learning:
TR06-032 | 25th February 2006
Vitaly Feldman

Optimal Hardness Results for Maximizing Agreements with Monomials

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

TR08-091 | 10th September 2008
Vitaly Feldman

On The Power of Membership Queries in Agnostic Learning

Revisions: 1

We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning?

Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>>

TR10-018 | 15th February 2010
Vitaly Feldman

A Complete Characterization of Statistical Query Learning with Applications to Evolvability

Revisions: 1

Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves. We describe a new and simple characterization of the query complexity ... more >>>

TR10-023 | 23rd February 2010
Adam Klivans, Homin Lee, Andrew Wan

Mansour’s Conjecture is True for Random DNF Formulas

Revisions: 3

In 1994, Y. Mansour conjectured that for every DNF formula on $n$ variables with $t$ terms there exists a polynomial $p$ with $t^{O(\log (1/\epsilon))}$ non-zero coefficients such that $\E_{x \in \{0,1\}}[(p(x)-f(x))^2] \leq \epsilon$. We make the first progress on this conjecture and show that it is true for several natural ... more >>>

TR11-090 | 2nd June 2011
Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee

Submodular Functions Are Noise Stable

Revisions: 2

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on $\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$ ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... more >>>

TR14-166 | 8th December 2014
Mark Bun, Thomas Steinke

Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness

Polynomial approximations to boolean functions have led to many positive results in computer science. In particular, polynomial approximations to the sign function underly algorithms for agnostically learning halfspaces, as well as pseudorandom generators for halfspaces. In this work, we investigate the limits of these techniques by proving inapproximability results for ... more >>>

ISSN 1433-8092 | Imprint