Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective

Abhishek Shetty; Adam Block

REVIEW 3 major objections 5 minor 54 references

Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A rho-separation condition on the function class lets a Gaussian-perturbed leader achieve small-loss regret and optimal-rate private learning through a new Gaussian-process stability bound.

desk verdict The Gaussian stability lemma and the online small-loss bound are the real contributions; the privacy theorem does not follow from its proof as stated and the exponential comparison to Wang et al. is overstated, but the core idea is sound and deserves a serious referee. read the letter →

arxiv 2502.10292 v1 pith:BG6P4Q2F submitted 2025-02-14 cs.LG stat.ML

Adam Block , Abhishek Shetty This is my paper · ORCID

classification cs.LGstat.ML MSC 68Q3268T05

keywords onlinelearningsmall-lossboundsdifferentialprivacyoracleefficiencyfollowtheperturbedleaderGaussianprocessrho-separationregret

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims that a single geometric condition, $\rho$-separation, is enough to make oracle-efficient algorithms achieve the strong stability that small-loss online learning and differentially private learning both require. Under $\rho$-separation, distinct functions in the class must be at least $\rho$ apart in $L^2(\mu)$ for some measure $\mu$, so noisy versions of a hypothesis remain distinguishable. The paper derives a Gaussian-process stability bound (Lemma 1) showing that the distribution of the minimizer changes only mildly when the mean function changes by a bounded amount, and uses it to analyze a Follow-the-Perturbed-Leader algorithm with Gaussian perturbation. The resulting regret is $\widetilde{O}\big(\sqrt{\log|\mathcal F|\,L^{\star}}/\rho + \log|\mathcal F|/\rho^2\big)$, and a private variant attains optimal sample complexity up to the standard privacy cost.

What carries the argument

