Department of Mathematics

Search

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.

Spring Semester 2023

Date / Time Speaker Title Location
* 27 January 2023
12:20-13:00 		Pranav Nuti
Stanford University, Stanford, USA
Event Details

DACO Seminar

Title Online selection problems and how Ramsey’s theorem solves a card game
Speaker, Affiliation Pranav Nuti, Stanford University, Stanford, USA
Date, Time 27 January 2023, 12:20-13:00
Location HG G 19.2
Abstract In a basic online selection problem, we observe a sequence of numbers one-by-one, and we have to make an irrevocable decision to select one of the numbers. Both the secretary problem and the prophet problem are of this type, but they differ along a few dimensions: the order in which the numbers appear, how much information we have about the numbers before we observe them, and the objective we desire to maximize. Several models that are in between the secretary and prophet problems along these dimensions have previously been investigated. In this talk, I will say a little bit about these different models, and then explain how we can use Ramsey’s theorem (for hypergraphs) to obtain optimal results for one such model. This model has an interpretation as a simple card game.
Online selection problems and how Ramsey’s theorem solves a card gameread_more
HG G 19.2
20 February 2023
14:15-16:00
Event Details

DACO Seminar

Title Title T.B.A.
Speaker, Affiliation
Date, Time 20 February 2023, 14:15-16:00
Location HG G 19.1
Title T.B.A.
HG G 19.1
21 February 2023
14:15-16:00 		Prof. Dr. Martin Kassabov
Cornell University, USA
Event Details

DACO Seminar

Title Tame automorphism groups of polynomial rings with property (T) and infinitely many alternating group quotients
Speaker, Affiliation Prof. Dr. Martin Kassabov, Cornell University, USA
Date, Time 21 February 2023, 14:15-16:00
Location HG G 19.1
Abstract We construct new families of groups with property (T) and infinitely many alternating group quotients. One of those consists of subgroups of Aut(Fp[x1,…,xn]) generated by a suitable set of tame automorphisms. Finite quotients are constructed using the natural action of Aut(F_p[x_1,…,x_n]) on the n-dimensional affine spaces over finite extensions of F_p. As a consequence, we obtain explicit presentations of Gromov hyperbolic groups with property (T) and infinitely many alternating group quotients. Our construction also yields an explicit infinite family of expander Cayley graphs of degree 4 for alternating groups of degree p^7−1 for any odd prime p.
Tame automorphism groups of polynomial rings with property (T) and infinitely many alternating group quotientsread_more
HG G 19.1
* 24 February 2023
16:15-17:15 		Prof. Dr. Amir Ali Ahmadi
Princeton University, Princeton, USA
Event Details

DACO Seminar

Title Complexity of Finding Local Minima in Polynomial Optimization
Speaker, Affiliation Prof. Dr. Amir Ali Ahmadi, Princeton University, Princeton, USA
Date, Time 24 February 2023, 16:15-17:15
Location HG G 19.2
Abstract We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if a polynomial has a point of that type. Our results characterize the complexity of these two questions for all degrees left open by prior literature. Our main contributions reveal that many of these questions turn out to be tractable for cubic polynomials. By contrast, we show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c\geq 0$) of a local minimizer of an $n$-variate quadratic polynomial over a polytope. This result (with $c=0$) answers a question of Pardalos and Vavasis that appeared on a list of seven open problems in complexity theory for numerical optimization in 1992. Based on joint work with Jeffrey Zhang (CMU).
Complexity of Finding Local Minima in Polynomial Optimizationread_more
HG G 19.2
* 9 March 2023
14:15-16:00 		Prof. Dr. Friedrich Eisenbrand
EPF Lausanne
Event Details

DACO Seminar

Title From approximate to exact integer programming
Speaker, Affiliation Prof. Dr. Friedrich Eisenbrand, EPF Lausanne
Date, Time 9 March 2023, 14:15-16:00
Location HG G 19.2
Abstract We show in this talk, how an oracle for approximate integer programming can be used to solve an integer program exactly. The method is based on convex optimzation techniques. It yields the best known complexity bounds for general integer programming and novel complexity results for integer programs in equality form in which the domain is bounded by a polynomial in the dimension. Joint work with Daniel Dadush and Thomas Rothvoss
From approximate to exact integer programmingread_more
HG G 19.2
* 14 March 2023
10:40-11:20 		Vasilis Livanov
University of Illinois at Urbana Champaign, USA
Event Details

DACO Seminar

