Walking Logistically, but Lazily, for Online Discrepancy Minimization

We study online discrepancy minimization in the oblivious setting, where vectors $v_1,\dots ,v_T\in {\mathbb{R}}^d$ satisfying $\Vert v_i{\Vert }_2\le 1$ are fixed in advance and revealed one at a time. The goal is to assign signs in {$-1,+1$} upon arrival while keeping all prefix sums small in ${\ell }_{\infty }$ norm. (Liu et al., 2022) showed that a parity obstruction prevents a one-dimensional Markov chain with steps in {$-1,+1$} from preserving a Gaussian distribution exactly. By allowing coefficients in {$-1,0,+1$}, they constructed a Gaussian fixed-point walk with at least $96$% nonzero coefficients in expectation and an $O(\sqrt{\log T})$ prefix discrepancy bound with high probability, matching the optimal order for fully signed online discrepancy. More recently, (Aden-Ali, 2026) introduced the Gaussian triplet walk, which couples three Gaussian fixed-point walks to assign signs in {$-1,+1$}, achieving the optimal bound in linear time. We propose two complementary random walks. The first is a Metropolis-adjusted logistic walk, parametrized by $\beta$, that achieves the optimal discrepancy order while assigning coefficients in {$-1,0,+1$}. The parameter $\beta$ controls both the subgaussian parameter of the partial sums and the uniform upper bound on the expected fraction of zero coefficients. The second is a fully signed, unadjusted logistic walk that lacks a proved optimality guarantee but is empirically competitive. Across seven real datasets, the unadjusted walk is $2.28-2.77\times$ faster than the Gaussian triplet walk and has $3.5$%$-11.6$% lower mean maximum prefix discrepancy on six datasets, averaging $7.9$% over those six. At $\beta =2$, the adjusted walk is $1.89-2.22\times$ faster than the Gaussian triplet walk and also has lower mean maximum prefix discrepancy on six datasets, while incurring a higher, though still less than $1.8$%, observed fraction of zero coefficients than the Gaussian fixed-point walk.