PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal exponential memory for sequential Euclidean connections: edge-power costs and phase transitions

Pedro M. M. de Castro

arXiv:2608.27777v2cs.CGmath.OC

TL;DR

Choosing memory for sequential Euclidean connections requires understanding edge-power costs; the paper isolates this geometric objective across uniform and arbitrary input sequences. The paper analyzes the time-homogeneous γ-strategy, in which each point attaches to the current state and a fixed-gain update determines the next attachment point. The joint window near power one has an explicit subcritical profile and threshold; at threshold, the optimizer follows a Lambert profile, and above it approaches the exact stationary root q1/(αN−1).

  • Problem

    Choosing memory for sequential Euclidean connections requires understanding edge-power costs; the paper isolates this geometric objective across uniform and arbitrary input sequences.

    Source: §1 · p. 2

  • Method

    The paper analyzes the time-homogeneous γ-strategy, in which each point attaches to the current state and a fixed-gain update determines the next attachment point.

    Source: §1 · p. 2

  • Results

    The joint window near power one has an explicit subcritical profile and threshold; at threshold, the optimizer follows a Lambert profile, and above it approaches the exact stationary root q1/(αN−1).

    Source: §9 · p. 34

  • Takeaways & Limitations

    The stationary and worst-case criteria select different memory parameters, so the preferred choice depends on which input regime is considered.

    Source: §5.1 · p. 15

    The adversarial problem beyond the cubic range remains open for further investigation.

    Source: §9 · p. 34

Abstract

from arXiv · show

We study the edge-power cost of the labelled tree generated by the $γ$-strategy, a constant-gain rule for sequential Euclidean connections. Starting with $x_0=p_0$, each input point $p_i$ is attached to $x_{i-1}$, and the state is updated by $x_i=γx_{i-1}+(1-γ)p_i$. Retaining $x_i$ subdivides the insertion segment into a spine edge and a leaf edge. The memory parameter $γ$ controls how long earlier points influence subsequent attachment points. We minimize the sum of the $α$-powers of the edge lengths under independent uniform input and arbitrary input sequences. For uniform points in the unit ball, the stationary problem has a transition at $α=1$. Its continuous extension is minimized at the boundary for $0<α\leq1$, while every global minimizer is interior for $α>1$. We determine the finite optimizer in the joint window $α_N=1+\varepsilon_N$, $\varepsilon_N\log N\toλ$. Below an explicit threshold it lies on the $N^{-1/2}$ scale, at the threshold its scale is $\sqrt{\log N/(N\log\log N)}$, and above the threshold it approaches an explicit stationary root with two computable corrections. A second threshold identifies the governing correction, and differentiated estimates prove eventual uniqueness. At $α=3d+8$, the linear coefficient at the stationary endpoint changes sign and a branch of strict local maxima enters the parameter interval. For arbitrary input sequences, the optimal parameter and asymptotic worst-case edge-power cost per point are explicit for $0<α\leq3$. At high powers, periodic antipodal block inputs give explicit lower bounds which, with a separation argument, show that the optimized cost is asymptotic to $2\log2/\logα$. Exact results for powers two and four, a rational recursion for every even power, and a high-dimensional expansion complete the analysis.

1 Introduction · 2 Model and probabilistic framework · 3 Stationary optimization under uniform random input

These sections study stationary edge-power optimization for a constant-gain memory rule under uniform random input. They develop rational stationary objectives for even powers and describe changes in optimizer behavior at power thresholds.

1 Introduction

  • The γ-strategy uses one stored point and the same affine update at every step, defining a sequential network-design rule for the isolated edge-power cost.The paper also previews a complete finite-size phase diagram near power one and exact stationary solutions for quadratic and higher even powers.Source: §1 · p. 2, §3 · p. 7
  • At the critical window α_N = 1 + ε_N with ε_N log N → λ, a threshold separates an N^-1/2 optimizer from a stationary-scale optimizer.At the threshold the scale is sqrt(log N/(N log log N)); above it, the first displacement correction has stationary and transient terms, with dominance changing at λ = 3λ⋆(d)/2. Uniform two-derivative estimates establish eventual uniqueness in the critical and supercritical windows.Source: §1 · p. 2

