3 ms·
If by "online algorithm" you mean incremental learning, the problem is that they still don't work well due to catastrophic forgetting...
by 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 agoBack 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 agoIndeed. 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