DACO seminar

×

Modal title

Modal content

Please subscribe here if you would you like to be notified about these events via e-mail. Moreover you can also subscribe to the iCal/ics Calender.

Autumn Semester 2022

Date / Time Speaker Title Location
* 18 October 2022
14:45-16:00
Prof. Dr. Nicolas Boumal
EPFL
Details

DACO Seminar

Title A bumpy start: why we can't quite accelerate gradient methods on negatively curved spaces
Speaker, Affiliation Prof. Dr. Nicolas Boumal, EPFL
Date, Time 18 October 2022, 14:45-16:00
Location HG G 19.1
Abstract What sets optimization on Euclidean spaces apart from optimization on Riemannian manifolds? Not that much. By and large, classical algorithms for smooth optimization on Euclidean spaces carry over to optimize on Riemannian manifolds, often with essentially the same (adequately rephrased) theoretical guarantees. As a notable exception, it turns out that such is not the case for Nesterov's accelerated gradient descent. Building on several ideas by Hamilton and Moitra (2021), we construct a resisting oracle that shows it is not possible to minimize smooth, strongly geodesically convex functions on Hadamard manifolds at an accelerated rate. I will give some geometric intuition as to why negative curvature makes life harder for optimizers, and why this may not be the end of the story. This is work with Chris Criscitiello, COLT 2022.
A bumpy start: why we can't quite accelerate gradient methods on negatively curved spacesread_more
HG G 19.1
* 25 October 2022
15:00-16:00
Haotian Jiang
University of Washington, Seattle
Details

DACO Seminar

Title Resolving Matrix Spencer Conjecture Up to Polylogarithmic Rank
Speaker, Affiliation Haotian Jiang, University of Washington, Seattle
Date, Time 25 October 2022, 15:00-16:00
Location HG G 19.1
Zoom talk, "watch party" at HG G 19.1
Abstract Abstract: In this talk, I will present a simple proof of the matrix Spencer conjecture up to poly-logarithmic rank: given symmetric d by d matrices A_1,...,A_n each with operator norm at most 1 and rank at most n/\log^3 n, one can efficiently find \pm 1 signs x_1,... ,x_n such that their signed sum has spectral norm \|\sum_{i=1}^n x_i A_i\|_op= O(\sqrt{n}). This result also implies a (\log n - 3 \log \log n) qubit lower bound for quantum random access codes encoding n classical bits with advantage >> 1/\sqrt{n}. Our proof uses the recent refinement of the non-commutative Khintchine inequality in [Bandeira, Boedihardjo, van Handel, 2022] for random matrices with correlated Gaussian entries. This talk is based on a joint work with Nikhil Bansal and Raghu Meka, available at https://arxiv.org/abs/2208.11286.
Resolving Matrix Spencer Conjecture Up to Polylogarithmic Rankread_more
HG G 19.1
Zoom talk, "watch party" at HG G 19.1
* 13 December 2022
10:30-11:15
Prof. Dr. Arnold Filtser
Bar Ilan University
Details

DACO Seminar

Title Locality-Sensitive Orderings
Speaker, Affiliation Prof. Dr. Arnold Filtser, Bar Ilan University
Date, Time 13 December 2022, 10:30-11:15
Location HG G 19.1
Abstract Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ordering (LSO), a new tool that allows one to reduce problems in the Euclidean space R^d to the 1-dimensional line. They used LSO's to solve a host of problems. Later, Buchin, Har-Peled, and Oláh [2019,2020] used the LSO of Chan et al. to construct very sparse reliable spanners for the Euclidean space. A highly desirable feature of a reliable spanner is its ability to withstand a massive failure: the network remains functioning even if 90% of the nodes fail. We develop the theory of LSO's in non-Euclidean metrics by introducing new types of LSO's suitable for general and topologically structured metrics. We then construct such LSO's, as well as constructing considerably improved LSO's for doubling metrics. Afterwards, we use our new LSO's to construct reliable spanners with improved stretch and sparsity parameters. Time permitting, we will also discuss several additional applications of LSO's.
Locality-Sensitive Orderingsread_more
HG G 19.1

Notes: events marked with an asterisk (*) indicate that the time and/or location are different from the usual time and/or location.

JavaScript has been disabled in your browser