Bonjour à tous,

Vous êtes cordialement invité.e.s à la soutenance de thèse de Beheshteh Tolouei Rakhshan le lundi 21 septembre à 9h30 EST (mode hybride).

Title : Memory-Efficient Methods for High-Dimensional Computation and Learning: Randomized Methods, Tensor Networks, and Quantized Optimization.

Date: Lundi 21 septembre à 9h30 

Salle: Mila, Auditorium 2, 6650 Rue Saint-Urbain

Jury

Abstract:

Modern artificial intelligence and scientific computing are increasingly limited not by what we can compute but by what we can afford to store. Ever-larger models and inherently high-dimensional data push memory budgets to their limits: storing parameters, gradients, optimizer states, and high-order tensors whose size grows exponentially with their order has become a central bottleneck for both training and deployment. This thesis develops memory-friendly methods: algorithms that drastically shrink the memory footprint of high-dimensional computation while provably preserving the information that matters. The unifying idea is to compute over a smaller and faithful surrogate of the object at hand, built from three complementary instruments: randomized algorithms, tensor network methods, and quantization.

The first contribution bridges the gap between randomized methods and tensor decompositions. We propose tensorized random projection (RP) maps by enforcing the low-rank Tensor Train (TT) and CANDECOMP/PARAFAC (CP) formats on the rows of the dense Gaussian random projection matrix. This reduces the memory of the projection from exponential to linear in the order of a tensor while approximately preserving Euclidean distances. We prove that both maps are valid Johnson–Lindenstrauss transforms, and that the TT format requires a considerably smaller embedding for a given distortion compared to the CP format.

The second contribution pushes randomness into Alternating Least Squares (ALS), the workhorse of tensor decomposition. By maintaining the canonical form of the TT decomposition at every iteration, we sample from its exact leverage scores in time logarithmic in the tensor size, turning each least-squares solve into a small sketched problem with strong error guarantees and yielding large speed-ups on massive dense and sparse tensors.

The third contribution explores the training of large language models (LLMs) using reduced-precision computation. We introduce Q-SOAP, a quantized second-order optimizer that compresses weights, activations, gradients, preconditioners, and moments to INT8 and INT4. It also encodes the skewed second moment through a non-linear blockwise codebook, and uses stochastic rounding to accumulate updates faithfully in low precision, while matching full-precision accuracy at a fraction of the memory.

The fourth contribution steps back to tensor network methods and presents the graphical language underlying these methods. We present the Tensor Cookbook, a self-contained development of tensor algebra, decompositions, gradients, and high-dimensional probability entirely through tensor network diagrams, showing that the diagrammatic approach yields genuinely shorter and more transparent proofs for classical identities.

Together, these contributions show that exploiting randomness, tensor network methods, and reduced precision makes large-scale learning and high-dimensional computation substantially more tractable, without sacrificing fidelity.