Upcoming Talks 2014

Jan­u­ary 14
Thomas Rothvoss, Depart­ment of Math­e­mat­ics, MIT.
The match­ing poly­tope has expo­nen­tial exten­sion complexity

Jan­u­ary 21
Mary Beth Hribar, Microsoft.
Adven­tures in the Unknown, My Career in Indus­try after an Opti­miza­tion Dissertation

Jan­u­ary 28
Samet Oymak, Depart­ment of Elec­tri­cal Engi­neer­ing, Cal­tech.
A Gen­eral The­ory of Noisy Lin­ear Inverse Problems

Feb­ru­ary 11
Mario Micheli, Depart­ment of Math­e­mat­ics, UW.
An Opti­miza­tion Approach for Image Recov­ery Through Opti­cal Turbulence

Feb­ru­ary 21 [MAC]
Maryam Fazel, Depart­ment of Elec­tri­cal Engi­neer­ing, UW.
Fill­ing In the Gaps: Recov­ery from Incom­plete Information

Feb­ru­ary 25
Marina Meila, Depart­ment of Sta­tis­tics, UW.
Opti­miza­tion for Ordered Data

March 18
Dvi­jotham Krish­na­murthy, Depart­ment of Com­puter Sci­ence and Engi­neer­ing, UW.
Con­vex For­mu­la­tions of Con­troller Synthesis

March 31 [CORE]
David Blei, Depart­ment of Com­puter Sci­ence, Prince­ton Uni­ver­sity.
Prob­a­bilis­tic Topic Mod­els of Text and Users

April 8
Rishabh Iyer, Depart­ment of Elec­tri­cal Engi­neer­ing, UW.
Sub­mod­u­lar Com­bi­na­to­r­ial Prob­lems in Machine Learn­ing: Algo­rithms and Applications

April 15 [CORE]
San­jeev Arora, Depart­ment of Com­puter Sci­ence, Prince­ton Uni­ver­sity.
Over­com­ing Intractabil­ity in Unsu­per­vised Learning

April 22
Hongbo Dong, Depart­ment of Math­e­mat­ics, Wash­ing­ton State Uni­ver­sity.
A New Approach to Relax Non­con­vex Quadratics

April 29
Rina Foygel, Depart­ment of Sta­tis­tics, Uni­ver­sity of Chicago.
Demix­ing sig­nals: the geom­e­try of cor­rupted sensing

May 2–3
West Coast Opti­miza­tion Meeting

May 9 [MAC]
Dan Spiel­man, Depart­ment of Com­puter Sci­ence, Yale Uni­ver­sity.
Phys­i­cal metaphors for graphs and networks

May 13
Noah Simon, Depart­ment of Bio­sta­tis­tics, Uni­ver­sity of Wash­ing­ton.

May 27
Tim Hoheisel, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Wurzburg.

Click on the title or see below for the abstracts.

Rina Foygel; Demixing signals: the geometry of corrupted sensing

April 29, 2014, 4:00pm
EEB 303
Rina Foygel, Depart­ment of Sta­tis­tics, Uni­ver­sity of Chicago.
Demix­ing sig­nals: the geom­e­try of cor­rupted sensing

Abstract: In the com­pressed sens­ing prob­lem, a high-dimensional sig­nal with under­ly­ing struc­ture can often be recov­ered with a small num­ber of lin­ear mea­sure­ments. When mul­ti­ple struc­tured sig­nals are super­im­posed, sim­i­lar tech­niques can be used to try to sep­a­rate the sig­nals at a low sam­ple size. We extend the­o­ret­i­cal work on com­pressed sens­ing to the cor­rupted sens­ing prob­lem, where our mea­sure­ments of a struc­tured sig­nal are cor­rupted in a struc­tured way (such as a sparse set of out­liers in the mea­sure­ments). Con­vex penal­ties placed on the sig­nal and the cor­rup­tion reflect their respec­tive latent struc­ture (e.g. spar­sity, block-wise spar­sity, low rank, etc). The result­ing penal­ized opti­miza­tion prob­lem involves a tun­ing para­me­ter con­trol­ling the trade­off between the two penal­ties. We find that this tun­ing para­me­ter can be cho­sen by com­par­ing geo­met­ric prop­er­ties of the two types of struc­ture, which requires no cross-validation and yields nearly opti­mal results in the­ory and in simulations.

