Pith. sign in

REVIEW 2 major objections 5 minor 69 references

A hierarchical data structure keeps online proportional sampling efficient even as high-dimensional piecewise partitions explode under smoothed adversaries.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-14 08:00 UTC pith:UZPYIW3Q

load-bearing objection Solid multi-dimensional data structure for smoothed proportional sampling with tight depth bounds and clean no-regret applications; axis-parallel restriction is real but stated clearly. the 2 major comments →

arxiv 2607.10963 v1 pith:UZPYIW3Q submitted 2026-07-13 cs.LG cs.AIcs.CGcs.GTecon.TH

Efficient Online Proportional Sampling with Applications to Smoothed Online Learning

Amirmahdi Mirfakhar , Maria-Florina Balcan , Hedyeh Beyhaghi This is my paper
classification cs.LG cs.AIcs.CGcs.GTecon.TH
keywords online proportional samplingsmoothed analysishierarchical interval treeslazy insertionpiecewise-structured rewardsonline learningWeighted MajorityEXP3
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tackles a basic computational bottleneck that appears whenever a learner must repeatedly sample actions from a continuous domain whose reward landscape is piecewise structured and keeps changing. Naively, after t rounds in d dimensions the number of atomic regions can grow like t to the power d, so maintaining weights and sampling becomes intractable. The authors build a multi-layer interval-tree structure that never materializes every subregion; instead it records deferred contributions with a compact vector encoding that can later be scaled in constant time. Under a σ-smoothed adversary they prove the tree depth stays only O(sqrt(σ T)), which is tight, and therefore every insert, update, and draw costs only a sub-linear (in T) number of operations. The same machinery yields efficient no-regret implementations of Weighted Majority and EXP3 for piecewise-constant and piecewise-linear rewards under both full-information and bandit feedback. A sympathetic reader cares because the same primitive appears in dynamic pricing, contract design, and algorithm configuration, where previous theory either ignored computational cost or treated only the one-dimensional case.

Core claim

Under a σ-smoothed adaptive adversary the expected depth of the authors' hierarchical interval-tree data structure is tightly O(sqrt(σ T)); consequently every proportional-sampling operation can be performed in time O(d t^{(d+1)/2}), and the resulting online-learning algorithms achieve sublinear regret for the piecewise-structured rewards that arise in the target applications.

What carries the argument

Lazy Insertion together with scalable cumulative-reward vectors: new hyperplane endpoints are recorded only along the traversal path and deferred contributions are stored as monomial coefficient vectors that can be scaled to any subregion in O(1) time, so the structure never pays the full O(t^d) cascade cost.

Load-bearing premise

All discontinuities must be cut by axis-parallel hyperplanes (or by hyperplanes from a fixed finite set of directions); the full-information analysis further needs new cuts to arrive along only one free direction while the others stay inside a fixed finite menu.

What would settle it

Construct a σ-smooth adaptive sequence of axis-parallel partitions for which the longest increasing subsequence of projected endpoints forces expected tree height ω(sqrt(σ T)); if such a sequence exists the claimed depth bound is false.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies efficient online proportional sampling over a d-dimensional domain when the weight function is induced by a sequence of piecewise-structured partitions under a σ-smoothed adversary. The central technical contribution is a hierarchical interval-tree data structure with a Lazy Insertion mechanism and parametric (vector-valued) cumulative reward encodings that support insert, update, cumulative-reward, and exact proportional sampling without materializing the naïve O(t^d) atomic regions each round. Under a σ-smoothed adaptive (or oblivious) adversary the authors prove a tight O(√(σT)) bound on tree depth (Theorem 4.2), yielding O(d t^{(d+1)/2}) per-round time (Theorem 4.1); under random-order the depth improves to O(log T). The framework is applied to obtain efficient no-regret implementations of Weighted Majority (full information, piecewise-constant) and EXP3 (bandit, piecewise-linear) with explicit sublinear regret bounds (Theorems 6.1–6.2).

Significance. If the claims hold, the work supplies the first efficient data structure for exact proportional sampling over dynamically refined multi-dimensional piecewise partitions under smoothed adversaries, together with a tight smoothed analysis of hierarchical interval-tree height that is of independent interest (including a tight O(√(σT)) bound for longest increasing subsequence under a smoothed adversary). The resulting efficient WM/EXP3 implementations close a long-standing computational gap left by prior regret analyses of piecewise-structured online learning (Balcan et al., Cohen-Addad–Kanade). The Lazy Insertion + parametric-vector design and the r*-averse reduction are novel technical contributions that should be reusable beyond the present applications.

