5 papers
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Tianhao Wu, Matthew Zurek, Weina Wang +1
We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs) under a generative model. Naive reduction…
Wasserstein-p Central Limit Theorem Rates: From Local Dependence to Markov Chains
Yixuan Zhang, Qiaomin Xie
Non-asymptotic central limit theorem (CLT) rates play a central role in modern machine learning and operations research. In this paper, we study CLT rates for multivariate dependen…
Contextual Online Pricing with (Biased) Offline Data
Yixuan Zhang, Ruihao Zhu, Qiaomin Xie
We study contextual online pricing with biased offline data. For the scalar price elasticity case, we identify the instance-dependent quantity that measures how far the offli…
A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression
Yixuan Zhang, Dongyan Huo, Yudong Chen +1
Motivated by robust and quantile regression problems, we investigate the stochastic gradient descent (SGD) algorithm for minimizing an objective function that is locally strong…
Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way
Jeongyeol Kwon, Luke Dotson, Yudong Chen +1
Previous studies on two-timescale stochastic approximation (SA) mainly focused on bounding mean-squared errors under diminishing stepsize schemes. In this work, we investigate {\it…