The load-bearing object is a Gaussian process indexed by the function class $\mathcal F$, with mean equal to the cumulative loss (or empirical loss) and covariance kernel $K(f,f')=\langle f,f'\rangle_m$ on a fixed $\rho$-separating set of points. Lemma 1 controls how the distribution of the process's argmin changes when the mean function changes by at most $\tau$; the proof pins the Gaussian process at its minimizer, uses the fact that a pinned Gaussian process has a covariance independent of the pinning value, and adds an auxiliary constant function to remove any lower bound on the covariance. The $\rho$-separation assumption is what lets $L^2$ distance between distinct functions serve as a certificate that they remain distinguishable under noise.

What would settle it

Compute, for a small $\rho$-separated class such as the Hadamard class on $\mathbb F_2^n$, the exact selection probabilities $P(f^{*}=f)$ and $P(f^{*\prime}=f)$ for a two-point Gaussian process with mean shift $\tau$, and check whether any parameter choice violates the ratio bound in Lemma 1; a violation would disprove the stability lemma. Alternatively, take a standard ERM oracle for such a class and show that the augmented objectives used in Algorithm 1 cannot be solved with a polylogarithmic number of oracle calls, which would falsify the oracle-efficiency claim.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Lemma 1: for a $\rho$-separated function class, if two mean functions $m,m'$ satisfy $\sup_{f\in\mathcal F}|m(f)-m'(f)|\le \tau$ and the noise level satisfies $\eta \ge 32\tau \rho^{-2}\big(E[\sup_{f\in\mathcal F}\omega(f)]+\sqrt{2\log(2/\delta)}\big)$, then $P(f^{*}=f)\le \big(1+\frac{32\tau}{\eta\rho^2}(E[\sup_{f\in\mathcal F}\omega(f)]+\sqrt{2\log(2/\delta)})\big)P(f^{*\prime}=f)+\delta$ for every $f$. This distributional stability, rather than mere closeness of minimizers, is what converts the bias-stability tradeoff of Follow-the-Perturbed-Leader into a small-loss regret bound and turns perturbed ERM into a differentially private learner. The paper presents $\rho$-separation as the structural condition underlying separator sets and $\gamma$-approximability, and it exhibits classes where the Gaussian perturbation improves over both.

Load-bearing premise

The load-bearing premise is that the learner's ERM oracle can also solve the perturbed minimization problem that adds a Gaussian linear functional on a fixed auxiliary set, since Algorithms 1 and 2 are defined through such calls and the proofs do not show how to implement them with a plain ERM oracle.

Editorial extensions

If this is right

With constant separation $\rho$, Algorithm 1 achieves $\widetilde{O}\big(\sqrt{\log|\mathcal F|\,L^{\star}}+\log|\mathcal F|\big)$ expected regret, which is optimal up to logarithmic factors in $T$, and it recovers $\widetilde{O}(\sqrt{T\log|\mathcal F|}/\rho)$ regret in the worst case.
For classes with a separator set of size $m$, the same algorithm gives $\widetilde{O}(m\log|\mathcal F|+\sqrt{mT\log|\mathcal F|})$ regret, improving the separator-based bound of Syrgkanis et al.; for $\delta$-admissible classes it also improves the Dudík et al. bound by a $\sqrt{m}$ factor in the dominant term.
Since $\gamma$-approximability implies $\rho$-separation at the cost of a $\sqrt{m}$ factor, Gaussian FTPL attains $\widetilde{O}(\gamma\sqrt{m\log|\mathcal F|\,L^{\star}}+m\gamma^2\log|\mathcal F|)$ regret, reducing the dominant term of the Wang et al. bound by $\sqrt{m}$; on Hadamard classes the gap becomes exponential in the natural parameter.
With constant separation, Algorithm 2 is $(\varepsilon,\delta)$-differentially private and achieves the sample complexity of non-private learning up to the standard $\varepsilon^{-1}$ privacy blow-up, which is impossible for general classes because private learning requires finite Littlestone dimension.
The separating measure does not constrain the test distribution, so certifying $\rho$-separation can be done once, as a preprocessing step, and reused for later learning tasks over the same class.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The authors leave implicit that the Gaussian stability lemma should generalize to any sub-Gaussian perturbation with matching tail bounds, which would give analogous small-loss and private learners for Laplacian or other perturbation families.
Because the separating set is fixed and distribution-free, the authors leave implicit that its certification cost can be amortized across many tasks with the same hypothesis class.
An implementation question left open is whether standard ERM solvers for concrete classes can answer the augmented oracle calls (cumulative loss plus a Gaussian linear functional) with the same efficiency as plain ERM, since Algorithms 1 and 2 are defined through such calls.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The online learning half is in good shape; the privacy half has a real algebraic error in the stated theorem, and the comparison to Wang et al. oversells the gap. The central technical contribution is genuine and deserves referee time.

Lemma 1 is the heart of the paper and a real advance: a Gaussian-process stability bound that trades the covariance well-conditioning assumption from Block et al. 2022/2024a for the new rho-separation condition, giving exactly the distributional control that small-loss and private learning need. The proof in Appendix B is detailed and follows the established template. rho-separation itself is a clean unification of separator sets and gamma-approximability, and Theorem 1's regret bound—roughly sqrt(log|F|*L*)/rho plus log|F|/rho^2—checks out; the Be-the-Leader analysis in Appendix C is coherent. The paper is also upfront that separation limits generality, which is fair. For the online learning result alone I'd send this out.

The problems start in Section 3.2. Theorem 2's stated sample complexity does not follow from the proof. Substitute Lemma 2's eta into Lemma 3's accuracy condition and you get cross terms G(F)sqrt(log(1/delta)) and G(F)sqrt(log(1/beta)) over epsilon*rho^2*alpha alongside the retained G(F)^2 and sqrt(log(1/delta)log(1/beta)) terms. The cross terms are dropped without justification, and they are not dominated by the retained ones across the parameter range. The stress-test note says the G(F)^2/(epsilon*rho^2*alpha) term is also omitted—that part is wrong; that term appears in the stated numerator. But the core complaint is right: the "and simplifying" step in Section 4.3 does not produce the displayed bound. This is fixable by restating Theorem 2, but the theorem as printed is not implied by the derivation.

Proposition 3 also overstates the case against Wang et al. The exponential gap comes from evaluating their bound with a truth-table matrix whose width forces the sqrt(m log|F|) term. A more sensible gamma-approximable matrix—basis evaluations, m equal to the dimension, gamma on the order of n—brings Wang's regret down to polynomial and leaves a sqrt(n) gap, not an exponential one. The paper gives no lower bound on gamma-approximability for its constructions, so the exponential claim should be proven or dropped.

One caveat on framing: the algorithms need the oracle to minimize the cumulative loss plus a linear Gaussian functional. The paper states this explicitly in its oracle definition and it is standard for FTPL, but it is a stronger requirement than a plain ERM oracle, and "oracle-efficient" should be read with that in mind.

Bottom line: the paper is for people working on oracle-efficient online and private learning, and the stability lemma is a reusable tool. Send it to review with a request to fix Theorem 2 and tone down Proposition 3.

Referee Report

3 major / 5 minor

Summary. The paper introduces a Gaussian-process stability lemma (Lemma 1) proving that, for a ρ-separated function class, the distribution of the minimizer of a Gaussian process changes by a controlled multiplicative factor when the mean function is perturbed by at most τ. This lemma is then used to derive two main results under the ρ-separation condition: an oracle-efficient Follow-the-Perturbed-Leader algorithm with a small-loss regret bound (Theorem 1), and a differentially private ERM variant with a claimed optimal sample complexity rate (Theorem 2). The paper unifies prior stability-based frameworks such as separator sets and γ-approximability, and gives examples where the new regret bound improves on existing oracle-efficient algorithms.

Significance. If the Gaussian-process stability lemma is correct, it is a substantial technical contribution: it strengthens previously known approximate-minimizer closeness bounds to a distributional stability bound, and it removes a well-conditionedness assumption on the covariance kernel. This could provide a widely applicable tool for oracle-efficient online and private learning. The regret improvement over prior FTPL analyses in the comparison with Wang et al. is meaningful, and the explicit connection between ρ-separation, separator sets, and γ-approximability is a useful conceptual unification. However, the paper's advertised optimal-rate private learning guarantee is currently not supported by the provided derivation, which tempers the overall assessment until the theorem and its proof are corrected.

major comments (3)

[Section 3.2, Theorem 2 and Section 4.3, Lemma 3] The sample complexity stated in Theorem 2 does not follow from the proof. Lemma 3 requires n ≥ η(G(F)+√log(1/β))/α, and Lemma 2 sets η ≍ (G(F)+√log(1/δ))/(ρ^2 ε). Substituting η into Lemma 3 gives a second max argument of order ((G(F)+√log(1/δ))(G(F)+√log(1/β)))/(α ρ^2 ε), which contains the four terms G(F)^2, G(F)√log(1/δ), G(F)√log(1/β), and √(log(1/δ)log(1/β)), each divided by α ρ^2 ε. The expression printed in Theorem 2 retains only G(F)^2 and the product-of-logs term (or, if parsed with G(F)^2 outside the fraction, omits G(F)^2/(α ρ^2 ε) entirely); the two cross terms G(F)√log(1/δ) and G(F)√log(1/β) are missing under either reading. Since all these terms are positive, the stated n can be strictly smaller than the sufficient n established by the proof. In the common regime √log(1/δ) ≍ G(F), the missing cross term is of the same order as the retained G(F)^2 term, so the omission is not merely a constant-factor issue. The theorem should be restated with the full expression obtained by substitution, or an additional argument must be supplied showing that the cross terms can be absorbed without changing the claimed rate.
[Section 3.2, Theorem 2 vs. Algorithm 2] Theorem 2 assumes that the points Z_1,...,Z_m are a fixed ρ-separating set for F, but Algorithm 2 (Step 1) draws Z_1,...,Z_m as i.i.d. samples from a separating distribution μ, which is not mentioned in the theorem. The privacy proof in Section 4.3 (Lemma 2) relies on sampled separation: it invokes Proposition 2 to assert that the empirical measure of the sampled points is ρ/2-separating with high probability. That argument requires a lower bound on m and an explicit distribution μ, as given in Lemma 7. As stated, Theorem 2 provides neither, so the reader cannot verify the differential privacy guarantee from the stated assumptions. The theorem, the algorithm pseudocode, and the proof should be aligned: either state the condition as 'μ is a ρ-separating measure and m is sufficiently large' (with the quantitative bound on m), or change Algorithm 2 to use the fixed separating set Z.
[Section 2.1 and Algorithms 1-2] The oracle-efficiency claim depends on an augmented oracle. The ERM oracle is defined in Section 2.1 to accept, in addition to ordinary losses, linear functionals of the form ξ_i f(x_i) for Gaussian ξ_i on auxiliary points, and both Algorithm 1 (Step 2) and Algorithm 2 (Step 3) require this capability for every oracle call. This is a genuine strengthening of the standard ERM oracle: it may not be implementable by an off-the-shelf empirical risk minimizer without further modification. The paper should state this augmented-oracle requirement explicitly as a separate assumption and discuss when it can be simulated by a standard ERM oracle, for example by augmenting the input representation or the function class. Without such a discussion, the practical scope of the oracle-efficiency claim is overstated.

minor comments (5)

[Section 4.3, Lemma 2 proof] The Gaussian process in the proof of Lemma 2 is written as Ω(f) = Σ_i ℓ(f(x_i),y_i) + (1/√m) Σ_i ξ_i f(z_i), but Algorithm 2 uses the perturbation (η/√m) Σ_i ω_i f(z_i). The factor η is missing from the process definition in the proof; without it, the subsequent condition on η does not correspond to the algorithm's noise scale. Please insert the missing η.
[Section 2.2, Proposition 2 and proof of Lemma 2] The proof of Lemma 2 cites Proposition 2 for the statement that a sample of size m = (d + log(100/δ))ρ^{-2} induces a ρ/2-separating measure with high probability. Proposition 2 only states existence of a separating set of polynomial size; the high-probability sample bound is Lemma 7. Please cite Lemma 7 here.
[Section 3.1, Theorem 1] Theorem 1 uses log(|F|) in the regret bound but does not explicitly state that F is finite. The comparison examples and the Hadamard construction assume finite classes; please add a finiteness assumption or replace |F| with a Gaussian-complexity bound that applies to infinite classes.
[Section 4.3, Lemma 3] The second argument of the max in Lemma 3 is printed as ηG(F) + √log(1/β)/α, but the proof bounds the perturbation by (η/n)(G(F)+√log(1/β)), so the statement should be η(G(F)+√log(1/β))/α.
[Global] There are several typos and redundancies: 'stengthens' in the introduction, 'In aprticular' in Section 2.1, and the duplicated phrase 'we get the following result we get that' at the end of Section 4.3. These should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: Lemma 1 is proved in-appendix and the small-loss and privacy bounds are derived from it rather than assumed.

full rationale

The derivation chain is self-contained. Lemma 1 is not an input to itself: Appendix B proves it from a Gaussian tail bound, a pinned-Gaussian covariance calculation, and an auxiliary well-conditioned process; the proof does not invoke the small-loss regret or differential privacy statements of Theorems 1 and 2. Theorem 1 follows by substituting Lemma 1 into the Be-the-Leader bound and balancing eta subject to the lemma's condition, with L* arising from a second BTL estimate rather than from the desired regret bound. Theorem 2 follows by instantiating Lemma 1 with tau=1 for privacy and then combining uniform convergence with Gaussian concentration for the perturbation; no fitted parameter is renamed as a prediction. rho-separation is an explicit hypothesis, and the relationships to separator sets and gamma-approximability are proved (Propositions 2 and 3, Appendix E), not assumed as the desired conclusions. The paper's self-citations to Block et al. for the proof template and FTPL family are not load-bearing: the new lemma and theorems are given full proofs in this manuscript, and the cited results are used only as a source of a technical density inequality and proof strategy. The requirement that the ERM oracle can also minimize loss plus a Gaussian linear functional is an implicit modelling assumption; an assumption is not a circular reduction. The apparent omission of a G(F)^2/(alpha epsilon rho^2) term in the displayed sample complexity of Theorem 2 is a derivation-checking concern, distinct from circularity.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central result rests on the separation condition, the augmented oracle, and standard concentration inequalities. No constants are fitted to data; the only tuning parameter is eta, whose optimal value depends on the unknown L*. The privacy theorem's sample bound contains an algebraic error, which is a soundness issue rather than a free-parameter issue.

free parameters (1)

eta (Gaussian perturbation scale) = optimal choice depends on unknown L* (left-hand side of the balancing inequality in Appendix C)
Theorem 1's bound holds for an eta that is a function of L*, the optimal loss of the benchmark function. The learner does not know L* in advance, so as stated the algorithm is not adaptive to the small-loss regime unless a doubling or epoch trick is added, which the paper does not describe.

assumptions (4)

domain assumption The ERM oracle can minimize loss plus a Gaussian linear functional on the separating set Z, i.e. it can solve argmin_f sum_i loss(f(x_i), y_i) + eta m^{-1/2} sum_j xi_j f(Z_j).
Algorithms 1 and 2 require this stronger oracle; standard ERM oracles that only handle the loss are not sufficient. The paper notes that constructing a separating set may modify the oracle assumption, Section 3.1.
domain assumption There exists a known rho-separating measure mu, and a sample from it of size O(log|F|/rho^2) preserves rho/2 separation with high probability.
This is the separation condition of Definition 5; the sampling preservation is Lemma 7, which relies on finite-class uniform convergence.
standard math Standard Gaussian concentration inequalities and the Be-the-Leader lemma (Kalai-Vempala) are used without proof.
Used in proofs of Theorem 1 and Lemma 4, e.g., in Section 4.2 and Appendix C.
domain assumption The function class F is finite, as implied by separation plus learnability and required by the log|F| terms in the bounds.
Theorem 1's bound contains log|F|; the paper explicitly says it is assuming F is finite in the discussion after Theorem 1. Proposition 2 shows learnability plus rho-separation implies finiteness in the binary case.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective." pith.science (2026). https://pith.science/paper/BG6P4Q2F

@misc{pith2026250210292,
  author       = {Pith},
  title        = {Pith review of: Small Loss Bounds for Online Learning Separated Function Classes: A Gaussian Process Perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BG6P4Q2F}},
  note         = {Machine review of arXiv:2502.10292}
}

