Fast Iterative Methods in Optimization

source: Simons Institute     2017年10月2日
Iterative methods have been greatly influential in continuous optimization. In fact, almost all algorithms in that field are iterative in nature. Recently, a confluence of ideas from optimization and theoretical computer science has led to breakthroughs in terms of new understanding and running time bound improvements for some of the classic iterative continuous optimization primitives. In this workshop we explore these advances as well as new directions that they have opened up. Some of the specific topics that this workshop plans to cover are: advanced first-order methods (non-smooth optimization, regularization and preconditioning), structured optimization, fast LP/SDP solvers, advances in interior point methods and fast streaming/sketching techniques. One of the key themes that will be highlighted is how combining the continuous and discrete points of view can often allow one to achieve near-optimal running time bounds.
For more information, please visit https://simons.berkeley.edu/workshops...
These presentations were supported in part by an award from the Simons Foundation.

1 55:29 Continuous Methods for Discrete Optimization: From Convex Relaxations, to Iterative Schemes...
2 47:11 Width-independent Iterative Algorithms for Packing and Covering Programs
3 38:47 Slime Molds and Sparse Recovery
4 45:55 Michael Cohen and ell_p Regression
5 44:36 Chordal Graphs and Sparse Semidefinite Optimization
6 46:26 On the Optimization Landscape of Matrix and Tensor Decomposition Problems
7 45:27 The State of Contemporary Computing Substrates for Optimization Methods
8 39:14 Let's Make Block Coordinate Descent Go Fast
9 45:00 Stochastic, Second-order Black-box Optimization for Step Functions
10 48:22 Algorithmic Tools for Smooth Nonconvex Optimization
11 42:22 Zero-order and Dynamic Sampling Methods for Nonlinear Optimization
12 43:32 Dealing with Linear Constraints via Random Permutation
13 42:05 Randomized Iterative Methods and Complexity for Markov Decision Process
14 49:28 Sketching as a Tool for Fast Algorithm Design
15 49:47 Sublinear Time Low-rank Approximation of Positive Semidefinite Matrices
16 44:16 Hashing-based-estimators for Kernel Density in High Dimensions
17 48:50 Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
18 51:38 Trends in Large-scale Nonconvex Optimization
19 47:37 Faster Algorithms and New Iterative Methods for Computing the Stationary Distribution
20 34:41 Nonconvex Optimization for High-dimensional Learning: From ReLUs to Submodular Maximization
21 48:12 Will Vanishing Gradients Ever Vanish from Deep Learning?
22 46:46 From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure
23 51:40 Natasha 2: Faster Non-convex Optimization Than SGD

Discrete Optimization via Continuous Relaxation

source: Simons Institute        2017年9月11日
Much of the progress in solving discrete optimization problems, especially in terms of approximation algorithms, has come from designing novel continuous relaxations. The primary tools in this area are linear programming and semidefinite programming. Other forms of relaxations have also been developed, such as multilinear relaxation for submodular optimization. In this workshop, we explore the state-of-the-art techniques for performing discrete optimization based on continuous relaxations of the underlying problem, as well as our current understanding of the limitations of this kind of approach. We focus on LP/SDP relaxations and techniques for rounding their solutions, as well as methods for submodular optimization, both in the offline and online setting. We also investigate the limits of such relaxations and hardness of approximation results.
For more information, please visit: https://simons.berkeley.edu/workshops...
These presentations were supported in part by an award from the Simons Foundation.

