The Empirical Algorithmics Reading Group (EARG)

                  

Held weekly on Wednesday at 13:30 in room X530 (seminar room by the beta lab)

We have weekly research meetings of people working on automated algorithm design/configuration/selection right after the talk. In some weeks, we don't have a talk but only the research meeting.


This reading group focuses on empirical aspects of computer science. Every computer science student takes a lot of math and theory courses, but typically not even a single course about the design of meaningful experiments and the analysis of their results. In this group, we discuss research papers with a focus on empirical issues; the papers typically concern solving hard computational problems (SAT, TSP, scheduling, etc) and computer aided algorithm design.

Since this is a joint BETA/LCI reading group we often discuss AI papers, but we are open to other areas and also have a theoretician amongst us. Our meeting format is presentations with lots of audience interaction, so you can come without having read the paper (though you may get more out of it if you read it).

If you are planning to attend our meetings, you should sign up to the mailing list (ea-rg), where the papers and schedules will be announced: just send an email to majordomo@cs.ubc.ca with the command "subscribe ea-rg" in the body of your message.


Upcoming presentations

Date Time Presenter General Topic

Paper / Title

April 2, 2014 13:30 - 14:30 Steve Ramage TBD TBD

Previous presentations

Date Time Presenter General Topic

Paper / Title

March 26, 2014 14:30 - 15:30 Alex Fréchette Bandits Continued:
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba Szepesvári
X-Armed Bandits (continued)
March 5, 2014 13:00 - 14:00 Alex Fréchette Bandits Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba Szepesvári
X-Armed Bandits
February 12, 2014 13:00 - 14:00 Sam Bayless SAT instance generation Sam Bayless, Dave A.D. Tompkins, Holger H. Hoos
Evaluating Instance Generators by Configuration
January 29, 2014 13:00 - 14:00 Chris Fawcett Parallel SAT Alejandro Arbelaez, Charlotte Truchet, Philippe Codognet
Using sequential runtime distributions for the parallel speedup prediction of SAT local search
November 6, 2013 13:00-14:00 Manuel López-Ibáñez Grammar-based algorithm design From grammars to parameters: How to use irace to design algorithms from a grammar description
October 29, 2013 15:45-16:45 Chris Thornton MSc. thesis presentation Auto-WEKA: Combined Selection and Hyperparameter Optimization of Supervised Machine Learning Algorithms
October 9, 2013 12:30-13:30 Sam Bayless SAT Sam Bayless, Celina G. Val, Thomas Bally, Holger H. Hoos, and Alan J. Hu
Efficient Modular SAT Solving for IC3
September 11, 2013 12:30-13:30 Sam Bayless Parallel SAT Martin Aigner, Armin Biere, Christoph M. Kirsch, Aina Niemetz, and Mathias Preiner
Analysis of Portfolio-Style Parallel SAT Solving on Current Multi-Core Architectures.
July 22, 2013 12:00-13:00 Steve Ramage ACLib An introduction to ACLib
June 5, 2013 12:30-13:30 Steve Ramage Algorithm configuration Aldy Gunawan, Hoong Chuin Lau, Lindawati
Fine-Tuning Algorithm Parameters Using the Design of Experiments Approach.
April 3, 2013 12:30-13:30 Chris Fawcett Algorithm Parameter Importance Informal presentation of Ablation Analysis paper submitted to MIC 2013
March 13, 2013 12:30-13:30 Frank Hutter Algorithm Parameter Importance Last presentation before leaving UBC, covering functional ANOVA for parameter importance
February 27, 2013 12:30-13:30 Sam Bayless Incremental SAT Solving
February 21, 2013 12:30-13:30 Alex Fréchette Algorithm portfolios Mladen Nikolić, Filip Marić, and Predrag Janičić
Simple algorithm portfolio for SAT.
February 6, 2013 12:30-13:30 Chris Thornton Hyperparameter optimization Jasper Snoek, Hugo Larochelle, and Ryan P. Adams
Practical Bayesian Optimization of Machine Learning Algorithms.
December 5, 2012 12:30-13:30 Quinn Hsu HAL The future of scripting support in HAL
November 28, 2012 12:30-13:30 Lin Xu Empirical analysis Simon F. Goldsmith, Alex S. Aiken, and Daniel S. Wilkerson
Measuring Empirical Computational Complexity.
November 21, 2012 12:30-13:30 Chris Thornton Matching Laurent Charlin, Richard S. Zemel, Craig Boutilier
A Framework for Optimizing Paper Matching.
November 14, 2012 12:30-13:30 Chris Fawcett Algorithm portfolios Jendrik Seipp, Manuel Braun, Johannes Garimort, and Malte Helmert
ICAPS 2012: Learning Portfolios of Automatically Tuned Planners.
November 7, 2012 12:30-13:30 Alex Fréchette Algorithm portfolios Holger Hoos, Kevin Leyton-Brown, Torsten Schaub, and Marius Schneider
CoCoMile 2012: Algorithm ConīŦguration for Portfolio-based Parallel SAT-Solving.
October 24, 2012 12:30-13:30 Sam Bayless SAT solving Laurent Simon and Gilles Audemard
IJCAI-09: Predicting Learnt Clauses Quality in Modern SAT Solvers.
October 3, 2012 12:30-13:30 Lin Xu Algorithm selection Serdar Kadioglu, Yuri Malitsky, and Meinolf Sellmann.
AAAI-12: Non-Model-Based Search Guidance for Set Partitioning Problems.
September 26, 2012 12:30-13:30 Alexandre Fréchette Robust network design Presentation of M.Sc. work.
September 19, 2012 12:30-13:30 Nick Harvey Submodularity Submodular Functions: Learnability, Structure, and Optimization
August 22, 2012 12:30-13:30 Torsten Schaub Answer-set programming Martin Gebser, Benjamin Kaufmann, and Torsten Schaub.
Multi-threaded ASP Solving with clasp
August 15, 2012 12:30-13:30 Lin Xu Algorithm selection; Portfolio construction Practice talk: MIP and evaluating candidate solvers
August 8, 2012 12:30-13:30 Lin Xu SAT solving Shaowei Cai and Kaile Su.
AAAI-12: Configuration Checking with Aspiration in Local Search for SAT.
August 1, 2012 12:30-13:30 Sam Bayless Delta-debugging Model-based delta debugging
July 25, 2012 12:30-13:30 Quinn Hsu HAL Demo of the 1.1.0 release candidate
July 11, 2012 12:30-13:30 Frank Hutter Bias/variance tradeoffs Trevor Hastie, Robert Tibshirani, Jerome Friedman.
The Elements of Statistical Learning: Data Mining, Inference, and Prediction.
Chapter 7, continued.
June 20, 2012 12:30-13:30 Frank Hutter Bias/variance tradeoffs Trevor Hastie, Robert Tibshirani, Jerome Friedman.
The Elements of Statistical Learning: Data Mining, Inference, and Prediction.
Chapter 7.
May 16, 2012 12:30-13:30 Chris Thornton Hyper-parameter optimization James Bergstra, Rémi Bardenet, Yoshua Bengio, Balázs Kégl.
NIPS-11: Algorithms for Hyper-Parameter Optimization.
April 25, 2012 12:30-13:30 Lin Xu Algorithm selection Continuation of 3S.
April 11, 2012 12:30-13:30 Lin Xu Algorithm Selection Informal discussion about 3S
March 28, 2012 12:30-13:30 Chris Fawcett Empirical distributions Sampling from multivariate empirical distributions
March 21, 2012 12:30-13:30 Chris Thornton Hyper-parameter optimization James Bergstra and Yoshua Bengio.
JMLR: Random Search for Hyper-Parameter Optimization.
March 14, 2012 12:30-13:30 Roman from Westgrid Cluster allocation and scheduling issues
Feb 29, 2012 12:30-13:30 Sam SAT submission #2
Feb 22, 2012 12:30-13:30 Chris F
Feb 15, 2012 12:30-13:30 Everyone Adding papers and topics to the queue.
Feb 8, 2012 12:30-13:30 Chris T
Feb 1, 2012 12:30-13:30 Lin Runtime prediction Ling Huang, Jinzhu Jia, Bin Yu, Byung-Gon Chun, Petros Maniatis, Mayur Naik.
NIPS 2010: Predicting Execution Time of Computer Programs Using Sparse Polynomial Regression
Jan 11, 2012 12:30-13:30 James Algorithm configuration James Styles, Holger Hoos, Martin Mueller.
LION 2012: Automatically Configuring Algorithms for Scaling Performance
Jan 4, 2012 12:30-13:30 Martin Brain Automated Music Composition Title : Computational Music Theory

