PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sanghwa Kim, Kyoungseok Jang, Se-Young Yun

arXiv:2610.12919v1stat.MLcs.LG

TL;DR

The paper studies online binary prediction when obtaining more precise feature measurements costs resources, so learners must balance prediction loss and acquisition cost. It develops methods for paid noisy features under an additive degradation ordering and shows that covariance alone does not determine logistic loss. The known- and unknown-profile settings have regret guarantees with matching lower bounds up to logarithmic factors.

  • Problem

    Online prediction with paid noisy features requires learning the trade-off between population prediction quality and acquisition cost.

    Source: §1 · pp. 1–2

  • Method

    The paper uses an ordered additive degradation structure to share information across payment levels when degradation distributions are known, and learns payment levels separately when they are unknown.

    Source: §5 · pp. 9–10

  • Results

    The unknown-profile algorithm achieves eO(T^2/3) regret with a matching lower bound up to logarithmic factors, and the paper reports matching horizon-dependent bounds for both profile settings.

    Source: §5 · p. 10

  • Takeaways & Limitations

    Covariance alone does not characterize logistic loss, while additive degradation provides an ordering that supports learning across payment levels.

    Source: §1 · p. 2, §5 · pp. 9–10

    The results rely on ordered additive degradation, a condition generally stronger than covariance ordering.

    Source: §5 · p. 10

Abstract

from arXiv · show

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 $\widetilde O(\sqrt{T})$ regret when the noise structure is known and $\widetilde O(T^{2/3})$ regret when it is unknown, with matching lower bounds up to logarithmic factors.

1 INTRODUCTION

The paper studies online logistic prediction with paid noisy features, where learners must trade off prediction loss against acquisition cost. It shows that covariance alone cannot characterize logistic loss and gives algorithms for known and unknown noise profiles with regret guarantees.

1 INTRODUCTION

  • The learner chooses a payment and prediction rule before observing a noisy feature, then minimizes cumulative logistic loss plus a payment penalty relative to the optimal population trade-off.The motivating examples include medical testing and online purchase prediction, where more reliable information costs more.Source: §1 · pp. 1–2
  • Covariance alone cannot characterize logistic prediction under noisy features: equal-variance noise can yield different optimized losses, and lower variance can yield higher loss.The introduction contrasts this with paid linear regression under squared loss.Source: §1 · p. 2
  • With a known degradation-increment distribution, higher-payment observations can be transformed into valid lower-payment observations, enabling one-sided simulation-based elimination.The paper pairs this method with a minimax lower bound and describes the horizon dependence as optimal up to logarithmic factors.Source: §1 · p. 2
  • With an unknown noise profile, observations generally cannot be reused across payment levels, so an asynchronous grid lower confidence bound algorithm learns the prediction-payment trade-off.The algorithm achieves eO(T^2/3) regret, matched up to logarithmic factors by a lower bound even for one-dimensional Gaussian noise with decreasing variance.Source: §1 · p. 2

2 PROBLEM SETTING

The learner observes noisy features selected by a payment made before the feature arrives, and evaluates predictions with logistic loss plus payment cost. Because covariance does not order logistic loss, the paper assumes additive degradation across payments to recover a useful ordering.

2 PROBLEM SETTING

  • At each round, the learner selects a payment and linear predictor before observing a corrupted feature, predicts a binary response, and then observes its outcome.The latent feature is drawn independently across rounds, and the response follows a logistic model.Source: §2 · p. 3
  • The clean-feature parameter need not be the best logistic-linear predictor from a noisy feature, because conditioning on that feature can produce a probability not representable by the same model.The conditional probability is the expectation of the clean-feature logistic probability given the noisy feature.Source: §2 · p. 3
  • The objective is cumulative population loss relative to the best fixed payment and predictor, with logistic prediction loss combined with a payment penalty.The stated regularity conditions include sub-Gaussian features and measurement noise with known bounds.Source: §2 · p. 3

