Papers to choose from for Friday, August 9 presentations

Statistical Learning: Suggestions from Rob Schapire

• Learnability, Stability and Uniform Convergence Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, Karthik Sridharan
• PAC-Bayesian Stochastic Model Selection David A. McAllester
• Evolvability Leslie G. Valiant
• Efficient Noise-Tolerant Learning from Statistical Queries Michael Kearns
• Learnability can be undecidable Shai Ben-David, Pavel Hrubeš, Shay Moran, Amir Shpilka & Amir Yehudayoff
• Chapter 5 or 6 from Boosting: Foundations and Algorithms

Convex Optimization: Suggestions from Sebastien Bubeck

• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) Bach and Moulines 2013. See also this blog post.
• A geometric alternative to Nesterov's accelerated gradient descent Bubeck, Lee, Singh 2015.
• Optimal Algorithms for Non-Smooth Distributed Optimization in Networks Scaman et al. 2018
• Bandit convex optimization: towards tight bounds, Hazan and Levy 2014. For the brave, see also this.

Bandits: Suggestions from Kevin Jamieson

• On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models Emilie Kaufmann, Olivier Cappé, Aurélien Garivier 2016
• A tutorial on thompson sampling, Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, 2018
• Improved algorithms for linear stochastic bandits, Yasin Abbasi-Yadkori, Dávid Pál, Csaba Szepesvári, 2011.
• An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits, Yevgeny Seldin, Gábor Lugosi, 2017

Reinforcement Learning: Suggestions from Emma Brunskill

• Contextual decision processes with low Bellman rank are PAC-learnable. Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., & Schapire, R. E Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017.
• Data-efficient off-policy policy evaluation for reinforcement learning. Thomas, P. and Brunskill, E., 2016, June. In International Conference on Machine Learning (pp. 2139-2148).
• Batch Policy Learning under Constraints. Le, H., Voloshin, C., & Yue, Y. (2019, May). In International Conference on Machine Learning (pp. 3703-3712).
• Minimax regret bounds for reinforcement learning. Azar, M. G., Osband, I., & Munos, R. (2017, August). In Proceedings of the 34th International Conference on Machine Learning-Volume 70 (pp. 263-272).

Deep Learning: Suggestions from Joan Bruna

• Breaking the curse of dimensionality with convex neural networks, F. Bach, JMLR’17
• On lazy training in differentiable programming, L. Chizat, E. Oyallon, F. Bach
• Trainability and Accuracy of Neural Networks: An interacting particle system approach, G. Rotskoff, E. Vanden-Eijnden, CPAM,’19
• On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport, Chizat & Bach, Neurips’18.
• Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks, Safran & Shamir, ICML’17