Timezone: »
Resource efficiency is key for making ideas practical. It is crucial in many tasks, ranging from largescale learning ("big data'') to smallscale mobile devices. Understanding resource efficiency is also important for understanding of biological systems, from individual cells to complex learning systems, such as the human brain. The goal of this workshop is to improve our fundamental theoretical understanding and link between various applications of learning under constraints on the resources, such as computation, observations, communication, and memory. While the founding fathers of machine learning were mainly concerned with characterizing the sample complexity of learning (the observations resource) [VC74] it now gets realized that fundamental understanding of other resource requirements, such as computation, communication, and memory is equally important for further progress [BB11].
The problem of resourceefficient learning is multidimensional and we already see some parts of this puzzle being assembled. One question is the interplay between the requirements on different resources. Can we use more of one resource to save on a different resource? For example, the dependence between computation and observations requirements was studied in [SSS08,SSST12,SSB12]. Another question is online learning under various budget constraints [AKKS12,BKS13,CKS04,DSSS05,CBG06]. One example that Badanidiyuru et al. provide is dynamic pricing with limited supply, where we have a limited number of items to sell and on each successful sale transaction we lose one item. A related question of online learning under constraints on information acquisition was studied in [SBCA13], where the constraints could be computational (information acquisition required computation) or monetary. Yet another direction is adaptation of algorithms to the complexity of operation environment. Such adaptation can allow resource consumption to reflect the hardness of a situation being faced. An example of such adaptation in multiarmed bandits with side information was given in [SAL+11]. Another way of adaptation is interpolation between stochastic and adversarial environments. At the moment there are two prevailing formalisms for modeling the environment, stochastic and adversarial (also known as the average case'' and
the worst case''). But in reality the environment is often neither stochastic, nor adversarial, but something in between. It is, therefore, crucial to understand the intermediate regime. First steps in this direction were done in [BS12]. And, of course, one of the flagman problems nowadays is ``big data'', where the constraint shifts from the number of observations to computation. We strongly believe that there are deep connections between problems at various scales and with various resource constraints and there are basic principles of learning under resource constraints that are yet to be discovered. We invite researchers to share their practical challenges and theoretical insights on this problem.
One additional important direction is design of resourcedependent performance measures. In the past, algorithms were compared in terms of predictive accuracy (classification errors, AUC, Fmeasures, NDCG, etc.), yet there is a need to evaluate them with additional metrics related to resources, such as memory, CPU time, and even power. For example, reward per computation operation. This theme will also be discussed at the workshop.
References:
[AKKS12] Kareem Amin, Michael Kearns, Peter Key and Anton Schwaighofer. Budget Optimization for Sponsored Search: Censored Learning in MDPs. UAI 2012.
[BB11] Leon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. In Suvrit Sra, Sebastian Nowozin, and Stephen J. Wright, editors, Optimization for Machine Learning. MIT Press, 2011.
[BKS13] Ashwinkumar Badanidiyuru, Robert Kleinberg and Aleksandrs Slivkins. Bandits with Knapsacks. FOCS, 2013.
[BS12] Sebastien Bubeck and Aleksandrs Slivkins. The best of both worlds: stochastic and adversarial bandits. COLT, 2012.
[CBG06] Nicolò CesaBianchi and Claudio Gentile. Tracking the best hyperplane with a simple budget perceptron. COLT 2006.
[CKS04] Koby Crammer, Jaz Kandola and Yoram Singer. Online Classification on a Budget. NIPS 2003.
[DSSS05] Ofer Dekel, Shai Shalevshwartz and Yoram Singer. The Forgetron: A kernelbased perceptron on a fixed budget. NIPS 2004.
[SAL+11] Yevgeny Seldin, Peter Auer, François Laviolette, John ShaweTaylor, and Ronald Ortner. PACBayesian Analysis of Contextual Bandits. NIPS, 2011.
[SBCA13] Yevgeny Seldin, Peter Bartlett, Koby Crammer, and Yasin AbbasiYadkori. Prediction with Limited Advice and Multiarmed Bandits with Paid Observations. 2013.
[SSB12] Shai ShalevShwartz and Aharon Birnbaum. Learning halfspaces with the zeroone loss: Timeaccuracy tradeoffs. NIPS, 2012.
[SSS08] Shai ShalevShwartz and Nathan Srebro. SVM Optimization: Inverse Dependence on Training Set Size. ICML, 2008.
[SSST12] Shai ShalevShwartz, Ohad Shamir, and Eran Tromer. Using more data to speedup training time. AISTATS, 2012.
[VC74] Vladimir N. Vapnik and Alexey Ya. Chervonenkis. Theory of pattern recognition. Nauka, Moscow (in Russian), 1974. German translation: W.N.Wapnik, A.Ya.Tschervonenkis (1979), Theorie der Zeichenerkennug, Akademia, Berlin.
Author Information
Yevgeny Seldin (University of Copenhagen)
Yasin Abbasi Yadkori (Adobe Research)
Yacov Crammer (Technion)
Ralf Herbrich (Amazon)
Peter Bartlett (UC Berkeley)
More from the Same Authors

2019 Poster: Thompson Sampling and Approximate Inference »
My Phan · Yasin Abbasi Yadkori · Justin Domke 
2019 Poster: Bootstrapping Upper Confidence Bound »
Botao Hao · Yasin Abbasi Yadkori · Zheng Wen · Guang Cheng 
2018 Workshop: NeurIPS 2018 Competition Track Day 2 »
Ralf Herbrich · Sergio Escalera 
2018 Workshop: NeurIPS 2018 Competition Track Day 1 »
Sergio Escalera · Ralf Herbrich 
2018 Poster: Adaptation to Easy Data in Prediction with Limited Advice »
Tobias Sommer Thune · Yevgeny Seldin 
2018 Poster: GenOja: Simple & Efficient Algorithm for Streaming Generalized Eigenvector Computation »
Kush Bhatia · Aldo Pacchiano · Nicolas Flammarion · Peter Bartlett · Michael Jordan 
2018 Poster: Factored Bandits »
Julian Zimmert · Yevgeny Seldin 
2018 Poster: HorizonIndependent Minimax Linear Regression »
Alan Malek · Peter Bartlett 
2018 Poster: Efficient LossBased Decoding on Graphs for Extreme Classification »
Itay Evron · Edward Moroshko · Yacov Crammer 
2018 Poster: Scalar Posterior Sampling with Applications »
Georgios Theocharous · Zheng Wen · Yasin Abbasi Yadkori · Nikos Vlassis 
2017 Poster: Near Minimax Optimal Players for the FiniteTime 3Expert Prediction Problem »
Yasin Abbasi Yadkori · Peter Bartlett · Victor Gabillon 
2017 Poster: Rotting Bandits »
Nir Levine · Yacov Crammer · Shie Mannor 
2017 Poster: Conservative Contextual Linear Bandits »
Abbas Kazerouni · Mohammad Ghavamzadeh · Yasin Abbasi · Benjamin Van Roy 
2017 Poster: Spectrallynormalized margin bounds for neural networks »
Peter Bartlett · Dylan J Foster · Matus Telgarsky 
2017 Spotlight: Spectrallynormalized margin bounds for neural networks »
Peter Bartlett · Dylan J Foster · Matus Telgarsky 
2017 Poster: Alternating minimization for dictionary learning with random initialization »
Niladri Chatterji · Peter Bartlett 
2017 Poster: Acceleration and Averaging in Stochastic Descent Dynamics »
Walid Krichene · Peter Bartlett 
2017 Spotlight: Acceleration and Averaging in Stochastic Descent Dynamics »
Walid Krichene · Peter Bartlett 
2016 Poster: Adaptive Averaging in Accelerated Descent Dynamics »
Walid Krichene · Alexandre Bayen · Peter Bartlett 
2015 Workshop: Machine Learning From and For Adaptive User Technologies: From Active Learning & Experimentation to Optimization & Personalization »
Joseph Jay Williams · Yasin Abbasi Yadkori · Finale DoshiVelez 
2015 Poster: Linear MultiResource Allocation with SemiBandit Feedback »
Tor Lattimore · Yacov Crammer · Csaba Szepesvari 
2015 Poster: Accelerated Mirror Descent in Continuous and Discrete Time »
Walid Krichene · Alexandre Bayen · Peter Bartlett 
2015 Spotlight: Accelerated Mirror Descent in Continuous and Discrete Time »
Walid Krichene · Alexandre Bayen · Peter Bartlett 
2015 Poster: Minimax Time Series Prediction »
Wouter Koolen · Alan Malek · Peter Bartlett · Yasin Abbasi Yadkori 
2014 Workshop: Largescale reinforcement learning and Markov decision problems »
Benjamin Van Roy · Mohammad Ghavamzadeh · Peter Bartlett · Yasin Abbasi Yadkori · Ambuj Tewari 
2014 Poster: Learning Multiple Tasks in Parallel with a Shared Annotator »
Haim Cohen · Yacov Crammer 
2014 Poster: LargeMargin Convex Polytope Machine »
Alex Kantchelian · Michael C Tschantz · Ling Huang · Peter Bartlett · Anthony D Joseph · J. D. Tygar 
2014 Poster: Efficient Minimax Strategies for Square Loss Games »
Wouter M Koolen · Alan Malek · Peter Bartlett 
2013 Workshop: Probabilistic Models for Big Data »
Neil D Lawrence · Joaquin Quiñonero Candela · Tianshi Gao · James Hensman · Zoubin Ghahramani · Max Welling · David Blei · Ralf Herbrich 
2013 Poster: PACBayesEmpiricalBernstein Inequality »
Ilya Tolstikhin · Yevgeny Seldin 
2013 Poster: How to Hedge an Option Against an Adversary: BlackScholes Pricing is Minimax Optimal »
Jacob D Abernethy · Peter Bartlett · Rafael Frongillo · Andre Wibisono 
2013 Spotlight: How to Hedge an Option Against an Adversary: BlackScholes Pricing is Minimax Optimal »
Jacob D Abernethy · Peter Bartlett · Rafael Frongillo · Andre Wibisono 
2013 Spotlight: PACBayesEmpiricalBernstein Inequality »
Ilya Tolstikhin · Yevgeny Seldin 
2013 Poster: Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions »
Yasin Abbasi Yadkori · Peter Bartlett · Varun Kanade · Yevgeny Seldin · Csaba Szepesvari 
2012 Workshop: MultiTradeoffs in Machine Learning »
Yevgeny Seldin · Guy Lever · John ShaweTaylor · Nicolò CesaBianchi · Yacov Crammer · Francois Laviolette · Gabor Lugosi · Peter Bartlett 
2012 Demonstration: DIRTBIS  Distributed RealTime Bayesian Inference Service »
Ralf Herbrich 
2012 Poster: Volume Regularization for Binary Classification »
Yacov Crammer · Tal Wagner 
2012 Spotlight: Volume Regularization for Binary Classification »
Yacov Crammer · Tal Wagner 
2012 Poster: Learning Multiple Tasks using Shared Hypotheses »
Yacov Crammer · Yishay Mansour 
2011 Workshop: New Frontiers in Model Order Selection »
Yevgeny Seldin · Yacov Crammer · Nicolò CesaBianchi · Francois Laviolette · John ShaweTaylor 
2011 Poster: Improved Algorithms for Linear Stochastic Bandits »
Yasin Abbasi Yadkori · David Pal · Csaba Szepesvari 
2011 Spotlight: Improved Algorithms for Linear Stochastic Bandits »
Yasin Abbasi Yadkori · David Pal · Csaba Szepesvari 
2011 Poster: PACBayesian Analysis of Contextual Bandits »
Yevgeny Seldin · Peter Auer · Francois Laviolette · John ShaweTaylor · Ronald Ortner 
2011 Session: Opening Remarks and Awards »
Terrence J Sejnowski · Peter Bartlett · Fernando Pereira 
2010 Poster: Learning via Gaussian Herding »
Yacov Crammer · Daniel Lee 
2010 Poster: New Adaptive Algorithms for Online Classification »
Francesco Orabona · Yacov Crammer 
2009 Workshop: Advances in Ranking »
Shivani Agarwal · Chris J Burges · Yacov Crammer 
2009 Poster: Adaptive Regularization of Weight Vectors »
Yacov Crammer · Alex Kulesza · Mark Dredze 
2009 Poster: Informationtheoretic lower bounds on the oracle complexity of convex optimization »
Alekh Agarwal · Peter Bartlett · Pradeep Ravikumar · Martin J Wainwright 
2009 Spotlight: Informationtheoretic lower bounds on the oracle complexity of convex optimization »
Alekh Agarwal · Peter Bartlett · Pradeep Ravikumar · Martin J Wainwright 
2009 Spotlight: Adaptive Regularization of Weight Vectors »
Yacov Crammer · Alex Kulesza · Mark Dredze 
2008 Session: Oral session 6: Neural Coding »
Yacov Crammer 
2008 Poster: Exact Convex ConfidenceWeighted Learning »
Yacov Crammer · Mark Dredze · Fernando Pereira 
2008 Spotlight: Exact Convex ConfidenceWeighted Learning »
Yacov Crammer · Mark Dredze · Fernando Pereira 
2007 Workshop: Machine Learning and Games (MALAGA): Open Directions in Applying Machine Learning to Games »
Joaquin Quiñonero Candela · Thore K Graepel · Ralf Herbrich 
2007 Oral: Adaptive Online Gradient Descent »
Peter Bartlett · Elad Hazan · Sasha Rakhlin 
2007 Poster: TrueSkill Through Time: Revisiting the History of Chess »
Pierre Dangauthier · Ralf Herbrich · Tom Minka · Thore K Graepel 
2007 Poster: Adaptive Online Gradient Descent »
Peter Bartlett · Elad Hazan · Sasha Rakhlin 
2007 Spotlight: TrueSkill Through Time: Revisiting the History of Chess »
Pierre Dangauthier · Ralf Herbrich · Tom Minka · Thore K Graepel 
2007 Demonstration: Learning To Race by ModelBased Reinforcement Learning with Adaptive Abstraction »
Thore K Graepel · Phil A Trelford · Ralf Herbrich · Mykel J Kochenderfer 
2007 Poster: Optimistic Linear Programming gives Logarithmic Regret for Irreducible MDPs »
Ambuj Tewari · Peter Bartlett 
2007 Poster: Learning Bounds for Domain Adaptation »
John Blitzer · Yacov Crammer · Alex Kulesza · Fernando Pereira · Jennifer Wortman Vaughan 
2006 Poster: Shifting, OneInclusion Mistake Bounds and Tight Multiclass Expected Risk Bounds »
Benjamin Rubinstein · Peter Bartlett · J. Hyam Rubinstein 
2006 Poster: Learning from Multiple Sources »
Yacov Crammer · Michael Kearns · Jennifer Wortman Vaughan 
2006 Poster: Sample Complexity of Policy Search with Known Dynamics »
Peter Bartlett · Ambuj Tewari 
2006 Poster: Information Bottleneck for Non CoOccurrence Data »
Yevgeny Seldin · Noam Slonim · Naftali Tishby 
2006 Poster: TrueSkill: A Bayesian Skill Rating System »
Ralf Herbrich · Tom Minka · Thore K Graepel 
2006 Poster: Analysis of Representations for Domain Adaptation »
John Blitzer · Shai BenDavid · Yacov Crammer · Fernando Pereira 
2006 Talk: TrueSkill: A Bayesian Skill Rating System »
Ralf Herbrich · Tom Minka · Thore K Graepel 
2006 Poster: AdaBoost is Consistent »
Peter Bartlett · Mikhail Traskin