Rocco A. Servedio

Distribution-Free Testing Lower Bounds for BasicBoolean Functions (2009)

of decision lists and linear threshold functions

Dana Glasner, Rocco A. Servedio

Abstract. In the distribution-free property testing model, the distance betweenfunctions is measured with respect to an arbitrary and unknown probability distribution D over the input domain. We...

Abstract (2009)

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1} n. We give a polynomial time algorithm for learning decision trees and DNF formulas in...

y (2009)

Abstract We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an...

Abstract (2009)

Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright

of decision lists and linear threshold functions

\Lambda (2009)

Columbia University

On PAC Learning using Winnow, Perceptron, and a Perceptron-Like Algorithm (2008)

Jon Feldman, Cliff Stein, Tal Malkin, Rocco A. Servedio, Martin J. Wainwright

We show that for low-density parity-check (LDPC) codes with sufficient expansion, the

In this paper we analyze the PAC learning abilities of several simple iterative algorithms for learning linear threshold functions, obtaining both positive and negative results. We show that...

Adam Tauman Kalai, Rocco A. Servedio

Boosting algorithms are procedures that “boost ” low accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice and has...

1 (2008)

Marta Arias, Roni Khardon, Rocco A. Servedio

2 1

On the Capacity of Secure Network Coding (2008)

Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein

We consider the problem of using a multicast network code to transmit information securely in the presence of a "wire-tap " adversary who can eavesdrop on a bounded number of...

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution on the Boolean hypercube to within any constant error parameter. We...

PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption (2008)

We give new upper and lower bounds on the degree of real multivariate polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential...

Abstract. We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. [12]....

Perceptron-Like Performance for Intersections of (2008)

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1} n. We give a polynomial time algorithm for learning decision trees and DNF formulas in...

1 Divsion of Engineering and Applied Sciences (2008)

Given a set of examples on the unit ball in Rn which are labelled by a halfspace h which has margin ae (minimum Euclidean distance from any point to the separating hyperplane), the well known...

Abstract. We consider two well-studied problems regarding attribute efficient learning: learning decision lists and learning parity functions. First, we give an algorithm for learning decision lists...

Learning Unions of!(1)-Dimensional Rectangles (2008)

Ilias Diakonikolas, Ronitt Rubinfeld, Homin K. Lee, Rocco A. Servedio, Kevin Matulef, Krzysztof Onak, ...

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. [6] with ideas from...

Alp Atici, Rocco A. Servedio

Abstract. We consider the problem of learning unions of rectangles over the domain [b]n, in the uniform distribution membership query learning setting, where both b and n are...

Learning Unions of ω(1)-Dimensional Rectangles (2008)

This paper studies boosting algorithms that make a single pass over a set of base classifiers. We first analyze a one-pass algorithm in the setting of boosting with diverse base classifiers. Our...

Alp Atıcı, Rocco A. Servedio

Abstract. We consider the problem of learning unions of rectangles over the domain [b] n, in the uniform distribution membership query learning setting, where both b and n are “large”. We obtain...

PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption (2008)

DNF are Teachable in the Average Case (2008)

Abstract. We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. [12]....

Homin K. Lee, Rocco A. Servedio, Andrew Wan

1 Introduction Many results in computational learning theory consider learners that have someform of access to an oracle that provides labeled examples. Viewed as teachers, these oracles tend to be...

1.1 Polynomial Threshold Functions (2008)

Efficiently Testing Sparse GF(2) Polynomials (2008)

Using techniques from learning theory, we show that any s-term DNF over n variables can be computed by a polynomial threshold function of degree O(n 1/3 log s). This upper bound matches, up to a...

Diakonikolas, Ilias, Lee, Homin K., Matulef, Kevin, Servedio, Rocco A., Wan, Andrew

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function $f: \{0,1\}^n \to \{0,1\}$ is an $s$-sparse GF(2) polynomial versus $\eps$-far from...

We show that any weak ranker that can achieve an area under the ROC curve slightly better than 1/2 (which can be achieved by random guessing) can be efficiently boosted to achieve an area under the...

Separating Models of Learning from Correlated and Uncorrelated Data (2008)

