Empirical Optimization with Divergent Fixed Point Algorithm – When All Else Fails

Entitled “Empirical Optimization with Divergent Fixed Point Algorithm – When All Else Fails”, the full version in PDF format is accessible in the “Free Books and Articles” section, here. Also discussed in details with Python code in my book “Synthetic Data”, available here.

While the technique discussed here is a last resort solution when all else fails, it is actually more powerful than it seems at first glance. First, it also works in standard cases with “nice” functions. However, there are better methods when the function behaves nicely, taking advantage of the differentiability of the function in question, such as the Newton algorithm (itself a fixed-point iteration). It can be generalized to higher dimensions, though I focus on univariate functions here.

Perhaps the attractive features are the fact that it is simple and intuitive, and quickly leads to a solution despite the absence of convergence. However, it is an empirical method and may require working with different parameter sets to actually find a solution. Still, it can be turned into a black-box solution by automatically testing different parameter configurations. In that respect, I compare it to the empirical elbow rule to detect the number of clusters in unsupervised clustering problems. I also turned the elbow rule into a fully automated black-box procedure, with full details offered in the same book.

Abstract

Why would anyone be interested in an algorithm that never converges to the solution you are looking for? This version of the fixed-point iteration, when approaching a zero or an optimum, emits a strong signal and allows you to detect a small interval likely to contain the solution: the zero or global optimum in question. It may approach the optimum quite well, but subsequent iterations do not lead to convergence: the algorithm eventually moves away from the optimum, or oscillates around the optimum without ever reaching it.

The fixed-point iteration is the mother of all optimization and root-finding algorithms. In particular, all gradient-based optimization techniques are a particular version of this generic method. In this chapter, I use it in a very challenging setting. The target function may not be differentiable or may have a very large number of local minima and maxima. All the standard techniques fail to detect the global optima. In this case, even the fixed-point method diverges. However, somehow, it can tell you the location of a global optimum with a rather decent precision. Once an approximation is obtained, the method can be applied again, this time focusing around a narrow interval containing the solution to achieve higher precision. Also, this method is a lot faster than brute force such as grid search.

I first illustrate the method on a specific problem. Then, generating synthetic data that emulates and generalizes the setting of the initial problem, I illustrate how the method performs on different functions or data sets. The purpose is to show how synthetic data can be used to test and benchmark algorithms, or to understand when they work, and when they don’t. This, combined with the intuitive aspects of my fixed-point iteration, illustrates a particular facet of explainable AI. Finally, I use a smoothing technique to visualize the highly chaotic functions involved here. It highlights the features of the functions that we are interested in, while removing the massive noise that makes these functions almost impossible to visualize in any meaningful way.

Table of Contents

1. Introduction
   • The problem, with illustration
2. Non-converging fixed-point algorithm
   • Trick leading to intuitive solution
   • Root detection: method and parameters
   • Case study with conclusions
3. Generalization with synthetic data
   • Example
   • Connection to the Poisson-binomial distribution
   • Location of next root: guesstimate
   • Integer sequences with high density of primes
   • Python code: finding the optimum
4. Smoothing highly chaotic curves
   • Python code: smoothing

Download the Article

The technical article, entitled Empirical Optimization with Divergent Fixed Point Algorithm – When All Else Fails, is accessible in the “Free Books and Articles” section, here. It contains links to my GitHub files, to easily copy and paste the code. The text highlighted in orange in this PDF document are keywords that will be incorporated in the index, when I aggregate all my related articles into books about machine learning, visualization and Python, similar to these ones. The text highlighted in blue corresponds to external clickable links, mostly references. And red is used for internal links, pointing to a section, bibliography entry, equation, and so on.

To not miss future articles, sign-up to our newsletter, here.

About the author

Vincent Granville is a pioneering data scientist and machine learning expert, co-founder of Data Science Central (acquired by  TechTarget in 2020), founder of MLTechniques.com, former VC-funded executive, author and patent owner. Vincent’s past corporate experience includes Visa, Wells Fargo, eBay, NBC, Microsoft, and CNET. Vincent is also a former post-doc at Cambridge University, and the National Institute of Statistical Sciences (NISS).  

Vincent published in Journal of Number Theory, Journal of the Royal Statistical Society (Series B), and IEEE Transactions on Pattern Analysis and Machine Intelligence. He is also the author of multiple books, including “Intuitive Machine Learning and Explainable AI”, available here. He lives  in Washington state, and enjoys doing research on spatial stochastic processes, chaotic dynamical systems, experimental math and probabilistic number theory.