Sham M. Kakade: Publications


2014

  • Least Squares Revisited: Scalable Approaches for Multi-class Prediction.
    Alekh Agarwal, Sham M. Kakade, Nikos Karampatziakis, Le Song, Gregory Valiant.
    To appear in ICML, 2014.
    ArXiv Report, arXiv:1310.1949.

  • Tensor decompositions for learning latent variable models.
    Anima Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, Matus Telgarsky.
    To appear in JMLR, 2014. ArXiv Report, arXiv:1210.7559.

  • An Analysis of Random Design Linear Regression.
    Daniel Hsu, Sham M. Kakade, Tong Zhang.
    Foundations of Computational Mathematics, 2014.
    ArXiv Report, arXiv:1106.2363.


2013

  • When are overcomplete topic models identifiable? Uniqueness of tensor Tucker decompositions with structured sparsity.
    Anima Anandkumar, Daniel Hsu, Majid Janzamin, Sham M. Kakade.
    In NIPS, 2013.
    ArXiv Report, arXiv:1308.2853, 2013.

  • A Tensor Spectral Approach to Learning Mixed Membership Community Models.
    Anima Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade.
    In COLT, 2013.
    ArXiv Report, arXiv:1302.2684, 2013.

  • A Risk Comparison of Ordinary Least Squares vs Ridge Regression.
    Paramveer Dhillon, Dean P. Foster, Sham M. Kakade, Lyle Ungar.
    In JMLR, 2013.
    ArXiv Report, arXiv:1105.0875.

  • Optimal Dynamic Mechanism Design and the Virtual Pivot Mechanism.
    Sham M. Kakade, Ilan Lobel, Hamid Nazerzadeh.
    To appear in Operations Research.
    SSRN Report, SSRN ID 1782211 .

  • Learning Linear Bayesian Networks with Latent Variables.
    Animashree Anandkumar, Daniel Hsu, Adel Javanmard, Sham M. Kakade.
    In ICML, 2013.
    ArXiv Report, arXiv:1209.5350.

  • Learning Mixtures of Spherical Gaussians: Moment Methods and Spectral Decompositions.
    Daniel Hsu, Sham M. Kakade.
    In the 4th Innovations in Theoretical Computer Science (ITCS), 2013.
    ArXiv Report, arXiv:1206.5766.

  • Stochastic convex optimization with bandit feedback.
    Alekh Agarwal, Dean P. Foster, Daniel Hsu, Sham M. Kakade, Alexander Rakhlin.
    In SIAM Journal on Optimization (SIOPT), 2013.
    In NIPS 2011. ArXiv Report, arXiv:1107.1744.


2012

  • Identifiability and Unmixing of Latent Parse Trees.
    Daniel Hsu, Sham M. Kakade, Percy Liang.
    In Neural Information Processing Systems (NIPS), 2012.
    ArXiv Report, arXiv:1206.3137, 2012.

  • A Spectral Algorithm for Latent Dirichlet Allocation.
    Animashree Anandkumar , Dean P. Foster, Daniel Hsu, Sham M. Kakade, Yi-Kai Liu.
    In Neural Information Processing Systems (NIPS), 2012.
    ArXiv Report, arXiv:1204.6703, 2012.

  • Learning High-Dimensional Mixtures of Graphical Models.
    Animashree Anandkumar, Furong Huang, Daniel Hsu, Sham M. Kakade.
    In Neural Information Processing Systems (NIPS), 2012.
    ArXiv Report, arXiv:1203.0697, 2012.

  • A tail inequality for quadratic forms of subgaussian random vectors.
    Daniel Hsu, Sham M. Kakade, Tong Zhang.
    In Electronic Communications in Probability, 2012.
    ArXiv Report, arXiv:1110.2842.

  • A Method of Moments for Mixture Models and Hidden Markov Models.
    Animashree Anandkumar, Daniel Hsu, Sham M. Kakade.
    In Conference on Learning Theory (COLT), 2012.
    ArXiv Report, arXiv:1203.0683, 2012.

  • (weak) Calibration is Computationally Hard.
    Elad Hazan, Sham M. Kakade.
    In Conference on Learning Theory (COLT), 2012.
    ArXiv Report, arXiv:1202.4478, 2012.

  • Towards minimax policies for online linear optimization with bandit feedback.
    Sebastien Bubeck, Nicolo Cesa-Bianchi, Sham M. Kakade.
    In Conference on Learning Theory (COLT), 2012.
    ArXiv Report, arXiv:1202.3079.

  • An Analysis of Random Design Linear Regression.
    Daniel Hsu, Sham M. Kakade, Tong Zhang.
    In Conference on Learning Theory (COLT), 2012.
    ArXiv Report, arXiv:1106.2363.

  • Tail inequalities for sums of random matrices that depend on the intrinsic dimension.
    Daniel Hsu, Sham M. Kakade, Tong Zhang.
    In Electronic Communications in Probability, 2012.
    ArXiv Report, arXiv:1104.1672.

    Errata:. Analysis of a randomized approximation scheme for matrix multiplication.
    ArXiv Report, arXiv:1211.5414.

  • Regularization Techniques for Learning with Matrices
    Sham M. Kakade, Shai Shalev-Shwartz, Ambuj Tewari.
    In JMLR, 2012, PDF.

  • Domain Adaptation: Overfitting and Small Sample Statistics.
    Dean P. Foster, Sham M. Kakade, Ruslan Salakhutdinov.
    In AISTAT, 2012.
    ArXiv Report, arXiv:1105.0857.