This paper studies boosting algorithms that make a single pass over a set of base classifiers. We first analyze a one-pass algorithm in the setting of boosting with diverse base classifiers. Our...

Ariel Elbaz, Homin K. Lee, Rocco A. Servedio, Andrew Wan

Abstract. We consider a natural framework of learning from correlated data, in which successive examples used for learning are generated according to a random walk over the space of possible...

We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. [18]. We give a poly(n/ɛ) time...

of decision lists and linear threshold functions

Recent work has introduced Boolean kernels with which one can learn linear threshold functions over a feature space containing all conjunctions of length up to k (for any 1 ≤ k ≤ n) over the...

ABSTRACT Boosting in the Presence of Noise (2008)

Ilias Diakonikolas, Ronitt Rubinfeld, Homin K. Lee, Rocco A. Servedio, Kevin Matulef, Krzysztof Onak, ...

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. [6] with ideas from...

Adam Kalai, Rocco A. Servedio

Boosting algorithms are procedures that “boost ” low accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice and has...

Distribution-Free Testing Lower Bounds for Basic Boolean Functions (2008)

Dana Glasner, Rocco A. Servedio

Abstract. In the distribution-free property testing model, the distance between functions is measured with respect to an arbitrary and unknown probability distribution D over the input domain. We...

Separating Models of Learning from Correlated and Uncorrelated Data (2008)

Ariel Elbaz, Homin K. Lee, Rocco A. Servedio, Andrew Wan, Peter Auer, Ron Meir

We consider a natural framework of learning from correlated data, in which successive examples used for learning are generated according to a random walk over the space of possible examples. A recent...

DNF are Teachable in the Average Case (2008)

Homin K. Lee, Rocco A. Servedio, Andrew Wan

Abstract. We study the average number of well-chosen labeled examples that are required for a helpful teacher to uniquely specify a target function within a concept class. This “average teaching...

Polynomial Certificates for Propositional Classes ⋆ Abstract (2008)

Marta Arias, Aaron Feigelson, Roni Khardon, Rocco A. Servedio

This paper studies the complexity of learning classes of expressions in propositional logic from equivalence queries and membership queries. In particular, we focus on bounding the number of queries...

Unsupervised Evidence Integration (2008)

Philip M. Long, Vinay Varadan, Sarah Gilman, Mark Treshock, Rocco A. Servedio

Many biological propositions can be supported by a variety of different types of evidence. It is often useful to collect together large numbers of such propositions, together with the evidence...

We show that any weak ranker that can achieve an area under the ROC curve slightly better than 1/2 (which can be achieved by random guessing) can be efficiently boosted to achieve an area under the...

Zafer Barutcuoglu, Philip M. Long, Rocco A. Servedio, Thispaperstudiesboostingalgorithmsthatmakeasingle Passoverasetofbase

classifiers.

This paper studies boosting algorithms that make a single pass over a set of base classifiers. We first analyze a one-pass algorithm in the setting of boosting with diverse base classifiers. Our...

uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow Parameters. Providing an algorithmic version of Chow’s theorem — i.e., efficiently...

Smooth Boosting and Linear Threshold Learning with Malicious Noise (2007)

We study the learnability of sets in R n under the Gaussian distribution, taking Gaussian surface area as the “complexity measure ” of the sets being learned. Let CS denote the class of all...

On the Limits of Efficient Teachability (2007)

We describe a PAC algorithm for learning linear threshold functions when some fraction of the examples used for learning are generated and labeled by an omniscient malicious adversary. The algorithm...

In recent years a number of researchers in learning theory have developed and analyzed