major comments (2)
  1. Lemma G.5 states that T requires O(t^d) memory, while the abstract and introduction claim the structure avoids “the cost of explicitly maintaining this exponential growth.” The Lazy Insertion analysis (Section 5, Theorem 4.1) reduces per-round insertion work to a product of heights, but does not appear to reduce asymptotic memory below O(t^d). Please clarify whether memory is truly O(t^d) even with deferred insertions, and if so, discuss the practical implications for moderate-to-large d; otherwise correct the memory bound.
  2. Theorem 6.1 (full-information) further restricts the adversary so that new endpoints arrive along only one designated direction while the remaining d−1 directions are drawn from a fixed set of size M. This is substantially stronger than the general σ-smooth model of Section 3 and limits applicability to the motivating settings (pricing, contract design, multi-parameter algorithm configuration). The manuscript should state more explicitly how restrictive this is for those applications and whether the restriction is information-theoretic or an artifact of the current exponential-weight scaling argument (Example 3 / Section I.1).
minor comments (5)
  1. Notation for regular vs. lazy nodes (v-nodes vs. w-nodes) and the multi-index chains ⃗r_{v0,…,wj,…} becomes dense in higher dimensions; a short notation table early in Section 5 would help.
  2. Figure 3 is helpful for the 2-d lazy/regular insertion idea; a companion schematic for the d-dimensional recursive construction (even a high-level one) would improve readability of Section F.
  3. The connection to longest increasing subsequence under a smoothed adversary is highlighted as a byproduct of independent interest; a short formal statement of that corollary (with the precise input model) would make the contribution easier to cite.
  4. In several places “Height(T^{(i)})” is used both for a random variable and for its expectation; making the distinction notationally consistent (e.g., always writing E[Height(·)] when the bound is in expectation) would avoid minor ambiguity.
  5. Typos / polish: “reward function parameterss” (double s) appears in the update discussion; “action parameter space” is used interchangeably with the domain [0,1]^d—pick one term.

Circularity Check

0 steps flagged

No circularity: depth, runtime, and regret bounds are derived from first-principles analysis of the r*-averse reduction, Cauchy-Schwarz on record increments, and standard WM/EXP3 under the stated smoothness model.

full rationale

The load-bearing claims (Theorems 4.1–4.2 on O(√(σT)) expected height under adaptive/oblivious σ-smoothed adversaries and the resulting O(d t^{(d+1)/2}) per-round cost; Theorems 6.1–6.2 on sublinear regret for Weighted Majority/EXP3) are obtained by an explicit reduction of tree height to the length of the longest increasing subsequence of endpoints under a monotone r*-averse strategy of shifted uniforms of length 1/σ, followed by a direct application of Cauchy–Schwarz to the sum of record increments whose total length is at most 1, plus a matching lower-bound construction. The same height bound is then multiplied by the number of layers to obtain the runtime of lazy insertion + parametric vector scaling. Regret follows the classical analyses of Weighted Majority and EXP3 once the data structure supplies exact proportional samples. No parameter is fitted to data and then re-used as a “prediction”; no uniqueness theorem or ansatz is imported from the authors’ prior work as a load-bearing premise; the citations to Balcan et al. and Cohen-Addad–Kanade supply only the application setting and the one-dimensional special case, not the multi-dimensional height or runtime proofs. The derivation is therefore self-contained under the explicitly stated axis-parallel (or fixed finite Γ) and one-direction-smoothness assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 2 invented entities

The paper rests on standard probabilistic and geometric assumptions plus the modeling choice that discontinuities are axis-parallel (or from a fixed direction set). No free parameters are fitted; the invented algorithmic devices (lazy insertion, parametric reward vectors) are methods rather than ontological entities.

