ISyE Seminar Series: Jing Dong
"Stochastic Gradient Descent with Adaptive Data"
Jing Dong
DeRosa Family Associate Professor of Business in the Decision, Risk, and Operations Division
Columbia Business School
About the Seminar:
Stochastic gradient descent (SGD) is a powerful optimization technique that is particularly useful in online learning scenarios. Its convergence analysis is relatively well understood under the assumption that the data samples are independent and identically distributed (iid). However, applying SGD to policy optimization problems in operations research involves a distinct challenge: the policy changes the environment and thereby affects the data used to update the policy. The adaptively generated data stream involves samples that are non-stationary, no longer independent from each other, and affected by previous decisions. The influence of previous decisions on the data generated introduces bias in the gradient estimate, which presents a potential source of instability for online learning not present in the iid case. In this paper, we introduce simple criteria for the adaptively generated data stream to guarantee the convergence of SGD. We show that the convergence speed of SGD with adaptive data is largely similar to the classical iid setting, as long as the mixing time of the policy-induced dynamics is factored in. Our Lyapunov-function analysis allows one to translate existing stability analysis of stochastic systems studied in operations research into convergence rates for SGD, and we demonstrate this for queueing and inventory management problems. We also showcase how our result can be applied to study the sample complexity of an actor-critic policy gradient algorithm.
This is joint work with Ethan Che and Xin Tong.
About the Speaker:
Jing Dong is the DeRosa Family Associate Professor of Business in the Decision, Risk, and Operations Division at Columbia Business School. Her research is at the interface of applied probability and service operations management, with a special focus on patient flow management in healthcare delivery systems. She received an NSF CAREER Award in 2020. She currently serves on the editorial boards of Operations Research, Mathematics of Operations Research, Management Science, Manufacturing and Service Operations Management, and Operations Research Letters. She received her Ph.D. in Operations Research from Columbia University. Before joining Columbia Business School, she was a faculty at Northwestern University.
If you wish to be added to the ISyE Graduate Seminar Series emailing list, please email Event Coordinator Emily Rice at [email protected].