Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AGNOSTIC LEARNING:
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 >>>

TR18-156 | 8th September 2018
Mark Bun, Robin Kothari, Justin Thaler

#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give ... more >>>

ISSN 1433-8092 | Imprint