[Feature request] Adding Hill Climbing

[jmuchovej]

👋 I was wondering if there's a reason that [Stochastic] Hill Climbing isn't part of Optim.jl – I definitely get that Simulated Annealing is a "better" version of [S]HC, but [S]HC is still useful for many problems. (Definitely understand that it's a local optimizer, but it's not that uncommon to use in Program Synthesis!)

I'm happy to contribute it, just wanted to get a sense of why it might not already be in Optim.jl. 🙂

[pkofod]

What's your intended use-case? Is the domain (multivariate) continuous?

[jmuchovej]

My intended use case (at the moment) is program synthesis – programs are symbolic though (I haven't figured out how I might be able to reduce it to a vector/matrix-centric representation).

The domain is currently discrete, but will become mixed (so aspects discrete, others continuous).

I didn't see this before I opened the issue – but I don't believe I can actually specify the problem's objective using the syntax Optim.jl desires (demands?). (i.e., there's an objective, but the objective doesn't have a clear mathematical formulation, instead it relies on simulation.)

[pkofod]

What's the objective?

[jmuchovej]

Assemble a program which maximizes the likelihood of an action sequence in a POMDP. The program specifies rewards and beliefs for the POMDP, then simulation is used to MC-integrate a likelihood estimate. (Trying to be as high-level as possible, let me know if this is unclear. 😅)

[pkofod]

Assemble a program which maximizes the likelihood of an action sequence in a POMDP. The program specifies rewards and beliefs for the POMDP, then simulation is used to MC-integrate a likelihood estimate. (Trying to be as high-level as possible, let me know if this is unclear. 😅)

Alright, that makes it a bit more clear. Are you simulating this program writing process?

[jmuchovej]

I don't think so? (I don't fully understand what you're looking for. 😅)

In terms of [S]HC: You can treat the neighboring programs as mutations (a la EvoComp-style mutations) of the best program. Each mutation is then scored via simulation (processed described above). Then, we convert the likelihoods of the neighbors into a distribution via softmax and follow [S]HC accordingly. (So, either taking argmax or sample from this distribution as the proposed neighbor.)

[jmuchovej]

@pkofod friendly ping about this. 🙂