abstract

In order to develop practical and efficient algorithms while circumventing overly pessimistic computational lower bounds, recent work has been interested in developing oracle-efficient algorithms in a variety of learning settings. Two such settings of particular interest are online and differentially private learning. While seemingly different, these two fields are fundamentally connected by the requirement that successful algorithms in each case satisfy stability guarantees; in particular, recent work has demonstrated that algorithms for online learning whose performance adapts to beneficial problem instances, attaining the so-called small-loss bounds, require a form of stability similar to that of differential privacy. In this work, we identify the crucial role that separation plays in allowing oracle-efficient algorithms to achieve this strong stability. Our notion, which we term $\rho$-separation, generalizes and unifies several previous approaches to enforcing this strong stability, including the existence of small-separator sets and the recent notion of $\gamma$-approximability. We present an oracle-efficient algorithm that is capable of achieving small-loss bounds with improved rates in greater generality than previous work, as well as a variant for differentially private learning that attains optimal rates, again under our separation condition. In so doing, we prove a new stability result for minimizers of a Gaussian process that strengthens and generalizes previous work.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 42 canonical work pages

[1]

Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, and Ambuj Tewari

Jacob D. Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, and Ambuj Tewari. Online learning via the differential privacy lens. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019

work page 2019
[2]

John M. Abowd. The U.S. census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, page 2867, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355520

