19 papers
A Heavy Traffic Theory of Matching Queues
Sushil Mahavir Varma, Siva Theja Maguluri
Motivated by emerging applications in online matching platforms and marketplaces, we study a matching queue. Customers and servers that arrive in a matching queue depart as soon as…
Transform Method for Stochastic Processing and Matching Networks
Sushil Mahavir Varma, Prakirt Jhunjhunwala, Daniela Hurtado-Lange +1
Modern service systems, ranging from cloud data centers and ride-hailing platforms to healthcare facilities, operate at massive scales where it is important to handle congestion. Q…
How Accurately Can a Gaussian Approximate Stochastic Approximation Iterates?
Shaan Ul Haque, Zedong Wang, Zixuan Zhang +1
Stochastic approximation (SA) is a method for finding the root of an operator perturbed by noise. The focus of this paper is studying the distribution of SA iterates in finite time…
Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework
Zaiwei Chen, Siva Theja Maguluri
We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point…
Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise
Shubhada Agrawal, Siva Theja Maguluri, Martin Zubeldia
We establish maximal concentration bounds for the iterates generated by stochastic approximation algorithms with general step sizes, where the noise has a finite-state Markovian co…
Tail Bounds for Queues with Abandonment: Constant, Moderate, Large Deviations, and Efficient Concentration
Zedong Wang, Siva Theja Maguluri
We study a heavily overloaded single-server queue with abandonment and derive bounds on stationary tail probabilities of the queue length. As the abandonment rate ,…