DACO Seminar

Modal title

Modal content

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

Date / Time

Speaker

Title

Location

* 18 October 2022
14:45-16:00

Prof. Dr. Nicolas Boumal
EPFL

Event Details

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

* 25 October 2022
15:00-16:00

Haotian Jiang
University of Washington, Seattle

Event Details

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

* 13 December 2022
10:30-11:15

Prof. Dr. Arnold Filtser
Bar Ilan University

Event Details

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

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

Archive: SS 24 AS 23 SS 23 AS 22 SS 22 AS 21 SS 21 AS 20 SS 20