[AI Seminar] AI Lunch -- Ellen Vitercik -- September 27th, 2016

Ellen Vitercik vitercik at cs.cmu.edu
Fri Sep 23 17:11:34 EDT 2016

Dear faculty and students,

We look forward to seeing you this Tuesday, September 27th, at noon in NSH
3305 for AI lunch. To learn more about the seminar and lunch, please visit
the AI Lunch webpage <http://www.cs.cmu.edu/~aiseminar/>.

On Tuesday, I (Ellen Vitercik <http://www.cs.cmu.edu/~eviterci/>) will give
a talk titled "Foundations of application-specific algorithm selection."

*Abstract:* In many scientific domains, the underlying computational
problems are frequently NP-hard, but a wealth of algorithms exist which
efficiently find approximate solutions. These algorithms are often defined
by a number of tunable parameters, which introduce an infinite spectrum of
algorithm options. Which algorithm and choice of parameters will lead to
the best performance for the specific application at hand? One could
compare the worst-case performance of the algorithms in question and choose
the algorithm with the best worst-case performance. However, worst-case
instances may not occur in practice, which means that this technique will
not offer guidance specific to the application at hand. This problem, often
referred to as application-specific algorithm selection, has received
significant attention from an empirical perspective over the past several
decades, but it is not yet structured on a firm theoretical foundation. In
this work, we develop learning algorithms for application-specific
algorithm selection with robust guarantees. We focus on two large families
of algorithms, the first of which is an infinite set of clustering
algorithms based on hierarchical clustering followed by dynamic
programming. The second family we analyze is a rich parameterized class of
integer quadratic programming approximation algorithms based on SDP
rounding. We work within a widely applicable framework wherein the learning
algorithm is given samples from an application-specific distribution over
problem instances and learns an algorithm that performs well over the
distribution. We provide strong sample complexity guarantees and efficient
algorithms which optimize the parameters to best suit typical inputs from a
particular application.

This is joint work with Nina Balcan, Vaishnavh Nagarajan, and Colin White.

Ellen and Ariel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.srv.cs.cmu.edu/pipermail/ai-seminar-announce/attachments/20160923/2b295951/attachment.html>

More information about the ai-seminar-announce mailing list