{"65695":{"#nid":"65695","#data":{"type":"event","title":"CSE Seminar : Ken Clarkson","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EKen Clarkson\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIBM Almaden Research Center\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ECoordinate Sampling for Sublinear Optimization and Nearest Neighbor Search\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EI will describe randomized approximation algorithms for some classical problems of machine learning, where the algorithms have provable bounds that hold with high probability. Some of our algorithms are sublinear, that is, they do not need to touch all the data. Specifically, for a set of points a_1...a_n in d dimensions, we show that finding a d-vector x that approximately maximizes the\u003Cbr \/\u003Emargin min_i a_i dot x can be done in O(n+d)\/epsilon^2 time, up to logarithmic factors, where epsilon\u0026gt;0 is an additive approximation parameter. This was joint work with Elad Hazan and David Woodruff.\u003Cbr \/\u003E\u003Cbr \/\u003EA key step in these algorithms is the use of coordinate sampling to estimate dot products. This simple technique can be an effective alternative to random projection sketching in some settings. I will discuss the potential of coordinate sampling for speeding up some data structures for nearest neighbor searching in the Euclidean setting, via fast approximate distance evaluations.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EKen Clarkson is manager of the Computer Science Principles and Methodologies department at IBM Research, Almaden (in San Jose, CA). His work has mostly been on geometric algorithms, in particular on the use of randomization, for such problems as\u0026nbsp;linear programming, nearest neighbor search in metric spaces, simple polygon triangulation, building compressed quadtrees, and computing convex hulls.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;~~~~~~~~~~~~~~~~~~~~~~\u003C\/p\u003E\u003Cp\u003ETo receive future announcements, please sign up to the cse-seminar email list:\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/cse-seminar\u0022 target=\u0022_blank\u0022\u003Ehttps:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/cse-seminar\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Coordinate Sampling for Sublinear Optimization and Nearest Neighbor Search\/ By: Ken Clarkson"}],"uid":"27439","created_gmt":"2011-04-21 12:05:49","changed_gmt":"2016-10-08 01:54:50","author":"Lometa Mitchell","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-04-22T15:00:00-04:00","event_time_end":"2011-04-22T16:00:00-04:00","event_time_end_last":"2011-04-22T16:00:00-04:00","gmt_time_start":"2011-04-22 19:00:00","gmt_time_end":"2011-04-22 20:00:00","gmt_time_end_last":"2011-04-22 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50877","name":"School of Computational Science and Engineering"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDr. Alexander Gray at \u003Ca href=\u0022mailto:agray@cc.gatech.edu\u0022 target=\u0022_blank\u0022\u003Eagray@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}