CS Paper Radar

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

Pedro M. M. de Castro

cs.CG math.OC ·submitted 2026-08-26 02:10 UTC · v2

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=γx_{i-1}+(1-γ)p_i$, with $0\leqγ\leq1$. The cost is the sum of the $α$-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 $γ$ increases. If $d+α>2$, or if $(d,α)=(1,1)$, the optimal constant parameter satisfies $1-γ_N^*=Θ(N^{-1/2})$, with an explicit asymptotic constant and closed bounds. For $α=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 $α=2$, the optimizer is unique and characterized exactly. For the same $N$, choosing $1-γ_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γ<1$ and $0<α\leq3$, the exact asymptotic adversarial value is $(2/(1+γ))^α$. When $d\geq2$, exponential weighting is within a factor smaller than $1.161^α$ of the best fixed nonnegative weighted rule with the same average look-back, for $0<α\leq3$. Comparison with the running mean highlights its time-homogeneous update, stationary coefficient profile, and fixed effective memory.

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

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.CG math.OC ·2026-08-27 ·Pedro M. M. de Castro
code/data similarity 0.80
Abstract · 60 pages, 8 figures, 2 tables. Substantially expanded version with finite-size phase transitions, high-power adversarial bounds, high-dimens…

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.

0.31

Fast Multidimensional Approximate Agreement with Optimal Resilience Using Ball Validity

cs.DC ·2026-09-07 ·Tijana Milentijević, Stefan Schmid
theory similarity 0.57
Abstract

Multidimensional approximate agreement requires $n$ processes with inputs in $\mathbb{R}^d$ to output vectors close to each other, despite up to $t$ Byzantine faults. Under convex validity, outputs must lie in the convex hull of the correct inputs, which leads to resilience thresholds that grow with the dimension. We instead study Minimum Enclosing Ball (MEB) validity and its multiplicative relaxation $c$-MEB validity. Our first contribution is Adaptive MEB Contraction, a coordinate-free algorithm that, in the synchronous model with $n>(d+1)t$ contracts the correct MEB radius by $1/\sqrt2$ per round for $α=1$ while satisfying $\sqrt2$-MEB validity. We also give an example showing that this bound is tight for our analysis. Our main technical contribution is a dimension-free inflation theorem: if every $β$ balls in a finite family of Euclidean balls have a common point, then inflating each radius by $\sqrt{β/(β-1)}$ guarantees a common intersection. Applying the theorem to the candidate balls defining the local MEB-safe areas results in a synchronous algorithm with optimal resilience $n>3t$, contraction factor $\sqrt3/2$ and $\sqrt6$-MEB validity. To the best of our knowledge, this is the first multidimensional approximate agreement algorithm with optimal resilience, constant $c$-MEB validity and coordinate-free contraction. We further extend the approach to the asynchronous setting. Without inflation we obtain resilience $n>(d+2)t$, contraction factor $\sqrt{2/3}$ and $\sqrt6$-MEB validity, whereas with inflation for $n>4t$ we get the contraction factor $\sqrt{15}/4$ and $2\sqrt{10}$-MEB validity. Finally, we compare our guarantees with existing algorithms, including Minimum-Diameter Averaging (MDA), for which we derive MEB-validity guarantees. Our algorithms achieve strictly better resilience while providing substantially stronger MEB-validity guarantees than MDA.

0.44

Maximum-Cost Strategic Facility Location: The Limits of Randomization

cs.GT ·2026-08-17 ·Jabari Hastings, Misha Ivkov
similarity 0.57
Abstract · 15 pages

We consider strategic facility location in Euclidean space $\mathbb R^d$, where a mechanism selects a single facility based on the reported locations of $n$ agents and seeks to minimize the maximum distance from any agent to the facility. The optimal approximation ratio of deterministic strategyproof mechanisms is $2$. Whether randomization can yield a universal constant improvement over this factor has remained a major open question. We show that for $d \geq 2$, every strategyproof-in-expectation mechanism has approximation ratio at least \[ α(\mathcal M) \ge 2 - e^{-Θ(\sqrt d)} - O\left(n^{-2/(d-1)}\right). \] Therefore, no strategyproof-in-expectation mechanism can guarantee a $(2-\varepsilon)$-approximation uniformly over all $n$ and $d$, for any universal constant $\varepsilon>0$.

0.38

Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations

cs.IT math.OC ·2026-09-26 ·Yekini Shehu
theory similarity 0.56
Abstract · 55 pages, 5 figures

We study stochastic fixed-point iterations $x_{n+1}=θ_nx_0+(1-θ_n)\widehat T(x_n)$ for nonexpansive and contractive operators on Hilbert spaces, with a single-point unbiased oracle of bounded variance. Deterministically, every anchor schedule $θ_n=c_n/(n+2)$ whose density $c_n\in(0,1]$ does not oscillate between scales is either polynomially suboptimal on contractions or super-polynomially slow on rotations; for constant densities $θ_n=c/(n+2)$ the tradeoff is exact, with $\norm{x_n}\asympΓ(c+1)(n\varphi)^{-c}$ on rotations by angle $\varphi$ ($\varphi\to0$, $n\varphi\to\infty$) and, for the classical schedule, $\norm{x_n}=\frac{2|\sin(n\varphi/2)|}{n\varphi}+O(\frac1n)$. The dichotomy fails exactly under lacunary anchor concentration: an explicit $γ$-oblivious schedule, one per target accuracy, is simultaneously contraction-optimal and rotation-polynomial with exponent $1/α_0$, $α_0=\log_2(3/2)$, and, for each fixed target accuracy, the matching lower bound holds for Lebesgue-a.e.\ angle. For stochastic contractions, the minimax rate is $Θ(σ^2\eps^{-2}(1-γ)^{-2})$ on affine maps, and within the anchored class $Θ(σ^2\eps^{-2}(1-γ)^{-2}+(1-γ)^{-1}\ln(D/\eps))$ for known modulus via geometric batching; without a certified modulus bound no sound distance certificate exists, and a certified ceiling is the exact boundary. For nonexpansive maps we prove $O(Kσ^2D^2\eps^{-4})$ in every $2$-uniformly smooth Banach space and the Hilbert rate $\tildeΘ(σ^2\eps^{-2}+D\eps^{-1})$ by reduction to monotone inclusions. Numerical experiments are consistent with every scaling prediction.

