[Theory] REMINDER: [TTIC Talks] 4/12 Talks at TTIC: Moïse Blanchard, MIT

[Brandie Jones]

*When:*         Wednesday, April 12th* at 11:30pm CT  *


*Where:*       Talk will be given *live, in-person* at

                       TTIC, 6045 S. Kenwood Avenue

                       5th Floor, Room 530


*Virtually:*     via Panopto (Livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=cd2f77ce-e4f2-4a4b-a237-afbd011d2668>
)


*Who:          *Moïse Blanchard, Massachusetts Institute of Technology


*Title:*           Convex optimization with constrained memory: Is cutting
planes optimal?


*Abstract:   *Cutting plane methods such as the center-of-mass method are
known to achieve the optimal O(d log 1/ε) oracle complexity to solve convex
optimization problems in dimension d to accuracy ε. In practice, however,
these methods are seen as impractical due to their large runtime per
iteration and the large memory they require. A natural question is whether
one can improve the practicality of these methods while keeping optimal
oracle complexity, which we aim to address through the lens of memory. We
show that first-order convex optimization inherently requires full memory
by giving information-theoretic lower bounds for the
oracle-complexity/memory tradeoff. In particular, the center-of-mass
cutting-planes algorithm that uses quadratic memory is Pareto-optimal up to
logarithmic factors. Our techniques also extend to the feasibility problem
for which we can give stronger lower bounds.


*Bio:*     Moïse is a fourth-year PhD student in the Operations Research
Center and Laboratory for Information and Decision Systems at MIT, where he
is advised by Prof. Patrick Jaillet. My research interests lie at the
intersection of learnability in machine learning and statistics, online
algorithms and optimization in decision-making. Prior to my PhD, I
graduated as the valedictorian of Ecole Polytechnique in 2019 with a M.S.
degree in Applied Mathematics, and a B.S. degree in Mathematics, Computer
Science and Physics.


*Host: Nati Srebro <nati at ttic.edu>*

-- 
*Brandie Jones *
*Executive **Administrative Assistant*
Toyota Technological Institute
6045 S. Kenwood Avenue
Chicago, IL  60637
www.ttic.edu
Working Remotely: Feb 17th - March 3rd
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230410/f8ae21b0/attachment.html>