arXiv research

In this note, we derive concentration inequalities for random vectors with subGaussian norm (a generalization of both subGaussian random vectors and norm bounded random vectors), which are tight up to logarithmic factors.

Deep networks with path norm regularization can approximate analytic functions.

Lueck expressed the Gromov norm of a knot complement in terms of an infinite series that can be computed from a presentation of the fundamental group of the knot complement. In this note we show that Lueck's formula, applied to torus knots, yields surprising power series expansions for the logarithm function. This gene…

New algorithm reduces regret from sqrt(T) to polylog(T) in stochastic contextual linear bandits.

A new interpolation method speeds up neural ODE training.

In this paper, we consider low rank matrix estimation using either matrix-version Dantzig Selector $\hat{A}_λ^d$ or matrix-version LASSO estimator $\hat{A}_λ^L$. We consider sub-Gaussian measurements, $i.e.$, the measurements $X_1,\ldots,X_n\in\mathbb{R}^{m\times m}$ have $i.i.d.$ sub-Gaussian entries. Suppose $\textrm…

We study the generalization properties of minimum-norm solutions for three over-parametrized machine learning models including the random feature model, the two-layer neural network model and the residual network model. We proved that for all three models, the generalization error for the minimum-norm solution is compa…

We study the Seiberg-Witten equations on surfaces of logarithmic general type. First, we show how to construct irreducible solutions of the Seiberg-Witten equations for any metric which is "asymptotic" to a Poincaré type metric at infinity. Then we compute a lower bound for the $L^{2}$-norm of scalar curvature on these…

Estimates for geodesics on hyperbolic tori improve previous bounds.

Paper optimizes private PCA for covariance estimation in statistics.

The study analyzes robustness of estimators in linear models with adversarial errors.

Logarithmic network width suffices for robust memorization.

Study bounds for Brownian motion on manifolds with sticky boundary conditions.

New bounds on adaptivity cost in stochastic optimization.

We use Toponogov's triangle comparison theorem from Riemannian geometry along with quantitative scale oriented variants of classical propagation of singularities arguments to obtain logarithmic improvements of the Kakeya-Nikodym norms introduced in \cite{SKN} for manifolds of nonpositive sectional curvature. Using thes…

This paper studies Brownian motion and heat kernel measure on a class of infinite dimensional Lie groups. We prove a Cameron-Martin type quasi-invariance theorem for the heat kernel measure and give estimates on the $L^p$ norms of the Radon-Nikodym derivatives. We also prove that a logarithmic Sobolev inequality holds …

New framework for private convex optimization in arbitrary norms.

We investigate the statistical complexity of estimating the parameters of a discrete-state Markov chain kernel from a single long sequence of state observations. In the finite case, we characterize (modulo logarithmic factors) the minimax sample complexity of estimation with respect to the operator infinity norm, while…

Matrix rank minimizing subject to affine constraints arises in many application areas, ranging from signal processing to machine learning. Nuclear norm is a convex relaxation for this problem which can recover the rank exactly under some restricted and theoretically interesting conditions. However, for many real-world …

This paper deals with stability in the numerical solution of the prominent Heston partial differential equation from mathematical finance. We study the well-known central second-order finite difference discretization, which leads to large semi-discrete systems with non-normal matrices A. By employing the logarithmic sp…

New bounds for online portfolio selection without smoothness assumptions.

Develops a parameter-free SGD algorithm with optimal convergence rate.

The matrix completion problem consists in reconstructing a matrix from a sample of entries, possibly observed with noise. A popular class of estimator, known as nuclear norm penalized estimators, are based on minimizing the sum of a data fitting term and a nuclear norm penalization. Here, we investigate the case where …

Study inequalities on hyperbolic spaces and Riemannian manifolds using symmetrization and heat semigroup.

Matrix completion works well for smooth non-linear structures, even without low-rank assumptions.

We consider a variant of online convex optimization in which both the instances (input vectors) and the comparator (weight vector) are unconstrained. We exploit a natural scale invariance symmetry in our unconstrained setting: the predictions of the optimal comparator are invariant under any linear transformation of th…

Paper develops probabilistic bounds for a stochastic gradient algorithm in non-convex problems.

