Aggregation rules are the cornerstone of distributed (or federated) learning in the presence of adversaries, under the so-called Byzantine threat model. They are also interesting mathematical objects from the point of view of robust mean estimation. The Krum aggregation rule has been extensively studied, and endowed with formal robustness and convergence guarantees. Yet, MultiKrum, a natural extension of Krum, is often preferred in practice for its superior empirical performance, even though no theoretical guarantees were available until now. In this work, we provide the first proof that MultiKrum is a robust aggregation rule, and bound its robustness coefficient. To do so, we introduce κ*, the optimal robustness coefficient of an aggregation rule, which quantifies the accuracy of mean estimation in the presence of adversaries in a tighter manner compared with previously adopted notions of robustness. We then construct an upper and a lower bound on MultiKrum's robustness coefficient. As a by-product, we also improve on the best-known bounds on Krum's robustness coefficient. We show that MultiKrum's bounds are never worse than Krum's, and better in realistic regimes. In the full paper, we also illustrate this analysis by an experimental investigation on the quality of the lower bound.

If you tell a learning model that you prefer an alternative $a$ over another alternative $b$, then you probably expect the model to be *monotone*, that is, the valuation of $a$ increases, and that of $b$ decreases. Yet, perhaps surprisingly, many widely deployed comparison-based preference learning models, including large language models, fail to have this guarantee. Until now, the only comparison-based preference learning algorithms that were proved to be monotone are the Generalized Bradley-Terry models. Yet, these models are unable to generalize to uncompared data. In this paper, we advance the understanding of the set of models with generalization ability that are *monotone*. Namely, we propose a new class of Linear Generalized Bradley-Terry models with Diffusion Priors, and identify sufficient conditions on alternatives' embeddings that guarantee monotonicity. Our experiments show that this monotonicity is far from being a general guarantee, and that our new class of generalizing models improves accuracy, especially when the dataset is limited.

Many applications, e.g. in content recommendation, sports, or recruitment, leverage the comparisons of alternatives to score those alternatives. The classical Bradley-Terry model and its variants have been widely used to do so. The historical model considers binary comparisons (victory/defeat) between alternatives, while more recent developments allow finer comparisons to be taken into account. In this article, we introduce a probabilistic model encompassing a broad variety of paired comparisons that can take discrete or continuous values. We do so by considering a well-behaved subset of the exponential family, which we call the family of generalized Bradley-Terry (GBT) models, as it includes the classical Bradley-Terry model and many of its variants. Remarkably, we prove that all GBT models are guaranteed to yield a strictly convex negative log-likelihood. Moreover, assuming a Gaussian prior on alternatives' scores, we prove that the maximum a posteriori (MAP) of GBT models, whose existence, uniqueness and fast computation are thus guaranteed, varies monotonically with respect to comparisons (the more A beats B, the better the score of A) and is Lipschitz-resilient with respect to each new comparison (a single new comparison can only have a bounded effect on all the estimated scores). These desirable properties make GBT models appealing for practical use. We illustrate some features of GBT models on simulations.

MOTIVATION: Rotated template matching is an efficient and versatile algorithm to analyze microscopy images, as it automates the detection of stereotypical structures, such as organelles that can appear at any orientation. Its performance however quickly degrades in noisy image data. RESULTS: We introduce Steer'n'Detect, an ImageJ plugin implementing a recently published algorithm to detect patterns of interest at any orientation with high accuracy from a single template in 2D images. Steer'n'Detect provides a faster and more robust substitute to template matching. By adapting to the statistics of the image background, it guarantees accurate results even in the presence of noise. The plugin comes with an intuitive user interface facilitating results analysis and further post-processing. AVAILABILITY AND IMPLEMENTATION: https://github.com/Biomedical-Imaging-Group/Steer-n-Detect. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We propose a fast and scalablepolyatomic Frank-Wolfe (P-FW)algorithm for the resolution of high-dimensional LASSO regression problems. This algorithm improves upon traditional Frank-Wolfe methods by considering generalized greedy steps withpolyatomic(i.e.linear combinations of multiple atoms) update directions, hence allowing for a more efficient exploration of the search space. To preserve sparsity of the intermediate iterates, we re-optimize the LASSO problem over the set of selected atoms at each iteration. For efficiency reasons, the accuracy of this re-optimization step is relatively low for early iterations and gradually increases with the iteration count. We provide convergence guarantees for our algorithm and validate it in simulated compressed sensing setups. Our experiments reveal that P-FW outperforms state-of-the-art methods in terms of runtime, both for FW methods and optimal first-order proximal gradient methods such as theFast Iterative Soft-Thresholding Algorithm (FISTA).