Joint work with Lester Mackey.

Sanjeev Arora; Overcoming Intractability in Unsupervised Learning

April 15th, 2014, 4:00pm
CSE 691 (The Gates Com­mons)
San­jeev Arora, Depart­ment of Com­puter Sci­ence, Prince­ton.
Over­com­ing Intractabil­ity in Unsu­per­vised Learning

Abstract: Unsu­per­vised learn­ing – i.e., learn­ing with unla­beled data – is increas­ingly impor­tant given today’s data del­uge. Most nat­ural prob­lems in this domain – e.g. for mod­els such as mix­ture mod­els, HMMs, graph­i­cal mod­els, topic mod­els and sparse coding/dictionary learn­ing, deep learn­ing – are NP-hard. There­fore researchers in prac­tice use either heuris­tics or con­vex relax­ations with no con­crete approx­i­ma­tion bounds. Sev­eral non­con­vex heuris­tics work well in prac­tice, which is also a mystery.

The talk will describe a sequence of recent results whereby rig­or­ous approaches lead­ing to poly­no­mial run­ning time are pos­si­ble for sev­eral prob­lems in unsu­per­vised learn­ing. The proof of poly­no­mial run­ning time usu­ally relies upon non­de­gen­er­acy assump­tions on the data and the model para­me­ters, and often also on sto­chas­tic prop­er­ties of the data (average-case analy­sis). Some of these new algo­rithms are very effi­cient and prac­ti­cal – e.g. for topic modeling.

Bios­ketch: San­jeev Arora is the Charles C. Fitz­mor­ris Pro­fes­sor of Com­puter Sci­ence at Prince­ton Uni­ver­sity. His research spans The­o­ret­i­cal Com­puter Sci­ence, includ­ing foun­da­tional work in Algo­rithms and Com­pu­ta­tional Com­plex­ity. His recent work focuses on prov­able bounds for Machine Learn­ing. He has received numer­ous awards and dis­tinc­tion. Most recently, these include the 2012 Fulk­er­son Prize, the 2011 ACM-Infosys Foun­da­tion Award in Com­put­ing Sci­ences, the 2010 Goedel Prize, and the Best Paper Award at the 2010 Annual Sym­po­sium on Foun­da­tions of Com­put­ing. He is an ACM Fel­low and recip­i­ent of the 1995 ACM Doc­toral Dis­ser­ta­tion Award.

Hongbo Dong; A New Approach to Relax Nonconvex Quadratics

April 22, 2014, 4:00pm
EEB 303
Hongbo Dong, Depart­ment of Math­e­mat­ics, Wash­ing­ton State Uni­ver­sity. 
A New Approach to Relax Non­con­vex Quadratics

Abstract: In many areas of engi­neer­ing and com­puter sci­ences, opti­miza­tion mod­els with non­con­vex qua­dratic func­tions nat­u­rally arise, such as var­i­ous mod­els related to process net­works in Chem­i­cal Engi­neer­ing, com­pu­ta­tional geom­e­try, as well as cut­ting and par­ti­tion­ing of graphs. Tractable con­vex relax­ations are often cru­cial when the global opti­mal solu­tion or a good approx­i­mate solu­tion is of inter­ests. How­ever, most cur­rent relax­ation meth­ods based on lifting/linearization are bot­tle­necked by the huge amount of addi­tional vari­ables intro­duced, espe­cially when there are dense qua­drat­ics with a mod­er­ate num­ber of vari­ables (n >= 70).

In this talk, we will first describe a few sce­nar­ios where non­con­vex qua­drat­ics nat­u­rally arise. Then we will briefly overview some state-of-the-art relax­ation meth­ods based on poly­he­dral as well as semi­def­i­nite tech­niques. Finally I will intro­duce a novel cut­ting sur­face approach to derive con­vex qua­dratic relax­ations. Our approach uses diag­o­nal per­tur­ba­tions of the qua­drat­ics as cut­ting sur­faces that are iter­a­tively added into relax­ations. We devise a spe­cial­ized heuris­tic algo­rithm to search for good cut­ting sur­faces, where each iter­a­tion needs only O(n^2) flops. Com­pu­ta­tional results show promises of our new approach, espe­cially when large dense qua­drat­ics are present. We show that on a model with one non­con­vex qua­dratic func­tion, only a small num­ber of cut­ting sur­faces are needed to cap­ture the most strength of a semi­def­i­nite relax­ation, while our approach is much more scal­able. We also com­pare with another approach that gen­er­ates con­vex cut­ting sur­faces pro­posed by (Sax­ena, Bonami and Lee, 2011). We obtain slightly weaker bounds but in 1–2 orders of mag­ni­tude shorter time. Finally, we also dis­cuss how to incor­po­rate our meth­ods into a gen­eral branch-and-bound solver for mixed-integer qua­drat­i­cally con­strained pro­grams (MIQCP).

