Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

The Sample Complexity of Parameter-Free Stochastic Convex Optimization

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 This paper establishes that stochastic convex optimization can match known-parameter sample complexity even when the distance to optimality is unknown, and proves a separation between sample and gradient-oracle complexity.

desk verdict Strong claims, reusable techniques, but the central Theorem 2 proof has a data-dependent-lambda gap that needs a real fix before the perfect-adaptivity result is established. read the letter →

arxiv 2506.11336 v2 pith:R7RJCS2C submitted 2025-06-12 cs.LG math.OC

Jared Lawrence , Ari Kalinsky , Hannah Bradfield , Yair Carmon , Oliver Hinder This is my paper
classification cs.LGmath.OC MSC 90C2590C1568Q32
keywords parameter-freestochasticoptimizationsamplecomplexityconvexmodelselectionregularizedempiricalriskminimizationadaptivityconcentrationinequalities
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

The paper asks what it costs, in samples, to run stochastic convex optimization without knowing the distance from the starting point to the optimum or other problem parameters. It claims the cost can be zero up to constant factors: a two-stage method that first estimates the optimum's distance with norm-regularized empirical risk minimization, then runs a known-parameter optimal method inside the estimated ball, achieves the same $O(LR_\star/\sqrt{n})$ sample complexity as if $R_\star$ were given, for $\ell_1$, $\ell_2$, and $\ell_\infty$ geometries. Since existing lower bounds rule this out for gradient-oracle complexity, the paper's result separates sample complexity from oracle complexity in parameter-free convex optimization. It also develops a reliable model selection procedure that tunes learning rates to near-optimal sample complexity without overfitting small validation sets, and combines the two to adapt simultaneously to all three norms.

What carries the argument

The machinery is the regularized empirical risk minimizer $\hat x_\lambda\in\arg\min_x \bar F(x)+\lambda\|x\|$, a norm-regularized ERM with non-squared regularization. The key lemma shows that, when the empirical gradient error is controlled at the two radii $x^\star_{\lambda/3}$ and $x^\star_{3\lambda}$ (Condition 2), the estimated norm is sandwiched: $\|x^\star_{3\lambda}\|\le 3\|\hat x_\lambda\|\le 33\|x^\star_{\lambda/3}\|$, so the ball of radius $R=3\|\hat x_\lambda\|$ contains a near-optimal point and has radius $O(R_\star)$. New empirical-vector concentration inequalities (Lemma 3) and a dependent-sum lemma (Lemma 4) provide data-dependent choices of $\lambda$ for the Euclidean, $\ell_1$, and $\ell_\infty$ norms, after which any optimal known-ball algorithm such as AdaSGD, entropic mirror descent, or AdaGrad finishes the job.

What would settle it

Run Algorithm 2 on a one-dimensional convex stochastic optimization problem and check whether Condition 2 holds at both $x^\star_{\lambda/3}$ and $x^\star_{3\lambda}$. If the empirical gradient deviations exceed $\lambda/2$ with probability greater than $\delta$ on that instance, the sandwich estimate in Lemma 2 breaks and the claimed $O(LR_\star/\sqrt{n})$ guarantee no longer follows.

Watch

Extended reading notes

Core claim

The central discovery is that unknown distance to optimality does not worsen the sample complexity of stochastic convex optimization. Theorem 2 states that under a known upper bound on the Lipschitz constants, the output of Algorithm 2 satisfies $F(x_{\mathrm{perfect}})-F^\star \le (20\phi_p+3\lambda_p)R_\star$ and $\|x_{\mathrm{perfect}}\|\le 33R_\star$ with probability at least $1-3\delta$. Choosing $\lambda_p$ from the empirical gradient variance and $\phi_p$ from known-ball algorithms gives $O(LR_\star/\sqrt{n})$ suboptimality, the same rate as the known-parameter minimax bound. The paper also shows that standard validation-set model selection can catastrophically overfit when tuning learning rates, while its ReliableModelSelection method gives strong guarantees both with and without strong convexity.