axioms (4)
  • domain assumption A distribution is σ-smooth if its density is pointwise bounded by σ ≥ 1; hyperplanes parallel to each fixed direction are drawn independently from such distributions.
    Section 3; used throughout the height analysis and regret bounds.
  • domain assumption All partition boundaries are axis-parallel hyperplanes (or hyperplanes from a fixed finite set Γ of directions).
    Section 3 and the technical development of the data structure; essential for the interval-tree representation.
  • domain assumption Reward functions are piecewise polynomial of fixed degree with a common monomial basis; coefficients may vary by region and round.
    Section 4.1; enables the parametric vector encoding and closed-form scaling.
  • standard math Classical results on binary-search-tree height under random insertion order (Pittel 1984) and Hit-and-Run mixing for log-concave densities (Lovász-Vempala 2007).
    Invoked for the random-order depth bound and for sampling inside an atomic region.
invented entities (2)
  • Lazy Insertion mechanism (deferred structural insertion into associated trees) no independent evidence
    purpose: Avoids O(t^d) cascading updates by recording contributions at higher nodes and recovering them by scaling at query time.
    Core algorithmic novelty of Section 4–5; independent_evidence false because it is a data-structure design choice, not an external physical or mathematical object.
  • Parametric / scalable cumulative reward vectors no independent evidence
    purpose: Store monomial integrals separately so that deferred contributions can be scaled to subregions in O(1) time for non-constant rewards.
    Section 4.2 and Appendix A; again a representation technique rather than an independent entity.

pith-pipeline@v1.1.0-grok45 · 64759 in / 2802 out tokens · 33251 ms · 2026-07-14T08:00:35.707967+00:00 · methodology

0 comments
read the original abstract

We study the problem of efficient online proportional sampling from a high-dimensional domain under a $\sigma$-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions. This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design), and algorithm configuration and parameter tuning. The central challenge is maintaining an efficient data structure as the induced partition grows increasingly complex over time -- naively, the number of subregions can grow as $O(t^d)$ by round $t$ in $d$ dimensions. We design a data structure that supports efficient updates and proportional sampling while avoiding the cost of explicitly maintaining this exponential growth, where the discontinuities are structured from axis-parallel hyperplanes. Under a $\sigma$-smoothed adaptive adversary, we prove a tight $O(\sqrt{\sigma T})$ bound on the depth of our data structure, and an $O(\log T)$ bound under a random-order adversary -- to our knowledge, the first such results for this class of problems. We apply this framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms under both full-information and bandit feedback, with provable sublinear regret guarantees.

Figures

Figures reproduced from arXiv: 2607.10963 by Amirmahdi Mirfakhar, Hedyeh Beyhaghi, Maria-Florina Balcan.

