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

The paper studies how a constant-gain memory rule should optimize the edge-power cost of a labelled sequential geometric network. It analyzes the labelled-tree construction across uniform, adversarial, finite-size, and high-dimensional regimes, establishing phase transitions, explicit optimizers, and high-power asymptotics.

  • Problem

    The paper isolates the edge-power objective in sequential geometric network design, where retaining updated states creates a design tradeoff in the memory parameter.

  • Method

    The analysis uses the labelled caterpillar construction, exact adversarial insertion costs, periodic block witnesses, and a separation argument across the studied regimes.

  • Results

    The study gives a complete phase diagram, including a transition at power one, explicit finite-window optimizer scales, eventual uniqueness, and optimized high-power cost asymptotic to 2 log 2/log α.

  • Takeaways & Limitations

    The results characterize how the optimal memory parameter changes across distribution-sensitive, worst-case, finite-size, and high-dimensional settings within the constant-gain construction.

  • Takeaways & Limitations

    High-power periodic block inputs are lower-bound witnesses whose optimality among all input sequences is not established, while broader inputs and adversarial powers beyond the cubic range remain open.

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

The paper studies a constant-gain sequential connection rule whose retained states form a labelled caterpillar, and determines how the memory parameter controls edge-power costs across stationary, finite-size, and adversarial settings.

  • Model and interpretation: The γ-strategy attaches each input point to the previous state, updates that state with constant gain, and retains the resulting spine and leaf edges.The memory parameter is chosen before processing and controls how strongly earlier inputs influence later attachment points.
  • Model and interpretation: The isolated geometric objective captures edge-power cost, while fuller communication or facility models could additionally charge for state activation, movement, capacity, delay, or multihop transmission.This scope distinguishes the paper’s optimization target from broader network-design costs.
  • Finite-size analysis: Near power one, the finite-size phase diagram separates an N^-1/2 optimizer below an explicit threshold from a stationary-scale optimizer above it, with a Lambert-profile scale at the threshold.The supplied passages identify this as the paper’s first contribution and state the threshold structure, while the detailed threshold scale is given in the abstract.
  • Adversarial and exact results: For adversarial inputs, the paper gives exact optimization for 0 < α ≤3 and uses periodic block witnesses plus separation to obtain high-power asymptotics.It also provides exact quadratic and quartic results, a rational recursion for even powers, and high-dimensional expansions.
  • Stationary optimization: At α = 3d + 8, the endpoint linear coefficient changes sign; above it, a strict local-maximum branch enters while the global minimum remains interior.The endpoint is a strict one-sided local minimum for α > 3d + 8, creating an obstruction to a global convexity proof of uniqueness.

4 Worst-case optimization

The section optimizes the fixed memory parameter for arbitrary input sequences, obtaining exact results through power three and a high-power asymptotic value. Separation bounds and periodic antipodal block inputs provide the matching upper and lower analyses.

  • Exact optimization through power three: For 0 < α ≤3, the section determines the optimal fixed memory parameter and worst-case edge-power value.The exact optimization includes boundary behavior for 0 < α ≤1 and a closed optimal parameter for 1 < α ≤3.
  • Exact optimization through power three: Antipodal alternation attains the adversarial supremum for every fixed γ when 0 < α ≤3.This alternating input is the m = 1 case of the periodic block construction.
  • Exact optimization through power three: For 0 < α ≤1, the infimum is not attained, whereas for 1 < α ≤3 the unique global minimum is attained.
  • Large-power asymptotics: At high powers, periodic block inputs give explicit lower bounds, while a separation argument supplies the matching upper bound.The block length is chosen of order log α to control the tradeoff between approaching antipodal endpoints and switching frequently.

5 Numerical stationary and worst-case comparisons

