Saturday, September 04, 2021

Harvard Shopping Period, Here We Go Again

I was looking at today's Harvard Crimson, and noted that Harvard's shopping period looks ready to be vanished again.  Shopping period is that wonderful Harvard tradition where students don't preregister for classes, but instead they choose classes after the first week, after having a chance to go to a lecture or two and see how they like it.  I encourage students -- and faculty -- to push back against efforts that restrict student flexibility in choosing their classes.  While administrators hate it, I still think it's better for students to avoid strong forms of preregistration.   

In fact, I realized I've been fighting this fight for quite a while -- here's something I wrote about when the administration under Larry Summers tried to get rid of it, from this blog back in 2008, and here's a Crimson article from 2002, where I spoke out against the plan for moving to preregistration that the blog post refers to. 

More recently, in 2018-2019, I found myself on the "Course Registration Committee", a committee that initially seemed similarly designed to find a way to move Harvard from shopping period to preregistration.  But a few of us on the committee made convincing arguments that shopping period had many benefits, and the disappearance of shopping period seemed at least somewhat further delayed, while a better solution was found. 

Then the pandemic.  Shopping period seemed impossible in the chaos, and things were more ad hoc (although there was, last year, a push for "class previews" of some sort before the beginning of classes).  This seems to give an opening to remove shopping period again.   

I'm not saying there aren't ways to change the system to make it better.  I'm not blind to the issues of shopping period -- not having a determined class size before classes begin is problematic for some classes.  I believe the committee people who have continued to look at the issue are trying to make things better going forward.  But the push always seems to be to make a system which is easier for administrators, and somehow correspondingly that is worse for the students.  Students should have the flexibility to see classes and teachers before committing, which to me means either a shopping period, or a structure that allows them to easily change classes for the first couple of weeks with negligible overhead.  I suppose one could design an add/drop system with the flexibility I'd have in mind, but it never seems to work that way in practice -- students end up needing signatures and approvals of various flavors, because (I think) it's in the best interest of administrators to make it hard for students to change classes once classes begin.  (Having 60 people sign up for a class but then having 30 people leave in the first week is possibly worse than the shopping period approach of not having sign-ups before the class at all, but it's a lot easier to disincentivize students from switching out (or in) with a preregistration system, so that problem disappears, at the cost of student flexibility.)  

As an example of a "non-shopping" issue I've seen this semester, first-year students at Harvard first semester are "limited" to four classes.  (There may be a way to get an exception to this, but I understand it would be rare exception.)  So this semester, with no shopping period, first years have to choose their 4 classes -- without seeing them -- and then manage a confusing add/drop process if they don't like them.  The older students generally know how to play the game -- they sign up for 5 or even 6 classes (if they can) and drop the ones they don't like, because dropping is generally easier than adding.  But first years don't have that flexibility because the 4-course rule is enforced at signup.  (I advise some first year students, and this problem came up.)  

I'm sure many non-Harvard people reading this think the shopping period system sounds crazy, and maybe a few think Harvard students are bizarrely spoiled.  Perhaps they're right.  But I found as a student it was wonderful, and shaped my future in powerful ways by encouraging me to explore.  You walk into a class you thought you should take, and find the professor puts you to sleep;  or you get dragged to a class by a friend, and find an inspiring subject you had no idea you would like.  I believe my college experience would have been lessened significantly without shopping period.  

As a faculty member, shopping period is clearly a pain, but I think a manageable one.   Back in 2002-2003, the faculty pushed back against preregistration (see this old Crimson article), but it seems opinions have shifted over time;  many faculty seemed to have moved to thinking it's not worth it, which is probably in their own self-interest.  Having been on both sides, I'm still strongly in favor of shopping period.  I suppose if I ever get into administration I may see things differently.  

I hope there are (younger) defenders out there, in the students and faculty, to push to make sure any changes still favor student choice over administrative convenience, and lead to the best outcomes for students.  

Monday, August 09, 2021

Queues with Small Advice

I have had papers rejected, with comments of the form that the results seem too easy, and are at the level of a homework assignment.  Generally, I think these reviewers miss the point.  The fact that the results seem easy may be because the point isn't the derivation but the conception and framing of the problem.  I actually think that generally it's an interesting subclass of good papers that can be and are turned into homework assignments.

A new-ish paper of mine, Queues with Small Advice, was recently accepted to the very new SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), which took place July 19-21.  This conference focuses on algorithms with a close tie to applications.  Some people unfamiliar with theory conferences might think that algorithms work would naturally be tied to applications, but I've generally found that algorithmic work tied to applications is more negatively reviewed in theory conferences.  Indeed, that type of work is much more likely to receive comments of the form that the results seem too easy, and are at the level of a homework assignment.  So perhaps this new conference will fill an important role and hole in the current slate of theory conferences. 