Title Optimal Stopping Problems for Cost Minimization
Speaker, Affiliation Vasilis Livanov, University of Illinois at Urbana Champaign, USA
Date, Time 14 March 2023, 10:40-11:20
Location HG F 26.5
Abstract A classic result from optimal stopping theory asks when one should stop and accept a value from a sequence of observed values, presented one by one, if one knows the distributions that these values are coming from and wants to select the maximum. The catch is that, if a value is rejected, it can never be selected again. This setting, which combines online decision making with stochastic uncertainty, is called the prophet inequality. Over the past decade, there have been two very exciting discoveries, connecting auction theory and online combinatorial optimization with prophet inequality-type problems. In this talk, we cover some of the standard ideas and results on prophet inequalities and online combinatorial optimization. Afterwards, we present the first results in a new direction that studies prophet inequalities for minimization instead, a setting which resents rich and qualitatively different results from the maximization case.
Optimal Stopping Problems for Cost Minimizationread_more
HG F 26.5
21 March 2023
14:15-15:05 		Emmanuel Pilliat
Université de Montpellier, France
Event Details

DACO Seminar

Title Optimal Permutation Estimation in Crowd-Sourcing Problems
Speaker, Affiliation Emmanuel Pilliat, Université de Montpellier, France
Date, Time 21 March 2023, 14:15-15:05
Location HG G 19.1
Abstract Motivated by crowd-sourcing applications, we consider a model where we have partial observations from a bivariate isotonic n x d matrix with an unknown permutation \pi^* acting on its rows. Focusing on the twin problems of recovering the permutation \pi^* and estimating the unknown matrix, we introduce a polynomial-time procedure achieving the minimax risk for these two problems, this for all possible values of n, d and all sampling efforts. Along the way, we establish that in some regimes, recovering the permutation \pi^* is considerably simpler than estimating the matrix.
Optimal Permutation Estimation in Crowd-Sourcing Problemsread_more
HG G 19.1
* 28 March 2023
14:45-15:45 		Tatiana Brailovskaya
Princeton University, Princeton, USA
Event Details

DACO Seminar

Title Universality and matrix concentration inequalities
Speaker, Affiliation Tatiana Brailovskaya, Princeton University, Princeton, USA
Date, Time 28 March 2023, 14:45-15:45
Location HG G 19.1
Abstract Random matrices frequently appear in many different fields — physics, computer science, applied and pure mathematics. Oftentimes the random matrix of interest will have non-trivial structure — entries that are dependent and have potentially different means and variances (e.g. sparse Wigner matrices, matrices corresponding to adjacencies of random graphs, sample covariance matrices). However, current understanding of such complex random matrices remains lacking. In this talk, I will discuss recent results concerning the spectrum of sums of independent random matrices with a.s. bounded operator norms. In particular, I will demonstrate that under some fairly general conditions, such sums will exhibit the following universality phenomenon — their spectrum will lie close to that of a Gaussian random matrix with the same mean and covariance. No prior background in random matrix theory is required — basic knowledge of probability and linear algebra are sufficient. (joint with Ramon van Handel) Pre-print link: https://web.math.princeton.edu/~rvan/tuniv220113.pdf
Universality and matrix concentration inequalitiesread_more
HG G 19.1
* 18 April 2023
14:15-15:05 		Prof. Dr. Courtney Paquette
McGill, Canada
Event Details

DACO Seminar

Title DACO-FDS: Stochastic Algorithms in the Large: Batch Size Saturation, Stepsize Criticality, Generalization Performance, and Exact Dynamics (Part I)
Speaker, Affiliation Prof. Dr. Courtney Paquette, McGill, Canada
Date, Time 18 April 2023, 14:15-15:05
Location HG G 19.1
Abstract In this talk, we will present a framework for analyzing dynamics of stochastic optimization algorithms (e.g., stochastic gradient descent (SGD) and momentum (SGD+M)) when both the number of samples and dimensions are large. For the analysis, we will introduce a stochastic differential equation, called homogenized SGD. We show that homogenized SGD is the high-dimensional equivalent of SGD -- for any quadratic statistic (e.g., population risk with quadratic loss), the statistic under the iterates of SGD converges to the statistic under homogenized SGD when the number of samples n and number of features d are polynomially related. By analyzing homogenized SGD, we provide exact non-asymptotic high-dimensional expressions for the training dynamics and generalization performance of SGD in terms of a solution of a Volterra integral equation. The analysis is formulated for data matrices and target vectors that satisfy a family of resolvent conditions, which can roughly be viewed as a weak form of delocalization of sample-side singular vectors of the data. By analyzing these limiting dynamics, we can provide insights into learning rate, momentum parameter, and batch size selection. For instance, we identify a stability measurement, the implicit conditioning ratio (ICR), which regulates the ability of SGD+M to accelerate the algorithm. When the batch size exceeds this ICR, SGD+M converges linearly at a rate of $O(1/ \kappa)$, matching optimal full-batch momentum (in particular performing as well as a full-batch but with a fraction of the size). For batch sizes smaller than the ICR, in contrast, SGD+M has rates that scale like a multiple of the single batch SGD rate. We give explicit choices for the learning rate and momentum parameter in terms of the Hessian spectra that achieve this performance. Finally we show this model matches performances on real data sets.
DACO-FDS: Stochastic Algorithms in the Large: Batch Size Saturation, Stepsize Criticality, Generalization Performance, and Exact Dynamics (Part I)read_more
HG G 19.1
* 18 April 2023
15:10-16:00 		Prof. Dr. Elliot Paquette
McGill, Canada
Event Details

