Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds

• URL: http://arxiv.org/abs/2606.18218v1
• Date: Tue, 16 Jun 2026 17:47:47 GMT
• Title: Finite-Time Queue Peak Laws in Stochastic Networks: Logarithmic Scaling After Geometric Thresholds
• Abstract summary: We study finite-horizon queue peaks in generalized switches.<n>We show that slack reshapes the finite-time peak law for drift-minimizing scheduling policies.
• Score: 5.115427131586521
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study finite-horizon queue peaks in generalized switches, a standard stochastic-network model in which many queues share constrained service resources. Arrivals may be dependent, time-varying, and adapted to the past; the standing load condition is uniform interior slack, meaning the conditional mean arrival vector stays in a fixed contraction of the capacity region. We show that this slack reshapes the finite-time peak law for drift-minimizing scheduling policies such as MaxWeight. The square-root envelope that is sharp without slack persists only up to a geometry-dependent threshold; beyond that threshold, the running maximum grows only logarithmically with the horizon, both with high probability and in expectation. The mechanism is self-normalization: in the current queue direction, the projected fluctuation scale is normalized by the stabilizing drift scale. This removes capacity geometry from the logarithmic coefficient, while geometry remains in the threshold. Matching lower bounds show that both the logarithmic term and a geometric threshold are unavoidable. When finite-time state-space collapse is available, the threshold can be sharpened using local bottleneck geometry. For generalized input-queued switches, we obtain finite-time peak bounds with tight logarithmic coefficients. Simulations illustrate the two-phase envelope, local geometric refinements, and variance-sensitive improvements predicted by the theory.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Across the Loss Landscape with Progressive Growth [51.366966420881646]
  We show how grow-and-optimize strategies to train toward flatter regions by viewing growth as progressive relaxation.<n>We empirically validate these predictions in controlled toy basins and in a realistic ResNet/CI-100 setting.<n>Although progressive subspace growth reliably produces flatter solutions, curvature reductions do not universally translate into improved test performance, highlighting subtleties in the flatness-generalization connection.
  arXiv  Detail & Related papers  (2026-08-25T13:50:48Z)
• Adaptive Iterative Hard Thresholding for Online High-dimensional Quantile Regression [1.0067421338825542]
  We propose an online sparse-regression framework that alternates subgradient updates with adaptively scheduled hard-thresholding steps.<n>We develop the theory for high-dimensional online quantile regression, a challenging setting in which the loss is nonsmooth.
  arXiv  Detail & Related papers  (2026-06-26T23:44:10Z)
• Continuous-time quantum control across an exponentially small bottleneck in a frustrated Ising ring model [0.0]
  Continuous-time Quantum Annealing (QA) is a strategy for preparing ground state of nontrivial manybody systems.<n>We show how to implement quantum control over the annealing schedule in a frustrated Ising ring.
  arXiv  Detail & Related papers  (2026-06-05T11:38:11Z)
• A Residual-Based Quantum Linear System Algorithm with Dynamic Stopping and Applications to Elliptic PDEs [3.3636842548621275]
  Quantum linear-system algorithms (QLSAs) have rigorous worst-case complexity guarantees, but their runtimes are often chosen from spectral information assumed in advance.<n>What is largely lacking is an a posteriori progress flag: most QLSA, unlike the classical counterparts, do not provide a built-in mechanism to signal whether a particular instance has already converged.<n>We design an augmented dynamics with residual variables, in which measuring a residual register gives an on-the-fly convergence indicator.
  arXiv  Detail & Related papers  (2026-05-07T15:22:55Z)
• Forecasting as Rendering: A 2D Gaussian Splatting Framework for Time Series Forecasting [79.37674445572462]
  Time series forecasting (TSF) remains a challenging problem due to the intricate entanglement of intraperiod-fluctuations and interperiod-trends.<n>Treating reshaped tensors as static images results in a topological mismatch.<n> relying on uniform fixed-size representations allocates modeling capacity inefficiently.<n>TimeGS is a novel framework that fundamentally shifts the forecasting paradigm from regression to 2D generative rendering.
  arXiv  Detail & Related papers  (2026-02-10T14:13:36Z)
• Finite-Time Information-Theoretic Bounds in Queueing Control [54.11376591632282]
  We derive new policies that achieve them-for the total queue length in scheduling problems over processing networks with both adversarial and arrivals.<n>These findings reveal a fundamental limitation on "drift-only" methods and point the way toward principled, non-asymptotic optimality in queueing control.
  arXiv  Detail & Related papers  (2025-06-23T04:14:40Z)
• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise [51.87307904567702]
  Quantile regression is a leading approach for obtaining such intervals via the empirical estimation of quantiles in the distribution of outputs.<n>We propose Relaxed Quantile Regression (RQR), a direct alternative to quantile regression based interval construction that removes this arbitrary constraint.<n>We demonstrate that this added flexibility results in intervals with an improvement in desirable qualities.
  arXiv  Detail & Related papers  (2024-06-05T13:36:38Z)
• Path convergence of Markov chains on large graphs [3.693375843298262]
  We show that as the size of a graph goes to infinity, the random trajectories of the processes converge to deterministic curves on the space of measure-valued graphons. A novel feature of this approach is that it provides a precise exponential convergence rate for the Metropolis chain in a certain limiting regime.
  arXiv  Detail & Related papers  (2023-08-18T00:13:59Z)
• Simulating scalar field theories on quantum computers with limited resources [62.997667081978825]
  We present a quantum algorithm for implementing $phi4$ lattice scalar field theory on qubit computers. The algorithm allows efficient $phi4$ state preparation for a large range of input parameters in both the normal and broken symmetry phases.
  arXiv  Detail & Related papers  (2022-10-14T17:28:15Z)
• Exponential Concentration in Stochastic Approximation [0.8192907805418583]
  We analyze the behavior of approximation algorithms where iterates, in expectation, progress towards an objective at each step. We apply our results to several different Markov Approximation algorithms, specifically Projected Gradient Descent, Kiefer-Wolfowitz and Frank-Wolfe algorithms.
  arXiv  Detail & Related papers  (2022-08-15T14:57:26Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  We consider non- Hilbert optimization using first-order algorithms for which the gradient estimates may have tails. We show that a combination of gradient, momentum, and normalized gradient descent convergence to critical points in high-probability with best-known iteration for smooth losses.
  arXiv  Detail & Related papers  (2021-06-28T00:17:01Z)
• Online Stochastic Convex Optimization: Wasserstein Distance Variation [15.313864176694832]
  We consider an online proximal-gradient method to track the minimizers of expectations of smooth convex functions. We revisit the concepts of estimation and tracking error inspired by systems and control literature. We provide bounds for them under strong convexity, Lipschitzness of the gradient, and bounds on the probability distribution drift.
  arXiv  Detail & Related papers  (2020-06-02T05:23:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.