publications
Below is a list of my journal and conference publications and preprints in reverse chronological order. You can also check out my Google Scholar profile.
2023
- High-Dimensional Prediction for Sequential Decision MakingGeorgy Noarov, Ramya Ramalingam, Aaron Roth, and Stephan XieManuscript; Oral presentation at 15th International OPT Workshop on Optimization for ML 2023
We study the problem of making predictions of an adversarially chosen high-dimensional state that are unbiased subject to an arbitrary collection of conditioning events, with the goal of tailoring these events to downstream decision makers. We give efficient algorithms for solving this problem, as well as a number of applications that stem from choosing an appropriate set of conditioning events. For example, we can efficiently make predictions targeted at polynomially many decision makers, giving each of them optimal swap regret if they best-respond to our predictions. We generalize this to online combinatorial optimization, where the decision makers have a very large action space, to give the first algorithms offering polynomially many decision makers no regret on polynomially many subsequences that may depend on their actions and the context. We apply these results to get efficient no-subsequence-regret algorithms in extensive-form games (EFGs), yielding a new family of regret guarantees for EFGs that generalizes some existing EFG regret notions, e.g. regret to informed causal deviations, and is generally incomparable to other known such notions. Next, we develop a novel transparent alternative to conformal prediction for building valid online adversarial multiclass prediction sets. We produce class scores that downstream algorithms can use for producing valid-coverage prediction sets, as if these scores were the true conditional class probabilities. We show this implies strong conditional validity guarantees including set-size-conditional and multigroup-fair coverage for polynomially many downstream prediction sets. Moreover, our class scores can be guaranteed to have improved L2 loss, cross-entropy loss, and generally any Bregman loss, compared to any collection of benchmark models, yielding a high-dimensional real-valued version of omniprediction.
@article{noarov2023high, bibtex_show = {true}, title = {High-Dimensional Prediction for Sequential Decision Making}, author = {Noarov, Georgy and Ramalingam, Ramya and Roth, Aaron and Xie, Stephan}, arxiv = {2310.17651}, journal = {Manuscript; Oral presentation at 15th International OPT Workshop on Optimization for ML}, year = {2023} } - The Scope of Multicalibration: Characterizing Multicalibration via Property ElicitationGeorgy Noarov, and Aaron Roth40th International Conference on Machine Learning (ICML) 2023
We make a connection between multicalibration and property elicitation and show that (under mild technical conditions) it is possible to produce a multicalibrated predictor for a continuous scalar distributional property Γ if and only if Γ is elicitable. On the negative side, we show that for non-elicitable continuous properties there exist simple data distributions on which even the true distributional predictor is not calibrated. On the positive side, for elicitable Γ, we give simple canonical algorithms for the batch and the online adversarial setting, that learn a Γ-multicalibrated predictor. This generalizes past work on multicalibrated means and quantiles, and in fact strengthens existing online quantile multicalibration results. To further counter-weigh our negative result, we show that if a property Γ1 is not elicitable by itself, but is elicitable conditionally on another elicitable property Γ0, then there is a canonical algorithm that jointly multicalibrates Γ1 and Γ0; this generalizes past work on mean-moment multicalibration. Finally, as applications of our theory, we provide novel algorithmic and impossibility results for fair (multicalibrated) risk assessment.
@article{Noarov2023ScopeMC, bibtex_show = {true}, title = {The Scope of Multicalibration: Characterizing Multicalibration via Property Elicitation}, author = {Noarov, Georgy and Roth, Aaron}, arxiv = {2302.08507}, journal = {40th International Conference on Machine Learning (ICML)}, year = {2023} } - Batch Multivalid Conformal PredictionChristopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth11th International Conference on Learning Representations (ICLR) 2023
We develop fast distribution-free conformal prediction algorithms for obtaining multivalid coverage on exchangeable data in the batch setting. Multivalid coverage guarantees are stronger than marginal coverage guarantees in two ways: (1) They hold even conditional on group membership -- that is, the target coverage level \(1-\alpha\) holds conditionally on membership in each of an arbitrary (potentially intersecting) group in a finite collection \(G\) of regions in the feature space. (2) They hold even conditional on the value of the threshold used to produce the prediction set on a given example. In fact multivalid coverage guarantees hold even when conditioning on group membership and threshold value simultaneously. We give two algorithms: both take as input an arbitrary non-conformity score and an arbitrary collection of possibly intersecting groups \(G\), and then can equip arbitrary black-box predictors with prediction sets. Our first algorithm (BatchGCP) is a direct extension of quantile regression, needs to solve only a single convex minimization problem, and produces an estimator which has group-conditional guarantees for each group in \(G\). Our second algorithm (BatchMVP) is iterative, and gives the full guarantees of multivalid conformal prediction: prediction sets that are valid conditionally both on group membership and non-conformity threshold. We evaluate the performance of both of our algorithms in an extensive set of experiments.
@article{Jung2022BatchMC, bibtex_show = {true}, title = {Batch Multivalid Conformal Prediction}, author = {Jung, Christopher and Noarov, Georgy and Ramalingam, Ramya and Roth, Aaron}, arxiv = {2209.15145}, journal = {11th International Conference on Learning Representations (ICLR)}, year = {2023}, code = {https://github.com/ProgBelarus/BatchMultivalidConformal}, preview = {conformal.png} }
2022
- Practical Adversarial Multivalid Conformal PredictionOsbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth36th Conference on Neural Information Processing Systems (NeurIPS) 2022Selected as an Oral Presentation
We give a simple, generic conformal prediction method for sequential prediction that achieves target empirical coverage guarantees against adversarially chosen data. It is computationally lightweight -- comparable to split conformal prediction -- but does not require having a held-out validation set, and so all data can be used for training models from which to derive a conformal score. It gives stronger than marginal coverage guarantees in two ways. First, it gives threshold calibrated prediction sets that have correct empirical coverage even conditional on the threshold used to form the prediction set from the conformal score. Second, the user can specify an arbitrary collection of subsets of the feature space -- possibly intersecting -- and the coverage guarantees also hold conditional on membership in each of these subsets. We call our algorithm MVP, short for MultiValid Prediction. We give both theory and an extensive set of empirical evaluations.
@article{Bastani2022PracticalAM, selected = {true}, bibtex_show = {true}, title = {Practical Adversarial Multivalid Conformal Prediction}, author = {Bastani, Osbert and Gupta, Varun and Jung, Christopher and Noarov, Georgy and Ramalingam, Ramya and Roth, Aaron}, video = {https://slideslive.com/38991952}, arxiv = {2206.01067}, journal = {36th Conference on Neural Information Processing Systems (NeurIPS)}, year = {2022}, code = {https://github.com/ProgBelarus/MultiValidPrediction}, preview = {conformal.png}, slides = {MVP_Slides_Conf.pdf}, prize = {Selected as an Oral Presentation} } - Online Minimax Multiobjective Optimization: Multicalibeating and Other ApplicationsDaniel Lee, Georgy Noarov, Mallesh M. Pai, and Aaron Roth36th Conference on Neural Information Processing Systems (NeurIPS) 2022Selected as an Oral Presentation
We introduce a simple but general online learning framework, in which at every round, an adaptive adversary introduces a new game, consisting of an action space for the learner, an action space for the adversary, and a vector valued objective function that is convex-concave in every coordinate. The learner and the adversary then play in this game. The learner's goal is to play so as to minimize the maximum coordinate of the cumulative vector-valued loss. The resulting one-shot game is not convex-concave, and so the minimax theorem does not apply. Nevertheless, we give a simple algorithm that can compete with the setting in which the adversary must announce their action first, with optimally diminishing regret. We demonstrate the power of our simple framework by using it to derive optimal bounds and algorithms across a variety of domains. This includes no regret learning: we can recover optimal algorithms and bounds for minimizing external regret, internal regret, adaptive regret, multigroup regret, subsequence regret, and a notion of regret in the sleeping experts setting. Next, we use it to derive a variant of Blackwell's Approachability Theorem, which we term "Fast Polytope Approachability". Finally, we are able to recover recently derived algorithms and bounds for online adversarial multicalibration and related notions (mean-conditioned moment multicalibration, and prediction interval multivalidity).
@article{Noarov2021OnlineMM, preview = {multiobjective.png}, selected = {true}, bibtex_show = {true}, video = {https://www.youtube.com/watch?v=ZiB5Y88SawA}, title = {Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications}, author = {Lee, Daniel and Noarov, Georgy and Pai, Mallesh M. and Roth, Aaron}, journal = {36th Conference on Neural Information Processing Systems (NeurIPS)}, year = {2022}, arxiv = {2108.03837}, prize = {Selected as an Oral Presentation} } - Online Multivalid Learning: Means, Moments, and Prediction IntervalsVarun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, and Aaron Roth13th Conference on Innovations in Theoretical Computer Science (ITCS) 2022
We present a general, efficient technique for providing contextual predictions that are "multivalid" in various senses, against an online sequence of adversarially chosen examples \( (x,y)\). This means that the resulting estimates correctly predict various statistics of the labels y not just marginally -- as averaged over the sequence of examples -- but also conditionally on \(x \in g\) for any \(g\) belonging to an arbitrary intersecting collection of groups \(G\). We provide three instantiations of this framework. The first is mean prediction, which corresponds to an online algorithm satisfying the notion of multicalibration from Hebert-Johnson et al. The second is variance and higher moment prediction, which corresponds to an online algorithm satisfying the notion of mean-conditioned moment multicalibration from Jung et al. Finally, we define a new notion of prediction interval multivalidity, and give an algorithm for finding prediction intervals which satisfy it. Because our algorithms handle adversarially chosen examples, they can equally well be used to predict statistics of the residuals of arbitrary point prediction methods, giving rise to very general techniques for quantifying the uncertainty of predictions of black box algorithms, even in an online adversarial setting. When instantiated for prediction intervals, this solves a similar problem as conformal prediction, but in an adversarial environment and with multivalidity guarantees stronger than simple marginal coverage guarantees.
@article{Gupta2022OnlineML, preview = {multiobjective.png}, selected = {true}, bibtex_show = {true}, title = {Online Multivalid Learning: Means, Moments, and Prediction Intervals}, author = {Gupta, Varun and Jung, Christopher and Noarov, Georgy and Pai, Mallesh M. and Roth, Aaron}, arxiv = {2101.01739}, video = {https://www.youtube.com/watch?v=ceCm3GCOVqU}, journal = {13th Conference on Innovations in Theoretical Computer Science (ITCS)}, year = {2022} } - Computing Approximate Equilibria in Weighted Congestion Games via Best-ResponsesYiannis Giannakopoulos, Georgy Noarov, and Andreas S. SchulzMathematics of Operations Research 2022
We present a deterministic polynomial-time algorithm for computing \( d^{d+o(d)} \)-approximate (pure) Nash equilibria in weighted congestion games with polynomial cost functions of degree at most \(d\). This is an exponential improvement of the approximation factor relative to the previously best deterministic algorithm. An appealing additional feature of the algorithm is that it only uses best-improvement steps in the actual game, as opposed to the previously best algorithms, that first had to transform the game itself. Our algorithm is an adaptation of the seminal algorithm by Caragiannis at al. [2011, 2015], but we utilize an approximate potential function directly on the original game instead of an exact one on a modified game. A critical component of our analysis, which is of independent interest, is the derivation of a novel bound of \( [d/W(d/\rho)]^{d+1} \) for the price of anarchy (PoA) of \( \rho \)-approximate equilibria in weighted congestion games, where \(W\) is the Lambert-W function. More specifically, we show that this PoA is exactly equal to \(\Phi_{d,\rho}^{d+1} \), where \( \Phi_{d,\rho} \) is the unique positive solution of the equation \( \rho (x+1)^d = x^{d+1} \). Our upper bound is derived via a smoothness-like argument, and thus holds even for mixed Nash and correlated equilibria, whereas our lower bound is simple enough to apply even to singleton congestion games.
@article{doi:10.1287/moor.2021.1144, preview = {congestion.jpg}, abbr = {Congestion Games}, show = {true}, author = {Giannakopoulos, Yiannis and Noarov, Georgy and Schulz, Andreas S.}, title = {Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses}, arxiv = {1810.12806}, journal = {Mathematics of Operations Research}, volume = {47}, number = {1}, pages = {643-664}, year = {2022}, doi = {10.1287/moor.2021.1144}, url = {https://doi.org/10.1287/moor.2021.1144}, eprint = {https://doi.org/10.1287/moor.2021.1144}, bibtex_show = {true}, html = {https://pubsonline.informs.org/doi/abs/10.1287/moor.2021.1144} }
2021
- Binary Scoring Rules that Incentivize PrecisionEric Neyman, Georgy Noarov, and S. Matthew Weinberg22nd ACM Conference on Economics and Computation (EC) 2021
All proper scoring rules incentivize an expert to predict accurately (report their true estimate), but not all proper scoring rules equally incentivize precision. Rather than treating the expert's belief as exogenously given, we consider a model where a rational expert can endogenously refine their belief by repeatedly paying a fixed cost, and is incentivized to do so by a proper scoring rule. Specifically, our expert aims to predict the probability that a biased coin flipped tomorrow will land heads, and can flip the coin any number of times today at a cost of c per flip. Our first main result defines an incentivization index for proper scoring rules, and proves that this index measures the expected error of the expert's estimate (where the number of flips today is chosen adaptively to maximize the predictor's expected payoff). Our second main result finds the unique scoring rule which optimizes the incentivization index over all proper scoring rules. We also consider extensions to minimizing the ℓth moment of error, and again provide an incentivization index and optimal proper scoring rule. In some cases, the resulting scoring rule is differentiable, but not infinitely differentiable. In these cases, we further prove that the optimum can be uniformly approximated by polynomial scoring rules. Finally, we compare common scoring rules via our measure, and include simulations confirming the relevance of our measure even in domains outside where it provably applies.
@article{Neyman2021BinarySR, preview = {incentives.jpg}, bibtex_show = {true}, title = {Binary Scoring Rules that Incentivize Precision}, author = {Neyman, Eric and Noarov, Georgy and Weinberg, S. Matthew}, arxiv = {2002.10669}, journal = {22nd ACM Conference on Economics and Computation (EC)}, year = {2021}, poster = {EC_Poster.pdf} }
2019
- AI Education Matters: Building a Fake News DetectorMichael Guerzhoy, Lisa Zhang, and Georgy NoarovAI Matters 2019
@article{Guerzhoy2019AIEM, preview = {fakenews.avif}, bibtex_show = {true}, title = {AI Education Matters: Building a Fake News Detector}, author = {Guerzhoy, Michael and Zhang, Lisa and Noarov, Georgy}, journal = {AI Matters}, year = {2019}, volume = {5}, pages = {18-20}, pdf = {http://sigai.acm.org/static/aimatters/5-3/AIMatters-5-3-05-Guerzhoy.pdf}, html = {https://dl.acm.org/doi/10.1145/3362077.3362082} }