This work is based on our recent sub­mis­sion avail­able here.

David Blei; Probabilistic Topic Models of Text and Users

Mon­day, March 31st, 2014, 3:30pm
EEB 125
David Beli, Depart­ment of Com­puter Sci­ence, Prince­ton.
Prob­a­bilis­tic Topic Mod­els of Text and Users

Abstract: Prob­a­bilis­tic topic mod­els pro­vide a suite of tools for ana­lyz­ing large doc­u­ment col­lec­tions. Topic mod­el­ing algo­rithms dis­cover the latent themes that under­lie the doc­u­ments and iden­tify how each doc­u­ment exhibits those themes. Topic mod­el­ing can be used to help explore, sum­ma­rize, and form pre­dic­tions about documents.

Tra­di­tional topic mod­el­ing algo­rithms ana­lyze a doc­u­ment col­lec­tion and esti­mate its latent the­matic struc­ture. How­ever, many col­lec­tions con­tain an addi­tional type of data: how peo­ple use the doc­u­ments. For exam­ple, read­ers click on arti­cles in a news­pa­per web­site, sci­en­tists place arti­cles in their per­sonal libraries, and law­mak­ers vote on a col­lec­tion of bills. Behav­ior data is essen­tial both for mak­ing pre­dic­tions about users (such as for a rec­om­men­da­tion sys­tem) and for under­stand­ing how a col­lec­tion and its users are organized.

In this talk, I will review the basics of topic mod­el­ing and describe our recent research on col­lab­o­ra­tive topic mod­els, mod­els that simul­ta­ne­ously ana­lyze a col­lec­tion of texts and its cor­re­spond­ing user behav­ior. We stud­ied col­lab­o­ra­tive topic mod­els on 80,000 sci­en­tists’ libraries, a col­lec­tion that con­tains 250,000 articles.

With this analy­sis, I will show how we can build inter­pretable rec­om­men­da­tion sys­tems that point sci­en­tists to arti­cles they will like. Fur­ther, the same analy­sis lets us orga­nize the sci­en­tific lit­er­a­ture accord­ing to dis­cov­ered pat­terns of read­er­ship. For exam­ple, we can iden­tify arti­cles impor­tant within a field and arti­cles that tran­scend dis­ci­pli­nary boundaries.

More broadly, topic mod­el­ing is a case study in the large field of applied prob­a­bilis­tic mod­el­ing. Finally, I will sur­vey some recent advances in this field. I will show how mod­ern prob­a­bilis­tic mod­el­ing gives data sci­en­tists a rich lan­guage for express­ing sta­tis­ti­cal assump­tions and scal­able algo­rithms for uncov­er­ing hid­den pat­terns in mas­sive data.

Bios­ketch: David Blei is an asso­ciate pro­fes­sor of Com­puter Sci­ence at Prince­ton Uni­ver­sity. He earned his Bachelor’s degree in Com­puter Sci­ence and Math­e­mat­ics from Brown Uni­ver­sity and his PhD in Com­puter Sci­ence from the Uni­ver­sity of Cal­i­for­nia, Berke­ley. His research focuses on prob­a­bilis­tic topic mod­els, Bayesian non­para­met­ric meth­ods, and approx­i­mate pos­te­rior infer­ence. He works on a vari­ety of appli­ca­tions, includ­ing text, images, music, social net­works, user behav­ior, and sci­en­tific data.

Rishabh Iyer; Submodular Combinatorial Problems in Machine Learning: Algorithms and Applications

April 8, 2014, 4:00pm
EEB 303
Rishabh IyerDepart­ment of Elec­tri­cal Engi­neer­ing, UW
Sub­mod­u­lar Com­bi­na­to­r­ial Prob­lems in Machine Learn­ing: Algo­rithms and Applications