2011

  • Spectral Methods for Learning Multivariate Latent Tree Structure.
    Animashree Anandkumar, Kamalika Chaudhuri, Daniel Hsu, Sham M. Kakade, Le Song, Tong Zhang.
    In NIPS 2011. ArXiv Report, arXiv:1107.1283, 2011.

  • Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression.
    Sham M. Kakade, Adam T. Kalai, Varun Kanade, Ohad Shamir.
    In NIPS 2011. ArXiv Report, arXiv:1104.2018, 2011.

  • Robust matrix decomposition with outliers.
    Daniel Hsu, Sham M. Kakade, Tong Zhang.
    In IEEE Transactions on Information Theory, 2011.
    ArXiv Report, arXiv:1011.1518, 2011.

  • Domain Adaptation with Coupled Subspaces.
    John Blitzer, Dean Foster, and Sham Kakade.
    In AISTAT 2011. [pdf]


2010

  • Learning from Logged Implicit Exploration Data.
    Alex Strehl, John Langford, Lihong Li, Sham Kakade.
    In NIPS 2010. [pdf]

  • Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design.
    Niranjan Srinivas, Andreas Krause, Sham M. Kakade, Matthias Seeger.
    In IEEE Transactions on Information Theory.
    In ICML 2010, [pdf]. ArXiv Report, arXiv:0912.3995, 2010.

  • Learning exponential families in high-dimensions: Strong convexity and sparsity.
    Sham M. Kakade, Ohad Shamir, Karthik Sridharan, Ambuj Tewari.
    In AISTAT 2010. ArXiv Report, arXiv:0911.0054, 2009.

  • Multi-Label Prediction via Compressed Sensing.
    Daniel Hsu, Sham M. Kakade, John Langford, Tong Zhang.
    In NIPS 2010. (2009 Conference) [pdf]. [talk slides]. [arXiv].


2009

  • A Spectral Algorithm for Learning Hidden Markov Models
    Daniel Hsu, Sham M. Kakade, & Tong Zhang.
    In COLT 2009. [pdf]
    For full proofs see: ArXiv Tech Report, arXiv:0811.4413, 2008.

  • Multi-View Clustering via Canonical Correlation Analysis
    Kamalika Chaudhuri, Sham M. Kakade, Karen Livescu, & Karthik Sridharan.
    In the ICML 2009. [pdf]
    For full proofs see: TTI-C Tech Report, TTI-TR-2008-5, 2008. [pdf]

  • The Price of Truthfulness for Pay-Per-Click Auctions
    Nikhil Devanur & Sham M. Kakade.
    In the ACM Conference on Electronic Commerce 2009. [pdf]

  • On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization
    Sham M. Kakade, Karthik Sridharan, & Ambuj Tewari.
    In Proceedings of NIPS, 2009. [pdf]

  • On the Generalization Ability of Online Strongly Convex Programming Algorithms
    Sham M. Kakade & Ambuj Tewari.
    In Proceedings of NIPS, 2009. [pdf]

  • Mind the Duality Gap: Logarithmic regret algorithms for online optimization
    Sham M. Kakade & Shai Shalev-Shwartz.
    In Proceedings of NIPS, 2009. [pdf]


