1
$\begingroup$

I'm working on an optimization algorithm that I think could be considered machine learning, but I'm not sure. Basically I have a model that I want to optimize by adjusting its parameters. I don't have any target data to compare the output of my model to, so I don't know the loss factor. However, I'm able to generate information on whether increasing or decreasing a parameter will improve my model.

This information consists of a sum of positive and negative numbers that I'll call votes, and they are very noisy. I know I should increase the parameter if the average vote is positive and decrease it otherwise. I can generate as many votes as I like if I invest the computational resources, and I need to generate a sufficient number to over come the noise. I only know I've optimized the parameters if the average votes are zero.

I'm having a hard time optimizing my algorithm. Basically it's hard to decide how many votes I should take before shifting the parameters, and then how much I should shift them. I believe the optimal amounts depend very much on the circumstances. I'm wondering if my algorithm falls under a class of optimization algorithms that have a literature I could research. Or if anyone knows any literature that my be useful to what I'm working on.

$\endgroup$
0
$\begingroup$

It's hard to know what to recommend, without more context.

One possible approach is to use hill-climbing, simulated annealing, or some other form of local search. A simple form of hill-climbing is to pick a random variable, determine whether increasing/decreasing it will improve your model, and if so, increase/decrease it; then repeat until no further improvement is possible. You can combine with random restarts, or use a more powerful method like simulated annealing.

Alternatively, you could try using something like gradient descent. Suppose you learn not only whether increasing the parameter will improve the model, but how much it improves it. If you have this information, you can estimate the gradient at a point, then move in the direction of the gradient, and repeat. Based on experience with stochastic gradient descent, rather than repeating this many times at a single point and averaging, it's likely to be more effective to do this only once at each point and instead repeat for more iterations of gradient descent (perhaps with a smaller step size). Basically, because your information is noisy, each step is mostly random and is only loosely correlated with the correct direction, so this does a random walk that is slightly more likely to go in a good direction than a bad direction; after sufficiently many iterations, this should converge to a good solution. The analysis of stochastic gradient descent shows that in many settings this performs better than trying to compute many votes at a single point, average them to get a very good estimate of the direction to go, and repeat for many fewer iterations. So, the theory says: take only one vote. There's no theory to tell you how much to change the parameters (the step size). Usual practice in the machine learning literature is to treat this as a hyperparameter, try multiple different values (e.g., 0.0001, 0.001, 0.01, 0.1), and see which works best. Sometimes it may be helpful to start with a large step size and then reduce it after some number of iterations. There are also heuristic optimizers that try to adaptively adjust the step size, such as the Adam optimizer, but it's unclear whether they help or not.

Another approach is to use Bayesian optimization, which uses machine learning to construct a surrogate model that can predicts how well any set of parameters will perform, and then uses optimization methods on the surrogate model. See, e.g., Google Vizier for one representative of this approach.

I can't predict which approach is likely to be most suitable to your setting. That may depend on the number of dimensions (how many parameters you have), the dependence of the metric you care about as a function of the parameters (how nonlinear it is), and what kind of information you receive about any set of parameters.

Related: What solution to apply for finding the optimal parameters?, What is an appropriate global optimization technique for a noisy and expensive function?, Mathematical optimization on a noisy function.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.