acceptodds
Under review as a conference paper at ICLR 2027

Beyond Second-Order Information: Paid Logistic Regression with Noisy Features

Abstract

We consider online binary prediction with paid stochastic features, where the learner can spend resources to obtain better observations of the underlying features. This setting is motivated by applications such as medical testing, where additional cost can provide more precise measurements of patient's features for predicting a binary outcome. At each round, a latent feature is drawn i.i.d., the response is generated through a logistic model, and the learner chooses how much to pay before observing a noisy version of the feature. The goal of learner is to jointly control prediction loss and acquisition cost. In contrast to the former result on the online linear regression with paid features, covariance information alone is no longer sufficient: two noise distributions with the same covariance may induce different optimal logistic losses, and lower variance can even lead to higher loss. Under a structural ordering in which larger payments yield better observations by removing independent noise, we obtain regret when the noise structure is known and regret when it is unknown, with matching lower bounds up to logarithmic factors.

Primary area:
learning theory
Keywords:
Online learning, online regression, logistic regression, learning theory

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_NNWPOpenReview ↗
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

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)X \sim \mathcal{N} (1, \sigma^2), and show that the conclusions of Proposition 1 continue to hold for sufficiently small σ>0\sigma>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,c2G_{c_1,c_2} for c1≤c2c_1 \leq c_2, provided that a sample X~(c1)∼Gc1,c2(X^(c2),⋅)\widetilde X(c_1)\sim G_{c_1,c_2}\bigl(\widehat X(c_2),\cdot\bigr) 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})$.

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 TT, up to logarithmic factors, but do not establish tight dependence on dd. 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 TT.

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 T=5000T=5000, 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, L⋆(c)−λcL^\star(c) - \lambda c in cc. Assumption 2 is a sufficient condition for this monotonicity. In particular, for c1≤c2c_1\leq c_2,

\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.

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

This paper studies online logistic regression with costly, noisy features, where the learner chooses a payment level that determines the feature noise. It presents a natural extension of the work by Merlis et al. (2026), which studied linear regression with squared loss. The new tool is Rademacher concentration, which gives Propositions 3 and 4. These propositions are then used to define confidence intervals in the grid search algorithm and to derive its regret guarantees. Under a known noise-degradation profile, the proposed algorithm exploits the ability to synthesize observations at lower payment levels from observations acquired at higher payment levels. Similar to Merlis et al., this enables a regret bound of order (\widetilde O(\sqrt{T})). When the degradation profile is unknown, the paper obtains a regret bound of order (\widetilde O(T^{2/3})).

Critical strengths

The paper is clearly written, and I found the problem formulation and algorithmic idea appealing. The novelty compared to Merlis et al is sufficient in my opinion, although the fact that second-order statistics of the noise is insufficient beyond squared loss is unsurprising.

Critical weaknesses

None identified

Questions for authors

The known-profile algorithm relies on an additive degradation condition that enables exact simulation of lower-payment measurements from higher-payment observations. Would the algorithm extend from additive degradation to more general stochastic degradation?

1 comment

We thank the reviewer for the positive assessment and question.

General Degradation: We believe that the known-profile result extends beyond additive degradation, although not to every stochastic degradation without additional conditions. Consider a family of known kernels Gc1,c2G_{c_1,c_2} for c1≤c2c_1\leq c_2. Given an observation X^(c2)\widehat X(c_2), suppose that the learner knows a Markov kernel Gc1,c2G_{c_1,c_2} and samples X~(c1)∼Gc1,c2(X^(c2),⋅),\widetilde X(c_1)\sim G_{c_1,c_2}\bigl(\widehat X(c_2),\cdot\bigr), where X~(c1)\widetilde X(c_1) is independent of the response conditionally on X^(c2)\widehat X (c_2) and payments, and satisfies

\overset{d}{=} \bigl(\widehat X(c_1),Y\bigr).$$ If the resulting simulated features satisfy the same sub-Gaussian condition as the original observations, the learner can replace the additive simulation step in Algorithm 1 with a draw from $G_{c_1,c_2}$. An observation collected at the largest active payment then provides a valid simulated observation for every lower active payment. Consequently, the concentration and elimination arguments remain unchanged. We additionally need the optimized loss to satisfy $$L^\star(c_2) \leq L^\star(c_1)+\lambda(c_2-c_1).$$ One sufficient condition is that the garbling kernel is mean preserving: $$\int x'\,G_{c_1,c_2}(x,dx')=x \qquad\text{for every }x.$$ With this, conditional Jensen’s inequality then gives, for every predictor $\nu$, $$\mathbb E\!\left[ \ell\bigl(Y,\widetilde X(c_1)^\top\nu\bigr) \mid \widehat X(c_2),Y \right] \geq \ell\bigl(Y,\widehat X(c_2)^\top\nu\bigr),$$ which implies the required loss ordering. Under these conditions, the proof of Algorithm 1 yields the same $\widetilde O(\sqrt{dT})$ regret rate. Assumption 2 is a special case of this kernel: it maps $x$ to $x+\xi_{c_1,c_2}$, where the increment is independent and mean zero. We again thank the reviewer for the careful reading, positive assessment, and thoughtful question. The feedback helped us clarify the scope and possible extensions of our results, and we welcome any further questions or comments.
Reviewer_fgTuOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studies the problem of online logistic regression with noise features. The learner observes sequentially covariates plus added noise and has the option to tune the noise level at a corresponding cost. The authors extend previous work on online linear regression under the same covariate mechanism. They show that in the logistic model, the covariance matrix is not the object of interest and they propose an alternative noise model (assumption 2), that is well motivated. Then they provide two algorithms, for the known and unknown noise structure, with tight regret guarantees and the corresponding lower bounds.

