Simons Collaboration on Algorithms & Geometry 2018 Annual Meeting

  • Organized by
  • Mark Braverman, Ph.D.Princeton University
  • Amit Singer, Ph.D.Princeton University
Date & Time


This is the fourth annual meeting of the Simons Collaboration on Algorithms & Geometry.
 

  • Agendaplus--large

    Friday, May 18, 2018

    8:30 - 9:30 AMCheck-in & Breakfast
    9:30 - 9:35 AMWelcome
    9:35 - 10:25 AMStephane Mallat, Unsupervised Learning from Max Entropy to Deep Generative Networks
    10:25 - 10:40 AMBreak
    10:40 - 11:30 AMRachel Ward, Learning the learning rate in gradient descent methods
    11:30 - 11:45 AMBreak
    11:45 AM - 12:35 PMKonstantin Tikhomirov, Circular law for very sparse non-Hermitian random matrices
    12:35 - 2:15 PMLunch
    2:15 - 3:05 PMAleksandar Nikolov, Balancing Vectors in Any Norm
    3:05 - 3:20 PMBreak
    3:20 - 4:10 PMBenjamin Recht, The statistical foundations of learning to control
    4:10 - 5:00 PMTea
    5:00 - 6:00 PMPublic Lecture - Subhash Khot, Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorem
  • Abstractsplus--large

     

    Stephane Mallat
    Unsupervised Learning from Max Entropy to Deep Generative Networks

    Generative convolutional networks have obtained spectacular results to synthesize complex signals such as images, speech, music, with barely any mathematical understanding. This lecture will move towards this world by beginning from well relatively understood maximum entropy modelization. We first show that non-Gaussian and non-Markovian stationary processes requires to separate scales and measure scale interactions, which can be done with a deep neural network. Applications to turbulence models in physics and cosmology will be shown.

    We shall review deep Generative networks such as GAN and Variational Encoders, which can synthesize realizations of non-stationary processes or highly complex processes such as speech or music. We show that they can be considerably simplified by defining the estimation as an inverse problem. This will build a bridge with maximum entropy estimation. Applications will be shown on images, speech and music generation.

     

    Rachel Ward
    Learning the learning rate in gradient descent methods

    Finding a proper learning rate in stochastic optimization is an important problem.  Choosing a learning rate that is too small leads to painfully slow convergence, while a learning rate that is too large can cause the loss function to fluctuate around the minimum or even to diverge.  In practice, the learning rate is often tuned by hand for different problems at hand.    Several methods have been proposed recently for automatic  adjustment of the learning rate according to gradient data that is received along the way. We review these methods, and propose a simple method, inspired by reparametrization of the loss function in polar coordinates. We prove that the proposed method achieves optimal oracle convergence rates in batch and stochastic settings, but without having to know certain parameters of the loss function in advance.

    This is joint work with Xiaoxia Wu and Leon Bottou

     

    Konstantin Tikhomirov
    Circular law for very sparse non-Hermitian random matrices

    Consider an n by n random matrix with i.i.d Bernoulli entries, where each entry is equal one with probability p. In the regime when p is at least logarithmic in dimension n, the circular law for the limiting spectral distribution (of appropriately rescaled matrix) as the dimension grows to infinity, was previously established in works of Tao-Vu, Gotze-Tikhomirov, Basak-Rudelson. In our work, we consider the setting allowing p to be sublogarithmic; in particular, this implies that the random matrix is singular with high probability. With some restrictions on p, we are able to establish the limiting law for the spectrum for this random model, as well as for some of its generalizations. This is joint work with Mark Rudelson.

     

    Aleksandar Nikolov
    Balancing Vectors in Any Norm

    In the vector balancing problem, we are given symmetric convex bodies C and K in n-dimensional space, and our goal is to determine the minimum number b, known as the vector balancing constant from C to K, such that for any sequence of vectors in C there always exists a signed combination of them lying inside bK. This quantity goes back to a question of Dvoretzky from 1963. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Applied Mathematics, Vol 3 Issue 1, 1981), Spencer’s “six standard deviations suffice” theorem (Transactions of the American Mathematical Society, Vol 289 Issue 2, 1985) and Banaszczyk’s vector balancing theorem (Random Structures & Algorithms, Vol 12 Issue 4, 1998) correspond to bounds on vector balancing constants.

    The above theorems have inspired much research in recent years within theoretical computer science, from the development of efficient polynomial time algorithms that match existential vector balancing guarantees, to their applications in the context of approximation algorithms. In this work, we show that all vector balancing constants admit “good” approximate characterizations, with approximation factors depending only polylogarithmically on the dimension n. First, we show that a volumetric lower bound due to Banaszczyk is tight within a O(log n) factor. Second, we present a novel convex program which encodes the “best possible way” to apply Banaszczyk’s vector balancing theorem for bounding vector balancing constants from above, and show that it is tight within an O(log^{2.5} n) factor. This also directly yields a corresponding polynomial time approximation algorithm both for vector balancing constants, and for the hereditary discrepancy of any sequence of vectors with respect to an arbitrary norm. Our results yield the first guarantees which depend only polylogarithmically on the dimension of the norm ball K.

     

    Benjamin Recht
    The statistical foundations of learning to control

    Given the dramatic successes in machine learning over the past half-decade, there has been a resurgence of interest in applying learning techniques to continuous control problems in robotics, self-driving cars, and unmanned aerial vehicles. Though such applications appear to be straightforward generalizations of what is known as reinforcement learning, few fundamental baselines have been established prescribing how well one must know a system in order to control it. In this talk, I will discuss how one might merge techniques from statistical learning theory with robust control to derive baselines for such continuous control. I will further describe how these simple baselines give us insights into shortcomings of existing reinforcement learning methodology. I will close by listing several exciting open problems that must be solved before we can build robust, safe learning systems that interact with an uncertain physical environment.

  • Travelplus--large

    Air and Train

    Group A
    The foundation will arrange and pay for all air and train travel to the conference for those in Group A. Please provide your travel specifications by clicking the registration link above. If you are unsure of your group, please refer to your invitation sent via email.
    Group B
    The foundation will arrange and pay for hotel accommodations for individuals in Group B. Please provide your arrival and departure dates by clicking the registration link above. If you are unsure of your group, please refer to your invitation sent via email.
    Group C
    Individuals in Group C are considered local and will not receive travel or hotel support. Please register at the link above so that we can capture your dietary requirements. If you are unsure of your group, please refer to your invitation sent via email.

    Personal Car

    For participants driving to Manhattan, The Roger Hotel offers valet parking. Please note there are no in-and-out privileges when using the hotel’s garage, therefore it is encouraged that participants walk or take public transportation to the Simons Foundation.

     

  • Hotelplus--large

    Participants in Group A and Group B who require accommodations are hosted by the foundation for a maximum of two nights at The Roger hotel. Any additional nights are at the attendee’s own expense.

    The Roger New York
    131 Madison Avenue
    New York, NY 10016
    (between 30th and 31st Streets)

    To arrange accommodations, please register at the link above.

    For driving directions to The Roger, please click here.

  • Contactsplus--large

    Travel and Hotel Assistance

    Christophe Vergnol, Protravel International
    christophe.vergnol@protravelinc.com
    646-747-9767

    General Meeting Assistance

    Emily Klein
    MPS Event Coordinator, Simons Foundation
    eklein@simonsfoundation.org
    (646) 751-1262

Subscribe to MPS announcements and other foundation updates