2 Model and probabilistic framework

  • The labelled-tree cost is reduced to a scalar factor times insertion cost, separating attachment quality from the two-edge construction.The insertion cost measures attachment quality before multiplication by the cost of the two edges generated at each step.Source: §2 · p. 3, §2.1 · p. 4

2.1 Labelled caterpillar and cost reduction

  • Retaining each updated state creates a labelled caterpillar with a spine edge and a leaf edge per input, and γ controls how strongly earlier points influence later attachments.The model isolates this geometric edge-power cost; broader communication or facility models may add activation, multihop transmission, delay, capacity, or movement costs.Source: §1 · p. 2, §2.1 · p. 3

2.2 Stationary state and geometric moment formulas

  • For every α > 0, the stationary insertion moment is nonincreasing in γ and remains above its endpoint moment for γ < 1.The stationary framework uses an independent uniform input point and the stationary state to define the insertion moment used in optimization.Source: §2.2 · pp. 4–5

3.1 Transition at power one

  • For 0 < α ≤ 1 the stationary objective is minimized at γ = 1, whereas for α > 1 every global minimizer lies in (1/2, 1).For α ≤ 1 the stationary objective on [0, 1) has an unattained infimum; uniqueness for general α > 1 remains open. At α = 3d + 8, the endpoint’s linear coefficient changes sign, and for larger powers a strict local maximum enters the interval while the endpoint is a one-sided local minimum.Source: §1 · p. 3, §3.1 · pp. 7–8

3.2 Exact optimization for squared edge length

  • The quadratic stationary objective has a unique minimizer, and its finite-size problem also has a unique optimizer with a first correction.The stationary formula is dimension-independent and supplies the quadratic check for the paper’s later numerical analysis.Source: §3.2 · p. 8

3.3 Fourth and higher even powers

  • The fourth-power objective is strictly convex with a unique polynomial-root minimizer, and a cumulant recursion gives rational objectives for every higher even power.The fourth-power optimizer lies between 10/19 and 8/15.Source: §3.3 · p. 9
  • Cumulant additivity yields a recursion for all even moments and a rational stationary objective, but uniqueness of its minimizer remains open in general.The recursion uses the coefficient power sums of the isotropic weighted sum of independent uniform-ball points.Source: §3.3 · p. 10

3.4 Local behavior near the star parameter

  • At α = 3d + 8, the linear coefficient at the star endpoint changes sign, and a nearby stationary branch contains a strict local maximum just above the threshold.Figure 3 shows the branch, its curvature, and barrier-height asymptotics for d = 2.Source: §3.4 · pp. 10–11
  • For every α > 3d + 8, the endpoint is a strict one-sided local minimum, but the global minimum is attained in (1/2, 1).Above the threshold, the stationary objective is neither convex nor single-well unimodal on the full interval.Source: §3.4 · p. 11

4 Worst-case optimization

The section determines optimal fixed-memory behavior for arbitrary input sequences: it gives the exact optimization regimes through power three and the optimized high-power asymptotic. It also establishes that the asymptotic cost is independent of the initial state.

4 Worst-case optimization

  • For 0≤γ<1, the asymptotic value in Eq. (28) is independent of the initial state in B.The proof bounds differences in accumulated costs by a constant independent of sequence length and input sequence.Source: §4 · p. 12

4.1 Exact optimization through power three

  • For 0<α≤1, the infimum is not attained; for 1<α≤3, a unique global minimum is attained at an explicit parameter.In this range, antipodal alternation attains the worst-case insertion value for each fixed parameter.Source: §4.1 · p. 13, §4.2 · p. 13

4.2 Large-power asymptotics

  • Blocks of m copies of u followed by m copies of −u are explicit high-power witnesses, with m of order log α providing the needed lower-bound scale.For m≥2, their optimality among all input sequences is not established.Source: §4.2 · p. 13
  • As α grows, the optimized worst-case value has a determined high-power leading asymptotic behavior: periodic block inputs give lower bounds, and a separation argument gives the matching upper bound.Source: §4.2 · p. 13

5 Numerical stationary and worst-case comparisons

