acceptodds
Under review as a conference paper at ICLR 2027

Walking Logistically, but Lazily, for Online Discrepancy Minimization

Abstract

We study online discrepancy minimization in the oblivious setting, where vectors satisfying are fixed in advance and revealed one at a time. The goal is to assign signs in {} upon arrival while keeping all prefix sums small in norm. (Liu et al., 2022) showed that a parity obstruction prevents a one-dimensional Markov chain with steps in {} from preserving a Gaussian distribution exactly. By allowing coefficients in {}, they constructed a Gaussian fixed-point walk with at least % nonzero coefficients in expectation and an 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 {}, achieving the optimal bound in linear time. We propose two complementary random walks. The first is a Metropolis-adjusted logistic walk, parametrized by , that achieves the optimal discrepancy order while assigning coefficients in {}. The parameter 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 faster than the Gaussian triplet walk and has %% lower mean maximum prefix discrepancy on six datasets, averaging % over those six. At , the adjusted walk is 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 %, observed fraction of zero coefficients than the Gaussian fixed-point walk.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
discrepancy minimization, vector balancing, online algorithms

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_1epSOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper appears to address online discrepancy problem, which to my limited understanding has something to do with linearly combining a streaming set of vectors to minimize a summation of some sort; no problem definition is given so I could not judge these impressions. The paper jumps into jargon heavy literature review, followed highly technical details that are not properly introduced.

Critical strengths

N/A

Critical weaknesses
  1. The introduction is impossible to follow. No problem definition is given, and yet multiple technical details are given in jargon heavy language. Just a few examples, in which I could not understand what the sentence means:

a. “A different question is how few zero updates are needed to preserve an exact Gaussian distribution”