The numerical section compares stationary and worst-case parameter choices under a common relative-loss scale and examines two transition and asymptotic phenomena. It reports a near-one-percent balanced loss in the tabulated range, a strict-local-maximum branch near the local threshold, and slow finite-power convergence at high powers.

  • Balancing uniform and worst-case performance: The stationary and worst-case criteria select different memory parameters, so relative losses place both criteria on a common scale for 1 < α ≤3.The balanced parameter quantifies the price of using one fixed parameter when the input model is uncertain.
  • Balancing uniform and worst-case performance: Figure 2 traces uniform-model loss horizontally and adversarial loss vertically as γ varies, with the balanced diamond minimizing their larger loss.Circles and triangles mark the uniform-optimal and adversarial-optimal endpoints; curves cover d = 1, . . . , 100 and include the d →∞ limit.
  • Balancing uniform and worst-case performance: The balanced choice keeps the larger loss close to one percent throughout the reported range and below one percent except at (d, α) = (2, 1.25), where it is 1.003%.The stationary expectations use deterministic geometric quadrature, with a largest relative change of 9.2 × 10−5 between the two finest nonquadratic resolutions.
  • Local transition: Immediately above the local threshold, a narrow barrier separates the one-sided endpoint minimum from interior descent, and the emerging critical point is a strict local maximum.The computed branch curvature approaches −6.125, as predicted by Eq.(27).
  • Large-power convergence: At α = 108, the theorem bounds for the normalized value are 0.818105 and 1.136188, illustrating slow finite-power approach despite asymptotic agreement.Oscillations of the best block size arise from integer optimization over periodic lower-bound witnesses.

6 Finite-size optimization

Finite-size optimization has three scales in the joint window near α=1, with a threshold separating boundary and stationary behavior and a second threshold selecting the leading correction. Uniform derivative estimates establish eventual uniqueness.

  • Boundary regime: For 0<α<1, finite optimizers approach the stationary endpoint at scale N^−1/(α+1).The limiting profile on this scale has a unique minimizer and excludes smaller and larger scales.
  • Joint transition window: The joint window (α_N−1)log N=O(1) produces square-root, Lambert-corrected critical, and stationary optimizer scales.The transition is governed by an explicit threshold λ⋆(d).
  • Joint transition window: At the critical threshold, 1−γ_N follows a Lambert-corrected scale involving log N/(N log log N).The Lambert factor resolves the slowly varying correction at equality.
  • Joint transition window: Above the first threshold, the optimizer approaches the stationary scale, while the transient correction dominates below 3λ⋆(d)/2 and the stationary correction above it.The two corrections exchange dominance at λ=3λ⋆(d)/2.
  • Uniqueness: Uniform estimates for two derivatives prove eventual uniqueness of finite minimizers in the critical and supercritical windows.The same analysis transfers local profiles to global minimizers.

7 High-dimensional optimization

As dimension grows, stationary geometric averages converge uniformly to a limiting objective with a unique optimizer, while the first finite-dimensional correction is of order d^−1. For α>1, the limiting optimizer is interior and has a characterized high-power expansion.

  • High-dimensional limit: Uniform and differentiated expansions identify the limiting stationary objective, its optimizer, and the first correction of order d^−1.The remainder is controlled uniformly, including differentiated estimates.
  • Limiting optimizer: The limiting objective has a unique minimizer at γ=1 for 0<α≤1 and an interior minimizer γ∞,α∈(1/2,1) for α>1.For α>1, the optimizer is characterized through t=γ∞,α/(1−γ∞,α).
  • Finite-dimensional optimizer: For fixed α>1, the finite-dimensional stationary objective has a unique global minimizer for all sufficiently large d.Uniform convergence and positive curvature near the limiting root establish uniqueness.
  • High-power asymptotics: As α→∞, the limiting optimizer satisfies 1−γ∞,α=4/(α−1)+O((α−1)^−2).The associated ratio t diverges with t(α−1)→4/3.

8 Numerical evaluation and parameter selection

Numerical evaluations verify the finite-size transition and correction scales, test differentiated asymptotics, and provide computational constants for parameter selection across the reported regimes.

  • Finite-size transitions: The finite-size experiments follow the transition through power one and test the local shape of the finite objective.The computations compare finite behavior with the predicted transition and differentiated profiles.
  • Correction crossover: At r = 3/2, the correction crossover separates the explicit transient and stationary contributions to the refined supercritical location.Finite-size crossings and balance points lie slightly to the right because higher-order terms affect the finite curves.
  • Numerical validation: The largest two-resolution discrepancies were 4.01 × 10−4 for the profile, 1.01 × 10−3 for the slope, and 4.50 × 10−3 for the curvature.These checks used nested resolutions and independent audits on Chebyshev–Lobatto points.
  • Differentiated convergence: Theorem 6.20 is tested by comparing the finite profile, slope, and curvature with stationary and transient profiles, whose errors decrease with N.Figure 7 evaluates these comparisons for r = 1, 1.1, and 2 over 0.7 ≤ z ≤ 1.4.
  • Parameter selection: Table 2 supplies λ⋆(d), 3λ⋆(d)/2, the critical optimizer scale, and coefficients needed to apply the finite-size laws.The high-dimensional calculation separately tests the explicit first correction and its differentiated remainder for α = 2 and 4.
  • Scope: The resulting parameter-selection map covers the finite, adversarial, high-power, and high-dimensional regimes, while the conclusions remain specific to edge-power tree cost.Broader system objectives require additional activation, capacity, hop, delay, or state-movement charges.