We show generalisation error bounds for deep learning with two main improvements over the state of the art. (1) Our bounds have no explicit dependence on the number of classes except for logarithmic factors. This holds even when formulating the bounds in terms of the $L^2$-norm of the weight matrices, where previous bo…

Let $A:[0,1]\rightarrow\mathbb{H}_m$ (the space of Hermitian matrices) be a matrix valued function which is low rank with entries in Hölder class $Σ(β,L)$. The goal of this paper is to study statistical estimation of $A$ based on the regression model $\mathbb{E}(Y_j|τ_j,X_j) = \langle A(τ_j), X_j \rangle,$ where $τ_j$ …

We consider the problem of distributed mean estimation (DME), in which $n$ machines are each given a local $d$-dimensional vector $x_v \in \mathbb{R}^d$, and must cooperate to estimate the mean of their inputs $μ= \frac 1n\sum_{v = 1}^n x_v$, while minimizing total communication cost. DME is a fundamental construct in …

We consider the two logarithmic strain measures\[ω_{\rm iso}=\|\mathrm{dev}_n\log U\|=\|\mathrm{dev}_n\log \sqrt{F^TF}\|\quad\text{ and }\quad ω_{\rm vol}=|\mathrm{tr}(\log U)|=|\mathrm{tr}(\log\sqrt{F^TF})|\,,\]which are isotropic invariants of the Hencky strain tensor $\log U$, and show that they can be uniquely char…

This paper analyzes shallow ReLU networks in L^p and Sobolev spaces, focusing on approximation and generalization.

Solves approximation problems for zonoids and neural networks, closing gaps in dimensions 2 and 3.

The paper analyzes generalization in deep contrastive learning.

New robust estimators achieve subgaussian bounds using VC-dimension.

Gaussian Graphical Models (GGMs) have wide-ranging applications in machine learning and the natural and social sciences. In most of the settings in which they are applied, the number of observed samples is much smaller than the dimension and they are assumed to be sparse. While there are a variety of algorithms (e.g. G…

Sharp lower bounds on shallow neural networks' approximation rates are derived.

We introduce and analyze a form of variance-reduced $Q$-learning. For $γ$-discounted MDPs with finite state space $\mathcal{X}$ and action space $\mathcal{U}$, we prove that it yields an $ε$-accurate estimate of the optimal $Q$-function in the $\ell_\infty$-norm using $\mathcal{O} \left(\left(\frac{D}{ ε^2 (1-γ)^3} \ri…

We are concerned about the coarse and precise aspects of a priori estimates for Green's function of a regular domain for the Laplacian-Betrami operator on any $3\le n$-dimensional complete non-compact boundary-free Riemannian manifold through the square Sobolev/Nash/logarithmic-Sobolev inequalities plus the rough and s…

We consider the closeness testing problem for discrete distributions. The goal is to distinguish whether two samples are drawn from the same unspecified distribution, or whether their respective distributions are separated in $L_1$-norm. In this paper, we focus on adapting the rate to the shape of the underlying distri…

Paper shows linear convergence of ISTA and FISTA for ill-conditioned images.

New estimator tackles multi-task linear regression with outliers, avoiding eigenvalue lower bounds.

Deep ReLU networks can efficiently approximate Sobolev and Besov functions.

We study products of random matrices in the regime where the number of terms and the size of the matrices simultaneously tend to infinity. Our main theorem is that the logarithm of the $\ell_2$ norm of such a product applied to any fixed vector is asymptotically Gaussian. The fluctuations we find can be thought of as a…

This paper illustrates a computational approach to Culler-Morgan-Shalen theory using ideal triangulations, spun-normal surfaces and tropical geometry. Certain affine algebraic sets associated to the Whitehead link complement as well as their logarithmic limit sets are computed. The projective solution space of spun-nor…

A parameter-free PGD algorithm for convex optimization.

In this paper, we introduce the notions of logarithmic Poisson structure and logarithmic principal Poisson structure; we prove that the latter induces a representation by logarithmic derivation of the module of logarithmic Kahler differentials; therefore, it induces a differential complex from which we derive the notio…

New lower bounds for private covariance estimation of Gaussian distributions are proven.