The numerical comparisons examine the tradeoff between uniform-input and worst-case performance, then illustrate the local star-threshold transition and high-power convergence. They show that a balanced parameter keeps both relative losses small, while the high-power bounds approach their asymptotic agreement slowly.

5.1 Balancing uniform and worst-case performance

  • The section defines uniform and adversarial relative losses and uses the smallest achievable maximum of the two to quantify the price of one fixed parameter under model uncertainty.Figure 2 covers dimensions 1 through 100; for α = 2, all dimensions coincide.Source: §5.1 · p. 15, Figure 2 · p. 15
  • The balanced choice keeps the larger relative loss near 1% across the reported cases, exceeding 1% only at (d, α) = (2, 1.25), where it is 1.003%.The conservative uncertainty in the reported losses is below 0.019 percentage points; Table 1 compares uniform-optimal, adversarial-optimal, and balanced choices.Source: §5.1 · p. 16, Table 1 · p. 16

5.2 The local star threshold and the large-power limit

  • The computed branch curvature approaches −6.125 just above the local threshold, identifying the emerging critical point as a strict local maximum.A narrow barrier separates the one-sided endpoint minimum from the interior descent, and branch and barrier ratios converge to the theorem's coefficients.Source: §5.2 · p. 16
  • At α = 108, the computed theorem bounds for the normalized value are 0.818105 and 1.136188, illustrating slow finite-power approach despite asymptotic agreement.Within the periodic-witness family, the best block size oscillates because of integer optimization.Source: §5.2 · p. 16

6 Finite-size optimization

This section analyzes finite-size optimization across the scales below and above α = 1, including a three-regime transition when (α_N − 1) log N stays bounded. In the supercritical window, it identifies which correction governs the optimizer’s location and establishes eventual uniqueness of the global minimizer.

6.1 Fixed powers below one

  • For fixed 0 < α < 1, every global minimizer lies on the scale 1 − γ_N = N^-1/(α+1)y, where the limiting profile has a unique minimizer.The initialization coefficient H_d,α is positive for every real α > 0 and reduces to a finite sum of radial moments for even powers.Source: §6.1 · p. 19

6.2 Fixed powers above one

  • For fixed α > 1, the order-N objective restricts finite minimizers to stationary minimizers, and the order-one transient selects among them.At a unique nondegenerate stationary minimizer, the expansion gives an N^-1 displacement; the finite global minimizer is eventually unique under the theorem’s stated conditions.Source: §6.2 · p. 20

6.3 Transition window near α = 1

  • For fixed d, the stationary objective has a unique global minimizer for α sufficiently close to and greater than 1.The moving-window analysis includes α = 1 as ε_N = 0.Source: §6.1 · p. 18, §6.3 · p. 21
  • For λ > λ⋆(d), the stationary root sets the leading optimizer scale, with transient and stationary corrections exchanging dominance at λ = 3λ⋆(d)/2.The transient correction dominates below 3λ⋆(d)/2; the stationary correction dominates above it.Source: §6.3 · p. 25, Figure 5 · p. 26
  • For α_N = 1 + ε_N with ε_N log N → λ, the optimizer has boundary, Lambert-corrected critical, and stationary scales below, at, and above λ⋆(d).For λ < λ⋆(d), the limiting profile has a unique minimizer; the critical scale is √(log N/(N log log N)).Source: §6.3 · pp. 20, 23, 24, Figure 5 · p. 26
  • Under either stated assumption, ∆N → 0 and N∆N → ∞, while the normalized objective and its slope and curvature converge near ∆N to a strictly convex profile minimized at z = 1.The comparison profile is AN + BN; its unique minimizer gives the local optimizer scale.Source: §6.3 · p. 26
  • For all sufficiently large N, the finite objective has a unique global minimizer, whose ratio to ∆N tends to one.Uniform curvature and opposite derivative signs yield one critical point in a fixed multiplicative neighborhood of ∆N; earlier results place every global minimizer in that neighborhood.Source: §6.3 · pp. 26–27

7 High-dimensional optimization

As dimension grows, the stationary objective has a limiting optimizer with a transition at α=1. A first-order refinement describes finite-dimensional behavior for fixed α>1.