work page 2018
[3]

Learning in non-convex games with an optimization oracle

Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Conference on Learning Theory, pages 18--29. PMLR, 2019

work page 2019
[4]

Private PAC learning implies finite littlestone dimension

Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pages 852--860. ACM , 2019

work page 2019
[5]

The multiplicative weights update method: a meta-algorithm and applications

Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 0 (6), 2012

work page 2012
[6]

Bartlett and Shahar Mendelson

Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. In Computational Learning Theory, 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19, 2001, Proceedings , Lectu...

work page 2001
[7]

Fat-shattering and the learnability of real-valued functions

Peter L Bartlett, Philip M Long, and Robert C Williamson. Fat-shattering and the learnability of real-valued functions. In Proceedings of the seventh annual conference on Computational learning theory, 1994

work page 1994
[8]

Limits of private learning with access to public data

Raef Bassily, Shay Moran, and Noga Alon. Limits of private learning with access to public data. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019

work page 2019

Show all 54 references

[9]

Learning privately with labeled and unlabeled examples

Amos Beimel, Kobbi Nissim, and Uri Stemmer. Learning privately with labeled and unlabeled examples. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015 . SIAM , 2015

2015
[10]

Agnostic online learning

Shai Ben-David, D \'a vid P \'a l, and Shai Shalev-Shwartz. Agnostic online learning. 2009

