Electrical Engineering Systems Seminar

Speaker: Shahar Stein Ioushua

Ph.D. student under the supervision of Prof. Ofer Shayevitz

Sunday, 4^th August 2024, at 15:00

Room 011, Kitot Building, Faculty of Engineering

Problems in Information Theory and High Dimensional Statistics

Abstract

We study problems in information theory and statistics where high-dimension plays a key role. Often in such problems, the near-asymptotic setting enables the use of mathematical tools that are not applicable in low-dimension.

First, we study the problem of counting the number of graphs with a given subgraph distribution.

Le G be a large (simple, unlabeled) dense graph on n vertices. Suppose that we only know, or can estimate, the empirical distribution of the number of subgraphs F that each vertex in G participates in, for some fixed small graph F. How many other graphs would look essentially the same to us, i.e., would have a similar local structure? We derive upper and lower bounds on the number of graphs whose empirical distribution lies close (in the Kolmogorov-Smirnov distance) to that of G. Our bounds are given as solutions to a maximum entropy problem on random graphs of a fixed size k that does not depend on n, under global density constraints.

Next, we study the benefits of batch learning in the overparameterized linear regression setting. Learning algorithms that divide the data into batches are prevalent in many machine-learning applications, typically offering useful trade-offs between computational efficiency and performance. Here, we examine the benefits of batch-partitioning through the lens of a minimum-norm overparameterized linear regression model with isotropic Gaussian features. We suggest a natural small-batch version of the minimum-norm estimator, and derive an upper bound on its quadratic risk, showing it is inversely proportional to the noise level as well as to the overparameterization ratio, for the optimal choice of batch size. In contrast to minimum-norm, our estimator admits a stable risk behavior that is monotonically increasing in the overparameterization ratio, eliminating both the blowup at the interpolation point and the double-descent phenomenon. Interestingly, we observe that this implicit regularization offered by the batch partition is partially explained by feature overlap between the batches. Our bound is derived via a novel combination of techniques, in particular normal approximation in the Wasserstein metric of noisy projections over random subspaces.

השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בדף הנוכחות שיועבר באולם במהלך הסמינר

-נא להירשם בדף הנוכחות לפני תחילת הסמינר-

Electrical Engineering Systems Seminar

Speaker: Rami Zecharia

Ph.D. student under the supervision of Prof. Yuval Shavitt

Wednesday, 14^th August 2024, at 15:00

ZOOM Seminar

https://zoom.us/j/95848279798?pwd=Ar9KnFrcebMaNUkdoOrA76oba6BSVG.1

Meeting ID 958 4827 9798

passcode nPprr9

Routing Algorithms in Benes and CLOS Networks

Abstract

Benes/CLOS architectures are common scalable interconnection networks widely used in backbone routers, data centers, on-chip networks, multi-processor systems, and parallel computers. Recent advances in Silicon Photonic technology, especially in Mach–Zehnder Interferometer (MZI) technology which is the building block for low-cost high-speed 2x2 optical switch, have made Benes networks a very attractive scalable architecture for optical circuit switches.
Numerous routing algorithms for Benes networks were developed starting with sequential routing algorithms with time complexity of O(Nlog₂N) steps and, in some cases, requires backtracking, which makes them even less efficient. Parallel routing algorithms were developed to satisfy the stringent timing requirements of high-performance switching networks and have time complexity of O((log₂N)²). However, their implementation requires O(N²log₂N) wires (termed connectivity complexity), and thus are difficult to scale. Online (Adaptive) routing algorithms do not utilize the re-arrangeable characteristics of a network as they establish a single path at a time without interrupting already established paths. Such online algorithms yield poor utilization, resulting in low throughput and high latency which impedes their usage.

In this thesis, we present three new and improved routing algorithms for Benes network:

• A parallel routing algorithm combined with a unique scalable hardware architecture that supports full and partial input permutations. The algorithm achieves close to 100% utilization for both full and partial input permutations. Time complexity is limited to O((log₂N)²) steps to match the performance of parallel algorithms. The algorithm and architecture allow a reduction of the connectivity complexity to O(N²), a log₂N improvement over previous solutions.
• An engineering approach to the already known sequential routing algorithm along with a unique scalable hardware architecture. The new algorithm supports full and partial input permutations with a significantly lower time complexity of O(N^3/5) and connectivity complexity of O(N²) and achieves 100% complete routing of a given full or partial input permutation with probability of 99.9999%. The achieved time complexity is comparable to parallel algorithms.
• An online (adaptive) routing algorithm achieving significant increase of utilization (number of established paths for a given input permutation) compared to prior work hence increased throughput and reduce latency while operating within the same time complexity as prior works, hence enabling the usage of Benes network based optical switches for a wide range of applications. We further applied this algorithm to CLOS network achieving even higher average utilization as compared to a single Benes network-based switch of the same size. Hence, enabling the usage of large-scale CLOS-based optical networks for various applications.