Fall 2015 Calendar

Octo­ber 13 [CORE]
Michael Over­ton, Courant Insti­tute of Math­e­mat­i­cal Sci­ences, New York Uni­ver­sity
Non­smooth, Non­con­vex Opti­miza­tion: Algo­rithms and Examples

Octo­ber 20
Sasha Aravkin, Depart­ment of Applied Math­e­mat­ics, Uni­ver­sity of Wash­ing­ton
An Inte­rior Point Approach for Data Science

Octo­ber 27
Damek Davis, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Cal­i­for­nia, Los Ange­les
A Three-Operator Split­ting Scheme and its Opti­miza­tion Applications

Novem­ber 10
James Saun­der­son, Depart­ment of Elec­tri­cal Engi­neer­ing, Uni­ver­sity of Wash­ing­ton
Semi­def­i­nite descrip­tions of reg­u­lar poly­gons (and beyond)

Novem­ber 24 [CORE]
Pedro Domin­gos, Depart­ment of Com­puter Sci­ence and Engi­neer­ing, Uni­ver­sity of Wash­ing­ton
Non­smooth, Non­con­vex Opti­miza­tion: Algo­rithms and Examples

Decem­ber 8
Vic­tor Falgas-Ravry, Depart­ment of Math­e­mat­ics, Van­der­bilt University

Pedro Domingos; Recursive Decomposition for Nonconvex Optimization

CORE Series
Tues­day, Novem­ber 24, 2015, 4:00 pm
Gowen Hall, Room 201
Pedro Domin­gos,Uni­ver­sity of Wash­ing­ton.
Recur­sive Decom­po­si­tion for Non­con­vex Optimization

ABSTRACT: Most real-world con­tin­u­ous opti­miza­tion prob­lems are non­con­vex, caus­ing stan­dard con­vex tech­niques to find only local optima, even with exten­sions like ran­dom restarts and sim­u­lated anneal­ing. We observe that, in many cases, the local modes of the objec­tive func­tion have com­bi­na­to­r­ial struc­ture, and thus ideas from com­bi­na­to­r­ial opti­miza­tion can be brought to bear. Based on this, we pro­pose a problem-decomposition approach to non­con­vex opti­miza­tion. Sim­i­larly to DPLL-style SAT solvers and recur­sive con­di­tion­ing in prob­a­bilis­tic infer­ence, our algo­rithm, RDIS, recur­sively sets vari­ables so as to sim­plify and decom­pose the objec­tive func­tion into approx­i­mately inde­pen­dent sub­func­tions, until the remain­ing func­tions are sim­ple enough to be opti­mized by stan­dard tech­niques like gra­di­ent descent. The vari­ables to set are cho­sen by graph par­ti­tion­ing, ensur­ing decom­po­si­tion when­ever pos­si­ble. We show ana­lyt­i­cally that RDIS can solve a broad class of non­con­vex opti­miza­tion prob­lems expo­nen­tially faster than gra­di­ent descent with ran­dom restarts. Exper­i­men­tally, RDIS out­per­forms stan­dard tech­niques on prob­lems like struc­ture from motion and pro­tein folding.

Bio: Pedro Domin­gos is a pro­fes­sor of com­puter sci­ence at the Uni­ver­sity of Wash­ing­ton and the author of “The Mas­ter Algo­rithm”. He is a win­ner of the SIGKDD Inno­va­tion Award, the high­est honor in data sci­ence. He is a Fel­low of the Asso­ci­a­tion for the Advance­ment of Arti­fi­cial Intel­li­gence, and has received a Ful­bright Schol­ar­ship, a Sloan Fel­low­ship, the National Sci­ence Foundation’s CAREER Award, and numer­ous best paper awards. He received his Ph.D. from the Uni­ver­sity of Cal­i­for­nia at Irvine and is the author or co-author of over 200 tech­ni­cal pub­li­ca­tions. He has held vis­it­ing posi­tions at Stan­ford, Carnegie Mel­lon, and MIT. He co-founded the Inter­na­tional Machine Learn­ing Soci­ety in 2001. His research spans a wide vari­ety of top­ics in machine learn­ing, arti­fi­cial intel­li­gence, and data sci­ence, includ­ing scal­ing learn­ing algo­rithms to big data, max­i­miz­ing word of mouth in social net­works, uni­fy­ing logic and prob­a­bil­ity, and deep learning.

Semidefinite descriptions of regular polygons (and beyond), James Saunderson

Tues­day, Novem­ber 10, 2015, 4:00 pm
GUG 204

James Saun­der­son, Uni­ver­sity of Wash­ing­ton .
Semi­def­i­nite descrip­tions of reg­u­lar poly­gons (and beyond)

Abstract: This talk is focused on describ­ing cer­tain poly­topes as the fea­si­ble regions of semi­def­i­nite pro­grams (SDPs). The poly­topes of inter­est arise from abelian groups in a nat­ural way and include reg­u­lar poly­gons in the plane, par­ity poly­topes, cer­tain cyclic poly­topes, and cut poly­topes. These poly­topes pro­vide excel­lent exam­ples through which we can exam­ine gen­eral ques­tions about the rel­a­tive expres­sive power of semi­def­i­nite pro­gram­ming vs lin­ear pro­gram­ming, the role of sym­me­try in semi­def­i­nite descrip­tions, and dif­fer­ences in the size of descrip­tions based on the Lasserre hier­ar­chy and those based on gen­eral SDPs.