In this paper, we precisely quantify the wavelet compressibility of compound Poisson processes. To that end, we expand the given random process over the Haar wavelet basis and we analyse its asymptotic approximation properties. By only considering the nonzero wavelet coefficients up to a given scale, what we call the greedy approximation, we exploit the extreme sparsity of the wavelet expansion that derives from the piecewise-constant nature of compound Poisson processes. More precisely, we provide lower and upper bounds for the mean squared error of greedy approximation of compound Poisson processes. We are then able to deduce that the greedy approximation error has a sub-exponential and super-polynomial asymptotic behavior. Finally, we provide numerical experiments to highlight the remarkable ability of wavelet-based dictionaries in achieving highly compressible approximations of compound Poisson processes.

In contrast to their seemingly simple and shared structure of independence and stationarity, Lévy processes exhibit a wide variety of behaviors, from the self-similar Wiener process to piecewise-constant compound Poisson processes. Inspired by the recent paper of Ghourchian, Amini, and Gohari, we characterize their compressibility by studying the entropy of their double discretization (both in time and amplitude) in the regime of vanishing discretization steps. For a Lévy process with absolutely continuous marginals, this reduces to understanding the asymptotics of the differential entropy of its marginals at small times, for which we obtain a new local central limit theorem. We generalize known results for stable processes to the non-stable case, with a special focus on Lévy processes that are locally self-similar, and conceptualize a new compressibility hierarchy of Lévy processes, captured by their Blumenthal–Getoor index.

We provide a complete pipeline for the detection of patterns of interest in an image. In our approach, the patterns are assumed to be adequately modeled by a known template, and are located at unknown positions and orientations that we aim at retrieving. We propose a continuous-domain additive image model, where the analyzed image is the sum of the patterns to localize and a background with self-similar isotropic power-spectrum. We are then able to compute the optimal filter fulfilling the SNR criterion based on one single template and background pair: it strongly responds to the template while being optimally decoupled from the background model. In addition, we constrain our filter to be steerable, which allows for a fast template detection together with orientation estimation. In practice, the implementation requires to discretize a continuous-domain formulation on polar grids, which is performed using quadratic radial B-splines. We demonstrate the practical usefulness of our method on a variety of template approximation and pattern detection experiments. We show that the detection performance drastically improves when we exploit the statistics of the background via its power-spectrum decay, which we refer to as spectral-shaping. The proposed scheme outperforms state-of-the-art steerable methods by up to 50% of absolute detection performance.

We propose a novel sparse dictionary learning method for planar shapes in the sense of Kendall, namely configurations of landmarks in the plane considered up to similitudes. Our shape dictionary method provides a good trade-off between algorithmic simplicity and faithfulness with respect to the nonlinear geometric structure of Kendall's shape space. Remarkably, it boils down to a classical dictionary learning formulation modified using complex weights. Existing dictionary learning methods extended to nonlinear spaces map the manifold either to a reproducing kernel Hilbert space or to a tangent space. The first approach is unnecessarily heavy in the case of Kendall's shape space and causes the geometrical understanding of shapes to be lost, while the second one induces distortions and theoretical complexity. Our approach does not suffer from these drawbacks. Instead of embedding the shape space into a linear space, we rely on the hyperplane of centered configurations, including preshapes from which shapes are defined as rotation orbits. In this linear space, the dictionary atoms are scaled and rotated using complex weights before summation. Furthermore, our formulation is more general than Kendall's original one: it applies to discretely defined configurations of landmarks as well as continuously defined interpolating curves. We implemented our algorithm by adapting the method of optimal directions combined to a Cholesky-optimized order recursive matching pursuit. An interesting feature of our shape dictionary is that it produces visually realistic atoms, while guaranteeing reconstruction accuracy. Its efficiency can mostly be attributed to a clear formulation of the framework with complex numbers. We illustrate the strong potential of our approach for the characterization of datasets of shapes up to similitudes and the analysis of patterns in deforming two-dimensional shapes.

We propose a discretization method for continuous-domain linear inverse problems with multiple-order total-variation (TV) regularization. It is based on a recent result that proves that such inverse problems have sparse polynomial-spline solutions. Our method consists in restricting the search space to splines with knots on a uniform grid, which results in a standard convex finite-dimensional problem. As basis functions for this search space, we use the B-splines matched to the regularization order, which are optimally localized. This leads to a well-conditioned, computationally feasible optimization task. Our proposed iterative multiresolution algorithm then refines the grid size until a desired level of accuracy is met and converges to sparse solutions of our inverse problem. Finally, we present experimental results that validate our approach.

