Timezone: »
One of the main practical goals of machine learning is to identify relevant trade-offs in different problems, formalize, and solve them. We have already achieved fairly good progress in addressing individual trade-offs, such as model order selection or exploration-exploitation. In this workshop we would like to focus on problems that involve more than one trade-off simultaneously. We are interested both in practical problems where "multi-trade-offs" arise and in theoretical approaches to their solution. Obviously, many problems in life cannot be reduced to a single trade-off and it is highly important to improve our ability to address multiple trade-offs simultaneously. Below we provide several examples of situations, where multiple trade-offs arise simultaneously. The goal of the examples is to provide a starting point for a discussion, but they are not limiting the scope and any other multi-trade-off problem is welcome to be discussed at the workshop.
Multi-trade-offs arise naturally in interaction between multiple learning systems or when a learning system faces multiple tasks simultaneously; especially when the systems or tasks share common resources, such as CPU time, memory, sensors, robot body, and so on. For a concrete example, imagine a robot riding a bicycle and balancing a pole. Each task individually (cycling and pole balancing) can be modeled as a separate optimization problem, but their solutions have to be coordinated, since they share robot resources and robot body. More generally, each learning system or system component has its own internal trade-offs, which have to be balanced against trade-offs of other systems, whereas shared resources introduce external trade-offs that enforce cooperation. The complexity of interaction can vary from independent systems sharing common resources to systems with various degrees of relation between their inputs and tasks. In multi-agent systems communication between the agents introduces an additional trade-off.
We are also interested in multi-trade-offs that arise within individual systems. For example, model order selection and computational complexity [1], or model order selection and exploration-exploitation [2]. For a specific example of this type of problems, imagine a system for real-time prediction of the location of a ball in table tennis. This system has to balance between at least three objectives that interact in a non-trivial manner: (1) complexity of the model of flight trajectory, (2) statistical reliability of the model, (3) computational requirements. Complex models can potentially provide better predictions, but can also lead to overfitting (trade-off between (1) and (2)) and are computationally more demanding. At the same time, there is also a trade-off between having fast crude predictions or slower, but more precise estimations (trade-off between (3) and (1)+(2)).
Despite the complex nature of multi-trade-offs, there is still hope that they can be formulated as convex problems, at least in some situations [3].
References:
[1] Shai Shalev-Shwartz and Nathan Srebro. "SVM Optimization: Inverse Dependence on Training Set Size", ICML, 2008.
[2] Yevgeny Seldin, Peter Auer, François Laviolette, John Shawe-Taylor, and Ronald Ortner. "PAC-Bayesian Analysis of Contextual Bandits", NIPS, 2011.
[3] Andreas Argyriou, Theodoros Evgeniou and Massimiliano Pontil. Convex multi-task feature learning. Machine Learning, 2008, Volume 73, Number 3.
Author Information
Yevgeny Seldin (University of Copenhagen)
Guy Lever (UCL)
John Shawe-Taylor (UCL)
John Shawe-Taylor has contributed to fields ranging from graph theory through cryptography to statistical learning theory and its applications. However, his main contributions have been in the development of the analysis and subsequent algorithmic definition of principled machine learning algorithms founded in statistical learning theory. This work has helped to drive a fundamental rebirth in the field of machine learning with the introduction of kernel methods and support vector machines, driving the mapping of these approaches onto novel domains including work in computer vision, document classification, and applications in biology and medicine focussed on brain scan, immunity and proteome analysis. He has published over 300 papers and two books that have together attracted over 60000 citations. He has also been instrumental in assembling a series of influential European Networks of Excellence. The scientific coordination of these projects has influenced a generation of researchers and promoted the widespread uptake of machine learning in both science and industry that we are currently witnessing.
Nicolò Cesa-Bianchi (Università degli Studi di Milano, Italy)
Yacov Crammer (Technion)
Francois Laviolette (Université Laval)
Gabor Lugosi (Pompeu Fabra University)

