Princewill Okoroafor

STOC Conference 2025 Conference Paper

Breaking the T^(2/3) Barrier for Sequential Calibration

• Yuval Dagan
• Constantinos Daskalakis
• Maxwell Fishelson
• Noah Golowich
• Robert Kleinberg
• Princewill Okoroafor

NeurIPS Conference 2025 Conference Paper

Contextual Dynamic Pricing with Heterogeneous Buyers

• Thodoris Lykouris
• Sloan Nietert
• Princewill Okoroafor
• Chara Podimata
• Julian Zimmert

We initiate the study of contextual dynamic pricing with a heterogeneous population of buyers, where a seller repeatedly posts prices (over $T$ rounds) that depend on the observable $d$-dimensional context and receives binary purchase feedback. Unlike prior work assuming homogeneous buyer types, in our setting the buyer's valuation type is drawn from an unknown distribution with finite support size $K_{\star}$. We develop a contextual pricing algorithm based on optimistic posterior sampling with regret $\widetilde{O}(K_{\star}\sqrt{dT})$, which we prove to be tight in $d$ and $T$ up to logarithmic terms. Finally, we refine our analysis for the non-contextual pricing case, proposing a variance-aware zooming algorithm that achieves the optimal dependence on $K_{\star}$.

FOCS Conference 2025 Conference Paper

Near-Optimal Algorithms for Omniprediction

• Princewill Okoroafor
• Robert Kleinberg
• Michael P. Kim

Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class ℋ, simultaneously for every loss function within a class of losses ℒ. In this work, we give near-optimal learning algorithms for omniprediction, in both the online and offline settings. To begin, we give an oracle-efficient online learning algorithm that achieves (ℒ, ℋ)-omniprediction with $\tilde O\left( {\sqrt {T\log |\mathcal{H}|} } \right)$ regret for any class of Lipschitz loss functions ℒ ⊆ ℒ Lip. Quite surprisingly, this regret bound matches the optimal regret for minimization of a single loss function (up to a $\sqrt {\log (T)} $ factor). Given this online algorithm, we develop an online-to-offline conversion that achieves near-optimal complexity across a number of measures. In particular, for all bounded loss functions within the class of Bounded Variation losses ℒ BV (which include all convex, all Lipschitz, and all proper losses) and any (possibly-infinite) ℋ, we obtain an offline learning algorithm that, leveraging an (offline) ERM oracle and m samples from $\mathcal{D}$, returns an efficient (ℒ BV, ℋ, ε(m))-omnipredictor for ε(m) scaling near-linearly in the Rademacher complexity of Th◦ℋ, the class of all binary threshold functions on ℋ.

SODA Conference 2023 Conference Paper

Non-Stochastic CDF Estimation Using Threshold Queries

• Princewill Okoroafor
• Vaishnavi Gupta
• Robert Kleinberg

Estimating the empirical distribution of a scalar-valued data set is a basic and fundamental task. In this paper, we tackle the problem of estimating an empirical distribution in a setting with two challenging features. First, the algorithm does not directly observe the data; instead, it only asks a limited number of threshold queries about each sample. Second, the data are not assumed to be independent and identically distributed; instead, we allow for an arbitrary process generating the samples, including an adaptive adversary. These considerations are relevant, for example, when modeling a seller experimenting with posted prices to estimate the distribution of consumers' willingness to pay for a product: offering a price and observing a consumer's purchase decision is equivalent to asking a single threshold query about their value, and the distribution of consumers' values may be non-stationary over time, as early adopters may differ markedly from late adopters. Our main result quantifies, to within a constant factor, the sample complexity of estimating the empirical CDF of a sequence of elements of [ n ], up to ε additive error, using one threshold query per sample. The complexity depends only logarithmically on n, and our result can be interpreted as extending the existing logarithmic-complexity results for noisy binary search to the more challenging setting where noise is non-stochastic. Along the way to designing our algorithm, we consider a more general model in which the algorithm is allowed to make a limited number of simultaneous threshold queries on each sample. We solve this problem using Blackwell's Approachability Theorem and the exponential weights method. As a side result of independent interest, we characterize the minimum number of simultaneous threshold queries required by deterministic CDF estimation algorithms.