1 citations · 3 across the 17 of their papers we have counts for
19 papers
Counting Triangles of Graphs via Randomized Trace Estimation with Incomplete Matrix-Vector Products
Soumyadip Ghosh, Lior Horesh, Vasileios Kalantzis +3
Counting triangles in graphs is a fundamental operation in network analysis, underpinning metrics such as clustering coefficients and serving as a signal for community detection, l…
Analysis of Power Iteration Algorithm with Partially Observed Matrix-vector Products
Soumyadip Ghosh, Lior Horesh, Vassilis Kalantzis +3
We consider the problem of computing the dominant eigenvector of a symmetric matrix via the power iteration algorithm subject to constraints in the computation of matrix-vector pr…
On Hamiltonian Monte Carlo for Gaussian Random Variables with Random Hamiltonians
Yingdong Lu, Tomasz Nowicki
We study a family of (multivariate-)Gaussian Hamiltonian Monte Carlo (GHMC) operators and prove that the family of Gaussian distributions and their mixtures are invariant under suc…
Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions
Yanna Ding, Songtao Lu, Yingdong Lu +2
Transformer architectures can solve unseen tasks based on input-output pairs in a given prompt due to in-context learning (ICL). Existing theoretical studies on ICL have mainly foc…
Fast Linear Solvers via AI-Tuned Markov Chain Monte Carlo-based Matrix Inversion
Anton Lebedev, Won Kyung Lee, Soumyadip Ghosh +7
Large, sparse linear systems are pervasive in modern science and engineering, and Krylov subspace solvers are an established means of solving them. Yet convergence can be slow for…
Dynamical Behaviors of the Gradient Flows for In-Context Learning
Songtao Lu, Yingdong Lu, Tomasz Nowicki
We derive the system of differential equations for the gradient flow characterizing the training process of linear in-context learning in full generality. Next, we explore the geom…
On The Variance of Schatten -Norm Estimation with Gaussian Sketching Matrices
Lior Horesh, Vasileios Kalantzis, Yingdong Lu +1
Monte Carlo matrix trace estimation is a popular randomized technique to estimate the trace of implicitly-defined matrices via averaging quadratic forms across several observations…
On the iterations of some random functions with Lipschitz number one
Yingdong Lu, Tomasz Nowicki
For the iterations of random functions with Lipschitz number one, we represent the dynamics as a Markov chain and prove its convergence under mild conditions. We a…
Regenerative Ulam-von Neumann Algorithm: An Innovative Markov chain Monte Carlo Method for Matrix Inversion
Soumyadip Ghosh, Lior Horesh, Vassilis Kalantzis +2
This paper presents a regenerative variant of the classical Ulam-von Neumann Markov chain Monte Carlo algorithm for the approximation of the matrix inverse. The algorithm presented…
On Convergence of the Alternating Directions SGHMC Algorithm
Soumyadip Ghosh, Yingdong Lu, Tomasz Nowicki
We study convergence rates of Hamiltonian Monte Carlo (HMC) algorithms with leapfrog integration under mild conditions on stochastic gradient oracle for the target distribution (SG…
Non-Asymptotic Concentration of Magnetization in the Curie-Weiss Model at Subcritical Temperatures
Yingdong Lu
In this short paper, we obtain non-asymptotic concentration results for magnetization of the Curie-Weiss model at subcritical temperatures, which leads to a diffusion limit theorem…
On Representations of Mean-Field Variational Inference
Soumyadip Ghosh, Yingdong Lu, Tomasz Nowicki +1
The mean field variational inference (MFVI) formulation restricts the general Bayesian inference problem to the subspace of product measures. We present a framework to analyze MFVI…
Polynomial convergence of iterations of certain random operators in Hilbert space
Soumyadip Ghosh, Yingdong Lu, Tomasz J. Nowicki
We study the convergence of a random iterative sequence of a family of operators on infinite dimensional Hilbert spaces, inspired by the Stochastic Gradient Descent (SGD) algorithm…
Hamiltonian Monte Carlo with Asymmetrical Momentum Distributions
Soumyadip Ghosh, Yingdong Lu, Tomasz Nowicki
Existing rigorous convergence guarantees for the Hamiltonian Monte Carlo (HMC) algorithm use Gaussian auxiliary momentum variables, which are crucially symmetrically distributed. W…
On A Stein Method Based Approximation for A Two-Dimensional Markov Chain
Yingdong Lu
We study an approximation method of stationary characters of a two-dimensional Markov chain via the Stein method. For this purpose, innovative methods are developed to estimate the…
Local and Global Existence of A Nonlocal Equation with A Singular Integral Drift Term
Yingdong Lu
We study an initial value problem with fractional Laplacian and a singular drift term, and obtain local and global existence theorems similar to the results in Jourdain et al.(2005…
Approximating the Markov Chain of the Curie-Weiss Model
Yingdong Lu
In this paper, we quantify some known approximation to the Curie-Weiss model via applying the Stein method to the Markov chain whose stationary distribution coincides with Curie-We…
HMC, an Algorithms in Data Mining, the Functional Analysis approach
Soumyadip Ghosh, Yingdong Lu, Tomasz Nowicki
The main purpose of this paper is to facilitate the communication between the Analytic, Probabilistic and Algorithmic communities. We present a proof of convergence of the Hamilton…
On Convergence of the Hamiltonian Monte Carlo
Soumyadip Ghosh, Yingdong Lu, Tomasz Nowicki
We establish convergence for Hamiltonian Monte Carlo algorithms. More specifically, under mild conditions for the associated Hamiltonian motion, we show that the outputs of t…