Gabor Lugosi is an ICREA research professor at the Department of Economics and Business, Pompeu Fabra University, Barcelona. He received his Ph.D. from the Hungarian Academy of Sciences in 1991. His research has mostly focused on the mathematical aspects of machine learning and related topics in probability and mathematical statistics, including combinatorial statistics, the analysis of random structures, and information theory. He is a co-author of several monographs on pattern recognition, density estimation, online learning, and concentration inequalities.
Peter Bartlett (UC Berkeley)
More from the Same Authors
-
2021 : Progress in Self-Certified Neural Networks »
Maria Perez-Ortiz · Omar Rivasplata · Emilio Parrado-Hernández · Benjamin Guedj · John Shawe-Taylor -
2023 Poster: The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks »
Spencer Frei · Gal Vardi · Peter Bartlett · Nati Srebro -
2022 Poster: Finite Sample Analysis Of Dynamic Regression Parameter Learning »
Mark Kozdoba · Edward Moroshko · Shie Mannor · Yacov Crammer -
2021 Poster: Near Optimal Policy Optimization via REPS »
Aldo Pacchiano · Jonathan N Lee · Peter Bartlett · Ofir Nachum -
2021 Poster: On the Theory of Reinforcement Learning with Once-per-Episode Feedback »
Niladri Chatterji · Aldo Pacchiano · Peter Bartlett · Michael Jordan -
2021 Invited Talk: Benign Overfitting »
Peter Bartlett -
2021 Poster: Adversarial Examples in Multi-Layer Random ReLU Networks »
Peter Bartlett · Sebastien Bubeck · Yeshwanth Cherapanamjeri -
2021 Invited Talk: Do We Know How to Estimate the Mean? »
Gabor Lugosi -
2020 Poster: Preference learning along multiple criteria: A game-theoretic perspective »
Kush Bhatia · Ashwin Pananjady · Peter Bartlett · Anca Dragan · Martin Wainwright -
2020 Poster: PAC-Bayes Analysis Beyond the Usual Bounds »
Omar Rivasplata · Ilja Kuzborskij · Csaba Szepesvari · John Shawe-Taylor -
2020 Session: Orals & Spotlights Track 11: Learning Theory »
Dylan Foster · Nicolò Cesa-Bianchi -
2019 Poster: Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks »
Gaël Letarte · Pascal Germain · Benjamin Guedj · Francois Laviolette -
2018 Poster: Adaptation to Easy Data in Prediction with Limited Advice »
Tobias Sommer Thune · Yevgeny Seldin -
2018 Poster: Gen-Oja: 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: Horizon-Independent Minimax Linear Regression »
Alan Malek · Peter Bartlett -
2018 Poster: Efficient Loss-Based Decoding on Graphs for Extreme Classification »
Itay Evron · Edward Moroshko · Yacov Crammer -
2018 Poster: PAC-Bayes bounds for stable algorithms with instance-dependent priors »
Omar Rivasplata · Emilio Parrado-Hernandez · John Shawe-Taylor · Shiliang Sun · Csaba Szepesvari -
2018 Poster: Empirical Risk Minimization Under Fairness Constraints »
Michele Donini · Luca Oneto · Shai Ben-David · John Shawe-Taylor · Massimiliano Pontil -
2018 Tutorial: Statistical Learning Theory: a Hitchhiker's Guide »
John Shawe-Taylor · Omar Rivasplata -
2017 : Neil Lawrence, Francis Bach and François Laviolette »
Neil Lawrence · Francis Bach · Francois Laviolette -
2017 : John Shawe-Taylor - Distribution Dependent Priors for Stable Learning »
John Shawe-Taylor -
2017 : Yevgeny Seldin - A Strongly Quasiconvex PAC-Bayesian Bound »
Yevgeny Seldin -
2017 : Poster session »
Nicolò Cesa-Bianchi -
2017 : An Efficient Method to Impose Fairness in Linear Models »
Massimiliano Pontil · John Shawe-Taylor -
2017 : François Laviolette - A Tutorial on PAC-Bayesian Theory »
Francois Laviolette -
2017 Workshop: Workshop on Prioritising Online Content »
John Shawe-Taylor · Massimiliano Pontil · Nicolò Cesa-Bianchi · Emine Yilmaz · Chris Watkins · Sebastian Riedel · Marko Grobelnik -
2017 Workshop: From 'What If?' To 'What Next?' : Causal Inference and Machine Learning for Intelligent Decision Making »
Ricardo Silva · Panagiotis Toulis · John Shawe-Taylor · Alexander Volfovsky · Thorsten Joachims · Lihong Li · Nathan Kallus · Adith Swaminathan -
2017 Poster: Nonparametric Online Regression while Learning the Metric »
Ilja Kuzborskij · Nicolò Cesa-Bianchi -
2017 Poster: Near Minimax Optimal Players for the Finite-Time 3-Expert Prediction Problem »
Yasin Abbasi Yadkori · Peter Bartlett · Victor Gabillon -
2017 Poster: Rotting Bandits »
Nir Levine · Yacov Crammer · Shie Mannor -
2017 Poster: Spectrally-normalized margin bounds for neural networks »
Peter Bartlett · Dylan J Foster · Matus Telgarsky -
2017 Poster: Boltzmann Exploration Done Right »
Nicolò Cesa-Bianchi · Claudio Gentile · Gergely Neu · Gabor Lugosi -
2017 Spotlight: Spectrally-normalized 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 -
2017 Poster: Maximum Margin Interval Trees »
Alexandre Drouin · Toby Hocking · Francois Laviolette -
2016 Workshop: "What If?" Inference and Learning of Hypothetical and Counterfactual Interventions in Complex Systems »
Ricardo Silva · John Shawe-Taylor · Adith Swaminathan · Thorsten Joachims -
2016 Workshop: Learning, Inference and Control of Multi-Agent Systems »
Thore Graepel · Marc Lanctot · Joel Leibo · Guy Lever · Janusz Marecki · Frans Oliehoek · Karl Tuyls · Vicky Holgate -
2016 Poster: Adaptive Averaging in Accelerated Descent Dynamics »
Walid Krichene · Alexandre Bayen · Peter Bartlett -
2016 Poster: Efficient Second Order Online Learning by Sketching »
Haipeng Luo · Alekh Agarwal · Nicolò Cesa-Bianchi · John Langford -
2015 Poster: Linear Multi-Resource Allocation with Semi-Bandit 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: Large-scale 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: Large-Margin Convex Polytope Machine »
Alex Kantchelian · Michael C Tschantz · Ling Huang · Peter Bartlett · Anthony D Joseph · J. D. Tygar -
2014 Poster: Multilabel Structured Output Learning with Random Spanning Trees of Max-Margin Markov Networks »
Mario Marchand · Hongyu Su · Emilie Morvant · Juho Rousu · John Shawe-Taylor -
2014 Poster: Efficient Minimax Strategies for Square Loss Games »
Wouter M Koolen · Alan Malek · Peter Bartlett -
2013 Workshop: Resource-Efficient Machine Learning »
Yevgeny Seldin · Yasin Abbasi Yadkori · Yacov Crammer · Ralf Herbrich · Peter Bartlett -
2013 Poster: Online Learning with Switching Costs and Other Adaptive Adversaries »
Nicolò Cesa-Bianchi · Ofer Dekel · Ohad Shamir -
2013 Poster: PAC-Bayes-Empirical-Bernstein Inequality »
Ilya Tolstikhin · Yevgeny Seldin -
2013 Poster: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Poster: How to Hedge an Option Against an Adversary: Black-Scholes Pricing is Minimax Optimal »
Jacob D Abernethy · Peter Bartlett · Rafael Frongillo · Andre Wibisono -
2013 Spotlight: How to Hedge an Option Against an Adversary: Black-Scholes Pricing is Minimax Optimal »
Jacob D Abernethy · Peter Bartlett · Rafael Frongillo · Andre Wibisono -
2013 Oral: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · Nicolò Cesa-Bianchi · Claudio Gentile · Yishay Mansour -
2013 Spotlight: PAC-Bayes-Empirical-Bernstein Inequality »
Ilya Tolstikhin · Yevgeny Seldin -
2013 Poster: A Gang of Bandits »
Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
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 Poster: A Linear Time Active Learning Algorithm for Link Classification »
Nicolò Cesa-Bianchi · Claudio Gentile · Fabio Vitale · Giovanni Zappella -
2012 Poster: Mirror Descent Meets Fixed Share (and feels no regret) »
Nicolò Cesa-Bianchi · Pierre Gaillard · Gabor Lugosi · Gilles Stoltz -
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ò Cesa-Bianchi · Francois Laviolette · John Shawe-Taylor -
2011 Poster: Efficient Online Learning via Randomized Rounding »
Nicolò Cesa-Bianchi · Ohad Shamir -
2011 Oral: Efficient Online Learning via Randomized Rounding »
Nicolò Cesa-Bianchi · Ohad Shamir -
2011 Poster: PAC-Bayesian Analysis of Contextual Bandits »
Yevgeny Seldin · Peter Auer · Francois Laviolette · John Shawe-Taylor · Ronald Ortner -
2011 Poster: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2011 Spotlight: See the Tree Through the Lines: The Shazoo Algorithm »
Fabio Vitale · Nicolò Cesa-Bianchi · Claudio Gentile · Giovanni Zappella -
2011 Session: Opening Remarks and Awards »
Terrence 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 -
2010 Talk: Opening Remarks and Awards »
Richard Zemel · Terrence Sejnowski · John Shawe-Taylor -
2009 Workshop: Learning from Multiple Sources with Applications to Robotics »
Barbara Caputo · Nicolò Cesa-Bianchi · David R Hardoon · Gayle Leen · Francesco Orabona · Jaakko Peltonen · Simon Rogers -
2009 Workshop: Advances in Ranking »
Shivani Agarwal · Chris J Burges · Yacov Crammer -
2009 Workshop: Grammar Induction, Representation of Language and Language Learning »
Alex Clark · Dorota Glowacka · John Shawe-Taylor · Yee Whye Teh · Chris J Watkins -
2009 Poster: From PAC-Bayes Bounds to KL Regularization »
Pascal Germain · Alexandre Lacasse · Francois Laviolette · Mario Marchand · Sara Shanian -
2009 Poster: Adaptive Regularization of Weight Vectors »
Yacov Crammer · Alex Kulesza · Mark Dredze -
2009 Poster: Information-theoretic lower bounds on the oracle complexity of convex optimization »
Alekh Agarwal · Peter Bartlett · Pradeep Ravikumar · Martin J Wainwright -
2009 Spotlight: Information-theoretic 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 Workshop: Learning from Multiple Sources »
David R Hardoon · Gayle Leen · Samuel Kaski · John Shawe-Taylor -
2008 Workshop: New Challanges in Theoretical Machine Learning: Data Dependent Concept Spaces »
Maria-Florina F Balcan · Shai Ben-David · Avrim Blum · Kristiaan Pelckmans · John Shawe-Taylor -
2008 Session: Oral session 6: Neural Coding »
Yacov Crammer -
2008 Poster: Exact Convex Confidence-Weighted Learning »
Yacov Crammer · Mark Dredze · Fernando Pereira -
2008 Poster: A Transductive Bound for the Voted Classifier with an Application to Semi-supervised Learning »
Massih R Amini · Nicolas Usunier · Francois Laviolette -
2008 Poster: Linear Classification and Selective Sampling Under Low Noise Conditions »
Giovanni Cavallanti · Nicolò Cesa-Bianchi · Claudio Gentile -
2008 Spotlight: Exact Convex Confidence-Weighted Learning »
Yacov Crammer · Mark Dredze · Fernando Pereira -
2008 Spotlight: A Transductive Bound for the Voted Classifier with an Application to Semi-supervised Learning »
Massih R Amini · Nicolas Usunier · Francois Laviolette -
2008 Poster: Theory of matching pursuit »
Zakria Hussain · John Shawe-Taylor -
2008 Poster: On-Line Prediction on Large Diameter Graphs »
Mark Herbster · Massimiliano Pontil · Guy Lever -
2007 Workshop: Music, Brain and Cognition. Part 1: Learning the Structure of Music and Its Effects On the Brain »
David R Hardoon · Eduardo Reck-Miranda · John Shawe-Taylor -
2007 Oral: Adaptive Online Gradient Descent »
Peter Bartlett · Elad Hazan · Sasha Rakhlin -
2007 Poster: Adaptive Online Gradient Descent »
Peter Bartlett · Elad Hazan · Sasha Rakhlin -
2007 Poster: Variational Inference for Diffusion Processes »
Cedric Archambeau · Manfred Opper · Yuan Shen · Dan Cornford · John Shawe-Taylor -
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 Workshop: Dynamical Systems, Stochastic Processes and Bayesian Inference »
Manfred Opper · Cedric Archambeau · John Shawe-Taylor -
2006 Poster: A PAC-Bayes Risk Bound for General Loss Functions »
Pascal Germain · Alexandre Lacasse · Francois Laviolette · Mario Marchand -
2006 Poster: Shifting, One-Inclusion 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: Tighter PAC-Bayes Bounds »
Amiran Ambroladze · Emilio Parrado-Hernandez · John Shawe-Taylor -
2006 Poster: Information Bottleneck for Non Co-Occurrence Data »
Yevgeny Seldin · Noam Slonim · Naftali Tishby -
2006 Poster: Analysis of Representations for Domain Adaptation »
John Blitzer · Shai Ben-David · Yacov Crammer · Fernando Pereira -
2006 Poster: PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier »
Alexandre Lacasse · Francois Laviolette · Mario Marchand · Pascal Germain · Nicolas Usunier -
2006 Spotlight: PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier »
Alexandre Lacasse · Francois Laviolette · Mario Marchand · Pascal Germain · Nicolas Usunier -
2006 Poster: AdaBoost is Consistent »
Peter Bartlett · Mikhail Traskin