Load-bearing premise

The perfect-adaptivity guarantee relies on computing a supremum over the whole domain of the empirical gradient variance when choosing $\lambda$, and on solving the regularized ERM exactly; with only the paper's practical grid-search fallback the bound picks up a $\log\log$ factor.

Editorial extensions

If this is right

  • If the central claim is right, an optimization method can be sample-optimal without knowing the distance to optimality, so sample efficiency no longer forces a user to guess or grid search that parameter.
  • The two-stage localization step is generic: any algorithm with an optimal guarantee inside a known norm ball can be plugged into stage two without changing the sample complexity.
  • Combined with ReliableModelSelection, the method adapts simultaneously to Euclidean, $\ell_1$, and $\ell_\infty$ geometries, matching the known-parameter lower bounds up to constants.
  • The result sharpens the picture of parameter-free convex optimization: gradient-oracle complexity has a $\log\log$-type adaptivity price, but sample complexity does not.

Reading between the lines

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

  • The exact-constant theorem depends on a supremum over the whole domain for $\lambda$; the paper's own grid-search fallback adds $\log\log$ factors, so a practical implementation will likely need structure or approximations to realize the advertised constant.
  • The reliable model selection algorithm could be tested on other small-validation practice, such as choosing prompts or few-shot checkpoints, whenever a reference model and a bounded per-sample deviation function are available.
  • The dependent-sum concentration lemma may be useful beyond this paper, for example in high-dimensional estimation problems where coordinates are not independent and union bounds are too loose.
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.

Referee Report

3 major / 5 minor

Summary. The paper studies the sample complexity of stochastic convex optimization when problem parameters (notably the distance to optimality) are unknown. It develops two tools: a reliable model selection procedure (Algorithm 1) with high-probability guarantees that avoid overfitting to small validation sets, and a two-stage regularized-ERM localization method (Algorithm 2) that aims to match known-parameter optimal sample complexity up to constant factors for the Euclidean, L1, and L-infinity norms. The central claim, stated as Theorem 2, is that for p in {1,2,∞}, the output of Algorithm 2 with the data-dependent regularizer λ_p from Table 1 satisfies F(x_perfect)-F* ≤ (20φ_p + 3λ_p)R* and ∥x_perfect∥ ≤ 33R* with probability at least 1-3δ, giving what the authors call perfect adaptivity to unknown distance to optimality. Theorem 3 then combines these results with the reliable model selection method to adapt simultaneously to several geometries. The paper also reports few-shot CLIP and prompt-engineering experiments illustrating the practical behavior of ReliableModelSelection.

Significance. If the central claims are correct, the paper makes a valuable contribution: it provides a parameter-free stochastic convex optimization method whose sample complexity matches known-parameter optimal rates up to constant factors, and it identifies a separation between gradient-oracle complexity and sample complexity for this problem class. The reliable model selection analysis (Section 2) is also a useful addition, since it gives strong-convexity-adaptive guarantees for unbounded losses, going beyond earlier bounded-loss analyses. The empirical Bernstein-type vector concentration inequalities in Lemma 3, especially Lemma 3.2b, are interesting and potentially useful independently of the main optimization result. The paper is clearly written and the overall structure of the argument is coherent. However, as detailed below, two load-bearing steps in the proof of the main adaptivity theorem are currently not justified: the concentration argument for data-dependent regularization points, and the final numerical inequality in the proof of Lemma 4.