Critical strengths
  1. The authors find an appropriate noise model and extend the previous work in online linear regression with noisy features to the logistic case.

  2. They provide lower bounds that match the regret of their algorithms in both the known and unknown noise regime.

  3. The presentation and the writting of the paper is very good.

Critical weaknesses
  1. While the model is interesting and intuitive from a theoretical perspective does not seem applicable in real world scenarios.

  2. This work would benefit from adding some experimental validation, even with synthetic data.

Questions for authors
  1. Is the knowledge of the horizon T necessary?

  2. Could you provide an example of a realistic application or some known dataset where this model applies?

2 comments

We thank the reviewer for the constructive feedback and questions. We address the concerns and questions below.

Applicability (W1, Q2). We believe that our setting captures an important aspect of real-world prediction problems that is often overlooked in standard machine learning models: features may be observed with noise, and improving their quality may require additional resources. Although measurement error has been studied in the errors-in-variables literature (Appendix A), the sequential trade-off between feature quality and acquisition cost has received comparatively less attention (Merlis et al., 2026).

A primary application is medical prediction, where patient features are often obtained through noisy measurements or tests. Repeated measurements or more expensive tests can provide more reliable patient information for predicting disease status or health outcomes. For example, if repeated measurements have independent, unbiased Gaussian errors, averaging these repeated measurements reduces measurement variance. Thus, the number of measurements determines the acquisition cost, and the resulting noise family satisfies our ordered additive-degradation assumption.

Another application is customer profiling and preference learning, where monetary incentives can encourage individuals to disclose more accurate or detailed information. Such settings involve a trade-off between the cost of acquiring information and its informativeness for predicting customer behavior or preferences.

We acknowledge that our assumptions idealize these applications. In practice, measurement errors may be biased, dependent, or heterogeneous across individuals, and the exact noise distributions may be unknown. Nevertheless, assuming approximately Gaussian measurement errors with negligible bias can provide practical models for many real-world scenarios, while noise profiles may be estimated through calibration when such information is available.

An important direction for future work is to integrate feature acquisition with decision-making. For example, a contextual-bandit extension would jointly choose the feature quality and the action, optimizing the resulting reward including acquisition cost.

Experiments (W2): We agree that experimental validation would strengthen the paper. We added synthetic experiments in Appendix L, comparing the proposed algorithms (Algorithms 1 and 2) with explore-then-commit (ETC), fixed-payment policies, and an oracle-payment reference. The experiments use Gaussian features and a Gaussian noise family, which satisfies ordered additive degradation, and report cumulative population regret over 20 independent runs for four values of λ\lambda. Algorithm 1 has lower mean regret than Algorithm 2 at every tested cost, illustrating the value of reusing a high-payment observation to simulate observations at all lower active payments. It also has lower mean regret than ETC at three costs and similar regret at the fourth.

Knowledge of TT (Q1): Prior knowledge of TT is not necessary. The standard doubling trick divides time into epochs of lengths Tj=2jT_j=2^j and restarts the algorithm at each epoch. The grid sizes are chosen according to the corresponding theorems (Theorems 5 and 10) with TT replaced by TjT_j: Kj≍TjK_j\asymp\sqrt{T_j} in the known-profile setting and Kj≍Tj1/3K_j\asymp T_j^{1/3} in the unknown-profile setting, ignoring instance-dependent and logarithmic factors. Setting the epoch-level confidence parameter to δj=Tj−2\delta_j=T_j^{-2}, the geometric sums of the epoch-wise regret bounds give

=\widetilde O(\sqrt{dT})$$ for the known-profile setting and $$\sum_{j=1}^{J}\widetilde O(d^{1/3}T_j^{2/3}) =\widetilde O(d^{1/3}T^{2/3})$$ for the unknown-profile setting. Thus, the same expected regret rates are preserved without prior knowledge of $T$. This argument is added in Appendix J of revision. We again thank the reviewer for the careful reading, constructive feedback, and positive assessment. The comments helped us improve the practical motivation and empirical presentation of the paper, and we would be happy to address any further questions.

I thank the authors for adding experimental evaluations in the appendix. All my questions have been answered; I will maintain my positive score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.