Ding

Qinghua, Ding, Venkat Anantharam

The classical isomorphism theorems for reversible Markov chains have played an important role in studying the properties of local time processes of strongly symmetric Markov processes~\cite{mr06}, bounding the cover time of a graph by a random walk~\cite{dlp11}, and in topics related to physics, such as random walk loop soups and Brownian loop soups~\cite{lt07}. Non-reversible versions of these theorems have been discovered by Le Jan, Eisenbaum, and Kaspi~\cite{lejan08, ek09, eisenbaum13}. Here, we give a density-formula-based proof for all these non-reversible isomorphism theorems, extending the results in \cite{bhs21}. Moreover, we use this method to generalize the comparison inequalities derived in \cite{eisenbaum13} for permanental processes and derive an upper bound for the cover time of non-reversible Markov chains.

Qinghua, Ding, Venkat Anantharam

We study true self-avoiding walk (TSAW) as a mechanism for improving empirical integral estimation via Markov chain Monte Carlo (MCMC). We consider finite-state adaptive sampling dynamics associated with an irreducible Markov kernel $P$ on a finite set, with stationary distribution $π$, in which the transition probabilities are penalized according to empirical overuse. Our main result is that the empirical occupation counts $L_t(i)$ and transition counts $N_t(i,j)$ of the resulting TSAW-based walk satisfy \[ L_t(i)-tπ_i = O(\sqrt{\log t}) \quad\text{and}\quad N_t(i,j)-tπ_iP_{ij}=O(\sqrt{\log t}) \qquad\text{almost surely} \] for every state $i$ and every edge $(i,j)$ with $P_{ij}>0$. Consequently, for every bounded function $f:V\to\mathbb R$, the error of our integral estimator converges as \[ \left|\frac1t\sum_{s=0}^{t-1} f(X_s)-\sum_{i\in V}π_i f(i)\right| = O\left(\frac{\sqrt{\log t}}{t}\right) \qquad\text{almost surely}. \] These results show that, in contrast with the usual $t^{-1/2}$ error scaling for empirical averages under standard random-walk-based methods, TSAW-based estimator yields empirical integral errors of order $O(\sqrt{\log t}/t)$ almost surely, thereby achieving a substantially sharper dependence on the sample size $t$.

Qinghua, Ding, Venkat Anantharam

Reinforced random walks are random walks on graphs whose transition probabilities along edges from a vertex are proportional to the weights of those edges, but where the weight of an edge evolves in a way that depends on the past traversals across it. In an edge-reinforced random walk (ERRW), the weight of an edge increases by $1$ whenever that edge is traversed, in either direction. On a finite graph, an ERRW admits a remarkable representation as a random walk in a random environment. The law of the environment is given by the so-called {\em magic formula}, with this law depending on the initial edge weights. This representation provides a natural route for studying statistical properties of ERRWs. This work focuses on various information-theoretic quantities associated with ERRWs on finite graphs, motivated in part by the problem of statistically distinguishing between different ERRW models from observed trajectories. In particular, we study the entropy rate of an ERRW. We also study the Kullback--Leibler divergence (KL divergence) between two ERRW environment laws, and the KL divergence between the corresponding finite-trajectory distributions. Leveraging structural properties of the underlying random environment, we derive an annealed representation of the entropy rate, a closed-form formula for the environment-level KL divergence, and quantitative bounds on the convergence of trajectory-level KL divergence toward environment-level KL divergence. These information-theoretic quantities are motivated by the two-point hypothesis testing problem for ERRW trajectories, and in particular by the associated Stein exponent. We also expect them to play a fundamental role in the study of other testing problems for ERRWs, including identity testing and closeness testing.

Tianqi, Ding, Dawei Xiang et al.

