{"638750":{"#nid":"638750","#data":{"type":"event","title":"ARC Colloquium: Sumegha Garg (Princeton)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003ESumegha Garg (Princeton)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 12, 2020\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EVirtual via Bluejeans - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp; \u003C\/strong\u003EExtractor-based Approach to Proving Memory-Sample Lower Bounds for Learning\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EA recent line of work has focused on the following question: Can one prove strong unconditional lower bounds on the number of samples needed for learning under memory constraints? We study an extractor-based approach to proving such bounds for a large class of learning problems as follows.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nA matrix M: A x X -\u0026gt; {-1,1} corresponds to the following learning problem: An unknown function f in X is chosen uniformly at random. A learner tries to learn f from a stream of samples, (a_1, b_1), (a_2, b_2) ..., where for every i, a_i in A is chosen uniformly at random and b_i = M(a_i,f).\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nAssume that k, l, r are such that any submatrix of M, with at least 2^{-k}|A| rows and at least 2^{-l}|X| columns, has a bias of at most 2^{-r} (extractor property). We show that any learning algorithm for the learning problem corresponding to M requires either a memory of size at least \u0026Omega;(k l), or at least 2^{\u0026Omega;(r)} samples.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nWe also extend the lower bounds to a learner that is allowed two passes over the stream of samples. In particular, we show that any two-pass algorithm for learning parities of size n requires either a memory of size \u0026Omega;(n^{3\/2}) or at least 2^{\u0026Omega;(n^{1\/2})} samples.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nJoint works with Ran Raz and Avishay Tal.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E----------------------------------\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u003Ca href=\u0022https:\/\/www.cs.princeton.edu\/~sumeghag\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/strong\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Extractor-based Approach to Proving Memory-Sample Lower Bounds for Learning: Virtual via Bluejeans at 11:00am"}],"uid":"27544","created_gmt":"2020-09-03 14:56:21","changed_gmt":"2020-09-29 16:23:41","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2020-10-12T12:00:00-04:00","event_time_end":"2020-10-12T13:00:00-04:00","event_time_end_last":"2020-10-12T13:00:00-04:00","gmt_time_start":"2020-10-12 16:00:00","gmt_time_end":"2020-10-12 17:00:00","gmt_time_end_last":"2020-10-12 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}