major comments (3)
  1. [Section 3, Condition 2 and Table 1 (with Lemma 3)] Condition 2 is stated for a known constant λ and for the two deterministic points x*_{λ/3} and x*_{3λ}, but Algorithm 2 and Table 1 set λ = λ_p(data), a function of the same n samples used to form the empirical gradient ∇Fbar and the regularized ERM. The evaluation points x*_{λ/3} and x*_{3λ} therefore also depend on the data. Lemma 3 provides a fixed-x concentration bound: for each deterministic x, the empirical gradient deviation is bounded with probability at least 1-δ. It does not imply the analogous bound at data-dependent points, because the desired event is not contained in the pointwise event for a pre-specified x. The footnote after Lemma 3 explicitly acknowledges that Lemma 12 is for a fixed x, yet the proof of Lemma 2, and hence Theorem 2, requires concentration at the two data-dependent points. No uniform-in-x covering argument or sample splitting is supplied. This is a missing step in the derivation of the paper's central perfect-adaptivity claim, and it is distinct from the practical issue of computing the supremum in Table 1.
  2. [Appendix C.1.3, proof of Lemma 4] The final step of the proof of Lemma 4 claims that the displayed function f(δ) satisfies f(δ) ≤ δ because f is monotone increasing and f(1) ≈ 0.99 < 1. This is logically insufficient: monotonicity and f(1)<1 only give f(δ)<1, not f(δ)≤δ. In fact, direct evaluation at δ=0.5 with the stated constants gives f(0.5) ≈ 0.92 > 0.5. Thus the proof of Lemma 4 does not establish the claimed tail bound. Since Lemma 4 is used to prove Lemma 3.2b, which supplies the p=∞ row of Table 1, the corresponding part of Theorem 2 is not supported by the current proof. This appears repairable by choosing different constants or using a sharper estimate, but as written the argument is incomplete.
  3. [Theorem 3 and Appendix C.4] Theorem 3 states that the algorithm 'samples n functions', but Algorithm 3 takes 3n input functions: n for the three regularized-ERM runs and another n for reliable model selection on f_{2n+1},...,f_{3n}. The statement should be corrected to '3n functions' (or the algorithm should be modified to use n functions total). This does not affect the asymptotic rate, but the current statement is inconsistent with the algorithm.
minor comments (5)
  1. [Assumption 1] The sentence 'where \hat L and \hat L are known' appears to contain a typo: the second \hat L should presumably be \hat L_j (or the vector \hat L), since the coordinate-wise bound is on |∇_j f| ≤ L_j ≤ \hat L_j.
  2. [Section 4, experimental τ_k] The experiments use τ_k = √V_k/(2√n) + M(x_k)/(2n), but the bound derived from Maurer-Pontil in Condition 1 has the form √(2V_k ln(4K/δ)/n) + (14/3) ln(4K/δ) \hat L ∥x_k∥/(n-1). For moderate n and δ, the experimental τ_k is smaller than the guaranteed value, so it is not clear that the experiments satisfy Condition 1. The paper should either state the δ used or justify why the smaller empirical τ_k is covered by the theory.
  3. [Figure 1 and Figure 3] The figure labels contain garbled text such as '/uni00000014/uni00000013/...' in the provided manuscript. The labels should be cleaned up before publication.
  4. [Lemma 4 proof, Equation (23)] The condition is written as 't/w_j · Γ τ ≤ 1/b_j', which appears to mean t/w_j · Γ/τ ≤ 1/b_j. Please fix the typesetting.
  5. [Algorithm 1] The line 'τ0 := 0' is never used; either remove it or explain its role.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bounds are derived from stated concentration and optimization results; same-author lower bounds are used only as external benchmarks.

full rationale

The paper's central derivation (Theorem 2 via Lemma 2, Condition 2, Lemma 3, and Assumption 2) is self-contained: the localization bound is proved directly from the definition of the regularized ERM and from the high-probability gradient-concentration events, and the final suboptimality bound is assembled from those events plus the off-the-shelf constrained-optimization guarantee in Assumption 2. The data-dependent lambda in Table 1 is an empirical-Bernstein-style estimate, not a parameter fitted to the target quantity R*; the proof attempts to verify Condition 2 by Lemma 3, so the result does not reduce to its inputs by construction. The same-author citations [9,10] are used as lower-bound benchmarks and as comparisons for the model-selection method, not as premises that force the upper-bound conclusion; a lower bound is external evidence and does not create circularity. Reviewer-flagged gap: the step from pointwise Lemma 3 to Condition 2 at the data-dependent points x*_{lambda/3} and x*_{3lambda} (Section 3, Lemma 2) is a possible missing uniformity/concentration argument, but a missing proof step is a correctness risk, not circularity. No fitted input is renamed as a prediction, and no ansatz is smuggled in via citation. Score 0.

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

