
- Sponsor
- Coordinated Science Lab
- Speaker
- Prof. Serder Yuksel, Queen's University
- Contact
- Prashant Mehta
- mehtapg@illinois.edu
- Originating Calendar
- CSL Decision and Control Group
Title: Transformers via Stochastic Control: Optimal Training, Generalization, and Near-Lossless Token Prediction for non-Markovian Data
Abstract: We present a stochastic control theoretic approach to transformer training, compatible with structural constraints such as realized-input-independence during execution and the ensemble control nature of the problem. We model the transformer architecture as a discrete-time controlled interacting particle system with shared actions, exhibiting McKean-Vlasov dynamics. We show that closed-loop policies in a suitably lifted model is equivalent to an initial-distribution dependent open-loop policy, which are realized-input-dependent; establish regularity properties, and then the existence of globally optimal policies and continuity of value functions. To train a transformer with dynamic programming, we obtain a finite approximate model for the lifted MDP by quantizing the state, probability measure, and action spaces, and show that an optimal policy for the finite MDP model is near-optimal for the original training problem. This approach provides a globally near-optimal and robust alternative to gradient-based training.
We then derive robustness (to distribution perturbations) properties, and obtain generalization and sample complexity bounds on transformer training, using concentration inequalities for empirical laws together with Lipschitz regularity of the value function. We also show that the same approach applies to a distributionally robust control formulation for the training problem.
Finally, we study an application: next-token (measure valued) prediction via transformers for sources that need not be Markovian. We consider non-Markovian sources which are either stationary and ergodic or those which are hidden Markov. In either case, we first obtain error bounds via finite models with finite window approximation. For stationary ergodic sources, the resulting error is bounded by an entropy gap via an information theoretic analysis; for $N$th order Markovian sources, it decays at an exponential rate determined by filter stability. We then construct an optimally trained transformer, with the construction noted above, of depth $M+1$, one head per layer, near optimally realizing a truncated predictor and show that the error between the true next token predictor (with infinite history for real data) and that under the trained transformer is determined by memory length, quantization errors, and sample complexity, and in particular can be made near lossless for the classes of non-Markovian sources considered. Numerical studies are also presented.
[Joint work with Kağan Akman, Jake F. Starosta and Naci Saldi]
Bio:
Academic Experience:
2020 - Professor, Mathematics and Statistics, Queen's University
2016 - Adjunct Professor, Department of Electrical and Electronics Engineering, Bilkent University
2013 - 2020 Associate Professor, Mathematics and Statistics, Queen's University
2007 - 2013 Assistant Professor, Mathematics and Statistics, Queen's University
Sept. 2006 - Aug. 2007 Post-Doctoral Researcher, Yale University, New Haven, CT (Advisor: Prof. Sekhar Tatikonda)Visiting Associate Professor, University of Passau, May 2016 (intensive course on 'Control of Stochastic Systems')
Visiting Associate Professor, Bilkent University, January 2014-Summer 2014 (on sabbatical leave).
Visiting Assistant Professor, KTH-Sweden, May 2012 (intensive summer course on 'Stochastic Networked Control Systems').Education:
2003 - 2006 PhD in Electrical and Computer Engineering (at Coordinated Science Laboratory)
University of Illinois at Urbana Champaign (Advisor: Prof. Tamer Basar)
2001 - 2003 MS in Electrical and Computer Engineering (at Coordinated Science Laboratory)
University of Illinois at Urbana-Champaign (Advisor: Prof. Tamer Basar)
1997 - 2001 BS in Electrical Engineering, Bilkent University, Ankara
Summer 2004 Research Internship at Xerox PARC, 2004 (hosts. Dr. Haitham Hindi and Dr. Lara Crawford)Awards/Honors:
2013 CAIMS/PIMS Early Career Award in Applied Mathematics (lecture / citation)
2013 IEEE Transactions on Automatic Control Outstanding Reviewer
2018 NSERC Discovery Accelerator Supplement Award
2021 University of Illinois CSL Visitors Scholar, Visitors Scholar Lecture
Some Paper Recognitions:
2018 IEEE Conference on Decision and Control Outstanding Student Paper Award (for paper with Ali D. Kara).
2022 Automatica Editors' Choice: Robustness to incorrect models and data-driven learning in average-cost optimal stochastic control (with A.D. Kara, M. Raginsky), vol. 139, May 2022.
2023 CSS Networks and Communication Systems TC Outstanding Student Paper Prize (for paper with B. Yongacoglu and G. Arslan)
2024 TMLR Featured Certification (for paper with Ali D. Kara)
