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 email@example.com with the command "subscribe ea-rg" in the body of your message.
Paper / Title
|March 5, 2014||13:00 - 14:00||Alex Fréchette||Bandits||
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, Csaba Szepesvári
|March 12, 2014||13:00 - 14:00||Steve Ramage||TBD||TBD|
Paper / Title
|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.
|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
|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
|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.
|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
|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-
"How much do we pay for using default parameters? (2009 paper in the Journal of Computational Optimization and Applications, see http://www.springerlink.com/
|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
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|
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
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
|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|
|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
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)
Previous presentations 2008
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
Marco Chiarandini, Chris Fawcett, Holger H. Hoos
A Competition Retrospective.
|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/
|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)
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
|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
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
|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
Wireless Networks", SIGCOMM 2007.
|June 11, 2008||12:00-1:30pm||Frank||Online parameter tuning||Online Estimation of SAT
by Shai Haim and Toby Walsh,
|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
|July 16, 2008||12:00-1:30pm||Lin||Backdoors||Backdoors To
Typical Case Complexity
Ryan Williams, Carla P. Gomes, Bart Selman
|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
|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
|Oct 22, 2008||11-12:30||Dave||Experimental Methodology||J.N. Hooker
Testing Heuristics: We Have It All Wrong
Journal of Heustics, 1995
|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
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
|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:
|Game theory||Local search and computing equilibria in congestion games
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
Title: Modeling the Reasoning of Agents in Games
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
|Oct 18, 2007||Frank||Automated parameter tuning||
Thomas Bartz–Beielstein and Sandor Markon.
In Congress on Evolutionary Computation (CEC'04)
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.
Paper / Title
|Global optimization survey||
Donald R. Jones
|Global optimization: one approach||
Brigham S. Anderson, Andrew W. Moore, and David Cohn.
|Global optimization: one approach||
Mauro Brunato, Roberto Battiti and Srinivas Pasupuleti
|Experimental Design: foundations||
Merlise A. Clyde
|Experimental Design: applications||
Steven Coy, Bruce L. Golden, George C. Runger, Edward A. Wasil
Philip Kilby, John Slaney, Sylvie Thiebaux, and Toby Walsh
|Learning of search space structure||
Shumeet Baluja and Scott Davies
|Combining local and global search||
Meinolf Sellmann and Carlos Ansotegui
Previous discussions spring and summer 2007
Paper / Title
|Aug 30, 2007||12:30-14:00||Lin||Portfolios for SAT||
Lin Xu, Frank Hutter, Holger Hoos, Kevin Leyton-Brown.
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
|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
|July 10, 2007||12:30-14:00||Erik||Machine learning||
Thomas G. Dietterich
|July 3, 2007||12:30-14:00||Frank||Reinforcement learning for SAT||
Michail G. Lagoudakis and Michael L. Littman.
|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
|Apr 17, 2007||12:30-14:00||Erik||Stochastic optimisation||
L. Mercier and P. Van Hentenryck.
Analysis of Online Anticipatory Algorithms for Large Multistage
Stochastic Integer Programs
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
into Local Search for SAT
|Mar 20, 2007||12:30-14:00||Ashique||Algorithm portfolios||
Carla Gomes and Bart Selman. Artificial Intelligence Journal,
Vol. 126, 2001, 43-62
|Mar 13, 2007||12:30-14:00||Invited speaker: Karl Lieberherr||Experimental studies in theory||
Karl J. Lieberherr
|Feb 27, 2007||12:30-14:00||Lin||Machine learning||
Chris Bishop and Markus Svensen
|Feb 22, 2007||Statistics in medicine||
Interesting & relevant article in the economist, found by KLB:
Signs of the times
|Feb 13, 2007||12:30-14:00||Mike L||Experimental studies in theory||
Kamesh Madduri, David A. Bader, Jonathan W.Berry, and Joseph
|Jan 22, 2007||12:30-14:00||Frank||Bandits||
Matthew J. Streeter and Stephen F. Smith
Here is Matthew's presentation from CP
Previous discussions fall term 2006/07
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.
|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
|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.
|Sep 27, 2006||12:30-14:00||Lin||Run-time prediction||
|Sep 20, 2006||12:30-14:00||Lin||Run-time prediction||
Matteo Gagliolo and Juergen M. Schmidhuber
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,
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.
|Aug 16, 2006||13:00-
|Kevin LB/ Frank||Model counting||
A New Strategy for Obtaining Good Bounds
Here are the original slides of the AAAI talk
Previous paper discussions 2004 - 2006
Paper / Title
|Feb 23, 2006||16:00-17:30||Kevin M||Experimental design for optimization||
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
|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|
|Mar 9, 2005||14:30-16:00||Jacek||Experimental design|
|Mar 2, 2005||14:30-16:00||Jacek||Experimental design||
Analysis-of-variance, chapters 6 in the book; started by Jacek
|Feb 23, 2005||14:30-16:00||Kevin LB||Experimental design|
|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
“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
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
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
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):
Here's the old EARG site with all previous papers
Original site creation and maintenance: Frank Hutter.
Currently maintained by: Chris Fawcett.