Monday, August 22nd, 2016

9:30 am10:30 am

This tutorial will present an overview of techniques from Approximation Algorithms as relevant to Stochastic Optimization problems. In these problems, we assume partial information about inputs in the form of distributions.  Special emphasis will be placed on techniques based on linear programming and duality. The tutorial will assume no prior background in stochastic optimization.

The second session of this mini course will take place on Monday, August 22nd, 2016 11:00 am – 12:00 pm.

11:00 am12:00 pm

This tutorial will present an overview of techniques from Approximation Algorithms as relevant to Stochastic Optimization problems. In these problems, we assume partial information about inputs in the form of distributions.  Special emphasis will be placed on techniques based on linear programming and duality. The tutorial will assume no prior background in stochastic optimization.

The first session of this mini course will take place on Monday, August 22nd, 2016 9:30 am – 10:30 am.

1:30 pm2:30 pm

In this tutorial, I'll cover two popular versions of online selection problems - secretary problems and prophet inequalities. In the vanilla version of both, elements of a set are revealed to you one at a time. When an element is revealed, you learn its "weight," and must immediately and irrevocably decide whether to accept, claiming its weight as your reward but forgoing the opportunity to see the remaining elements, or reject, bypassing the element forever (but you will see future elements). In secretary problems, the weights are chosen by an adversary and the elements are revealed in a uniformly random order. In prophet inequalities, the weights are drawn independently from known distributions, and an adversary chooses the order (and distributions). Your goal is to maximize your expected reward.

There is a ton of recent work solving multiple-choice online selection problems, where you may now accept multiple elements, but are subject to some feasibility constraints (often related to matroids). The tutorial will cover in detail the solutions to both vanilla problems (Dynkin for the secretary problem and Krengel-Sucheston for prophet inequalities), as well as a subset of these recent works.

The second session of this mini course will take place on Monday, August 22nd, 2016 3:00 pm – 4:00 pm.

3:00 pm4:00 pm

In this tutorial, I'll cover two popular versions of online selection problems - secretary problems and prophet inequalities. In the vanilla version of both, elements of a set are revealed to you one at a time. When an element is revealed, you learn its "weight," and must immediately and irrevocably decide whether to accept, claiming its weight as your reward but forgoing the opportunity to see the remaining elements, or reject, bypassing the element forever (but you will see future elements). In secretary problems, the weights are chosen by an adversary and the elements are revealed in a uniformly random order. In prophet inequalities, the weights are drawn independently from known distributions, and an adversary chooses the order (and distributions). Your goal is to maximize your expected reward.

There is a ton of recent work solving multiple-choice online selection problems, where you may now accept multiple elements, but are subject to some feasibility constraints (often related to matroids). The tutorial will cover in detail the solutions to both vanilla problems (Dynkin for the secretary problem and Krengel-Sucheston for prophet inequalities), as well as a subset of these recent works.

The first session of this mini course will take place on Monday, August 22nd, 2016 1:30 pm – 2:30 pm.

Tuesday, August 23rd, 2016

9:30 am10:30 am

The talk will survey various applications of linear programming to the design and analysis of competitive online algorithms. A unified approach, based on the primal-dual method, is discussed for a wide range of online covering and packing problems, having various objective functions. This approach has lead to the resolution of several important open problems, as well as a simple alternative view and analysis of many previously suggested algorithms. Recently, the framework has been extended to the non-linear setting, e.g., convex objective functions and semidefinite programming. Another important technique is dual fitting which plays an important role in the design of online algorithms, in particular in network design and scheduling. The focus of the talk will be on developing the general methodology, as well as highlighting connections to other fields such as online learning.

The second session of this mini course will take place on Tuesday, August 23rd, 2016 11:00 am – 12:00 pm.

11:00 am12:00 pm

