- 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
- 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.”
-
Algorithm 1 is given in the introduction, prior to defining the problem and the notation. I had to skip it.
-
The preliminaries section focuses on notation only, which are all standard, and does not define what problem is being solved.
-
I skimmed through the paper, and could not find a proper problem definition.
-
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
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:
-
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.
-
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.
-
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?
-
Avoid AI generated nicknames to notion in the paper, such as “Metropolis-adjusted”, “target”, “constant-subgaussian”.
-
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.
- 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 , 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.
- 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.
- 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 with . At each step, we flip a coin whose bias depends on the current state , and move towards or . As discussed, we want the induced invariant distribution of the walk to be -subgaussian for a constant . The symmetry of the increments motivates a symmetric distribution.
A first candidate is a two-point invariant distribution with equal mass at and , so that the distance between the two points equals the step length . This is the distribution of , where . It is a mixture of two Dirac measures, or point masses,
To preserve this distribution, the walk must move from to and back deterministically. Thus, if denotes the probability of moving towards from state , and denotes the probability of moving towards , invariance forces
When initialized at either support point, this walk alternates deterministically between and . However, this construction does not specify transitions at other states , 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 gives the random vector:
Equivalently, we can write this mixture as a convex combination of two Gaussian measures with equal weights:
This distribution remains symmetric, while allowing transitions from every state . We later show that this distribution is -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 . In the finite horizon online setting, we have a sequence of vectors , potentially pointing in different directions. Each vector allows a different invariant mixture , 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 , 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 with . At each step , we choose a coefficient to update the current state from to . 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 and use as the common invariant distribution. To incorporate information about the incoming vector and reduce the number of zero steps, we let the component covariance of the proposal's invariant mixture depend on . To determine this covariance, consider an arbitrary update vector with and let , where and . The mixture is centered and has covariance . Matching this covariance to that of the invariant distribution therefore gives
Thus, , and substitution into equation 2 gives exactly the logistic proposal probabilities used in Algorithm 1, taking at step . The reverse of a proposal with sign uses sign , which explains the reverse-proposal factor in the acceptance ratio.
- 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".
- The added paragraph about Markov...
We revised the paragraph in the preliminaries section to read:
Consider a Markov chain and let 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 . Given the current state , a proposal distribution generates a candidate next state . 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 . If the candidate is rejected, the state remains at , 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.
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.
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.
We added the definition of the Metropolis correction [1] to Section 2.1 ("Preliminaries"). The added passage reads:
We also added an explanation in the introduction of why we use a Gaussian distribution. The passage reads:
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.