DACO Seminar

Title DACO-FDS: Stochastic Algorithms in the Large: Batch Size Saturation, Stepsize Criticality, Generalization Performance, and Exact Dynamics (Part II)
Speaker, Affiliation Prof. Dr. Elliot Paquette, McGill, Canada
Date, Time 18 April 2023, 15:10-16:00
Location HG G 19.1
Abstract In this talk, we will present a framework for analyzing dynamics of stochastic optimization algorithms (e.g., stochastic gradient descent (SGD) and momentum (SGD+M)) when both the number of samples and dimensions are large. For the analysis, we will introduce a stochastic differential equation, called homogenized SGD. We show that homogenized SGD is the high-dimensional equivalent of SGD -- for any quadratic statistic (e.g., population risk with quadratic loss), the statistic under the iterates of SGD converges to the statistic under homogenized SGD when the number of samples n and number of features d are polynomially related. By analyzing homogenized SGD, we provide exact non-asymptotic high-dimensional expressions for the training dynamics and generalization performance of SGD in terms of a solution of a Volterra integral equation. The analysis is formulated for data matrices and target vectors that satisfy a family of resolvent conditions, which can roughly be viewed as a weak form of delocalization of sample-side singular vectors of the data. By analyzing these limiting dynamics, we can provide insights into learning rate, momentum parameter, and batch size selection. For instance, we identify a stability measurement, the implicit conditioning ratio (ICR), which regulates the ability of SGD+M to accelerate the algorithm. When the batch size exceeds this ICR, SGD+M converges linearly at a rate of $O(1/ \kappa)$, matching optimal full-batch momentum (in particular performing as well as a full-batch but with a fraction of the size). For batch sizes smaller than the ICR, in contrast, SGD+M has rates that scale like a multiple of the single batch SGD rate. We give explicit choices for the learning rate and momentum parameter in terms of the Hessian spectra that achieve this performance. Finally we show this model matches performances on real data sets.
DACO-FDS: Stochastic Algorithms in the Large: Batch Size Saturation, Stepsize Criticality, Generalization Performance, and Exact Dynamics (Part II)read_more
HG G 19.1
* 9 May 2023
14:15-15:30 		Prof. Dr. Susan Holmes
Stanford University
Event Details

DACO Seminar

Title Generative models for power, identifiability and goodness of fit testing
Speaker, Affiliation Prof. Dr. Susan Holmes, Stanford University
Date, Time 9 May 2023, 14:15-15:30
Location HG G 19.1
Abstract By linking conceptual theories with observed data, generative models can support reasoning in complex situations. They have come to play a central role both within and beyond statistics, providing the basis for power analysis in molecular biology, theory building in particle physics, and resource allocation in epidemiology. This talk will survey some applications of modern generative models and show how they inform experimental design, iterative model refinement, goodness-of-fit evaluation, and agent based simulation. We emphasize a modular view of generative mechanisms and discuss how they can be flexibly recombined in new problem contexts. Current research in generative models is currently split across several islands of activity, and we highlight opportunities lying at disciplinary intersections. This is joint work with Kris Sankaran that was recently published and for which practical illustrations are available at https://github.com/krisrs1128/generative_review.
Generative models for power, identifiability and goodness of fit testingread_more
HG G 19.1
* 16 May 2023
14:15-15:15 		Dr. Daniel Bartl
University of Vienna, Austria
Event Details

DACO Seminar

