Tag - Optimization

Éva Tardos: Stability and Learning in Strategic Games

6th October, 2023

Over the last two decades we have developed good understanding how to quantify the impact of strategic user behaviour on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated games assuming players use a form of no-regret learning to adapt to the environment. We will review how this area evolved since its early days, and also discuss some of the new frontiers, including when repeated interactions have carry-over effects between rounds: when outcomes in one round effect the game in the future, as is the case in many applications. In this talk, we study this phenomenon in the context of a game modelling queuing systems: routers compete for servers, where packets that do not get served need to be resent, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. In joint work with Jason Gaitonde, we analyse the resulting highly dependent random process, and show bounds on the excess server capacity needed to guarantee that all packets get served despite the selfish (myopic) behaviour of the queues.

Ola Svensson: Polyhedral Techniques in Combinatorial Optimization: Matchings and Tours

5th October, 2023

We overview recent progress on two of the most classic problems in combinatorial optimization: the matching problem and the travelling salesman problem. We focus on deterministic parallel algorithms for the perfect matching problem and the first constant-factor approximation algorithm for the asymmetric travelling salesman problem. While these questions pose seemingly different challenges, recent progress has been achieved using similar polyhedral techniques. In particular, for both problems, we will explain the use linear programming formulations, even exponential-sized ones, to extract structure from problem instances to guide the design of better algorithms.

Sadhika Malladi: Mathematical Views on Modern Deep Learning Optimization

28th September, 2023

This talk focuses on how rigorous mathematical tools can be used to describe the optimization of large, highly non-convex neural networks. We start by covering how stochastic differential equations (SDEs) provide a rigorous yet flexible model of how deep networks change over the course of training. We then cover how the SDEs yield practical insights into scaling training to highly distributed settings while preserving generalization performance. In the second half of the talk, we will explore the new deep learning paradigm of pre-training and fine-tuning large language models. We show that fine-tuning can be described by a very simplistic mathematical model, and insights allow us to develop a highly efficient and performant optimizer to fine-tune LLMs at scale. The talk will focus on various mathematical tools and the extent to which they can describe modern day deep learning.

Huy Tuan Pham: Structures in Random Graphs: New Connections

28th July, 2023

In 1947, Paul Erdos famously gave a construction of graphs with no large cliques and independent sets via the probabilistic method. Since then, Erdos’ ingenious probabilistic insight and the emergence of structures in random graphs have motivated fundamental developments in combinatorics and probability. In this talk, I highlight several recent results in random graph studies with interesting connections to additive combinatorics, theoretical computer science and probability.

In joint work with David Conlon, Jacob Fox and Liana Yepremyan, we study structures in random Cayley graphs of general groups. Given a fixed finite group, random Cayley graphs are constructed by choosing the generating set at random. These graphs thus reflect interesting symmetries and properties of the group, at the cost of inducing complex dependencies. We will discuss results on clique and independence numbers in random Cayley graphs of general groups, as well as progress towards a conjecture of Alon on Cayley graphs with small clique and independence number. These questions are naturally connected with some fundamental problems in additive combinatorics, where we surprisingly discover that in some of them the group structure is superfluous.

Certain important aspects in the study of structures in random graphs can be phrased in terms of thresholds. In joint work with Jinyoung Park, building on insights in our resolution of Talagrand’s selector process conjecture, we prove the Kahn-Kalai conjecture, that thresholds of general monotone properties are closely predicted by expectation obstructions. The Kahn-Kalai conjecture is a beautiful milestone towards the understanding of emergence of general structures, and yet to complete the quest, it remains to study these expectation obstructions. This latter task can prove to be highly challenging in several cases and bring in interesting connections. As an illustration, I will discuss joint work with Vishesh Jain that determines the threshold for edge-colorings of complete bipartite graphs by exploiting connections to the Lovasz Local Lemma and local uniformity properties, which have played an important role in sampling solutions to constraint satisfaction problems.

Mohamed Ali: Self-similarity and stability analysis of flow: a numerical approach

24th June, 2023

I will discuss the motivation of using computational fluid dynamics to conduct a stability analysis of flow. Linear, non-linear and optimum optimization problems related to stability analysis will be discussed with some applications. Special attention will be given to the stability analysis of (i) the Batchelor vortex (swirling jet type) used to model the trailing vortex of aircraft and (ii) the helical vortex generated at the tip of a rotating blade. The self-similarity of the 3D helical vortex will be investigated. Then, the results of the stability analysis of the perturbed helical vortex with selected frequencies will be presented.

Diogo Gomes: Hessian Riemannian flows in mean-field games

15th February, 2023

Hessian Riemannian flows are a powerful tool for the construction of numerical schemes for monotone mean-field games that have their origin in constrained optimization problems. In this talk, we discuss the general construction of these flows for monotone mean-field games, their existence and regularity properties, and their asymptotic convergence.

Emanuel Carneiro: Hilbert spaces and low-lying zeros of L-functions

10th November, 2022

In this talk I would like to present some ideas behind a general Hilbert space framework for solving certain optimization problems that arise when studying the distribution of the low-lying zeros of families of L-functions. For instance, in connection to previous work of Iwaniec, Luo, and Sarnak (2000), we will discuss how to use information from one-level density theorems to estimate the proportion of non-vanishing of L-functions in a family at a low-lying height on the critical line. We will also discuss the problem of estimating the height of the first low-lying zero in a family, considered by Hughes and Rudnick (2003) and Bernard (2015). This is based on joint work with M. Milinovich and A. Chirre.

Julián David Gutiérrez Pineda: Machine learning architectures for mean-field games models of price formation

29th September, 2022

In this talk, we approach the solution of mean-field game systems arising in price formation models employing machine learning. We use a min-max characterization of the optimal control and price variables. We guarantee the convergence of the training algorithm using first-order conditions of the underlying optimal control problem. Numerical results for linear-quadratic models illustrate our results.

Wenqing Li: Backdoor attack detection in deep neural networks: a coherence optimization based method

13th June, 2022

Backdoor attacks impose a new threat in Deep Neural Networks (DNNs), where a backdoor is inserted into the neural network by poisoning the training dataset, misclassifying inputs that contain the adversary trigger. The major challenge for defending against these attacks is that only the attacker knows the secret trigger and the target class. The problem is further exacerbated by the recent introduction of Hidden Triggers, where the triggers are carefully fused into the input, bypassing detection by human inspection and causing backdoor identification through anomaly detection to fail. To defend against such attacks, in this work we systematically analyze how representations, i.e., the set of neuron activations for a given DNN when using the training data as inputs, are affected by backdoor attacks. We propose PiDAn, an algorithm based on coherence optimization purifying the poisoned data. Our analysis shows that representations of poisoned data and authentic data in the target class are still embedded in different linear subspaces, which implies that they show different coherence with some latent spaces. Based on this observation, the proposed PiDAn algorithm learns a sample-wise weight vector to maximize the projected coherence of weighted samples, where we demonstrate that the learned weight vector has a natural grouping effect'' and is distinguishable between authentic data and poisoned data. This enables the systematic detection and mitigation of backdoor attacks. Based on our theoretical analysis and experimental results, we demonstrate the effectiveness of PiDAn in defending against backdoor attacks that use different settings of poisoned samples on GTSRB and ILSVRC2012 datasets in comparison with the state-of-the-art methods. Our PiDAn algorithm can detect more than 90% infected classes and identify 95% poisoned samples.