Why you should put Fixed Point Strategies in Your Toolbox
Fixed point strategies can approximate infinite depth.- The methods are easy to train/implement.
- This essential set of tools can model and analyze a wide range of DS problems.
Fixed point theory, which first developed about 60 years ago, is directly connected to limits and traditional control and optimization [1]. These methods are ideal for finding solutions to a broad range of phenomena that crop up in large-scale optimization and highly structured data problems. They work for problems formulated as minimization problems, or more general forms like Nash equilibria [no term] or nonlinear operator equations.
Compared to traditional models, fixed point methods are in their infancy. However, there’s a lot of research suggesting that these algorithms may be the future of data science.
How do Fixed Point Methods Work?
Fixed point theory works in a similar way to optimization and is related to the idea of a limit in calculus: at some point in the process, you get “close enough” to a solution: one that’s good enough for your purposes. When it’s not possible to find an exact solution, or an exact answer isn’t needed, a fixed-point algorithm can give an approximate answer.
As a simple example, your company might want to create a model for the maximum amount of money a U.S. citizen is willing to spend on new household gadgets per year. An exact solution would depend on many factors, including the fickle nature of consumerism, changing tastes and the effect of climate change on purchasing decisions. It would be difficult (if not impossible) to find an exact solution ($561.23? $981.65?). But there’s going to be a cap, or a limit, which the amount spent tends towards: possibly $570 per annum, possibly $1,000.
You could attempt to find the solution to a large-scale optimization problem like this one with traditional methods—if you have the computer resources to take on the challenge. In some cases, even the most powerful computer may not be able to hand the computations, which is where fixed point theory steps in.
Advantages of Fixed-Point Methods
Fixed point methods have several major advantages over traditional methods. They create a more efficient framework for implicit depth without requiring more memory or increasing the computational costs of training [2]. On the algorithmic front, fixed point strategies include powerful convergence principles which simplify the design and analysis of iterative methods. In addition, block-coordinate or block-iterative strategies reduce an iteration’s computational load and memory requirements [3].
Google research scientist Zelda Mariet and MIT professor Suvrit Sra approached the problem of maximum-likelihood estimation [no term] by comparing performance of the EM algorithm against a novel fixed-point iteration [4]. When the authors compared performance on both synthetic and real-world data, they found that their fixed-point method gave shorter runtimes when handling large matrices and training sets. The fixed-point approach also ran “remarkably faster” for a range of ground set sizes and number of samples. Not only was it faster than the EM algorithm, but it was also remarkably simple to implement.
The Future of Deep Learning?
One of the major problems with the creation of deep learning models is that the deeper and more expressible a model becomes, the more memory is required. In a practical sense, the amount of computer memory is limited by model depth. A workaround is implicit depth methods, but these come with the burden of more computational cost to train networks. At a certain point, some problems simply become too complex to be solve using traditional methods. As we go on to the future, models are destined to become more complex, which means we must find better ways to arrive at solutions.
When finding an exact solution isn’t possible because of computational limits, many problems can be formulated in terms of fixed-point optimization schemes. These schemes, applied to standard models, guarantee the convergence of a solution to the fixed point limit.
References:
Image: mikemacmarketing / photo on flickr, CC BY 2.0 , via Wikimedia Commons
[1] Fixed Point Theory and Algorithms for Sciences and Engineering
[2] Fixed Point Networks: Implicit Depth Models with Jacobian-Free Backprop
[3] Fixed Point Strategies in Data Science
[4] Fixed-point algorithms for learning determinantal point processes