b. “a logistic proposal derived from a two-Gaussian mixture and a Metropolis correction to preserve a common Gaussian target” (I don’t know what a “proposal” is, not what is a “Metropolis correction”, what a “target” is, nor why it should be Gaussian.

c. “The posterior probabilities of the component labels give the logistic sign-selection rule, which exactly preserves the mixture for a fixed update vector.”

  1. Algorithm 1 is given in the introduction, prior to defining the problem and the notation. I had to skip it.

  2. The preliminaries section focuses on notation only, which are all standard, and does not define what problem is being solved.

  3. I skimmed through the paper, and could not find a proper problem definition.

  4. The connection to the scope of ICLR is unclear. There are two lines in the introduction which mention that “online discrepancy minimization” has several applications in AI systems, but again, there is no problem definition, and the connection remains muted.

Questions for authors

I would kindly request the authors to rewrite the paper so as to explain the problem from first principles in a way that would be understandable to readers not familiar with it. Additionally, I would suggest the authors not to mention notions and jargon before properly defining them.

4 comments

We regret that the reviewer found the paper difficult to read. We aim to make our work accessible to the community.

To that end, we revised the introduction and preliminaries to clarify the problem and our contributions.

Problem definition

We kindly note that the problem is described in the first two sentences of the abstract and in the first paragraph of the introduction.

We understand that the absence of a formal mathematical statement may have caused confusion. We have updated the introduction accordingly.

“a logistic proposal derived from a two-Gaussian mixture and a Metropolis correction to preserve a common Gaussian target” (I don’t know what a “proposal” is, not what is a “Metropolis correction”, what a “target” is, nor why it should be Gaussian.

We added the definition of the Metropolis correction [1] to Section 2.1 ("Preliminaries"). The added passage reads:

A Markov chain is a random process whose next-state distribution depends on the past only through its current state. A random walk is a type of Markov chain that evolves through randomly chosen steps in Rd\mathbb{R}^d. The Metropolis–Hastings correction [1], called the Metropolis correction here, modifies the transition rule of such a chain to preserve a chosen target distribution π\pi. Given the current state x\mathbf{x}, a proposal distribution q(⋅∣x)q(\cdot\mid\mathbf{x}) generates a candidate next state y\mathbf{y}. Given this candidate, the proposed move is accepted with probability

for π(x)q(y∣x)>0\pi(\mathbf{x})q(\mathbf{y}\mid\mathbf{x}) > 0. If the candidate is rejected, the state remains at x\mathbf{x}, so the walk takes a zero step. Here π\pi and qq denote densities or probability mass functions. The resulting chain preserves π\pi: if the current state is distributed according to π\pi, so is the next state. In our random walk, the proposed moves are signed vector updates, and rejections discard the corresponding input vectors.

We also added an explanation in the introduction of why we use a Gaussian distribution. The passage reads:

A common approach to analysing online discrepancy algorithms is to show that their partial sums are KK-subgaussian, meaning that their tails are bounded by those of an appropriate Gaussian distribution. Because the Gaussian is rotation invariant, these guarantees hold uniformly in every direction.

We also removed the terms "convex domination" and "parity obstruction" from the introduction because they are not needed to understand our work. We replaced them with simpler explanations to make the introduction easier to follow.

We welcome any further questions the reviewer may have regarding the updated text.

[1] W. Keith Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1):97–109, 1970.

The paper has improved, and I increase my score to “weak reject”, but I retain my opinion that it is not ready for publication in its current form. With the help of my fellow reviewers, I was able to decipher some of the statements and the bottom lines of the paper, but the reader will not have that luxury. For the aid of the authors, I list a few suggestions to improve future versions of the paper:

  1. Concrete comparison to prior art: It appears that Aden-Ali solved the “fully signed” problem, in what sense are your algorithm “complementary”? The exact advantage of your algorithms must be stated clearly early on in the paper.

  2. One of the algorithms (Algorithm 3), even though it plays a sufficiently crucial role in the paper so as to be mentioned in the abstract, is given deep inside the appendix and barely mentioned throughout.

  3. Provide context to the given statements, and explain why they are proved. A few examples:

a. “We first seek a sign-selection rule for updates in …” Why is that done? Does that refer to any particular step in the algorithm? How will this rule be applied and where? Why are we doing this analysis in this section?

b. “We now prove that the logistic update preserves this mixture for an arbitrary component covariance.” What is “logistic update”? Which mixture? Covariance of what? Component of what?

  1. Avoid AI generated nicknames to notion in the paper, such as “Metropolis-adjusted”, “target”, “constant-subgaussian”.

  2. The added paragraph about Markov chains in 2.1 is exemplary of non-human writing: extreme level of details about obvious facts alongside complete omission of crucial ones. It is safe to assume your reader knows what a Markov chain is, and there is no reason to explain it. However, the explanation immediately jumps to: “modifies the transition rule … to preserve a chosen target distribution”. What purpose does it serve? Chosen distribution over what? What is a “proposal distribution”, and who proposes it? What does “move is accepted” mean? “Here pi and q denote densities” is obvious, but what do they represent, who proposes them, and why are they discussed?

We sincerely thank the reviewer for the constructive feedback. We hope that the following changes address the concerns raised.

  1. Concrete comparison to prior art...

We revised the discussion of prior work in the introduction to clarify how our constructions differ from those of Alweiss et al., Liu et al., and Aden-Ali.

[...] We derive this logistic transition rule from the component posterior probabilities of a symmetric mixture of two Gaussians. An interesting observation is that, near the origin, the logistic rule recovers the linear rule of Alweiss et al. (2021) to first order, revealing a natural connection between the two walks. Since the invariant mixture depends on the incoming vector, we introduce a Metropolis correction to preserve a common Gaussian invariant distribution throughout the walk. The resulting transition uses one auxiliary state and explicit probabilities, avoiding the alternating series of Liu et al. (2022).

Although the Gaussian triplet walk of Aden-Ali (2026) achieves a provably optimal prefix discrepancy bound with coefficients in −1,+1\\{-1,+1\\}, our unadjusted logistic walk has slightly lower mean maximum prefix discrepancy on six of seven real datasets and runs more than twice as fast in our Python implementations. These empirical improvements may benefit practical applications of online discrepancy minimization, including those discussed above. Both logistic walks are considerably simpler than the aforementioned walks, while the Metropolis-adjusted logistic walk admits a direct analysis. [...]

Please see the revised manuscript for the full context of these changes.

  1. One of the algorithms (Algorithm 3), even though it plays a sufficiently crucial role...

We agree with the reviewer. The unadjusted logistic walk is now Algorithm 2 in the main text, immediately after Theorem 1.1.

  1. Provide context to the given statements

We thank the reviewer for this suggestion. It helped us identify ways to improve the clarity of our presentation.

3.a We first seek a sign-selection rule for updates...

The revised passage reads:

We now seek to motivate the transition rule for our random walk. We first consider a simplified setting: fix a nonzero vector s∈Rd\boldsymbol{s}\in\mathbb{R}^d with ∥s∥2≤1\lVert \boldsymbol{s}\rVert_2\leq1. At each step, we flip a coin whose bias depends on the current state w∈Rd\boldsymbol{w} \in\mathbb{R}^d, and move towards w−s\boldsymbol{w}-\boldsymbol{s} or w+s\boldsymbol{w}+\boldsymbol{s}. As discussed, we want the induced invariant distribution of the walk to be KK-subgaussian for a constant KK. The symmetry of the increments motivates a symmetric distribution.

A first candidate is a two-point invariant distribution with equal mass at −s/2-\boldsymbol{s}/2 and s/2\boldsymbol{s}/2, so that the distance between the two points equals the step length ∥s∥2\lVert \boldsymbol{s}\rVert_2. This is the distribution of bs/2\mathrm{b}\boldsymbol{s}/2, where b∼Rad⁡(1/2)\mathrm{b} \sim \operatorname{Rad}(1/2). It is a mixture of two Dirac measures, or point masses,

To preserve this distribution, the walk must move from −s/2-\boldsymbol{s}/2 to s/2\boldsymbol{s}/2 and back deterministically. Thus, if p+(w)p^+(\boldsymbol{w}) denotes the probability of moving towards w+s\boldsymbol{w}+\boldsymbol{s} from state w\boldsymbol{w}, and p−(w)=1−p+(w)p^-(\boldsymbol{w})=1-p^+(\boldsymbol{w}) denotes the probability of moving towards w−s\boldsymbol{w}-\boldsymbol{s}, invariance forces

p+(s/2)=0.\qquad p^+(\boldsymbol{s}/2)=0.

When initialized at either support point, this walk alternates deterministically between −s/2-\boldsymbol{s}/2 and s/2\boldsymbol{s}/2. However, this construction does not specify transitions at other states w\boldsymbol{w}, beyond the two support points.

A natural way to overcome this limitation is to introduce some Gaussian noise to smooth the two-point distribution. This choice is also supported by the subgaussianity requirement. Adding g0,Id\mathbf{g}_{0,\boldsymbol{I}_d} gives the random vector:

Equivalently, we can write this mixture as a convex combination of two Gaussian measures with equal weights:

12N(−s/2,Id)+12N(s/2,Id). \frac12\mathcal{N}(-\boldsymbol{s}/2,\boldsymbol{I}_d) +\frac12\mathcal{N}(\boldsymbol{s}/2,\boldsymbol{I}_d).

This distribution remains symmetric, while allowing transitions from every state w∈Rd\boldsymbol{w}\in\mathbb{R}^d. We later show that this distribution is O(1)O(1)-subgaussian. [...]

We also added the definition of the Dirac measure to the preliminaries.

3.b We now prove that the logistic update...

We expanded the explanation as follows:

[...] The above lemma concerns a fixed vector s\boldsymbol{s}. In the finite horizon online setting, we have a sequence of vectors v1,…,vT\boldsymbol{v}_1,\ldots,\boldsymbol{v}_T, potentially pointing in different directions. Each vector allows a different invariant mixture mvi,Σ\mathbf{m}_{\boldsymbol{v}_i,\boldsymbol{\Sigma}}, and hence a different logistic transition rule. We overcome this obstacle by applying a Metropolis correction that preserves a common invariant distribution at every step. The correction allows δt=0\delta_t=0, so some input vectors are discarded. Although we do not establish discrepancy guarantees for the (unadjusted) logistic walk, it maintains low discrepancy in every setting considered in Section 4.

2.4 A Metropolis-adjusted logistic walk

Consider a finite sequence of vectors v1,…,vT∈Rd\boldsymbol{v}_1,\ldots,\boldsymbol{v}_T\in\mathbb{R}^d with ∥vi∥2≤1\lVert \boldsymbol{v}_i\rVert_2\leq1. At each step tt, we choose a coefficient δt∈−1,0,+1\delta_t\in\\{-1,0,+1\\} to update the current state from xt−1\mathbf{x}_{t-1} to xt=xt−1+δtvt\mathbf{x}_t=\mathbf{x}_{t-1}+\delta_t\boldsymbol{v}_t. Telescoping the updates gives

Since we need the invariant distribution to have a constant subgaussian parameter, a natural choice is a centered Gaussian distribution. We fix β>1\beta > 1 and use N(0,β2Id/4)\mathcal{N}(0,\beta^2\boldsymbol{I}_d/4) as the common invariant distribution. To incorporate information about the incoming vector v\boldsymbol{v} and reduce the number of zero steps, we let the component covariance of the proposal's invariant mixture depend on v\boldsymbol{v}. To determine this covariance, consider an arbitrary update vector v∈Rd\boldsymbol{v}\in\mathbb{R}^d with ∥v∥2≤1\lVert \boldsymbol{v}\rVert_2\leq1 and let z:=Σ1/2g+bv2=dmv,Σ\mathbf{z}:=\boldsymbol{\Sigma}^{1/2}\mathbf{g}+\frac{\mathrm{b}\boldsymbol{v}}{2}\overset{\mathrm d}{=}\mathbf{m}_{\boldsymbol{v},\boldsymbol{\Sigma}}, where g∼N(0,Id)\mathbf{g}\sim\mathcal{N}(0,\boldsymbol{I}_d) and b∼Rad⁡(1/2)\mathrm{b}\sim\operatorname{Rad}(1/2). The mixture is centered and has covariance Cov⁡(z)=Σ+vv⊤4\operatorname{Cov}(\mathbf{z})=\boldsymbol{\Sigma}+\frac{\boldsymbol{v}\boldsymbol{v}^\top}{4}. Matching this covariance to that of the invariant distribution therefore gives

Thus, Σ−1v=4vβ2−∥v∥22\boldsymbol{\Sigma}^{-1}\boldsymbol{v}=\frac{4\boldsymbol{v}}{\beta^2-\lVert \boldsymbol{v}\rVert_2^2}, and substitution into equation 2 gives exactly the logistic proposal probabilities used in Algorithm 1, taking v=vi\boldsymbol{v}=\boldsymbol{v}_i at step ii. The reverse of a proposal with sign εi\varepsilon_i uses sign −εi-\varepsilon_i, which explains the reverse-proposal factor pi−εi(x+εivi)p_i^{-\varepsilon_i}(\boldsymbol{x}+\varepsilon_i\boldsymbol{v}_i) in the acceptance ratio.

  1. Avoid AI generated nicknames to notion....

In the revised explanation, we use "O(1)-subgaussian" and "invariant distribution" in place of "constant-subgaussian" and "target". We kept "Metropolis-adjusted" because it is standard terminology. Examples include the Metropolis-adjusted Langevin algorithm. We also use "transition rule" in place of "sign-selection rule".

  1. The added paragraph about Markov...

We revised the paragraph in the preliminaries section to read:

Consider a Markov chain and let π\pi be the desired stationary distribution. The Metropolis–Hastings correction (Hastings, 1970), called the Metropolis correction here, modifies the transition rule of a Markov chain to preserve a distribution π\pi. Given the current state x\boldsymbol{x}, a proposal distribution q(⋅∣x)q(\cdot\mid\boldsymbol{x}) generates a candidate next state y\boldsymbol{y}. Given this candidate, the proposed move is accepted with probability

\frac{\pi(\boldsymbol{y})\\,q(\boldsymbol{x}\mid\boldsymbol{y})} {\pi(\boldsymbol{x})\\,q(\boldsymbol{y}\mid\boldsymbol{x})}\right\\},