In any case, I actually do think this paper is in some ways easy (in that the analysis is readily approachable with standard tools), and parts of it would, I believe, make a great homework assignment.  The goal was to show the potential power of using even very simple advice, such as from machine-learning algorithms, in queueing systems.  This seems to me to be a very understudied topic, and fits into the recently growing theme of Algorithms with Predictions.  (The paper was rejected previously from a conference, where the most negative review said "Very accessible and well written paper, which certainly provides motivation to consider problems of this type." but also said "The mathematical analysis in this paper is fairly standard, and in that sense not novel... the paper is interesting, but not advancing sufficiently the state of the art.")  

The paper focuses on the case of 1 bit of advice -- essentially, is the job "short" or "long".  I think this type is advice is a good approach to look at for queueing -- it corresponds naturally to putting a job at the front of the queue, or the back.  And it may be easier for machine-learning algorithms to generate accurately.  Simple is often good in practice.  

Rather than describe the paper further, I'll go ahead and turn it directly into a collection of homework problems.  Feel free to use them or variations you come up with;  hopefully, the students won't find the paper for answers. I personally would be thrilled if one outcome of this paper was that prediction-based problems of this form made their way into problem sets.  (Although, serious question:  who still teaches queueing theory any more?)  

Section 1:  One-Bit Advice (Single Queue)

a)  Consider the standard M/M/1 queue, with Poisson arrivals at rate λ, and exponentially distributed service times of mean 1;  the expected time a job spends in the queue in equilibrium is 1/(1-λ).  Now suppose each job comes with one bit advice;  if the job has service time greater than T, the bit is 1, and if it is smaller than T, the bit is 0.  A "big" job goes to the end of the queue, a "small" job goes to the front.  (Assume the queue is non-preemptive.)  Find the expected time for a job in this queue in equilibrium, as a function of T and λ.

b)  What is the optimal value for T (as a function of λ)? 

c)  Repeat parts a and b, but this time with a preemptive queue.  Does preemption help or hurt performance?

Harder variation:  The above questions, but with an M/G/1 queue (that is, for a general, given service distribution);  derive a formula for the expected time in the system, where the formula may involve terms based on the service distribution.

Easier variation:  Write a simulation, experimentally determine the best threshold, and the improvements from one bit of advice.  Different service time distributions can be tried.  

Section 2:  One-Bit Advice with Predictions (Single Queue)

Where would possibly get a bit of advice in real life?  Perhaps from a machine learning predictor.  But in that case, the advice might turn out to be wrong.  What if our bit of advice is just right most of the time?

a)  Consider the (non-preemptive) M/M/1 queue variation from Section 1 part a above, but now the advice is correct with some probability p.  Find the expected time for a job in this queue in equilibrium, as a function of p, T, and λ.

b)  Repeat part a with a preemptive queue.

Harder variations:  The above questions, but have the probability the advice is correct depend on the size of the job.  A particularly fun example is when the "predicted service time" for a job with true time x is exponentially distributed with mean x, and the prediction bit is 1 if the predicted time is larger than T, and 0 otherwise.  Also, one can again consider general service times.  

Easier variation:  Again, write a simulation and derive experimental results/insights.  

Section 3:  One-Bit Advice with Prediction (Power of 2 Choices)  [harder, grad student level;  needs to know fluid limit models;  I'd stick with sections 1 and 2!]

a)  Derive fluid limit equations for a collection of N queues, where there are two types of jobs:  "large" jobs arrive as a Poisson stream of rate λ₁N and have exponentially distributed service times with mean μ₁ and "small" jobs arrive as a Poisson stream of rate λ₂N and have exponentially distributed service times of mean μ₂.  Each job comes with a bit of advice determining whether it is large or small, but large jobs are mislabelled with probability p₁ and small jobs are mislabelled with probability p₂.  An incoming job selects a queue using "the power of two choices" -- it is up to you to describe how a job determines what is the better of the two choices (there are multiple possibilities) and how jobs are processed within a queue (non-preemptive is suggested).   

[Hint:  the queue state can be represented by the number of jobs that are labelled short that are waiting, the number of jobs that are labelled long that are waiting, and the type of the job currently being serviced.]  

b)  Compare fluid limit results to simulations for 1000 queues to see if your equations seem accurate.  


Tuesday, June 08, 2021

Machine Learning for Algorithms Workshop (July 13-14)

We're having an online workshop on "Machine Learning for Algorithms" on July 13-14, with a great group of speakers.  Announcement below, link at https://fodsi.us/ml4a.html, free registration (but please register in advance)!

