Source-linked AI summary
Sequential Euclidean tree construction with exponential memory: distributional performance and worst-case guarantees
Pedro M. M. de Castro
TL;DR
The paper asks whether one observation-derived memory point can improve uniform-input insertion costs while reducing the path’s adversarial behavior. It studies exponentially weighted memory and establishes distributional monotonicity, near-optimal finite-horizon scaling, and worst-case guarantees.
Problem
The paper asks what information about preceding points should be retained when choosing the next attachment point, given that insertion paths can incur diameter-length connections while center stars ignore the observed sequence.
Method
The construction retains one d-dimensional state using x_i=γx_{i-1}+(1-γ)p_i, an exponentially weighted summary whose parameter γ controls the influence of the past.
Results
For uniform inputs, insertion lengths decrease stochastically with γ; optimal parameters satisfy 1-γ_N^*=Θ(N^-1/2), while for 0<α≤3 the worst-case asymptotic mean cost is (2/(1+γ))^α.
Takeaways & Limitations
The one-point exponential-memory rule interpolates between the path and center star, improving uniform-input performance while reducing the path’s exact worst-case scale.
Takeaways & Limitations
The complete adversarial value for α>3 remains open, as do extensions to other convex bodies, nonuniform distributions, and time-varying weighting rules.
Abstract
from arXiv · showhide
Let $p_0,p_1,\ldots,p_N$ be points of the unit ball of $\mathbb R^d$, processed in a prescribed order. We study the insertion cost $\sum_{i=1}^N\lVert p_i-x_{i-1}\rVert^α$, where each $x_{i-1}$ is computed from the previously observed points. The input-order path is sensitive to the input distribution but can repeatedly pay the diameter under adversarial input. The center star has controlled worst-case scale but ignores the observed sequence. We compress the past into one point through $x_0=p_0$ and $x_i=γx_{i-1}+(1-γ)p_i$, where $0\leqγ\leq1$. Thus $x_i$ is an exponentially weighted memory of the input, maintained with one $d$-dimensional point of working state. For independent uniform points, the stationary insertion length is nonincreasing in the usual stochastic order as $γ$ increases. If $d\geq2$ and $α>0$, every optimal constant parameter for $N$ insertions satisfies $1-γ_N^*=Θ(N^{-1/2})$. We determine its asymptotic constant and the resulting $\sqrt N$ correction, with explicit bounds in $d$ and $α$. For $α=1$, the leading expected tree length equals that of the center star and is strictly smaller than those of the endpoint constructions. For $α=2$, the minimizer is unique for $N\geq2$, with $1-γ_N^*=N^{-1/2}-\tfrac12N^{-1}+O(N^{-3/2})$. For arbitrary input sequences and fixed $0\leqγ<1$, the largest asymptotic mean cost is $(2/(1+γ))^α$ for $0<α\leq3$, strictly below the path value when $γ>0$. Among fixed nonnegative weighting rules whose contributing points have the same average distance in the input order from the most recent point, exponential weighting is within a factor smaller than $1.161^α$ of the best adversarial value in dimension at least two; this ratio tends to one as that average distance grows.
1 Introduction
The paper studies whether one exponentially weighted point can improve uniform-input insertion costs while reducing the path’s adversarial scale. It establishes distributional monotonicity, optimized finite-horizon behavior, worst-case guarantees, and comparisons with broader weighting rules.
- Strategy: The rule retains the observed sequence in one d-dimensional state, with γ controlling how strongly older points influence future attachment locations.γ = 0 gives the insertion-order path, while γ = 1 gives the star centered at p0.
- Distributional performance: For independent uniform points, increasing γ makes the stationary insertion length smaller in the usual stochastic order and decreases every positive moment.As γ approaches one, the expected α-power approaches d/(d + α), the center-star value.
- Finite-horizon optimization: For fixed-parameter optimization, every minimizing choice in the stated parameter regimes satisfies 1 − γ_N^* = Θ(N^-1/2), with an explicitly bounded correction term.The asymptotic constant is represented by a one-dimensional integral and bounded in terms of d and α.
- Finite-horizon optimization: For α = 1, the optimized rule has leading expected cost Nd/(d + 1), matching the center-O star and strictly improving on the input-order path and the star centered at p0.The endpoint constructions have leading expected length Nμ_d.
- Worst-case guarantees: For fixed 0 ≤ γ < 1 and 0 < α ≤ 3, the largest asymptotic mean adversarial cost is (2/(1 + γ))^α, approaching the center star’s unit scale as γ increases.Alternating diameter endpoints attain the lower bound, while explicit state potentials provide the upper bound.
- Weighting-rule comparison: Among fixed nonnegative weighting rules with the same mean lag, exponential weighting is within a factor smaller than 1.161^α of the best adversarial value in dimension at least two.The ratio tends to one as the average lag grows, although the comparison class need not have a constant-state implementation.
2 The insertion strategy
The γ-strategy compresses the observed sequence into one recursively updated point, interpolating between the insertion-order path and a star centered at p0. Its fixed-parameter cost is the insertion cost of the resulting subdivided tree, with endpoint and asymptotic behavior requiring separate treatment.
- State and update: The γ-strategy updates x_i as a geometrically weighted average of past points, using one d-dimensional point of state.The parameter γ controls how long the past influences later attachments.
- Endpoint constructions: γ = 0 produces the insertion-order path, while γ = 1 produces the star centered at p0.These endpoint identifications follow from the recursion and initialization x_0 = p_0.
- Geometric validity: For 0 < γ < 1, each update remains in the convex hull of the observed points and therefore inside the unit ball.The update is a convex combination of x_{i-1} and p_i.
- Tree realization: The tree retains labelled auxiliary states x_i and subdivides each connection into [x_{i-1}, x_i] and [x_i, p_i].Edge lengths are counted with multiplicity, and the insertion objective refers to the specified subdivision.
- Endpoint behavior: The endpoint γ = 1 is singular for stationary asymptotics, whereas every fixed γ < 1 has a unique stationary law under independent uniform input.At γ = 1 the state stays at p_0, so no unique stationary law exists.
3 Uniform points in the ball
For uniform points, the paper analyzes the radial insertion cost, stationary state, and finite-horizon optimization of the γ-strategy. Increasing γ improves stationary insertion-length moments, while the optimal finite-horizon memory scale is 1 − γ_N^* = Θ(N^-1/2).
- Finite-horizon optimization: 1 − γ_N^* = Θ(N^-1/2) for d ≥ 2 and α > 0, with an asymptotic constant and explicit bounds determined by the paper.The balance is between accumulated stationary excess of scale N(1 − γ) and initial-state forgetting of scale (1 − γ)^-1.
- Time-varying comparison: The running mean also stores one point but has time-varying coefficients and incurs an excess of order log N over N c_{d,α}.Its contributing observations lie, on average, t/2 insertion steps before the most recent point.
- Comparison with endpoints: For α = 1, the optimized exponential rule has a strictly smaller leading constant than either endpoint construction.The comparison follows from the strict inequality μ_d > c_{d,1} for the radial mean cost away from the origin.
- Stationary law: The stationary state has a unique distribution for 0 ≤ γ < 1, invariant under orthogonal transformations and supported on the unit ball.The state distribution is obtained from the absolutely convergent weighted recursion.
- Stationary insertion length: Increasing γ makes every positive moment of the stationary insertion length nonincreasing in the usual stochastic order.As γ approaches one, the stationary insertion length converges in distribution to the radius of a uniform point, matching the center-O star cost d/(d + α).
4 Adversarial sequences
For fixed γ<1, alternating diameter endpoints attain the exact worst-case asymptotic mean cost (2/(1+γ))^α for 0<α≤3. Exponential weighting is also near-optimal among fixed nonnegative weight sequences with equal mean lag, while α>3 admits a substantive limitation.
- Worst-case cost: Alternating diameter endpoints attain equality because the state converges to a two-periodic orbit with insertion length 2/(1+γ).Transient costs contribute only a vanishing amount to the asymptotic mean.
- Worst-case cost: (2/(1+γ))^α is the largest asymptotic mean insertion cost over arbitrary sequences for 0<α≤3.The bound is independent of the initial state and is attained by alternating diameter endpoints.
- Scope boundary: For every fixed 0<γ<1, periodic endpoint blocks eventually exceed alternation in adversarial mean cost for sufficiently large α.Thus the complete adversarial value for α>3, including the first power where alternation ceases to be optimal, remains open.
- General weighted averages: For weights with mean lag a, exponential weights use γ=a/(a+1) and have adversarial scale 2/(1+γ).The comparison class permits unrestricted support and need not admit a constant-state implementation.
5 Concluding remarks
The concluding results present exponential memory as a compromise between sequence responsiveness and controlled adversarial cost. They also identify limitations concerning constant parameters, weighting classes, and powers above three.
- Main conclusions: The γ-strategy combines sequence-sensitive expected performance with explicitly controlled adversarial cost approaching the center-star scale as γ increases.The state remains a geometrically weighted average of observed points.
- Main conclusions: For ordinary length, the optimized rule matches the center-O star in leading expected cost and improves on both endpoint constructions.The constant-parameter optimum has a square-root asymptotic correction, with a unique quadratic-case minimizer.
- Main conclusions: Among fixed nonnegative weights with equal mean lag, exponential weighting has a bounded approximation factor that converges to one as mean lag grows.The comparison class may have unbounded support and storage.
- Open limitations: For α>3, periodic endpoint blocks can outperform alternation, and the full adversarial characterization remains open.Other open directions include different convex bodies, nonuniform inputs, and time-varying weighting rules.
A A stochastic comparison for the running mean
The appendix proves a stochastic comparison for weighted averages of independent uniform points. Equal weighting is the most peaked case, yielding no larger expected positive-power insertion cost than arbitrary nonnegative weights.
- Stochastic comparison: The expected α-power is no larger for the running mean than for any weighted average, for every α>0.The comparison applies to an independent uniform additional point.
- Proof mechanism: Every probability vector of weights majorizes the equal vector, enabling the comparison through peakedness of weighted sums.The proof uses the symmetry and log-concavity of the uniform density on the ball.
- Proof mechanism: The proof applies peakedness inequalities to radial, nonincreasing superlevel sets and then averages over the independent point.This establishes the stated moment comparison after integration.
B Exact transforms and fourth moments
The appendix develops an exact transform description of the stationary state and insertion vector under uniform input, then records fourth-moment formulas used in the high-memory analysis.
- Stationary transform: The stationary state is characterized by a locally uniformly convergent product of characteristic functions.Geometric decay of the coefficients ensures convergence on compact frequency sets.
- Stationary transform: Rotation invariance reduces the uniform-ball characteristic function to a radial expression involving a Bessel function.The Bessel function has order ν=d/2.
- Moment calculations: The small-frequency expansion includes the fourth-order term 2(d+2)+O(r^4).This expansion supports moment calculations for the stationary state.
- Moment calculations: The fourth moments of the stationary state and insertion vector are recorded explicitly.The formulas are obtained by expanding finite weighted sums and passing to the L4 limit.
C High-memory limits of the stationary state
As γ approaches one, the stationary state concentrates near the center while its rescaled fluctuations converge to an isotropic Gaussian. The section also develops exact distributional and Wasserstein descriptions for stationary insertion lengths.
- The stationary state concentrates at the center as γ tends to one, with its fluctuations determining the corresponding insertion length.
- The standardized radial fourth moment converges to (d + 2)/d, matching the value for an isotropic Gaussian vector.
- The rescaled stationary state converges to N(0, I_d/(d+2)).The convergence follows from characteristic functions and the continuity theorem in R^d.
- Theorem C.2 bounds the Wasserstein distance between the stationary radial law Z_γ and the radius ρ of a uniform point in the ball.The proof uses a coupling sharing the same point and then applies the reverse triangle inequality, Cauchy–Schwarz, and the second-moment formula.
- At γ = 0, the stationary insertion length is the distance between two independent uniform points, while intermediate γ has an exact vector law.
D Periodic endpoint blocks beyond the cubic range
Theorem 4.8 applies through α = 3, while periodic blocks of repeated antipodal inputs demonstrate that this range cannot extend to all larger exponents. For sufficiently large α, longer blocks yield higher adversarial mean cost than alternation.
- Theorem 4.8 covers 0 < α ≤ 3, but a periodic family shows the corresponding formula cannot hold for every α > 3.
- For a period of m copies of u followed by m copies of −u, Proposition D.1 gives the attracting periodic orbit's mean insertion cost.The construction uses a fixed unit vector u and 0 < γ < 1.
- For every fixed m ≥ 2, C_m,α(γ) exceeds C_1,α(γ) for all sufficiently large α.Thus the m-block construction has strictly larger adversarial mean cost than antipodal alternation in that range.
- The periodic-orbit calculation represents the state as a scalar multiple of u and evaluates successive insertion lengths across each repeated block.
- Summing the α-powers over both halves of the period and dividing by 2m yields the periodic mean cost.
- For m ≥ 2, the relevant base exceeds one and the γ-dependent power fraction tends to one, so the complete expression diverges as α tends to infinity.