Departement Mathematik

DACO seminar

×

Modal title

Modal content

Bitte abonnieren Sie hier, wenn Sie über diese Veranstaltungen per E-Mail benachrichtigt werden möchten. Ausserdem können Sie auch den iCal/ics-Kalender abonnieren.

Herbstsemester 2022

Datum / Zeit Referent:in Titel Ort
* 18. Oktober 2022
14:45-16:00 		Prof. Dr. Nicolas Boumal
EPFL
Details

DACO Seminar

Titel A bumpy start: why we can't quite accelerate gradient methods on negatively curved spaces
Referent:in, Affiliation Prof. Dr. Nicolas Boumal, EPFL
Datum, Zeit 18. Oktober 2022, 14:45-16:00
Ort 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. Oktober 2022
15:00-16:00 		Haotian Jiang
University of Washington, Seattle
Details

DACO Seminar

Titel Resolving Matrix Spencer Conjecture Up to Polylogarithmic Rank
Referent:in, Affiliation Haotian Jiang, University of Washington, Seattle
Datum, Zeit 25. Oktober 2022, 15:00-16:00
Ort 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. Dezember 2022
10:30-11:15 		Prof. Dr. Arnold Filtser
Bar Ilan University
Details

DACO Seminar

Titel Locality-Sensitive Orderings
Referent:in, Affiliation Prof. Dr. Arnold Filtser, Bar Ilan University
Datum, Zeit 13. Dezember 2022, 10:30-11:15
Ort 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

Hinweise: mit einem Stern gekennzeichnete Ereignisse (*) zeigen an, dass die Zeit und/oder der Ort von der üblichen Zeit und/oder dem üblichen Ort abweichen.

Archiv: FS 24 HS 23 FS 23 HS 22 FS 22 HS 21 FS 21 HS 20 FS 20

JavaScript wurde auf Ihrem Browser deaktiviert