for π(x)q(y∣x)>0\pi(\boldsymbol{x})q(\boldsymbol{y}\mid\boldsymbol{x}) > 0. If the candidate is rejected, the state remains at x\boldsymbol{x}, so the walk takes a zero step. In our random walk, the proposed moves are signed vector updates, and rejections discard the corresponding input vectors.

Finally, we moved the paragraph on structured vector sequences from the introduction to the appendix to keep the introduction focused on the oblivious setting.

We kindly refer the reviewer to the revised manuscript for the full context of these changes.

We remain available for any further questions.

Reviewer_9tvoOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper considers the problem of online discrepancy minimization. In this problem, a sequence of TT vectors vi∈Rnv_i\in \mathbb{R}^n with ∣vi∣≤2|v_i| \leq 2 arrives online. The goal is to assign signs xi∈{−1,1}x_i\in \{-1,1\} so that every prefix sum ∑itxivi\sum_{i}^t x_iv_i is small in the ℓ∞\ell_{\infty} norm. This is known as the discrepancy. This problem has been studied intensely by the TCS community. A common approach followed in the prior work (Alweiss et al (2021), Liu et al (2022), Kulkarni et al (2024)) is to give online algorithms that generate random signs so that every prefix sum is kk-subgaussian. From standard concentration bounds, it can be argued that the prefix discrepancy is at most O(Klog⁡T)O(K\sqrt{\log T}). A summary of some relevant results is as follows:

Liu et al designed an algorithm which drops a small fraction of the vectors (that is, gives them sign 0), and achieves a discrepancy bound of O(log⁡T)O(\sqrt{\log T}). From what I understand, they assign signs in a way that the prefix sums correspond to a Gaussian fixed point walk. That is, ∑i=1t=−G0+Gt\sum_{i=1}^{t}=-G_0+G_t, where GtG_t and G0G_0 are both marginally distributed as a 0 mean Gaussian.

Kulkarni et al showed there exists an algorithm which achieves O(log⁡T)O(\sqrt{\log T}) discrepancy, and they also show this is optimal. But their algorithm is slow, running in time is exponential.

Building on the work of Liu et al, Aden-Ali showed that if the prefix sum correspond to coupled three copies of the Gaussian fixed point walk, then one obtain a discrepancy bound of O(log⁡T)O(\sqrt{\log T}) and his algorithm has a runtime of O(nT)O(nT).

In this work, the authors propose what they term as a “Metropolis-adjusted logistic walk”, which works as follows:

Derive a logistic sign selection rule from the posterior of a two-Gaussian mixture and choose the mixture covariance so that it matches a common Gaussian target.

This rule has a good property that if the update vector was the same in each step, then the distribution is exactly preserved. The authors show that this rule already performs well empirically, but do not show guarantees. To allow for the distribution to be preserved even if the update vectors change, the authors accept/reject the proposed move with some probability (the metropolis correction).

