On-line balancing of random inputs

DOI10.1002/RSA.20955MaRDI QIDQ3386519zbMATH OpenOpenAlexFDO

Authors N. Bansal, Joel Spencer

Publication date 5 January 2021

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.06898

zbMATH Keywords

discrepancyonline algorithmsrandom vectors

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithmic game theory and complexity (91A68)

Abstract: We consider an online vector balancing game where vectors $v_t$, chosen uniformly at random in ${-1,+1}^n$, arrive over time and a sign $x_{t}in-1,+1$ must be picked immediately upon the arrival of $v_t$. The goal is to minimize the $L^{i}nfty$ norm of the signed sum $su{m}_t{x}_t{v}_t$. We give an online strategy for picking the signs $x_t$ that has value $O(n^{1/2})$ with high probability. Up to constants, this is the best possible even when the vectors are given in advance.

Recommendations

• Balancing vectors in the max norm
• Balancing sums of random vectors
• Randomized algorithms for online vector load balancing
• A balancing strategy
• Vector balancing games with aging

Cites work

• Deterministic discrepancy minimization
• Hitting-time and occupation-time bounds implied by drift analysis with applications
• scientific article; zbMATH DE number 734955 (Why is no real title available?)
• On a class of balancing games
• On a lemma of Littlewood and Offord
• On Khintchine inequalities with a weight
• Six Standard Deviations Suffice
• Twice-Ramanujan sparsifiers

Cited in

(18)

• Balancing vectors in the max norm
• Balancing game with a buffer
• Gaussian discrepancy: a probabilistic relaxation of vector balancing
• Algorithmic pure states for the negative spherical perceptron
• Vector Balancing Games with Aging
• Vector balancing games with aging
• Discrepancy theory and related algorithms
• On the atypical solutions of the symmetric binary perceptron
• Searching for (sharp) thresholds in random structures: where are we now?
• Thinning to improve two-sample discrepancy
• Average-case matrix discrepancy: satisfiability bounds
• Weaver's discrepancy for Gaussian random vectors
• Stochastic gradient descent for streaming linear and rectified linear systems with adversarial corruptions
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Smoothed analysis with adaptive adversaries
• Efficient splitting of necklaces
• Overlap gap and computational thresholds in the square wave perceptron
• Discrepancy minimization via a self-balancing walk

This page was built for publication: On-line balancing of random inputs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386519)