Sequential Euclidean connections with exponential memory: distributional performance and adversarial robustness

Abstract

Points in the unit ball of ${\mathbb{R}}^d$ are processed sequentially. Each new point $p_i$ is connected to a state $x_{i-1}$ that summarizes earlier observations, after which $x_i=\gamma x_{i-1}+(1-\gamma )p_i$, with $0\le \gamma \le 1$. The cost is the sum of the $\alpha$-powers of the connection lengths. This constant-gain rule interpolates between the input-order path and the star centered at the initial point. For independent uniform points, we establish the stationary insertion-length distribution and prove that it decreases in stochastic order as $\gamma$ increases. If $d+\alpha >2$, or if $(d,\alpha )=(1,1)$, the optimal constant parameter satisfies $1-{\gamma }_N^{\ast }=\Theta (N^{-1/2})$, with an explicit asymptotic constant and closed bounds. For $\alpha =1$, its leading expected tree length equals that of the center star and is eventually smaller than the expected lengths of both endpoint constructions. For $\alpha =2$, the optimizer is unique and characterized exactly. For the same $N$, choosing $1-{\gamma }_N$ as a fixed positive multiple of $N^{-1/2}$ gives a sharp two-term expansion of the expected uniform-input cost and a maximal adversarial mean cost of $1+O(N^{-1/2})$. For every fixed $0\le \gamma <1$ and $0<\alpha \le 3$, the exact asymptotic adversarial value is $(2/(1+\gamma ){)}^{\alpha }$. When $d\ge 2$, exponential weighting is within a factor smaller than $1.161^{\alpha }$ of the best fixed nonnegative weighted rule with the same average look-back, for $0<\alpha \le 3$. Comparison with the running mean highlights its time-homogeneous update, stationary coefficient profile, and fixed effective memory.

44 pages, 6 figures, 3 tables. Substantially expanded and retitled version. Includes numerical evaluation, endpoint distribution limits, additional adversarial analysis, and reproducibility materials