Seminar from the PhD students of EDMH
By Louise Davy, Romain Therezien, Anna Van Elst

On Thursday 8 October at 2pm, room TBA.

Louise Davy (S2A) : Doing well with less! On Sampling Techniques for Empirical Pairwise Loss Estimation/Minimization

Many machine learning problems, including similarity learning, ranking, and clustering, rely on empirical pairwise loss functions whose quadratic computational cost quickly becomes prohibitive at scale. We demonstrate how a frugal approach that retains only a fraction of the available information on pairs can achieve estimation or optimization performance comparable to that obtained by using all pairs, by leveraging survey sampling techniques. A central finding, supported by both theory and experiments, is that such sampling plans must target pairs directly rather than individual observations. In particular, for pairwise losses between high-dimensional vectors such as embeddings in vision or graph learning, assigning higher inclusion probabilities to informative pairs using suitable auxiliary information yields performance close to full pairwise evaluation, providing a principled and theoretically grounded trade-off between accuracy and computational cost.

Romain Therezien (S2A) : On Pairwise Quantile Regression - Statistical Guarantees and Applications

Quantile regression is a powerful tool for analyzing the conditional distribution of a response variable beyond its mean, especially in the presence of high variability. We extend the methodology to pairwise settings, where the response is a similarity score between two observations and the predictors are their associated covariates. We introduce a pairwise quantile regression framework based on the pinball loss and establish theoretical guarantees, including generalization bounds and fast learning rates using concentration results for U-processes. Simulations confirm the validity of the approach, while an application to facial recognition demonstrates its usefulness for understanding and characterizing similarity-scoring errors in biometric systems. ng, hiking, and photography.

Anna Van Elst (S2A) : Robust and Decentralized Machine Learning

The increasing availability of computational resources at the edge creates new opportunities for machine learning beyond centralized data centers. Decentralized learning enables distributed agents to learn collaboratively through peer-to-peer communication, but raises fundamental challenges in achieving robustness, communication and memory efficiency, and tolerance to asynchrony. We focus in particular on robust statistical estimation, where standard gossip methods based on averaging are highly sensitive to outliers, while robust alternatives such as medians and trimmed means are difficult to compute using only local pairwise interactions. We develop GoRank, a gossip-based algorithm for decentralized rank estimation, and GoTrim, a fully decentralized algorithm for trimmed-mean estimation over arbitrary communication graphs. GoRank reconstructs global ordering information through pairwise comparisons and random-walk propagation, while GoTrim builds upon this primitive to enable robust aggregation without centralized coordination. Both methods are accompanied by non-asymptotic convergence guarantees, including O(1/t) rates and explicit dependence on network connectivity through the spectral gap. More recently, we develop Goal-PD, an asynchronous gossip algorithm for decentralized nonsmooth convex optimization that can be applied to median estimation by exploiting its optimization-based characterization through the pinball loss. Goal-PD requires only constant memory per node, addressing a major limitation of existing asynchronous decentralized optimization methods that require additional state variables. We prove almost-sure convergence to a minimizer of the underlying optimization problem and linear convergence when the functions are piecewise linear-quadratic, a class that includes the pinball loss used for median estimation. Our experiments show faster convergence on median estimation than existing asynchronous baselines while requiring substantially less memory. Together, these results lay the foundation for robust decentralized learning under memory, communication, and asynchronous constraints.