1 1:07:15 The Power of Hierarchies for Detecting Hidden Structures
2 33:25 Simplex Transformations and Multiway Cut
3 31:45 LPs and Convex Programming Relaxations and Rounding for Stochastic Problems
4 1:03:56 Discrepancy and Approximation Algorithms
5 31:42 On Approximating the Covering Radius and Finding Dense Lattice Subspaces
6 31:35 A Strongly Polynomial Algorithm for Bimodular Integer Linear Programming
7 1:01:27 Improved Approximation Algorithms for the TSP and S-t-path TSP
8 1:07:59 A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
9 30:12 Compact, Provably-good LPs for Orienteering and Regret-bounded Vehicle Routing
10 28:28 Surviving in Directed Graphs: A Quasi-polynomial-time Polylogarithmic Approximation...
11 30:26 Improved Approximation for Non-preemptive Scheduling via Time-indexed LP Relaxations
12 32:19 LP Rounding for Poise
13 59:18 Submodular Optimization
14 29:26 Submodular Unsplittable Flow on Trees
15 33:03 A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
16 1:00:56 Online Optimization, Smoothing, and Competitive Ratio
17 32:13 The Non-Uniform k-Center Problem
18 56:56 Beyond Worst Case Analysis in Approximation
19 32:15 Algorithms for Stable and Perturbation-resilient Problems
20 29:25 Scheduling on Related Machines
21 34:10 Low Diameter Graph Decompositions and Approximating Unique Games
22 54:30 A (1+epsilon)-approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
23 34:39 LP Relaxations for Reordering Buffer Management
24 58:13 A Survey of Dependent Rounding
25 26:10 Finding Best LP Relaxations for Various Cut Problems
26 34:27 Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration
27 29:10 Approximating the Permanent of Positive Semidefinite Matrices
28 28:11 Local Guarantees in Graph Cuts and Clustering

Bridging Continuous and Discrete Optimization Boot Camp

source: Simons Institute         2017年8月21日
The Boot Camp is intended to acquaint program participants with the key themes of the program. It will consist of five days of tutorial presentations, each with ample time for questions and discussion, as follows:
Michel Goemans (MIT): Duality
Pablo Parrilo (MIT) and Ankur Moitra (MIT): LP/SDP Hierarchies and Sum of Squares Proofs
Lorenzo Orecchia (Boston University), Maryam Fazel (University of Washington) and Stefanie Jegelka (MIT): Continuous Methods
Sasha Rakhlin (University of Pennsylvania), Ben Recht (UC Berkeley) and Laurent El Ghaoui (UC Berkeley): Robustness, Stochastics, Uncertainty
Thomas Rothvoß (University of Washington), Prasad Raghavendra (UC Berkeley) and Hamza Fawzi (University of Cambridge): Extended Formulations
Steve Wright (University of Wisconsin-Madison), Aaron Sidford (Stanford University) and Aleksander Mądry (MIT): Interior Point Methods
For more information, please visit: https://simons.berkeley.edu/workshops...
These presentations were supported in part by an award from the Simons Foundation.

1 1:01:01 Duality 1
2 1:02:24 Duality 2
3 1:00:46 LP/SDP Hierarchies and Sum of Squares Proofs 1
4 1:04:16 LP/SDP Hierarchies and Sum of Squares Proofs 2
5 1:04:50 Duality 3
6 1:01:39 Continuous Methods 1
7 58:07 Continuous Methods 2
8 1:00:47 Robustness, Stochastics, Uncertainty 1
9 1:01:20 Robustness, Stochastics, Uncertainty 2
10 59:13 LP/SDP Hierarchies and Sum of Squares Proofs 3
11 1:06:19 LP/SDP Hierarchies and Sum of Squares Proofs 4
12 57:39 Extended Formulations 1
13 1:00:09 Extended Formulations 2
14 1:02:37 Robustness, Stochastics, Uncertainty 3
15 53:25 Extended Formulations 3
16 57:46 Extended Formulations 4
17 1:00:33 Interior Point Methods 1
18 54:25 Interior Point Methods 2
19 1:10:07 Interior Point Methods 3
20 1:01:59 Continuous Methods 3
21 59:47 Continuous Methods 4
22 1:08:29 Interior Point Methods 4

Computational Challenges in Machine Learning

