Algorithms Seminar/Fall11

From ResearchWiki

You do not have permission to edit this page, for the following reason:

You can view and copy the source of this page:

'''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== * [http://www.cs.utah.edu/~suresh Suresh Venkatasubramanian], Assistant Professor * [http://www.cs.utah.edu/~praman Parasaran Raman], PhD Student * [http://www.cs.utah.edu/~moeller/ John Moeller], PhD Student * Shobhit Gupta, Masters Student * Amirali Abdullah, PhD Student * Samira Daruki, PhD Student * [http://www.cs.utah.edu/~huangrh Ruihong Huang], PhD Student ==Schedule== {| border="1" style="width: 100%; text-align:left" class="content" |- ! Date || Topic || Outline and Paper(s) || Presenter |- | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''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 [http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Chaper 9 of Convex Optimization], and there are [http://www.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf 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|| [http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Chaper 9 of Convex Optimization], with additional reading from the [http://www.athenasc.com/NLP_Slides.pdf lecture slides on Nonlinear Optimization] (starting at page 45/201) || John Moeller |- | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Discrete Local Search: Basics''' |- | Sep 14 || Discrete Local Search: approximations for NP-hard problems || [http://www.designofapproxalgs.com/book.pdf 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 [http://www.cse.iitd.ernet.in/~pandit/lsearchSICOMP.pdf 5-approximation for the k-median] by Arya et al. Since the link appears to be down occasionally, [http://www-bcf.usc.edu/~dkempe/CS599/0427-0429.pdf here's an explanation of the algorithm].|| Ruihong |- | Sep 21 || Discrete Local Search: heuristic search strategies || [http://www.springerlink.com/content/978-3-540-35853-4/#section=286373&page=1 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 |- | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Coordinate Descent methods''' |- | Sep 28 || Coordinate descent methods: Basics || the basic framework, and applications to alternating optimization, matching pursuit and projection pursuit. [http://dspace.mit.edu/bitstream/handle/1721.1/3164/P-1924-21454764.pdf?sequence=1 Original work on the convergence of cyclic coordinate descent], and [http://arxiv.org/PS_cache/arxiv/pdf/1005/1005.2146v1.pdf a nice modern work] analyzing the behavior of cyclic methods. || Ruihong |- | 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://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], [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''' |- | 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] || Shobhit Gupta |- | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Miscellaneous''' |- | 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] || Parasaran Raman |- | 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]. [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], [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.

Return to Algorithms Seminar/Fall11.