À¶Ý®ÊÓƵ

Title:: The training dynamics and local geometry of high-dimensional learning

Abstract:Many modern data science tasks can be expressed as optimizing a complex, random functions in high dimensions. The go-to methods for such problems are variations of stochastic gradient descent (SGD), which perform remarkably well—c.f. the success of modern neural networks. However, the rigorous analysis of SGD on natural, high-dimensional statistical models is in its infancy. In this talk, we study a general model that captures a broad range of learning tasks, from Matrix and Tensor PCA to training two-layer neural networks to classify mixture models. We show the evolution of natural summary statistics along training converge, in the high-dimensional limit, to a closed, finite-dimensional dynamical system called their effective dynamics. We then turn to understanding the landscape of training from the point-of-view of the algorithm. We show that in this limit, the spectrum of the Hessian and Information matrices admit an effective spectral theory: the limiting empirical spectral measure and outliers have explicit characterizations that depend only on these summary statistics. I will then illustrate how these techniques can be used to give rigorous demonstrations of phenomena observed in the machine learning literature such as the lottery ticket hypothesis and the "spectral alignment" phenomenona. This talk surveys a series of joint works with G. Ben Arous (NYU), R. Gheissari (Northwestern), and J. Huang (U Penn).

This talk is based on joint work with Saeed Ghadimi and Henry Wolkowicz from University of À¶Ý®ÊÓƵ and Diego Cifuentes and Renato Monteiro from Georgia Tech.

Ìý

Ìý

Title:ÌýNew Strongly Regular Graphs from Finite Semifields and Finite Geometry

Abstract: Finite geometry often provides natural examples of highly structured combinatorial objects, many of which exhibit strong symmetry properties.Ìý

In particular, many constructions of strongly regular graphs arise from classical geometric configurations. In this talk, we will present two new constructions of quasi-polar spaces, that give rise to two families of pairwise non-isomorphic strongly regular graphs, having the same non-trivial automorphism group.

Both constructions are related to a pair of commuting polarities in a projective space. Surprisingly, one of these constructions is connected to the algebraic structure of finite semifields and their tensor representation.

Title: Log-concavity of random Radon partitions

ÌýAbstract: Over one hundred years ago, Radon proved that any set of d+2 points in R^d can be partitioned into two sets whose convex hulls intersect. I will talk about Radon partitions when the points are selected randomly. In particular, if the points are independent normal random vectors, let p_k be the probability that the Radon partition has size (k, d+2-k). Answering a conjecture of Kalai and White, we show that the sequence (p_k) is ultra log-concave and that, in fact, a balanced partition is the most likely. Joint work with Swee Hong Chan, Gil Kalai, Bhargav Narayanan, and Moshe White.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title:ÌýExact algorithms for combinatorial interdiction problems

Abstract: Typical optimization paradigms involve a single decision maker that can control all variables involved. However, several practical situations involve multiple (potentially adversarial) decision makers. Bilevel optimization is a field that involves two decision makers. The key paradigm is that an upper-level decision maker acts first and after observing the upper-level decisions, a lower level decision maker optimizes their own objective. One particular important instance of such problems are so-called interdiction problems, where the upper-level decision is to try and forbid access to some decisions by the lower level and the goal of the upper level is to make the most impact into the lower-level decisions. These problems are, in general $\Sigma^P_2$-hard (likely harder than NP-hard).Ìý

Ìý

In this talk I will present recent work on improving significantly on state-of-the-art exact algorithms to obtain optimal solutions to some combinatorial interdiction problems. Despite the hardness results, our algorithm can solve instances consistently in a short amount of time. We also generalize our algorithms to propose a framework that could be applied to other similar problems, by deriving relaxations based on looking at these problems as games and performing operations on such games.Ìý

Ìý

This is joint work with Noah Weninger.

Ìý

Ìý

Title:ÌýQuantum Search with the Signless Laplacian