2008

  • An Information Theoretic Framework for Multi-view Learning
    Karthik Sridharan & Sham M. Kakade.
    In COLT 2008. [pdf]

  • Stochastic Linear Optimization under Bandit Feedback
    Varsha Dani, Thomas Hayes, & Sham M. Kakade.
    In COLT 2008. COLT version with complete proofs: [pdf]

  • High-Probability Regret Bounds for Bandit Online Linear Optimization
    Peter Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin & Ambuj Tewari.
    In COLT 2008. [pdf]

  • Efficient Bandit Algorithms for Online Multiclass Prediction
    Sham M. Kakade, Shai Shalev-Shwartz, & Ambuj Tewari.
    In the ICML 2008. [pdf]

  • Deterministic Calibration and Nash Equilibrium
    Sham M. Kakade & Dean P. Foster.
    In the J.C.S.S Learning Theory Special Issue 2008. [pdf]

  • Information Consistency of Nonparametric Gaussian Process Methods
    Matthias Seeger, Sham M. Kakade, & Dean P. Foster
    In IEEE Transactions on Information Theory, 2008. [pdf]

  • The Price of Bandit Information for Online Optimization
    Varsha Dani, Thomas Hayes, & Sham M. Kakade
    In Proceedings of NIPS, 2008. [pdf]


2007

  • Leveraging Archival Video for Building Face Datasets
    Deva Ramanan, Simon Baker & Sham M. Kakade
    In ICCV 2007. [pdf]

  • Playing Games with Approximation Algorithms
    Sham M. Kakade, Adam T. Kalai, & Katrina Ligett
    In STOC 2007. [pdf]

  • Multi-View Regression via Canonical Correlation Analysis
    Sham M. Kakade & Dean P. Foster
    In COLT 2007. [pdf]

  • Maximum Entropy Correlated Equilibria
    Luis Ortiz, Robert Schapire, & Sham M. Kakade
    In AISTAT 2007. [pdf]

  • The Value of Observation for Monitoring Dynamic Systems
    Eyal Even-Dar, Sham M. Kakade, & Yishay Mansour
    In the IJCAI 2007. [pdf]


2006

  • Cover Trees for Nearest Neighbor
    Alina Beygelzimer, Sham M. Kakade & John Langford
    In the ICML 2006. [pdf]

  • (In)Stability Properties of Limit Order Dynamics.
    E. Even-Dar, S. M. Kakade, M. Kearns, and Y. Mansour.
    In the ACM Conference on Electronic Commerce 2006. [ps] [pdf]

  • Calibration via Regression
    Sham M. Kakade & Dean P. Foster
    In the IEEE Information Theory Workshop 2006. [pdf]

  • From Batch to Transductive Online Learning
    Sham M. Kakade & Adam Kalai
    In NIPS 2006. [pdf]

  • Worst-Case Bounds for Gaussian Process Models
    Sham M. Kakade, Matthias W. Seeger, & Dean P. Foster
    In NIPS 2006. [ps] [pdf]