source: Simons Institute        2017年5月1日
The aim of this workshop is to bring together a broad set of researchers looking at algorithmic questions that arise in machine learning. The primary target areas will be large-­scale learning, including algorithms for Bayesian estimation and variational inference, nonlinear and nonparametric function estimation, reinforcement learning, and stochastic processes including diffusion, point processes and MCMC. While many of these methods have been central to statistical modeling and machine learning, recent advances in their scope and applicability lead to basic questions about their computational efficiency. The latter is often linked to modeling assumptions and objectives. The workshop will examine progress and challenges and include a set of tutorials on the state of the art by leading experts.
For more information, please visit https://simons.berkeley.edu/workshops...
These presentations were supported in part by an award from the Simons Foundation.

1 1:05:29 Variational Inference: Foundations and Innovations
2 44:41 Representational and Optimization Properties of Deep Residual Networks
3 41:36 Composing Graphical Models with Neural Networks for Structured Representations and Fast Inference
4 46:48 Scaling Up Bayesian Inference for Big and Complex Data
5 36:23 Unbiased Estimation of the Spectral Properties of Large Implicit Matrices
6 53:37 Stochastic Gradient MCMC for Independent and Dependent Data Sources
7 1:02:06 On Gradient-Based Optimization: Accelerated, Distributed, Asynchronous and Stochastic
8 48:31 Sampling Polytopes: From Euclid to Riemann
9 38:54 Understanding Generalization in Adaptive Data Analysis
10 39:37 Your Neural Network Can't Learn Mine
11 Efficient Distributed Deep Learning Using MXNet
12 Machine Learning for Healthcare Data
13 Machine Learning Combinatorial Optimization Algorithms
14 A Cost Function for Similarity-Based Hierarchical Clustering
15 The Imitation Learning View of Structured Prediction
16 Exponential Computational Improvement by Reduction
17 Embedding as a Tool for Algorithm Design
18 Robust Estimation of Mean and Covariance
19 Computational Efficiency and Robust Statistics
20 42:11 System and Algorithm Co-Design, Theory and Practice, for Distributed Machine Learning
21 42:41 The Polytope Learning Problem
22 1:03:24 Computational Challenges and the Future of ML Panel
23 1:03:16 Computationally Tractable and Near Optimal Design of Experiments
24 43:14 Learning from Untrusted Data
25 41:35 The “Tell Me Something New” Model of Computation for Machine Learning

Michael Cohen Memorial Symposium

source: Simons Institute       2017年11月27日
Michael Cohen tragically passed away at the beginning of the Fall 2017 semester in Berkeley. He was a brilliant mathematician and a rising star in theoretical computer science. In this mini-symposium, some of his co-authors will present a sample of his impressive contributions.
For more information please visit: https://simons.berkeley.edu/workshops...
These presentations were supported in part by an award from the Simons Foundation.

1 28:00 Welcome and Bird's Eye View of Michael's Work/Uniform Sampling and Inverse Maintenance
2  34:43 Michael Cohen and High-dimensional Probability
3 34:20 Michael Cohen and Self-concordant Barriers over L_p Balls
4 39:37 Michael Cohen and Oblivious Routing
5 31:25 Preconditioning in Expectation
6 29:22 Michael Cohen and Directed Laplacians

CEMRACS 2017 - Summer School

source: Centre International de Rencontres Mathématiques 2017年8月11日