Critical strengths

The paper presents two complementary walks, called metropolis adjusted random walk for online discrepancy minimization problem that has the optimal discrepancy bound. While I haven’t carefully checked the claims, I believe they are correct. To prove the guarantees of the first walk, they follow a similar proof strategy as in other papers in the literature, i.e. showing that all prefix sums are sub-Gaussian with a constant factor, which by known concentration bounds implies the discrepancy result. This is a non-trivial theoretical contribution.

They also provide a bound on the probability that a vector is dropped. This also adds to their theoretical contribution.

The idea of using Metropolis correction to make sure the prefix sum is a Gaussian is interesting. The authors mention that their approach is easier than that of Liu et al, who also want to keep the prefix sum a Gaussian, but they do so by assigning transition probabilities to the possible next states. From what I understand this transition rule is hard to calculate numerically

The current algorithm also performs better than the algorithm of Aden-Ali on real world data sets.

Critical weaknesses

The unadjusted random walk, which seems to perform well empirically, is not supported by a theoretical guarantee.

From what it seems to me, subsequent to the work of Aden-Ali (2026), the problem of online discrepancy is essentially “solved” especially since his algorithm is theoretically efficient. AFAICT the main motivation behind these results is that they perform better empirically. The authors say that they are concerned with practical performance because of applications to KV-cache compression and streaming attention approximation. I would help if the authors could better explain how improvement in prefix discrepancy lead to gains in those applications.

While the paper says that their walks are complementary to Aden-Ali, it seems they solve a relaxed version of the problem where one is allowed to drop some constraints.

I think the introduction could be written better. To understand the broader context, I had to look at Aden-Ali 2026. For example, in many places why not just write the math instead of writing the text. It makes the text unambiguous IMO, and in any case the person who is reading the paper will be writing the math down anyway! Some examples of this are:

Paragraph 1 on pg 1: “the goal is to keep the infinity norm of every partial sum small”-> “the goal is to minimize max⁡t∑∥xivi∥∞\max_{t}\sum \|x_i v_i\|_{\infty}”

Paragraph 3 on page 2 uses a lot of technical jargon like “convex-domination argument” or “linear sign selection rule”.

