Refine Dimension Reduction using Probabilistic Surrogate Models

Combinatorics and Probability

Speaker:

Hengrui Luo

Institution:

Lawrence Berkeley National Laboratory and UCB

Time:

Wednesday, May 31, 2023 - 1:00pm

Location:

440R Rowland Hall

We introduce an efficient and robust auto-tuning framework for hyperparameter selection in dimension reduction (DR) algorithms, focusing on large-scale datasets and arbitrary performance metrics. By leveraging Bayesian optimization with a surrogate model, our approach enables efficient hyperparameter selection with multi-objective trade-offs and allows us to perform data-driven sensitivity analysis. By incorporating normalization and subsampling, the proposed framework demonstrates versatility and efficiency, as shown in applications to visualization techniques such as t-SNE and UMAP. We evaluate our results on various synthetic and real-world datasets using multiple quality metrics, providing a robust and efficient solution for hyperparameter selection in DR algorithms.

The geometry of bilinear forms in extremal graph theory

Combinatorics and Probability

Speaker:

Sam Mattheus

Speaker Link:

https://sammattheus.wordpress.com/research/

Institution:

UCSD

Time:

Wednesday, May 17, 2023 - 1:00pm to 2:00pm

Host:

Asaf Ferber

Location:

440R Rowland Hall

Problems in extremal graph theory typically aim to maximize some graph parameters under local restrictions. In order to prove lower bounds for these kinds of problems, several techniques have been developed. The most popular one, initiated by Paul Erdős, is the probabilistic method. While this technique has enjoyed tremendous success, it does not always provide sharp lower bounds. Frequently, algebraically and geometrically defined graphs outperform random graphs. We will show how historically, geometry over finite fields has been a rich source of such graphs. I will show a broad class of graphs defined from the geometry of finite fields, which has found several recent applications in extremal graph theory. Often, certain interesting families of graphs had in fact already been discovered and studied, years before their value in extremal graph theory was realized. I will demonstrate some instances of this phenomenon as well, which indicates that there might still be uncharted territory to explore.

On sharp isoperimetric inequalities on the hypercube

Combinatorics and Probability

Speaker:

Paata Ivanisvili

Speaker Link:

https://sites.google.com/view/paata

Institution:

UCI

Time:

Wednesday, April 26, 2023 - 11:30am to 12:30pm

Location:

RH 340P

I will talk about sharp isoperimetric inequalities on the hypercube refining several
results due to Kahn--Park and Talagrand. In the second half of the talk I will present Talagrand's isoperimetric inequalities
for functions taking values in a Banach space having finite cotype. In addition to that, several different proofs
of recently resolved Talagrand's conjecture will be presented.

This is joint with David Beltran and José Ramón Madrid Padilla.

Semidefinite programming on population clustering: a global analysis

Combinatorics and Probability

Speaker:

Shuheng Zhou

Speaker Link:

https://sites.google.com/view/shuhengz

Institution:

UC Riverside

Time:

Wednesday, May 10, 2023 - 1:00pm to 2:00pm

Location:

440R Rowland Hall

In this paper, we consider the problem of partitioning a small data sample of size n drawn from a mixture of 2 sub-gaussian distributions. Our work is motivated by the application of clustering individuals according to their population of origin using markers, when the divergence between the two populations is small. We are interested in the case that individual features are of low average quality γ, and we want to use as few of them as possible to correctly partition the sample. We consider semidefinite relaxation of an integer quadratic program which is formulated essentially as finding the maximum cut on a graph where edge weights in the cut represent dissimilarity scores between two nodes based on their features.

A small simulation result in Blum, Coja-Oghlan, Frieze and Zhou (2007, 2009) shows that even when the sample size n is small, by
increasing p so that $np= \Omega(1/\gamma^2)$ , one can classify a mixture of two product populations using the spectral method therein with success rate reaching an ``oracle'' curve. There the ``oracle'' was computed assuming that distributions were known,
where success rate means the ratio between correctly classified individuals and the sample size n. In this work, we show the theoretical underpinning of this observed concentration of measure phenomenon in high dimensions, simultaneously for the semidefinite optimization goal and the spectral method, where the input is based on the gram matrix computed from centered data. We allow a full range of tradeoffs between the sample size and the number of features such that the product of these two is lower bounded by $1/\gamma^2$ so long as the number of features p is lower bounded by $1/\gamma$ .

Beyond the broken tetrahedron

Combinatorics and Probability

Speaker:

Bjarne Schuelke

Speaker Link:

https://sites.google.com/view/bjarneschuelke/home

Institution:

Caltech

Time:

Wednesday, April 12, 2023 - 1:00pm to 2:00pm

Host:

Asaf Ferber

Location:

440R Rowland Hall

Here we consider the hypergraph Tur\'an problem in uniformly dense hypergraphs as was suggested by Erd\H{o}s and S\'os. Given a $3$ -graph $F$ , the uniform Tur\'an density $\pi_u(F)$ of $F$ is defined as the supremum over all $d\in[0,1]$ for which there is an $F$ -free uniformly $d$ -dense $3$ -graph, where uniformly $d$ -dense means that every linearly sized subhypergraph has density at least $d$ . Recently, Glebov, Kr\'al', and Volec and, independently, Reiher, R\"odl, and Schacht proved that $\pi_u(K_4^{(3)-})=\frac{1}{4}$ , solving a conjecture by Erd\H{o}s and S\'os. There are very few hypergraphs for which the uniform Tur\'an density is known. In this work, we determine the uniform Tur\'an density of the $3$ -graph on five vertices that is obtained from $K_4^{(3)-}$ by adding an additional vertex whose link forms a matching on the vertices of $K_4^{(3)-}$ . Further, we point to two natural intermediate problems on the way to determining $\pi_u(K_4^{(3)})$ and solve the first of these.