The rapid growth of industrial automation has highlighted the need for precise and efficient defect detection in large-scale machinery. Traditional inspection techniques, involving manual procedures such as scaling tall structures for visual evaluation, are labor-intensive, subjective, and often hazardous. To overcome these challenges, this paper introduces an automated defect detection framework built on Neural Radiance Fields (NeRF) and the concept of digital twins. The system utilizes UAVs to capture images and reconstruct 3D models of machinery, producing both a standard reference model and a current-state model for comparison. Alignment of the models is achieved through the Iterative Closest Point (ICP) algorithm, enabling precise point cloud analysis to detect deviations that signify potential defects. By eliminating manual inspection, this method improves accuracy, enhances operational safety, and offers a scalable solution for defect detection. The proposed approach demonstrates great promise for reliable and efficient industrial applications.

Qinghua, Ding, Venkat Anantharam

Reinforced random walks (RRWs), including vertex-reinforced random walks (VRRWs) and edge-reinforced random walks (ERRWs), model random walks where the transition probabilities evolve based on prior visitation history~\cite{mgr, fmk, tarres, volkov}. These models have found applications in various areas, such as network representation learning~\cite{xzzs}, reinforced PageRank~\cite{gly}, and modeling animal behaviors~\cite{smouse}, among others. However, statistical estimation of the parameters governing RRWs remains underexplored. This work focuses on estimating the initial edge weights of ERRWs using observed trajectory data. Leveraging the connections between an ERRW and a random walk in a random environment (RWRE)~\cite{mr, mr2}, as given by the so-called "magic formula", we propose an estimator based on the generalized method of moments. To analyze the sample complexity of our estimator, we exploit the hyperbolic Gaussian structure embedded in the random environment to bound the fluctuations of the underlying random edge conductances.

Priyanka Nigam, Yiwei Song, Vijai Mohan et al.

We study the problem of semantic matching in product search, that is, given a customer query, retrieve all semantically related products from the catalog. Pure lexical matching via an inverted index falls short in this respect due to several factors: a) lack of understanding of hypernyms, synonyms, and antonyms, b) fragility to morphological variants (e.g. "woman" vs. "women"), and c) sensitivity to spelling errors. To address these issues, we train a deep learning model for semantic matching using customer behavior data. Much of the recent work on large-scale semantic search using deep learning focuses on ranking for web search. In contrast, semantic matching for product search presents several novel challenges, which we elucidate in this paper. We address these challenges by a) developing a new loss function that has an inbuilt threshold to differentiate between random negative examples, impressed but not purchased examples, and positive examples (purchased items), b) using average pooling in conjunction with n-grams to capture short-range linguistic patterns, c) using hashing to handle out of vocabulary tokens, and d) using a model parallel training architecture to scale across 8 GPUs. We present compelling offline results that demonstrate at least 4.7% improvement in Recall@100 and 14.5% improvement in mean average precision (MAP) over baseline state-of-the-art semantic search methods using the same tokenization method. Moreover, we present results and discuss learnings from online A/B tests which demonstrate the efficacy of our method.

Julian Ryde, Xuchu, Ding

We introduce an approach for the real-time (2Hz) creation of a dense map and alignment of a moving robotic agent within that map by rendering using a Graphics Processing Unit (GPU). This is done by recasting the scan alignment part of the dense mapping process as a rendering task. Alignment errors are computed from rendering the scene, comparing with range data from the sensors, and minimized by an optimizer. The proposed approach takes advantage of the advances in rendering techniques for computer graphics and GPU hardware to accelerate the algorithm. Moreover, it allows one to exploit information not used in classic dense mapping algorithms such as Iterative Closest Point (ICP) by rendering interfaces between the free space, occupied space and the unknown. The proposed approach leverages directly the rendering capabilities of the GPU, in contrast to other GPU-based approaches that deploy the GPU as a general purpose parallel computation platform. We argue that the proposed concept is a general consequence of treating perception problems as inverse problems of rendering. Many perception problems can be recast into a form where much of the computation is replaced by render operations. This is not only efficient since rendering is fast, but also simpler to implement and will naturally benefit from future advancements in GPU speed and rendering techniques. Furthermore, this general concept can go beyond addressing perception problems and can be used for other problem domains such as path planning.