EE Seminar: Beyond Worst Case In Machine Learning: The Oracle Model

18 בדצמבר 2019, 15:00 
Room 011, Kitot Building 

(The talk will be given in English)

 

Speaker:     Dr. Alon Gonen
                     University of California San Diego

 

Wednesday, December 18th, 2019
15:00 - 16:00

Room 011, Kitot Bldg., Faculty of Engineering

 

Beyond Worst Case In Machine Learning: The Oracle Model

Abstract

In recent years there has been an increasing gap between the success of machine learning algorithms and our ability to explain their success theoretically. 

Namely, many of the problems that are solved to a satisfactory degree of precision are computationally hard in the worst case. Fortunately, there are often reasonable assumptions which help us to get around these worst-case impediments and allow us to rigorously analyze heuristics that are used in practice. 

In this talk I will advocate a complementary approach, where instead of explicitly characterizing some desired "niceness" properties of the data, we assume access to an optimization oracle that solves a relatively simpler task. This allows us to identify the sources of hardness and extend our theoretical understanding to new domains. Furthermore we will show that seemingly innocents (and arguably justifiable) modifications to the oracle can lead to tractable reductions and even to bypass hardness results. 

We demonstrate these ideas using the following results: i) An efficient algorithm for non-convex online learning using an optimization oracle. b) A faster boosting algorithm using a "simple" weak learner. iii) An efficient reduction from online to private learning.

 

Joint works with Naman Agarwal, Noga Alon, Elad Hazan, and Shay Moran.

 

Short Bio
Alon Gonen is a postdoctoral at University of California San Diego. Prior to that he was a postdoctoral at Princeton university. He completed his MSc and PhD at the Hebrew University in under the supervision of Shai Shalev-Shwartz. His research focuses on theoretical aspects of machine learning. 

 

 

אוניברסיטת תל אביב עושה כל מאמץ לכבד זכויות יוצרים. אם בבעלותך זכויות יוצרים בתכנים שנמצאים פה ו/או השימוש
שנעשה בתכנים אלה לדעתך מפר זכויות, נא לפנות בהקדם לכתובת שכאן >>