Sebastien Bubeck; The Entropic Bar­rier: A New and Opti­mal Uni­ver­sal Self-concordant Barrier

May 12, 2015, 4pm
GUG 204
Sebastien Bubeck, Microsoft Research, Red­mond.
The Entropic Bar­rier: A New and Opti­mal Uni­ver­sal Self-concordant Barrier

Abstract: A fun­da­men­tal result in the the­ory of Inte­rior Point Meth­ods is Nes­terov and Nemirovski’s con­struc­tion of a uni­ver­sal self-concordant bar­rier. In this talk I will intro­duce the entropic bar­rier, a new (and in some sense opti­mal) uni­ver­sal self-concordant bar­rier. The entropic bar­rier con­nects many top­ics of inter­est in Machine Learn­ing: expo­nen­tial fam­i­lies, con­vex dual­ity, log-concave dis­tri­b­u­tions, Mir­ror Descent, and expo­nen­tial weights.

Andrew Fitzgibbon; Learning about Shape

CORE Series
Mon­day, March 30, 2015, 4pm
EEB 125
Andrew Fitzgib­bon, Microsoft Research, Cam­bridge.
Learn­ing about Shape

Abstract: Vision is nat­u­rally con­cerned with shape. If we could recover a sta­ble and com­pact rep­re­sen­ta­tion of object shape from images, we would hope it might aid with numer­ous vision tasks. Just the sil­hou­ette of an object is a strong cue to its iden­tity, and the sil­hou­ette is gen­er­ated by its 3D shape. In com­puter vision, many rep­re­sen­ta­tions have been explored: col­lec­tions of points, “sim­ple” shapes like ellip­soids or poly­he­dra, alge­braic sur­faces and other implicit sur­faces, gen­er­al­ized cylin­ders and rib­bons, and piece­wise (ratio­nal) poly­no­mial rep­re­sen­ta­tions like NURBS and sub­di­vi­sion sur­faces. Many of these can be embed­ded more or less straight­for­wardly into prob­a­bilis­tic shape spaces, and recov­ery (a.k.a. “learn­ing”) of one such space is the goal of the exper­i­men­tal part of this talk.

When recov­er­ing shape from mea­sure­ments, there is at first sight a nat­ural hier­ar­chy of sta­bil­ity: straight lines can rep­re­sent very lit­tle but may be robustly recov­ered from data, then come conic sec­tions, splines with fixed knots, and gen­eral piece­wise rep­re­sen­ta­tions. I will show, how­ever, that one can pass almost imme­di­ately to piece­wise rep­re­sen­ta­tions with­out loss of robust­ness. In par­tic­u­lar, I shall show how a pop­u­lar rep­re­sen­ta­tion in com­puter graphics—subdivision curves and surfaces—may read­ily be fit to a vari­ety of image data using the tech­nique for ellipse fit­ting intro­duced by Gan­der, Golub, and Strebel in 1994. I show how we can address the previously-difficult prob­lem of recov­er­ing 3D shape from mul­ti­ple sil­hou­ettes, and the con­sid­er­ably harder prob­lem which arises when the sil­hou­ettes are not from the same object instance, but from mem­bers of an object class, for exam­ple 30 images of dif­fer­ent dol­phins each in dif­fer­ent poses. This requires that we simul­ta­ne­ously learn the shape space and the pro­jec­tions from each instance into its image. This simul­ta­ne­ous opti­miza­tion is rem­i­nis­cent of the bun­dle adjust­ment prob­lem in com­puter vision, and indeed our most recent appli­ca­tion, to track­ing the human hand, makes good use of the Ceres Solver.

Joint work with Tom Cash­man and others.

Bio: Andrew Fitzgib­bon is a prin­ci­pal researcher in the com­puter vision group at Microsoft Research Cam­bridge. He is best known for his work on 3D vision, hav­ing been a core con­trib­u­tor to the Emmy-award-winning 3D cam­era tracker “bou­jou” (www.boujou.com) and to the human body track­ing of Kinect for Xbox 360, but his inter­ests are broad, span­ning com­puter vision, graph­ics, machine learn­ing, and even a lit­tle neu­ro­science. He has pub­lished numer­ous highly-cited papers, and received many awards for his work, includ­ing 9 con­fer­ence prizes for best paper or runner-up, the Sil­ver medal of the Royal Acad­emy of Engi­neer­ing, and the British Com­puter Society’s Roger Need­ham award. He is a fel­low of the Royal Acad­emy of Engi­neer­ing, the British Com­puter Soci­ety, and the Inter­na­tional Asso­ci­a­tion for Pat­tern Recog­ni­tion. He has been pro­gram chair of CVPR and ECCV. Before join­ing Microsoft in 2005, he was a Royal Soci­ety Uni­ver­sity Research Fel­low at Oxford Uni­ver­sity, hav­ing pre­vi­ously stud­ied at Edin­burgh Uni­ver­sity, Heriot-Watt Uni­ver­sity, and Uni­ver­sity Col­lege, Cork.

