Embedded Files
Computing Nonlinear Functions over Communication Networks
SENSIBILITÉ describes a novel theory for distributed computing of nonlinear functions over communication networks. Motivated by the long-lasting open challenge to invent technologies that scale with the network size, this intriguing and far-reaching theory elevates distributed encoding and joint decoding of information sources, to the critical network computing problem for a class of network topologies and a class of nonlinear functions of dependent sources. Our theory will elevate distributed communication to the realm of distributed computation of any function over any network.
Our research focuses on distributed computation, in the presence of structured and correlated data, and in the presence of limited network capacity. This captures a variety of distributed computing and distributed learning scenarios of interest. My approach aims to fuse a computer science-inspired view of distributed computing with the rigorous machinery of information theory, and the clever design stemming from coding theory.
Our SENSIBILITÉ team has used some of the most recent and, in many ways, subtle results in information theory to devise a theoretically motivated look at the central problem of coordinating computation and caching in networks. Most recently, we have been researching in the direction of distributed compression of information for computing functions over communication networks, exploiting graph theory and function representations in computer science, as well as coding and information theory, toward a novel perspective on the fundamental underpinnings of computation and communications in networks. This research paves the way for unraveling the tradeoffs between communication rate and computation cost.
CONTRIBUTIONS
Our major research contributions in the context of SENSIBILITÉ include the following:
(Secure distributed nonlinear computations from a communication and computational complexity standpoint.) D. Malak, ``Structured Codes for Distributed Matrix Multiplication," submitted, Dec. 2024.
In the first part of this work, we develop encoding schemes for distributed source compression tailored to nonlinear transformations, including inner products, symmetric matrix products, and general square matrix products over finite fields. Our approach combines nonlinear mappings of distributed sources A and B with the structured linear encoding scheme by Körner and Marton, ensuring distributed computation without requiring full data disclosure. We derive achievable and converse bounds on the sum rate for distributed computation of inner products <A, B> and general matrix products A'B, accommodating non-commutative or asymmetric source matrices. Leveraging the lower bounds on the communication cost set by Han-Kobayashi (given by H(A | B)+H(B | A)), and Slepian-Wolf (given by H(A , B)), and our generalization of the scheme of Körner-Marton that captures the structure of matrix computation with a sum rate given by
where \oplus_q denotes the modulo-q sum of the nonlinear source mappings g1 and g2, respectively, where
we demonstrate unbounded compression gains over Slepian-Wolf coding in cases with specific source correlations, validated by analytical and simulation-based evidence, conditions for rate savings with less stringent correlation structures, and when the sum rate can drop below twice the entropy (given by 2H(A'B)) of the target computation. Furthermore, we upper bound the multiplicative gaps from the lower bounds established by Han-Kobayashi.
In the second part, we introduce a new class of polynomial codes ---structured polynomial codes (StPolyDot codes) --- designed for distributed matrix multiplication in a master-workers-receiver framework. We analyze storage costs for workers alongside end-to-end communication and computation costs, and extend StPolyDot codes to support both chain matrix multiplications and information-theoretically secure computations. Our results show that, by leveraging Körner-Marton's distributed scheme, StPolyDot codes retain the optimality of the communication cost of Dutta et al.'s approach within a factor of 2. Notably, StPolyDot codes achieve this even for distributed master nodes with only a bounded increase in computation cost, inversely proportional to the memory parameter.
(Scalable nonlinear function computation in the presence of structured data and limited rate.) D. Malak, M. R. Deylam Salehi, B. Serbetci, P. Elia, ``Multi-Server Multi-Function Distributed Computation," ENTROPY (Special issue: ``Foundations of Goal-Oriented Semantic Communication in Intelligent Networks"), vol. 26, no. 6, p. 448, Jun. 2024.
The work here studies the communication cost for a multi-server multi-task distributed computation framework, and does so for a broad class of functions and data statistics. Considering the framework where a user seeks the computation of multiple complex (conceivably non-linear) tasks from a set of distributed servers, we establish communication cost upper bounds for a variety of data statistics, function classes and data placements across the servers.
To do so, we proceed to apply, for the first time here, K{\"o}rner's characteristic graph approach --- which is known to capture the structural properties of data and functions --- to the promising framework of multi-server multi-task distributed computing. Going beyond the general expressions, and in order to offer clearer insight, we also consider the well-known scenario of cyclic dataset placement and linearly separable functions over the binary field, in which case our approach exhibits considerable gains over the state of art. Similar gains are identified for the case of multi-linear functions.
NEWS
I am honored to be awarded the ERC Starting Grant for my project SENSIBILITÉ at the intersection of computation and information theory (read our blog).
Recipient of the European Research Council (ERC) 2022 Starting Grant on a research proposal titled, ``Computing Nonlinear Functions over Communication Networks (SENSIBILITÉ)", 2023-2028.
Google Sites
Report abuse