2009
[11]

Harmonic analysis and applications

John J Benedetto. Harmonic analysis and applications. CRC Press, 2020

2020
[12]

Smoothed analysis of sequential probability assignment

Alankrita Bhatt, Nika Haghtalab, and Abhishek Shetty. Smoothed analysis of sequential probability assignment. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December ...

2023
[13]

The sample complexity of approximate rejection sampling with applications to smoothed online learning

Adam Block and Yury Polyanskiy. The sample complexity of approximate rejection sampling with applications to smoothed online learning. In The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India , Proceedings of Machine Learning Resea...

2023
[14]

Smoothed online learning is as easy as statistical learning

Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. In Conference on Learning Theory, pages 1716--1786. PMLR, 2022

2022
[15]

Oracle-efficient smoothed online learning for piecewise continuous decision making

Adam Block, Max Simchowitz, and Alexander Rakhlin. Oracle-efficient smoothed online learning for piecewise continuous decision making. In Proceedings of Thirty Sixth Conference on Learning Theory, Proceedings of Machine Learning Research. PMLR, 2023

2023
[16]

Oracle-efficient differentially private learning with public data

Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, and Steven Wu. Oracle-efficient differentially private learning with public data. arXiv preprint arXiv:2402.09483, 2024 a

2024 arXiv
[17]