9 Conclusions

The paper gives a complete phase diagram for the fixed-parameter γ-strategy across the studied uniform, worst-case, finite-size, and high-dimensional settings, while identifying open extensions beyond its current scope.

  • Overall scope: The analysis covers the fixed-parameter γ-strategy across uniform, worst-case, finite-size, and high-dimensional regimes.This is the paper’s overall phase-diagram conclusion for the regimes considered.
  • Stationary optimization: The edge subdivision factor creates the stationary transition at power one and interior minimizers for every power greater than one.Exact low-power results also show that stationary and adversarial optimal parameters need not coincide.
  • High-power behavior: Periodic block lower bounds and separation at γ = 1/2 determine the optimized high-power scale and its leading constant.The paper also identifies stationary quadratic and transient corrections and a first high-dimensional displacement.
  • Finite-size optimization: At the critical threshold, the optimizer follows a Lambert profile with scale sqrt(log N/(N log log N)); above it, the optimizer approaches the exact stationary root.Differentiated moving-profile estimates establish eventual uniqueness in the critical and supercritical windows.
  • Open scope: Further work includes broader geometric inputs, time-varying rules, explicit state costs, adversarial powers beyond three, and coupled dimension-power-size limits.These are stated as directions rather than results established by the present analysis.

A Foundational insertion-cost inputs

The foundational analysis establishes monotonicity, endpoint behavior, and adversarial insertion-cost bounds that support the stationary and worst-case optimization results.

  • Core inputs: The foundational results establish ordering of the stationary moment, a radial upper envelope, and the exact adversarial value through power three.These three insertion-cost facts underpin the later optimization arguments.
  • Peakedness: Majorization makes the normalized affine sums more peaked as γ increases, and this peakedness transfers to the stationary states.The argument uses symmetric log-concavity of the uniform distribution and passage from truncated sums to their limits.
  • Stationary ordering: The stationary moment Md,α is nonincreasing for every α > 0, and strict comparisons follow away from the zero state.Tail-probability integration supplies the monotonicity argument.
  • Endpoint behavior: The stationary state is nonzero almost surely, so the stationary objective exceeds the endpoint value for γ < 1 and converges to that endpoint as γ → 1−.The endpoint limit follows from xγ → 0 in L2 and bounded convergence.
  • Reduction arguments: The radial and endpoint estimates reduce the relevant maximizations to boundary or diameter configurations, enabling the explicit low-power inequalities.The fourth-power potential is convex in the reduced one-dimensional coordinate.
  • Adversarial bounds: Alternating antipodal inputs attain the asymptotic insertion value aγ, while direct inequalities provide matching upper bounds through powers two and three.For α = 3, the upper bound follows after summing a nonnegative quartic potential inequality and telescoping the bounded potential.

B Bernstein certificate for the fourth-power objective

The fourth-power objective admits a Bernstein-basis certificate whose coefficients are all positive for d ≥ 1, proving the required convexity.

  • Certificate: The Bernstein representation supplies a convexity certificate for the fourth-power objective.The certificate is built from twelve explicitly listed coefficients.
  • Coefficient sign: All twelve Bernstein coefficients are strictly positive for d ≥ 1.Their positivity establishes the nonnegativity invoked in the main text.

C Proof for the high-power adversarial limit

The proof combines an upper bound at γ = 1/2 with two matching lower-bound certificates, whose exchange is controlled by γ0 and γ1.

  • Upper bound: The upper bound is obtained by separating almost maximal insertion lengths at γ = 1/2.
  • Lower bounds: An m-block input controls parameters near 1/2, while antipodal alternation controls the remaining parameters.
  • Lower bounds: The lower-bound certificates exchange at the points γ0 and γ1.
  • Intermediate region: The function rm first increases and then decreases, so its minimum on [γ0, γ1] occurs at an endpoint.
  • Intermediate region: The proof establishes sm(γ) ≥ 2 − o(1) throughout [γ0, γ1], then treats the alternating-input region γ ≥ γ1.
  • Conclusion: The upper and lower estimates match asymptotically, proving the stated high-power constant.

D Proofs for fixed-power finite-size regimes

