arXiv research

Sharp inequalities for star bodies in 2D space.

We derive exponential tail inequalities for sums of random matrices with no dependence on the explicit matrix dimensions. These are similar to the matrix versions of the Chernoff bound and Bernstein inequality except with the explicit matrix dimensions replaced by a trace quantity that can be small even when the dimens…

Matrix Chernoff bound for Markov chains applied to co-occurrence matrices.

New inequalities for matrix supermartingales converge under various conditions.

Improved sample complexity for learning halfspaces with malicious noise.

New PAC-Bayes bounds for unbounded losses using Cramér-Chernoff techniques.

We improve the over-parametrization size over two beautiful results [Li and Liang' 2018] and [Du, Zhai, Poczos and Singh' 2019] in deep learning theory.

Paper analyzes trade-offs between fairness, privacy, and accuracy using Chernoff Information.

Unified approach to discrete and smooth isoperimetric inequalities of arbitrary order.

Paper extends Chernoff sampling for active testing and parameter estimation, improving neural network and regression models.

Two spectral algorithms for community detection in graphs with covariates are compared.

A note on extending Chernoff bound for unit interval random variables.

We prove a central limit theorem for the components of the eigenvectors corresponding to the $d$ largest eigenvalues of the normalized Laplacian matrix of a finite dimensional random dot product graph. As a corollary, we show that for stochastic blockmodel graphs, the rows of the spectral embedding of the normalized La…

Optimizes network sampling for efficient community detection.

Method bounds tail probabilities of continuous RVs.

New bounds for Neyman-Pearson region using $f$-divergences.

Sharp inequalities for matrix means with unknown variance.

Near-optimal confidence intervals for bounded data.

This paper introduces a new bound to explain generalization in over-parameterized models.

We study nonzero-sum hypothesis testing games that arise in the context of adversarial classification, in both the Bayesian as well as the Neyman-Pearson frameworks. We first show that these games admit mixed strategy Nash equilibria, and then we examine some interesting concentration phenomena of these equilibria. Our…

We study "active" decision making over sensor networks where the sensors' sequential probing actions are actively chosen by continuously learning from past observations. We consider two network settings: with and without central coordination. In the first case, the network nodes interact with each other through a centr…

The paper extends log-Sobolev inequalities to matrix-valued settings using combinatorial methods.

Simplified proof for approximations of set systems.

In this paper, we present a new framework to obtain tail inequalities for sums of random matrices. Compared with existing works, our tail inequalities have the following characteristics: 1) high feasibility--they can be used to study the tail behavior of various matrix functions, e.g., arbitrary matrix norms, the absol…

Derives matrix Harnack inequalities for semilinear heat equations on manifolds.

Improved regret bounds for DP-KLUCB and DP-IMED in Bernoulli bandits.

Paper proves inequality for Green function on Kähler manifolds.

Paper extends tail bounds to high-dimensional random objects on Riemannian manifolds.

This note gives a simple analysis of a randomized approximation scheme for matrix multiplication proposed by Sarlos (2006) based on a random rotation followed by uniform column sampling. The result follows from a matrix version of Bernstein's inequality and a tail inequality for quadratic forms in subgaussian random ve…

Recent research has made significant progress on the problem of bounding log partition functions for exponential family graphical models. Such bounds have associated dual parameters that are often used as heuristic estimates of the marginal probabilities required in inference and learning. However these variational est…

Nonnegative sectional curvature linked to matrix displacement convexity.

A new matrix concentration inequality for random products of matrices.

We prove constrained trace, matrix and constrained matrix Harnack inequalities for the nonlinear heat equation $ω_t=Δω+aω\ln ω$ on closed manifolds. We also derive a new interpolated Harnack inequality for the equation $ω_t=Δω-ω\lnω+\varepsilon Rω$ on closed surfaces under the $\varepsilon$-Ricci flow. Finally we prove…

We use topological methods to prove a semicontinuity property of the Hodge spectra for analytic germs defined on an isolated surface singularity. For this we introduce an analogue of the Seifert matrix (the fractured Seifert matrix), and of the Levine--Tristram signatures associated with it, defined for null-homologous…

From concentration inequalities for the suprema of Gaussian or Rademacher processes an inequality is derived. It is applied to sharpen existing and to derive novel bounds on the empirical Rademacher complexities of unit balls in various norms appearing in the context of structured sparsity and multitask dictionary lear…

Paper improves CI and CS for bounded means using betting and mixtures.

This work establishes always-valid risk bounds for online matrix completion.

The paper develops concentration inequalities for structured random data, extending beyond independent terms.

Study noncommutative Sobolev inequalities using quantum state metrics.

The aim of this paper is to provide some theoretical understanding of quasi-Bayesian aggregation methods non-negative matrix factorization. We derive an oracle inequality for an aggregated estimator. This result holds for a very general class of prior distributions and shows how the prior affects the rate of convergenc…

Let us assume that $f$ is a continuous function defined on the unit ball of $\mathbb R^d$, of the form $f(x) = g (A x)$, where $A$ is a $k \times d$ matrix and $g$ is a function of $k$ variables for $k \ll d$. We are given a budget $m \in \mathbb N$ of possible point evaluations $f(x_i)$, $i=1,...,m$, of $f$, which we …

In recent years, random matrices have come to play a major role in computational mathematics, but most of the classical areas of random matrix theory remain the province of experts. Over the last decade, with the advent of matrix concentration inequalities, research has advanced to the point where we can conquer many (…

We recall the Chernoff-Marsden definition of weak symplectic structure and give a rigorous treatment of the functional analysis and geometry of weak symplectic Banach spaces. We define the Maslov index of a continuous path of Fredholm pairs of Lagrangian subspaces in continuously varying Banach spaces. We derive basic …

We give a geometric interpretation of Hamilton's matrix Harnack inequality for the Ricci flow as the curvature of a connection on space-time.

This paper improves coreset size via smoothed analysis.

This paper gives new concentration inequalities for the spectral norm of a wide class of matrix martingales in continuous time. These results extend previously established Freedman and Bernstein inequalities for series of random matrices to the class of continuous time processes. Our analysis relies on a new supermarti…

Since Li and Yau obtained the gradient estimate for the heat equation, related estimates have been extensively studied. With additional curvature assumptions, matrix estimates that generalize such estimates have been discovered for various time-dependent settings, including the heat equation on a Kähler manifold, Ricci…

New model for community detection with side information improves recovery accuracy.