- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper extends online regression with paid noisy features (Merlis et al., 2026) from squared loss to logistic loss. Proposition 1 shows that noise covariance does not determine the optimized logistic loss. Under an ordered additive-degradation assumption, the authors give two results. With known increment distributions, a grid-elimination algorithm reuses high-payment observations as simulated lower-payment samples and achieves Õ(√(dT)) regret. With unknown distributions, a grid-LCB algorithm achieves Õ(T^{2/3}) regret. Both rates come with matching lower bounds in T.
Critical strengths
Natural extension to binary outcomes; clearly identifies what breaks relative to the squared-loss case.
The simulation-by-degradation idea is elegant: all active payments share one sample stream, so the statistical error depends only logarithmically on the grid size.
Rates are tight in T in both regimes. The unknown-profile lower bound requires a non-trivial regularity and inversion argument for the Gaussian logistic loss.
Well written; proofs appear sound.
Critical weaknesses
Incremental relative to Merlis et al. (2026): the algorithms, rates, and lower-bound strategy closely mirror the linear case. The genuinely new steps should be stated explicitly.
Proposition 1 is close to immediate for a non-quadratic loss. Its construction is degenerate (deterministic X = 1, discrete noise). Non-degenerate examples, e.g. Gaussian X, would be more convincing.
Assumption 2 is stronger than what is used. The unknown-profile result needs only monotonicity, i.e. one-sided Lipschitzness, of the loss in c. The known-profile result needs only a known garbling (Blackwell) kernel, of which additive noise is a special case.
Exact samplers for all increment distributions is a strong requirement. Robustness to misspecified samplers is not discussed.
Second-order properties logistic regression are discussed in such references as Drmota et al (2025, "Precise Regularized Minimax Regret with Unbounded Weights" ) and Drmota 2026, ALT 2026 ("Phase transition of Regret for Logistic Regression with Large Weights" ..". The authors should also inspect Wu at al " Information-theoretic Limits of Online Classification with Noisy Labels" (Neurips 2024).
The lower bounds are one-dimensional, so the dependence on d is not shown to be tight. There are no numerical illustrations.
Typos: "the the", "how how", "estalishes", "imporatant", and duplicated contribution headers.
Questions for authors
Does Theorem 10 hold under monotonicity of L⋆(c) − λc alone?
Does the known-profile result extend to general known garbling kernels?
How does sampler misspecification enter the regret?
3 comments
References (W5): We thank the reviewer for these suggestions. We added Drmota et al. (2025, 2026), which characterize fixed-design minimax log-loss regret, to our discussion of online logistic regression in related work (Appendix A). We also added Wu et al. (2024), which study noiseless features and stochastically corrupted labels, to our discussion of online learning with noisy information.
Lower bound (W6): Our one-dimensional lower bounds establish optimal dependence on , up to logarithmic factors, but do not establish tight dependence on . We conjecture that the dimension dependence in our upper bounds is also tight. Achieving the conjectured dimension dependence requires a multidimensional hard-instance construction and remains an open problem. We now consistently restrict our optimality claims to the dependence on .
Numerical illustration (W7): We added synthetic experiments in Appendix L, comparing Algorithms 1 and 2 with ETC, fixed-payment policies, and an oracle-payment reference. The experiments use Gaussian features and a Gaussian noise profile satisfying Assumption 2, with , four acquisition-cost levels, and 20 independent runs. Algorithm 1 has lower mean regret than Algorithm 2 at every tested cost, illustrating the benefit of reusing high-payment observations at lower payments.
Theorem 10 (Q1): Yes, it is the direct result of monotonicity of prediction loss, in . Assumption 2 is a sufficient condition for this monotonicity. In particular, for ,
\leq L^\star(c_1)+\lambda(c_2-c_1).$$ This is the only cross-payment property used in the proof, which yields the discretization bound in Eq. (12) (p. 26); the remaining argument uses only payment-wise concentration. Therefore, Assumption 2 is a sufficient, but not necessary, condition for Theorem 10. We again thank the reviewer for the detailed and thoughtful review. The comments helped us sharpen the contributions and assumptions of the paper, and we would be happy to clarify any remaining questions.Thank you for your response. I maintain my score.
We thank the reviewer for the detailed and constructive feedback.
Incremental contribution (W1): The extension to logistic response model with logistic loss is natural, but the results do not follow directly by simply replacing quadratic loss with logistic loss. In Section 2.1, we show that covariance alone neither determines the optimized logistic loss nor guarantees that covariance ordering agrees with optimized-loss ordering. Thus, the covariance-based reduction used under squared loss does not carry over directly as in Merlis et al. (2026). This motivates our ordered additive-degradation condition (Assumption 2) and the one-way simulation principle underlying Algorithm 1.
We agree that the basic observation that covariance may be insufficient for a nonquadratic loss is not by itself surprising. Proposition 1 instead formally introduce the precise failure relevant to our problem at the level of optimized prediction loss and explains why an additional distributional structure is needed. In response to the reviewer, we also strengthened the result from the original deterministic-feature case to a non-degenerate Gaussian feature case in Appendix C (Proof of Proposition 1).
The new technical steps are as follows. First, we establish uniform concentration of the logistic loss over the entire predictor class under sub-Gaussian features (Proposition 3) with any payment. Second, we prove that, even under adaptive payment choices, a high-payment observation can be transformed into a statistically valid lower-payment observation (Proposition 4). This permits all active lower payments to share one sample stream and leads to the simulation-based elimination algorithm (Algorithm 1). Third, both lower bounds require logistic-specific constructions. For the known-profile lower bound, we establish a transverse crossing between optimized Gaussian logistic risks in two payment regions. For the unknown-profile lower bound, we prove strict monotonicity and regularity of the optimized Gaussian logistic risk, construct a controlled inverse, and use it to realize flat and locally perturbed optimized-loss profiles. These constructions do not follow from the squared-loss proof because optimized logistic risk has no closed-form covariance representation.
Proposition 1 (W2): In Appendix C, we additionally provide the Gaussian feature case, where X∼N(1,σ2), and show that the conclusions of Proposition 1 continue to hold for sufficiently small σ>0.
Assumption 2 (W3, Q2): We believe that Assumption 2 is sufficient but not minimal.
For the known-profile result, additive degradation can be replaced by a known and samplable garbling kernel Gc1,c2 for c1≤c2, provided that a sample X(c1)∼Gc1,c2(X(c2),⋅) satisfies
\overset{d}{=} \bigl(\widehat X(c_1),Y\bigr),$$ is mean preserving and satisfies the required tail condition. The first condition enables exact reuse of higher-payment observations, while mean preservation gives the loss ordering through Jensen’s inequality. Assumption 2 guarantees all these properties through an independent mean-zero increment. Please see our response to Reviewer iFxT on general stochastic degradation for more detailed discussion. **Sampler misspecification (W4, Q3):** Studying sampler misspecification provides an interesting extension of our current analysis, and we thank the reviewer for this suggestion. In Appendix K, we added an analysis assuming that each approximate increment can be coupled with the exact increment with almost-sure error at most $\varepsilon$. Since logistic loss is $1$-Lipschitz in its score and $\| \nu\|_2\leq S$, the approximate and exact empirical losses differ by at most $S\varepsilon$ uniformly across the predictors. If the learner knows an upper bound on $\varepsilon$, it can enlarge the confidence radius by $S\varepsilon$, which preserves the elimination argument and adds $O(S\varepsilon T)$ to the regret. If the learner is unaware that misspecification exists and runs the original algorithm, the optimal payment may be eliminated. Nevertheless, each elimination increases the best remaining population loss by at most $2S\varepsilon$, giving an additional $O(S\varepsilon T\log T)$ term. If the learner knows that misspecification may exist but does not know its magnitude, an additional mechanism for estimating or upper-bounding $\varepsilon$ would be required. Thus, the robustness guarantee is meaningful when the sampler error is sufficiently small relative to the horizon or decreases as the sampler improves. For a fixed $\varepsilon>0$, the error accumulates over time, and these bounds do not guarantee sublinear regret. In particular, preserving the original rate requires approximately $\varepsilon=\widetilde O(T^{-1/2})$.