Tag Archives: algorithms

Computation time and model development

20 seconds, 20 minutes, or 20 hours.  These are all amounts of time that a computational method I’ve been working at some time has taken to complete processing.  They each lead to a very different experience for the model developer, and probably in the end for the model, too. Twenty seconds is definitely what I prefer.

Comments Off

Filed under statistics, TCS

Algorithms in the Field Workshop

Last week I attended the workshop Algorithms in the Field or “8F”, as its puzzling acronym turns out to be. David Eppstein published comprehensive notes on the talks on his blog:

I like to think that I’m doing “8F” in my global health job, and also some algorithms in the forest, algorithms in the desert, etc. But this workshop gave me a chance to think about the connection to Algorithms with a capitol “A”, the kind going on in the theory group of the ivory towered computer science department. I’ve been pretty successful at coming up with little challenges in global health where algorithmic thinking is useful (e.g. Doctors = Noise Machines), and I’m going to try to use the blog to throw more of these puzzles over the fence in the next few weeks. My barrier to doing this in the past has been the amount of background research I need to do to avoid sounding foolish. But my writing style was never suited to caution. Let’s see how it goes. I hope that even half-explained connections between Algorithms and global health will inspire some algorithmitician to fill in the details.

What I challenge myself to do more of is to go beyond the little puzzles, and synthesize something bigger to ask from algorithmists. What algorithmic innovation would really change how we’re doing things in Global Health? This is a domain where avoiding foolishness is even more of a recipe for silence. But I will try.

On my mind now: the computation time necessary to fit a model. 20 seconds, 20 minutes, or 20 hours is a really big difference. More on that thought to come.

Question to readers from Global Health Departments, what do you think capitol-A algorithms researchers can offer us?

Comments Off

Filed under global health, TCS

Losing touch with theory?

I’ve been flipping through the titles of SODA acceptances listed on the blogs, and wondering if I’m losing touch with TCS research. It’s a good chance for me to think about what algorithms (discrete or otherwise) have been really big in the health metrics work I’ve been doing recently.

  • Markov Chain Monte Carlo (MCMC):  This is the workhorse algorithm for me when fitting statistical models.  There are a few MCMC-sounding titles in the SODA list;  does anything have an exciting new step method to speed up my life?
  • Mixed Integer Programming (MIP):  This classic formulation of operations research must make an appearance in some of the approximation algorithms or other analysis in SODA.  Is there any work there that’s taking it on directly?
  • Stochastic Programming:  There was a lot of excitement about two-stage stochastic programming a few years ago, but the fad seems to have died down in theory land.  Too bad for me, because two-stage formulations are not really what I need, and my StoPro needs are growing.
  • Random Forests:  I really didn’t get enough education on machine learning in grad school.  What I do know is very much on the theoretical side of the spectrum.  But this Random Forests business has been pretty promising so far, and I just made a bet 10-to-1 that it will out-perform an ad-hoc method for verbal autopsy.  I believe the odds, but I wasn’t paying enough attention to the stakes…
  • Nonlinear optimization:  I love MCMC, but I don’t love waiting around for my chains to mix.  The alternative approach to statistical modeling, where you make due with a maximum likelihood estimate is starting to look pretty appealing.  This is pretty outside of the SODA realm.  I tried to convince Steven Rudich to include Newton’s Method in his course “Great Theoretical Ideas in Computer Science” some years ago, but I didn’t succeed.
  • Automatic Differentiation:  If I’m getting into nonlinear optimization, I will at least be a user of automatic differentiation, since the nonlinear optimizer wants to know the gradient, and I’m sure not going to be computing it if I don’t have to be.

So I guess my research needs are not squarely within the SODA realm.  But they are not disjoint from it either.  I’m still touching theory, if not totally in touch.  Maybe one day soon I’ll even have time to prove something.

Comments Off

Filed under TCS