No new physical entities or forces are introduced; the paper introduces algorithms and proofs. The only user-chosen constant is γ in Algorithm 1. The main load-bearing assumptions are the Lipschitz bounds in Assumption 1, the oracle guarantee in Assumption 2, exact ERM solves, and the external lower bounds.

free parameters (1)
  • γ in ReliableModelSelection = 3 in experiments; any γ≥1 in theory
    User-specified constant controlling how conservative the candidate set F is; larger γ behaves more like standard model selection. Not fitted to data but chosen by hand and affects the guarantee's constants.
assumptions (5)
  • domain assumption f is differentiable, convex, and ∥∇f(x;S)∥2 ≤ L ≤ L̂ and |∇_j f(x;S)| ≤ L_j ≤ L̂_j a.s. (Assumption 1)
    Required for the empirical gradient variance bounds and the λ selection in Table 1; without it the concentration inequalities do not apply.
  • domain assumption The stage-2 algorithm A satisfies the high-probability guarantee in Assumption 2 for a known ball radius
    Used to turn the localized ball into a final suboptimality bound; known algorithms (AdaSGD, AdaEMD, AdaGrad) satisfy it.
  • ad hoc to paper The regularized ERM minimizer \x_λ is computed exactly
    Lemma 2 and Theorem 2 assume x\\_hat_λ is an exact minimizer of F̄+λ‖x‖; the paper does not analyze approximate ERM solves, which in practice would perturb the radius R and the guarantees.
  • standard math Standard concentration inequalities (Hoeffding, Bennett, Maurer-Pontil, Howard et al.) are valid
    Used throughout Sections 2 and 3; standard results cited in Appendix A.
  • domain assumption The lower bounds of Carmon and Hinder [10] are correct
    The claimed separation between sample and oracle complexity compares against these lower bounds; they are prior work by the same authors but used as an external benchmark.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Sample Complexity of Parameter-Free Stochastic Convex Optimization." pith.science (2026). https://pith.science/paper/R7RJCS2C

@misc{pith2026250611336,
  author       = {Pith},
  title        = {Pith review of: The Sample Complexity of Parameter-Free Stochastic Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R7RJCS2C}},
  note         = {Machine review of arXiv:2506.11336}
}
read the original abstract

We study the sample complexity of stochastic convex optimization when problem parameters such as the distance to optimality and the Lipschitz constant are unknown. We pursue two strategies. First, we develop a reliable model selection method that avoids overfitting to the validation set. This method allows us to generically tune the learning rate of stochastic optimization methods to match the optimal known-parameter sample complexity up to log log factors. Second, we develop a regularization-based method that is specialized to the case that only the distance to optimality is unknown. More specifically, it uses norm-regularized empirical risk minimization to estimate the distance to optimality to within a constant factor, allowing known-parameter stochastic optimization methods to achieve optimal sample complexity. This method provides perfect adaptability to unknown distance to optimality, demonstrating a separation between the sample and computational complexity of parameter-free stochastic convex optimization. Combining these two methods allows us to simultaneously adapt to multiple problem structures. Experiments performing few-shot learning on CIFAR-10 by fine-tuning CLIP models and prompt engineering Gemini to count shapes indicate that our reliable model selection method can help mitigate overfitting to small validation sets.

Figures

Figures reproduced from arXiv: 2506.11336 by the authors.

