Neural Network Scaling Laws Predict Performance with Problem Complexity.

The predictable relationship between computational resources and the performance of artificial neural networks is a central question in contemporary machine learning. Recent investigations have established scaling laws linking performance to factors such as dataset size and model parameters, but a comprehensive understanding of how problem complexity influences these relationships remains elusive. Researchers at Virginia Tech and Kensho Technologies, led by Lowell Weissman, Michael Krumdick, and A. Lynn Abbott, address this gap in their work, “Complexity Scaling Laws for Neural Models using Combinatorial Optimization”. Their analysis, utilising the well-defined challenge of the Traveling Salesman Problem (TSP) – a classic problem in combinatorial optimisation concerned with finding the shortest possible route that visits a set of cities and returns to the origin – demonstrates that even without a readily interpretable measure of error, predictable scaling laws emerge when considering the size of the solution space and the complexity of the problem’s representation. The study reveals consistent patterns of increasing suboptimality as problem scale increases, irrespective of the training methodology employed, and suggests that even simple optimisation techniques can reveal these underlying trends.

The Traveling Salesperson Problem (TSP), a classic combinatorial optimisation challenge, exhibits predictable scaling behaviour according to recent research. Despite its inherent complexity, investigations reveal surprisingly smooth trends in solution cost as the number of cities increases, enabling the derivation of quantifiable scaling laws. This contrasts with the expectation of chaotic or unpredictable cost increases typical of such problems.

The observed scaling behaviour proves remarkably robust, persisting across diverse solution methodologies. Whether employing reinforcement learning, supervised fine-tuning of existing models, or a straightforward gradient descent approach, the consistent trends bolster the validity of the findings and suggest an underlying principle governing the problem’s difficulty. This consistency is notable, as different algorithms often exhibit varying performance characteristics on complex problems.

Researchers have established both upper and lower bounds on the growth of suboptimality – the difference between the solution found and the absolute optimal solution – as the number of cities, or dimensions in higher-dimensional variations of the problem, increases. This predictability allows for a more nuanced understanding of how solution quality degrades with increasing problem size, and provides a benchmark for evaluating the performance of different algorithms.

Interestingly, the research suggests that simple heuristics, such as generating random tour sequences, may perform comparatively well in high-dimensional spaces. This challenges conventional wisdom which often prioritises complex algorithms for tackling difficult optimisation problems, and implies that more sophisticated approaches may not always yield substantial improvements in certain scenarios.

The findings draw parallels with recent advances in neural scaling laws, which demonstrate predictable relationships between model size, training data, and performance in machine learning. This connection suggests that the size of the solution/search space – a fundamental characteristic of problem complexity – plays a crucial role in determining the scaling behaviour of optimisation problems generally.

While the established scaling laws hold true for uniformly distributed city coordinates, the constant ‘λ’ within the mathematical bound is sensitive to the specific coordinate distribution. This highlights the importance of considering the characteristics of the input data when analysing and addressing optimisation problems, as different data distributions can significantly impact algorithm performance and scalability.