What:
The workshop proposes to focus on relations between machine learning problems. We use “relation” quite generally to include (but not limit ourselves to) notions such as: one type of problem being viewed special case of another type (e.g., classification as thresholded probability estimation); reductions between learning problems (e.g., transforming ranking problems into classification problems); and the use of surrogate losses (e.g., replacing misclassification loss with some other, convex loss). We also include relations between sets of learning problems, such as those studied in the (old) theory of “comparison of experiments”, as well as recent connections between machine learning problems and what could be construed as "economic learning problems" such as prediction markets and forecast elicitation.
Why: The point of studying relations between machine learning problems is that it stands a reasonable chance of being a way to be able to understand the field of machine learning as a whole. It could serve to prevent reinvention, and rapidly facilitate the growth of new methods. The motivation is not dissimilar to Hal Varian’s notion of combinatorial innovation. Another analogy is to consider the development of function theory in the 19th century and observe the rapid advances made possible by the development of functional analysis, which, rather than studying individual functions, studied operators that transformed one function to another.
Much recent work in machine learning can be interpreted as relations between problems. For example:
• Surrogate regret bounds (bound the performance attained for one learning problem in terms of that obtained for another) [Bartlett et al, 2007]
• Relationships between binary classification problems and distances between probability distributions [Reid and Williamson 2011]
• Reductions from class probability estimation to classification, or reinforcement learning to classification [Langford et al; 2005]
More recently there have been connections to problems that do not even seem to be about machine learning, such as the equivalence between
• Costfunction based prediction markets and noregret learning [Chen and WortmanVaughan 2010]
• Elicitability of properties of distributions and proper losses [Lambert 2011]
In fact some older work in machine learning can be viewed as relations between problems:
• Learning with realvalued functions in the presence of noise can be reduced to multiclass classification [Bartlett, Long & Williamson 1996]
• Comparison of Experiments [Blackwell 1955]
If one attempts to construct a catalogue of machine learning problems at present one is rapidly overwhelmed by the complexity. And it is not at all clear (on the basis of the usual description of them) whether or not two problems with different names are really different. (If the reader is unconvinced, consider the following partial list: batch, online, transductive, offtraining set, semisupervised, noisy (label, attribute, constant noise / variable noise, data of variable quality), data of different costs, weighted loss functions, active, distributed, classification (binary weighted binary multiclass), structured output, probabilistic concepts / scoring rules, class probability estimation, learning with statistical queries, NeymanPearson classification, regression, ordinal regression, ranked regression, ranking, ranking the best, optimising the ROC curve, optimising the AUC, regression, selection, novelty detection, multiinstance learning, minimum volume sets, density level sets, regression level sets, sets of quantiles, quantile regression, density estimation, data segmentation, clustering, cotraining, covalidation, learning with constraints, conditional estimators, estimated loss, confidence / hedging estimators, hypothesis testing, distributional distance estimation, learning relations, learning total orders, learning causal relationships, and estimating performance (cross validation)!
Specific topics: We would solicit contributions on novel relations between machine learning problems, as well as theoretical and practical frameworks to construct such relations. We are not restricting the workshop to pure theory, although it seems natural the workshop will have a theoretical bent.
Who: We believe the workshop will be of considerable interest to theoretically inclined machine learning researchers, as it offers a new view as to how to situate one’s work. Furthermore we also believe it should be of interest to practitioners because being able to relate a new problem to an old one can save substantial work in having to construct a new solution.
Outcomes:
• New relations between learning problems – not individual solutions to individual problems
• Visibility and promulgation of the “meme” of relating problems;
• We believe the nature of the workshop would suit the publication of workshop proceedings.
• Potential agreement to a shared community effort to build a comprehensive map of the relations between machine learning problems.
Author Information
Robert Williamson (Australian National University & Data61)
John Langford (Microsoft Research)
John Langford is a machine learning research scientist, a field which he says "is shifting from an academic discipline to an industrial tool". He is the author of the weblog hunch.net and the principal developer of Vowpal Wabbit. John works at Microsoft Research New York, of which he was one of the founding members, and was previously affiliated with Yahoo! Research, Toyota Technological Institute, and IBM's Watson Research Center. He studied Physics and Computer Science at the California Institute of Technology, earning a double bachelor's degree in 1997, and received his Ph.D. in Computer Science from Carnegie Mellon University in 2002. He was the program cochair for the 2012 International Conference on Machine Learning.
Ulrike von Luxburg (University of Tübingen)
Mark Reid (Apple)
Jenn Wortman Vaughan (Microsoft Research)
Jenn Wortman Vaughan is a Senior Researcher at Microsoft Research, New York City, where she studies algorithmic economics, machine learning, and social computing, with a frequent focus on prediction markets and crowdsourcing. Jenn came to MSR in 2012 from UCLA, where she was an assistant professor in the computer science department. She completed her Ph.D. at the University of Pennsylvania in 2009, and subsequently spent a year as a Computing Innovation Fellow at Harvard. She is the recipient of Penn's 2009 Rubinoff dissertation award for innovative applications of computer technology, a National Science Foundation CAREER award, a Presidential Early Career Award for Scientists and Engineers (PECASE), and a handful of best paper or best student paper awards. In her "spare" time, Jenn is involved in a variety of efforts to provide support for women in computer science; most notably, she cofounded the Annual Workshop for Women in Machine Learning, which has been held each year since 2006.
More from the Same Authors

2019 Poster: A PrimalDual link between GANs and Autoencoders »
Hisham Husain · Richard Nock · Robert Williamson 
2019 Poster: Foundations of ComparisonBased Hierarchical Clustering »
Debarghya Ghoshdastidar · Michaël Perrot · Ulrike von Luxburg 
2018 Poster: When do random forests fail? »
Cheng Tang · Damien Garreau · Ulrike von Luxburg 
2018 Poster: Measures of distortion for machine learning »
Leena Chennuru Vankadara · Ulrike von Luxburg 
2018 Poster: A loss framework for calibrated anomaly detection »
Aditya Menon · Robert Williamson 
2018 Poster: Constant Regret, Generalized Mixability, and Mirror Descent »
Zakaria Mhammedi · Robert Williamson 
2018 Spotlight: Constant Regret, Generalized Mixability, and Mirror Descent »
Zakaria Mhammedi · Robert Williamson 
2018 Spotlight: A loss framework for calibrated anomaly detection »
Aditya Menon · Robert Williamson 
2018 Poster: Practical Methods for Graph TwoSample Testing »
Debarghya Ghoshdastidar · Ulrike von Luxburg 
2017 Workshop: Learning in the Presence of Strategic Behavior »
Nika Haghtalab · Yishay Mansour · Tim Roughgarden · Vasilis Syrgkanis · Jennifer Wortman Vaughan 
2017 Poster: fGANs in an Information Geometric Nutshell »
Richard Nock · Zac Cranko · Aditya K Menon · Lizhen Qu · Robert Williamson 
2017 Poster: A Decomposition of Forecast Error in Prediction Markets »
Miro Dudik · Sebastien Lahaie · Ryan Rogers · Jennifer Wortman Vaughan 
2017 Spotlight: fGANs in an Information Geometric Nutshell »
Richard Nock · Zac Cranko · Aditya K Menon · Lizhen Qu · Robert Williamson 
2017 Poster: Kernel functions based on triplet comparisons »
Matthäus Kleindessner · Ulrike von Luxburg 
2016 Tutorial: Crowdsourcing: Beyond Label Generation »
Jennifer Wortman Vaughan 
2015 Poster: Learning with Symmetric Label Noise: The Importance of Being Unhinged »
Brendan van Rooyen · Aditya Menon · Robert Williamson 
2015 Spotlight: Learning with Symmetric Label Noise: The Importance of Being Unhinged »
Brendan van Rooyen · Aditya Menon · Robert Williamson 
2015 Poster: Convergence Analysis of Prediction Markets via Randomized Subspace Descent »
Rafael Frongillo · Mark Reid 
2014 Workshop: NIPS’14 Workshop on Crowdsourcing and Machine Learning »
David Parkes · Denny Zhou · ChienJu Ho · Nihar Bhadresh Shah · Adish Singla · Jared Heyman · Edwin Simpson · Andreas Krause · Rafael Frongillo · Jennifer Wortman Vaughan · Panagiotis Papadimitriou · Damien Peters 
2014 Workshop: NIPS Workshop on Transactional Machine Learning and ECommerce »
David Parkes · David H Wolpert · Jennifer Wortman Vaughan · Jacob D Abernethy · Amos Storkey · Mark Reid · Ping Jin · Nihar Bhadresh Shah · Mehryar Mohri · Luis E Ortiz · Robin Hanson · Aaron Roth · Satyen Kale · Sebastien Lahaie 
2014 Session: Oral Session 9 »
Jennifer Wortman Vaughan 
2014 Poster: From Stochastic Mixability to Fast Rates »
Nishant Mehta · Robert Williamson 
2014 Oral: From Stochastic Mixability to Fast Rates »
Nishant Mehta · Robert Williamson 
2014 Poster: Scalable Nonlinear Learning with Adaptive Polynomial Expansions »
Alekh Agarwal · Alina Beygelzimer · Daniel Hsu · John Langford · Matus J Telgarsky 
2013 Workshop: Crowdsourcing: Theory, Algorithms and Applications »
Jennifer Wortman Vaughan · Greg Stoddard · ChienJu Ho · Adish Singla · Michael Bernstein · Devavrat Shah · Arpita Ghosh · Evgeniy Gabrilovich · Denny Zhou · Nikhil Devanur · Xi Chen · Alexander Ihler · Qiang Liu · Genevieve Patterson · Ashwinkumar Badanidiyuru Varadaraja · Hossein Azari Soufiani · Jacob Whitehill 
2013 Poster: Density estimation from unweighted knearest neighbor graphs: a roadmap »
Ulrike von Luxburg · Morteza Alamgir 
2013 Tutorial: Learning to Interact »
John Langford 
2012 Poster: Mixability in Statistical Learning »
Tim van Erven · Peter Grünwald · Mark Reid · Robert Williamson 
2012 Demonstration: Protocols and Structures for Inference: A RESTful API for Machine Learning Services »
James Montgomery · Mark Reid 
2012 Poster: Interpreting prediction markets: a stochastic approach »
Nicolás Della Penna · Mark Reid · Rafael Frongillo 
2011 Workshop: 2nd Workshop on Computational Social Science and the Wisdom of Crowds »
Winter Mason · Jennifer Wortman Vaughan · Hanna Wallach 
2011 Poster: Phase transition in the family of presistances »
Morteza Alamgir · Ulrike von Luxburg 
2011 Spotlight: Phase transition in the family of presistances »
Morteza Alamgir · Ulrike von Luxburg 
2011 Poster: Composite Multiclass Losses »
Elodie Vernet · Robert Williamson · Mark Reid 
2010 Workshop: Learning on Cores, Clusters, and Clouds »
Alekh Agarwal · Lawrence Cayton · Ofer Dekel · John Duchi · John Langford 
2010 Workshop: Computational Social Science and the Wisdom of Crowds »
Jennifer Wortman Vaughan · Hanna Wallach 
2010 Spotlight: Getting lost in space: Large sample analysis of the resistance distance »
Ulrike von Luxburg · Agnes Radl · Matthias Hein 
2010 Poster: Getting lost in space: Large sample analysis of the resistance distance »
Ulrike von Luxburg · Agnes Radl · Matthias Hein 
2009 Workshop: Clustering: Science or art? Towards principled approaches »
Margareta Ackerman · Shai BenDavid · Avrim Blum · Isabelle Guyon · Ulrike von Luxburg · Robert Williamson · Reza Zadeh 
2009 Poster: MultiLabel Prediction via Compressed Sensing »
Daniel Hsu · Sham M Kakade · John Langford · Tong Zhang 
2009 Oral: MultiLabel Prediction via Compressed Sensing »
Daniel Hsu · Sham M Kakade · John Langford · Tong Zhang 
2008 Poster: Sparse Online Learning via Truncated Gradient »
John Langford · Lihong Li · Tong Zhang 
2008 Spotlight: Sparse Online Learning via Truncated Gradient »
John Langford · Lihong Li · Tong Zhang 
2008 Poster: Influence of graph construction on graphbased clustering measures »
Markus M Maier · Ulrike von Luxburg · Matthias Hein 
2008 Poster: Predictive Indexing for Fast Search »
Sharad Goel · John Langford · Alexander L Strehl 
2008 Oral: Influence of graph construction on graphbased clustering measures »
Markus M Maier · Ulrike von Luxburg · Matthias Hein 
2007 Workshop: Principles of Learning Problem Design »
John Langford · Alina Beygelzimer 
2007 Session: Spotlights »
Ulrike von Luxburg 
2007 Session: Spotlights »
Ulrike von Luxburg 
2007 Spotlight: Consistent Minimization of Clustering Objective Functions »
Ulrike von Luxburg · Sebastien Bubeck · Stefanie S Jegelka · Michael Kaufmann 
2007 Spotlight: PrivacyPreserving Belief Propagation and Sampling »
Michael Kearns · Jinsong Tan · Jennifer Wortman Vaughan 
2007 Poster: PrivacyPreserving Belief Propagation and Sampling »
Michael Kearns · Jinsong Tan · Jennifer Wortman Vaughan 
2007 Poster: Consistent Minimization of Clustering Objective Functions »
Ulrike von Luxburg · Sebastien Bubeck · Stefanie S Jegelka · Michael Kaufmann 
2007 Poster: Learning Bounds for Domain Adaptation »
John Blitzer · Yacov Crammer · Alex Kulesza · Fernando Pereira · Jennifer Wortman Vaughan 
2007 Poster: The EpochGreedy Algorithm for Multiarmed Bandits with Side Information »
John Langford · Tong Zhang 
2006 Poster: Learning from Multiple Sources »
Yacov Crammer · Michael Kearns · Jennifer Wortman Vaughan