2.1 BEYOND COVARIANCE: STRUCTURE OF NOISE PROFILE

  • Unlike squared loss, logistic loss can differ across noise distributions with equal variance, and variance ordering can oppose optimized-loss ordering.The paper's proposition gives one-dimensional examples of both phenomena.Source: §2.1 · p. 4
  • Ordered additive degradation assumes lower-payment noise is obtained by adding independent mean-zero noise to higher-payment noise, making prediction loss nonincreasing with payment.Convexity and Jensen's inequality yield one-sided Lipschitzness of population loss after the payment penalty is included.Source: §2.1 · p. 4
  • The known-profile regime gives the learner degradation-increment distributions and an exact sampler, whereas the unknown-profile regime assumes the ordering but withholds those distributions.Without the increment distributions, observations at one payment level cannot generally be reused at another.Source: §2.1 · p. 4

3 ONLINE LOGISTIC REGRESSION WITH KNOWN NOISE PROFILE

With a known degradation-increment distribution, higher-payment observations can be simulated at lower payment levels, enabling shared learning across the payment grid. The resulting algorithm has order-optimal regret in T.

3.1 UNIFORM CONCENTRATION AT A FIXED PAYMENT

  • At a fixed payment, uniform concentration controls empirical logistic loss over all predictors, including data-dependent choices.The concentration result assumes the feature and noise regularity conditions in Assumption 1.Source: §3.1 · p. 5

3.2 VALIDITY OF SIMULATED LOWER-PAYMENT OBSERVATIONS

  • A higher-payment observation can be degraded with an independent increment to yield a valid lower-payment sample, even when payments are chosen adaptively.These simulated observations support concentration at each target payment.Source: §3.2 · pp. 5–6

3.3 ONE-SIDED SIMULATION-BASED GRID ELIMINATION ALGORITHM

  • The algorithm pays at the largest active grid point and reuses each observation to update every active lower payment, eliminating payments as evidence accumulates.Batches end at doubling sample-count checkpoints or at the horizon.Source: §3.3 · pp. 6–7
  • Increasing the grid size reduces discretization error without a polynomial increase in statistical error, because active payments share observations.The simulated streams may be dependent across payments; the analysis applies concentration separately and combines events with a union bound.Source: §3.3 · p. 7
  • eO(sqrt(dT)) regret is achieved with a known noise profile, and an Ω(sqrt(T)) lower bound makes the horizon dependence optimal up to logarithmic factors.The lower bound applies to one-dimensional instances.Source: §3.3 · p. 7

4 EXTENSION TO UNKNOWN NOISE PROFILE

When the noise profile is unknown, observations cannot be converted across payment levels, so each grid payment must be learned from its own samples. An asynchronous lower-confidence-bound algorithm achieves the matching order-optimal horizon dependence.

4 EXTENSION TO UNKNOWN NOISE PROFILE

  • Without an increment sampler, observations from one payment cannot be reused at another, so each grid payment requires its own data stream.The unknown-profile setting still assumes ordered additive degradation, but its increment distribution is unavailable to the learner.Source: §4 · p. 8, §4.1 · p. 8

4.1 ASYNCHRONOUS GRID LOWER CONFIDENCE BOUND ALGORITHM

  • The algorithm initializes every grid payment, then selects optimistically by lower confidence bound and updates each payment at its own power-of-two sample checkpoints.Sample counts and checkpoints therefore progress asynchronously across payments.Source: §4.1 · p. 8
  • The grid creates a trade-off: increasing its size reduces approximation error but raises statistical error and leaves a λ^(1/3) factor in the regret bound.The statistical error scales with the number of separately learned payments.Source: §4.1 · pp. 8–9
  • eO(d^(1/3)T^(2/3)) regret is achieved without knowing the noise profile, and an Ω(T^(2/3)) lower bound makes the horizon dependence optimal up to logarithmic factors.The lower bound holds even for one-dimensional instances with an unknown noise profile.Source: §4.1 · pp. 8–9

5 CONCLUSION

