More Like this

1. Finite-Sample Bounds for Adaptive Inverse Reinforcement Learning Using Passive Langevin Dynamics

   https://doi.org/10.1109/TIT.2025.3555479  

   Snow, Luke; Krishnamurthy, Vikram (June 2025, IEEE Transactions on Information Theory)

   This paper provides a finite-sample analysis of a passive stochastic gradient Langevin dynamics (PSGLD) algo- rithm. This algorithm is designed to achieve adaptive inverse reinforcement learning (IRL). Adaptive IRL aims to estimate the cost function of a forward learner performing a stochastic gradient algorithm (e.g., policy gradient reinforcement learning) by observing their estimates in real-time. The PSGLD algorithm is considered passive because it incorporates noisy gradients provided by an external stochastic gradient algorithm (forward learner), of which it has no control. The PSGLD algorithm acts as a randomized sampler to achieve adaptive IRL by reconstructing the forward learner’s cost function nonparametrically from the stationary measure of a Langevin diffusion. This paper analyzes the non-asymptotic (finite-sample) performance; we provide explicit bounds on the 2-Wasserstein distance between PSGLD algorithm sample measure and the stationary measure encoding the cost function, and provide guarantees for a kernel density estimation scheme which reconstructs the cost function from empirical samples. Our analysis uses tools from the study of Markov diffusion operators. The derived bounds have both practical and theoretical significance. They provide finite-time guarantees for an adaptive IRL mechanism, and substantially generalize the analytical framework of a line of research in passive stochastic gradient algorithms. 

   more » « less
2. Efficient Distributed Community Detection in the Stochastic Block Model

   https://doi.org/10.1109/ICDCS.2019.00048  

   Fathi, Reza; Molla, Anisur; Pandurangan, Gopal (July 2019, 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS))

   Designing effective algorithms for community detection is an important and challenging problem in large-scale graphs, studied extensively in the literature. Various solutions have been proposed, but many of them are centralized with expensive procedures (requiring full knowledge of the input graph) and have a large running time. In this paper, we present a distributed algorithm for community detection in the stochastic block model (also called planted partition model), a widely-studied and canonical random graph model for community detection and clustering. Our algorithm called CDRW(Community Detection by Random Walks) is based on random walks, and is localized and lightweight, and easy to implement. A novel feature of the algorithm is that it uses the concept of local mixing time to identify the community around a given node. We present a rigorous theoretical analysis that shows that the algorithm can accurately identify the communities in the stochastic block model and characterize the model parameters where the algorithm works. We also present experimental results that validate our theoretical analysis. We also analyze the performance of our distributed algorithm under the CONGEST distributed model as well as the k-machine model, a model for large-scale distributed computations, and show that it can be efficiently implemented. 

   more » « less
3. Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions

   Ozgul, Guneykan; Li, Xiantao; Mahdavi, Mehrdad; Wang, Chunhao (June 2024, Proceedings of the 41st International Conference on Machine Learning)

   We present quantum algorithms for sampling from possibly non-logconcave probability distributions expressed as 𝜋(𝑥)∝exp(−𝛽𝑓(𝑥)) as well as quantum algorithms for estimating the partition function for such distributions. We also incorporate a stochastic gradient oracle that implements the quantum walk operators inexactly by only using mini-batch gradients when 𝑓 can be written as a finite sum. One challenge of quantizing the resulting Markov chains is that they do not satisfy the detailed balance condition in general. Consequently, the mixing time of the algorithm cannot be expressed in terms of the spectral gap of the transition density matrix, making the quantum algorithms nontrivial to analyze. We overcame these challenges by first building a reference reversible Markov chain that converges to the target distribution, then controlling the discrepancy between our algorithm’s output and the target distribution by using the reference Markov chain as a bridge to establish the total complexity. Our quantum algorithms exhibit polynomial speedups in terms of dimension or precision dependencies when compared to best-known classical algorithms under similar assumptions. 

   more » « less
4. Improved algorithm for identifying partial saddle-points in polymer field theoretic simulations

   https://doi.org/10.1063/5.0264036  

   Chen, Kexin; Morse, David C (June 2025, The Journal of Chemical Physics)

   Field-theoretic simulations that rely on a partial saddle-point approximation have become powerful tools for studying complex polymer materials. The computational cost of such simulations depends critically upon the efficiency of the iterative algorithm used to identify a partial saddle-point field configuration during each step of a stochastic simulation. We introduce a new algorithm for this purpose that relies on a physically motivated approximation in which the linear response of the density to a small change in a pressure-like field is approximated by the response of a hypothetical homogeneous system. The computational cost of the resulting algorithm is significantly less than that of the commonly used Anderson mixing algorithm. 

   more » « less
5. Empirical Q-Value Iteration

   https://doi.org/10.1287/stsy.2019.0062  

   Kalathil, Dileep; Borkar, Vivek S.; Jain, Rahul (October 2020, Stochastic Systems)

   null (Ed.)

   We propose a new simple and natural algorithm for learning the optimal Q-value function of a discounted-cost Markov decision process (MDP) when the transition kernels are unknown. Unlike the classical learning algorithms for MDPs, such as Q-learning and actor-critic algorithms, this algorithm does not depend on a stochastic approximation-based method. We show that our algorithm, which we call the empirical Q-value iteration algorithm, converges to the optimal Q-value function. We also give a rate of convergence or a nonasymptotic sample complexity bound and show that an asynchronous (or online) version of the algorithm will also work. Preliminary experimental results suggest a faster rate of convergence to a ballpark estimate for our algorithm compared with stochastic approximation-based algorithms. 

   more » « less