7.1 Limiting objective and optimizer

  • For 0<α≤1, the limiting objective is uniquely minimized at γ=1; for α>1, its unique minimizer γ∞,α lies in (1/2, 1).For α>1, the ratio t=γ∞,α/(1−γ∞,α) is characterized by the equation in the theorem.Source: §7.1 · pp. 27–28

7.2 First-order correction

  • For every fixed α > 1, the stationary objective has a unique global minimizer γd,α for all sufficiently large d; the differentiated estimate is uniform on compact intervals in (0, 1).Source: §7.2 · pp. 28–29
  • As ε=α−1→0+, t=γ∞,α/(1−γ∞,α)→∞ and tε→4/3, implying 1−γ∞,α is asymptotic to 3ε/4.Here t is the ratio characterizing the limiting optimizer.Source: §7.2 · p. 29

8 Numerical evaluation and parameter selection

Section 8 numerically checks the finite-size transition near power one and the high-dimensional correction, then presents the results as a parameter-selection map for the fixed-parameter γ-strategy.

8.1 Finite-size transitions near power one

  • For d = 2, the size-pair exponent tends to 1/2 for r ≤ 1 and 1/(2r) for r > 1; the correction crossover is r = 3/2, with finite crossings slightly higher.Figure 6 also shows nonuniform convergence near r = 1 under the regime-specific normalization.Source: §8.1 · pp. 29–30, Figure 6 · p. 30
  • Near z = 1, Figure 7 numerically supports Theorem 6.20: the finite objective minus the stationary and transient profiles converges to zero with its first two derivatives.The figure compares the objective, slope, and curvature with the corresponding profiles.Source: §8.1 · p. 30, Figure 7 · p. 31

8.2 The high-dimensional expansion

  • For α = 2 and 4, Figure 8 shows scaled high-dimensional differences approaching explicit Cα(γ); the differentiated remainder aligns with the d^-2 reference, using exact moments without sampling error.The remainder is measured in the C2([0.5, 0.9]) norm.Source: §8.2 · p. 32, Figure 8 · p. 33

8.3 Implications for parameter selection

  • The finite phase diagram guides fixed-parameter selection by balancing long-memory benefit against initialization cost; the adversarial theorem gives an exact robust choice through power three, and the high-power theorem sets the scale when longest edges dominate.The numerical evaluations make transition and correction scales available for the dimensions reported in Table 2.Source: §8.3 · p. 33

9 Conclusions

The paper gives a phase diagram for the fixed-parameter γ-strategy across uniform, worst-case, finite-size, and high-dimensional regimes, and identifies open directions for extending the analysis.

Conclusions

  • The analysis provides a complete phase diagram for the fixed-parameter γ-strategy across the uniform, worst-case, finite-size, and high-dimensional regimes studied.It also separates insertion cost from the two-edge factor introduced by subdivision at each labelled auxiliary vertex.Source: §9 · p. 33
  • The subdivision factor creates a stationary transition at power one and interior minimizers for every power above one; exact low-power results show stationary and adversarial optima need not agree.The distinction follows from separating attachment quality, measured by insertion cost, from the two-edge subdivision factor.Source: §9 · p. 33
  • Periodic blocks provide stronger high-power lower-bound certificates than alternation in part of the parameter interval, and separation at γ = 1/2 determines the optimized scale and leading constant.For 0 < α < 1, the finite-size constant is expressed by a positive geometric integral.Source: §9 · pp. 33–34
  • Near power one, the finite optimizer has subcritical, threshold, and supercritical profiles, with eventual uniqueness in the critical and supercritical windows.At the threshold its Lambert profile has scale sqrt(log N/(N log log N)); above it, the optimizer approaches the stationary root, with stationary quadratic and transient corrections.Source: §9 · p. 34
  • In high dimension, differentiated convergence establishes eventual uniqueness of the stationary optimizer and determines its first displacement.Source: §9 · p. 34
  • Further work includes broader geometric inputs, state-dependent or time-varying rules, explicit costs for resources or delay, adversarial powers beyond the cubic range, and joint dimension-power-sample limits.The global structure of the stationary minimizer also remains open.Source: §9 · p. 34

A Foundational insertion-cost inputs

This section establishes three insertion-cost ingredients for the optimization: ordering of the stationary moment, a radial upper envelope, and adversarial bounds through power three.