The paper concludes that logistic prediction with paid noisy features requires more than covariance information, and obtains order-optimal regret under ordered additive degradation. It distinguishes this prediction objective from work centered on latent-covariate inference or other acquisition settings.

5 CONCLUSION

  • Equal noise covariance can produce different optimized logistic losses, and covariance ordering need not preserve loss ordering.The conclusion contrasts this with paid linear regression under squared loss.Source: §5 · p. 9, A RELATED WORK · p. 15
  • With known profiles, simulation-based elimination achieves eO(dT) regret; with unknown profiles, learning each payment level separately gives eO(T 2/3), with matching lower bounds optimal in horizon dependence up to logarithmic factors.The results rely on ordered additive degradation, generally stronger than covariance ordering.Source: §5 · p. 10

A RELATED WORK

  • Unlike nonlinear errors-in-variables work that targets inference on latent clean covariates, this paper predicts from corrupted features whose quality is controlled by payment.The optimal logistic-linear predictor need not equal the parameter generating responses from clean features.Source: A RELATED WORK · p. 15
  • Paid stochastic-expert work studies reliability of binary expert predictions, whereas this setting measures continuous noisy feature vectors for logistic-linear prediction.Van Der Hoeven et al. (2023) is identified as a particularly relevant starting point for the cost–information trade-off.Source: A RELATED WORK · p. 15
  • The closest predecessor studies paid stochastic features under squared loss; logistic loss changes how noise affects prediction, despite the same optimal horizon dependence.Merlis et al. (2026) established optimal horizon dependences for known and unknown profiles in the linear setting.Source: A RELATED WORK · p. 15
  • Costly feature-acquisition work commonly chooses coordinates or tests, while this paper chooses measurement accuracy for a common latent feature vector and gives an online regret guarantee.The comparison concerns the objective relative to an optimal fixed payment–predictor pair.Source: A RELATED WORK · p. 16
  • Prior online logistic-regression and bandit work assumes covariates arrive at fixed quality; this paper adds an online decision about how much to pay for their quality.The setting abstracts away strategic reporting and mechanism-design constraints in privacy-sensitive acquisition models.Source: A RELATED WORK · pp. 15–16

B PROOF OF EQ. (1)

The proof step uses the timing of the learner’s choices and the tower property.

B PROOF OF EQ. (1)

  • The payment and predictor are chosen before the current noisy feature and outcome are observed.This is the stated timing condition for the proof step.Source: B PROOF OF EQ. (1) · p. 16
  • The proof’s transition is grounded in pre-observation choices followed by the tower-property step.Both conditions appear in the supplied proof fragments.Source: B PROOF OF EQ. (1) · p. 16
  • The argument invokes the tower property to pass between conditional and unconditional expectations.The passage states this as the justification for the transition.Source: B PROOF OF EQ. (1) · p. 16

C PROOF OF PROPOSITION 1

The proof constructs mean-zero noise examples showing that variance alone does not determine optimized logistic loss. Even lower variance need not imply lower logistic loss.

C PROOF OF PROPOSITION 1

D PROOF OF PROPOSITION 2

The proof applies Assumption 2 and Eq. (2) across payment levels, then uses the minimizing parameters at each level to derive its final comparison.

D PROOF OF PROPOSITION 2

E PROOF OF PROPOSITION 3

The proof of Proposition 3 combines a Lipschitz loss transformation, empirical-process bounds, and sub-Gaussian concentration. Supporting lemmas provide the contraction and vector concentration steps.

E PROOF OF PROPOSITION 3

E.1 SUPPORTING LEMMAS

F PROOF OF PROPOSITION 4

The proof simulates observations for a target payment and completes the sequence with virtual observations. This makes the completed sequence i.i.d. with the target-payment distribution, allowing Proposition 3 to be applied.

F PROOF OF PROPOSITION 4

G PROOF OF THEOREM 5

The proof controls regret by tracking payment-specific loss estimates at doubling checkpoints and eliminating payments whose estimated loss is too high. It then combines the surviving payments’ loss bounds with a grid approximation to the continuous payment range.

