Opens in a new tab<\/span><\/p>\n Frontiers in Artificial Intelligence<\/span> is a series of public lectures at Microsoft Research Cambridge featur-ing leading researchers in the field, focusing on the cutting edge topics at the intersection of machine learning, statistics, and artificial intelligence. Students, scientists, and engineers in academia and in-dustry are all welcome to join us for these exciting talks and the opportunity to socialize with the Cam-bridge AI\/ML community.<\/p>\n In this work, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized and decentralized communications over a network. For centralized (i.e. master\/slave) algorithms, we show that distributing Nesterov’s accelerated gradient descent is optimal and achieves a precision in time that depends on the condition number of the (global) function to optimize, the diameter of the network, and the time needed to communicate values between two neighbors (resp. perform local computations). For decentralized algorithms based on gossip, we provide the first optimal algorithm, called the multi-step dual accelerated (MSDA) method, that achieves the a precision that depends on the condition number of the local functions and the (normalized) eigengap of the gossip matrix used for communication between nodes. We then verify the efficiency of MSDA against state-of-the-art methods for two problems: least-squares regression and classification by logistic regression. (joint work with Kevin Scaman, S\u00e9bastien Bubeck, Yin Tat Lee, and Laurent Massouli\u00e9)Opens in a new tab<\/span><\/p>\n Francesco Orabona – Coin Betting for Backprop without Learning rates and More<\/a><\/p>\n Regina Barzilay – How Can NLP Help Cure Cancer? (opens in new tab)<\/span><\/a><\/p>\n Aapo Hyvarinen – Nonlinear ICA using temporal structure: a principled framework for unsupervised deep learning\u00a0<\/a><\/p>\n Max Welling – Generalizing Convolutions for Deep Learning <\/a><\/p>\n Opens in a new tab<\/span><\/p>\n","protected":false},"excerpt":{"rendered":" 21 Station Road Cambridge CB1 2FB View the whole series on talks.cam (opens in new tab) Opens in a new tab Frontiers in Artificial Intelligence is a series of public lectures at Microsoft Research Cambridge featur-ing leading researchers in the field, focusing on the cutting edge topics at the intersection of machine learning, statistics, […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_startdate":"2018-01-16","msr_enddate":"2018-01-16","msr_location":"Microsoft Research Cambridge","msr_expirationdate":"","msr_event_recording_link":"","msr_event_link":"","msr_event_link_redirect":false,"msr_event_time":"13:00","msr_hide_region":true,"msr_private_event":false,"msr_hide_image_in_river":0,"footnotes":""},"research-area":[13556],"msr-region":[239178],"msr-event-type":[197944],"msr-video-type":[],"msr-locale":[268875],"msr-program-audience":[],"msr-post-option":[],"msr-impact-theme":[],"class_list":["post-451002","msr-event","type-msr-event","status-publish","hentry","msr-research-area-artificial-intelligence","msr-region-europe","msr-event-type-hosted-by-microsoft","msr-locale-en_us"],"msr_about":"\n\n 21 Station Road <\/p>\n View the whole series on talks.cam (opens in new tab)<\/span><\/a><\/p>\n Opens in a new tab<\/span><\/p>\n Frontiers in Artificial Intelligence<\/span> is a series of public lectures at Microsoft Research Cambridge featur-ing leading researchers in the field, focusing on the cutting edge topics at the intersection of machine learning, statistics, and artificial intelligence. Students, scientists, and engineers in academia and in-dustry are all welcome to join us for these exciting talks and the opportunity to socialize with the Cam-bridge AI\/ML community.<\/p>\n In this work, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized and decentralized communications over a network. For centralized (i.e. master\/slave) algorithms, we show that distributing Nesterov’s accelerated gradient descent is optimal and achieves a precision in time that depends on the condition number of the (global) function to optimize, the diameter of the network, and the time needed to communicate values between two neighbors (resp. perform local computations). For decentralized algorithms based on gossip, we provide the first optimal algorithm, called the multi-step dual accelerated (MSDA) method, that achieves the a precision that depends on the condition number of the local functions and the (normalized) eigengap of the gossip matrix used for communication between nodes. We then verify the efficiency of MSDA against state-of-the-art methods for two problems: least-squares regression and classification by logistic regression. (joint work with Kevin Scaman, S\u00e9bastien Bubeck, Yin Tat Lee, and Laurent Massouli\u00e9)Opens in a new tab<\/span><\/p>\n Francesco Orabona – Coin Betting for Backprop without Learning rates and More<\/a><\/p>\n Regina Barzilay – How Can NLP Help Cure Cancer?<\/a><\/p>\n Aapo Hyvarinen – Nonlinear ICA using temporal structure: a principled framework for unsupervised deep learning\u00a0<\/a><\/p>\n Max Welling – Generalizing Convolutions for Deep Learning <\/a><\/p>\n Opens in a new tab<\/span><\/p>\n","tab-content":[{"id":0,"name":"About","content":"Frontiers in Artificial Intelligence<\/span> is a series of public lectures at Microsoft Research Cambridge featur-ing leading researchers in the field, focusing on the cutting edge topics at the intersection of machine learning, statistics, and artificial intelligence. Students, scientists, and engineers in academia and in-dustry are all welcome to join us for these exciting talks and the opportunity to socialize with the Cam-bridge AI\/ML community.\r\n![\"\"](\"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-content\/uploads\/2017\/12\/Francis-288x300.jpg\")
<\/h3>\nOptimal algorithms for smooth and strongly convex distributed optimization in networks<\/span><\/h3>\n
Francis Bach, INRIA<\/h4>\n
\nCambridge
\nCB1 2FB<\/p>\n<\/h3>\nOptimal algorithms for smooth and strongly convex distributed optimization in networks<\/span><\/h3>\n
Francis Bach, INRIA<\/h4>\n
<\/h3>\r\nOptimal algorithms for smooth and strongly convex distributed optimization in networks<\/span><\/h3>\r\n
Francis Bach, INRIA<\/h4>\r\nIn this work, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized and decentralized communications over a network. For centralized (i.e. master\/slave) algorithms, we show that distributing Nesterov's accelerated gradient descent is optimal and achieves a precision in time that depends on the condition number of the (global) function to optimize, the diameter of the network, and the time needed to communicate values between two neighbors (resp. perform local computations). For decentralized algorithms based on gossip, we provide the first optimal algorithm, called the multi-step dual accelerated (MSDA) method, that achieves the a precision that depends on the condition number of the local functions and the (normalized) eigengap of the gossip matrix used for communication between nodes. We then verify the efficiency of MSDA against state-of-the-art methods for two problems: least-squares regression and classification by logistic regression. (joint work with Kevin Scaman, S\u00e9bastien Bubeck, Yin Tat Lee, and Laurent Massouli\u00e9)"},{"id":1,"name":"Past Speakers","content":"Francesco Orabona - Coin Betting for Backprop without Learning rates and More<\/a>\r\n\r\nRegina Barzilay - How Can NLP Help Cure Cancer?<\/a>\r\n\r\nAapo Hyvarinen - Nonlinear ICA using temporal structure: a principled framework for unsupervised deep learning\u00a0<\/a>\r\n\r\nMax Welling - Generalizing Convolutions for Deep Learning <\/a>\r\n\r\n "}],"msr_startdate":"2018-01-16","msr_enddate":"2018-01-16","msr_event_time":"13:00","msr_location":"Microsoft Research Cambridge","msr_event_link":"","msr_event_recording_link":"","msr_startdate_formatted":"January 16, 2018","msr_register_text":"Watch now","msr_cta_link":"","msr_cta_text":"","msr_cta_bi_name":"","featured_image_thumbnail":null,"event_excerpt":"Frontiers in Artificial Intelligence is a series of public lectures at Microsoft Research Cambridge featur-ing leading researchers in the field, focusing on the cutting edge topics at the intersection of machine learning, statistics, and artificial intelligence. Students, scientists, and engineers in academia and in-dustry are all welcome to join us for these exciting talks and the opportunity to socialize with the Cam-bridge AI\/ML community. Optimal algorithms for smooth and strongly convex distributed optimization in networks…","msr_research_lab":[199561],"related-researchers":[],"msr_impact_theme":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-opportunities":[],"related-publications":[],"related-videos":[],"related-posts":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/451002","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-event"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-event"}],"version-history":[{"count":4,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/451002\/revisions"}],"predecessor-version":[{"id":1147130,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/451002\/revisions\/1147130"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=451002"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=451002"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=451002"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=451002"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=451002"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=451002"},{"taxonomy":"msr-program-audience","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-program-audience?post=451002"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=451002"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=451002"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}