The talk will survey various applications of linear programming to the design and analysis of competitive online algorithms. A unified approach, based on the primal-dual method, is discussed for a wide range of online covering and packing problems, having various objective functions. This approach has lead to the resolution of several important open problems, as well as a simple alternative view and analysis of many previously suggested algorithms. Recently, the framework has been extended to the non-linear setting, e.g., convex objective functions and semidefinite programming. Another important technique is dual fitting which plays an important role in the design of online algorithms, in particular in network design and scheduling. The focus of the talk will be on developing the general methodology, as well as highlighting connections to other fields such as online learning.

The first session of this mini course will take place on Tuesday, August 23rd, 2016 9:30 am – 10:30 am.

1:30 pm2:30 pm

The theory of scheduling has a long and storied history. Out of this large body of work two distinct research communities have emerged and, unfortunately, researchers in each community are typically unaware of results and tools from the other community. One set of researchers, from the online scheduling community, focuses on providing competitive guarantees for scheduling disciplines in worst-case settings; while another set of researchers, from the queueing community, focuses on providing exact performance analyses of scheduling policies in stochastic/probabilistic environments. Our goal in this tutorial is to highlight places where there is potential for techniques to be developed to bridge these communities, achieving the "best of both worlds".  To that end, we will highlight some success stories from recent years in addition to promising open research directions.

The second session of this mini course will take place on Tuesday, August 23rd, 2016 3:00 pm – 4:00 pm.

3:00 pm4:00 pm

The theory of scheduling has a long and storied history. Out of this large body of work two distinct research communities have emerged and, unfortunately, researchers in each community are typically unaware of results and tools from the other community. One set of researchers, from the online scheduling community, focuses on providing competitive guarantees for scheduling disciplines in worst-case settings; while another set of researchers, from the queueing community, focuses on providing exact performance analyses of scheduling policies in stochastic/probabilistic environments. Our goal in this tutorial is to highlight places where there is potential for techniques to be developed to bridge these communities, achieving the "best of both worlds".  To that end, we will highlight some success stories from recent years in addition to promising open research directions.

The first session of this mini course will take place on Tuesday, August 23rd, 2016 1:30 pm – 2:30 pm.

Wednesday, August 24th, 2016

9:00 am9:45 am

Sampling is a powerful technique, which is at the core of statistical data analysis and machine learning. Using a finite, often small, set of observations, we attempt to estimate properties of an entire sample space. How good are estimates obtained from a sample? Any rigorous application of sampling requires an understanding of the sample complexity of the problem – the minimum size sample needed to obtain the required results. In this tutorial we will cover some of the rich mathematical theory that has been develop in recent years to address this question, in particular in the context of statistical machine learning and rigorous data mining.

Main topics: Uniform convergence; VC-dimension - the ϵ-net and ϵ-sample theorems; Rademacher complexity; Applications in machine learning and data mining.

The second session of this mini course will take place on Wednesday, August 24th, 2016 10:15 am – 11:00 am.

10:15 am11:00 am

Sampling is a powerful technique, which is at the core of statistical data analysis and machine learning. Using a finite, often small, set of observations, we attempt to estimate properties of an entire sample space. How good are estimates obtained from a sample? Any rigorous application of sampling requires an understanding of the sample complexity of the problem – the minimum size sample needed to obtain the required results. In this tutorial we will cover some of the rich mathematical theory that has been develop in recent years to address this question, in particular in the context of statistical machine learning and rigorous data mining.

Main topics: Uniform convergence; VC-dimension - the ϵ-net and ϵ-sample theorems; Rademacher complexity; Applications in machine learning and data mining.

The first session of this mini course will take place on Wednesday, August 24th, 2016 9:00 am – 9:45 am.

11:30 am12:15 pm

In this tutorial we introduce the framework of online convex optimization, the standard model for the design and analysis of online learning algorithms. After defining the notions of regret and regularization, we describe and analyze some of the most important online algorithms, including Mirror Descent, AdaGrad, and Online Newton Step.

The second session of this mini course will take place on Wednesday, August 24th, 2016 2:00 pm – 2:45 pm.

2:00 pm2:45 pm