0.40

The threshold for online balancing of i.i.d. binary vectors

cs.DS math.PRmath.CO ·2026-09-14 ·Dylan J. Altschuler, Konstantin Tikhomirov
theory similarity 0.56
Abstract · Supersedes and replaces arxiv.org/abs/2509.02432, which has the same lower bound, but only has an upper bound for the ultra-sparse regime

Consider the task of online vector balancing for stochastic arrivals $X_1,\ldots,{X_T}$, where the $X_i$ are independent uniformly random $d$--sparse binary vectors in $\{0,1\}^n$. This is a random analogue of the online Beck--Fiala problem. We show that uniformly for $2\le d\le n/2$ and $T = Θ(n)$, the optimal online prefix discrepancy $\max\limits_{t\leq T}\left\|\sum_{i=1}^tσ_i X_i\right\|_\infty$ is of order \[ Θ\big(\max\{\sqrt d,\log\log n\}\big). \] The upper bound is achieved by an efficient online algorithm. Thus, for $d\le(\log\log n)^2$, the optimal discrepancy is $Θ(\log\log n)$ and is independent of the sparsity up to constant factors, whereas above this scale it is $Θ(\sqrt d)$, matching the order of the offline discrepancy. This identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model.

0.44

A Geometric Principle for Path Selection in Directed Acyclic Graphs

cs.SI physics.soc-phmath.CO ·2026-10-19 ·Haya AlMuhanna, Tim S. Evans
similarity 0.56
Abstract

There are many types of path between nodes of a Directed acyclic graph (DAG), including the shortest and longest paths. Here, we ask whether the choice of path used in any analysis reflects the geometry of the latent space in which the DAG is embedded. To do this we define L_p-cube spacetimes, a family of continuous ordered spaces in which a single parameter p determines whether the ordered distance satisfies the ordered triangle identity when p>1, or the reverse ordered triangle identity when 0<p<1 or p<0, both of which are rarely studied. The forward connection kernel in the p<0 case has infinite hyper-volume, yet it is a well defined model. We then construct random geometric DAGs embedded in our L_p-cube spacetime and study their geometry. For p>1, where the ordered triangle identity holds, the shortest paths provide the closest approximation to the continuum ordered geodesic while for 0<p<1 and p<0, where the reverse ordered triangle identity holds, this role is instead taken by the longest weighted path. We also test the robustness of this relationship in a geometric citation model in which the random geometric DAG is supplemented by a preferential-attachment-type mechanism allowing connections beyond the strict geometric cut-off. The same broad correspondence between latent geometry and ordered geodesic path type is recovered. Our results show that the preference for shortest or longest paths in a DAG is closely connected to the geometry assumed for its latent space, and suggest that path structure can provide information about latent geometry, even when that geometry is not directly observed.

0.34

Exact Universality of Online Discrepancy

cs.DS math.PR ·2026-09-08 ·Sunghyeon Jo, Taekyun Lee
theory similarity 0.56
Abstract · 40 pages

We study online vector balancing with $N$ random vectors in $\mathbb{R}^M$ revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival. The goal is to minimize the expected $\ell^\infty$ norm of the final signed sum. For i.i.d. entries with mean zero, variance one, and a finite fourth moment, we prove that, as $M/N\toα\in(0,\infty)$, the optimal value divided by $\sqrt N$ converges to a limit $R_α$ independent of the entry distribution. This limit is the stochastic control value identified for Gaussian inputs by Fiedler, Jackson, Lacker, and Niles-Weed. In particular, it determines the exact asymptotic optimum for Rademacher inputs. For every $κ>R_α$, we construct a randomized online algorithm whose final signed sum has $\ell^\infty$ norm at most $κ\sqrt N$ with high probability; for $κ<R_α$, every online algorithm has vanishing success probability. Consequently, the online threshold of the symmetric binary perceptron is universal at every positive margin. The main step is a coupling that transfers Brownian controls to non-Gaussian inputs, while truncation controls rare large entries.

0.44

Adversarially Robust PAC Learning with Optimal VC Rates

cs.LG stat.MLmath.ST ·2026-09-21 ·Steve Hanneke, Amirreza Shaeiri
theory similarity 0.56
Abstract · 35 pages, 2 figures

We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over $\mathcal{X} \times \{0,1\}$, as in classical PAC learning. However, given a perturbation map $\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}}$ known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation $z \in \mathcal{U}(x)$ of most future examples $(x,y)$ drawn from the same underlying distribution. We determine the \emph{optimal} $\mathcal{U}$-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class $\mathcal{H}$ of $\operatorname{VC}$ dimension $d$, we prove upper bounds of $\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big)$ in the realizable setting and $\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big)$ in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs \emph{no additional} distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call \emph{binomial-bagging}. We believe that binomial-bagging and its analysis may be of independent interest.

0.17