Week 4 Summary and Questions -- Seldonian Algorithm (Tutorial #1)

[dashaasienga]

@katcorr

This week, I began working on the "Hello, World!" of the Seldonian algorithm. This is basically a simple problem designed to help us understand the inner workings of the Seldonian framework, both from a theoretical and computational standpoint.

I created a Jupyter notebook (found in the Python folder of this repo) to start implementing and running some of their code on my own computer. I made it about halfway through the tutorial. Jupyter notebook works similar to R Markdown files since it allows one to segment their code into cells and add comments. It supports LateX and all publicly available Python packages, so I chose to use it and may consider shifting to another platform if I run into any roadblocks. We used it in the ML course and I also used a similar platform during my internship this summer, so I'm pretty familiar with it.

Theoretical Framework

To demonstrate how the Seldonian algorithm works, we will consider a simple regression problem. Let X∈ℝ and Y∈ℝ be two dependent random variables. Our goal is to estimate Y given X, based on training data consisting of m independent and identically distributed samples. In this example we construct synthetic data (50000 points) where the inputs X come from a standard normal distribution and where the outputs Y are equal to the inputs, plus noise with a standard normal distribution: X∼N(0,1) and Y∼N(X,1). Notice that Seldonian algorithms will not know the distributions of X and Y in advance.

The plot of the points will be akin to this:

The goal is to construct an algorithm that:

• Minimizes MSE (maximize the negative of the MSE).
• Ensures that, with probability at least 0.9, the MSE of its predictions is below 2.0 and above 1.25.

This is intended to not only display the core computational aspects of the Seldonian framework, but to also test the ability of a Seldonian algorithm to handle behavioral constraints that may be in conflict with the objective function.

As quasi-Seldonian algorithms tend to be more practical and data-efficient than Seldonian algorithms, the researchers focus on creating a quasi-Seldonian algorithm here.

The complete algorithm works as follows:

Therefore, when finding the candidate solution, we set it up such that we’re using the training set to find an algorithm that maximizes the objective function, but that is also predicted to pass the safety test.

Computational Framework

Let's review the work I've done on the Python notebook so far :)

Questions

There is a lot of technical jargon in how the algorithm is set up. I'd like to review them with you to make sure I fully understand what is going on. See screenshots below.

Next Steps

1. Complete the Seldonian tutorial.
2. Continue understanding the theoretical underpinnings of the framework (actually working with the code is helping to make these concepts more clear!)

[dashaasienga]

The problem:

[dashaasienga]

The behavioral constraints:

[dashaasienga]

The safety test:

[dashaasienga]

The candidate solution:

Note that when the primary objective and behavioral constraints are conflicting (as they are in this problem), the candidate selection mechanism tends to be over-confident that the candidate solution will pass the safety test -- likely due to overfitting. To work around this, we double the width of the confidence interval when predicting the outcome of the safety test, by multiplying the second term of the upper bound by 2.