Abstract : Most automated composition systems use machine learning
techniques to produce a pastiche of their training set.  This talk
presents Anton, an automatic composition system that uses an alternative
approach.  Knowledge representation technology is used to express music
theory in a declarative logic programming language.  Techniques similar
to constraint and SAT solving can be used to compose novel pieces of
melodic, harmonic and rhythmic music in the modelled style.  No prior
knowledge of music, music theory or answer set programming is be
required and there will be demos and music.

About the speaker : Martin Brain is a post-doc researcher working
jointly with University of Bath and Altran-Praxis Limited. Current
projects include developing an algebra of search spaces, building
program verification tools and trying to untangle the mess that is
floating point reasoning.  More at http://www.cs.bath.ac.uk/~mjb/
Nov 30, 2011 14:00-15:00 James P, NP, etc Russel Impagliazzo: "A Personal View of Average-Case Complexity"
(http://portal.acm.org/citation.cfm?id=829786,
http://cseweb.ucsd.edu/~russell/average.ps)
Nov 23, 2011 14:00-15:00 Chris T Robot soccer software Using genetic algorithms to optimize robot soccer players.
Nov 16, 2011 14:00-15:00 Chris F Scheduling Solving real-world scheduling problems, both for UBC exams and
NSERC reviews
Nov 2, 2011 14:00-15:00 Sam Formal verification A tutorial on SAT-based formal verification
Oct 19, 2011 14:00-15:00 Lin Algorithm portfolios Work in progress on experiments with model-free portfolios
Oct 10, 2011 14:00-15:00 James Algorithm configuration Work in progress for LION
Oct 3, 2011 14:00-15:00 Chris N HAL MSc thesis presentation
Sept 29, 2011 14:00-15:00 Kevin LB Algorithm configuration & selection Review of "Beyond Worst Case Complexity" Workshop
Sept 21, 2011 14:00-15:00 Rui Summary of summer project
Sept 1, 2011 14:00-15:00 Maverick/Jonathan/Rui Summary of summer projects
August 24, 2011 11:00-13:00 Lin Visualization of configuration spaces From Satenstein journal paper
June 23 & 30, 2011 14:00-15:00 Sam Delta debugging
June 16, 2011 14:00-15:00 James Parameter tuning Parameter tuning by simple regret algorithms and multiple simultaneous hypothesis testing
Amine Bourki, Matthieu Coulm, Philippe Rolet, Olivier Teytaud, Paul Vayssiere, ININCO 2010.
June 9, 2011 14:00-15:00 Dave SLS for SAT SAT practice talk
June 7, 2011 14:00-15:30 Chris F Automated Configuration of Planners 2 ICAPS workshop practice talks
March 30, 2011 13:30-14:30 Chris F Parallel SAT solving Improving Parallel Local Search for SAT
Alejandro Arbelaez and Youssef Hamadi, LION 2011.
March 23, 2011 13:30-14:30 Sam Systematic SAT Solvers Watched literals and Sam's work on improving them
March 16, 2011 13:30-14:30 Lin Per-Instance Algorithm Configuration Instance-Based Selection of Policies for SAT Solvers.
Mladen Nikolic, Filip Maric and Predrag Janicic. SAT 2009.
March 3, 2011 10:30-11:30 Maverick Algorithm Configuration Update on the implementation of SMAC in HAL
February 24, 2011 10:30-11:30 Marius Schneider Algorithm Configuration for ASP and for Parallel Solvers Update on the work done in Potsdam
February 10, 2011 10:30-11:30 Dave T Random Instance Generation for SAT Towards Industrial-Like Random SAT Instances.
Carlos Ansotegui, Jordi Levy, and Maria Luisa Bonet. IJCAI-09.
February 3, 2011 10:30-11:30 James GPU computing, Performance tuning Automatic Tuning Matrix Multiplication Performance on Graphics Hardware
Changhao Jiang and Marc Snir.
Technical Report UIUC DCS-R-2005-2558
Department of Computer Science, UIUC
Jan 13, 2011 1pm-3pm Chris N.
Frank
Metaalgorithmics 
Algorithm configuration
Practice talks for LION-5:

HAL: A Framework for the Automated Analysis and Design of High-Performance Algorithms.
Christopher Nell, Chris Fawcett, Holger H. Hoos, and Kevin Leyton-Brown.

Sequential Model-Based Optimization for General Algorithm Configuration.
Frank Hutter, Holger Hoos, and Kevin Leyton-Brown.
Dec 23, 2010 1pm-2pm Chris N Metaalgorithmics Practice talk for LION: HAL: A Framework for the Automated Analysis and Design of High-Performance Algorithms.
Christopher Nell, Chris Fawcett, Holger H. Hoos, and Kevin Leyton-Brown
Nov 24, 2010 1pm-2pm Chris F. Timetabling Chris's work on UBC's exam scheduling. Slides
Nov 2, 2010 1pm-2pm Chris N Metaalgorithmics Experiment design and administration for computer clusters for SAT-solvers (EDACC) - System description
Adrian Balint, Daniel Gall, Gregor Kapler, and Robert Retz
Journal on Satisfiability, Boolean Modeling and Computation 7 (2010) 77–82.
Sept 8, 2010 1pm-2pm Lin Algorithm selection + configuration ISAC - Instance Specific Algorithm Configuration. Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann, Kevin Tierney. ECAI '10: Proceedings of the 19th European Conference on Artificial Intelligence (2010)
Aug 10, 2010 4:15-5:15pm Mike Osborne Gaussian Processes Gaussian Processes for Sequential Prediction, Optimisation and Quadrature
July 21 (Wed!), 2010 4:15-5:15pm Alvaro Fialho Dynamic Bandits
June 29, 2010 4:15-5:15pm Frank Algorithm Configuration "Automated Tuning of Optimization Software Parameters" (2007 Tech Report, see http://www.optimization-online.org/DB_FILE/2007/10/1819.pdf)
and
"How much do we pay for using default parameters? (2009 paper in the Journal of Computational Optimization and Applications, see http://www.springerlink.com/content/l287ht480k459n34/ )
June 8, 2010 4:15-5:15pm Frank Algorithm Configuration Automated Configuration of Mixed Integer Programming Solvers
Frank Hutter, Holger H. Hoos and Kevin Leyton-Brown. Accepted at CP-AI-OR-10.
Practice talk for CP-AI-OR.
May 25, 2010 4:15-5:15pm Kevin LB Empirical research in game theory -
May 18, 2010 4:15-5:15pm Lin Algorithm selection + configuration Hydra: Automatically Configuring Algorithms for Portfolio-Based Selection
Lin Xu, Holger Hoos, and Kevin Leyton-Brown. To appear in AAAI-10.
Mar 16, 2010 4:15-5:15pm Dave SAT Dynamic Scoring Functions with Variable Expressions: New SLS Methods for Solving SAT
Dave Tompkins and Holger H. Hoos. Accepted to SAT-10.
Mar 9, 2010 4:15-5:15pm Frank Parameter Tuning Tuning Local Search by Average-Reward Reinforcement Learning.
Steven Prestwich. LION 2 (2008)
Feb 9, 2010 3:45-4:45pm Fahiem Bacchus SAT Preprocessing SAT instances with hyper-binary resolution

Presentations 2009

Date Time Presenter General Topic

Paper / Title

Jan 20, 2009 12:30-2pm Ashique Automated algorithm configuration Ashique's MSc thesis presentation
Feb 3, 2009 12:30-2pm Chris Automated algorithm configuration Bryan A. Tolson and Christine A. Shoemaker
Dynamically dimensioned search algorithm for computationally efficient watershed model calibration
Water Resources Research, 2005
Mar 3, 2009 12:30-2pm Dave Thompson Empirical Algorithmics in Game Theory David Robert Martin Thompson and Kevin Leyton-Brown
Computational Analysis of Perfect-Information Position Auctions
Submitted to the 10th ACM Conference on Electronic Commerce
Mar 10, 2009 12:30-2pm Dave Thompson Empirical Algorithmics in Game Theory Dave's presentation continued
Mar 24, 2009 12:30-2pm Lin Empirical Hardness Models Eric A. Brewer
High-Level Optimization via Automated Statistical Modeling
Principles and Practice of Parallel Programming, 1995
Apr 6, 2009 12:30-2pm Lin Empirical Hardness Models Lin's presentation continued
May 5, 2009 12:30-2pm Lin Feature selection Material from various sources
June 2, 2009 12:30-2pm Chris F Algorithm synthesis Jean-Noel Monette, Yves Deville, and Pascal Van Hentenryck
AEON: Synthesizing Scheduling Algorithms from High-Level Models
Operations Research and Cyber-Infrastructure
Summer 2009 - - Research Informal meetings to discuss various research topics
Sept 16, 2009 1:30-2:30pm Frank Algorithm configuration PhD thesis defence practice talk.
Thesis defence: 12:30pm on Friday, Sept 18, room 200, Graduate Student Centre.
Sept 23, 2009 1:30-2:30pm Massih Khorvash Maximum Cliques MSc thesis defence. Thesis title: On uniform sampling of maximum cliques.
Oct 7, 2009 1:30-2:30pm Chris F Algorithm synthesis Arne Lokketangen and Roland Olsson
Generating Meta-Heuristic Optimization Code using ADATE
(paper under review at Journal of Heuristics; no, Chris is not the reviewer, he got a preprint at SLS 2009)
Oct 14, 2009 1:30-2:30pm Fahiem Bacchus Constraint Optimization, Branch and Bound Solving Constraint Optimization Problems with Branch and Bound
Oct 28, 2009 11:30-2:30pm Fahiem Bacchus Constraint Optimization, Branch and Bound Solving Constraint Optimization Problems with Branch and Bound
Nov 25, 2009 1:30-2:30pm Chris N Learning Heuristics
Learning Heuristics for the Superblock Instruction Scheduling Problem
T. Russell, A.M. Malik, M. Chase, and P. van Beek.
IEEE Transactions on Knowledge and Data Engineering, 21 (10). p.1489-1502 (Oct. 2009)
http://ai.uwaterloo.ca/~vanbeek/Publications/tkde09.pdf

Previous presentations 2008

Date Time Presenter General Topic

Paper / Title

January 30, 2008 12:00-1:30pm Lin Statistics
Statistical analysis of experiments. Not based on a paper. 
February 13, 2008 12:00-1:30pm Lin Statistics Continued: statistical analysis of experiments. Not based on a paper.
February 20, 2008 -- -- Reading week --
February 27, 2008 12:00-1:30pm Frank
Automated parameter tuning
Parameter tuning using response surfaces. No paper, discussion of ongoing work. Slides
March 5, 2008 12:00-1:30pm Frank Automated parameter tuning Continued: parameter tuning using response surfaces. No paper, discussion of ongoing work. Updated slides
March 12, 2008 12:00-1:30pm Chris
Scheduling Competition A Modular Multiphase Heuristic Solver for Post Enrolment Course Timetabling
Marco Chiarandini, Chris Fawcett, Holger H. Hoos
A Competition Retrospective.
Slides
March 26, 2008 12:00-1:30pm Erik Empirical algorithmics course presentation Simple Search Methods For Finding A Nash Equilibrium by Porter, Nudelman and Shoham (http://robotics.stanford.edu/~eugnud/papers/computing-nash-journal.pdf)
April 2, 2008 12:00-1:30pm Chris & Zoreh Empirical algorithmics course presentations Chris: Panagopoulou, P. N. and Spirakis, P. G. 2007. Algorithms for pure Nash equilibria in weighted congestion games. J. Exp. Algorithmics 11  (Feb. 2007), 2.7. (http://www.cs.ubc.ca/~hutter/earg/papers08/p1-panagopoulou.pdf)
Slides
Zoreh: W. Spears, V. Anand, A Study of Crossover Operators in Genetic  Programming, Proceedings of the 6th International Symposium on  Methodologies for Intelligent Systems.(http://citeseer.ist.psu.edu/82031.html)
Slides
April 9, 2008 12:00-1:30pm Ashique & Xiaofei Empirical algorithmics course presentations Ashique: C. M. Li, W. Wei, and H. Zhang. Combining Adaptive Noise and Look-Ahead in Local Search for SAT. In Proceedings of LSCS-2006, pages 2–16, 2006. (http://www.springerlink.com/index/l60287431756851m.pdf)
Slides
Xiaofei: Ozun, Alper and Cifter, Atilla (2007): Nonlinear Combination of Financial Forecast with Genetic Algorithm.
MPRA Paper 2488, University Library of Munich, Germany. (http://mpra.ub.uni-muenchen.de/2488/
April 23, 2008 12:00-1:30pm Dave Local search for SAT Advances in Local Search for Satisfiability
Duc Nghia Pham, John Thornton, Charles Gretton, and Abdul Sattar
May 7, 2008 12:00-1:30pm Xiaofei Empirical algorithmics course presentation K. Jamieson, H. Balakrishnan, "PPR: Partial Packet Recovery for
Wireless Networks", SIGCOMM 2007.
(http://nms.lcs.mit.edu/papers/fp315-jamieson.pdf)
June 11, 2008 12:00-1:30pm Frank Online parameter tuning Online Estimation of SAT Solving Runtime
by Shai Haim and Toby Walsh,
SAT 2008 
July 2, 2008 12:00-1:30pm Ashique Bandits for parameter tuning Adaptive Operator Selection with Dynamic Multi-Armed Bandits
Luis DaCosta, Álvaro Fialho, Marc Schoenauer, Michèle Sebag
GECCO 2008
July 16, 2008 12:00-1:30pm Lin Backdoors Backdoors To Typical Case Complexity
Ryan Williams, Carla P. Gomes, Bart Selman
IJCAI-03
August 13, 2008 12-1:30pm Chris (practice talk) Timetabling Marco Chiarandini, Chris Fawcett, and Holger H. Hoos.
A Modular Multiphase Heuristic Solver for Post Enrolment Course Timetabling
In PATAT 2008
Oct 3, 2008 11-12:30 Frank Automated Parameter Tuning J. Gratch and S. Chien
Adaptive Problem-solving for Large-scale Scheduling Problems: A Case Study
JAIR 1996
Slides
Oct 15, 2008 11-12:30 Chris Experimental Methodology Marco Chiarandini, Luis Paquete, Mike Preuss and Enda Ridge
Experiments on Metaheuristics: Methodological Overview and Open Issues
Technical report
Slides
Oct 22, 2008 11-12:30 Dave Experimental Methodology J.N. Hooker
Testing Heuristics: We Have It All Wrong
Journal of Heustics, 1995
Slides
Oct 29, 2008 11-12:30 Lin Algorithm Portfolios, Bandits Matteo Gagliolo and Juergen M. Schmidhuber
Algorithm Selection as a Bandit Problem with Unbounded Losses
Technical report, 2008
Nov 5, 2008 11-12:30 Ashique Statistical Tests Oren Etzioni and Ruth Etzioni
Statistical Methods for Analyzing Speedup Learning Experiments
Journal of Machine Learning, 1994
Nov 12, 2008 11-12:30 Frank Algorithm Portfolios, Bandits Matteo Gagliolo and Juergen M. Schmidhuber
Learning Dynamic Algorithm Portfolios
Technical Report, 2007
Nov 19, 2008 11-12:30 Frank Algorithm Portfolios, Bandits Continued:
Matteo Gagliolo and Juergen M. Schmidhuber
Learning Dynamic Algorithm Portfolios
Technical Report, 2007
Nov 26, 2008 11-12:30 Holger Algorithm configuration Alex Fukunaga
Automated Discovery of Local Search Heuristics for Satisfiability Testing - not available online, come get a copy from me
Evolutionary Computation, 2008
Dec 3, 2008 11-12:30 Evgeny Local Search, Theory Andrei A. Bulatov and Evgeny S. Skvortsov
Phase transition for Local Search on planted SAT

Previous presentations fall 2007

Date Time Presenter General Topic

Paper / Title

Dec 13, 2007 11:30am-1pm Hoyt Clustering Hoyt A. Koepke and Bertrand Clarke.
A Bayesian Approach to Cluster Validation
To appear in the International Symposium on AI & MATH '08.
Nov 30, 2007 11:30am-1pm Ashique Structure in SAT R. Ostrowski, E. Gregoire, B. Mazure and L. Sais.
Recovering and Exploiting Structural Knowledge from CNF Formulas
CP 2002
Nov 23, 2007 11:30am-1pm Firas PhD defense practice talk Sampling-based approaches to inference in undirected graphical models
Nov 16, 2007 11:30am-1pm Guest speaker: 
Alexander Skopalik
Game theory Local search and computing equilibria in congestion games
(research talk)

Abstract:
Congestion games are games where the cost of a player from using a certain resource depends on the total number of players that are using the same resource. In this talk, we present new results on the complexity of computing and approximating  pure Nash equilibria (PNE) in congestion game.
We start by giving an overview over the complexity class PLS that contains many interesting local search problems.  It is known that computing PNE in congestion games is PLS-hard. A natural and convincing notion of approximation for equilibria in congestion games assumes that agents are ambivalent between strategies whose delay differs by less than a factor of $\alpha$, for some $\alpha$  > 1.
In this talk, we show that computing an $\alpha$-approximate equilibrium is PLS-complete. Thus finding an approximate Nash equilibrium is as hard as finding an exact Nash equilibrium or solving any other problem in PLS.
Nov 9, 2007 EARG cancelled due to talk by Avi Pfeffer, Harvard University, 11am-12:30.
Title: Modeling the Reasoning of Agents in Games
Abstract:
Why do agents (people or computers) do things in strategic situations? Answering this question will impact how we build computer systems to assist, represent or interact with people in interactions with other agents such as negotiations and resource allocation.  We identify four reasoning patterns that agents might use: choosing an action for its direct effect on the agent's utility, attempting to manipulate another agent, signalling information to another agent that the first agent knows, or revealing or hiding information from another agent that the first agent itself does not know.  We present criteria that characterize each reasoning pattern as a pattern of paths in a multi-agent influence diagram, a graphical representation of games. We define a class of strategies in which agents do not make unmotivated distinctions, and show that if we assume all agents play these kinds of strategies, our categorization of reasoning patterns is complete and captures all situations in which an agent has reason to make a decision.

We then study how people use two reasoning patterns in a particular negotiation game.  We use machine learning to learn models of people's play, and embed our learned models in computer negotiators.  We find that negotiators that use our learned model outperform classical game-theoretic agents and also outperform people.  Finally, we learn models of the way people's behavior changes in ongoing interactions with the same agent, particularly the degree to which retrospective (rewarding or punishing past behavior) and prospective (attempting to induce future good behavior) reasoning play a role.
Nov 2, 2007 11:30am-1pm Lin No free lunch theorems David H. Wolpert and William G. Macready
No free lunch theorems for optimization
IEEE Transactions on Evolutionary Computation, 1997
Oct 25, 2007 11:30am-1pm Ashique SAT

Lintao Zhang, Sharad Malik

The Quest for Efficient Boolean Satisfiability Solvers
CAV 2002

Oct 18, 2007 Frank Automated parameter tuning

Thomas Bartz–Beielstein and Sandor Markon.
Tuning Search Algorithms for Real-World
Applications: A Regression Tree Based Approach

In Congress on Evolutionary Computation (CEC'04)

Frank's slides

On the stack - please feel free to pick one of these if you are looking for a paper to present. Other papers are of course also welcome.

Date Time Presenter General Topic

Paper / Title

      Global optimization survey

Donald R. Jones
A Taxonomy of Global Optimization Methods Based on Response Surfaces
Journal of Global Optimization 21: 345–383, 2001.

      Global optimization: one approach

Brigham S. Anderson, Andrew W. Moore, and David Cohn.
A Nonparametric Approach to Noisy and Costly Optimization
In Proceedings of the 17th International Conference on Machine Learning, pp. 17-24

      Global optimization: one approach

Mauro Brunato, Roberto Battiti and Srinivas Pasupuleti
A Memory-Based RASH Optimizer
AAAI 2006 Workshop

      Experimental Design: foundations

Merlise A. Clyde
Experimental Design: A Bayesian Perspective
Int. Encyc. Social and Behavioral Sciences 4 April 2001

      Experimental Design: applications

Steven Coy, Bruce L. Golden, George C. Runger, Edward A. Wasil
Using Experimental Design to Find Effective Parameter Settings for Heuristics
Journal of Heuristics, 7: 77–97 (2000)

      Runtime prediction

Philip Kilby, John Slaney, Sylvie Thiebaux, and Toby Walsh
Estimating Search Tree Size
AAAI 06 Workshop on Learning for Search

      Learning of search space structure

Shumeet Baluja and Scott Davies
Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space
In Proceedings of the Fourteenth Int. Conf. on Machine Learning (ICML 1997), pp. 30--38.

      Combining local and global search

Meinolf Sellmann and Carlos Ansotegui
Disco – Novo – GoGo Integrating Local Search and Complete Search with Restarts
AAAI 06 Workshop on Learning for Search

 

Previous discussions spring and summer 2007

Date Time Presenter General Topic

Paper / Title

Aug 30, 2007 12:30-14:00 Lin Portfolios for SAT

Lin Xu, Frank Hutter, Holger Hoos, Kevin Leyton-Brown.

SATzilla-07: The Design and Analysis of an Algorithm Portfolio for SAT

Practice talk for CP

Aug 23, 2007 12:30-14:00 Lin Expectation Maximization for CSPs

Eric I. Hsu and Matthew Kitching and Fahiem Bacchus and Sheila A. McIlraith

Using EM to Find Likely Assignments for Solving CSP's

Aug 8, 2007 12:30-14:00 Hoyt Feature selection

Huan Liu and Lei Yu

Toward Integrating Feature Selection Algorithms for Classification and Clustering

Available online at http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1401889

Aug 1, 2007 12:30-14:00 Erik Statistical evaluation

Eric Sodomka, John Collins, and Maria Gini

Efficient Statistical Methods for Evaluating Trading Agent Performance

AAAI 07

July 10, 2007 12:30-14:00 Erik Machine learning

Thomas G. Dietterich

Machine Learning for Sequential Data: A Review

July 3, 2007 12:30-14:00 Frank Reinforcement learning for SAT

Michail G. Lagoudakis and Michael L. Littman.

Learning to Select Branching Rules in the DPLL Procedure for Satisfiability

June 19, 2007 12:30-14:00 Lin Reinforcement learning

Slides by Ann Nowe based on the book by Sutton and Barto: http://www.cs.ualberta.ca/~sutton/book/ebook/the-book.html

 

 

June 5, 2007 12:30-14:00 Frank Automated parameter tuning

Prasanna Balaprakash, Mauro Birattari, and Thomas Stuetzle

Improvement Strategies for the F-Race algorithm: Sampling Design and Iterative Refinement
Technical report

Apr 17, 2007 12:30-14:00 Erik Stochastic optimisation

L. Mercier and P. Van Hentenryck.

Performance Analysis of Online Anticipatory Algorithms for Large Multistage Stochastic Integer Programs
One of two IJCAI 07 distinguished papers

A slide show is available at http://www.cs.brown.edu/people/mercier/slides/IJCAI_07_AnticipatoryAlg.html

Apr 3, 2007 12:30-14:00 Frank Stochastic local search

Duc Nghia Pham, John Thornton, and Abdul Sattar

Building Structure into Local Search for SAT
One of two IJCAI 07 distinguished papers

 

Mar 20, 2007 12:30-14:00 Ashique Algorithm portfolios

Carla Gomes and Bart Selman. Artificial Intelligence Journal, Vol. 126, 2001, 43-62
Algorithm portfolios

Mar 13, 2007 12:30-14:00 Invited speaker: Karl Lieberherr Experimental studies in theory

Karl J. Lieberherr

Algorithmic extremal problems in combinatorial optimization
Journal of algorithms, 1982

Feb 27, 2007 12:30-14:00 Lin Machine learning

Chris Bishop and Markus Svensen

Bayesian Hierarchical Mixtures of Experts
UAI 03

Feb 22, 2007     Statistics in medicine

Interesting & relevant article in the economist, found by KLB:

Signs of the times
Why so much medical research is rot

http://www.economist.com/science/displaystory.cfm?story_id=8733754

Feb 13, 2007 12:30-14:00 Mike L Experimental studies in theory

Kamesh Madduri, David A. Bader, Jonathan W.Berry, and Joseph R. Crobak

An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances
ALENEX 07

Jan 22, 2007 12:30-14:00 Frank Bandits

Matthew J. Streeter and Stephen F. Smith
A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem
CP 06

Here is Matthew's presentation from CP

 

Previous discussions fall term 2006/07

Date Time Presenter General Topic

Paper / Title

Dec 13, 2006 12:30-14:00 Frank Automated parameter tuning

Frank talking about his ongoing research on local search for parameter tuning. Here are the slides

Nov 29, 2006 12:30-14:00    

Cancelled because of Geoff Hinton's talk

Nov 15, 2006 12:30-14:00 Kevin LB Restart Strategies

Matteo Gagliolo and Juergen M. Schmidhuber.
Learning Restart Strategies
IJCAI 07

Nov 1, 2006 12:30-14:00 Holger Multi-objective optimization Continuation of Chapter 4 of SLS:FA, and multi-objective optimization
Oct 25, 2006 12:30-14:00 Holger Experimental analysis of Las Vegas algorithms Chapter 4 of SLS:FA
Oct 18, 2006 12:30-14:00 Michael L Experimental analysis in the theoretical algorithms community

Arthur Brady and Lenore Cowen
Compact Routing on Power Law Graphs with Additive Stretch
In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the Third Workshop on Analytic Algorithmics and Combinatorics, pages 119-128, 2006.

Oct 11, 2006 12:30-14:00 Mirela Bayesian learning

Continuation of Bayesian CART and start of Mick's presentation

Oct 4, 2006 12:30-14:00 Mirela Bayesian learning

Yuhong Wu, Hakon Tjelmeland and Mike West.
Bayesian CART - Prior Specification and Posterior Simulation.
Working paper. January 22, 2006

Sep 27, 2006 12:30-14:00 Lin Run-time prediction

Continuation of:
Matteo Gagliolo and Juergen M. Schmidhuber
Impact of censored sampling on the performance of restart strategies.
To appear at CP 2006.

Sep 20, 2006 12:30-14:00 Lin Run-time prediction

Matteo Gagliolo and Juergen M. Schmidhuber
Impact of censored sampling on the performance of restart strategies.
To appear at CP 2006.

I'll see Matteo at CP - if you have comments or questions please let me know.

Sep 13, 2006 12:30-14:00 Alena PhD defense

Title: Novel Heuristic Search Methods for Protein Folding and Identification of Folding Pathways

Abstract: Proteins form the very basis of life. If we were to open up any living cell, we would find, apart from DNA and RNA molecules whose primary role is to store genetic information, a large number of different proteins that comprise the cell itself (for example the cell membrane and organelles), as well as a diverse set of enzymes that catalyze various metabolic reactions. If enzymes were absent, the cell would not be able to function, since a number of metabolic reactions would not be possible. Functions of proteins are the consequences of their functional 3D shape. Therefore, to control these versatile properties, we need to be able to predict the 3D shape of proteins; in other words, solve the protein folding problem. The prediction of a protein's conformation from its amino-acid sequence is currently one of the most prominent problems in molecular biology, biochemistry and bioinformatics. In this thesis, we address the protein folding problem and the closely-related problem of identifying folding pathways. The leading research objective for this work was to design efficient heuristic search algorithms for these problems, to empirically study these new methods and to compare them with existing algorithms.

This thesis makes the following contributions: (1) we show that biologically inspired approaches based on the notion of stigmergy – where a collection of agents modifies the environment, and those changes in turn affect the decision process of each agent (particularly artificial colonies of ants that give rise to such properties as self-organization and cooperation also observed in proteins) is a promising field of study for the protein folding problem; (2) we develop a novel adaptive search framework that is used to identify and to bin promising candidate solutions and to adaptively retrieve solutions when the search progress is unsatisfactory; (3) we develop a new method that efficiently explores large search neighbourhoods by performing biased iterated solution construction for identifying folding pathways; and (4) we show that our algorithms efficiently search the vast search landscapes encountered and are able to capture important aspects of the process of protein folding for some widely accepted computational models.

Sep 6, 2006 - - LCI open house -
Aug 23, 2006 12:30-14:00 Frank Experimental design for optimization

Belarmino Adenso-Díaz and Manuel Laguna,
Fine-tuning of Algorithms Using Fractional Experimental Design and Local Search Operations Research 54(1), 2006. (let me know if you want to access the paper and the above link doesn't work for you)

Here are my slides. There was a life demonstration of their CALIBRA software: I ran CALIBRA on the branin test function with a wrapper outputting which parameter settings are begin run into a file. Then I used Matlab to visualize that trajectory. I packed all this into a zip file.

My Summary:
The CALIBRA system combines fractional experimental design with a local search mechanism. Being limited to at most five free parameters, it starts off by evaluating each parameter configuration in a full factorial design. It then iteratively homes in to good regions in parameter space by employing fractional experimental designs that evaluate nine configurations around the so far best performing configuration. The grid for the experimental design becomes finer in each iteration, which provides a nice solution to the automatic discretization of continuous parameters. Once a local optimum is found and cannot be refined anymore, the search is restarted (with a coarser grid) by combining some of the best configurations found so far, but also introducing some noise for sake of diversification. The experiments reported in the paper show great promise in that CALIBRA was able to find parameter settings for six independent algorithms that matched or beat the respective originally proposed parameter configurations.

Aug 16, 2006 13:00-
14:00
Kevin LB/ Frank Model counting

Model Counting: A New Strategy for Obtaining Good Bounds
Carla P. Gomes, Ashish Sabharwal, Bart Selman AAAI-06.
Proceedings of the 21st National Conference on Artificial Intelligence, pp 54-61, Boston, MA, Jul 2006. (Best paper award)

Here are the original slides of the AAAI talk

 


Previous paper discussions 2004 - 2006

Date Time Presenter General Topic

Paper / Title

Feb 23, 2006 16:00-17:30 Kevin M Experimental design for optimization

Efficient Global Optimization of Expensive Black Box Functions

Donald R. Jones, Matthias Schonlau, William J. Welch. Journal of Global Optimization (?), 1998.

This is very well written and the basis of section 6.3.5 of the DACE book.

Feb 9, 2006 16:00-17:30 Kevin M Active learning Chapter 6 of the DACE book. Please see Frank for a copy.
Nov 21, 2005 17:30-19:00 Holger Space-filling designs for computer experiments Chapter 5 of the DACE book. Please see Frank for a copy.
Nov 14, 2005 13:30-15:00 Lin Additional topics in prediction methodology Chapter 4 of the DACE book, continued. Please see Frank for a copy. Lin's slides.
Nov 7, 2005 13:30-15:00 Lin Additional topics in prediction methodology Chapter 4 of the DACE book. Please see Frank for a copy. Lin's slides.
Oct 31, 2005 17:30-19:00 Kevin LB Predicting output from computer experiments Chapter 3 of the DACE book. Please see Frank for a copy. Kevin's slides
Oct 24, 2005 13:30-15:00 Hendrik Gaussian processes Section 2.3 of the DACE book. Please see Frank for a copy.
Since this is all about Gaussian processes, please also read Carl Rasmussen's tutorial
Gaussian processes in Machine Learning. Although Hendrik won't present this paper, we will discuss questions and comments people have ...
Oct 3, 2005 17:30-19:00 Frank Introduction to DACE Chapter 1 and sections 2.1-2.2 of the DACE book. Please see Frank for a copy. My slides.
May 4, 2005 14:30-16:00 Kevin M Experimental design Sacks, Welch, Michtell & Wynn, 1989: Design and Analysis of Computer Experiments
Apr 28, 2005 14:30-16:00 Kevin LB Experimental design Design and Analysis with Quantitative Predictors and Factors, chapters 14-19 in the book, part 3
Apr 21, 2005 14:30-16:00 Kevin LB Experimental design Design and Analysis with Quantitative Predictors and Factors, chapters 14-19 in the book, part 2
Apr 14, 2005 14:30-16:00 - - cancelled
Apr 7, 2005 14:30-16:00 Kevin LB Experimental design Design and Analysis with Quantitative Predictors and Factors, chapters 14-19 in the book, part 1
Mar 30, 2005 14:30-16:00 Frank Experimental design Design and Analysis with Random Effects, chapters 9-13 in the book continued
Mar 23, 2005 14:30-16:00 Frank Experimental design Design and Analysis with Random Effects, chapters 9-13 in the book
Mar 16, 2005 14:30-16:00 Clint Experimental design

Fractional Factorial Experiments, chapters 7-8 in the book
Clint's slides

Mar 9, 2005 14:30-16:00 Jacek Experimental design

Analysis-of-variance, chapters 6 in the book
Jacek's slides and anova in Matlab

Mar 2, 2005 14:30-16:00 Jacek Experimental design

Design of Factorial Experiments, chapters 4-5 in the book, finished by Kevin LB: Here's Kevin's slides

Analysis-of-variance, chapters 6 in the book; started by Jacek

Feb 23, 2005 14:30-16:00 Kevin LB Experimental design

Design of Factorial Experiments, chapters 4-5 in the book, to be finished
Here's Kevin's slides

Feb 16, 2005 14:30-16:00 - Reading week All but reading :-)
Feb 9, 2005 14:30-16:00 Kevin M Reading week Why I am a Bayesian
Here's Kevin's slides
Feb 2, 2005 14:30-16:00 Holger Experimental design Statistical tests, chapters 2-3 in the book - continued and finished.
Jan 26, 2005 14:30-16:00 - Experimental design

Talk by and meeting with David Johnson.

Jan 19, 2005 14:30-16:00 Holger Experimental design Statistical tests, chapters 2-3 in the book, to be continued
Jan 12, 2005 14:30-16:00 Holger Experimental design Foundations of statistical experimental design, chapter 1 in the book
Dec 9, 2004 15:00-16:00 - Organizational meeting -
Dec 2, 2004 15:00-16:00 Clinton Experimental design Statistical Design of Experiments - specific topic & paper to be agreed upon
Nov 25, 2004 15:00-16:00 Dan Experimental Design Statistical Design of Experiments (continued)

Nov 18, 2004

15:00-16:00 Asher / Dan Experimental design

“Designing and Reporting Computational Experiments with Heuristic Methods” by Barr, R. S., B. L. Golden, J. P. Kelly, M. G. C. Resende and W. R. Stewart (1995). [pdf] continued

and some stuff on Statistical Design of Experiments Dan will let us know about soon ...

Nov 11, 2004 No meeting - Remembrance day -

Nov 4, 2004

15:00-16:00 Asher Experimental design

“Designing and Reporting Computational Experiments with Heuristic Methods” by Barr, R. S., B. L. Golden, J. P. Kelly, M. G. C. Resende and W. R. Stewart (1995). [pdf]

Oct 28, 2004 15:00-16:00 Kevin Leyton-Brown Search in Game Theory Computing Nash Equilibria of Action-Graph Games. Bhat, Leyton-Brown. Presented at the 20th Conference on Uncertainty in Artificial Intelligence (UAI-2004) [pdf]
Oct 21, 2004 15:00-16:00 Frank / Dave Search in
Game Theory

Multi-Agent Algorithms for Solving Graphical Games [pdf] (continued)

and Multi-agent oriented constraint satisfaction [pdf] (local search for CSP cast as collaborating agents)

Oct 14, 2004 15:00-16:00 Frank Search in
Game Theory

Multi-Agent Algorithms for Solving Graphical Games [pdf]

This is a local search paper for a compact set of games called graphical games (basically Bayes nets for games)

Oct 7, 2004 15:00-16:00 Asher Search in
Game Theory

Simple Search Methods for Finding a Nash Equilibrium [pdf]

This paper concerns complete search.

Sep 30, 2004 15:00-16:00 Kevin Smyth Search space analysis Holger H. Hoos, Kevin Smyth, and Thomas St¨utzle. Search Space Features Underlying the Performance of Stochastic Local Search Algorithms for MAX-SAT. In Parallel Problem Solving from Nature – PPSN 2004, 2004. [pdf]
Sep 23, 2004 15:00-16:00 Alena Shmygelska Ant Colony Optimisation Dorigo M., G. Di Caro & L. M. Gambardella (1999). Ant Algorithms for Discrete Optimization. Artificial Life, 5(2):137-172. [pdf]

Relevant Sections (4.5 pages):
3.2 Application of ACO Algorithm to Dynamic Combinatorial Optimisation Problem (an example of application ACO to Network Routing)
3.2.1 Connection-Oriented Network Routing
3.2.2 Connectionless Network Routing

Here's the old EARG site with all previous papers


Original site creation and maintenance: Frank Hutter.

Currently maintained by: Chris Fawcett.