In this talk I will describe a com­bi­na­to­r­ial way to con­struct such semi­def­i­nite descrip­tions for this fam­ily of poly­topes. When applied to the nth cut poly­tope we obtain a proof that the Lasserre hier­ar­chy is exact after \lceil n/2\rceil rounds (estab­lish­ing a con­jec­ture of Lau­rent). When applied to trigono­met­ric cyclic poly­topes we obtain semi­def­i­nite descrip­tions that are sig­nif­i­cantly smaller than any pos­si­ble lin­ear pro­gram­ming descrip­tions of these polytopes.

Based on joint work with Hamza Fawzi and Pablo Parrilo

A Three-Operator Splitting Scheme and its Optimization Applications, Damek Davis

Tues­day, Octo­ber 27, 2015, 4:00 pm
GUG 204

Damek Davis, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Cal­i­for­nia, Los Ange­les .
A Three-Operator Split­ting Scheme and its Opti­miza­tion Applications

Abstract: For over 50 years, operator-splitting schemes have been used to solve PDE, fea­si­bil­ity prob­lems, and more recently, large-scale prob­lems in data analy­sis. Despite much devel­op­ment, it is known that most exist­ing split­ting schemes reduce to one of three basic schemes, each intro­duced between 15 and 36 years ago.

We intro­duce a new split­ting scheme that extends the Douglas-Rachford and forward-backward split­ting schemes to monot­one inclu­sions with three oper­a­tors, one of which is coco­er­cive. We dis­cuss why this algo­rithm works, derive sev­eral spe­cial cases, includ­ing a sim­ple three-block ADMM algo­rithm, and intro­duce an accel­er­a­tion that achieves the opti­mal rate of con­ver­gence for strongly monot­one inclu­sions. Finally, we dis­cuss sev­eral appli­ca­tions and future research directions.

An Interior Point Approach for Data Science, Sasha Aravkin

Tues­day, Octo­ber 20, 2015, 4:00 pm
GUG 204

Sasha Aravkin, Uni­ver­sity of Wash­ing­ton .
An Inte­rior Point Approach for Data Science

Abstract: Many impor­tant appli­ca­tions can be for­mu­lated as large-scale opti­miza­tion prob­lems, includ­ing clas­si­fi­ca­tion in machine learn­ing, data assim­i­la­tion in weather pre­dic­tion, inverse prob­lems, and med­ical and seis­mic imag­ing. While first-order meth­ods have proven widely suc­cess­ful in recent years, recent devel­op­ments sug­gest that matrix-free second-order meth­ods, such as interior-point meth­ods, can be competitive.

We first develop a mod­el­ing frame­work for a wide range of prob­lems, and show how con­ju­gate rep­re­sen­ta­tions can be exploited to design an inte­rior point approach for this class. We then show sev­eral appli­ca­tions, with empha­sis on mod­el­ing and prob­lem struc­ture, and end by dis­cussing exten­sions to large-scale problems.

Michael Overton; Nonsmooth, Nonconvex Optimization: Algorithms and Examples

CORE Series
Tues­day, Octo­ber 13, 2015, 4:00 pm
Raitt Hall (RAI), Room 121
Michael Over­ton, New York Uni­ver­sity .
Non­smooth, Non­con­vex Opti­miza­tion: Algo­rithms and Examples

Abstract: In many appli­ca­tions one wishes to min­i­mize an objec­tive func­tion that is not con­vex and is not dif­fer­en­tiable at its min­i­miz­ers.
We dis­cuss two algo­rithms for min­i­miza­tion of non­smooth, non­con­vex func­tions. Gra­di­ent Sam­pling is a sim­ple method that, although com­pu­ta­tion­ally inten­sive, has a nice con­ver­gence theory.The method is robust and the con­ver­gence the­ory has recently been extended to con­strained prob­lems. BFGS is a well known method, devel­oped for smooth prob­lems, but which is remark­ably effec­tive for non­smooth prob­lems too. Although our the­o­ret­i­cal results in the non­smooth case are quite lim­ited, we have made some remark­able empir­i­cal obser­va­tions and have had broad suc­cess in appli­ca­tions. Lim­ited Mem­ory BFGS is a pop­u­lar exten­sion for large prob­lems, and it is also applic­a­ble to the non­smooth case, although our expe­ri­ence with it is more mixed.
Through­out the talk we illus­trate the ideas through exam­ples,
some very easy and some very chal­leng­ing. Our work is
with Jim Burke (U. Wash­ing­ton) and Adrian Lewis (Cornell).

