8 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…
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 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…