“A different question is how few 0 updates are needed to preserve an exact Gaussian distribution” -> it look me a really long time to understand that in this case one is studying a relaxation where one can drop certain vectors or assign sign 0. This actually might be worth writing properly as this is precisely the setting the authors also study!

What is the parity obstruction? It seems that this reason is why the work of Liu et al allows for assigning sign 0 to the vectors. Again, authors study the same relaxation. Perhaps its worth mentioning what this is?

Questions for authors

None.

3 comments

We thank the reviewer for their comments. We address the points in the order raised:

It would help if the authors could better explain how improvement in prefix discrepancy lead to gains in those applications.

We have clarified this connection in the applications paragraph of the introduction. Improvements in discrepancy minimization can yield more accurate data summaries and reduce the time needed to construct them.

For example, in the KV cache application, Kochetkova et al. [1] recursively select smaller sets of vectors to approximate the full attention computation. Lower discrepancy in these balancing steps can reduce approximation error at a fixed cache size, while faster signing can reduce the cost of constructing the compressed cache.

We revised the relevant paragraph in the introduction to explain these applications more clearly.

We kindly refer the reviewer to our response to Reviewer 5ACf for additional applications of online discrepancy minimization that we added to the introduction.

[1] Ekaterina Kochetkova, Kshiteej Jitesh Sheth, Insu Han, Amir Zandieh, and Michael Kapralov. Streaming attention approximation via discrepancy theory. Advances in Neural Information Processing Systems, 38:20935–20972, 2026.

I think the introduction could be written better.

We thank the reviewer for these comments. We revised the introduction to include the precise mathematical formulation of the problem.

We removed the terms "convex domination" and "parity obstruction" from the introduction because they are not needed to understand our work. We replaced them with simpler explanations to make the introduction easier to follow.

We are available to address any further questions the reviewer may have regarding the updated text.

I thank the authors for their responses. I maintain my score, I still lean towards acceptance. I hope the authors will consider my suggestions considering the presentation of the introduction. I suggest that the authors should focus on making it sure that the paper can be appreciated for readers not familiar with Aden-Ali 2026.

Dear reviewer,

We have updated the manuscript to clarify the contributions and provide a more detailed discussion of prior work. We hope these revisions address your concerns and make the paper easier to follow for readers unfamiliar with the work of Aden-Ali.

We refer the reviewer to our response to Reviewer 1epS for a more detailed explanation of the changes and to the uploaded revised manuscript for the full context.

We would be happy to answer any further questions.

Best, the authors

Reviewer_5ACfOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the problem of online discrepancy minimization: a sequence of vectors v_1, v_2, ... arrive in order. When v_i arrives, the algorithm must assign a sign \epsilon_i. The goal is to ensure that || \sum_j \epsilon_j v_j ||_\infty (which is called the discrepancy) remains small at all time steps. Recent works have shown that \sqrt{\log T} is a tight bound for the max discrepancy. In the spirit of the classic work of Spencer, many works only achieve something slightly weaker: they assign \epsilon_i \in {0, \pm 1} instead of just {\pm 1}, and post-hoc ensure that the number of i's assigned 0 is small.

The main result of the paper is a simple algorithm that achieves a "partial coloring" guarantee as above; the algorithm has a parameter \beta, and depending on the value, a small subset of the i's (in expectation) get ϵi=0\epsilon_i =0 and the rest of the i's satisfy ϵi∈{±1}\epsilon_i \in \{\pm 1\}. As far as the result goes, this is weaker than the bounds from the very recent work of Aden-Ali (who achieves a full coloring, i.e., no zero assignments). However, the algorithm is a bit simpler, and as the authors show, also about 2x faster. The paper also gives another simple algorithm that always gives a \pm 1 coloring to a vector as it arrives, but they do not prove a discrepancy bound, instead they demonstrate its effectiveness via experiments.

Critical strengths
  • The algorithm given is quite simple. Given a current "state" x (signed sum so far), when a next vector v arrives, the algorithm determines if v should get a +1 or -1 sign using an interesting procedure: they consider appropriate Gaussians centered at +v/2 and -v/2, and then try to infer which Gaussian the 'x' is likely to have come from; using this, they determine the sign (the details here are important and this is what distinguishes from other works).

  • The authors are quite clear about their results and limitations (e.g., the lack of concentration in Prop 3.2)

