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\leq\gamma\leq1$. 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^*=\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\leq\gamma<1$ and $0<\alpha\leq3$, the exact asymptotic adversarial value is $(2/(1+\gamma))^\alpha$. When $d\geq2$, 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\leq3$. Comparison with the running mean highlights its time-homogeneous update, stationary coefficient profile, and fixed effective memory.