Algorithms Seminar/Fall11

From ResearchWiki

(Difference between revisions)
Jump to: navigation, search
(→Schedule)
(→Schedule)
 
(7 intermediate revisions not shown)
Line 59: Line 59:
| Oct 5 || A case study in coordinate descent: Frank-Wolfe optimization || [http://www.almaden.ibm.com/u/kclarkson/sga/p.pdf Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm] - there's more at [http://www.almaden.ibm.com/u/kclarkson/pubs.html Ken Clarkson's webpage]. [http://cseweb.ucsd.edu/~djhsu/notes/fw.pdf Good notes on Clarkson's paper] by Daniel Hsu || Suresh Venkat
| Oct 5 || A case study in coordinate descent: Frank-Wolfe optimization || [http://www.almaden.ibm.com/u/kclarkson/sga/p.pdf Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm] - there's more at [http://www.almaden.ibm.com/u/kclarkson/pubs.html Ken Clarkson's webpage]. [http://cseweb.ucsd.edu/~djhsu/notes/fw.pdf Good notes on Clarkson's paper] by Daniel Hsu || Suresh Venkat
|-
|-
-
| Oct 19 || Alternating Optimization: <math>k</math>-means, ICP and others || [http://cseweb.ucsd.edu/~dasgupta/291/lec2.pdf What is <math>k</math>-means?], <math>k</math>-means convergence [http://webdocs.cs.ualberta.ca/~nray1/CMPUT466_551/kmeans_convergence.pdf 1] and [http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04767478 2]. [http://www.cs.duke.edu/courses/spring07/cps296.2/scribe_notes/lecture24.pdf What is ICP?], [http://www.cs.princeton.edu/~smr/papers/fasticp/fasticp_paper.pdf Fast ICP] || Parasaran Raman
+
| Oct 19 || Alternating Optimization: <math>k</math>-means, ICP and others || [http://geomblog.blogspot.com/2008/01/important-heuristics-alternating.html What is alternating optimization]. [http://cseweb.ucsd.edu/~dasgupta/291/lec2.pdf What is <math>k</math>-means?], <math>k</math>-means convergence [http://webdocs.cs.ualberta.ca/~nray1/CMPUT466_551/kmeans_convergence.pdf 1] and [http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04767478 2]. [http://www.cs.duke.edu/courses/spring07/cps296.2/scribe_notes/lecture24.pdf What is ICP?], [http://www.cs.princeton.edu/~smr/papers/fasticp/fasticp_paper.pdf Fast ICP] || Parasaran Raman
|-
|-
-
| Oct 26 || Matching, Basis and Projection Pursuit|| [http://www.math.tamu.edu/~popov/Learning/Cohen.pdf A good comparison of matching pursuit and basis pursuit], [http://www.stat.rutgers.edu/home/rebecka/Stat687/huber.pdf an overview of projection pursuit]. Source material: [http://math.unipa.it/~tegolo/MTDS/Art9_Projection%20Pursuit.pdf The Friedman and Tukey projection pursuit paper] ||  
+
| Oct 26 || Matching, Basis and Projection Pursuit|| [http://www.math.tamu.edu/~popov/Learning/Cohen.pdf A good comparison of matching pursuit and basis pursuit], [http://www.stat.rutgers.edu/home/rebecka/Stat687/huber.pdf an overview of projection pursuit]. Source material: [http://math.unipa.it/~tegolo/MTDS/Art9_Projection%20Pursuit.pdf The Friedman and Tukey projection pursuit paper], [http://dx.doi.org/10.1109/78.258082 the Mallat and Zhang matching pursuit paper], and [http://www.stanford.edu/group/SOL/papers/BasisPursuit-SIGEST.pdf the Chen et al basis pursuit paper] || Samira Daruki
|-
|-
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Learning from experts'''  
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Learning from experts'''  
Line 67: Line 67:
| Nov 2 || Multiplicative weight updates: theory|| [http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf Survey by Arora, Hazan and Kale]|| Shobhit Gupta
| Nov 2 || Multiplicative weight updates: theory|| [http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf Survey by Arora, Hazan and Kale]|| Shobhit Gupta
|-
|-
-
| Nov 9 || Multiplicative weight updates: examples || [http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf Survey by Arora, Hazan and Kale] || Parasaran Raman
+
| Nov 9 || Multiplicative weight updates: examples || [http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf Survey by Arora, Hazan and Kale] || Shobhit Gupta
|-
|-
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Miscellaneous'''  
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Miscellaneous'''  
Line 73: Line 73:
| Nov 16 || Branch and bound|| Best reference is [http://www.amazon.com/Integer-Combinatorial-Optimization-Laurence-Wolsey/dp/0471359432 chapter II.4.2 of Nemhauser and Wolsey].  See also [http://euler.nmt.edu/~brian/thesis.pdf Brian Borcher's thesis] and a [http://www.springer.com/cda/content/document/cda_downloaddocument/9783642165320-c1.pdf nice review of branching methods for exact solutions]|| John Moeller
| Nov 16 || Branch and bound|| Best reference is [http://www.amazon.com/Integer-Combinatorial-Optimization-Laurence-Wolsey/dp/0471359432 chapter II.4.2 of Nemhauser and Wolsey].  See also [http://euler.nmt.edu/~brian/thesis.pdf Brian Borcher's thesis] and a [http://www.springer.com/cda/content/document/cda_downloaddocument/9783642165320-c1.pdf nice review of branching methods for exact solutions]|| John Moeller
|-
|-
-
| Nov 23 ||Iteratively reweighted least squares|| the basic method and applications to computing Fermat-Weber points as well as [http://www.ricam.oeaw.ac.at/people/page/fornasier/DDFG14.pdf $\ell_1$-minimization] || Shobhit Gupta
+
| Nov 23 ||Iteratively reweighted least squares|| the basic method and applications to computing Fermat-Weber points as well as [http://www.ricam.oeaw.ac.at/people/page/fornasier/DDFG14.pdf $\ell_1$-minimization] || Parasaran Raman
|-  
|-  
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Complexity Theory'''  
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Complexity Theory'''  
|-
|-
-
| Nov 30 || Complexity theory: PLS|| [http://www.karlin.mff.cuni.cz/~krajicek/jpy2.pdf the original paper], and [http://www2.research.att.com/~dsj/columns/col26.pdf David Johnson's review article]|| Amirali Abdullah
+
| Nov 30 || Complexity theory: PLS|| [http://www.karlin.mff.cuni.cz/~krajicek/jpy2.pdf the original paper], and [http://www2.research.att.com/~dsj/columns/col26.pdf David Johnson's review article]. [http://theory.stanford.edu/~megiddo/pdf/papadimX.pdf Meggido and Papdimitriou's paper on TFNP]|| Amirali Abdullah
|-
|-
-
| Dec 7 || Complexity theory: PPAD|| [http://www2.research.att.com/~dsj/columns/col26.pdf David Johnson's review article] ||
+
| Dec 7 || Complexity theory: PPAD|| [http://www2.research.att.com/~dsj/columns/col26.pdf David Johnson's review article], [http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf Papadimitriou's original paper] and a [http://www.math.uchicago.edu/~amwright/BFPT.pdf helpful explanation of Sperner's Lemma and Brouwer's theorem]. ||
|}
|}
 +
 +
==Topics Not Covered ==
 +
* [http://en.wikipedia.org/wiki/Beam_search Beam search]
 +
* Conjugate gradient search
 +
* Levenberg-Marquandt and other nonlinear optimization methods.

Latest revision as of 03:20, 8 December 2011

CS 7936: Heuristic algorithm design strategies

Wed 1:25-2:45pm

MEB 3147 (LCR)

Contents

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

Schedule

Date Topic Outline and Paper(s) Presenter
Smooth methods
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) John Moeller
Discrete Local Search: Basics
Sep 14 Discrete Local Search: approximations for NP-hard problems Chapter 2 of Williamson/Shmoys (starting at 2.3). Specifically, scheduling, TSP and min-degree spanning trees. Another nice example of local search that gives a guarantee is the 5-approximation for the k-median by Arya et al. Since the link appears to be down occasionally, here's an explanation of the algorithm. Ruihong
Sep 21 Discrete Local Search: heuristic search strategies Theoretical aspects of local search. Chapters 1.1, and 7 (neighborhood functions, basics of the neighborhood graph and connectivity, local improvement methods, tabu search and simulated annealing) Samira Daruki
Coordinate Descent methods
Sep 28 Coordinate descent methods: Basics the basic framework, and applications to alternating optimization, matching pursuit and projection pursuit. Original work on the convergence of cyclic coordinate descent, and a nice modern work analyzing the behavior of cyclic methods. Ruihong
Oct 5 A case study in coordinate descent: Frank-Wolfe optimization Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm - there's more at Ken Clarkson's webpage. Good notes on Clarkson's paper by Daniel Hsu Suresh Venkat
Oct 19 Alternating Optimization: k-means, ICP and others What is alternating optimization. What is k-means?, k-means convergence 1 and 2. What is ICP?, Fast ICP Parasaran Raman
Oct 26 Matching, Basis and Projection Pursuit A good comparison of matching pursuit and basis pursuit, an overview of projection pursuit. Source material: The Friedman and Tukey projection pursuit paper, the Mallat and Zhang matching pursuit paper, and the Chen et al basis pursuit paper Samira Daruki
Learning from experts
Nov 2 Multiplicative weight updates: theory Survey by Arora, Hazan and Kale Shobhit Gupta
Nov 9 Multiplicative weight updates: examples Survey by Arora, Hazan and Kale Shobhit Gupta
Miscellaneous
Nov 16 Branch and bound Best reference is chapter II.4.2 of Nemhauser and Wolsey. See also Brian Borcher's thesis and a nice review of branching methods for exact solutions John Moeller
Nov 23 Iteratively reweighted least squares the basic method and applications to computing Fermat-Weber points as well as $\ell_1$-minimization Parasaran Raman
Complexity Theory
Nov 30 Complexity theory: PLS the original paper, and David Johnson's review article. Meggido and Papdimitriou's paper on TFNP Amirali Abdullah
Dec 7 Complexity theory: PPAD David Johnson's review article, Papadimitriou's original paper and a helpful explanation of Sperner's Lemma and Brouwer's theorem.

Topics Not Covered

  • Beam search
  • Conjugate gradient search
  • Levenberg-Marquandt and other nonlinear optimization methods.
Retrieved from "http://www.cs.utah.edu/~suresh/mediawiki/index.php/Algorithms_Seminar/Fall11"
Personal tools