On the performance of empirical risk minimization with smoothed data

Adam Block, Alexander Rakhlin, and Abhishek Shetty. On the performance of empirical risk minimization with smoothed data. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Resea...

2024
[18]

Smoothed online learning for prediction in piecewise affine systems

Adam Block, Max Simchowitz, and Russ Tedrake. Smoothed online learning for prediction in piecewise affine systems. Advances in Neural Information Processing Systems, 36, 2024 c

2024
[19]

Concentration Inequalities: A Nonasymptotic Theory of Independence

St \'e phane Boucheron, G \'a bor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford, 2013. ISBN 9780199535255

2013
[20]

An equivalence between private classification and online prediction

Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. ArXiv preprint, 2020

2020
[21]

Prediction, learning, and games

Nicolo Cesa-Bianchi and G \'a bor Lugosi. Prediction, learning, and games. Cambridge university press, 2006

2006
[22]

Oracle-efficient online learning and auction design

Miroslav Dud \' k, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan. Oracle-efficient online learning and auction design. Journal of the ACM (JACM), 67 0 (5): 0 1--57, 2020

2020
[23]

The speed of mean glivenko-cantelli convergence

Richard Mansfield Dudley. The speed of mean glivenko-cantelli convergence. The Annals of Mathematical Statistics, 0 (1), 1969

1969
[24]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings , Lecture Notes in Computer ...

2006
[25]

The algorithmic foundations of differential privacy

Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 0 (3--4), 2014

2014
[26]

Dual query: Practical private query release for high dimensional data

Marco Gaboardi, Emilio Jes \' u s Gallego Arias, Justin Hsu, Aaron Roth, and Zhiwei Steven Wu. Dual query: Practical private query release for high dimensional data. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June ...

2014
[27]

Exact identification of read-once formulas using fixed points of amplification functions

Sally A Goldman, Michael J Kearns, and Robert E Schapire. Exact identification of read-once formulas using fixed points of amplification functions. SIAM Journal on Computing, 22 0 (4): 0 705--726, 1993

1993
[28]

Smoothed analysis of online and differentially private learning

Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, v...

2020
[29]

Oracle-efficient online learning for beyond worst-case adversaries

Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for beyond worst-case adversaries. In Advances in Neural Information Processing Systems (NeurIPS) 36, 2022 a

2022
[30]

Smoothed analysis with adaptive adversaries

Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022 b

2021
[31]

Jordan, and Eric Zhao

Nika Haghtalab, Michael I. Jordan, and Eric Zhao. A unifying perspective on multi-calibration: Game dynamics for multi-objective learning, 2023

2023
[32]

The computational power of optimization in online learning

Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 128--141, 2016

2016
[33]

Prediction with expert advice by following the perturbed leader for general weights

Marcus Hutter and Jan Poland. Prediction with expert advice by following the perturbed leader for general weights. In International Conference on Algorithmic Learning Theory, pages 279--293. Springer, 2004

2004
[34]

