We develop a coreset for robust geometric median, reducing size dependency on outliers.
problem Robust geometric median problem in Euclidean space with outliers.
method Construction of a compact coreset with size dependency on m eliminated. result Elimination of O(m) dependency in coreset size, achieving O(ε−2⋅min{ε−2,d}) size. Convex cores found for group actions on median spaces.
problem Understanding group actions on median spaces without metric or topology.
method Introduced convex cores for actions on finite-rank median algebras.
result Actions on median spaces have nonempty convex cores.
We prove a version of the Tits alternative for groups acting on complete, finite rank median spaces. This shows that group actions on finite rank median spaces are much more restricted than actions on general median spaces. Along the way, we extend to median spaces the Caprace-Sageev machinery and part of Hagen's theor…
Algorithm identifies best arm in bandit game with variance consideration.
problem Identifying the best arm in a stochastic multi-armed bandit game with varying variances.
method Adaptive algorithm using grouped median elimination to explore gaps and variances.
result Guarantees to output the best arm with probability (1-δ) using optimal number of samples.
Groups with specific properties have similar cubulations and coarse median structures.
problem Understanding the structure of certain groups through cubical coarsening.
method Analyzing right-angled Artin and Coxeter groups, focusing on automorphisms and cubulations.
result Automorphisms of specific groups preserve coarse median structures and have nice fixed subgroups.
Unique median structures found in hyperbolic spaces.
problem Uniqueness of median structures in hyperbolic spaces.
method Analyzing product of hyperbolic spaces and properties of relative hyperbolicity.
result Non-hyperbolic pants graphs can have unique median structures.
The paper studies automorphisms of RAAGs and RACGs, proving properties of their fixed subgroups.
problem Fixed subgroups of automorphisms of RAAGs and RACGs.
method Introducing coarse-median preserving automorphisms and proving properties of fixed subgroups.
result Fixed subgroups of RAAGs and RACGs are finitely generated, undistorted, and quasi-convex.
Study cup products on CAT(0) cube complexes, proving quasimorphisms' vanishing results.
problem Understanding cup products in higher bounded cohomology groups.
method Extending vanishing results from Brooks quasimorphisms to median quasimorphisms on CAT(0) cube complexes.
result Vanishing results for cup products of median quasimorphisms on CAT(0) cube complexes.
We show that uniform lattices of isometries of products of real hyperbolic spaces act properly discontinuously and cocompactly on a median space. For lattices in products of at least two factors, this is the strongest degree of compatibility possible with the median geometry. Our theorem is also relevant for potential …
Distributed model training is vulnerable to byzantine system failures and adversarial compute nodes, i.e., nodes that use malicious updates to corrupt the global model stored at a parameter server (PS). To guarantee some form of robustness, recent work suggests using variants of the geometric median as an aggregation r…
Study of automorphisms and splittings of special groups, showing infinite groups under certain conditions.
problem Understanding the structure and automorphisms of special groups G. method Constructing and analyzing non-small, stable G-actions on R-trees. result Conditions for the existence of infinite-order automorphisms and splittings.
Finite rank median spaces are a simultaneous generalisation of finite dimensional CAT(0) cube complexes and real trees. If Γ is an irreducible lattice in a product of rank one simple Lie groups, we show that every action of Γ on a complete, finite rank median space has a global fixed point. This is in sharp…
Proposes a robust clustering method using the Median-of-Means estimator.
problem Noise and outliers in data affect clustering quality and require specifying the number of clusters.
method Integrates model-based and centroid-based clustering methods using the Median-of-Means estimator.
result Mitigates noise effects and estimates the number of clusters automatically.
Study shows how certain spaces can be mapped to R^n with specific properties.
problem Characterizing and mapping locally compact median spaces of finite rank.
method Analyzing the combinatorics of halfspaces and properties of isometric actions.
result Spaces with certain actions are isometric to R^n, and orbits are discrete.
We study the construction of quasimorphisms on groups acting on trees introduced by Monod and Shalom, that we call median quasimorphisms, and in particular we fully characterise actions on trees that give rise to non-trivial median quasimorphisms. Roughly speaking, either the action is highly transitive on geodesics, i…
Unified framework for mean testing under truncation bias.
problem High-dimensional mean testing under arbitrary truncation.
method Characterizes fundamental limits and develops a simple second-order test.
result Unified framework connects finite-moment, sub-Gaussian, and median-regular structural regimes.
The main goal of this paper is a detailed study of asymptotic cones of the mapping class groups. In particular, we prove that every asymptotic cone of a mapping class group has a bi-Lipschitz equivariant embedding into a product of real trees, sending limits of hierarchy paths onto geodesics, and with image a median su…
An extended Study of Dunwoody's Construction and Sageev's Theorem
Algorithm identifies Pareto set in bandits with contaminated feedback.
problem Identifying Pareto set in multi-objective bandits with adversarial contamination.
method Sample median-based multi-objective adaptive elimination algorithm.
result Sample complexity bound that depends on contamination probability.
We study commensurating actions of groups and the associated properties FW and PW, in connection with wallings, median graphs, CAT(0) cubings and multi-ended Schreier graphs.
Continuous Sweep improves binary quantifier performance.
problem Estimating class prevalence in datasets.
method Parametric binary quantifier inspired by Median Sweep, using parametric class distributions and mean of Adjusted Count estimates.
result Continuous Sweep outperforms other quantifiers in simulations and empirical data analysis.
Study the geometry of graph product extension graphs.
problem Properties of graph products.
method Introduce and study the extension graph of graph products of groups.
result Extension graph is isomorphic to crossing graph of a quasi-median graph and exhibits asymptotic dimension similar to quasi-trees.
We construct compactifications for median spaces with compact intervals, generalising Roller boundaries of CAT(0) cube complexes. Examples of median spaces with compact intervals include all finite rank median spaces and all proper median spaces of infinite rank. Our methods also work for general median algebra…
Generators found for automorphisms of special groups.
problem Characterizing automorphisms of special groups.
method Using a novel hierarchical shortening argument, the paper provides generators for automorphisms of special groups.
result Generators for automorphisms of special groups are found, including Dehn twists and pseudo-twists.
New concept of coarse medians for higher rank symmetric spaces.
problem Understanding medians in higher rank symmetric spaces.
method Introducing coarse r-median spaces and proving their existence. result Existence of coarse higher medians on divisible and quasi-homogeneous convex domains.
Study on median algebra structures on Euclidean spaces and manifolds with local CAT(0) cubulation.
problem Understanding median algebra structures on Euclidean spaces and manifolds.
method Showed local CAT(0) cubulation for median structures on ER homology manifolds.
result Median structures on ER homology manifolds have a local CAT(0) cubulation structure.
Paper addresses fault-tolerance in distributed machine learning with stochastic gradient descent.
problem Fault-tolerance in distributed stochastic gradient descent (D-SGD) for machine learning.
method Proposes norm-based comparative gradient elimination (CGE) to robustify D-SGD against Byzantine faulty agents.
result CGE guarantees fault-tolerance against a bounded fraction of Byzantine agents under standard stochastic assumptions.
Study on connectivity and geometry of random Coxeter groups.
problem Connectivity threshold for square percolation on random graphs.
method Probabilistic combinatorics and techniques from geometric group theory.
result Determines connectivity threshold and cubical coarse median structure for random Coxeter groups.
We introduce and begin to explore the mean and median of finite sets of shapes represented as integral currents. The median can be computed efficiently in practice, and we focus most of our theoretical and computational attention on medians. We consider questions on the existence and regularity of medians. While the me…
New method for summarizing ranking distributions using consensus ranking distributions.
problem Summarizing ranking distributions efficiently and accurately.
method Introducing consensus ranking distributions and a top-down tree-structured statistical algorithm.
result Optimal distortion can be expressed as a function of pairwise probabilities, enabling efficient learning methods.
This paper is a short summary of our recent work on the medians and means of probability measures in Riemannian manifolds. Firstly, the existence and uniqueness results of local medians are given. In order to compute medians in practical cases, we propose a subgradient algorithm and prove its convergence. After that, F…
A method for estimating the median of gradients in stochastic optimization.
problem Robust gradient estimation in stochastic optimization for various applications.
method Stochastic Proximal Point Method for median gradient estimation.
result The proposed method can converge even under heavy-tailed, state-dependent noise.
This paper introduces online algorithms to estimate robust geometric median in large data streams.
problem Detecting outliers in large data sets using robust statistical measures.
method Online stochastic Newton methods for estimating the geometric median.
result Rates of convergence for online estimation of the geometric median.
Useful alpha returns vanished in modern stock markets.
problem The inefficiency of modern stock markets in generating useful alpha.
method Analysis of 200 published long-short anomaly equity portfolios over different time periods and stock selection criteria.
result Even modest allowances for luck or transaction costs eliminated published academic anomalies.
The study finds that maximizing median returns is the only viable strategy in portfolio selection.
problem Difficulties in studying optimal portfolio strategies due to discontinuity and time inconsistency in maximizing median and quantile returns.
method Used intra-personal equilibrium approach to analyze portfolio selection under median and quantile maximization.
result Median maximization is the only viable strategy, with no investment in risky assets for other quantiles.
New graph properties inherited by Frechet mean and median.
problem Characterizing the average of graph-valued samples.
method Analysis of Frechet mean and median graphs.
result Edge density is hereditary in Frechet mean and median graphs.
M2M tackles zero-shot structured noise suppression in images.
problem Structured noise with strong anisotropic correlations in real-world images.
method M2M introduces a novel sampling strategy that generates pseudo-independent sub-image pairs from a single noisy input, using directional interpolation and generalized median filtering.
result M2M consistently outperforms state-of-the-art zero-shot methods under correlated noise.
Tukey median performance analyzed under TV corruptions.
problem Performance analysis of Tukey median under TV corruptions.
method Analysis of Tukey median and projection algorithm under TV corruptions.
result Breakdown point reduced to 1/4 under TV corruptions, compared to 1/3 under Huber's model.
The consistency of Fréchet medians is proved for probability measures in proper metric spaces. In the context of Riemannian manifolds, assuming that the probability measure has more than a half mass lying in a convex ball and verifies some concentration conditions, the positions of its Fréchet medians are estimated. It…
New subspace prototype flag median improves clustering on noisy data.
problem Finding robust prototypes for datasets of images and videos.
method Proposes flag median and introduces FlagIRLS algorithm for its calculation.
result Flag median is robust to outliers and improves cluster purity.
In high dimensions, the mean and geometric median are nearly identical.
problem Understanding the relationship between mean and geometric median in high-dimensional spaces.
method Analytical derivation and simulation of the distance between mean and geometric median.
result The distance between mean and geometric median vanishes with dimensionality in high dimensions.
Improved median of means estimator with tighter bounds.
problem Improving the efficiency and reliability of median of means estimator.
method Modification of the median of means estimator with sub-Gaussian deviation bounds.
result Achieves nearly optimal constants under minimal assumptions.
Empirical median performs well in estimating location with varying scales.
problem Estimating location with varying scales in data.
method Analysis of empirical median as an estimator.
result Matching upper and lower bounds on estimation error.
This article is devoted to the problem of predicting the value taken by a random permutation Σ, describing the preferences of an individual over a set of numbered items {1,…,n} say, based on the observation of an input/explanatory r.v. X e.g. characteristics of the individual), when error is measured…
New estimator for symmetric kernel expectations, robust to missing data.
problem Efficient estimation of symmetric kernel expectations with missing data.
method Median-of-Incomplete-U-Statistics (MIU) estimator.
result Established finite-sample concentration rate for MIU.
Median-of-means sampling outperforms mean-of-means for large sample sizes in numerical integration.
problem Improving numerical integration accuracy in high dimensions.
method Median-of-means sampling compared to mean-of-means using RQMC methods.
result Median-of-means sampling is superior for large sample sizes, while mean-of-means is better for smaller sample sizes.
Upper bound for Hausdorff distance between hyperbolic space and its medianization.
problem Calculating the Hausdorff distance between hyperbolic space and its medianization.
method Using de Sitter space to model finite-dimensional hyperbolic space and its medianization, calculating the Hausdorff distance.
result An upper bound for the Hausdorff distance between hyperbolic space and its medianization is calculated.
A method to robustly federate learning with non-i.i.d. data and Byzantine workers.
problem Byzantine workers sending malicious messages in federated learning with non-i.i.d. data.
method Resampling strategy to reduce inner and outer variation, stochastic average gradient, robust geometric median aggregation.
result The method reaches a neighborhood of the optimal solution at a linear convergence rate and learning error depends on the number of Byzantine workers.