Bio: Michael L. Over­ton is Pro­fes­sor of Com­puter Sci­ence and Math­e­mat­ics at the Courant Insti­tute of Math­e­mat­i­cal Sci­ences, New York Uni­ver­sity. He received his Ph.D. in Com­puter Sci­ence from Stan­ford Uni­ver­sity in 1979.
He is a fel­low of SIAM (Soci­ety for Indus­trial and Applied Math­e­mat­ics) and of the IMA (Insti­tute of Math­e­mat­ics and its Appli­ca­tions, UK). He served on the Coun­cil and Board of Trustees of SIAM from 1991 to 2005, includ­ing a term as Chair of the Board from 2004 to 2005. He served as Editor-in-Chief of SIAM Jour­nal on Opti­miza­tion from 1995 to 1999 and of the IMA Jour­nal of Numer­i­cal Analy­sis from 2007 to 2008, and was the Editor-in-Chief of the MPS(Mathematical Pro­gram­ming Society)-SIAM joint book series from 2003 to 2007. He is cur­rently an edi­tor of SIAM Jour­nal on Matrix Analy­sis and Appli­ca­tions, IMA Jour­nal of Numer­i­cal Analy­sis, Foun­da­tions of Com­pu­ta­tional Math­e­mat­ics, and Numerische Math­e­matik. His research inter­ests are at the inter­face of opti­miza­tion and
lin­ear alge­bra, espe­cially non­smooth opti­miza­tion prob­lems involv­ing eigen­val­ues, pseu­dospec­tra, sta­bil­ity and robust con­trol. He is the author of “Numer­i­cal Com­put­ing with IEEE Float­ing Point Arith­metic” (SIAM, 2001).

Jonathan Kelner; Bridging the Numerical and the Combinatorial: Emerging Tools, Techniques, and Design Principles for Graph Algorithms

CORE Series
May 19, 2015, 4:00pm
EEB 125
Jonathan Kel­ner, Depart­ment of Math­e­mat­ics, MIT.
Bridg­ing the Numer­i­cal and the Com­bi­na­to­r­ial: Emerg­ing Tools, Tech­niques, and Design Prin­ci­ples for Graph Algorithms

Abstract: Flow and cut prob­lems on graphs are among the most fun­da­men­tal and exten­sively stud­ied prob­lems in Oper­a­tions Research and Opti­miza­tion, play­ing a foun­da­tional role in both the the­ory and prac­tice of algo­rithm design. While the clas­si­cal algo­rithms for these prob­lems were largely based on com­bi­na­to­r­ial approaches, the past sev­eral years have wit­nessed the emer­gence of a pow­er­ful col­lec­tion of new tech­niques based on geom­e­try, spec­tral graph the­ory, com­pu­ta­tional lin­ear alge­bra, ran­dom­iza­tion, and iter­a­tive meth­ods from con­tin­u­ous opti­miza­tion. These numer­i­cal tech­niques have allowed researchers to pro­vide bet­ter prov­able algo­rithms for a wide range of graph prob­lems, in some cases break­ing algo­rith­mic bar­ri­ers that had stood for sev­eral decades.

The rela­tion­ship between graph the­ory and numer­i­cal analy­sis has proven fruit­ful in the other direc­tion as well. In addi­tion to pro­vid­ing numer­i­cal tech­niques for graph algo­rithms, it has given rise to new com­bi­na­to­r­ial tech­niques for com­pu­ta­tional lin­ear alge­bra. In par­tic­u­lar, it has led to fast algo­rithms for Lapla­cian lin­ear sys­tems, which have broad appli­ca­tions in numer­i­cal sci­en­tific com­put­ing, machine learn­ing, oper­a­tions research, com­puter vision, and net­work analy­sis, among others.

In this talk, I dis­cuss some of the recur­ring themes that arise in this con­flu­ence of fields. I will apply these to sketch algo­rithms that run in close to lin­ear time for two basic algo­rith­mic prob­lems: solv­ing Lapla­cian lin­ear sys­tems and find­ing approx­i­mately max­i­mum flows on undi­rected graphs.

The talk will be based on joint work with Yin Tat Lee, Aaron Sid­ford, Lorenzo Orec­chia, and Zeyuan Zhu.

Bio: Jonathan Kel­ner is an Asso­ciate Pro­fes­sor of Applied Math­e­mat­ics in the MIT Depart­ment of Math­e­mat­ics and a mem­ber of the MIT Com­puter Sci­ence and Arti­fi­cial Intel­li­gence Lab­o­ra­tory (CSAIL). His research focuses on the appli­ca­tion of tech­niques from pure math­e­mat­ics to the solu­tion of fun­da­men­tal prob­lems in algo­rithms and com­plex­ity the­ory. He was an under­grad­u­ate at Har­vard Uni­ver­sity, and he received his Ph.D. in Com­puter Sci­ence from MIT in 2006. Before join­ing the MIT fac­ulty, he spent a year as a mem­ber of the Insti­tute for Advanced Study. He has received a vari­ety of awards for his work, includ­ing an NSF CAREER Award, an Alfred P. Sloan Research Fel­low­ship, the Best Paper Awards at STOC 2011, SIGMETRICS 2011, and SODA 2014, the Harold E. Edger­ton Fac­ulty Achieve­ment Award, and the MIT School of Sci­ence Teach­ing Prize.