The detection of landmarks or patterns is of interest for extracting features in biological images. Hence, algorithms for finding these keypoints have been extensively investigated in the literature, and their localization and detection properties are well known. In this paper, we study the complementary topic of local orientation estimation, which has not received similar attention. Simply stated, the problem that we address is the following: estimate the angle of rotation of a pattern with steerable filters centered at the same location, where the image is corrupted by colored isotropic Gaussian noise. For this problem, we propose an estimator formulated as linear combinations of circular harmonics with given radial profiles. We prove that the proposed estimator is unbiased. This property allows us to use a statistical framework based on the Cramér--Rao lower bound (CRLB) to study the limits on the accuracy of the corresponding class of estimators. We aim at evaluating the performance of detection methods based on steerable filters in terms of angular accuracy (as a lower bound), while considering the connection to maximum likelihood estimation. Beyond the general results, we analyze the asymptotic behavior of the lower bound in terms of the order of steerablility and propose an optimal subset of components that minimizes the bound. We define a mechanism for selecting optimal subspaces of the span of the detectors. These are characterized by the most relevant angular frequencies. Finally, we project our template to the span of circular harmonics with given radial profiles and experimentally show that the prediction accuracy achieves the predicted CRLB. As an extension, we also consider steerable wavelet detectors.

We study continuous-domain linear inverse problems with generalized total-variation (gTV) regularization, expressed in terms of a regularization operator L. It has recently been proved that such inverse problems have sparse spline solutions, with fewer jumps than the number of measurements. Moreover, the type of spline solely depends on L (L-splines) and is independent of the measurements. The continuous-domain inverse problem can be recast in an exact way as a finite-dimensional problem by restricting the search space to splines with knots on a uniform finite grid. However, expressing the L-spline coefficients in the dictionary basis of the Green's function of L is ill-suited for practical problems due to its infinite support. Instead, we propose to formulate the problem in the B-spline dictionary basis, which leads to better-conditioned problems. As we make the grid finer, we show that a solution of the continuous-domain problem can be approached arbitrarily closely with functions of this search space. This result motivates our proposed multiresolution algorithm, which computes sparse solutions of our inverse problem. We demonstrate that this algorithm is computationally feasible for 1D signals when L is an ordinary differential operator.

We introduce a new model of parametric contours defined in a continuous fashion. Our curve model relies on Hermite spline interpolation and can easily generate curves with sharp discontinuities; it also grants direct access to the tangent at each location. With these two features, the Hermite snake distinguishes itself from classical spline-snake models and allows one to address certain bioimaging problems in a more efficient way. More precisely, the Hermite snake construction allows introducing sharp corners in the snake curve and designing directional energy functionals relying on local orientation information in the input image. Using the formalism of spline theory, the model is shown to meet practical requirements such as invariance to affine transformations and good approximation properties. Finally, the dependence on initial conditions and the robustness to the noise is studied on synthetic data in order to validate our Hermite snake model, and its usefulness is illustrated on real biological images acquired using brightfield, phase-contrast, differential-interference-contrast, and scanning-electron microscopy.

We present a theoretical analysis and comparison of the effect of l1versus l2regularization for the resolution of ill-posed linear inverse and/or compressed sensing problems. Our formulation covers the most general setting where the solution is specified as the minimizer of a convex cost functional. We derive a series of representer theorems that give the generic form of the solution depending on the type of regularization. We start with the analysis of the problem in finite dimensions and then extend our results to the infinite-dimensional spaces l2(Z) and l1(Z). We also consider the use of linear transformations in the form of dictionaries or regularization operators. In particular, we show that the l2solution is forced to live in a predefined subspace that is intrinsically smooth and tied to the measurement operator. The l1solution, on the other hand, is formed by adaptively selecting a subset of atoms in a dictionary that is specified by the regularization operator. Beside the proof that l1solutions are intrinsically sparse, the main outcome of our investigation is that the use of l1regularization is much more favorable for injecting prior knowledge: it results in a functional form that is independent of the system matrix, while this is not so in the l2scenario.

It is well documented that natural images are compressible in wavelet bases and tend to exhibit fractal properties. In this paper, we investigate statistical models that mimic these behaviors. We then use our models to make predictions on the statistics of the wavelet coefficients. Following an innovation modeling approach, we identify a general class of finite-variance self-similar sparse random processes. We first prove that spatially dilated versions of self-similar sparse processes are asymptotically Gaussian as the dilation factor increases. Based on this fundamental result, we show that the coarse-scale wavelet coefficients of these processes are also asymptotically Gaussian, provided the wavelet has enough vanishing moments. Moreover, we quantify the degree of Gaussianity by deriving the theoretical evolution of the kurtosis of the wavelet coefficients across scales. Finally, we apply our analysis to one- and two-dimensional signals, including natural images, and show that the wavelet coefficients tend to become Gaussian at coarse scales.

We study the statistics of wavelet coefficients of non-Gaussian images, focusing mainly on the behaviour at coarse scales. We assume that an image can be whitened by a fractional Laplacian operator, which is consistent with an ∥ω∥-γspectral decay. In other words, we model images as sparse and self-similar stochastic processes within the framework of generalised innovation models. We show that the wavelet coefficients at coarse scales are asymptotically Gaussian even if the prior model for fine scales is sparse. We further refine our analysis by deriving the theoretical evolution of the cumulants of wavelet coefficients across scales. Especially, the evolution of the kurtosis supplies a theoretical prediction for the Gaussianity level at each scale. Finally, we provide simulations and experiments that support our theoretical predictions.