Figure 1
Figure 1. Left: CLIP model fine-tuning of the last layer for ViT-L/14 starting from the zero-shot weights on CIFAR10. Right: Prompt engineering a large language model, gemini-1.5-flash-002, on the task of counting the number of shapes in images. Both experiments are based on 200 runs, each of which resamples the training and validation set. Shaded regions represents one standard error. section provides an overview of them, co… view at source ↗
Figure 2
Figure 2. Additional plots for the CLIP experiments. The percentiles are over the runs. For [PITH_FULL_IMAGE:figures/full_fig_p036_2.png] view at source ↗
Figure 3
Figure 3. Additional plot for the prompt engineering experiments. The percentiles are over [PITH_FULL_IMAGE:figures/full_fig_p037_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: A sample of images, generated by the outlined process, that were presented to [PITH_FULL_IMAGE:figures/full_fig_p038_4.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Clipping the Price of Adaptivity at the Tail

    cs.LG 2026-06 unverdicted novelty 7.0 of 10

    Under a model-loss decomposition, clipping model outputs in tail events yields adaptive SCO bounds matching known-parameter optima up to logarithmic factors in uncertainty.

Reference graph

Works this paper leans on

59 extracted references · 51 canonical work pages · cited by 1 Pith paper

  1. [1]

    Information-theoretic lower bounds on the oracle complexity of stochastic convex opti- mization

    Alekh Agarwal, Peter L Bartlett, Pradeep Ravikumar, and Martin J Wainwright. Information-theoretic lower bounds on the oracle complexity of stochastic convex opti- mization. IEEE Transactions on Information Theory , 58(5):3235–3249, 2012

    work page 2012

  2. [2]

    Characterizing subdifferential of norm, 2023

    Andersen Ang. Characterizing subdifferential of norm, 2023. URL https://angms. science/doc/CVX/SubdifferentialOfNorm.pdf. Accessed: 2025-02-02

    work page 2023

  3. [3]

    How free is parameter-free stochastic optimization? In International Conference on Machine Learning (ICML) , 2024

    Amit Attia and Tomer Koren. How free is parameter-free stochastic optimization? In International Conference on Machine Learning (ICML) , 2024

    work page 2024

  4. [4]

    Mirror descent and nonlinear projected subgradient methods for convex optimization

    Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167–175, 2003. 20

    work page 2003

  5. [5]

    Probability inequalities for the sum of independent random variables

    George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association , 57(297):33–45, 1962

    work page 1962

  6. [6]

    The ladder: A reliable leaderboard for machine learn- ing competitions

    Avrim Blum and Moritz Hardt. The ladder: A reliable leaderboard for machine learn- ing competitions. In International Conference on Machine Learning , pages 1006–1014. PMLR, 2015

    work page 2015

  7. [7]

    Sharper bounds for uni- formly stable algorithms

    Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uni- formly stable algorithms. In Conference on Learning Theory , pages 610–626. PMLR, 2020

    work page 2020

  8. [8]

    Olshen, and Charles J

    Leo Breiman, Jerome Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Chapman and Hall, New York, 1984

    work page 1984

Show all 59 references
  1. [9]

    Making SGD parameter-free

    Yair Carmon and Oliver Hinder. Making SGD parameter-free. In Conference on Learn- ing Theory (COLT), 2022

    2022

  2. [10]

    The price of adaptivity in stochastic convex optimiza- tion

    Yair Carmon and Oliver Hinder. The price of adaptivity in stochastic convex optimiza- tion. arXiv:2402.10898, 2024

    2024 arXiv

  3. [11]

    Better parameter-free stochastic optimization with ODE updates for coin-betting

    Keyi Chen, John Langford, and Francesco Orabona. Better parameter-free stochastic optimization with ODE updates for coin-betting. In AAAI Conference on Artificial Intelligence, 2022

    2022

  4. [12]

    Artificial constraints and hints for unbounded online learning

    Ashok Cutkosky. Artificial constraints and hints for unbounded online learning. In Conference on Learning Theory (COLT), 2019

    2019

  5. [13]

    Black-box reductions for parameter-free online learning in banach spaces

    Ashok Cutkosky and Francesco Orabona. Black-box reductions for parameter-free online learning in banach spaces. In Conference On Learning Theory, pages 1493–1529. PMLR, 2018

    2018

  6. [14]

    Learning-rate-free learning by D- adaptation

    Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by D- adaptation. In International Conference on Machine Learning (ICML) , 2023

    2023

  7. [15]

    An image is worth 16x16 words: Trans- formers for image recognition at scale

    Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Syl- vain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Trans- formers for image recognitio...

    2021

  8. [16]

    Adaptive subgradient methods for online learning and stochastic optimization

    John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research , 12(7), 2011

    2011

  9. [17]

    Data filtering networks

    Alex Fang, Albin Madappally Jose, Amit Jain, Ludwig Schmidt, Alexander T Toshev, and Vaishaal Shankar. Data filtering networks. In The Twelfth International Confer- ence on Learning Representations , 2024. URL https://openreview.net/forum?id= KAk6ngZ09F. 21

    2024

  10. [18]

    A unified approach to adaptive regu- larization in online and stochastic optimization

    Vineet Gupta, Tomer Koren, and Yoram Singer. A unified approach to adaptive regu- larization in online and stochastic optimization. arXiv:1706.06569, 2017

    2017 arXiv

  11. [19]

    The Elements of Statistical Learning: Data Mining, Inference, and Prediction

    Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction . Springer, New York, 2nd edition, 2009

    2009

  12. [20]

    Beyond the regret minimization barrier: optimal al- gorithms for stochastic strongly-convex optimization

    Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal al- gorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(1):2489–2512, 2014

    2014

  13. [21]

    Probability inequalities for sums of bounded random variables

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Jour- nal of the American Statistical Association , 58(301):13–30, 1963

    1963

  14. [22]

    Time-uniform chernoff bounds via nonnegative supermartingales

    Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform chernoff bounds via nonnegative supermartingales. Probability Surveys , 17:257–317, 2020

    2020

  15. [23]

    Pushing the limits of simple pipelines for few-shot learning: External data and fine-tuning make a difference

    Shell Xu Hu, Da Li, Jan St¨ uhmer, Minyoung Kim, and Timothy M Hospedales. Pushing the limits of simple pipelines for few-shot learning: External data and fine-tuning make a difference. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages...

    2022

  16. [24]

    J. D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science & Engi- neering, 9(3):90–95, 2007. doi: 10.1109/MCSE.2007.55

    2007 doi

  17. [25]

    Openclip, July 2021

    Gabriel Ilharco, Mitchell Wortsman, Ross Wightman, Cade Gordon, Nicholas Car- lini, Rohan Taori, Achal Dave, Vaishaal Shankar, Hongseok Namkoong, John Miller, Hannaneh Hajishirzi, Ali Farhadi, and Ludwig Schmidt. Openclip, July 2021. URL https://doi.org/10.5281/zenodo.5143773....

    2021 doi

  18. [26]

    DoG is SGD’s best friend: A parameter-free dynamic step size schedule

    Maor Ivgi, Oliver Hinder, and Yair Carmon. DoG is SGD’s best friend: A parameter-free dynamic step size schedule. In International Conference on Machine Learning (ICML) , 2023

    2023

  19. [27]

    Scaling laws for neural language models

    Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv:2001.08361, 2020

    2001 arXiv

  20. [28]

    Algorithmic stability and sanity-check bounds for leave- one-out cross-validation

    Michael Kearns and Dana Ron. Algorithmic stability and sanity-check bounds for leave- one-out cross-validation. In Proceedings of the tenth annual conference on Computa- tional learning theory , pages 152–162, 1997

    1997

  21. [29]

    Adaptive scale- invariant online algorithms for learning linear models

    Michal Kempka, Wojciech Kotlowski, and Manfred K Warmuth. Adaptive scale- invariant online algorithms for learning linear models. In International Conference on Machine Learning (ICML) , 2019. 22

    2019

  22. [30]

    Tuning-free stochastic optimization

    Ahmed Khaled and Chi Jin. Tuning-free stochastic optimization. In International Conference on Machine Learning (ICML) , 2024

    2024

  23. [31]

    On the upper bound for the absolute constant in the berry–esseen inequality

    V Yu Korolev and Irina G Shevtsova. On the upper bound for the absolute constant in the berry–esseen inequality. Theory of Probability & Its Applications , 54(4):638–658, 2010

    2010

  24. [32]

    Accelerated parameter-free stochastic optimization

    Itai Kreisler, Maor Ivgi, Oliver Hinder, and Yair Carmon. Accelerated parameter-free stochastic optimization. In The Thirty Seventh Annual Conference on Learning Theory, pages 3257–3324. PMLR, 2024

    2024

  25. [33]

    Learning multiple layers of features from tiny images

    Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009

    2009

  26. [34]

    Necessary and sufficient geometries for gradient meth- ods

    Daniel Levy and John C Duchi. Necessary and sufficient geometries for gradient meth- ods. Advances in Neural Information Processing Systems (NeurIPS) , 2019

    2019

  27. [35]

    Martingale methods for sequential estimation of convex functionals and divergences

    Tudor Manole and Aaditya Ramdas. Martingale methods for sequential estimation of convex functionals and divergences. IEEE Transactions on Information Theory , 69(7): 4641–4658, 2023

    2023

  28. [36]

    Empirical Bernstein bounds and sample variance penalization

    Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penalization. Conference on Learning Theory (COLT), 2009

    2009

  29. [37]

    pandas: a foundational python library for data analysis and statistics

    Wes McKinney et al. pandas: a foundational python library for data analysis and statistics. Python for high performance and scientific computing , 14(9):1–9, 2011

    2011

  30. [38]

    Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations

    H Brendan McMahan and Francesco Orabona. Unconstrained online linear learning in Hilbert spaces: Minimax algorithms and normal approximations. In Conference on Learning Theory (COLT), 2014

    2014

  31. [39]

    Adaptive bound optimization for online convex optimization

    H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. Conference on Learning Theory (COLT), 2010

    2010

  32. [40]

    The effect of natural distribution shift on question answering models

    John Miller, Karl Krauth, Benjamin Recht, and Ludwig Schmidt. The effect of natural distribution shift on question answering models. In International conference on machine learning, pages 6905–6916. PMLR, 2020

    2020

  33. [41]

    Proximity and duality in a hilbertian space

    Jean-Jacques Moreau. Proximity and duality in a hilbertian space. Bulletin of the Mathematical Society of France, 93:273–299, 1965

    1965

  34. [42]

    word2number, 2014

    Akshay Nagpal. word2number, 2014. URL https://github.com/akshaynagpal/w2n

    2014

  35. [43]

    Problem complexity and method efficiency in optimization

    Arkadi Nemirovski and David Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, New York, 1983

    1983

  36. [44]

    A modern introduction to online learning

    Francesco Orabona. A modern introduction to online learning. arXiv:1912.13213v7, 2019. 23

    1912 arXiv

  37. [45]

    Training deep networks without learning rates through coin betting

    Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting. In Advances in Neural Information Processing Systems (NeurIPS), 2017

    2017

  38. [46]

    Py- Torch: An imperative style, high-performance deep learning library

    Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmai- son, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, L...

    2019

  39. [47]

    Learning transferable visual models from natural language supervision

    Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sand- hini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In International C...

    2021

  40. [48]

    Do imagenet classifiers generalize to imagenet? In International conference on machine learning , pages 5389–5400

    Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International conference on machine learning , pages 5389–5400. PMLR, 2019

    2019

  41. [49]

    A meta-analysis of overfitting in machine learning

    Rebecca Roelofs, Vaishaal Shankar, Benjamin Recht, Sara Fridovich-Keil, Moritz Hardt, John Miller, and Ludwig Schmidt. A meta-analysis of overfitting in machine learning. Advances in neural information processing systems , 32, 2019

    2019

  42. [50]

    Gemini 1.5: Unlock- ing multimodal understanding across millions of tokens of context

    Gemini Team, Petko Georgiev, Ving Ian Lei, Ryan Burnell, Libin Bai, Anmol Gulati, Garrett Tanzer, Damien Vincent, Zhufeng Pan, Shibo Wang, et al. Gemini 1.5: Unlock- ing multimodal understanding across millions of tokens of context. arXiv:2403.05530, 2024

    2024 arXiv

  43. [51]

    An overview of statistical learning theory

    Vladimir N Vapnik. An overview of statistical learning theory. IEEE transactions on neural networks, 10(5):988–999, 1999

    1999

  44. [52]

    Welcome to the tidyverse

    Hadley Wickham, Mara Averick, Jennifer Bryan, Winston Chang, Lucy D’Agostino McGowan, Romain Fran¸ cois, Garrett Grolemund, Alex Hayes, Lionel Henry, Jim Hester, Max Kuhn, Thomas Lin Pedersen, Evan Miller, Stephan Milton Bache, Kirill M¨ uller, Jeroen Ooms, David Robinson, Dan...

    2019 doi

  45. [53]

    Cold case: The lost MNIST digits.Advances in neural information processing systems, 32, 2019

    Chhavi Yadav and L´ eon Bottou. Cold case: The lost MNIST digits.Advances in neural information processing systems, 32, 2019. A Well-known results Theorem 4 (Hoeffding’s inequality [21]) . Let Z, Z1, ..., Zn be i.i.d. random variables with values in [a, b] and let δ >0. Then w...

    2019

  46. [54]

    [22] withYt = 1 n Pt i=1(Vi −ν), ct = H/n, Ψ(·) = ∥·∥ 2, D = 1, m = H 2/n, x = p (m/2) ln 2/δ, we get that with probability 1 − δ that ∥ ¯V − ν∥2 ≤ H r 2 ln(2/δ) n

    (31) Then by Corollary 10a of Howard et al. [22] withYt = 1 n Pt i=1(Vi −ν), ct = H/n, Ψ(·) = ∥·∥ 2, D = 1, m = H 2/n, x = p (m/2) ln 2/δ, we get that with probability 1 − δ that ∥ ¯V − ν∥2 ≤ H r 2 ln(2/δ) n . (32) Combining Equation (32) and Equation (31) gives nX i=1 ∥Vi − ν...

  47. [55]

    Remove all asterisks ( *) left as formatting artifacts

  48. [56]

    37 Figure 4: A sample of images, generated by the outlined process, that were presented to Gemini showcasing all 15 backgrounds

    Return the last token directly if it is purely numeric. 37 Figure 4: A sample of images, generated by the outlined process, that were presented to Gemini showcasing all 15 backgrounds

  49. [57]

    } and within square brackets [

    Isolate content within braces { . . . } and within square brackets [ . . . ], returning 0 if a hyphenated range is detected

  50. [58]

    The first successful conversion is returned, or 0 otherwise

    Perform a reverse search through each remaining word (what we have isolated in the previous step, or the entire output if an isolation was not made), first checking for numeric types and then attempting to extract numbers in word form. The first successful conversion is return...

  51. [59]

    3 circles, 2 squares, 1 star

    Clip all extracted values outside the range [0, 12] to the nearest endpoint. This numerical extraction is compared to the true number of shapes in each image to deter- mine error, in this case absolute error. 38 Table 2: Prompts ordered by performance on all 5 , 000 examples. ...

Pith tools

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