Stationary moment ordering

  • The stationary moment M_d,α(γ) is nonincreasing in γ, exceeds c_d,α for γ < 1, and converges to c_d,α as γ → 1.The ordering follows from peakedness of the stationary states; the endpoint limit follows from x_γ → 0 in L2.Source: A Foundational insertion-cost inputs · p. 35

Radial upper envelope

Adversarial costs

  • Alternating antipodal inputs have insertion length a_γ = 2/(1 + γ) on their attracting two-periodic orbit, yielding the adversarial lower bound.The same asymptotic value holds from every initial state.Source: A Foundational insertion-cost inputs · p. 36
  • At powers 2 and 3, potential inequalities give matching upper bounds to the alternating-input value; interpolation extends the bound to 2 < α < 3.The power-two bound follows by direct maximization, while the power-three bound uses a bounded telescoping potential.Source: A Foundational insertion-cost inputs · pp. 36–37

B Bernstein certificate for the fourth-power objective

The fourth-power objective has a Bernstein convexity certificate: all twelve coefficients are strictly positive for d ≥ 1.

B Bernstein certificate for the fourth-power objective

  • Proposition 3.5’s proof uses a twelve-entry Bernstein coefficient vector for the fourth-power objective.The first six entries are 17(d + 3), 3(53d + 157)/11, 2(359d + 1071)/55, 4(509d + 1546)/165, 31(43d + 133)/110, and (5701d + 17705)/462.Source: B Bernstein certificate for the… · p. 37
  • The coefficient vector’s final six entries complete the Bernstein representation used in the proof.They are 2(1512d + 4559)/231, (809d + 2227)/55, 4(747d + 1690)/165, 4(353d + 548)/55, 48(10d + 7)/11, and 8(11d − 4).Source: B Bernstein certificate for the… · p. 37
  • All twelve Bernstein coefficients are strictly positive for d ≥ 1, certifying the convexity invoked in the main text.Source: B Bernstein certificate for the… · p. 37

C Proof for the high-power adversarial limit

The proof matches an upper bound at γ = 1/2 with lower bounds from block and antipodal inputs, establishing the high-power asymptotic cost. It divides the lower-bound argument into parameter regions where different certificates apply.

Proof strategy

  • An upper bound comes from separating almost-maximal insertion lengths at γ = 1/2; an m-block input and antipodal alternation provide matching lower certificates across the parameter range.The points γ0 and γ1 mark where the two lower-bound certificates are exchanged.Source: C Proof for the high-power adversarial… · p. 37

Lower-bound regions

Matching the asymptotic constant

D Proofs for fixed-power finite-size regimes

The proofs separate boundary-scale optimization for 0 < α < 1 from finite-size selection among stationary minimizers for α > 1. They establish localization and, in the nondegenerate case, uniqueness and refined corrections.

Proof of Theorem 6.2

Proof of Theorem 6.3 and Corollary 6.4

  • For α > 1, the finite objective has a C2 expansion FN = NΦ + Ψ + o(1) on compact parameter intervals, with exponentially summable transient corrections.The expansion holds in C2(K), and the slower Hölder case still has an exponential rate.Source: D Proofs for fixed-power finite-size… · pp. 39, 41, 42
  • For sufficiently large N, every global minimizer lies in a fixed compact interval and approaches S, where Ψ selects among the minimizers M of Φ.The leading term selects M; the order-one term selects S, and the proof also establishes the finite objective bound in Eq. (51).Source: D Proofs for fixed-power finite-size… · pp. 39, 42, 43
  • When M is a singleton with positive curvature, the finite minimizer is eventually unique, and the proof derives refined location and value corrections.The location correction is given in Eq. (52).Source: D Proofs for fixed-power finite-size… · p. 43

E Uniform endpoint and transient estimates

The section establishes endpoint regularity and localizes the global minimizer as α approaches 1 from above. It also controls finite-time terms by coupling them to a stationary state driven by the same later inputs, with the comparison extended to two derivatives.

Transient estimates

  • The transient estimates couple each finite state to a stationary state using shared later inputs, and the final comparison controls the coupling with two derivatives and finite truncation.The differentiated infinite series can be differentiated twice term by term on compact subintervals of (0, 1).Source: E Uniform endpoint and transient… · pp. 43, 47, 49, 50