Abstract: Hav­ing long been rec­og­nized in com­bi­na­torics, the con­cept of sub­mod­u­lar­ity is becom­ing increas­ingly impor­tant in machine learn­ing, since it can cap­ture intu­itive and yet non­triv­ial inter­ac­tions between vari­ables. This expres­sive­ness has found many appli­ca­tions in machine learn­ing, par­tic­u­larly in under­stand­ing struc­tured data like text, vision and speech. Sub­mod­u­lar func­tions nat­u­rally cap­ture aspects of infor­ma­tion, cov­er­age and diver­sity in max­i­miza­tion prob­lems, while also mod­el­ing notions of coop­er­a­tion, spar­sity, com­plex­ity and economies of scale in min­i­miza­tion prob­lems. In this talk, we shall con­sider a large class of sub­mod­u­lar opti­miza­tion prob­lems and moti­vate them with sev­eral real world appli­ca­tions, par­tic­u­larly in machine learn­ing. We shall then pro­vide a uni­fy­ing algo­rith­mic frame­work for solv­ing sev­eral of these opti­miza­tion prob­lems, and high­light the scal­a­bil­ity and prac­ti­cal­ity of this approach. We shall also high­light novel the­o­ret­i­cal char­ac­ter­i­za­tions, which pro­vide bet­ter con­nec­tions between the­ory and prac­tice. We shall ground this entire talk with a large num­ber of appli­ca­tions in machine learn­ing, includ­ing image seg­men­ta­tion, image cor­re­spon­dence, image col­lec­tion sum­ma­riza­tion, fea­ture selec­tion, and data sub­set selec­tion. This talk should be self con­tained and shall not require prior knowl­edge of sub­mod­u­lar func­tions and optimization.

This is based on joint work with Jeff Bilmes, Ste­fanie Jegelka, Sebas­t­ian Tschi­atschek and Kai Wei.

Bio: Rishabh Iyer is a Ph.D can­di­date at the Uni­ver­sity of Wash­ing­ton, Seat­tle, where he works with Jeff Bilmes. His main inter­ests are in the­o­ret­i­cal and applied aspects of Dis­crete Opti­miza­tion and specif­i­cally sub­mod­u­lar­ity  with appli­ca­tions in Machine Learn­ing, Com­puter Vision and Speech. He received his MS from Uni­ver­sity of Wash­ing­ton in 2013, and his B.Tech from IIT-Bombay in 2011. He has been a vis­i­tor at Microsoft Research, Red­mond and Simon Fraser Uni­ver­sity. His work on sub­mod­u­lar opti­miza­tion has received numer­ous awards includ­ing the Microsoft Research Fel­low­ship award, the Face­book Fel­low­ship award and best paper awards at the Inter­na­tional Con­fer­ence for Machine Learn­ing (ICML) and Neural Infor­ma­tion Pro­cess­ing Sys­tems (NIPS).

Marina Meila; Optimization for Ordered Data

Feb­ru­ary 25, 2014, 4:00pm
Guggen­heim 218
Marina MeilaDepart­ment of Sta­tis­tics, UW
Opti­miza­tion for Ordered Data

This talk is con­cerned with sum­ma­riz­ing — by means of sta­tis­ti­cal mod­els — of data that expresses pref­er­ences. This data is typ­i­cally a set of rank­ings of n items by a panel of experts; the sim­plest sum­mary is the “con­sen­sus rank­ing”, or the “cen­troid” of the set of rankings.

I will describe how com­bi­na­torics, algo­rithms and sta­tis­tics come together in this endeavor. At the cen­ter of the results is the _code_ of a per­mu­ta­tion. This nat­ural math­e­mat­i­cal way to rep­re­sent a per­mu­ta­tion is key both to fast com­put­ing and to bet­ter under­stand­ing the mod­els we cre­ate. The mod­els have per­mu­ta­tions _as parameters_ and fit­ting them to data leads to com­bi­na­to­r­ial opti­miza­tion prob­lems which are often NP-hard. The talk will intro­duce a class of algo­rithms to attack these prob­lems, that are exact but intractable in the worst case, and will demon­strate that they are effec­tive on real-world examples.

Joint work with Alnur Ali, Raman Arora, Le Bao, Jeff Bilmes, Harr Chen, Bhushan Mand­hani, Chris Meek, Bren­dan Mur­phy, Kapil Phad­nis, Arthur Patterson.