[iasmath-semru] Theoretical Computer Science/Discrete Math Seminars--Week of December 10, 2018

[Kristina Phillips]

INSTITUTE FOR ADVANCED STUDY

School of Mathematics

Princeton, NJ 08540

 

Theoretical Computer Science/Discrete Math Seminars

Week of December 10, 2018

 

 

--------------

To view mathematics in titles and abstracts, please click on the talk's
link.

--------------

 

Monday, December 10

 

Computer Science/Discrete Mathematics Seminar I

Topic:                    A matrix expander Chernoff bound

Speaker:              Ankit Garg, Microsoft Research

Time/Room:       11:15am - 12:15pm/Simonyi Hall 101

Abstract Link:      <http://www.math.ias.edu/seminars/abstract?event=128879>
http://www.math.ias.edu/seminars/abstract?event=128879

 

 

 

Monday, December 10

 

Seminar on Theoretical Machine Learning

Topic:                    On Expressiveness and Optimization in Deep
Learning

Speaker:              Nadav Cohen, Member, School of Mathematics

Time/Room:       12:15pm - 1:45pm/White Levy Room

Abstract Link:      <http://www.math.ias.edu/seminars/abstract?event=139466>
http://www.math.ias.edu/seminars/abstract?event=139466

 

 

 

Tuesday, December 11

 

Computer Science/Discrete Mathematics Seminar II

Topic:                    An invitation to tensor networks

Speaker:              Michael Walter, University of Amsterdam

Time/Room:       10:30am - 12:30pm/Simonyi Hall 101

Abstract Link:      <http://www.math.ias.edu/seminars/abstract?event=129115>
http://www.math.ias.edu/seminars/abstract?event=129115

 

1 A matrix expander Chernoff bound 
   Ankit Garg 




Chernoff-type bounds study concentration of sums of independent random
variables and are extremely useful in various settings. In many settings,
the random variables may not be completely independent but only have limited
independence. One such setting, which turns out to be useful in
derandomization and theoretical computer science, in general, involves
random walks on expanders. I will talk about a Chernoff-type bound for sums
of matrix-valued random variables sampled via a random walk on an expander.
Our proof is based on a new multi-matrix extension of the Golden-Thompson
inequality which improves in some ways a recent inequality due to Sutter et
al. and may be of independent interest, as well as an adaptation of an
argument for the scalar case due to Healy. Based on joint work with Yin Tat
Lee, Zhao Song and Nikhil Srivastava.

http://www.math.ias.edu/seminars/abstract?event=128879

2 On Expressiveness and Optimization in Deep Learning 
   Nadav Cohen 




Understanding deep learning calls for addressing three fundamental
questions: expressiveness, optimization and generalization. Expressiveness
refers to the ability of compactly sized deep neural networks to represent
functions capable of solving real-world problems. Optimization concerns the
effectiveness of simple gradient-based algorithms in solving non-convex
neural network training programs. Generalization treats the phenomenon of
deep learning models not overfitting despite having much more parameters
than examples to learn from. This talk will describe a series of works aimed
at unraveling some of the mysteries behind expressiveness and optimization.
I will begin by establishing an equivalence between convolutional and
recurrent networks --- the most successful deep learning architectures to
date --- and hierarchical tensor decompositions. The equivalence will be
used to answer various questions concerning expressiveness, resulting in new
theoretically-backed tools for deep network design. I will then turn to
discuss a recent line of work analyzing optimization of deep linear neural
networks. By studying the trajectories of gradient descent, we will derive
the most general guarantee to date for efficient convergence to global
minimum of a gradient-based algorithm training a deep network. Moreover, in
stark contrast with conventional wisdom, we will see that sometimes,
gradient descent can train a deep linear network faster than a classic
linear model. In other words, depth can accelerate optimization, even
without any gain in expressiveness, and despite introducing non-convexity to
a formerly convex problem. 

The talk will be of a high-level nature, suitable for a diverse crowd. It
will cover works done in collaboration with Sanjeev Arora, Noah Golowich,
Elad Hazan, Wei Hu, Yoav Levine, Or Sharir, Amnon Shashua, Ronen Tamari and
David Yakira.

http://www.math.ias.edu/seminars/abstract?event=139466

3 An invitation to tensor networks 
   Michael Walter 




Tensor networks describe high-dimensional tensors as the contraction of a
network (or graph) of low-dimensional tensors. Many interesting tensor can
be succinctly represented in this fashion -- from many-body ground states in
quantum physics to the matrix multiplication tensors in algebraic
complexity. I will give a mathematical introduction to the formalism, give
several examples, and sketch some of the most important results. We will
discuss the role of the network, how symmetries are encoded, tensor networks
as a computational model, and survey some recent algorithmic results.

http://www.math.ias.edu/seminars/abstract?event=129115

Computer Science/Discrete Math Seminars can be found on our web page:

http://www.math.ias.edu/csdm
http://www.math.ias.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/iasmathsemrutgers/attachments/20181204/fc0fe4d8/attachment.html>