In recent years there has been increasing interest in using machine learning to improve the performance of classical algorithms in computer science, by fine-tuning their behavior to adapt to the properties of the input distribution. This "data-driven" or "learning-based" approach to algorithm design has the potential to significantly improve the efficiency of some of the most widely used algorithms. For example, they have been used to design better data structures, online algorithms, streaming and sketching algorithms, market mechanisms and algorithms for combinatorial optimization, similarity search and inverse problems.  This virtual workshop will feature talks from experts at the forefront of this exciting area.

The workshop is organized by Foundations of Data Science Institute (FODSI), a project supported by the NSF TRIPODS program (see fodsi.us). To attend, please register at    
 
https://fodsi.us/ml4a.html  

Sunday, November 29, 2020

ADAPT: Designing Activity-Informed Viral Diagnostic Assays

I wanted to give a pointer to a new preprint on bioRxiv on developing diagnostic assays for viruses, by (first author) Hayden Metsky (and others!) out of the Sabeti Lab at the Broad Institute (that I've been a bit involved with).  Hayden, who somehow is both a computer science PhD and an expert in virology, has devised a novel software pipeline for developing diagnostics that are designed from the start to deal with genomic diversity (a virus evolves to have many somewhat different variants) and the challenge of false matches (you don't want to get false positives from matching some other different virus) -- also known as sensitivity and specificity.  Algorithmically, he uses machine learning to determine scores for possible tests for matches to small pieces of the genome, or probes, and utilizes locality-sensitive hashing, combinatorial optimization algorithms for submodular maximization, and sharding pattern matching across tries as substages in the overall design.  

I am always excited to see algorithmic ideas being used to solve real-world problems, and this is a deep and difficult example of the "algorithmic lens"  at work.  I am optimistically hopeful that this type of technology will help drive the development of viral diagnostic and monitoring methods forward.     

Thursday, November 26, 2020

TCS Connections Questionnaire

I wanted to link to a survey that is up entitled Committee on TCS Connections Questionnaire.  They are examining modifying approaches to publishing in the theoretical computer science community, and they are focusing on FOCS/STOC.

I personally approve of the idea of the committee, though I admit I am concerned that it's too little, too late.  For years, FOCS/STOC has been a culture concerned with some sense of "prestige" -- the number of accepted papers has to be kept low, because we want people outside of theory to take FOCS/STOC as an imprimatur for the top theory work.  Because of this, FOCS/STOC has stayed essentially the same size, while the field (whether you view the field as TCS or computer science writ large) has expanded.  This has led to a proliferation of additional conferences (ITCS, HALG, various theory workshops...) that reduce the importance of FOCS/STOC and their role in creating community cohesion.  It has also led to other areas (most notably AI) becoming the home to work that should be quite at home in major TCS conferences.  

I don't think FOCS/STOC is what is used to be (the central home for theory results, when theory was smaller) or what it has supposedly wanted to be (the home for the best theory results).  I think it makes a lot of sense to stop and think about what they should be for the future.  Hence the survey is important, and I encourage the theoretical computer science community to respond.  I'm not sure, though, that there are great answers -- external forces, and the community's general aversion to change, may mean that there is not much to be done.  

Wednesday, September 02, 2020

