GroundedML: Anchoring Machine Learning in Classical Algorithmic Theory

Recent advances in Machine Learning (ML) have revolutionized our ability to solve complex problems in a myriad of application domains. Yet, just as empirical data plays a fundamental role in the development of such applications, the process of designing these methods has also remained empirical: we have learned which of the known methods tend to perform better for certain types of problems, and have developed intuition guiding our discovery of new methods.

In contrast, classical algorithmic theory provides tools directly addressing the mathematical core of a problem, and clear theoretical justifications motivate powerful design techniques. At the heart of this process is the analysis of the correctness and time/space efficiency of an algorithm, providing actionable bounds and guarantees. Problems themselves may be characterized by bounding the performance of any algorithm, providing a meaningful reference point to which concrete algorithms may be compared. While ML models may appear to be an awkward fit for such techniques, some research in the area has succeeded in obtaining results with the “definitive” flavour associated with algorithms, complementary to empirical ones. Are such discoveries bound to be exceptions, or can they be part of a new algorithmic theory?

The GoundedML workshop seeks to bring together researchers from both the algorithmic theory and machine learning communities, starting a dialogue on how ideas from theoretical algorithm design can inspire and guide future research in machine learning.