Boundary control

  • For d ≥ 2, the Hessian kernel is uniformly integrable near the boundary for α ∈ [1 − η, 1 + η]; in d = 1, a density bound and exponential tail control its singular term.These estimates yield a globally bounded D²Q on the ball.Source: E Uniform endpoint and transient… · p. 44

Endpoint expansion

  • The endpoint estimate gives |F| ≤ Cδ^3, |F′| ≤ Cδ^2, and |F′′| ≤ Cδ for F(δ) = E Q(sδ).The proof controls the boundary contribution using an exponentially small tail probability and justifies differentiation under the expectation.Source: E Uniform endpoint and transient… · pp. 44–45

Global localization and uniqueness

  • As α → 1+, every global minimizer approaches the endpoint, and localization plus the derivative estimates proves the unique critical point is the unique global minimizer.The minimizer is localized by uniform convergence to the endpoint objective, whose unique minimizer is γ = 1.Source: E Uniform endpoint and transient… · p. 45

F Proofs for the joint finite-size windows

The proofs localize finite minimizers near the endpoint, then compare rescaled profiles with uniform remainders to establish their critical and supercritical scales. A moving-window C2 expansion supports the local-uniqueness argument.

Moving-window expansion

  • A moving-window expansion uniform with two derivatives supplies the C2 convergence used to establish local uniqueness.The final proof controls the centered, rescaled remainder uniformly over z in a fixed interval.Source: F Proofs for the joint finite-size… · pp. 51, 55, 56

Global localization

  • Every global minimizer satisfies 1 − γ_N → 0, after the proof excludes bounded N(1 − γ_N) and parameters separated from the endpoint.Away from the endpoint, the finite objective differs from its stationary approximation by at most a constant, and the resulting order-N gap contradicts the trial value.Source: F Proofs for the joint finite-size… · pp. 51–52

Critical profile and scale

  • In the critical regime, the exact finite objective inherits the rescaled model profile’s unique minimizer, with (1 − γ_N)/(δ_N e^{w_N/2}) → 1.The model profile is strictly convex, and the remainder estimates exclude every fixed multiplicative separation from the stated scale.Source: F Proofs for the joint finite-size… · pp. 52–53

Supercritical scale and value

  • For the supercritical regime, the leading profile localizes every minimizer to z → 1, and evaluating there preserves the second-order minimum value.The profile is strictly convex near its minimum, while uniform endpoint expansions control the correction terms.Source: F Proofs for the joint finite-size… · p. 54

Refined location and crossover

  • The two location corrections have the same order at λ = 3λ⋆(d)/2, where substitution yields the crossover formula.The proof refines the minimizer location by expanding the first-order condition on the scale (1 − γ_N)/δ_N − 1.Source: F Proofs for the joint finite-size… · p. 55

G Proof of the first-order high-dimensional expansion

The proof refines the high-dimensional limit by expanding the radial power around its deterministic limit. It computes centered moments and controls the Taylor remainder, including its first two derivatives.

Moment identities

  • The radial expansion centers r at σ², with z = r − σ², and writes the target expansion around this deterministic limit.The proof expands f(r) = r^β to order three at σ².Source: G Proof of the first-order… · pp. 56, 58
  • Gram identities and coordinate cumulants determine the centered moments used in the expansion.Cumulants add for the independent weighted sum, and rotational invariance reconstructs its third radial moment.Source: G Proof of the first-order… · pp. 56–57

Uniform remainder estimate

  • The Taylor remainder and its first two derivatives are O(d^-2) on compact parameter intervals, using separate bounds for central, upper, and lower events.The upper event is controlled by a fourth-moment Markov inequality, while the lower event has an exponentially small bound.Source: G Proof of the first-order… · p. 58
  • The expansion’s value estimate extends uniformly to α in [0, 1] because the coefficient power sums and centered moments extend continuously to the endpoints.The proof uses 1 ≤ σ² ≤ 2 and 0 ≤ r ≤ 4 to control the complement of |z| ≤ σ²/2.Source: G Proof of the first-order… · p. 58

Related papers

Loading 2608.27777v2…