Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, April 11, 2013, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Michel Verlinden

Sublinear-time algorithms for support vector machines

The Sublinear Perceptron is a recent algorithm for linear binary classification with support vector machines. It was recently developed by K.L. Clarkson, E. Hazan and D.P. Woodruff. This algorithm approximately solves the problem of finding a hyperplane isolating a set of vectors into a single half-space. The hyperplane is optimal in the sense that the distance of the vectors nearest to the hyperplane is maximized. The algorithm runs in sublinear time which implies that it does not require to read the whole input. It involves randomization based on a novel sampling techniques and a new multiplicative update method.

This talk will present the Sublinear Perceptron and the performance results obtained with our implementation. We shall also present the extension of the algorithm to non-linear classification. The preservation of sublinear-time complexity with non-linear classifiers induces further randomization of the Sublinear Perceptron.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login