The finite-size analysis separates leading stationary behavior from transient and boundary corrections, localizes minimizers, and proves selection and uniqueness through uniform expansions.

  • Objective decomposition: The proof decomposes the objective as FN = NΦ + Ψ + o(1), with Φ selecting M and Ψ selecting S.
  • Uniform expansion: On the scale δ = yN^-β, a coercive envelope controls the objective uniformly, while exact second moments yield the required finite-size expansion.
  • Transient control: The transient correction and its first two derivatives are uniformly summable on compact subsets of (0, 1), including the slower Hölder case.
  • Localization: For α > 1, every global minimizer eventually lies in a fixed compact subinterval away from 0 and 1.
  • Selection: Every finite minimizer approaches the stationary-minimizer selection set S, and the finite objective attains the corresponding asymptotic value.
  • Uniqueness: When the stationary minimizer is nondegenerate, strict convexity on a neighborhood proves eventual uniqueness of the finite minimizer.

E Uniform endpoint and transient estimates

The endpoint and transient analysis establishes uniform regularity, controls singular behavior near α = 1, and derives differentiated expansions with explicit remainder bounds.

  • Proof strategy: The endpoint analysis combines stationary expansion, finite-to-stationary coupling, and repeated coupling with two derivatives.
  • Boundary regularity: Uniform integrability controls the singular Hessian near α = 1 in dimensions d ≥ 2, while a density bound handles d = 1.
  • Differentiation: Differentiation under expectation is justified by truncation, pathwise convergence, finite-Lq convergence, and uniform integrability.
  • Endpoint expansion: The endpoint expansion yields |F| ≤ Cδ^3, |F′| ≤ Cδ^2, and |F′′| ≤ Cδ.
  • Transient estimates: The finite-state and stationary-state comparison produces exponentially controlled transient and truncation errors.
  • Potential regularity: The radial potential has bounded or Hölder-controlled derivatives, with the logarithmic modulus required at (d, α) = (2, 1).

F Proofs for the joint finite-size windows

The joint finite-size proofs identify endpoint scales through rescaled profiles, control remainders uniformly, and distinguish critical, crossover, and supercritical regimes.

  • Proof architecture: The proof order first localizes minimizers to endpoint scales, then compares critical and supercritical profiles, and finally establishes C2 convergence for uniqueness.
  • Endpoint localization: The Nδ = O(1) regime is excluded, forcing minimizers into a smaller endpoint scale.
  • Critical regime: The rescaled critical profile is strictly convex, and the exact finite objective inherits its scale and minimizer after remainder control.
  • Critical regime: In the critical regime, the optimizer satisfies δN = N^-1/2+o(1), with wN = O(log log N) and ΔN = N^-1/2+o(1).
  • Critical regime: Multiplicative localization shows that (1 − γN)/(δN e^{wN/2}) → 1.
  • Crossover: The two correction terms have equal order at λ = 3λ⋆(d)/2, identifying the crossover threshold.

G Proof of the first-order high-dimensional expansion

The proof derives a high-dimensional expansion for the stationary edge-power quantity by computing centered radial moments and controlling the Taylor remainder, including two derivatives. It combines coordinate-moment identities, cumulant calculations, and uniform bounds to establish the expansion on compact parameter intervals and at the endpoints.

  • Expansion setup: The scalar expansion centers the radial variable at σ2(γ)=2/(1+γ), with r=∥p−xγ∥2 and z=r−σ2.The target expansion is organized around fluctuations of the stationary distance from its deterministic limit.
  • Moment calculations: The proof computes centered radial moments using Gram identities, coordinate moments of uniform-ball points, and additive cumulants of the independent weighted sum.Rotational invariance reconstructs radial moments from coordinate cumulants, while finite-sum identities extend to infinite series by bounded convergence.
  • Uniformity: The resulting expansion holds uniformly on compact intervals I⊂(0,1), and the same cubic argument gives a uniform value estimate on [0,1].Uniform convergence of the coefficient power sums and centered moments extends the estimate to the endpoints.
  • Taylor expansion: A cubic Taylor expansion of f(r)=r^β supplies the expansion coefficients, while the coefficient of the relevant Gram term is identified as Cα.The expansion also uses the identity relating moments of z to moments of r and σ2.
  • Remainder control: Uniform remainder estimates control the Taylor error and its first two derivatives by Oα,I(d^-2) on the main and upper events, with an exponentially small contribution from the lower event.The argument splits according to the size of |z| and does not differentiate event indicators.
Loading 2608.27777v2…