2005

  • Trading in Markovian Price Models
    Sham M. Kakade & Michael Kearns
    In COLT 2005.
    [ps] [pdf]

  • Planning in POMDPs Using Multiplicity Automata
    Eyal Even-Dar, Sham M. Kakade, & Yishay Mansour
    In UAI 2005.
    [ps] [pdf]

  • Reinforcement Learning in POMDPs Without Resets
    Eyal Even-Dar, Sham M. Kakade, & Yishay Mansour
    In IJCAI 2005.
    [pdf]

  • The Economic Properties of Social Networks.
    Sham M. Kakade, Michael Kearns, Luis Ortiz, Robin Pemantle, & Siddharth Suri.
    In NIPS 2005. [ps] [pdf]

  • Experts in a Markov Decision Process
    Eyal Even-Dar, Sham M. Kakade, & Yishay Mansour
    In NIPS 2005. [ps] [pdf]

  • Online Bounds for Bayesian Algorithms
    Sham M. Kakade & Andrew Y. Ng
    In NIPS 2005. [ps] [pdf]


2004

  • Deterministic Calibration and Nash Equilibrium
    Sham M. Kakade & Dean P. Foster
    In COLT 2004.
    [ps] [pdf]

  • Graphical Economics.
    Sham Kakade, Michael Kearns, & Luis Ortiz.
    In COLT 2004.
    [ps] [pdf]

  • Competitive Algorithms for VWAP and Limit Order Trading.
    Sham Kakade, Michael Kearns, Yishay Mansour, & Luis Ortiz.
    In the Proceedings of the ACM Electronic Commerce Conference 2004. [ps] [pdf]

Thesis

  • On the Sample Complexity of Reinforcement Learning.
    Sham Kakade.
    Gatsby Computational Neuroscience Unit.
    University College London, 2003.
    [abstract] [ps.gz] [pdf]


2003

  • Correlated Equilibria in Graphical Games.
    Sham Kakade, Michael Kearns, John Langford, & Luis Ortiz.
    In the Proceedings of the ACM Electronic Commerce Conference 2003. [ps] [pdf]

  • Policy Search by Dynamic Programming.
    Drew Bagnell, Sham Kakade, Andrew Ng, & Geoff Schneider.
    In NIPS 2003. [ps] [pdf]

  • Exploration in Metric State Spaces.
    Sham Kakade, Michael Kearns, & John Langford.
    In the Proceedings of the 20th International Conference on Machine Learning 2003. [ps] [pdf]


2002

  • Approximately Optimal Approximate Reinforcement Learning.
    Sham Kakade & John Langford.
    In Proceedings of the Nineteenth International Conference on Machine Learning 2002. [ps] [pdf]

  • Competitive Analysis of the Explore/Exploit Tradeoff.
    John Langford, Martin Zinkevich, & Sham Kakade.
    In Proceedings of the Nineteenth International Conference on Machine Learning 2002. [ps] [pdf]

  • A Natural Policy Gradient.
    Sham Kakade.
    In Advances in Neural Information Processing Systems 14 2002. [ps] [pdf]

  • An Alternative Objective Function for Markovian Fields.
    Sham Kakade, Yee Whye Teh, & Sam Roweis.
    In Proceedings of the Nineteenth International Conference on Machine Learning 2002. [ps]

  • Opponent Interactions Between Serotonin and Dopamine.
    Nathaniel D. Daw, Sham Kakade, & Peter Dayan.
    In Neural Networks 2002. [pdf]

  • Dopamine: Generalization and Bonuses
    Sham Kakade & Peter Dayan.
    In Neural Networks 2002. [pdf]
    Also see Dopamine Bonuses.
    In Advances in Neural Information Processing Systems 13 2001.
    [ps.gz] [pdf]

  • Acquisition and Extinction in Autoshaping.
    Sham Kakade & Peter Dayan.
    In Psychological Review 2002. [ps.gz] [pdf]
    Also see Acquisition in Autoshaping.
    In Advances in Neural Information Processing Systems 12, 2000. [ps.gz] [pdf]


2001

  • Optimizing Average Reward Using Discounted Rewards.
    Sham Kakade.
    In Proceedings of the 14th Annual Conference on Computational Learning Theory 2001. [ps] [pdf]

  • Explaining Away in Weight Space.
    Peter Dayan & Sham Kakade.
    In Advances in Neural Information Processing Systems 13, 2001. [ps.gz] [pdf]


2000

  • Learning and Selective Attention.
    Peter Dayan, Sham Kakade, & P. Read Montague.
    Nature Neuroscience, 3, 1218-1223. 2000. [pdf]