Broad Testing Thank You

 I have a loose association with the Broad Institute, an institute created so that "complementary expertise of the genomic scientists and the chemical biologists across MIT and Harvard be brought together in one place to drive the transformation of medicine with molecular knowledge."  (See https://www.broadinstitute.org/history )

They recently passed an amazing milestone, having performed over 1 million Covid tests.  They weren't set up to be a Covid testing lab, but the converted their institute space to respond to the Covid crisis.  (See https://covid19-testing.broadinstitute.org/ )  

In short, they stepped up.  They certainly didn't have to, but they did.  Maybe it will help them do good science, now and in the future.  But my understanding is that they saw a clear societal need (lots of outbreak specialists there ) and they realized they had the expertise and equipment to do good that went beyond science.  I just wanted to give a shout out to the Broad for their good works, scientific and societal.  

Saturday, June 27, 2020

STOC Workshop on "Algorithms with Predictions"

The STOC workshop on Algorithms with Predictions was on Friday, and I thought it went really well!  I can't speak for my talk, but the other 3 talks (Tim Roughgarden, Edith Cohen, Ravi Kumar) were fantastic and inspiring, and I really recommend them for anyone with an interest in "Beyond Worst-Case Analysis".   

The talks are all on Youtube.  And the workshop page is full of useful links and information. 

Thursday, June 25, 2020

Writing Code for a Paper : A Note to Students

This post both relates to some of the stuff I'll be presenting at Friday's STOC workshop on Algorithms with Predictions, but is also for future students in my classes, who sometimes wonder why I have them write code on theory material.  (Somehow this might be a theme for a lecture in my grad class next semester, so maybe these are a first attempt at notes for the lecture.  Comments  and  suggestions welcome.)

Some of the work I'm doing is looking at how queueing systems perform with various sorts of predictions on the times the jobs take.  This particular work I'm doing on my own.  (While most of my research has been and is with collaborators, and it's one of the things I enjoy about computer science -- we're a very collaborative field!, which seems to surprise many people -- I still sometimes like to do research projects on my own.  I've looked at queueing systems since my PhD thesis, and it's a bit outside the research interest of most of my collaborator pool, and it's "fun" sometimes to do my own thing.  The reason why "fun" is in quotes is described below.) 

Often in my work in queueing I'm looking at mean-field limits (meant to model infinite systems of queues, which provides a good approximation for large finite systems under reasonable assumptions), where I can derive families of differential equations describing the system behavior.  I can also simulate the large finite system directly, and make sure the results match.  I generally do this for all of these types of papers.

Now the numbers I get from simulating the system directly and from simulating the differential equations should match (say within 1% or so).  If they don't, something is wrong.  In an effort to avoid wrongness, I won't consider the paper ready for outside consumption until I get a match.  Unfortunately, there are three ways things can go wrong.

1.  My simulation code for the queueing system might have bugs.
2.  My code to evaluate the differential equations might have bugs.
3.  My equations themselves might have bugs.

And I find there are two main categories of bugs.  Sometimes the bugs are simple/standard coding mistakes -- I'm off by 1 on an index, or I cut and paste and forget to change an i++ to a j++ in one my double loops, or I type x instead of a y.  Usually it's pretty easy to find these things, although I've had times where a hidden typo took hours to find.  But sometimes the bug is a thinking mistake -- I've forgotten a subcase and so my equations aren't complete (and so my code evaluating the equations won't give the right answer), or I've not handled a subcase correctly in my simulation.  That type usually takes longer. 

Usually, the first time through, most all of these types of bugs happen -- my math is off, I've typed some stuff wrong, it can all happen.  And then, like coders everywhere, I go through and fix it.  And it's painful.  Sometimes everything goes right, a quick check or two and everything works.  For more complicated stuff, it's more time figuring out what went wrong than setting up the code to begin with.  And being the personality type to not let things sit, that can mean late nights figuring out what went wrong.

For my talk this week, there was one last problem I wanted to include, which meant finally taking the model and writing the equations and code.  I didn't even need it for the talk, but it's also the last bit before I put a paper draft on arxiv, so taking advantage of a deadline, I figured now was the time.  Which means the last 2 days, I've spent many hours (and a late night) trying to remove the disagreements.

On the plus side, when everything finally works, it's a wonderful feeling.  And it always makes me feel better when I have worked to verify my math this way;  this time, what kept me up well past midnight and took several hours to track down was actually a boundary case I had left out of the equations.  (I had looked at the equations over and over again without noticing I had left out the subcase;  I had to step through numbers from the differential equations one time step at a time to track down what was missing, and then the numbers told me what I had done wrong.)

On the down side, it's work, and debugging is never particularly fun.

For students out there, maybe I'm just explaining that I understand the pain that I am putting you through.  You may wonder why I have you do simulations that take a few hours if you do them well, but days if you don't think through the best approach.  But using programming and theory together can be powerful;  it's helped me countless times in my research.

(Related: on theory and experiments that I've written on before, along with a viewpoint by Jeffrey Ullman.)


Wednesday, June 17, 2020

Algorithms with Predictions: Survey and Workshop

There's a whole new, interesting theory trend  -- Algorithms with Predictions.  The idea, spurred by advances in machine learning, is that you assume you have predictor that tells you something about your input.  For example, in caching, you might have a prediction of when the item you are currently accessing will be next accessed.  Of course, machine learning predictions aren't perfect.  Still, you'd like to use this prediction to improve your caching algorithm, but from the theory side, we'd like provable statements.  For example, you could say, if my prediction is THIS good (e.g., the error is bounded under some metric), then my caching performance will correspondingly be at least THIS good (e.g., performance bounded in some way).

If you haven't seen the burgeoning spread of this line of work and are interested, you're in luck.  First, Sergei Vassilvitskii and I have written a brief survey that's now on the arxiv.  We had written it for a collection Tim Roughgarden is organizing on Beyond Worst-Case Analysis (that we thought we be out by now, and should be out from the publisher soon-ish), but we've gone ahead and put a version on the arxiv to make it available.  The area is moving fast, so there are already many new results --  we hope to update the "survey" with new material as the area grows.

Second, one of the STOC'20 Workshops will be on Algorithms with Predictions.  It will be on Friday from 1-4pm, with speakers Tim Roughgarden, Edith Cohen,  Ravi Kumar, and me.  I'll be talking about some of my recent work  (in submission) on queues with predictions, and partitioned learned Bloom filters.  (Arxiv papers are here, here, and here, but maybe you want to see the talk first.)  I'll also do a blog post on partitioned learned Bloom filters in the near future.