BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Kyle Luh

Kyle Luh contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithmsmath.PRMachine Learningmath.COquant-phArtificial IntelligenceComputer VisionDiscrete Mathematicsmath.CVmath.FAmath.OCmath.STStatistics Theory

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
13topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2023arXiv

Rate of Convergence in Multiple SLE using Random Matrix Theory

We provide an order of convergence for a version of the Carathéodory convergence for the multiple SLE model with a Dyson Brownian motion driver towards its hydrodynamic limit, for $β=1$ and $β=2$. The result is obtained by combining techniques from the field of Schramm-Loewner Evolutions with modern techniques from random matrices. Our approach shows how one can apply modern tools used in the proof of universality in random matrix theory, in the field of Schramm-Loewner Evolutions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Analog quantum algorithms for the mixing of Markov chains

The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently we provided an upper bound on the quantum mixing time for Erdös-Renyi random graphs [Phys. Rev. Lett. 124, 050501 (2020)]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Robustness Implies Generalization via Data-Dependent Generalization Bounds

This paper proves that robustness implies generalization via data-dependent generalization bounds. As a result, robustness and generalization are shown to be connected closely in a data-dependent manner. Our bounds improve previous bounds in two directions, to solve an open problem that has seen little development since 2010. The first is to reduce the dependence on the covering number. The second is to remove the dependence on the hypothesis space. We present several examples, including ones for lasso and deep learning, in which our bounds are provably preferable. The experiments on real-world data and theoretical models demonstrate near-exponential improvements in various situations. To achieve these improvements, we do not require additional assumptions on the unknown distribution; instead, we only incorporate an observable and computable property of the training samples. A key technical innovation is an improved concentration bound for multinomial random variables that is of independent interest beyond robustness and generalization.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates

We study the algorithmic problem of estimating the mean of heavy-tailed random vector in $\mathbb{R}^d$, given $n$ i.i.d. samples. The goal is to design an efficient estimator that attains the optimal sub-gaussian error bound, only assuming that the random vector has bounded mean and covariance. Polynomial-time solutions to this problem are known but have high runtime due to their use of semi-definite programming (SDP). Conceptually, it remains open whether convex relaxation is truly necessary for this problem. In this work, we show that it is possible to go beyond SDP and achieve better computational efficiency. In particular, we provide a spectral algorithm that achieves the optimal statistical performance and runs in time $\widetilde O\left(n^2 d \right)$, improving upon the previous fastest runtime $\widetilde O\left(n^{3.5}+ n^2d\right)$ by Cherapanamjeri el al. (COLT '19). Our algorithm is spectral in that it only requires (approximate) eigenvector computations, which can be implemented very efficiently by, for example, power iteration or the Lanczos method. At the core of our algorithm is a novel connection between the furthest hyperplane problem introduced by Karnin et al. (COLT '12) and a structural lemma on heavy-tailed distributions by Lugosi and Mendelson (Ann. Stat. '19). This allows us to iteratively reduce the estimation error at a geometric rate using only the information derived from the top singular vector of the data matrix, leading to a significantly faster running time.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A nonuniform Littlewood-Offord inequality for all norms

Let $\mathbf{v}_i$ be vectors in $\mathbb{R}^d$ and $\{\varepsilon_i\}$ be independent Rademacher random variables. Then the Littlewood-Offord problem entails finding the best upper bound for $\sup_{\mathbf{x} \in \mathbb{R}^d} \mathbb{P}(\sum \varepsilon_i \mathbf{v}_i = \mathbf{x})$. Generalizing the uniform bounds of Littlewood-Offord, Erdős and Kleitman, a recent result of Dzindzalieta and Juškevičius provides a non-uniform bound that is optimal in its dependence on $\|\mathbf{x}\|_2$. In this short note, we provide a simple alternative proof of their result. Furthermore, our proof demonstrates that the bound applies to any norm on $\mathbb{R}^d$, not just the $\ell_2$ norm. This resolves a conjecture of Dzindzalieta and Juškevičius.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Eigenvectors and controllability of non-Hermitian random matrices and directed graphs

We study the eigenvectors and eigenvalues of random matrices with iid entries. Let $N$ be a random matrix with iid entries which have symmetric distribution. For each unit eigenvector $\mathbf{v}$ of $N$ our main results provide a small ball probability bound for linear combinations of the coordinates of $\mathbf{v}$. Our results generalize the works of Meehan and Nguyen as well as Touri and the second author for random symmetric matrices. Along the way, we provide an optimal estimate of the probability that an iid matrix has simple spectrum, improving a recent result of Ge. Our techniques also allow us to establish analogous results for the adjacency matrix of a random directed graph, and as an application we establish controllability properties of network control systems on directed graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Four Deviations Suffice for Rank 1 Matrices

We prove a matrix discrepancy bound that strengthens the famous Kadison-Singer result of Marcus, Spielman, and Srivastava. Consider any independent scalar random variables $ξ_1, \ldots, ξ_n$ with finite support, e.g. $\{ \pm 1 \}$ or $\{ 0,1 \}$-valued random variables, or some combination thereof. Let $u_1, \dots, u_n \in \mathbb{C}^m$ and $$ σ^2 = \left\| \sum_{i=1}^n \text{Var}[ ξ_i ] (u_i u_i^{*})^2 \right\|. $$ Then there exists a choice of outcomes $\varepsilon_1,\ldots,\varepsilon_n$ in the support of $ξ_1, \ldots, ξ_n$ s.t. $$ \left \|\sum_{i=1}^n \mathbb{E} [ ξ_i] u_i u_i^* - \sum_{i=1}^n \varepsilon_i u_i u_i^* \right \| \leq 4 σ. $$ A simple consequence of our result is an improvement of a Lyapunov-type theorem of Akemann and Weaver.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

How fast do quantum walks mix?

The fundamental problem of sampling from the limiting distribution of quantum walks on networks, known as \emph{mixing}, finds widespread applications in several areas of quantum information and computation. Of particular interest in most of these applications, is the minimum time beyond which the instantaneous probability distribution of the quantum walk remains close to this limiting distribution, known as the \emph{quantum mixing time}. However this quantity is only known for a handful of specific networks. In this letter, we prove an upper bound on the quantum mixing time for \emph{almost all networks}, i.e.\ the fraction of networks for which our bound holds, goes to one in the asymptotic limit. To this end, using several results in random matrix theory, we find the quantum mixing time of Erdös-Renyi random networks: networks of $n$ nodes where each edge exists with probability $p$ independently. For example for dense random networks, where $p$ is a constant, we show that the quantum mixing time is $\mathcal{O}\left(n^{3/2 + o(1)}\right)$. Besides opening avenues for the analytical study of quantum dynamics on random networks, our work could find applications beyond quantum information processing. Owing to the universality of Wigner random matrices, our results on the spectral properties of random graphs hold for general classes of random matrices that are ubiquitous in several areas of physics. In particular, our results could lead to novel insights into the equilibration times of isolated quantum systems defined by random Hamiltonians, a foundational problem in quantum statistical mechanics.

0 citations0 reviewsNo code linkedOpen access