1 1:08:00 Stefano Marelli: Metamodels for uncertainty quantification and reliability analysis
2 56:33 Olivier Le Maître: Global Sensitivity Analysis in Stochastic Systems
3 1:00:34 Julia Charrier: Subsurface flow with uncertainty : applications and numerical analysis issues
4 1:46:10 Raúl Tempone: Adaptive strategies for Multilevel Monte Carlo
5 1:51:58 Raúl Tempone: Multilevel and Multi-index Monte Carlo methods for the McKean-Vlasov equation
6 1:46:25 Plamen Turkedjiev: Least squares regression Monte Carlo for approximating BSDES and semilinear PDES
7 1:03:26 Vianney Perchet: Bandits in Auctions (& more)
8 1:02:51 Jean-David Benamou: Dynamic formulations of Optimal Transportation and variational MFGs
9 1:33:55 Xavier Warin: Branching for PDEs
10 1:51:24 Gilles Pagès: Optimal vector Quantization: from signal processing to clustering and ...
11 1:04:35 Marc Bellemare: Model-free control with deep learning
12 1:05:25 Pierre Degond: On the interplay between kinetic theory and game theory
13 1:51:24 Dan Crisan: Cubature methods and applications
14 1:02:07 Mireille Bossy: Particle algorithm for McKean SDE : a short review on numerical analysis
15 1:48:42 Peter Imkeller: An introduction to BSDE
16 54:56 René Carmona: Mean field games with major and minor players
17 1:05:16 René Aïd: Capacity expansion games with application to competition in power generation investments
18 49:36 Yves Achdou: Numerical methods for mean field games - Introduction to the system of PDEs and...
19 1:51:11
Yves Achdou: Numerical methods for mean field games - Monotone finite difference schemes
20 1:11:57 Yves Achdou: Numerical methods for mean field games - Variational MFG and related algorithms for...
21 1:50:05 Jérôme Lelong : Introduction to HPC, Random generation and OpenMP
22 1:39:57 Jérôme Lelong : Introduction to HPC - MPI : Design of parallel program and MPI
23 58:52 Benjamin Jourdain: The Metropolis Hastings algorithm: introduction and optimal scaling of...

Lie Theory and Generalizations

source: Centre International de Rencontres Mathématiques  2016年11月24日

1 50:40 Ramla Abdellatif : Extensions between Iwahori-Hecke modules for SL2(F) in characteristic p
2 43:33 Jean Michel : Quasisemisimple classes
3 1:13:07 Yves Benoist: Dense subgroups in simple groups - Lecture 2
4 1:00:10 Dominique Manchon: Free post-Lie algebras, the Hopf algebra of Lie group integrators and planar...

(français / in French) Services numériques pour les mathématiques

source: Centre International de Rencontres Mathématiques    2016年11月2日

1 44:21 Gérard Grancher : Démocratie, dictature ... et mathématiques
2 55:50 Damien Ferney : Panorama des Services Numériques de la Plateforme en Ligne pour les Mathématiques
3 40:55 Laurent Azema : Correspondants Mathrice
4 2:26:23 Serge Bordères : Les mobiles au sein d'un réseau de laboratoire
5 34:53 Benoît Métrot : La PLM et le portail des Mathématiques

(theme videos) Topology

source: Centre International de Rencontres Mathématiques   2016年7月6日

Francesco Bei : On the Hodge-Kodaira Laplacian on the canonical bundle of a compact Hermitian... 21:45
Werner Müller : Analytic torsion for locally symmetric spaces of finite volume 1:02:55
Markus Banagl : The L-Homology fundamental class for singular spaces and the stratified Novikov 54:25
Ilaria Mondello : An Obata-Lichnerowicz theorem for stratified spaces 23:51
Pierre Albin : Extending the Cheeger-Müller theorem through degeneration 54:48
Leslie Saper : L2-cohomology and the theory of weights 59:05
Gabriel Rivière: Correlation spectrum of Morse-Smale flows 57:47
Jean-Yves Welschinger: Expected topology of a random subcomplex in a simplicial complex 1:16:32
Penka Georgieva: Real curves and a Klein TQFT 1:03:21
Stepan Orevko: On real algebraic knots and links 57:38
Steve Awodey: Type theories and polynomial monads​ 56:02
Eric Hoffbeck: Shuffles of trees​ 1:01:17
François Métayer: Homotopy theory of strict omega-categories and its connections with...Part 2 1:31:11
François Métayer: Homotopy theory of strict omega-categories and its connections with...Part 1 1:27:35
François Métayer: Homotopy theory of strict omega-categories and its connections with...Part 3 1:22:20
Terence Tao: An integration approach to the Toeplitz square peg problem 58:44
Delphine Moussard: Finite type invariants of knots in homology 3-spheres 1:02:23
Anton Zorich: Equidistribution of square-tiled surfaces, meanders, and Masur-Veech volumes ​1:06:17
Kimihiko Motegi: L-space knots in twist families and satellite L-space knots 51:48
Julien Marché: Differential equation for the Reidemeister torsion 1:08:25
Jeffrey Meier: Bridge trisections of knotted surfaces in four-manifolds​ 1:04:39
Andrew Lobb: Quantum sln knot cohomology and the slice genus 50:01
David Cimasoni : Covering spaces and spanning trees 1:02:32
Mark Powell: Surface systems for links​ 1:03:31
David Gay: Trisections diagrams and surgery operations on embedded surfaces​ 1:03:11
Stefan Friedl: Exceptional 3-manifolds​ 58:07
Camille Horbez: Automorphisms of hyperbolic groups and growth 1:07:00
Emily Stark: The visual boundary of hyperbolic free-by-cyclic groups 57:02
Daniel Groves: Homomorphisms to 3-manifold groups and other families 57:09
Bena Tshishiku: Groups with Bowditch boundary a 2-sphere 58:17
Mladen Bestvina: The Farrell-Jones conjecture for free-by-cyclic groups 1:05:10

