Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm

• Outlying curves in large, high-dimensional samples may corrupt the mean trajectory, motivating robust alternatives.Source: §1 · p. 2
• Because the median objective is differentiable everywhere when the distribution has no atoms, the paper uses online stochastic gradients and extends the study to geometric quantiles.Source: §1 · p. 3
• The paper states almost-sure consistency and L2 convergence rates for stochastic-gradient estimators, while the averaged estimator is asymptotically normal with the same distribution as classical estimators.Source: §1 · p. 3
• The study compares the estimator with Vardi and Zhang’s static algorithm at equal sample size and computation time, and analyzes a one-day television-audience example.Source: §1 · pp. 2–3

2.1 Definitions and assumptions

• The median is defined for H-valued observations without requiring a finite first moment of their norm.Source: §2.1 · p. 4
• A1 rules out distributions concentrated on a straight line and ensures uniqueness, while A2 models X as a mixture of two “nice” distributions, including a discrete component.Source: §2.1 · p. 4

2.2 Some convexity and robustness properties of the median

• Under A1 and A2, the objective is strictly convex throughout H and strongly convex on bounded sets.Source: §2.2 · p. 6
• The geometric median also has bounded gross error sensitivity in a separable Hilbert space.Source: §2.2 · p. 7

2.3 The algorithms

• The proposed stochastic-gradient algorithm estimates the objective’s gradient from each observation, and its averaged version averages the past estimates.Source: §2.3 · pp. 7–8

3.1 Almost sure convergence of the stochastic gradient algorithm

• Under (A1) and (A2) and the stated step-size conditions, the stochastic-gradient estimates Z_n converge almost surely to m.The rate results additionally require (A3), which controls the difference between G and its quadratic approximation near m.Source: §3.1 · p. 9, §3.2 · p. 10

3.2 Rates of convergence and asymptotic normality

• On events of arbitrarily high probability, Z_n attains the classical quadratic-mean convergence rates up to a logarithmic factor.The rate statement is given under (A1), (A2), and (A3).Source: §3.2 · pp. 9–10
• The averaged estimator Z_n and classic static estimator b_mn have the same asymptotic distribution, making the averaged estimator first-order efficient relative to the slower static estimator.The theorem assumes (A1), (A2), and (A3).Source: §3.2 · p. 10

4.1 A simulation study

• The simulation study compares the averaged stochastic estimator with Vardi and Zhang’s static estimator across sample sizes and from a second perspective intended for settings where computation time matters.The study runs 1000 simulations at sample sizes 250, 500, and 2000.Source: §4.1 · p. 10, §4.1.1 · p. 11

4.1.1 Fixed sample sizes

• For fixed sample sizes, the averaged procedure performs well against Vardi–Zhang, which gives only slightly better estimates, and is not very sensitive to c_γ values from 2 to 75.The simulation compares estimation errors across sample sizes and tuning values; Table 1 presents the error statistics.Source: §4.1.1 · p. 11, Table 1 · p. 12

4.1.2 Fixed computation time

• At n=1000, the averaged estimator is about 30 times faster than the static procedure when both are coded in the same language.Both algorithms have O(nd) computation time; the averaged approach is reported as much faster on the same computer.Source: §4.1.2 · pp. 11–12
• In one second, the Vardi–Zhang estimator handles 150 observations, while the averaged algorithm can handle at least 90,000.The comparison concerns sample sizes handleable under the same fixed time budget.Source: §4.1.2 · p. 12

4.2 Estimation of the median television audience profile

• The television-audience application produces a geometric-median profile with the same three-peak shape as the mean, but smaller estimated values.The median profile is reported as less sensitive to small perturbations and outliers; the averaged algorithm converged in under a minute, while memory constraints prevented the static estimate.Source: §4.2 · p. 13

5 Concluding remarks

• For large samples with potential outliers, online stochastic-gradient methods can update recursively under fixed computation budgets and handle larger samples.Source: §5 · p. 13
• The averaged recursive estimators are reported to be much more accurate than static procedures and not very sensitive to tuning parameter cγ.Source: §5 · p. 13
• Resampling methods such as bootstrap could approximate the asymptotic distribution and build pointwise intervals, but rigorous validation is outside the paper’s scope.Source: §5 · p. 13
• Online clustering is a possible extension via an adapted MacQueen algorithm; despite its nonconvex criterion, stochastic-gradient approaches converge almost surely to stationary points.Source: §5 · pp. 13–14
• With real covariates such as age or city size, conditional geometric medians are a further direction for fast, sequentially estimated varying-time regression models.Source: §5 · p. 14
• Because independence is rarely satisfied in real studies, determining which dependence conditions preserve Theorems 3.1 and 3.4 remains open.Source: §5 · p. 14

6.1 Convexity — Proofs of Proposition 2.1 and Corollary 2.2

• The proofs establish Φ as a subgradient of G and derive the convexity bounds using assumption (A1), which rules out support on a line.The corollary follows from Proposition 2.1 and the subgradient property.Source: §6.1 · pp. 14–15

6.2 Proof of Theorem 3.1.

• The proof shows that the squared distance from Zn to m converges almost surely to zero, establishing the consistency conclusion of Theorem 3.1.It first proves almost-sure convergence to a finite random limit, then rules out any nonzero limit.Source: §6.2 · pp. 15–17

6.3 Proof of Lemma 3.3 and Proposition 3.2

• The proof notes that the smallest eigenvalue λmin of Γm is strictly positive, identifies a gradient part going to m and a noise part, and names Rn as the error term.It concludes the induction step and the proof of Proposition 3.2.Source: §6.3 · pp. 18, 19, 23

6.4 Proof of Theorem 3.4

• The proof of Theorem 3.4 follows Pelletier's decomposition, linearizing Φ around the true value m to analyze the error.The passage identifies this as a decomposition of the error in equation (21).Source: §6.4 · p. 23
• The proof checks the martingale central-limit conditions using bounded martingale differences and almost-sure convergence of the covariance operators to Σ.It invokes Theorem 5.1 and condition 5.2 of Jakubowski (1988).Source: §6.4 · p. 24
• The final remainder term converges to zero by Kronecker’s lemma, completing the proof’s control of the residual terms.The decomposition also identifies ξ_k as a martingale difference and δ_k as an error term.Source: §6.4 · pp. 23–25