O( (2007)

Lower Bounds for Learning Discrete Distributions (2007)

We show that the class of monotone 2

We study the model of learning discrete probability distributions which was introduced by Kearns, Mansour, Ron, Rubinfeld, Schapire, and Sellie in [13]. Our main results are a lower bound on...

y (2007)

Jerey C. Jackson, Adam R. Klivans, Rocco A. Servedio

We give new upper and lower bounds on the degree of real multivariate polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the rst known subexponential time...

y (2007)

We give an algorithm to learn constant-depth polynomial-size circuits augmented with majority gates under the uniform distribution using random examples only. For circuits which contain a...

Abstract. We show that the class of monotone 2 O( (2007)

Engineering Sciences Lab 102 (2007)

log n)-term DNF formulae can be PAC learned in polynomial time under the uniform distribution from random examples only. This is an exponential improvement over the best previous polynomial-time...

Adam A. Deaton, Rocco A. Servedio

Considerable research effort has been directed in recent years toward the problem of computationally identifying genes in DNA sequences. A fundamental component of a genefinding system is a predictor...

Probabilistic Construction of Monotone Formulae for Positive Linear Threshold Functions (2007)

Polynomial Certificates for Propositional Classes (2007)

We extend Valiant's construction of monotone formulae for the majority function to obtain an efficient probabilistic construction of small monotone formulae for arbitrary positive linear...

Marta Arias, Roni Khardon, Rocco A. Servedio

This paper studies the query complexity of learning classes of expressions in propositional logic from equivalence and membership queries. We give new constructions of polynomial size certificates of...

Maximum Margin Algorithms with Boolean Kernels (2007)

Recent work has introduced Boolean kernels with which one can learn over a feature space containing all conjunctions of length up to k (for any 1 k n) over the original n Boolean features in the...

y (2007)

Quantum Algorithms for Learning and Testing Juntas (2007)

We give the rst polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution to within any constant error parameter. We also give the rst...

Atici, Alp, Servedio, Rocco A.

In this article we develop quantum algorithms for learning and testing juntas, i.e. Boolean functions which depend only on an unknown set of k out of n input variables. Our aim is to develop...

In this paper we give new extremal bounds on polynomial threshold function (PTF) representations of Boolean functions. Our results include the following: • Almost every Boolean function has PTF...

Ilias Diakonikolas, Ronitt Rubinfeld, Homin K. Lee, Rocco A. Servedio, Kevin Matulef, Krzysztof Onak, ...

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. [FKR + 04] with ideas...

Lisa Hellerstein, Rocco A. Servedio

We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying...

Kevin Matulef, Rocco A. Servedio, Ronitt Rubinfeld

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x) = sgn(w ·x−θ). We consider halfspaces over the continuous domain R...

Kevin Matulef, Rocco A. Servedio, Ronitt Rubinfeld

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x) = sgn(w ·x−θ). We consider halfspaces over the continuous domain R...

PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption (2006)

Feldman, Jon, O'Donnell, Ryan, Servedio, Rocco A.

We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. Here the task is to...

Abstract (2006)

Adam Tauman Kalai, Adam R. Klivans, Rocco A. Servedio, Yishay Mansour

We give the first dimension-efficient algorithm that learns (under distributional assumptions) a halfspace in the difficult agnostic framework of Kearns et al. [21], where a learner is given access...

Software Abstractions (2006)

Jeffrey C. Jackson, Homin K. Lee, Andrew Wan, Rocco A. Servedio

We give an algorithm that with high probability properly learns random monotone t(n)-term DNF under the uniform distribution on the Boolean cube {0, 1} n. For any polynomially bounded function t(n)...

Every linear threshold function has a low-weight approximator (2006)

PAC learning mixtures of Gaussians with no separation assumption (2006)

Given any linear threshold function f on n Boolean variables, we construct a linear threshold function g which disagrees with f on at most an ɛ fraction of inputs and has integer weights each of...

Toward Attribute Efficient Learning of Decision Lists and Parities (2006)

Abstract. We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. [12]....

Adam R. Klivans, Rocco A. Servedio, Dana Ron

We consider two well-studied problems regarding attribute efficient learning: learning decision lists and learning parity functions. First, we give an algorithm for learning decision lists of length...

PAC learning mixtures of Gaussians with no separation assumption (2006)

Abstract. We propose and analyze a new vantage point for the learning of mixtures of Gaussians: namely, the PAC-style model of learning probability distributions introduced by Kearns et al. [12]....

Abstract (2006)

Adam Tauman Kalai, Adam R. Klivans, Rocco A. Servedio, Yishay Mansour

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1} n. We give a polynomial time algorithm for learning decision trees and DNF formulas in...

Abstract (2006)

We give the first dimension-efficient algorithm that learns (under distributional assumptions) a halfspace in the difficult agnostic framework of Kearns et al. [21], where a learner is given access...