SPECIAL 7th European congress of Mathematics Berlin 2016.

source: Centre International de Rencontres Mathématiques   2015年8月3日

1 1:03:04 Gerd Faltings: The category MF in the semistable case
2 10:55 Interview at CIRM : Peter Scholze
3 46:01 Ingrid Bauer: Faithful actions of Gal(Q¯/Q) and change of fundamental group
4 55:21 Peter Scholze: p-adic cohomology of the Lubin-Tate tower
5 30:40 Salma Kuhlmann: Real closed fields and models of Peano arithmetic
6 55:47 Ulrike von Luxburg: Statistics on graphs and networks (II)
7 55:55 Natalia Tronko: Exact conservation laws for gyrokinetic Vlasov-Poisson equations
8 49:34 Sven Bachmann: A classification of gapped Hamiltonians in d=1
9 46:16 Christian Bär: Characteristic initial value problem for wave equations on manifolds
10 1:02:19 Peter Scholze: The Witt vector affine Grassmannian
11 15:51 Interview Pavel Exner
12 46:14 Christian Bär: Characteristic initial value problem for wave equations on manifolds
13 47:45 Jochen Blath: Genetic variability under the seed bank coalescent
14 52:18 Jan Bruinier: Classes of Heegner divisors and traces of singular moduli
15 42:59 Volker Diekert: Recognizable languages are Church-Rosser congruential
16 54:45 Peter Friz: Some examples of homogenization related rough paths
17 1:00:38 Ernst-Ulrich Gekeler: Algebraic curves with many rational points over non-prime finite fields
18 53:32 Jérémy Guéré : Mirror symmetry for singularities
19 1:06:49 Marc Levine: The rational motivic sphere spectrum and motivic Serre finiteness
20 25:24 Interview at CIRM : Endre Szemerédi, Abel Prize 2012
21 1:07:25 Heinrich Matzat: Braids and Galois groups
22 59:43 Volker Mehrmann : Extended Lagrange spaces and optimal control
23 59:52 Norbert Müller : Wrapping in exact real arithmetic
24 55:01 Hermann Schulz-Baldes: Invariants of disordered topological insulators
25 46:54 Aurélien Tellier: Plant ecology influences population genetics: the role of seed banks in [...]
26 55:04 Stefan Teufel: Peierls substitution for magnetic Bloch bands
27 1:32:07 Stephan Volkwein: POD a-posteriori error estimation for PDE constrained optimization
28 42:37 Tobias Weich: Resonance chains on Schottky surfaces
29 47:28 Dirk Werner: The Daugavet equation for Lipschitz operators
30 53:23 Sander Zwegers: Fourier coefficients of meromorphic Jacobi forms
31 36:26 Endre Szemerédi: Maximum size of a set of integers