In this tutorial we introduce the framework of online convex optimization, the standard model for the design and analysis of online learning algorithms. After defining the notions of regret and regularization, we describe and analyze some of the most important online algorithms, including Mirror Descent, AdaGrad, and Online Newton Step.

The first session of this mini course will take place on Wednesday, August 24th, 2016 11:30 am – 12:15 pm.

3:15 pm4:00 pm

Reinforcement learning studies a dynamic environment where the learner's actions influence the state of the environment, which in turn influences the future rewards of the learner.  The goal of the learner is to maximize its long-term reward.  The common model for reinforcement learning is Markov Decision Processes (MDPs).

I will give a short tutorial on reinforcement learning and MDPs.  (I will assume very little on the background of the audience.) I will (try) and cover the following topics:
1. Mathematical model of Markov Decision Processes (MDP)
2. Planning in MDP: computing an optimal policy
3. Learning in (unknown) MDP
4. Large (exponential) state MDP
5. Partially Observable MDP (time permitting).

This tutorial is intended to be interactive with the audience participation.

The second session of this mini course will take place on Wednesday, August 24th, 2016 4:30 pm – 5:15 pm.

4:30 pm5:15 pm

Reinforcement learning studies a dynamic environment where the learner's actions influence the state of the environment, which in turn influences the future rewards of the learner.  The goal of the learner is to maximize its long-term reward.  The common model for reinforcement learning is Markov Decision Processes (MDPs).
I will give a short tutorial on reinforcement learning and MDPs.  (I will assume very little on the background of the audience.) I will (try) and cover the following topics:
1. Mathematical model of Markov Decision Processes (MDP)
2. Planning in MDP: computing an optimal policy
3. Learning in (unknown) MDP
4. Large (exponential) state MDP
5. Partially Observable MDP (time permitting).

This tutorial is intended to be interactive with the audience participation.

The first session of this mini course will take place on Wednesday, August 24th, 2016 3:15 pm – 4:00 pm.

Thursday, August 25th, 2016

9:30 am10:30 am
In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input.  This approach has countless success stories, but there are also important computational problems --- like linear programming, clustering, and online caching --- where the worst-case analysis framework does not provide any helpful advice on how to solve the problem.  This tutorial covers a number of modeling methods for going beyond worst-case analysis and articulating which inputs are the most relevant.
 
The first part of the tutorial focuses on deterministic models --- well-motivated conditions on inputs that explain when heuristics work well.  It explains why "clustering is hard only when it doesn't matter," and in particular covers the notions of approximation and perturbation stability, with applications to the k-median and multiway cut problems.  It also touches on the field of sparse recovery --- specifically, compressive sensing, l1-minimization, and the RIP condition --- to highlight the strong similarities with the other topics covered.
 
The second part of the tutorial covers probabilistic models, which make some type of distributional assumption. We pass over traditional average-case analysis, which assumes a known input distribution, in favor of more robust performance guarantees.  Specific topics include: planted and semi-random models for clique and bisection; smoothed analysis, with applications to linear programming and local search; a survey of additional "hybrid" analysis models that interpolate between worst- and average-case analysis; and the use of "average-case thought experiments" to generate novel deterministic input restrictions (like the RIP condition and graph classes for social networks) and performance benchmarks (as in no-regret online learning and prior-free auction design).
 

The second session of this mini course will take place on Thursday, August 25th, 2016 11:00 am – 12:00 pm.

11:00 am12:00 pm
In the worst-case analysis of algorithms, the overall performance of an algorithm is summarized by its worst performance on any input.  This approach has countless success stories, but there are also important computational problems --- like linear programming, clustering, and online caching --- where the worst-case analysis framework does not provide any helpful advice on how to solve the problem.  This tutorial covers a number of modeling methods for going beyond worst-case analysis and articulating which inputs are the most relevant.
 
The first part of the tutorial focuses on deterministic models --- well-motivated conditions on inputs that explain when heuristics work well.  It explains why "clustering is hard only when it doesn't matter," and in particular covers the notions of approximation and perturbation stability, with applications to the k-median and multiway cut problems.  It also touches on the field of sparse recovery --- specifically, compressive sensing, l1-minimization, and the RIP condition --- to highlight the strong similarities with the other topics covered.
 
