costnips 2011 - Workshop on Computational Trade-offs in Statistical Learning

Computational Trade-offs in Statistical Learning

NIPS 2011 Workshop, Sierra Nevada, Spain

https://sites.google.com/site/costnips/

-- Submission Deadline: October 17, 2011 --



OVERVIEW

Since its early days, the field of Machine Learning has focused on
developing computationally tractable algorithms with good learning
guarantees. The vast literature on statistical learning theory has led
to a good understanding of how the predictive performance of different
algorithms improves as a function of the number of training samples.
By the same token, the well-developed theories of optimization and
sampling methods have yielded efficient computational techniques at
the core of most modern learning methods. The separate developments in
these fields mean that given an algorithm we have a sound
understanding of its statistical and computational behavior. However,
there hasn't been much joint study of the computational and
statistical complexities of learning, as a consequence of which,
little is known about the interaction and trade-offs between
statistical accuracy and computational complexity. Indeed a systematic
joint treatment can answer some very interesting questions: what is
the best attainable statistical error given a finite computational
budget? What is the best learning method to use given different
computational constraints and desired statistical yardsticks? Is it
the case that simple methods outperform complex ones in
computationally impoverished scenarios?

The goal of our workshop is to draw the attention of machine learning
researchers to this rich and emerging area of problems and to
establish a community of researchers that are interested in
understanding computational and statistical trade-offs. We aim to
define a number of common problems in this area and to encourage
future research.

TOPICS

We would like to welcome high-quality submissions on topics including
but not limited to:

* Fundamental statistical limits with bounded computation
* Trade-offs between statistical accuracy and computational costs
* Computation-preserving reductions between statistical problems
* Algorithms to learn under budget constraints
* Budget constraints on other resources (e.g. bounded memory)
* Computationally aware approaches such as coarse-to-fine learning

Interesting submissions in other relevant topics not listed above are
welcome too. Due to the time constraints, most accepted submissions
will be presented as poster spotlights.

INVITED SPEAKERS

* Shai Shalev-Shwartz
* Ben Taskar

SUBMISSION GUIDELINES

Submissions should be written as extended abstracts, no longer than 4
pages in the NIPS latex style. NIPS style files and formatting
instructions can be found at
http://nips.cc/PaperInformation/StyleFiles. The submissions should
include the authors' name and affiliation since the review process
will not be double blind. The extended abstract may be accompanied by
an unlimited appendix and other supplementary material, with the
understanding that anything beyond 4 pages may be ignored by the
program committee. The papers can be submitted at
https://sites.google.com/site/costnips/submission by Oct 17, 5PM PST.
Authors will be notified on or before Nov 4.

ORGANIZERS

Alekh Agarwal
Alexander Rakhlin

PROGRAM COMMITTEE

Léon Bottou, Olivier Chapelle , John Duchi, Claudio Gentile, John
Langford, Maxim Raginsky, Pradeep Ravikumar, Ohad Shamir, Karthik
Sridharan, David Weiss