Critical weaknesses
  • The algorithm and analysis, though clean, come across as slight modifications of existing results.
  • I am not sure if the 2x improvements in runtime is too significant, given the primarily theoretical nature of the problem. (The authors do try to make the case for applicability, e.g., in KV cache compression, but this still seems like a stretch.)
  • The result of Aden-Ali undermines the current paper; also the work of Liu et al. from 4 years ago already achieves similar bounds (albeit slightly weaker, but with better concentration). The Smirnov-Vershynin paper is also quite similar in spirit. Given these, I think the paper is not showing something too significant. (Given that the result is AI-assisted, it feels a bit on the weak side in terms of results.)
Questions for authors
  • The proof seems to closely align with that of Aden-Ali, and also the other recent works cited (in the review above). Can the authors highlight some of the novel aspects? Specifically the bounds in Lemma 3.1 seem new?

  • Can the authors give a bit more of the implementation details and wall-clock time comparisons for the experiments? Given that the performance difference is somewhat small (~2x change), it is not clear if slight optimizations can actually bridge the gap..

  • How are the norms of the data points distributed in the experiments?

4 comments

We thank the reviewer for their comments. We address the weaknesses and questions below.

We address the first and third weaknesses together with the first question, as they raise similar points.

The algorithm and analysis, though clean, come across as slight modifications of existing results.

The proof seems to closely align with that of Aden-Ali, and also the other recent works cited (in the review above). Can the authors highlight some of the novel aspects? Specifically the bounds in Lemma 3.1 seem new?

The result of Aden-Ali undermines the current paper; also the work of Liu et al. from 4 years ago already achieves similar bounds (albeit slightly weaker, but with better concentration). The Smirnov-Vershynin paper is also quite similar in spirit. Given these, I think the paper is not showing something too significant. (Given that the result is AI-assisted, it feels a bit on the weak side in terms of results.)

To control deviations in every direction, our analysis uses a subgaussian distribution whose law is unchanged by rotations, giving uniform bounds over all directions. To this end, we attempt to show that the subgaussian distribution remains invariant under the random walk. This is a standard tool in the analysis of random walks.

Liu et al. use a sign-selection rule based on a convergent series and show that an exact Gaussian distribution can be maintained with an expected fraction of zero steps of at most 4%.

Aden-Ali uses a different approach based on coupling three Gaussian walks whose sign increments sum to −1-1 or +1+1, allowing a nonzero sign to be assigned to every vector.

Our constructions are fundamentally different: both logistic walks are based on a mixture of two Gaussian distributions and use a sign-selection rule derived from the sigmoid function. The Metropolis-adjusted logistic walk adds a Metropolis correction, which omits some vectors. To the best of our knowledge, these constructions are new.

Smirnov and Vershynin also use a Metropolis correction, but their setting and results differ from ours. They study how to keep a random walk inside a convex body. Their proposed signs are independent and uniformly random, while our sign probabilities depend on the current state. They guarantee that the walk stays inside the body, with the expected number of discarded steps controlled by a quantity based on Fisher information.

Lemma 3.1 gives an explicit bound on the zero-update probability, averaged over the Gaussian state distribution. It also bounds the expected fraction of zero updates. To our knowledge, this bound for the Metropolis-adjusted logistic rule is new, but we do not claim that it is a significant contribution.

We updated the introduction to clarify our contributions and their relationship to prior work.

I am not sure if the 2x improvements in runtime is too significant, given the primarily theoretical nature of the problem. (The authors do try to make the case for applicability, e.g., in KV cache compression, but this still seems like a stretch.)

We thank the reviewer for this comment. It motivated us to look further into applications of online discrepancy minimization.

In addition to the applications already mentioned, we identified several recent works that use online discrepancy minimization in different contexts:

  • Covariate balancing and average treatment effect estimation: Ren et al. [1] use discrepancy-based data summaries to balance observed features across treatment groups and estimate average treatment effects in streaming data.
  • Accelerating training through data orderings for stochastic gradient descent: Lu et al. [2] and Cooper et al. [3] use online gradient balancing to achieve faster convergence than random reshuffling in centralized and distributed training, respectively.
  • Online envy minimization in fair division: Halpern et al. [4] connect online discrepancy minimization to reducing envy when indivisible items arrive sequentially.

