13 ms·

I am extremely optimistic about using learned heuristics in discrete algorithms like A* or Focal search or the various families of ILP. In most modern discrete

I am extremely optimistic about using learned heuristics in discrete algorithms like A* or Focal search or the various families of ILP. In most modern discrete optimization libraries, e.g. CPLEX it's the heuristics and tuning that explain the performance. I'm less understanding of using a end to end learning approach to replace a well understood optimal search routine, but that might be pearl clutching. It just seems to me the authors missed that opportunity.

boesboes 3y ago
I think it is just the bubble/hype effect around transformers and AI. I might try to use transformers to solve tic-tac-toe and apply for some VC moneys. In a few years we'll all be writing about how much more efficient actual code is compared to AI perhaps ;)
- losvedir 3y ago
  Everyone on Transformer News will be talking about the latest web framework for GPT-7 and how to horizontally scale their system to handle dozens of requests a second, and how when you need to scale beyond that it will "be a good problem to have". Meanwhile, you and I will be talking about how our low-level, handwritten Ruby on Rails code is so much faster and more efficient, and closer to the metal so you can understand what's _really_ going on.
nvrmnd 3y ago
I agree, learning admissible heuristics will retain worst case performance, which has always been the measuring stick for these algorithms. It's not at all uncommon to find faster solutions for the average or even p99 cases that cannot provide guarantees on the worst case.
- SnowflakeOnIce 3y ago
  How would one go about proving that a learned heuristic (something from an AI model) is in fact admissible?
  - jvanderbot 3y ago
    For something like focal search, it doesn't even need admissibility, you just apply it as a second selection heuristic among the choices your admissable heuristic returns as 'top k' choices.
    - SnowflakeOnIce 3y ago
      So a tiebreaker then?

boesboes 3y ago

I think it is just the bubble/hype effect around transformers and AI. I might try to use transformers to solve tic-tac-toe and apply for some VC moneys. In a few years we'll all be writing about how much more efficient actual code is compared to AI perhaps ;)

losvedir 3y ago
Everyone on Transformer News will be talking about the latest web framework for GPT-7 and how to horizontally scale their system to handle dozens of requests a second, and how when you need to scale beyond that it will "be a good problem to have". Meanwhile, you and I will be talking about how our low-level, handwritten Ruby on Rails code is so much faster and more efficient, and closer to the metal so you can understand what's _really_ going on.

nvrmnd 3y ago

I agree, learning admissible heuristics will retain worst case performance, which has always been the measuring stick for these algorithms. It's not at all uncommon to find faster solutions for the average or even p99 cases that cannot provide guarantees on the worst case.

SnowflakeOnIce 3y ago
How would one go about proving that a learned heuristic (something from an AI model) is in fact admissible?
- jvanderbot 3y ago
  For something like focal search, it doesn't even need admissibility, you just apply it as a second selection heuristic among the choices your admissable heuristic returns as 'top k' choices.
  - SnowflakeOnIce 3y ago
    So a tiebreaker then?