arXiv research

The paper tackles dictionary learning with almost sure error constraints.

In this article we dwell into the class of so called ill posed Linear Inverse Problems (LIP) in machine learning, which has become almost a classic in recent times. The fundamental task in an LIP is to recover the entire signal / data from its relatively few random linear measurements. Such problems arise in variety of…

Using integration by parts on Gaussian space we construct a Stein Unbiased Risk Estimator (SURE) for the drift of Gaussian processes using their local and occupation times. By almost-sure minimization of the SURE risk of shrinkage estimators we derive an estimation and de-noising procedure for an input signal perturbed…

We introduce the notion of a stationary random manifold and develop the basic entropy theory for it. Examples include manifolds admitting a compact quotient under isometries and generic leaves of a compact foliation. We prove that the entropy of an ergodic stationary random manifold is zero if and only if the manifold …

Paper proves convergence of SA algorithm via martingale and converse Lyapunov methods.

The purpose of this paper is to provide further understanding into the structure of the sequential allocation ("stochastic multi-armed bandit", or MAB) problem by establishing probability one finite horizon bounds and convergence rates for the sample (or "pseudo") regret associated with two simple classes of allocation…

Paper establishes convergence rates and concentration bounds for stochastic approximation and reinforcement learning with Markovian noise.

The purpose of this paper is to provide a sharp analysis on the asymptotic behavior of the Durbin-Watson statistic. We focus our attention on the first-order autoregressive process where the driven noise is also given by a first-order autoregressive process. We establish the almost sure convergence and the asymptotic n…

The paper analyzes convergence rates for stochastic approximation and reinforcement learning.

A well-conditioned Jacobian spectrum has a vital role in preventing exploding or vanishing gradients and speeding up learning of deep neural networks. Free probability theory helps us to understand and handle the Jacobian spectrum. We rigorously show almost sure asymptotic freeness of layer-wise Jacobians of deep neura…

We reveal a model rank that predicts successful recovery of target functions at overparameterization.

Learning from unlabeled and noisy data is one of the grand challenges of machine learning. As such, it has seen a flurry of research with new ideas proposed continuously. In this work, we revisit a classical idea: Stein's Unbiased Risk Estimator (SURE). We show that, in the context of image recovery, SURE and its gener…

Tensor CANDECOMP/PARAFAC (CP) decomposition is an important tool that solves a wide class of machine learning problems. Existing popular approaches recover components one by one, not necessarily in the order of larger components first. Recently developed simultaneous power method obtains only a high probability recover…

First-passage percolation affects graph properties like curvature and geodesics.

A new hybrid Newton algorithm improves convergence in logistic regression.

Random quotients preserve hyperbolic properties in groups.

A martingale \int H.dZ is defined as having Dimension k if H has rank k almost surely, almost all t. Dimension can be used as a geometric invariant to classify and study martingales. We also define general Brownian motions in higher dimensions.

Random branched covers of groups are homotopy equivalent to geometrically small cancellation complexes.

We study two global structural properties of a graph $Γ$, denoted AS and CFS, which arise in a natural way from geometric group theory. We study these properties in the Erdös--Rényi random graph model G(n,p), proving a sharp threshold for a random graph to have the AS property asymptotically almost surely, and giving f…

We show that gradient descent converges to a local minimizer, almost surely with random initialization. This is proved by applying the Stable Manifold Theorem from dynamical systems theory.

New algorithm solves saddle point problems in Banach spaces.

Let $M$ be a pinched negatively curved Riemannian manifold, whose unit tangent bundle is endowed with a Gibbs measure $m_F$ associated to a potential $F$. We compute the Hausdorff dimension of the conditional measures of $m_F$. We study the $m_F$-almost sure asymptotic penetration behaviour of locally geodesic lines of…

This short note has been written as an Oberwolfach report for the workshop "Differentialgeometrie im Grossen". We discuss properties of metric spaces that at almost all points admit a tangent metric space. We explain why, under some mild assumptions, the tangents are almost surely subFinsler Carnot groups. We mention s…

In this work we construct an optimal linear shrinkage estimator for the covariance matrix in high dimensions. The recent results from the random matrix theory allow us to find the asymptotic deterministic equivalents of the optimal shrinkage intensities and estimate them consistently. The developed distribution-free es…

Paper solves graph matching problem using convex relaxation to the simplex.

Testing-by-betting strategies almost surely go bankrupt under null hypotheses.

We study first passage percolation (FPP) on a Gromov-hyperbolic group $G$ with boundary $\partial G$ equipped with the Patterson-Sullivan measure $ν$. We associate an i.i.d.\ collection of random passage times to each edge of a Cayley graph of $G$, and investigate classical questions about the asymptotics of first pass…

We provide the first solution for model-free reinforcement learning of ω-regular objectives for Markov decision processes (MDPs). We present a constructive reduction from the almost-sure satisfaction of ω-regular objectives to an almost- sure reachability problem and extend this technique to learning how to control an …

New algorithm achieves almost exact graph matching in almost quadratic time.

New betting strategy reduces regret to ln(ln n) with protection against adversarial data.

Study sparse function recovery from indirect noisy observations using $\ell^1$-regularization.

The paper analyzes convergence rates for SGD and SHB methods.

TSAW improves MCMC integral estimation with faster convergence.

We propose a unified and systematic framework for performing online nonnegative matrix factorization in the presence of outliers. Our framework is particularly suited to large-scale data. We propose two solvers based on projected gradient descent and the alternating direction method of multipliers. We prove that the se…

Maximal concentration bounds for stochastic approximation with heavy-tailed noise.

Unified framework for pattern recovery in penalized and thresholded estimation.

This paper formalizes $Q$-learning and linear TD convergence using Lean 4.

In this paper, we develop an approach to recursively estimate the quadratic risk for matrix recovery problems regularized with spectral functions. Toward this end, in the spirit of the SURE theory, a key step is to compute the (weak) derivative and divergence of a solution with respect to the observations. As such a so…

In this work we construct an optimal shrinkage estimator for the precision matrix in high dimensions. We consider the general asymptotics when the number of variables $p\rightarrow\infty$ and the sample size $n\rightarrow\infty$ so that $p/n\rightarrow c\in (0, +\infty)$. The precision matrix is estimated directly, wit…

We reformulate LIPs as min-max problems for easier solution.

In this paper, we prove some convergence results of a special case of optimistic policy iteration algorithm for stochastic shortest path problem. We consider both Monte Carlo and $TD(λ)$ methods for the policy evaluation step under the condition that the termination state will eventually be reached almost surely.

We study graph matching with correlated Gaussian features and find thresholds for exact recovery.

Geodesics spiral around compact subsets in CAT(0) spaces.

We present an actor-critic framework for MDPs where the objective is the variance-adjusted expected return. Our critic uses linear function approximation, and we extend the concept of compatible features to the variance-adjusted setting. We present an episodic actor-critic algorithm and show that it converges almost su…

Threshold found for embedding 2D complexes into random 2-complexes.

Randomly glued tetrahedra form connected 3-manifolds with a single boundary.

It is shown that curvature-dimension bounds CD(N, k) for a metric measure space (X,d,m) in the sense of Sturm imply a weak L^1- Poincare-inequality under some symmetry assumption on the choice of transport rays in the cut locus of (X,d). This condition is satisfied if (X,d) has m-almost surely no branching points.

SGD converges almost surely in non-convex problems, avoiding saddle points and accelerating convergence.