G PROOF OF THEOREM 5

  • The proof checks concentration failures over payment indices and doubling checkpoints, bounding the probability of any failure by a union bound.It defines checkpoints as sample counts 1, 2, 4, 8, and so on.Source: G PROOF OF THEOREM 5 · pp. 23, 25
  • At each checkpoint, the optimal grid payment remains active, while every surviving payment has population loss within 4γ_n of the best grid payment.The proof uses concentration bounds to keep empirical and population losses close for active payments.Source: G PROOF OF THEOREM 5 · pp. 23–24
  • The algorithm uses the largest surviving payment in the next batch, whose regret is bounded using that payment’s loss estimate.Batches after checkpoint n contain at most n rounds.Source: G PROOF OF THEOREM 5 · p. 24
  • A grid payment approximates any continuous payment, allowing the best grid loss to be compared with the optimum over [0, 1].The proof selects the grid point c(k) = ⌈Kc⌉/K for a given payment c.Source: G PROOF OF THEOREM 5 · p. 25
  • On the failure event, the proof separately bounds per-round regret using the feature and noise regularity assumptions.The final regret decomposition separates the good and bad events.Source: G PROOF OF THEOREM 5 · pp. 25–26

H PROOF OF THEOREM 10

Theorem 10’s proof uses payment-specific samples and local doubling checkpoints to control regret when the noise profile is unknown. The lower-bound section supplies Gaussian constructions, with scalar-loss regularity supporting both constructions.

H PROOF OF THEOREM 10

  • The proof partitions rounds by payment and local checkpoint, where each estimate is reused for at most its checkpoint count before the count doubles.Observations gathered at a fixed payment are i.i.d. from that payment’s distribution, even when the payment choices are adaptive.Source: H PROOF OF THEOREM 10 · pp. 27–29

I PROOF OF LOWER BOUNDS

  • The lower-bound constructions use one-dimensional Gaussian models to capture the statistical difficulty in both known- and unknown-profile settings.The section proves the known-profile lower bound before the unknown-profile lower bound.Source: I PROOF OF LOWER BOUNDS · p. 30

I.1 REGULARITY OF THE SCALAR GAUSSIAN LOGISTIC LOSS

  • The scalar Gaussian logistic loss has a unique constrained minimizer and is regular in its feature-variance and noise-variance arguments.The proof uses strict increase in noise variance and a uniformly Lipschitz inverse on a compact variance interval.Source: §I.1 · pp. 30–31

I.2 PROOF OF THEOREM 8: KNOWN PROFILE

The known-profile construction makes two nearby clean-feature variances favor opposite payment regions, while the unknown-profile construction hides a local improvement within an unknown payment interval. Both arguments establish hardness even under stronger feedback that reveals clean features after each round.

I.2 PROOF OF THEOREM 8: KNOWN PROFILE

  • In the known-profile construction, perturbing the clean-feature variance to opposite sides of a tie makes opposite payment regions optimal, with an order-ε loss gap for choosing the wrong region.The learner still faces this distinction when the clean feature is revealed after each round.Source: §I.2 · pp. 32–33
  • The known-profile lower bound comes from distinguishing nearby instances with different optimal payment regions, not from estimating the logistic parameter or recovering the clean feature.The measurement profile and other fixed model parameters may be known to the learner.Source: §I.2 · p. 34

I.3 PROOF OF THEOREM 12: UNKNOWN PROFILE

  • An unknown decreasing Lipschitz Gaussian profile can hide an improved payment region, yielding an Ω(T^2/3) regret lower bound.The construction inserts a depth δ_K ≍ 1/K improvement in one of K disjoint regions; choosing K ≍ T^1/3 keeps the alternatives hard to distinguish.Source: §I.3 · pp. 34, 37
  • For the unknown-profile lower bound, each alternative differs from a flat baseline only in its hidden region, so observations outside that region do not identify the improvement.The constructed Gaussian profiles satisfy the ordered additive degradation assumption.Source: §I.3 · pp. 34–36
Loading 2610.12919v1…