October 2019 - talks - lists.cs.princeton.edu

Colloquium Speaker: Tushar Krishna, Thursday 11/7 at 12:30pm
by Emily C. Lawrence 31 Oct '19

31 Oct '19

CS Colloquium Speaker Tushar Krishna from Georgia Tech Thursday, November 7 - 12:30pm E-Quad, B205 Host: Margaret Martonosi [ https://www.cs.princeton.edu/events/25888 | https://www.cs.princeton.edu/events/25888 ] Enabling Continuous Learning through Synaptic Plasticity in Hardware Ever since modern computers were invented, the dream of creating artificial intelligence (AI) has captivated humanity. We are fortunate to live in an era when, thanks to deep learning (DL), computer programs have paralleled, and in many cases even surpassed human level accuracy in tasks like visual perception and speech synthesis. However, we are still far away from realizing general-purpose AI. The problem lies in the fact that the development of supervised learning based DL solutions today is mostly open loop. A typical DL model is created by hand-tuning the deep neural network (DNN) topology by a team of experts over multiple iterations, followed by training over petabytes of labeled data. Once trained, the DNN provides high accuracy for the task at hand; if the task changes, however, the DNN model needs to be re-designed and re-trained before it can be deployed. A general-purpose AI system, in contrast, needs to have the ability to constantly interact with the environment and learn by adding and removing connections within the DNN autonomously, just like our brain does. This is known as synaptic plasticity. In this talk we will present our research efforts towards enabling general-purpose AI leveraging plasticity in both the algorithm and hardware. First, we will present GeneSys (MICRO 2018), a HW-SW prototype of a closed loop learning system for continuously evolving the structure and weights of a DNN for the task at hand using genetic algorithms, providing 100-10000x higher performance and energy-efficiency over state-of-the-art embedded and desktop CPU and GPU systems. Next, we will present a DNN accelerator substrate called MAERI (ASPLOS 2018), built using light-weight, non-blocking, reconfigurable interconnects, that supports efficient mapping of regular and irregular DNNs with arbitrary dataflows , providing ~100% utilization of all compute units, resulting in 3X speedup and energy-efficiency over our prior work Eyeriss (ISSCC 2016). Finally, time permitting, we will describe our research in enabling rapid design-space exploration and prototyping of hardware accelerators using our dataflow DSL + cost-model called MAESTRO (MICRO 2019). Bio: Tushar Krishna is an Assistant Professor in the School of Electrical and Computer Engineering at Georgia Tech. He also holds the ON Semiconductor Junior Professorship. He has a Ph.D. in Electrical Engineering and Computer Science from MIT (2014), a M.S.E in Electrical Engineering from Princeton University (2009), and a B.Tech in Electrical Engineering from the Indian Institute of Technology (IIT) Delhi (2007). Before joining Georgia Tech in 2015, Dr. Krishna spent a year as a post-doctoral researcher at Intel, Massachusetts. Dr. Krishna’s research spans computer architecture, interconnection networks, networks-on-chip ( NoC ) and deep learning accelerators - with a focus on optimizing data movement in modern computing systems. Three of his papers have been selected for IEEE Micro’s Top Picks from Computer Architecture, one more received an honorable mention, and two have won best paper awards. He received the National Science Foundation (NSF) CRII award in 2018, and both a Google Faculty Award and a Facebook Faculty Award in 2019. He also received the “Class of 1940 Course Survey Teaching Effectiveness” Award from Georgia Tech in 2018.

1 0

Jordan Fix will present his FPO "Hardware MultiThreaded Transactions: Enabling Speculative MuliThreaded Pipeline Parallelization For Complex Programs" on Tuesday, 11/12/2019 at 10am in CS 402
by Nicki Mahler 28 Oct '19

28 Oct '19

Jordan Fix will present his FPO "Hardware MultiThreaded Transactions: Enabling Speculative MuliThreaded Pipeline Parallelization For Complex Programs" on Tuesday, 11/12/2019 at 10am in CS 402. The members of his committee are: David August (adviser); Readers: David August and David Callahan (Reservoir Labs); Examiners: Margaret Martonosi, David Wentzlaff (ELE), and Andrew Appel. A copy of his thesis is available upon request. Please email ngotsis(a)cs.princeton if you would like a copy of the thesis. Everyone is invited to attend his talk. The talk abstract follows below: Speculation with transactional memory systems helps programmers and compilers produce profitable thread-level parallel programs. Prior work shows that supporting transactions that can span multiple threads, rather than requiring transactions be contained within a single thread, enables new types of speculative parallelization techniques for both programmers and parallelizing compilers. Unfortunately, software support for multi-threaded transactions (MTXs) comes with significant additional inter-thread communication overhead for speculation validation. This overhead can make otherwise good parallelization unprofitable for programs with sizeable read and write sets. Some programs using these prior software MTXs overcame this problem through significant efforts by expert programmers to minimize these sets and optimize communication, capabilities which compiler technology has been unable to achieve to date. Instead, this dissertation makes speculative parallelization less laborious and more feasible through low-overhead speculation validation, presenting the first complete design, implementation, and evaluation of hardware MTXs. Even with maximal speculation validation of every load and store inside transactions of tens to hundreds of millions of instructions, profitable parallelization of complex programs can be achieved. Across 8 benchmarks, this system achieves a geomean speedup of 104% over sequential execution on a multicore machine with 4 cores, with modest increases in power and energy consumption. This work could be used as a building block to enable more realistic automatic parallelization of complex programs, by providing low-overhead, long-running, resilient transactions that support a diverse set of parallel paradigm options.

1 0

Nayana Prasad Nagendra will present her Pre FPO "A Frontend For All Workloads" on Monday, November 4, 2019 at 11:30am in CS 302
by Nicki Mahler 28 Oct '19

28 Oct '19

Nayana Prasad Nagendra will present her Pre FPO "A Frontend For All Workloads" on Monday, November 4, 2019 at 11:30am in CS 302. The members of her committee are as follows: David August (adviser), Tipp Moseley (Google), David Wentzlaff (ELE), and Sharad Malik (ELE). Everyone is invited to attend her talk. The abstract follows below. Warehouse-Scale Computing applications experience an order of magnitude more front-end stalls than desktop applications because their code footprints are well beyond the capacity of today’s processor structures, including instruction caches and branch target buffers. Current approaches to reducing front-end stalls rely, at least in part, on some subset of processor structures having sufficient capacity. Since working set sizes for important applications will continue to grow faster than processor structures (27% Year-over-Year growth in web-search instruction working set size for example vs. 7% for L1 instruction cache), these approaches are not viable. Instead, we propose Predicted Path Prefetching with Confidence Hedging, a front-end architecture that does not rely on the capacity to prevent front-end stalls by also prefetching the path not predicted when confidence in the path prediction is low. Initial results show many fewer instruction cache misses per kilo instructions with similar prefetch costs compared to existing techniques.

1 0

Colloquium Speaker Sham Kakade TODAY at 12:30pm
by Emily C. Lawrence 24 Oct '19

24 Oct '19

CS Colloquium Speaker Sham Kakade from University of Washington Thursday, October 24 - 12:30pm Friend Center Convocation Room Host: Sanjeev Arora [ https://www.cs.princeton.edu/events/25891 | https://www.cs.princeton.edu/events/25891 ] Representation, Modeling, and Optimization in Reinforcement Learning Reinforcement learning is now the dominant paradigm for how an agent learns to interact with the world. The approach has led to successes ranging across numerous domains, including game playing and robotics, and it holds much promise in new domains, from self-driving cars to interactive medical applications. Some of the central challenges are: -Representational learning: does having a good representation of the environment permit efficient reinforcement learning? -Modeling: should we explicitly build a model of our environment or, alternatively, should we directly learn how to act? -Optimization: in practice, deployed algorithms often use local search heuristics. Can we provably understand when these approaches are effective and provide faster and more robust alternatives? This talk will survey a number of results on these basic questions. Throughout, we will highlight the interplay of theory, algorithm design, and practice. Bio: Sham Kakade is a Washington Research Foundation Data Science Chair, with a joint appointment in the Department of Computer Science and the Department of Statistics at the University of Washington, and is a co-director for the Algorithmic Foundations of Data Science Institute. He works on the mathematical foundations of machine learning and AI. Sham's thesis helped in laying the foundations of the PAC-MDP framework for reinforcement learning. With his collaborators, his additional contributions include: one of the first provably efficient policy search methods, Conservative Policy Iteration, for reinforcement learning; developing the mathematical foundations for the widely used linear bandit models and the Gaussian process bandit models; the tensor and spectral methodologies for provable estimation of latent variable models (applicable to mixture of Gaussians, HMMs, and LDA); the first sharp analysis of the perturbed gradient descent algorithm, along with the design and analysis of numerous other convex and non-convex algorithms. He is the recipient of the IBM Goldberg best paper award (in 2007) for contributions to fast nearest neighbor search and the best paper, INFORMS Revenue Management and Pricing Section Prize (2014). He has been program chair for COLT 2011. Sham was an undergraduate at Caltech, where he studied physics and worked under the guidance of John Preskill in quantum computing. He then completed his Ph.D. in computational neuroscience at the Gatsby Unit at University College London, under the supervision of Peter Dayan. He was a postdoc at the Dept. of Computer Science, University of Pennsylvania , where he broadened his studies to include computational game theory and economics from the guidance of Michael Kearns. Sham has been a Principal Research Scientist at Microsoft Research, New England, an associate professor at the Department of Statistics, Wharton, UPenn , and an assistant professor at the Toyota Technological Institute at Chicago.

1 0

Reminder: Colloquium Speaker Sham Kakade tomorrow at 12:30pm
by Emily C. Lawrence 23 Oct '19

23 Oct '19

CS Colloquium Speaker Sham Kakade from University of Washington Thursday, October 24 - 12:30pm Friend Center Convocation Room Host: Sanjeev Arora [ https://www.cs.princeton.edu/events/25891 | https://www.cs.princeton.edu/events/25891 ] Representation, Modeling, and Optimization in Reinforcement Learning Reinforcement learning is now the dominant paradigm for how an agent learns to interact with the world. The approach has led to successes ranging across numerous domains, including game playing and robotics, and it holds much promise in new domains, from self-driving cars to interactive medical applications. Some of the central challenges are: -Representational learning: does having a good representation of the environment permit efficient reinforcement learning? -Modeling: should we explicitly build a model of our environment or, alternatively, should we directly learn how to act? -Optimization: in practice, deployed algorithms often use local search heuristics. Can we provably understand when these approaches are effective and provide faster and more robust alternatives? This talk will survey a number of results on these basic questions. Throughout, we will highlight the interplay of theory, algorithm design, and practice. Bio: Sham Kakade is a Washington Research Foundation Data Science Chair, with a joint appointment in the Department of Computer Science and the Department of Statistics at the University of Washington, and is a co-director for the Algorithmic Foundations of Data Science Institute. He works on the mathematical foundations of machine learning and AI. Sham's thesis helped in laying the foundations of the PAC-MDP framework for reinforcement learning. With his collaborators, his additional contributions include: one of the first provably efficient policy search methods, Conservative Policy Iteration, for reinforcement learning; developing the mathematical foundations for the widely used linear bandit models and the Gaussian process bandit models; the tensor and spectral methodologies for provable estimation of latent variable models (applicable to mixture of Gaussians, HMMs, and LDA); the first sharp analysis of the perturbed gradient descent algorithm, along with the design and analysis of numerous other convex and non-convex algorithms. He is the recipient of the IBM Goldberg best paper award (in 2007) for contributions to fast nearest neighbor search and the best paper, INFORMS Revenue Management and Pricing Section Prize (2014). He has been program chair for COLT 2011. Sham was an undergraduate at Caltech, where he studied physics and worked under the guidance of John Preskill in quantum computing. He then completed his Ph.D. in computational neuroscience at the Gatsby Unit at University College London, under the supervision of Peter Dayan. He was a postdoc at the Dept. of Computer Science, University of Pennsylvania , where he broadened his studies to include computational game theory and economics from the guidance of Michael Kearns. Sham has been a Principal Research Scientist at Microsoft Research, New England, an associate professor at the Department of Statistics, Wharton, UPenn , and an assistant professor at the Toyota Technological Institute at Chicago.

1 0

Dingli Yu will present his General Exam on Thursday, October 24, 2019 at 9:30am in CS 401.
by Nicki Mahler 22 Oct '19

22 Oct '19

Dingli Yu will present his General Exam on Thursday, October 24, 2019 at 9:30am in CS 401. The members of his committee are as follows: Sanjeev Arora (adviser), Jason D. Lee (ELE), and Jia Deng. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Title: Harnessing the Power of Infinitely Wide Deep Nets Abstract: Recent research shows that the following two models are equivalent: (a) infinitely wide neural networks (NNs) trained under l2 loss by gradient descent with infinitesimally small learning rate (b) kernel regression with respect to so-called Neural Tangent Kernels (NTKs) (Jacot et al., 2018). An efficient algorithm to compute the NTK, as well as its convolutional counterparts (CNTK), appears in Arora et al. (2019a), yielded the finding that classification accuracy of CNTK on CIFAR-10 is within 6-7% of that of the corresponding CNN architecture (best figure being around 78%). Here, we show that NTK and CNTK or their enhanced version perform strongly in the following tasks. 1. On a standard testbed of classification/regression tasks from the UCI database, NTK SVM beats the previous gold standard, Random Forests (RF), and also the corresponding finite nets. 2. On VOC07 testbed for few-shot image classification tasks on ImageNet with transfer learning (Goyal et al., 2019), replacing the linear SVM currently used with a Convolutional NTK SVM consistently improves performance. 3. On CIFAR-10 with 10 – 640 training samples, CNTK consistently beats ResNet-34 by 1% - 3%. On the whole CIFAR-10 dataset, CNTK achieves 89% accuracy, matching the performance of AlexNet (Krizhevsky et al., 2012) by incorporating horizontal flip data augmentation, a pre-processing technique proposed by Coates et al. (2011) and a new operation called Local Average Pooling (LAP) which preserves efficient computability of the kernel and inherits the spirit of standard data augmentation using pixel shifts. Reading list: 1. Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2018 2. Peter L Bartlett, and Shahar Mendelson, Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463–482, 2002. 3. Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint arXiv:1904.11955, 2019. 4. Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584, 2019b. 5. Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019. 6. Simon S Du, Jason D Lee, Haochuan Li, LiweiWang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv:1811.03804, 2018. 7. Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? arXiv preprint arXiv:1902.10811, 2019. 8. Matthew Olson, Abraham Wyner, and Richard Berk. Modern neural networks generalize on small data sets. In Advances in Neural Information Processing Systems, pp. 3619-3628, 2018. 9. Manuel Fernandez-Delgado, Eva Cernadas, Senen Barro, and Dinani Amorim. Do we need hundreds of classifiers to solve real world classification problems? The Journal of Machine Learning Research, 15(1):3133-3181, 2014. 10. Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks.In Advances in neural information processing systems, pages 2627–2635, 2014. 11. Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 215–223, 2011. 12. Shuxiao Chen, Edgar Dobriban, and Jane H Lee. Invariance reduces variance: Understanding data augmentation in deep learning and beyond. arXiv preprint arXiv:1907.10905, 2019.

1 0

Nikunj Saunshi will present his General Exam on Wednesday, October 23, 2019 at 9:15am in CS 402
by Nicki Mahler 21 Oct '19

21 Oct '19

Nikunj Saunshi will present his General Exam on Wednesday, October 23, 2019 at 9:15am in CS 402. The members of his committee are Sanjeev Arora (adviser), Elad Hazan, and Karthik Narasimhan. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Title: A theoretical framework to analyze contrastive learning methods for representation learning Abstract: Contrastive learning, reminiscent of word2vec, is a family of methods that use unlabeled data to learn data representations, — e.g., sentence embeddings — that are useful for downstream classification tasks. Training leverages access to semantically similar pairs of data points and encourages high inner product for representations of similar pairs and low inner product for random pairs of data points. We provide a theoretical framework for understanding such methods by positing that similar pairs come from the same latent class. Using a within-class independent sampling assumption, we show that small unsupervised loss in contrastive learning guarantees good performance on linear classification tasks involving these latent classes. This novel connection between the unlabeled data distribution and downstream tasks also helps us show (labeled) sample complexity benefits of such representation learning methods. We then extend this framework by leveraging a graph-theoretic view of the unlabeled data distribution that motivates a more relaxed and realistic data model for similar pairs: cross subclass independence (CSI). Under this new assumption, we show similar guarantees for downstream classification performance by employing a duality-based analysis. Using the graph formulation, we also highlight the need for incorporating assumptions about inductive biases of the representation function class in order to show guarantees under even weaker assumptions Reading list ========================================= 1. Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014. 2. Logeswaran, L. and Lee, H. An efficient framework for learning sentence representations. In Proceedings of the International Conference on Learning Representations, 2018 3. Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. Distributed representations of words and phrases and their compositionality. In Neural Information Processing Systems, 2013. 4. Arora, S., Li, Y., Liang, Y., Ma, T. and Andrej Risteski. A latent variable model approach to PMI-based word embeddings. Transaction of Association for Computational Linguistics, 2016. 5. Gutmann, M. and Hyvarinen, A. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 297–304, 2010. 6. Ma, Z. and Collins, M. Noise contrastive estimation and negative sampling for conditional models: Consistency and statistical efficiency. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing 7. Maurer, A., Pontil, M., and Romera-Paredes, B. The benefit of multitask representation learning. J. Mach. Learn. Res., 2016. 8. Syed, U. and Schapire, R. A reduction from apprenticeship learning to classification. In Advances in Neural Information Processing Systems 2010. 9. Ross, S., Gordon, G. and Bagnell, D. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics 2011. 10. Sun, W., Vemula, A., Boots, B. and Bagnell, D.. Provably Efficient Imitation Learning from Observation Alone. Proceedings of the 36th International Conference on Machine Learning, 2019. ==========================================

1 0

Colloquium Speaker Andrés Monroy-Hernández, TODAY at 12:30pm
by Emily C. Lawrence 21 Oct '19

21 Oct '19

CS Colloquium Speaker Andrés Monroy-Hernández from Snap Inc. Monday, October 21 - 12:30pm Computer Science - Room 105 Host: Adam Finkelstein [ https://www.cs.princeton.edu/events/25890 | https://www.cs.princeton.edu/events/25890 ] Designing and deploying social computing systems inside and outside the lab Social computing has permeated most aspects of our lives, from work to play. In recent years, however, social platforms have faced challenges ranging from labor concerns about crowd work to misinformation on social media. These and other challenges, along with the emergence of new technical platforms, create opportunities to re-imagine the future of the field. In this talk, I will discuss my research designing and deploying social computing systems to help people connect and collaborate to learn new skills, crowdsource news reporting, and delegate tasks to hybrid AI systems. First, I describe an online community I created to connect millions of young creators to learn computational thinking skills as they create, share, and remix games and animations on the web. Then I shift to how this work inspired my next set of systems to connect urban residents as they share news about their local communities. Finally, I will discuss a novel workplace productivity tool we created to enable information workers to delegate tasks to hybrid intelligence systems powered by humans and AI. I close by articulating the challenges and opportunities ahead for the field, and the ways my team is beginning to explore new systems that support more authentic and intimate connections, building on new technologies including wearables sensors and AR. Bio: Andrés Monroy-Hernández is a lead research scientist at Snap Inc , where he manages the human-computing interaction research team. He is also an affiliate professor at the University of Washington. His work focuses on the design and study of social computing technologies that help people connect and collaborate. Previously, he was at Microsoft Research for six years, where he led the research and development of Calendar.help , Microsoft’s first hybrid AI product. His research has received best paper awards at CHI, CSCW, HCOMP, and ICWSM, and has been featured in The New York Times, CNN, Wired, BBC, and The Economist. Andrés was named one of the 35 Innovators under 35 by the MIT Technology Review magazine in Latin America, and one the most influential Latinos in Tech by CNET. Andrés holds master’s and Ph.D. from MIT, where he led the creation of the Scratch online community. He has a BS from Tec de Monterrey in México. More info at [ http://andresmh.com/ | http://andresmh.com ]

1 0

Reminder: Colloquium Speaker Andrés Monroy-Hernández, tomorrow at 12:30pm
by Emily C. Lawrence 20 Oct '19

20 Oct '19

CS Colloquium Speaker Andrés Monroy-Hernández from Snap Inc. Monday, October 21 - 12:30pm Computer Science - Room 105 Host: Adam Finkelstein [ https://www.cs.princeton.edu/events/25890 | https://www.cs.princeton.edu/events/25890 ] Designing and deploying social computing systems inside and outside the lab Social computing has permeated most aspects of our lives, from work to play. In recent years, however, social platforms have faced challenges ranging from labor concerns about crowd work to misinformation on social media. These and other challenges, along with the emergence of new technical platforms, create opportunities to re-imagine the future of the field. In this talk, I will discuss my research designing and deploying social computing systems to help people connect and collaborate to learn new skills, crowdsource news reporting, and delegate tasks to hybrid AI systems. First, I describe an online community I created to connect millions of young creators to learn computational thinking skills as they create, share, and remix games and animations on the web. Then I shift to how this work inspired my next set of systems to connect urban residents as they share news about their local communities. Finally, I will discuss a novel workplace productivity tool we created to enable information workers to delegate tasks to hybrid intelligence systems powered by humans and AI. I close by articulating the challenges and opportunities ahead for the field, and the ways my team is beginning to explore new systems that support more authentic and intimate connections, building on new technologies including wearables sensors and AR. Bio: Andrés Monroy-Hernández is a lead research scientist at Snap Inc , where he manages the human-computing interaction research team. He is also an affiliate professor at the University of Washington. His work focuses on the design and study of social computing technologies that help people connect and collaborate. Previously, he was at Microsoft Research for six years, where he led the research and development of Calendar.help , Microsoft’s first hybrid AI product. His research has received best paper awards at CHI, CSCW, HCOMP, and ICWSM, and has been featured in The New York Times, CNN, Wired, BBC, and The Economist. Andrés was named one of the 35 Innovators under 35 by the MIT Technology Review magazine in Latin America, and one the most influential Latinos in Tech by CNET. Andrés holds master’s and Ph.D. from MIT, where he led the creation of the Scratch online community. He has a BS from Tec de Monterrey in México. More info at [ http://andresmh.com/ | http://andresmh.com ]

1 0

Colloquium Speaker Sham Kakade Thursday, October 24 at 12:30pm
by Emily C. Lawrence 18 Oct '19

18 Oct '19

CS Colloquium Speaker Sham Kakade from University of Washington Thursday, October 24 - 12:30pm Friend Center Convocation Room Host: Sanjeev Arora [ https://www.cs.princeton.edu/events/25891 | https://www.cs.princeton.edu/events/25891 ] Representation, Modeling, and Optimization in Reinforcement Learning Reinforcement learning is now the dominant paradigm for how an agent learns to interact with the world. The approach has led to successes ranging across numerous domains, including game playing and robotics, and it holds much promise in new domains, from self-driving cars to interactive medical applications. Some of the central challenges are: -Representational learning: does having a good representation of the environment permit efficient reinforcement learning? -Modeling: should we explicitly build a model of our environment or, alternatively, should we directly learn how to act? -Optimization: in practice, deployed algorithms often use local search heuristics. Can we provably understand when these approaches are effective and provide faster and more robust alternatives? This talk will survey a number of results on these basic questions. Throughout, we will highlight the interplay of theory, algorithm design, and practice. Bio: Sham Kakade is a Washington Research Foundation Data Science Chair, with a joint appointment in the Department of Computer Science and the Department of Statistics at the University of Washington, and is a co-director for the Algorithmic Foundations of Data Science Institute. He works on the mathematical foundations of machine learning and AI. Sham's thesis helped in laying the foundations of the PAC-MDP framework for reinforcement learning. With his collaborators, his additional contributions include: one of the first provably efficient policy search methods, Conservative Policy Iteration, for reinforcement learning; developing the mathematical foundations for the widely used linear bandit models and the Gaussian process bandit models; the tensor and spectral methodologies for provable estimation of latent variable models (applicable to mixture of Gaussians, HMMs, and LDA); the first sharp analysis of the perturbed gradient descent algorithm, along with the design and analysis of numerous other convex and non-convex algorithms. He is the recipient of the IBM Goldberg best paper award (in 2007) for contributions to fast nearest neighbor search and the best paper, INFORMS Revenue Management and Pricing Section Prize (2014). He has been program chair for COLT 2011. Sham was an undergraduate at Caltech, where he studied physics and worked under the guidance of John Preskill in quantum computing. He then completed his Ph.D. in computational neuroscience at the Gatsby Unit at University College London, under the supervision of Peter Dayan. He was a postdoc at the Dept. of Computer Science, University of Pennsylvania , where he broadened his studies to include computational game theory and economics from the guidance of Michael Kearns. Sham has been a Principal Research Scientist at Microsoft Research, New England, an associate professor at the Department of Statistics, Wharton, UPenn , and an assistant professor at the Toyota Technological Institute at Chicago.

1 0