Efficient algorithms for online decision problems

Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71 0 (3): 0 291--307, 2005

2005
[35]

Bandit Algorithms

Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020

2020
[36]

Deep learning

Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 0 (7553): 0 436--444, 2015

2015
[37]

Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm

Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 1988

1988
[38]

Entropy and the combinatorial dimension

Shahar Mendelson and Roman Vershynin. Entropy and the combinatorial dimension. Inventiones mathematicae, 0 (1), 2003

2003
[39]

How to use heuristics for differential privacy

Seth Neel, Aaron Roth, and Zhiwei Steven Wu. How to use heuristics for differential privacy. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 , pages 72--93. IEEE Computer Society, 2019

2019
[40]

Seth Neel, Aaron Roth, Giuseppe Vietri, and Steven Z. Wu. Oracle efficient private non-convex optimization. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event , Proceedings of Machine Learning Research. PMLR , 2020

2020
[41]

The geometry of differential privacy: the sparse and approximate cases

Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013. ACM , 2013

2013
[42]

Online learning: Stochastic and constrained adversaries

Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic and constrained adversaries. arXiv preprint arXiv:1104.5070, 2011

2011 arXiv
[43]

Sequential complexities and uniform martingale laws of large numbers

Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 2015

2015
[44]

Shalev-Shwartz and S

S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge, 2014

2014
[45]

A wavelet tour of signal processing, 1999

Mallat Stephane. A wavelet tour of signal processing, 1999

1999
[46]

Online non-convex learning: Following the perturbed leader is optimal

Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algorithmic Learning Theory, pages 845--861. PMLR, 2020

2020
[47]

Efficient algorithms for adversarial contextual learning

Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning, pages 2159--2168. PMLR, 2016

2016
[48]

Hardness of agnostically learning halfspaces from worst-case lattice problems, 2022

Stefan Tiegel. Hardness of agnostically learning halfspaces from worst-case lattice problems, 2022

2022
[49]

A theory of the learnable

Leslie G Valiant. A theory of the learnable. Communications of the ACM, 0 (11), 1984

1984
[50]

A class of algorithms for pattern recognition learning

Vladimir Vapnik and Alexey Chervonenkis. A class of algorithms for pattern recognition learning. Avtomatika i Telemekhanika, 0 (6), 1964

1964
[51]

High-dimensional probability: An introduction with applications in data science, volume 47

Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

2018
[52]

Foundations of signal processing

Martin Vetterli, Jelena Kova c evi \'c , and Vivek K Goyal. Foundations of signal processing. Cambridge University Press, 2014

2014
[53]

New oracle-efficient algorithms for private synthetic data release

Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Zhiwei Steven Wu. New oracle-efficient algorithms for private synthetic data release. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event , Proceedings of ...

2020
[54]

Adaptive oracle-efficient online learning

Guanghui Wang, Zihao Hu, Vidya Muthukumar, and Jacob D Abernethy. Adaptive oracle-efficient online learning. Advances in Neural Information Processing Systems, 35: 0 23398--23411, 2022

2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, and Ambuj Tewari

Jacob D. Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, and Ambuj Tewari. Online learning via the differential privacy lens. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019

work page 2019

[2] [2]

John M. Abowd. The U.S. census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, page 2867, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355520

work page 2018

[3] [3]

Learning in non-convex games with an optimization oracle

Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Conference on Learning Theory, pages 18--29. PMLR, 2019

work page 2019

[4] [4]

Private PAC learning implies finite littlestone dimension

Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019 , pages 852--860. ACM , 2019

work page 2019

[5] [5]

The multiplicative weights update method: a meta-algorithm and applications

Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 0 (6), 2012

work page 2012

[6] [6]

Bartlett and Shahar Mendelson

Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. In Computational Learning Theory, 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Amsterdam, The Netherlands, July 16-19, 2001, Proceedings , Lectu...

work page 2001

[7] [7]

Fat-shattering and the learnability of real-valued functions

Peter L Bartlett, Philip M Long, and Robert C Williamson. Fat-shattering and the learnability of real-valued functions. In Proceedings of the seventh annual conference on Computational learning theory, 1994

work page 1994

[8] [8]

Limits of private learning with access to public data

Raef Bassily, Shay Moran, and Noga Alon. Limits of private learning with access to public data. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, 2019

work page 2019