Algorithms Seminar/Fall11
From ResearchWiki
CS 7936: Heuristic algorithm design strategies
Wed 1:25-2:45pm
MEB 3147 (LCR)
Synopsis
You've been there before. After the long and futile attempts at finding an exact algorithm. After the proof of NP-hardness. After the hours spent trying to get a decent approximation, and the realization that the problem is impossible to even approximate in polynomial time. You could just do brute force search, but you might as well give up your identity as a computer scientist. The siren calls of a black box MATLAB library seems so soothing to your ears, but you feel deep down that THERE MUST BE A BETTER WAY.
If this person is you, then this seminar is the cure.
What we will cover are metaheuristics. These are algorithm design strategies that apply in a variety of (usually) optimization problems. While they usually don't have strong guarantees on behavior, they tend to work very effectively in practice. Gradient descent is a simple example, as is simulated annealing, or iterative reweighted least squares. Some heuristics actually do have formal guarantees in specific situations, but are often used outside that realm successfully. Gradient descent is again an example of this, as is alternating optimization.
The goal of the seminar is
- identify when such heuristics might be applicable to a given problem
- understand the formal limits on what these heuristics can and cannot do.
- (If time permits) study some of the associated complexity theory about heuristic search (what classes of problems admit good heuristic strategies, and how are these problems related to each other)
What is expected of you:
- read the prescribed papers
- make at least one full presentation on one of the topics
- participate in class discussions
You can take the seminar for anywhere between 1 and 3 credits: more credits means more presentation.
Participants
- Suresh Venkatasubramanian, Assistant Professor
- Parasaran Raman, PhD Student
- John Moeller, PhD Student
- Shobhit Gupta, Masters Student
- Amirali Abdullah, PhD Student
- Samira Daruki, PhD Student
- Ruihong Huang, PhD Student
Schedule
| Date | Topic | Outline and Paper(s) | Presenter |
|---|---|---|---|
| Aug 24 | Background material: convexity, nonconvexity, convergence, rates of convergence | Suresh Venkatasubramanian | |
| Aug 31 | Smooth local search I: Simple descent | The source material is Chaper 9 of Convex Optimization, and there are slides for that material as well. Topics to be covered include basic setup/defns, descent algorithms including gradient descent and steepest descent, and the associated convergence analysis. We won't talk about self-concordance | Amirali Abdullah |
| Sep 7 | Smooth local search II: Newton's method | Chaper 9 of Convex Optimization, with additional reading from the lecture slides on Nonlinear Optimization (starting at page 45/201) | |
| Sep 14 | Discrete Local Search: approximations for NP-hard problems | Chapter 2 of Williamson/Shmoys (starting at 2.3) | Ruihong |
| Sep 21 | Discrete Local Search: heuristic search strategies | Samira Daruki | |
| Sep 28 | Stochastic Local search: Metropolis-Hastings and friends | ||
| Oct 5 | Complexity theory: PLS | http://www.karlin.mff.cuni.cz/~krajicek/jpy2.pdf | |
| Oct 19 | Coordinate descent methods and alternating optimization: Basics | ||
| Oct 26 | A study of k-means | Parasaran Raman | |
| Nov 2 | Branch and bound | http://euler.nmt.edu/~brian/thesis.pdf (placeholder material) | John Moeller |
| Nov 9 | Multiplicative weight updates: theory | ||
| Nov 16 | Multiplicative weight updates: examples | Parasaran Raman | |
| Nov 23 | |||
| Nov 30 | |||
| Dec 7 |
