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

arXiv: https://arxiv.org/abs/2610.12919 · HTML: https://mlsanity.com/paper/2610.12919/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 54 references that are in the map.
- First posted on arXiv 9 Oct 2026.

## Builds on (most cited first, 20 of 20)

- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2010.12642/) (2020)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Logistic Regression: The Importance of Being Improper](https://mlsanity.com/paper/1803.09349/) (2018)
- [Differential Privacy: An Economic Method for Choosing Epsilon](https://mlsanity.com/paper/1402.3329/) (2014)
- [Classification with Costly Features using Deep Reinforcement Learning](https://mlsanity.com/paper/1711.07364/) (2017)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [On Robustness of Principal Component Regression](https://mlsanity.com/paper/1902.10920/) (2019)
- [Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms](https://mlsanity.com/paper/2201.03968/) (2022)
- [Logistic Regression Regret: What's the Catch?](https://mlsanity.com/paper/2002.02950/) (2020)
- [Redrawing the Boundaries on Purchasing Data from Privacy-Sensitive Individuals](https://mlsanity.com/paper/1401.4092/) (2014)
- [Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles](https://mlsanity.com/paper/1703.01347/) (2017)
- [Polynomial Time and Sample Complexity for Non-Gaussian Component Analysis: Spectral Methods](https://mlsanity.com/paper/1704.01041/) (2017)
- [Adaptive Principal Component Regression with Applications to Panel Data](https://mlsanity.com/paper/2307.01357/) (2023)
- [High-dimensional logistic regression with missing data: Imputation, regularization, and universality](https://mlsanity.com/paper/2410.01093/) (2024)
- [Covariate Selection in High-Dimensional Generalized Linear Models With Measurement Error](https://mlsanity.com/paper/1407.1070/) (2014)
- [The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms and Fundamental Limits](https://mlsanity.com/paper/1603.06870/) (2016)
- [Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts](https://mlsanity.com/paper/2307.00836/) (2023)
- [Online Linear Regression with Paid Stochastic Features](https://mlsanity.com/paper/2511.08073/) (2025)

## Abstract (arXiv)

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(√T) regret when the noise structure is known and widetilde O(T2/3) regret when it is unknown, with matching lower bounds up to logarithmic factors.