# DIMACS Theory Seminar

## Title:

Learning noisy halfspaces and weak linear programming

## Speaker:

- Avrim Blum
- CMU

## Place:

- Room 402, Computer Science Building,
- 35 Olden Street, Princeton University

## Time:

- Lunch served at 11:45 AM, Room 402
- Talk: Room 402, at 12 Noon
- Friday, October 6, 1995

## Abstract:

The problem of learning a linear threshold function (a halfspace in n
dimensions, also called a "perceptron") is one of the oldest in machine
learning. Methods for doing this generally fall into two categories. Greedy
algorithms are simple and can be made noise tolerant; but, their running time
depends on a separation parameter that may be exponentially small. On the
other hand, linear programming algorithms such as the Ellipsoid Algorithm run
in polynomial time, but seem to be intolerant of noise. We show how greedy
methods can be used to find weak hypotheses (hypotheses that classify
noticeably more than half of the examples) in polynomial time, without
dependence on any separation parameter. This results in a polynomial-time
algorithm for learning halfspaces in the presense of classification noise.
This is joint work with Alan Frieze, Ravi Kannan, and Santosh Vempala.

Host: Sanjeev Arora

Document last modified on October 3, 1995