5 ms·

Another fun fact: if instead of considering a distribution on the inputs, you consider worst case, then Queueing Theory becomes Online Algorithms. The technique

by gnull 4y ago

Another fun fact: if instead of considering a distribution on the inputs, you consider worst case, then Queueing Theory becomes Online Algorithms. The techniques there seem very different from Queueing Theory, but I also heard some Computer Scientists calling Online Algorithms boring because the techniques used there are very similar and results aren't too suprizing (I can't say I share this sentiment).

Der_Einzige 4y ago
If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting...
- dunham 4y ago
  Back when I was in college, an online algorithm was one where you had to make scheduling decisions as the jobs came in. There would be an optimal schedule (say differing size jobs coming in with n cpus) if you knew the future, and you prove things like "this algorithm can hit that optimal time with 1.x as many CPUs" or "this algorithm is within 1.x of optimal". This also applies to stuff like swapping / expiring cache - if you knew all of the future disk / memory accesses you could hit optimal, otherwise you need some heuristics. It's been a couple of decades, but I think some the proofs involved playing the part of an omniscient adversary.
  - gnull 4y ago
    Indeed. One impressive result I remember from that area (if I'm not mistaken) is that Least Recently Used cache policy with cache size S performs at least as well as an offline algorithm with cache size S/2. I don't remember the details now, but the proof wasn't too complicated, they gave it to us as an exercise.
- q-big 4y ago
  > If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting... I rather think that with "online algorithm", gnull means exactly this classic computer science topic: > https://en.wikipedia.org/wiki/Online_algorithm https://en.wikipedia.org/wiki/Online_algorithm

by gnull 4y ago

Der_Einzige 4y ago

If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting...

dunham 4y ago
Back when I was in college, an online algorithm was one where you had to make scheduling decisions as the jobs came in. There would be an optimal schedule (say differing size jobs coming in with n cpus) if you knew the future, and you prove things like "this algorithm can hit that optimal time with 1.x as many CPUs" or "this algorithm is within 1.x of optimal". This also applies to stuff like swapping / expiring cache - if you knew all of the future disk / memory accesses you could hit optimal, otherwise you need some heuristics. It's been a couple of decades, but I think some the proofs involved playing the part of an omniscient adversary.
- gnull 4y ago
  Indeed. One impressive result I remember from that area (if I'm not mistaken) is that Least Recently Used cache policy with cache size S performs at least as well as an offline algorithm with cache size S/2. I don't remember the details now, but the proof wasn't too complicated, they gave it to us as an exercise.
q-big 4y ago
> If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting... I rather think that with "online algorithm", gnull means exactly this classic computer science topic: > https://en.wikipedia.org/wiki/Online_algorithm https://en.wikipedia.org/wiki/Online_algorithm