Learning Unions of $\omega(1)$-Dimensional Rectangles (2005)

Atici, Alp, Servedio, Rocco A.

We consider the problem of learning unions of rectangles over the domain $[b]^n$, in the uniform distribution membership query learning setting, where both b and n are "large". We obtain poly$(n,...

Every decision tree has an influential variable (2005)

O'Donnell, Ryan, Saks, Michael, Schramm, Oded, Servedio, Rocco A.

We prove that for any decision tree calculating a boolean function $f:\{-1,1\}^n\to\{-1,1\}$, \[ \Var[f] \le \sum_{i=1}^n \delta_i \Inf_i(f), \] where $\delta_i$ is the probability that the $i$th...

Agnostically Learning Halfspaces (2005)

Kalai, Adam, Klivans, Adam, Mansour, Yishay, Servedio, Rocco A.

We consider the problem of learning a halfspace in the agnostic framework of Kearns et al., where a learner is given access to a distribution on labelled examples but the labelling may be arbitrary....

Learning mixtures of product distributions over discrete domains (2005)

Feldman, Jon, O'Donnell, Ryan, Servedio, Rocco A.

We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. We give a $\poly(n/\eps)$ time algorithm...

On learning random DNF formulas under the uniform distribution (2005)

Jeffrey C. Jackson, Rocco A. Servedio

Abstract: We study the average-case learnability of DNF formulas in the model of learning from uniformly distributed random examples. We define a natural model of random monotone DNF formulas and...

function f: {−1, 1} n → {−1, 1}, (2005)

Michael Saks, Rocco A. Servedio, Oded Schramm

Theory Group (2005)

Redmond Wa, Rocco A. Servedio

We give an algorithm that learns any monotone Boolean function f: {−1, 1} n → {−1, 1} to any constant accuracy, under the uniform distribution, in time polynomial in n and in the decision tree...

Theory (2005)

Redmond Wa, Rocco A. Servedio

We give an algorithm that learns any monotone Boolean function f: {−1, 1} n → {−1, 1} to any constant accuracy, under the uniform distribution, in time polynomial in n and in the decision tree...

Computing sparse permanents faster (2005)

Rocco A. Servedio, Andrew Wan

Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any n × n zero-one matrix in expected time exp

Abstract (2005)

Adam Tauman Kalai, Rocco A. Servedio, Yishay Mansour

We consider the problem of learning a halfspace in the agnostic framework of Kearns et al. [18], where a learner is given access to a distribution on labelled examples but the labelling may be...

Computing sparse permanents faster (2005)

Rocco A. Servedio, Andrew Wan

Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any n × n zero-one matrix in expected time exp

Abstract (2005)

Adam Tauman Kalai, Adam R. Klivans, Rocco A. Servedio, Yishay Mansour

We give the first algorithm that (under distributional assumptions) efficiently learns halfspaces in the notoriously difficult agnostic framework of Kearns, Schapire, & Sellie, where a learner is...

Improved Bounds on Quantum Learning Algorithms (2004)

Atici, Alp, Servedio, Rocco A.

In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples. Hunziker et al. conjectured that for any class C of...

On decision trees, influences, and learning monotone decision trees (2004)

O'Donnell, Ryan, Servedio, Rocco A.

In this note we prove that a monotone boolean function computable by a decision tree of size $s$ has average sensitivity at most $\sqrt{\log_2 s}$. As a consequence we show that monotone functions...

Monotone Boolean formulas can approximate monotone linear threshold functions. Discrete Applied Mathematics (2004)

Jeffrey C. Jackson, Rocco A. Servedio

We show that any monotone linear threshold function on n Boolean variables can be approximated to within any constant accuracy by a monotone Boolean formula of poly(n) size. 1

Learning (2004)

random log-depth decision trees under the uniform distribution

LP decoding corrects a constant fraction of errors (2004)

Jon Feldman, Tal Malkin, Rocco A. Servedio, Cli Stein, Martin J. Wainwright

We show that for low-density parity-check (LDPC) codes with sucient expansion, the Linear Programming (LP) Decoder of Feldman, Karger and Wainwright (Allerton, 2003) can correct a constant fraction...

Equivalences and separations between quantum and classical learnability (2004)

Rocco A. Servedio, J. Gortler

Abstract. We consider quantum versions of two well-studied models of learning Boolean functions: Angluin’s model of exact learning from membership queries and Valiant’s Probably Approximately...

Abstract (2004)

Marta Arias, Roni Khardon, Aaron Feigelson, Rocco A. Servedio, Marta Arias, Roni Khardon, ...

This paper studies the complexity of learning classes of expressions in propositional logic from equivalence queries and membership queries. In particular, we focus on bounding the number of queries...

LP decoding corrects a constant fraction of errors (2004)

Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright

Abstract—We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a...

On the capacity of secure network coding (2004)

Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein

We consider the problem of using a multicast network code to transmit information securely in the presence of a “wire-tap ” adversary who can eavesdrop on a bounded number of network edges. Cai...

Toward Attribute Efficient Learning Algorithms (2003)

Klivans, Adam R., Servedio, Rocco A.

We make progress on two important problems regarding attribute efficient learnability. First, we give an algorithm for learning decision lists of length $k$ over $n$ variables using...

Learning intersections and thresholds of halfspaces Adam R. Klivans, a,1 Ryan O’Donnell, b,2 c,,3 (2003)

Elchanan Mossel, Rocco A. Servedio

ARTICLE IN PRESS We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution on the Boolean hypercube to within any constant...

Learning juntas (2003)

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for...

Learning juntas (2003)

Elchanan Mossel, Rocco A. Servedio

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for...

Boosting in the Presence of Noise (2003)

Adam Kalai, Rocco A. Servedio

Boosting algorithms are procedures that \boost " low-accuracy weak learning algorithms to achieve arbitrarily high accuracy. Over the past decade boosting has been widely used in practice...

Maximum margin algorithms with Boolean kernels (2003)

Learning DNF from Random Walks (2003)

Abstract. Recent work has introduced Boolean kernels with which one can learn over a feature space containing all conjunctions of length up to k (for any 1 ≤ k ≤ n) over the original n Boolean...

Extremal Properties of Polynomial Threshold Functions (2003)

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0,

Ryan O'Donnell, Rocco A. Servedio

In this paper we give new extremal bounds on polynomial threshold function (PTF) representations of Boolean functions. Our results include the following: .

Maximum margin algorithms with Boolean kernels (2003)

Maximum margin algorithms with Boolean kernels (2003)

Recent work has introduced Boolean kernels with which one can learn linear threshold functions over a feature space containing all conjunctions of length up to k (for any 1 ≤ k ≤ n) over the...

Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio

Recent work has introduced Boolean kernels with which one can learn linear threshold functions over a feature space containing all conjunctions of length up to k (for any 1 ≤ k ≤ n) over the...

Learning Juntas (2003)

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for...

Learning juntas (2003)

Elchanan Mossel, Rocco A. Servedio, Cambridge Ma

Polynomial certificates for propositional classes (2003)

Marta Arias, Roni Khardon, Rocco A. Servedio

Abstract. This paper studies the query complexity of learning classes of expressions in propositional logic from equivalence and membership queries. We give new constructions of polynomial size...

Extremal properties of polynomial threshold functions (2003)

Separating quantum and classical learning (2001)

In this paper we give new extremal bounds on polynomial threshold function (PTF) representations of Boolean functions. Our results include the following: • Almost every Boolean function has PTF...

On learning monotone DNF under product distributions (2001)

Abstract. We consider a model of learning Boolean functions from quantum membership queries. This model was studied in [26], where it was shown that any class of Boolean functions which is...

Quantum versus classical learnability (2001)

We show that the class of monotone 2 O( √ log n)-term DNF formulae can be PAC learned in polynomial time under the uniform distribution from random examples only. This is an exponential improvement...

Rocco Servedio, Rocco A. Servedio, Steven J. Gortler

This paper studies fundamental questions in computational learning theory from a quantum computation perspective. We consider quantum versions of two well-studied classical learning models:...

Quantum versus classical learnability (2001)

Rocco A. Servedio, Steven J. Gortler

Motivated by recent work on quantum black-box query complexity, we consider quantum versions of two wellstudied models of learning Boolean functions: Angluin's model of exact learning from...

Learning DNF in time 2 (2001)

Separating quantum and classical learning (2001)

Using techniques from learning theory, we show that any s-term DNF over n variables can be computed by a polynomial threshold function of degree O(n 1=3 log s). This upper bound matches, up to a...

Separating quantum and classical learning (2001)

We consider a model of learning Boolean functions from quantum membership queries. This model is a natural generalization of the classical membership query learning model to the quantum domain and is...

Smooth boosting and learning with malicious noise (2001)

Abstract. We consider a model of learning Boolean functions from quantum membership queries. This model was studied in [26], where it was shown that any class of Boolean functions which is...

Smooth boosting and learning with malicious noise (2001)

Abstract. We describe a new boosting algorithm which generates only smooth distributions which do not assign too much weight to any single example. We show that this new boosting algorithm can be...

Rocco A. Servedio, Manfred Warmuth

We describe a new boosting algorithm which generates only smooth distributions which do not assign too much weight to any single example. We show that this new boosting algorithm can be used to...

Learning dnf in time (2001)

Quantum versus Classical Learnability (2001)

Using techniques from learning theory, we show that any s-term DNF over n variables can be computed by a perceptron of order O((n log n) 1=3 log s). This upper bound matches, up to a polylogarithmic...

Rocco A. Servedio, Steven J. Gortler

This paper studies fundamental questions in computational learning theory from a quantum computation perspective. We consider quantum versions of two well-studied classical learning models:...

Efficiency versus convergence of boolean kernels for on-line learning algorithms (2001)

Roni Khardon, Dan Roth, Rocco A. Servedio

The paper studies machine learning problems where each example is described using a set of Boolean features and where hypotheses are represented by linear threshold elements. One method of increasing...

Efficiency versus convergence of boolean kernels for on-line learning algorithms (2001)

Roni Khardon, Dan Roth, Rocco A. Servedio

The paper studies machine learning problems where each example is described using a set of Boolean features and where hypotheses are represented by linear threshold elements. One method of increasing...

Smooth boosting and learning with malicious noise (2001)

Rocco A. Servedio, Manfred Warmuth

We describe a new boosting algorithm which generates only smooth distributions which do not assign too much weight to any single example. We show that this new boosting algorithm can be used to...

Efficiency versus convergence of boolean kernels for on-line learning algorithms (2001)

Roni Khardon, Dan Roth, Rocco A. Servedio

The paper studies machine learning problems where each example is described using a set of Boolean features and where hypotheses are represented by linear threshold elements. One method of increasing...

Martingale boosting (2001)

Quantum versus Classical Learnability (2000)

Abstract. Martingale boosting is a simple and easily understood technique with a simple and easily understood analysis. A slight variant of the approach provably achieves optimal accuracy in the...

Servedio, Rocco A., Gortler, Steven J.

We consider quantum versions of two well-studied classical learning models: Angluin's model of exact learning from membership queries and Valiant's Probably Approximately Correct (PAC) model of...

Computational Sample Complexity and Attribute-Efficient Learning (2000)

Rocco A. Servedio, Rocco Servedio

Two fundamental measures of the efficiency of a learning algorithm are its running time and the number of examples it requires (its sample complexity). In this paper we demonstrate that even for...

PAC Analogues of Perceptron and Winnow via Boosting the Margin (2000)

Rocco Servedio Division, Rocco A. Servedio

We describe a novel family of PAC model algorithms for learning linear threshold functions. The new algorithms work by boosting a simple weak learner and exhibit complexity bounds remarkably similar...

PAC Analogues of Perceptron and Winnow via Boosting the Margin (2000)

Boosting and hard-core sets (1999)

We describe a novel family of PAC model algorithms for learning linear threshold functions. The new algorithms work by boosting a simple weak learner and exhibit complexity bounds remarkably similar...

On PAC Learning Using Winnow, Perceptron, and a Perceptron-Like Algorithm (1999)

This paper connects two fundamental ideas from theoretical computer science: hard-core set construction, a type of hardness amplification from computational complexity, and boosting, a technique from...

Boosting and Hard-Core Sets (1999)

In this paper we analyze the PAC learning abilities of several simple iterative algorithms for learning linear threshold functions, obtaining both positive and negative results. We show that...