Have computer scientists discovered the limits of major research algorithms?

 Gradient descent is an essential algorithm used in many modern applied research fields. It is used to find the largest or smallest values of a specific mathematical function, known as optimizing the function. A variety of tasks, from optimizing product manufacturing to shift management, can be done using this algorithm. Despite its wide usage, it has been unclear which situations the algorithm finds most difficult. Now, a new study has revealed the answer. It turns out that gradient descent ultimately struggles with a difficult computational problem. Researchers are able to better understand the performance of gradient descent in various applications. The study was led by Paul Goldberg of the University of Oxford, and was recognized with a Best Paper Award at the annual Symposium on Theory of Computing. With this knowledge in hand, researchers now know the limitations of gradient descent and can more reliably use it for its many applications.

Gradient descent is the process of finding the local minimum of a function by searching downhill away from it, using the slope of the landscape as a guide. Before modern research, however, there was no comprehensive understanding of why gradient descent sometimes fails to work well. This is where computational complexity theory comes in. Computational complexity is the study of resources used to solve or verify different computing problems, and sorting these problems into different classes based on their shared characteristics. An example of this is if you were asked to find two people who live in the same house given a phone book of names and addresses — you know an answer exists, but it may take some time to find it. This is just one example of how computational complexity theory has helped to understand why gradient descent may not work at times.

TFNP is a complexity class that includes all computational problems that have solutions and can also be quickly verified. It includes two subsets of problems, PLS and PPAD. PLS stands for polynomial local search, which involves finding the minimum or maximum value of a function within a certain region. An example of this could be planning a route between a set number of cities with the shortest possible travel distance, by changing the order of any two consecutive cities. PPAD, or polynomial parity arguments on directed graphs, involves Brouwer’s fixed point theorem, which states that any continuous function must have one point which remains unchanged. An example of this could be stirring a glass of water; the theorem guarantees that there must be one particle of water that ends up in the same place it started from.

The intersection of the PLS and PPAD classes is known as PLS int PPAD, and it contains a wide variety of natural problems that are highly relevant to complexity researchers. Despite this, until now, a natural problem that is complete for PLS int PPAD has eluded researchers - meaning that no example of the hardest possible problems that fall within the class has been discovered.

The researchers discuss the computational complexity of gradient descent and its implications for various applications. Prior to their work, the only known PLS int PPAD-complete problem was a contrived construction called "Either-Solution," which combined complete problems from two different complexity classes, PLS and PPAD. In their new paper, the researchers show that gradient descent is as hard as the Either-Solution problem, establishing that gradient descent itself is PLS int PPAD-complete. The complexity classification of PLS int PPAD-complete suggests that gradient descent faces significant challenges in providing precise solutions for certain problems. While gradient descent remains fast and effective for many practical applications, it might not be suitable for situations where high precision is essential.

The key concern in computational complexity is evaluating the resource requirements of an algorithm. The precision of a solution and the speed of computation are often intertwined. An efficient algorithm should allow researchers to increase the precision of a solution without incurring an excessively high computational cost. The new result indicates that for applications requiring very precise solutions, gradient descent may not be a feasible approach. For machine learning tasks, where extreme precision is often unnecessary, gradient descent is commonly used and works well. If a researcher wants to increase the precision of an experiment, they may need to accept a longer running time for the gradient descent algorithm, but this trade-off is generally manageable.

However, for other applications like numerical analysis, researchers might require a significantly higher level of precision. Achieving this level of improvement in precision using gradient descent could result in a corresponding increase in the algorithm's running time, making the calculations intractable.The research outcome encourages researchers to be aware of the limitations of gradient descent for precise problem-solving. While compromise and trade-offs are often made in practice, such as accepting less precision or focusing on slightly easier problems, finding a fast algorithm for gradient descent itself is challenging. Moreover, any such fast algorithm for gradient descent would also imply the existence of fast algorithms for all other problems in the PLS int PPAD complexity class, which is a much higher bar to achieve.