Abstract: Continuous-time quantum walks are typically effected by either the discrete Laplacian or the adjacency matrix. In this paper, we explore a third option: the signless Laplacian, which has applications in algebraic graph theory and may arise in layered antiferromagnetic materials. We explore spatial search on the complete bipartite graph, which is generally irregular and breaks the equivalence of the three quantum walks for regular graphs, and where the search oracle breaks the equivalence of the Laplacian and signless Laplacian quantum walks on bipartite graphs without the oracle. We prove that a uniform superposition over all the vertices of the graph partially evolves to the marked vertices in one partite set, with the choice of set depending on the jumping rate of the quantum walk. We boost this success probability to 1 by proving that a particular non-uniform initial state completely evolves to the marked vertices in one partite set, again depending on the jumping rate. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.

This is joint work with Molly McLaughlin.

Title:ÌýPrice of information in combinatorial optimization

Abstract: Pandora's box is a classical example of a combinatorial optimization problem in which the input is uncertain and can only be revealed to us after paying probing prices.

In this problem we are given a set of n items, where each i ∈ [n] has a deterministic probing price pi ∈ R+ and a random cost Ci ∈ R+. The cost Ci is only revealed after the probing price pi is paid. The goal is to adaptively probe a subset of items S ⊆ [n] and select a probed item in order to minimize the expected selection cost plus probing price: E[min_{i∈S} Ci + ∑_{i∈S} pi]. It is well known that if the costs are independent then the problem admits an efficient and simple optimal policy.

In this talk we discuss a paper by Sahil Singla that studies a generalization of this model to more general combinatorial optimization problems such as matching, set cover and facility location.

Title:Strongly connected orientations and integer lattices

Abstract: Let D = (V, A) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper 'slanted' face F of P. We prove under a mild necessary condition that the 0,1 points in FÌýcontain anÌýintegralÌýbasisÌýB, i.e., B is linearly independent, and every integral vector in the linear of span of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form aÌýHilbert basis.

Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say k, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any odd prime number p, a p-adic packing of dijoins of value k and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by the 0,1 points in F, where F is the face of P satisfying x(C) = 1 for every minimum dicut C.

This is based on joint work with Gerard Cornuejols, Siyue Liu, and Olha Silina.

Ìý

Ìý

Title:ÌýExplicit Lossless Vertex Expanders

Abstract: We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any ε>0 and sufficiently large d, we give an explicit construction of an infinite family of d-regular graphs where every small set S of vertices has (1−ε)d|S| neighbors (which implies (1−2ε)d|S| unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding algorithm.

Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes.

Based on joint work with Jun-Ting Hsieh, Alexander Lubotzky, Assaf Reiner, and Rachel Yun Zhang ()

Title:ÌýRandom analogues of Erd\H{o}s-Ko-Rado type results.

Abstract:ÌýThe classical Erd\H{o}s-Ko-Rado (EKR) theorem and its variants can be translated into characterizing maximum co-cliques of graphs in Association schemes. For instance, the classical Erd\H{o}s-Ko-Rado characterizes maximum co-cliques in the Kneser graph. Given a graph $G$, by $G_{p}$, we denote the random subgraph of $G$ in which edges appear independently, each with a probability $p$. In this talk, we consider the following question: for which probabilities is the independence number of $G_{p}$ equal to that of $G$? Bollabas-Narayanan-Raigorodskii investigated the independence numbers of random subgraphs of the Kneser graph. In this talk, we will investigate the independence numbers of random subgraphs of (i) the derangement graph on permutations; and (ii) the perfect matching graphs. The derangement graph is associated with the EKR type result on permutations and the perfect matching graph is associated with EKR type result on perfect matchings. This is joint work with the members of the PIMS Collaborative Research Group on Movement and Symmetry in graphs. ÌýÌý

Title:Arrangements and Likelihood

Abstract: In this talk, we establish connections between hypersurface arrangements and likelihood geometry. The central object is the likelihood correspondence which captures the dependence between data and critical points of the likelihood function of a statistical model parametrized by the polynomials defining the arrangement. In particle physics, this same object is known as the scattering correspondence. The connection to hypersurface arrangements leads to a new description of the prime ideal of the likelihood correspondence, which is often computationally advantageous. This description is based on the Rees algebra of the likelihood module of the arrangement, a module closely related to the module of logarithmic derivations. We present results for generic and graphic arrangements.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,