Jiashan Wang; Iterative Re-weighted Linear Least Squares for Exact Penalty Subproblems on Product Sets

March 10, 2015, 4:00pm
GUG 204
Jiashan Wang, Depart­ment of Math­e­mat­ics, UW.
Iter­a­tive Re-weighted Lin­ear Least Squares for Exact Penalty Sub­prob­lems on Prod­uct Sets

Abstract: We present two matrix-free meth­ods for solv­ing exact penalty sub­prob­lems on prod­uct sets that arise when solv­ing large-scale opti­miza­tion prob­lems. The first approach is a novel iter­a­tive re-weighting algo­rithm (IRWA), which iter­a­tively min­i­mizes qua­dratic mod­els of relaxed sub­prob­lems while auto­mat­i­cally updat­ing a relax­ation vec­tor. The sec­ond approach is based on alter­nat­ing direc­tion aug­mented Lagrangian (ADAL) tech­nol­ogy applied to our set­ting. The main com­pu­ta­tional costs of each algo­rithm are the repeated min­i­miza­tions of con­vex qua­dratic func­tions which can be per­formed matrix-free. We prove that both algo­rithms are glob­ally con­ver­gent under loose assump­tions, and that each requires at most $O(1/\varepsilon^2)$ iter­a­tions to reach $\varepsilon$-optimality of the objec­tive func­tion. Numer­i­cal exper­i­ments exhibit the abil­ity of both algo­rithms to effi­ciently find inex­act solu­tions. How­ever, in cer­tain cases, these exper­i­ments indi­cate that IRWA can be sig­nif­i­cantly more effi­cient than ADAL.

Joint work with James Burke, Frank Cur­tis, and Hao Wang.

Emily Fox; Leveraging Optimization Techniques to Scale Bayesian Inference

Feb­ru­ary 24, 2015, 4:00pm
GUG 204
Emily Fox, Depart­ment of Sta­tis­tics, UW.
Lever­ag­ing Opti­miza­tion Tech­niques to Scale Bayesian Inference

Abstract: Data streams of increas­ing com­plex­ity are being col­lected in a vari­ety of fields rang­ing from neu­ro­science, genomics, and envi­ron­men­tal mon­i­tor­ing to e-commerce based on tech­nolo­gies and infra­struc­tures pre­vi­ously unavail­able. With the advent of Markov chain Monte Carlo (MCMC) com­bined with the com­pu­ta­tional power to imple­ment such algo­rithms, deploy­ing increas­ingly expres­sive mod­els has been a focus in recent decades. Unfor­tu­nately, tra­di­tional algo­rithms for Bayesian infer­ence in these mod­els such as MCMC and vari­a­tional infer­ence do not typ­i­cally scale to the large datasets encoun­tered in prac­tice. Like­wise, these algo­rithms are not applic­a­ble to the increas­ingly com­mon sit­u­a­tion where an unbounded amount of data arrive as a stream and infer­ences need to be made on-the-fly. In this talk, we will present a series of algo­rithms— sto­chas­tic gra­di­ent Hamil­ton­ian Monte Carlo, HMM sto­chas­tic vari­a­tional infer­ence, and stream­ing Bayesian non­para­met­ric infer­ence— to address var­i­ous aspects of the chal­lenge in scal­ing Bayesian infer­ence; our algo­rithms focus on deploy­ing sto­chas­tic gra­di­ents and work­ing within an opti­miza­tion frame­work. We demon­strate our meth­ods on a vari­ety of appli­ca­tions includ­ing online movie rec­om­men­da­tions, seg­ment­ing a human chro­matin data set with 250 mil­lion obser­va­tions, and clus­ter­ing a stream of New York Times documents.

Joint work with Tianqi Chen, Nick Foti, Dil­lon Laird, Alex Tank, and Jason Xu.

Hon Leung Lee; Minimizing Distance to an Orthogonally Invariant Matrix Set

Jan­u­ary 27, 2015, 4:00pm
GUG 204
Hon Leung Lee, Depart­ments of Math­e­mat­ics, UW.
Min­i­miz­ing Dis­tance to an Orthog­o­nally Invari­ant Matrix Set

Abstract: The prob­lem of find­ing the clos­est point in a set, with respect to Euclid­ean dis­tance, arises fre­quently in appli­ca­tions. In this talk we focus on orthog­o­nally invari­ant matrix sets and pro­vide a frame­work for com­put­ing and count­ing the real smooth crit­i­cal points of this min­i­miza­tion prob­lem, as well as find­ing the min­i­miz­ers. The key results are the “trans­fer prin­ci­ples” that allow cal­cu­la­tions to be done in the Euclid­ean space con­tain­ing the vec­tors of sin­gu­lar val­ues of the mem­bers in the matrix set. Run­ning exam­ples include Eckart-Young the­o­rem and find­ing the near­est essen­tial matrix. This is a joint work with Dmitriy Drusvy­atskiy and Rekha Thomas.