{"669336":{"#nid":"669336","#data":{"type":"event","title":"ISyE Seminar Speaker - Nikita Zhivotovskiy","body":[{"value":"\u003Cp\u003E\u003Cem\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EOptimal PAC Bounds without Uniform Convergence\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cstrong\u003E\u003Cem\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EAbstract:\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/em\u003E\u003C\/strong\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003EIn statistical learning theory, the problem of determining sample complexity of realizable binary classification for VC classes was a longstanding challenge. Notable advancements by Simon and Hanneke established sharp upper bounds, but their argument\u2019s reliance on the uniform convergence principle curtailed its broader applicability to learning settings like multiclass classification. In this presentation, we will discuss a new technique to resolve this limitation and introduce optimal high probability risk bounds within a framework that surpasses uniform convergence constraints. Beyond binary classification, we will also delve into applications in scenarios where uniform convergence is notably sub-optimal. For multiclass classification, we will prove an optimal risk bound that scales with the one-inclusion hypergraph density of the class, effectively addressing the sub-optimality in the analysis by Daniely and Shalev-Shwartz. Additionally, for realizable bounded regression with absolute loss, we will derive an optimal risk bound based on a revised version of the scale-sensitive dimension, thus refining the results of Bartlett and Long. This talk is based on the joint work with Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, and Abhishek Shetty.\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003ENikita Zhivotovskiy is a tenure-track Assistant Professor at the Unive\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003Ersity of\u0026nbsp;California Berkeley, Department of Statistics.\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EFrom January 2021 to October 2022 he was a postdoctoral researcher at the department of mathematics ETH, Z\u00fcrich hosted by\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Ca href=\u0022https:\/\/people.math.ethz.ch\/~abandeira\/\u0022 target=\u0022_blank\u0022\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EAfonso Bandeira\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/a\u003E\u003Cspan\u003E.\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EBetween January 2019 and December 2020 he was a postdoctoral researcher at\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003EGoogle Research,\u0026nbsp;\u003C\/span\u003E\u003Cspan\u003EZ\u00fcrich hosted by\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Ca href=\u0022https:\/\/research.google\/people\/OlivierBousquet\/\u0022 target=\u0022_blank\u0022\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EOlivier Bousquet\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/a\u003E\u003Cspan\u003E.\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EBefore that he spent half a year at the department of mathematics,\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003ETechnion I.I.T.\u003C\/span\u003E\u003Cspan\u003E\u0026nbsp;hosted by\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Ca href=\u0022https:\/\/maths-people.anu.edu.au\/~mendelso\/\u0022 target=\u0022_blank\u0022\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EShahar Mendelson\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/a\u003E\u003Cspan\u003E.\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003ENikita defended my thesis at Moscow Institute of Physics and Technology Moscow in 2018 under the supervision of\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Ca href=\u0022https:\/\/www.wias-berlin.de\/~spokoiny\/\u0022 target=\u0022_blank\u0022\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EVladimir Spokoiny\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/a\u003E\u003Cspan\u003E\u0026nbsp;and\u0026nbsp;\u003C\/span\u003E\u003Cspan\u003EKonstantin Vorontsov. During my time in Moscow, he was affiliated (part-time) with the Institute for Information Transmission Problems, Higher School of Economics, and Skoltech.\u0026nbsp;\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cspan\u003EHis main interests are in the intersection of mathematical statistics, probability and learning theory.\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003E\u003Cspan\u003E\u003Cspan\u003E\u003Cem\u003EIn statistical learning theory, the problem of determining sample complexity of realizable binary classification for VC classes was a longstanding challenge. Notable advancements by Simon and Hanneke established sharp upper bounds, but their argument\u2019s reliance on the uniform convergence principle curtailed its broader applicability to learning settings like multiclass classification. In this presentation, we will discuss a new technique to resolve this limitation and introduce optimal high probability risk bounds within a framework that surpasses uniform convergence constraints. Beyond binary classification, we will also delve into applications in scenarios where uniform convergence is notably sub-optimal. For multiclass classification, we will prove an optimal risk bound that scales with the one-inclusion hypergraph density of the class, effectively addressing the sub-optimality in the analysis by Daniely and Shalev-Shwartz. Additionally, for realizable bounded regression with absolute loss, we will derive an optimal risk bound based on a revised version of the scale-sensitive dimension, thus refining the results of Bartlett and Long. This talk is based on the joint work with Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, and Abhishek Shetty.\u003C\/em\u003E\u003C\/span\u003E\u003C\/span\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"Optimal PAC Bounds without Uniform Convergence"}],"uid":"36374","created_gmt":"2023-09-01 12:26:03","changed_gmt":"2023-09-01 12:26:03","author":"mwelch39","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-09-15T11:30:00-04:00","event_time_end":"2023-09-15T12:30:00-04:00","event_time_end_last":"2023-09-15T12:30:00-04:00","gmt_time_start":"2023-09-15 15:30:00","gmt_time_end":"2023-09-15 16:30:00","gmt_time_end_last":"2023-09-15 16:30:00","rrule":null,"timezone":"America\/New_York"},"location":" ISYE Groseclose 402","extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"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":"78771","name":"Public"},{"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":""}}}