Title On high dimensional Dvoretzky–Kiefer–Wolfowitz type inequalities
Speaker, Affiliation Dr. Daniel Bartl, University of Vienna, Austria
Date, Time 16 May 2023, 14:15-15:15
Location HG G 19.1
Abstract The DKW inequality is a non-asymptotic, high probability estimate on the L_\infty distance between the distribution function of a real-valued random variable and its empirical (random) counterpart. Little was known on generalisations of that inequality to high dimensions, where instead of a single random variable one is interested in the behaviour of empirical distribution functions of a family of marginals of a random vector. Based on chaining methods, we show that the behaviour of various notions of distance (including the L_\infty one) between the empirical and actual distributions of marginals in the given family can be fully characterised in terms of some (rather surprising) intrinsic complexity parameter of the family. Based on joint work with Shahar Mendelson.
On high dimensional Dvoretzky–Kiefer–Wolfowitz type inequalitiesread_more
HG G 19.1
* 24 May 2023
17:00-17:30 		Sabrina Bruckmeier
ETH Zurich, Switzerland
Event Details

DACO Seminar

Title Constrained Sparse Approximation over the Cube
Speaker, Affiliation Sabrina Bruckmeier, ETH Zurich, Switzerland
Date, Time 24 May 2023, 17:00-17:30
Location HG G 19.2
Abstract Due to the recent development in machine learning, data science and signal processing more and more data is generated, but only part of it might be necessary in order to already make predictions in a sufficiently good manner. Therefore, the question arises to best approximate a signal b by linear combinations of no more than \sigma vectors from a suitable dictionary A. Additionally, many areas of application - as for example portfolio selection theory, sparse linear discriminant analysis, general linear complementarity problems or pattern recognition - require the solution x to satisfy certain polyhedral constraints. This talk presents an analysis of the NP-hard minimization problem min{||b-Ax||: x \in [0,1]^n, |supp(x)| \leq \sigma} and its natural relaxation min{||b-Ax||: x \in [0,1]^n, \sum x_i \leq \sigma}. Our analysis includes a probabilistic view on when the relaxation is exact. We will also consider the problem from a deterministic point of view and provide a bound on the distance between the images of optimal solutions of the original problem and its relaxation under A. This leads to an algorithm for generic integer matrices A \in \mathbb{Z}^{m \times n} and achieves a polynomial running time provided that m and ||A||_{\infty} are fixed.
Constrained Sparse Approximation over the Cuberead_more
HG G 19.2
* 30 May 2023
14:15-15:00 		Felix Kuchelmeister
ETH Zurich, Switzerland
Event Details

DACO Seminar

Title Finite sample rates for logistic regression with small noise or few samples
Speaker, Affiliation Felix Kuchelmeister, ETH Zurich, Switzerland
Date, Time 30 May 2023, 14:15-15:00
Location HG G 19.2
Abstract The logistic regression estimator is known to inflate the magnitude of its coefficients if the sample size n is small, the dimension p is (moderately) large or the signal-to-noise ratio 1/\sigma is large (probabilities of observing a label are close to 0 or 1). With this in mind, we study the logistic regression estimator with p << n/\log n, assuming Gaussian covariates and labels generated by the Gaussian link function, with a mild optimization constraint on the estimator's length to ensure existence. We provide finite sample guarantees for its direction, which serves as a classifier, and its Euclidean norm, which is an estimator for the signal-to-noise ratio. We distinguish between two regimes. In the low-noise/small-sample regime (n\sigma <= p\log n), we show that the estimator's direction (and consequentially the classification error) achieve the rate (p\log n)/n - as if the problem was noiseless. In this case, the norm of the estimator is at least of order n/(p\log n). If instead n\sigma >= p\log n, the estimator's direction achieves the rate \sqrt{\sigma p\log n/n}, whereas its norm converges to the true norm at the rate \sqrt{p\log n/(n\sigma^3)}. As a corollary, the data are not linearly separable with high probability in this regime. The logistic regression estimator allows to conclude which regime occurs with high probability. Therefore, inference for logistic regression is possible in the regime n\sigma >= p\log n. In either case, logistic regression provides a competitive classifier. This is joint work with Sara van de Geer.
Finite sample rates for logistic regression with small noise or few samplesread_more
HG G 19.2
27 June 2023
14:15-16:00 		Prof. Dr. Nikita Zhivotovskiy
University of California Berkeley, Department of Statistics
Event Details

DACO Seminar

Title Optimal PAC Bounds without Uniform Convergence.
Speaker, Affiliation Prof. Dr. Nikita Zhivotovskiy, University of California Berkeley, Department of Statistics
Date, Time 27 June 2023, 14:15-16:00
Location HG G 19.2
Abstract In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hanneke established sharp upper bounds in this setting. However, the reliance of their argument on the uniform convergence principle limits its applicability to more general learning settings such as multiclass classification. In this talk, we will discuss a simple technique that addresses this issue. We will present optimal high probability risk bounds through a framework that surpasses the limitations of uniform convergence arguments. In addition to binary classification, we will see applications in settings where uniform convergence is provably sub-optimal. For multiclass classification, we prove an optimal risk bound scaling with the one-inclusion hypergraph density of the class, addressing the suboptimality of the analysis by Daniely and Shalev-Shwartz. Based on joint work with Ishaq Aden-Ali, Yeshwanth Cherapanamjeri and Abhishek Shetty.
Optimal PAC Bounds without Uniform Convergence.read_more
HG G 19.2
* 3 July 2023
15:15-16:15 		Prof. Dr. Jim Dai
Cornell University and The Chinese University of Hong Kong, Shenzhen
Event Details