Figure 1
Figure 1. Figure 1: ft. We now describe the technical core of T , a two-dimensional interval-tree struc￾ture for maintaining Ft. At a high level, T is a tree of trees: each level cor￾responds to one coordinate, with interval trees tracking projections onto that coordinate, where every node represents an interval whose endpoints are de￾termined by its children’s left and rightmost endpoints. Each node points to interval trees … view at source ↗
Figure 2
Figure 2. Figure 2: A 2-dimensional interval-tree T . (a): top-level interval tree T (0) over x-coordinate. (b): second￾level interval tree T (1), either regular or lazy, over y-coordinate associated with a node in the top-level. (c): each top-level node points to regular and lazy insertion trees over the other coordinate. Here are the components of the data structure in more detail: 1. Top-Level Tree T (0) (Horizontal Interv… view at source ↗
Figure 3
Figure 3. Figure 3: Lazy and Regular insertion of the green region [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The canonical path r ∗ . B.4 The Monotonic Structure of the Optimal Strategy πr ∗ for the r ∗ -Averse Adversary We now characterize the structure of the optimal policy πr ∗ for the r ∗ -averse adversary. We show that, in both the adaptive and oblivious settings, the adversary may be restricted without loss of generality to a simple monotone family of strategies. First, among all σ-smooth distributions on [… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

69 extracted references · 1 canonical work pages

  1. [3]

    New guarantees for learning revenue maximizing menus of lotteries and two-part tariffs

    Maria - Florina Balcan and Hedyeh Beyhaghi. New guarantees for learning revenue maximizing menus of lotteries and two-part tariffs. Transactions on Machine Learning Research, 2024. URL https://openreview.net/forum?id=mhawjZcmrJ

    2024

  2. [4]

    Data driven semi-supervised learning

    Maria - Florina Balcan and Dravyansh Sharma. Data driven semi-supervised learning. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual...

    2021

  3. [5]

    Dispersion for data-driven algorithm design, online learning, and private optimization

    Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 603--614. IEEE, 2018

    2018

  4. [6]

    Learning to link

    Maria - Florina Balcan, Travis Dick, and Manuel Lang. Learning to link. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 . OpenReview.net, 2020. URL https://openreview.net/forum?id=S1eRbANtDB

    2020

  5. [7]

    Learning-to-learn non-convex piecewise-lipschitz functions

    Maria - Florina Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Learning-to-learn non-convex piecewise-lipschitz functions. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 15056--15069, 2021. URL https://proceedings.ne...

    2021

  6. [8]

    Provably tuning the elasticnet across instances

    Maria - Florina Balcan, Misha Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the elasticnet across instances. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orlean...

    2022

  7. [9]

    Algorithm configuration for structured pfaffian settings, 2024 a

    Maria-Florina Balcan, Anh Tuan Nguyen, and Dravyansh Sharma. Algorithm configuration for structured pfaffian settings, 2024 a . URL https://arxiv.org/abs/2409.04367

    Pith/arXiv arXiv 2024

  8. [10]

    Accelerating ERM for data-driven algorithm design using output-sensitive techniques

    Maria - Florina Balcan, Christopher Seiler, and Dravyansh Sharma. Accelerating ERM for data-driven algorithm design using output-sensitive techniques. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024 b . URL http://pap...

    2024

  9. [11]

    Hartline

    Avrim Blum and Jason D. Hartline. Near-optimal online auctions. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005 , pages 1156--1163. SIAM , 2005. URL http://dl.acm.org/citation.cfm?id=1070432.1070597

    arXiv 2005

  10. [12]

    Sampling with unequal probabilities

    Ken RW Brewer and Muhammad Hanif. Sampling with unequal probabilities. New York: Springer, 1983

    1983

  11. [13]

    X-armed bandits

    S \'e bastien Bubeck, R \'e mi Munos, Gilles Stoltz, and Csaba Szepesv \'a ri. X-armed bandits. Journal of Machine Learning Research, 12 0 (5), 2011

    2011

  12. [14]

    Prediction, Learning, and Games

    Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006

    2006

  13. [15]

    Algorithmic chaining and the role of partial feedback in online nonparametric learning

    Nicol \`o Cesa-Bianchi, Pierre Gaillard, Claudio Gentile, and S \'e bastien Gerchinovitz. Algorithmic chaining and the role of partial feedback in online nonparametric learning. In Conference on Learning Theory, pages 465--481. PMLR, 2017

    2017

  14. [16]

    Probability Proportional Sampling, pages 5069--5071

    Adam Ka Lok Cheung. Probability Proportional Sampling, pages 5069--5071. Springer Netherlands, Dordrecht, 2014. ISBN 978-94-007-0753-5

    2014

  15. [17]

    Sampling techniques

    William Gemmell Cochran. Sampling techniques. john wiley & sons, 1977

    1977

  16. [18]

    Online optimization of smoothed piecewise constant functions

    Vincent Cohen-Addad and Varun Kanade. Online optimization of smoothed piecewise constant functions. In Artificial Intelligence and Statistics, pages 412--420. PMLR, 2017

    2017

  17. [19]

    Introduction to algorithms

    Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022

    2022

  18. [20]

    Haas, and Chris Jermaine

    Graham Cormode, Minos Garofalakis, Peter J. Haas, and Chris Jermaine. Synopses for massive data: Samples, histograms, wavelets, sketches. Found. Trends Databases, 4 0 (1--3): 0 1--294, January 2012. ISSN 1931-7883

    2012

  19. [21]

    Computational geometry: algorithms and applications

    Mark De Berg. Computational geometry: algorithms and applications. Springer Science & Business Media, 2000

    2000

  20. [22]

    Semi-bandit optimization in the dispersed setting

    Travis Dick, Wesley Pegden, and Maria - Florina Balcan. Semi-bandit optimization in the dispersed setting. In Proceedings of the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2020, virtual online, August 3-6, 2020 , volume 124 of Proceedings of Machine Learning Research, pages 909--918. AUAI Press, 2020. URL http://proceedings.mlr...

    2020

  21. [24]

    A pac approach to application-specific algorithm selection

    Rishi Gupta and Tim Roughgarden. A pac approach to application-specific algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 123--134, 2016

    2016

  22. [25]

    Smoothed analysis with adaptive adversaries

    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. Journal of the ACM, 71 0 (3): 0 1--34, 2024

    2024

  23. [26]

    Multidimensional segment trees can do range updates in poly-logarithmic time

    Nabil Ibtehaz, M Kaykobad, and M Sohel Rahman. Multidimensional segment trees can do range updates in poly-logarithmic time. Theoretical Computer Science, 854: 0 30--43, 2021

    2021

  24. [28]

    The geometry of logconcave functions and sampling algorithms

    L \'a szl \'o Lov \'a sz and Santosh Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures & Algorithms, 30 0 (3): 0 307--358, 2007

    2007

  25. [29]

    Randomized Algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995

    1995

  26. [30]

    On growing random binary trees

    Boris Pittel. On growing random binary trees. Journal of Mathematical Analysis and Applications, 103 0 (2): 0 461--480, 1984

    1984

  27. [31]

    Spielman and Shang - Hua Teng

    Daniel A. Spielman and Shang - Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. CoRR, cs.DS/0111050, 2001. URL https://arxiv.org/abs/cs/0111050

    arXiv 2001

  28. [32]

    Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023 , page 1188. ACM , 2023

    2023

  29. [33]

    Jordan , title =

    Banghua Zhu and Stephen Bates and Zhuoran Yang and Yixin Wang and Jiantao Jiao and Michael I. Jordan , title =. Proceedings of the 24th

  30. [34]

    Commitment Without Regrets: Online Learning in Stackelberg Security Games , booktitle =

    Maria. Commitment Without Regrets: Online Learning in Stackelberg Security Games , booktitle =

  31. [35]

    1977 , publisher=

    Sampling techniques , author=. 1977 , publisher=

    1977

  32. [36]

    1983 , publisher=

    Sampling with unequal probabilities , author=. 1983 , publisher=

    1983

  33. [37]

    Probability Proportional Sampling

    Cheung, Adam Ka Lok. Probability Proportional Sampling. Encyclopedia of Quality of Life and Well-Being Research. 2014

    2014

  34. [38]

    Randomized Algorithms , publisher=

    Motwani, Rajeev and Raghavan, Prabhakar , year=. Randomized Algorithms , publisher=

  35. [39]

    and Jermaine, Chris , title =

    Cormode, Graham and Garofalakis, Minos and Haas, Peter J. and Jermaine, Chris , title =. Found. Trends Databases , month = jan, pages =. 2012 , publisher =

    2012

  36. [40]

    Mahoney , title =

    Petros Drineas and Ravi Kannan and Michael W. Mahoney , title =. 2006 , url =. doi:10.1137/S0097539704442696 , timestamp =

    work page doi:10.1137/s0097539704442696 2006

  37. [41]

    Noga Alon and Yossi Matias and Mario Szegedy , title =. J. Comput. Syst. Sci. , volume =. 1999 , url =. doi:10.1006/JCSS.1997.1545 , timestamp =

    doi:10.1006/jcss.1997.1545 1999

  38. [42]

    Prediction, Learning, and Games , publisher=

    Cesa-Bianchi, Nicolo and Lugosi, Gabor , year=. Prediction, Learning, and Games , publisher=

  39. [43]

    Vempala , title =

    Adam Tauman Kalai and Santosh S. Vempala , title =. J. Comput. Syst. Sci. , volume =. 2005 , url =. doi:10.1016/J.JCSS.2004.10.016 , timestamp =

    doi:10.1016/j.jcss.2004.10.016 2005

  40. [44]

    The Nonstochastic Multiarmed Bandit Problem , journal =

    Peter Auer and Nicol. The Nonstochastic Multiarmed Bandit Problem , journal =. 2002 , url =. doi:10.1137/S0097539701398375 , timestamp =

    doi:10.1137/s0097539701398375 2002

  41. [45]

    Artificial Intelligence and Statistics , pages=

    Online optimization of smoothed piecewise constant functions , author=. Artificial Intelligence and Statistics , pages=. 2017 , organization=

    2017

  42. [46]

    Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , pages=

    A PAC approach to application-specific algorithm selection , author=. Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , pages=

    2016

  43. [47]

    Jordan , title =

    Banghua Zhu and Stephen Bates and Zhuoran Yang and Yixin Wang and Jiantao Jiao and Michael I. Jordan , title =. Proceedings of the 24th. 2023 , url =. doi:10.1145/3580507.3597673 , timestamp =

    doi:10.1145/3580507.3597673 2023

  44. [48]

    New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs , journal =

    Maria. New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs , journal =. 2024 , url =

    2024

  45. [49]

    Learning to Link , booktitle =

    Maria. Learning to Link , booktitle =. 2020 , url =

    2020

  46. [50]

    Hartline , title =

    Avrim Blum and Jason D. Hartline , title =. Proceedings of the Sixteenth Annual. 2005 , url =

    2005

  47. [51]

    Commitment Without Regrets: Online Learning in Stackelberg Security Games , booktitle =

    Maria. Commitment Without Regrets: Online Learning in Stackelberg Security Games , booktitle =. 2015 , timestamp =

    2015

  48. [52]

    Spielman and Shang

    Daniel A. Spielman and Shang. Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time , journal =. 2001 , url =

    2001

  49. [53]

    2024 , eprint=

    Algorithm Configuration for Structured Pfaffian Settings , author=. 2024 , eprint=

    2024

  50. [54]

    Learning-to-learn non-convex piecewise-Lipschitz functions , booktitle =

    Maria. Learning-to-learn non-convex piecewise-Lipschitz functions , booktitle =. 2021 , url =

    2021

  51. [55]

    Accelerating

    Maria. Accelerating. Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024 , year =

    2024

  52. [56]

    Semi-bandit Optimization in the Dispersed Setting , booktitle =

    Travis Dick and Wesley Pegden and Maria. Semi-bandit Optimization in the Dispersed Setting , booktitle =. 2020 , url =

    2020

  53. [57]

    Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009

    Pure exploration in multi-armed bandits problems , author=. Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009. Proceedings 20 , pages=. 2009 , organization=

    2009

  54. [58]

    2000 , publisher=

    Computational geometry: algorithms and applications , author=. 2000 , publisher=

    2000

  55. [59]

    2022 , publisher=

    Introduction to algorithms , author=. 2022 , publisher=

    2022

  56. [60]

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Dispersion for data-driven algorithm design, online learning, and private optimization , author=. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2018 , organization=

    2018

  57. [61]

    2012 , publisher=

    Calculus of several variables , author=. 2012 , publisher=

    2012

  58. [62]

    Numerische mathematik , volume=

    Gaussian elimination is not optimal , author=. Numerische mathematik , volume=. 1969 , publisher=

    1969

  59. [63]

    Journal of Mathematical Analysis and Applications , volume=

    On growing random binary trees , author=. Journal of Mathematical Analysis and Applications , volume=. 1984 , publisher=

    1984

  60. [64]

    Theoretical Computer Science , volume=

    Multidimensional segment trees can do range updates in poly-logarithmic time , author=. Theoretical Computer Science , volume=. 2021 , publisher=

    2021

  61. [65]

    Journal of the ACM , volume=

    Smoothed analysis with adaptive adversaries , author=. Journal of the ACM , volume=. 2024 , publisher=

    2024

  62. [66]

    arXiv preprint arXiv:2504.03745 , year=

    No-Regret Learning in Stackelberg Games with an Application to Electric Ride-Hailing , author=. arXiv preprint arXiv:2504.03745 , year=

    arXiv

  63. [67]

    arXiv preprint arXiv:2504.15568 , year=

    Is Learning Effective in Dynamic Strategic Interactions? Evidence from Stackelberg Games , author=. arXiv preprint arXiv:2504.15568 , year=

    Pith/arXiv arXiv

  64. [68]

    Random Structures & Algorithms , volume=

    The geometry of logconcave functions and sampling algorithms , author=. Random Structures & Algorithms , volume=. 2007 , publisher=

    2007

  65. [69]

    Wiley statsref: statistics reference online , pages=

    Probability proportional to size (PPS) sampling , author=. Wiley statsref: statistics reference online , pages=. 2014 , publisher=

    2014

  66. [70]

    Conference on Learning Theory , pages=

    Algorithmic chaining and the role of partial feedback in online nonparametric learning , author=. Conference on Learning Theory , pages=. 2017 , organization=

    2017

  67. [71]

    , author=

    X-Armed Bandits. , author=. Journal of Machine Learning Research , volume=

  68. [72]

    Provably tuning the ElasticNet across instances , booktitle =

    Maria. Provably tuning the ElasticNet across instances , booktitle =. 2022 , url =

    2022

  69. [73]

    Data driven semi-supervised learning , booktitle =

    Maria. Data driven semi-supervised learning , booktitle =. 2021 , url =

    2021