Machine Learning for Networks

Objectives

The goal of the course is to teach basic methodologies for machine learning and signal processing and to show their application to network data analysis and optimization. The machine learning tools include: (i) Sparse and low-rank data representations with applications to compressive sensing and matrix/tensor completion; (ii) New tools such as graph signal processing (GSP), suitable for the very general class of data defined over non-metric space domains. Graph-theoretical tools play a fundamental role in GSP, and then they are deeply discussed and analyzed, together with operations over graphs, like partitioning, filtering, topology inference, and graph-based deep neural networks. Finally, it is shown how to formulate and solve stochastic optimization problems at the edge of the wireless network, with the aim of enabling learning tasks in a distributed fashion from data collected by heterogeneous devices (e.g., smartphones, sensors, drones, etc.), while satisfying strict latency/energy constraints imposed by applications (e.g., automated driving, industry 4.0, etc.) foreseen in the (beyond) 5G roadmap.

Prerequisite: basic knowledge of calculus, linear algebra, and probability theory.

Final Exam: Oral exam.

Lessons: 10 hours, corresponding to 2 CFU

Dates: The course will be held in the "Sala Lettura" of the DIET Dept., second floor, according to the following schedule:

• 22-06-22 , 14.30 - 17.00 (Prof. Di Lorenzo)

• 24-06-22 , 14.30 - 17.00 (Prof. Di Lorenzo)

• 28-06-22 , 14.30 - 16.30 (Prof. Sardellitti)

• 01-01-22 , 14.30 - 17.30 (Prof. Sardellitti)

Contents

(ii) The course is divided into two parts, whose description follows.

Part 1: Learning from Network Data (5 hours, Sergio Barbarossa). The goal of this part is to make students able to represent information distributed over a graph, and to perform inferences about network data collected over, e.g., technological, biological, or information networks. The course will introduce fundamental tools from algebraic graph theory, spectral clustering, and graph signal processing, which will be used to perform unsupervised and semi-supervised learning over network data. Also, state of the art methods for inferring the graph topology that better describes relationships among observed data will be presented in some detail. Finally, extensions to methods incorporating multi-way relationships among data (e.g., hypergraphs, simplicial complexes) will be discussed.

Part 2: Stochastic Network Optimization and Learning (5 hours, Paolo Di Lorenzo). This part introduces Edge Machine Learning: a new paradigm aimed at solving learning tasks in a distributed fashion from data collected by heterogeneous devices (e.g., smartphones, sensors, drones, etc.) at the edge of the wireless network, while satisfying strict latency/energy constraints imposed by applications (e.g., automated driving, industry 4.0, etc.) foreseen in the 5G roadmap. The course will introduce fundamental tools from convex, nonconvex, and stochastic optimization, which will be used to (i) distribute the machine learning task among several machines, (ii) adaptively learn the joint communication (e.g., power, bits) and computation (e.g., CPU cycles) resource allocation strategy, in order to strike the best trade-off between energy spent by the system and accuracy of the learning tasks, while meeting strict latency constraints.

Textbooks and resources:

[1] Slides

[2] Vetterli, Martin, Jelena Kovačević, and Vivek K. Goyal. Foundations of signal processing. Cambridge University Press, 2014.

[3] S. Foucart and R. Holger, A mathematical introduction to compressive sensing, Basel: Birkhäuser, 2013.

[4] E.J. Candès et al., Exact matrix completion via convex optimization, Foundations of Computational mathematics, 9(6), 717-772, 2009.

[5] Sidiropoulos, Nicholas D., et al. Tensor decomposition for signal processing and machine learning, IEEE Transactions on Signal Processing, vol. 65, n. 13, pp. 3551-3582, 2017.

[6] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004;

[7] M.E.J. Newman, Networks: An Introduction, Oxford, UK: Oxford University Press.

[8] P. Di Lorenzo, S. Barbarossa, and P. Banelli, Sampling and Recovery of Graph Signals, Cooperative and Graph Signal Processing, P. Djuric and C. Richard Eds., Elsevier, 2018.

[9] S. Boyd et al., Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends in Machine Learning, 3(1):1–122, 2011.

[10] Neely, M. J., Stochastic network optimization with application to communication and queueing systems, Synthesis Lectures on Communication Networks, 3(1), 1-211, 2010.

[10] CVX software for convex optimization.