DACO Seminar

Title Queueing Network Controls via Deep Reinforcement Learning (Financial and Insurance Mathematics seminar, cross-listed)
Speaker, Affiliation Prof. Dr. Jim Dai, Cornell University and The Chinese University of Hong Kong, Shenzhen
Date, Time 3 July 2023, 15:15-16:15
Location HG G 43
Abstract For more information on this seminar see page ``Talks in Financial and Insurance Mathematics'' at https://math.ethz.ch/imsf/courses/talks-in-imsf.html?s=fs23
More information https://math.ethz.ch/imsf/courses/talks-in-imsf.html?s=fs23
Queueing Network Controls via Deep Reinforcement Learning (Financial and Insurance Mathematics seminar, cross-listed)read_more
HG G 43
18 July 2023
13:15-14:15 		Prof. Dr. Chandra Chekuri
University of Illinois at Urbana-Champaign
Event Details

DACO Seminar

Title Densest Subgraph: Supermodularity and Iterative Peeling
Speaker, Affiliation Prof. Dr. Chandra Chekuri, University of Illinois at Urbana-Champaign
Date, Time 18 July 2023, 13:15-14:15
Location HG G 19.2
Abstract The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected graph G = (V, E) find a subset S of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the set of edges with both endpoints in S. DSG and several of its variants are well-studied in theory and practice and have several applications in data mining and network analysis. We study fast algorithms and structural aspects of DSG via the lens of supermodularity. For this we consider the densest supermodular subset problem (DSS): given a non-negative supermodular function f over a ground set V, maximize f(S)/|S|. Greedy peeling algorithms have been very popular for DSG and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for DSS and analyze its approximation guarantee in a fashion that unifies several existing results. Boob et al. developed an iterative peeling algorithm for DSG which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges for DSS. In subsequent work we also showed that the algorithm converges to the densest supermodular set decomposition. The proofs are based on connections between the LP relaxation for DSG suggested by Charikar, Lovász extension of a supermodular function, Fujishige's result on lexicographically optimal base in a (contra) polymatroid, and continuous optimization algorithms such Frank-Wolfe method and Multiplicative Weight Updates. Based on joint work in papers with Harb El Farouk, Kent Quanrud and Manuel Torres.
Densest Subgraph: Supermodularity and Iterative Peelingread_more
HG G 19.2
* 26 July 2023
10:00-11:00 		Prof. Dr. Neil Olver
London School of Economics and Political Science, London, UK
Event Details

DACO Seminar

Title Thin trees for laminar families
Speaker, Affiliation Prof. Dr. Neil Olver, London School of Economics and Political Science, London, UK
Date, Time 26 July 2023, 10:00-11:00
Location HG G 19.2
Abstract In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This conjecture, if true, has a variety of implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Using iterative relaxation, combined with a simple reduction technique, we show that the thin tree conjecture is true whenever the specified cuts form a laminar family. Joint work with Nathan Klein.
Thin trees for laminar familiesread_more
HG G 19.2
27 July 2023
10:00-11:30 		Dr. Martin Nägele
University of Bonn
Event Details

DACO Seminar

Title An Improved Approximation Guarantee for Prize-Collecting TSP
Speaker, Affiliation Dr. Martin Nägele, University of Bonn
Date, Time 27 July 2023, 10:00-11:30
Location HG G 19.1
Abstract We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may choose to not include a vertex of the input graph in the returned tour at the cost of a given vertex-dependent penalty, and the objective is to balance the length of the tour and the incurred penalties for omitted vertices by minimizing the sum of the two. We present an algorithm that achieves an approximation guarantee of 1.774 with respect to the natural linear programming relaxation of the problem. This significantly reduces the gap between the approximability of classical TSP and PCTSP, beating the previously best known approximation factor of 1.915. As a key ingredient of our improvement, we present a refined decomposition technique for solutions of the LP relaxation, and show how to leverage components of that decomposition as building blocks for our tours. This is joint work with Jannis Blauth.
An Improved Approximation Guarantee for Prize-Collecting TSPread_more
HG G 19.1

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

JavaScript has been disabled in your browser