Reminder: Multi-Trade-offs in Machine Learning, NIPS-2012 workshop

Multi-Trade-offs in Machine Learning
NIPS-2012 Workshop, Lake Tahoe, Nevada, US
December 7 or 8, 2012

We invite submission of abstracts and open problems to Multi-Trade-offs in Machine Learning NIPS-2012 workshop.
Submission Deadline: October 16.
Travel Support Application Deadline: October 23.
Notification of Acceptance: October 30.
More details are provided below.


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 has 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 the 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].

[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.

Call for Contributions

We invite submission of abstracts and open problems to the workshop. Abstracts and open problems should be at most 4 pages long in the NIPS format (appendices are allowed, but the organizers reserve the right to evaluate the submissions based on the first 4 pages only). Selected abstracts and open problems will be presented as talks or posters during the workshop. Submissions should be sent by email to


Submission Deadline: October 16.

Notification of Acceptance: October 30.

• Theory and application-oriented contributions are equally welcome.
• All the submissions should indicate clearly at least two non-trivial trade-offs they are addressing.
• Submission of previously published work or work under review is allowed, in particular NIPS-2012 submissions. However, for oral presentations preference will be given to novel work or work that was not yet presented elsewhere (for example, recent journal publications or NIPS posters). All double submissions must be clearly declared as such!

Invited Speakers

Shai Shalev-Shwartz, The Hebrew University of Jerusalem
Jan Peters, Technische Universitaet Darmstadt and Max Planck Institute for Intelligent Systems
Csaba Szepesvari, University of Alberta


Yevgeny Seldin, Max Planck Institute for Intelligent Systems and University College London
Guy Lever, University College London
John Shawe-Taylor, University College London
Koby Crammer, The Technion
Nicolò Cesa-Bianchi, Università degli Studi di Milano
François Laviolette, Université Laval (Québec)
Gábor Lugosi, Pompeu Fabra University
Peter Bartlett, UC Berkeley and Queensland University of Technology


We are grateful for receiving support from the PASCAL network.

If you would also like to sponsor this event, please, contact

Tentative Schedule
7:30 – 7:35 Opening remarks
7:35 – 8:20 Invited Talk
8:20 – 8:50 Two Contributed Talks
8:50 – 9:10 Break
9:10 – 9:55 Invited Talk
9:55 – 10:30 Open Problems Session
10:30 – 15:30 Break
15:30 – 16:15 Invited Talk
16:15 – 16:25 Break
16:25 – 17:00 Two Contributed Talks
17:00 – 18:30 Posters
18:30 – 19:00 Workshop Summary and Open Discussion