Discrepancy minimization provides a way to reduce the complexity of large combinatorial objects. These applications involve sequential data or decisions and benefit from efficient online algorithms. This is a central reason why we believe our work can be valuable to the community.

We updated the introduction to include these applications and revised the conclusion to better reflect this broader motivation.

[1] Yixin Ren, Chenghou Jin, Yewei Xia, Zichuan Lin, Deheng Ye, Hao Zhang, Jihong Guan, and Shuigeng Zhou. Streaming Covariate Balancing via Discrepancy-Based Feature Coresets. Forty-third International Conference on Machine Learning, 2026.

[2] Yucheng Lu, Wentao Guo, and Christopher M. De Sa. GraB: Finding provably better data permutations than random reshuffling. Advances in Neural Information Processing Systems, 35:8969–8981, 2022.

[3] A. Feder Cooper, Wentao Guo, Duc Khiem Pham, Tiancheng Yuan, Charlie Ruan, Yucheng Lu, and Christopher M. De Sa. Coordinating distributed example orders for provably accelerated training. Advances in Neural Information Processing Systems, 36:56198–56210, 2023.

[4] Daniel Halpern, Alexandros Psomas, Paritosh Verma, and Daniel Xie. Online Envy Minimization and Multicolor Discrepancy: Equivalences and Separations. Proceedings of the 26th ACM Conference on Economics and Computation, page 188, 2025.

Can the authors give a bit more of the implementation details and wall-clock time comparisons for the experiments? Given that the performance difference is somewhat small (~2x change), it is not clear if slight optimizations can actually bridge the gap.

For a direct comparison, our implementations closely follow the respective algorithms. We evaluate the Metropolis acceptance probability in logarithmic form, a standard practice for numerical stability. Beyond such numerical choices, we aim to stay faithful to the algorithms. Implementation details are given in Appendix B.1, and Table 2 reports absolute wall-clock times.

Since we compare unoptimized implementations, we cannot rule out that further optimization could narrow or close the observed gap. In our measurements, the unadjusted logistic walk is 2.282.28–2.77×2.77\times faster than the Gaussian triplet walk across the seven real datasets. Aden-Ali's algorithm jointly updates three Gaussian walks to produce a single sign, whereas our unadjusted logistic walk uses a single random walk initialized from a Gaussian distribution. The additional calculations offer a plausible explanation for the runtime difference.

We updated the Experiments section to communicate the results more clearly. Implementation details remain in Appendix B.

How are the norms of the data points distributed in the experiments?

The setting we study requires ∥vt∥2≤1\|v_t\|_2\leq1, so we scaled each real dataset by a common factor where needed, preserving relative vector lengths. This preprocessing is already described in Appendix B.1 ("Datasets and preprocessing"), with the scaling factors reported in Table 3. For ArXiv and LAION, all original vector norms were already within 2×10−72\times10^{-7} of one before this scaling.

The table summarizes vector lengths after preprocessing.

DatasetMin25th percentileMedian75th percentileMax
MNIST0.2080.4670.5360.6031.000
NYTimes0.0000.8060.8300.8551.000
SIFT1M0.9900.9940.9950.9961.000
GIST0.0000.2620.3190.3721.000
Llama0.4490.7650.7990.8331.000
ArXiv1.0001.0001.0001.0001.000
LAION1.0001.0001.0001.0001.000

These results show a range of vector lengths across the real datasets. MNIST, NYTimes, GIST, and Llama have broader length distributions, while SIFT1M, ArXiv, and LAION are concentrated near unit length.

For the synthetic datasets, the sphere, basis-cycle, correlated, and blocks families contain vectors of unit length, up to numerical rounding. The varying-norm family cycles through 0.05,0.1,0.25,0.5,0.75,10.05,0.1,0.25,0.5,0.75,1, with each length occurring approximately equally often. The constructions are described in Appendix B.3.

Dear reviewer,

We have updated the manuscript. Changes include clarifications of the contributions, a more detailed discussion of prior work, and a more thorough explanation of the logistic transition rule and the derivation of the Metropolis-adjusted logistic walk.

We refer the reviewer to our response to Reviewer 1epS for a more detailed explanation of the changes and to the uploaded revised manuscript for the full context.

We remain available for any further questions.

Best, the authors.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.