The second part of the tutorial covers probabilistic models, which make some type of distributional assumption. We pass over traditional average-case analysis, which assumes a known input distribution, in favor of more robust performance guarantees.  Specific topics include: planted and semi-random models for clique and bisection; smoothed analysis, with applications to linear programming and local search; a survey of additional "hybrid" analysis models that interpolate between worst- and average-case analysis; and the use of "average-case thought experiments" to generate novel deterministic input restrictions (like the RIP condition and graph classes for social networks) and performance benchmarks (as in no-regret online learning and prior-free auction design).
 

The first session of this mini course will take place on Thursday, August 25th, 2016 9:30 am – 10:30 am.

1:30 pm2:30 pm

Problems are intractable when they “can be solved, but not fast enough for the solution to be usable” [HopcroftMotwani & Ullman, 2007]. NP-complete problems are commonly said to be intractable; however, the reality is more complex. All known algorithms for solving NP-complete prob­lems require exponential time in the worst case; however, these algorithms nevertheless solve many problems of practical impor­tance astoundingly quickly, and are hence relied upon in a broad range of applications. The propositional satisfiability problem (SAT) serves as a good example. The FCC's multi-billion dollar spectrum auctions operate by solving hundreds of thousands of SAT-encoded graph coloring problems, typically each involving tens of thousands of variables and millions of constraints. These instances can often be solved in seconds, even though the same solvers can be stymied by hand-crafted instances involving only hundreds of variables. Clearly, we could benefit from a more nuanced understanding of algorithm behaviour than is offered by asymptotic, worst-case analy­sis.

This tutorial is focused on the question most relevant to an end user: “How hard is it to solve a given family of problem instances, using the best available methods?” Formal, complexity-theoretic analysis of this question seems hopeless: the best available algorithms are highly complex (and, in some cases, only available in compiled form), and instance distributions representative of practical applications are heterogeneous and richly structured. For this reason, we turn to statistical, rather than combinatorial, analysis. The main claim of this tutorial is that rigorous statistical methods can characterize algorithm runtime with high levels of confidence. More specifically, this article surveys over a decade of research showing how to build empirical hardness models (EHMs) that, given a new problem instance, estimate the runtime of an algorithm in low-order polynomial time. We have shown that it is possible to build quite accurate models for different NP-complete problems (we have studied SAT, combinatorial auction winner determination, mixed integer program­ming, and the traveling salesman problem), distributions of problem instances (we have considered dozens), solvers (again, dozens). We have robustly found that even very succinct EHMs can achieve high accuracies, meaning that they describe simple relationships between instance characteristics and algorithm runtime. This makes our approach important even for theoretically inclined computer scientists who prefer proofs to experimental findings: EHMs can uncover new, simple relationships between instance characteristics and runtime, and thereby catalyze new theoretical work.

The tutorial will emphasize ways that EHMs contribute to our understanding of NP-complete problems; however, they are also useful ina variety of practical applications. Most straightforwardly, they can aid the distribution of problem instances across a cluster, or predict how long a run will take to complete. More interestingly, they can (1) be leveraged to automatically make benchmark distributions more challenging; (2) be used to combine a set of high-variance algorithms into an “algorithm portfolio” that outperforms its constituents; and (3) aid in the configuration (or “tuning”) of highly parameterized algorithms for good performance on given instance distributions. If time permits, I'll briefly discuss each of these applications. In particular, I'll explain how we leveraged ideas (2) and (3) to build the SAT solver portfolios that clear the FCC auctions.

The second session of this mini course will take place on Thursday, August 25th, 2016 3:00 pm – 4:00 pm.

3:00 pm4:00 pm