This talk is based on joint work with August Chen.

Sum-of-squares proofs for the trace power method

Combinatorics and Probability

Speaker:

Jonathan Shi

Speaker Link:

https://www.jshi.science/

Institution:

UCSD

Time:

Wednesday, May 3, 2023 - 1:00pm to 2:00pm

Location:

440R Rowland Hall

The sum-of-squares framework converts proofs into algorithms so long as those proofs can be formulated as sum-of-squares proofs—proofs that demonstrate their conclusions via the non-negativity of square polynomials. This is a powerful framework that captures many inequalities known in analysis. We formulate sum-of-squares proofs for the trace power method by giving sum-of-squares proofs for non-commutative (matrix) inequalities including the Araki-Lieb-Thirring inequality and Holder's inequality for Schatten norms, and sketch how one might use these proofs to obtain algorithms to constructively find solutions to random optimization problems whose upper bounds can be proven by techniques in random matrix and spin glass theory. Based on work in progress with Juspreet Singh Sandhu.

Amalgamated finite free convolutions: Towards a unified theory for proving root bounds

Combinatorics and Probability

Speaker:

Jorge Garza Vargas

Speaker Link:

https://jgarzavargas.people.caltech.edu/

Institution:

Caltech

Time:

Wednesday, April 19, 2023 - 1:00pm to 2:00pm

Location:

440R Rowland Hall

Between 2013 and 2015, Marcus, Spielman and Srivastava wrote a sequence of papers where they famously solved the Kadison-Singer problem and proved the existence of Ramanujan graphs of all sizes. For the latter, they used a convolution of polynomials introduced by Walsh, which they showed to have surprising connections to free probability theory. This discovery gave rise to finite free probability, which studies polynomial convolutions from a free probability perspective. With the aim of unifying the results of Marcus, Spielman and Srivastava, and developing general machinery for deducing root bounds, we extend the framework of finite free probability to multivariate polynomials. We show that this extended framework has interesting parallels with the theory of freeness with amalgamation, and can potentially be used to obtain important results in diverse areas, ranging from algebraic combinatorics to operator theory. This is work in progress with Nikhil Srivastava.

The Smith normal form of a polynomial of a random integral matrix

Combinatorics and Probability

Speaker:

Gilyoung Cheong

Speaker Link:

https://sites.google.com/view/gcheong/

Institution:

UCI

Time:

Wednesday, April 5, 2023 - 1:00pm to 2:00pm

Location:

440R Rowland Hall

Given a prime

$p$ , let

$P(t)$ be a non-constant monic polynomial in

$t$ over the ring

$\mathbb{Z}_{p}$ of

$p$ -adic integers. Let

$X_n$ be the

$n \times n$ uniformly random (0,1)-matrix over

$\mathbb{Z}_{p}$ . We compute the asymptotic distribution of the cokernel of

$P(X_n)$ as

$n$ goes to infinity. When

$P(t)$ is square-free modulo

$p$ , this lets us compute the asymptotic distribution of the Smith normal form of

$P(X_n)$ . In fact, we shall consider the same problem with a more general random matrix

$X_n$ , which also includes the example of a Haar-random matrix. Our work crucially uses a recent work of W. Sawin and M. M. Wood which shows that the moments of finite size modules over any ring determine their distribution. This is joint work with Myungjun Yu. https://arxiv.org/abs/2303.09125

The characteristic polynomial of sums of random permutations

Combinatorics and Probability

Speaker:

Yizhe Zhu

Speaker Link:

https://sites.google.com/uci.edu/yizhezhu

Institution:

UCI

Time:

Wednesday, January 18, 2023 - 2:00pm to 3:00pm

Location:

510R Rowland Hall

Let $A_n$ be the sum of $d$ permutation matrices of size $n\times n$ , each drawn uniformly at random and independently. We prove that the normalized characteristic polynomial $\frac{1}{\sqrt{d}}\det(I_n - z A_n/\sqrt{d})$ converges when $n\to \infty$ towards a random analytic function on the unit disk. As an application, we obtain an elementary proof of the spectral gap of random regular digraphs. Our results are valid both in the regime where $d$ is fixed and for $d$ slowly growing with $n$ .

Joint work with Simon Coste and Gaultier Lambert. https://arxiv.org/abs/2204.00524

Robustness of graph theory theorems

Combinatorics and Probability

Speaker:

Jie Han

Speaker Link:

https://jiehan773.github.io/

Institution:

Beijing Institute of Technology

Time:

Wednesday, February 1, 2023 - 2:00pm to 3:00pm

Host:

Asaf Ferber

Location:

510R Rowland Hall

Dirac's theorem says that any n-vertex graph with minimum degree at least n/2 contains a Hamiltonian cycle. A robust version of Dirac's theorem was obtained by Krivelevich, Lee and Sudakov: for such graphs, if we take a random subgraph where every edge is included with probability Clog(n)/n, for some large fixed constant C, then whp the resulting graph is still Hamiltonian. We will discuss some recent results along this line.

Combinatorics and Probability

Speaker:

Institution:

Time:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Host:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Host:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Location:

Speaker:

Speaker Link:

Institution:

Time:

Host:

Location:

Pages