Convexity and connectivity of the solution space in machine learning problems

Book excerpt: ScientiaRerum Thesis — 2018. This thesis investigates properties of the solution space of the machine-learning problem of random pattern classification. Such properties as convexity of the space of solutions, its connectivity and clusterization are studied. Evidence has been provided recently that there exists a universality class for random pattern classification models, making it possible to study the properties of the whole set of constraint satisfaction problems using the most simple model, the perceptron with spherical constraint: it is exactly solvable and exhibits the full stack of charactetistic properties of that class. In order to obtain statistically representative treatment of the model (as opposed to the best/worst-case scenarios), we used the well established methods of theoretical physics of disordered systems (a.k.a. spin glasses). In terms of that science, this model can be interpreted as a random packing problem and demonstrates the phenomenology of slow glassy relaxation and a jamming transition. The specific property of that model is that the corresponding constraint satisfaction problems ceases to be convex. The non-convex domain is exproled in detail in this thesis and its structure is presented on a phase diagram.Publisher : Scientia Rerum (academic publishers), Paris