Problems are intractable when they “can be solved, but not fast enough for the solution to be usable” [HopcroftMotwani & Ullman, 2007]. NP-complete problems are commonly said to be intractable; however, the reality is more complex. All known algorithms for solving NP-complete prob­lems require exponential time in the worst case; however, these algorithms nevertheless solve many problems of practical impor­tance astoundingly quickly, and are hence relied upon in a broad range of applications. The propositional satisfiability problem (SAT) serves as a good example. The FCC's multi-billion dollar spectrum auctions operate by solving hundreds of thousands of SAT-encoded graph coloring problems, typically each involving tens of thousands of variables and millions of constraints. These instances can often be solved in seconds, even though the same solvers can be stymied by hand-crafted instances involving only hundreds of variables. Clearly, we could benefit from a more nuanced understanding of algorithm behaviour than is offered by asymptotic, worst-case analy­sis.

This tutorial is focused on the question most relevant to an end user: “How hard is it to solve a given family of problem instances, using the best available methods?” Formal, complexity-theoretic analysis of this question seems hopeless: the best available algorithms are highly complex (and, in some cases, only available in compiled form), and instance distributions representative of practical applications are heterogeneous and richly structured. For this reason, we turn to statistical, rather than combinatorial, analysis. The main claim of this tutorial is that rigorous statistical methods can characterize algorithm runtime with high levels of confidence. More specifically, this article surveys over a decade of research showing how to build empirical hardness models (EHMs) that, given a new problem instance, estimate the runtime of an algorithm in low-order polynomial time. We have shown that it is possible to build quite accurate models for different NP-complete problems (we have studied SAT, combinatorial auction winner determination, mixed integer program­ming, and the traveling salesman problem), distributions of problem instances (we have considered dozens), solvers (again, dozens). We have robustly found that even very succinct EHMs can achieve high accuracies, meaning that they describe simple relationships between instance characteristics and algorithm runtime. This makes our approach important even for theoretically inclined computer scientists who prefer proofs to experimental findings: EHMs can uncover new, simple relationships between instance characteristics and runtime, and thereby catalyze new theoretical work.

The tutorial will emphasize ways that EHMs contribute to our understanding of NP-complete problems; however, they are also useful ina variety of practical applications. Most straightforwardly, they can aid the distribution of problem instances across a cluster, or predict how long a run will take to complete. More interestingly, they can (1) be leveraged to automatically make benchmark distributions more challenging; (2) be used to combine a set of high-variance algorithms into an “algorithm portfolio” that outperforms its constituents; and (3) aid in the configuration (or “tuning”) of highly parameterized algorithms for good performance on given instance distributions. If time permits, I'll briefly discuss each of these applications. In particular, I'll explain how we leveraged ideas (2) and (3) to build the SAT solver portfolios that clear the FCC auctions.

The first session of this mini course will take place on Thursday, August 25th, 2016 1:30 pm – 2:30 pm.

Friday, August 26th, 2016

11:00 am12:00 pm

Driven by a desire for increased sustainability, the power grid is in the midst of an enormous transformation. A crucial piece of this transformation is the incorporation of renewable energy from sources such as solar and wind.  However, the uncertainty inherent in these forms of generation places enormous challenges on the management of the grid.  In this tutorial, we will provide an overview of some of the crucial challenges grid operators face today as a result of increased uncertainty in generation.  We will highlight algorithmic and market challenges where uncertainty has upended traditional approaches for control and optimization, and discuss a variety of open problems where new designs are needed.

The second session of this mini course will take place on Friday, August 26th, 2016 1:30 pm – 2:30 pm.

1:30 pm2:30 pm

Driven by a desire for increased sustainability, the power grid is in the midst of an enormous transformation. A crucial piece of this transformation is the incorporation of renewable energy from sources such as solar and wind.  However, the uncertainty inherent in these forms of generation places enormous challenges on the management of the grid.  In this tutorial, we will provide an overview of some of the crucial challenges grid operators face today as a result of increased uncertainty in generation.  We will highlight algorithmic and market challenges where uncertainty has upended traditional approaches for control and optimization, and discuss a variety of open problems where new designs are needed.

The first session of this mini course will take place on Friday, August 26th, 2016 11:00 am – 12:00 pm.