<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (cshalizi)</title>
    <link>https://pinboard.in/u:cshalizi/public/</link>
    <description>recent bookmarks from cshalizi</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://arxiv.org/abs/2606.13280"/>
	<rdf:li rdf:resource="https://doi.org/10.1108/FTCIT-09-2025-0149"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2604.19560"/>
	<rdf:li rdf:resource="https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-19/issue-2/On-the-rate-of-convergence-of-an-over-parametrized-deep/10.1214/25-EJS2444.full"/>
	<rdf:li rdf:resource="https://link.springer.com/article/10.1007/s11203-025-09329-6"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2505.00110"/>
	<rdf:li rdf:resource="https://link.springer.com/article/10.1007/s10472-009-9148-3"/>
	<rdf:li rdf:resource="https://openreview.net/forum?id=O0Lz8XZT2b"/>
	<rdf:li rdf:resource="https://philsci-archive.pitt.edu/24910/"/>
	<rdf:li rdf:resource="https://www.nowpublishers.com/article/Details/MAL-112"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2503.02113"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2502.20375"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2411.00247"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2412.07684"/>
	<rdf:li rdf:resource="https://www.di.ens.fr/~fbach/ltfp_book.pdf"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2410.10101"/>
	<rdf:li rdf:resource="https://www.jmlr.org/papers/v16/gammerman15b.html"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2411.00109"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2304.06670"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2407.20199"/>
	<rdf:li rdf:resource="https://openreview.net/forum?id=ux9BrxPCl8"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2401.14483"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2310.20360"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2202.06915"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2404.03774"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2404.06757"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2405.18055v1"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2402.14987"/>
	<rdf:li rdf:resource="https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-2/Minimax-rates-for-conditional-density-estimation-via-empirical-entropy/10.1214/23-AOS2270.short"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2110.11216"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2402.13285"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2402.01502"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2311.07013"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2109.02224"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2309.13786"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2305.18887"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2311.03910"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2309.17016"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2305.11042"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1202.3699"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2007.13982"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2210.03458"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2202.09889"/>
	<rdf:li rdf:resource="https://notstatschat.rbind.io/2022/09/28/uniform-law-of-large-numbers/"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2305.17592"/>
	<rdf:li rdf:resource="https://ieeexplore.ieee.org/document/21929"/>
	<rdf:li rdf:resource="https://dl.acm.org/doi/abs/10.5555/93025.93105"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2305.00322"/>
	<rdf:li rdf:resource="https://proceedings.mlr.press/v206/bosch23a"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2107.04562"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2303.05369"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2302.06005"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2302.07263"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2212.13556"/>
	<rdf:li rdf:resource="https://hdsr.mitpress.mit.edu/pub/qixx99zn/release/1"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2105.12806"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2202.04985"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2204.01119"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2112.03626"/>
	<rdf:li rdf:resource="https://jmlr.org/papers/v23/20-644.html"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2202.04415"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2206.03515"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2205.01593"/>
	<rdf:li rdf:resource="https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.4.013201"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2103.14108"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2204.02909v1"/>
	<rdf:li rdf:resource="https://www.jmlr.org/papers/v23/20-644.html"/>
	<rdf:li rdf:resource="https://direct.mit.edu/rest/article-abstract/101/5/743/58556/Choosing-among-Regularized-Estimators-in-Empirical?redirectedFrom=fulltext"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2201.10408"/>
	<rdf:li rdf:resource="https://ieeexplore.ieee.org/abstract/document/9724643"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://arxiv.org/abs/2606.13280">
    <title>[2606.13280] Generalization Bounds for Transformer-Based Next-Token Prediction in a Language Model</title>
    <dc:date>2026-06-17T16:26:17+00:00</dc:date>
    <link>https://arxiv.org/abs/2606.13280</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A refined statistical understanding of LLM pre-training requires the analysis of the transformer architecture for data distributions that encapsulate key characteristics of text data. To address this, we propose a text data distribution based on an extension of the log-bilinear language model from the natural language processing literature. For this data generating process, we derive generalization bounds for deep transformer architectures, highlighting the dependence on the network architecture, the vocabulary size, the number of documents and the document length."]]></description>
<dc:subject>to:NB to_read learning_theory natural_language_processing large_language_models_(so_called) via:mraginsky</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:87e01de8c417/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:natural_language_processing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:large_language_models_(so_called)"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://doi.org/10.1108/FTCIT-09-2025-0149">
    <title>Volume 23 Issue 3-4 | Foundations and Trends in Communications and Information Theory | Emerald Publishing</title>
    <dc:date>2026-05-19T15:46:33+00:00</dc:date>
    <link>https://doi.org/10.1108/FTCIT-09-2025-0149</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Online learning is a foundational paradigm underlying applications from recommendation systems to the continual learning of modern AI models. Yet much of its theory centers on either fully adversarial or purely stochastic settings. However, real-world environments typically fall between these extremes, making classical models inadequate for describing practical behavior. This monograph develops a unified perspective for analyzing online learning under more nuanced and realistic environments. The authors approach the problem through the lens of universality from information theory and extend tools such as the Shtarkov sum, covering numbers and packing arguments to the online setting, revealing deeper structural connections between these two fields. Building on this viewpoint, they characterize minimax regret for logarithmic and Lipschitz losses, analyze expected regret under i.i.d. and more general stochastic processes and study hybrid adversarial–stochastic scenarios. The authors further develop constructive algorithms that achieve near-optimal regret guarantees, yielding a coherent and fine-grained information-theoretic framework of online universal learning."]]></description>
<dc:subject>to_read information_theory learning_theory learning_under_dependence in_NB low-regret_learning online_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:eb2f88390f74/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_under_dependence"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2604.19560">
    <title>[2604.19560] Separating Geometry from Probability in the Analysis of Generalization</title>
    <dc:date>2026-04-22T20:22:34+00:00</dc:date>
    <link>https://arxiv.org/abs/2604.19560</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The goal of machine learning is to find models that minimize prediction error on data that has not yet been seen. Its operational paradigm assumes access to a dataset S and articulates a scheme for evaluating how well a given model performs on an arbitrary sample. The sample can be S (in which case we speak of ``in-sample'' performance) or some entirely new S′ (in which case we speak of ``out-of-sample'' performance). Traditional analysis of generalization assumes that both in- and out-of-sample data are i.i.d.\ draws from an infinite population. However, these probabilistic assumptions cannot be verified even in principle. This paper presents an alternative view of generalization through the lens of sensitivity analysis of solutions of optimization problems to perturbations in the problem data. Under this framework, generalization bounds are obtained by purely deterministic means and take the form of variational principles that relate in-sample and out-of-sample evaluations through an error term that quantifies how close out-of-sample data are to in-sample data. Statistical assumptions can then be used \textit{ex post} to characterize the situations when this error term is small (either on average or with high probability)."]]></description>
<dc:subject>to:NB to_read recht.benjamin raginsky.maxim learning_theory optimization via:mraginsky to_teach:childs_garden_of_statistical_learning_theory straight_into_my_veins interpolation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:963cc7aaa897/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:recht.benjamin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:raginsky.maxim"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:straight_into_my_veins"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interpolation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-19/issue-2/On-the-rate-of-convergence-of-an-over-parametrized-deep/10.1214/25-EJS2444.full">
    <title>On the rate of convergence of an over-parametrized deep neural network regression estimate with ReLU activation function learned by gradient descent</title>
    <dc:date>2025-10-24T19:40:42+00:00</dc:date>
    <link>https://projecteuclid.org/journals/electronic-journal-of-statistics/volume-19/issue-2/On-the-rate-of-convergence-of-an-over-parametrized-deep/10.1214/25-EJS2444.full</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Estimation of a regression function from independent and identically distributed random variables is considered. The $L_2$ error with integration with respect to the design measure is used as an error criterion. Over-parametrized deep neural network estimates with ReLU activation function are defined where all the weights are learned by the gradient descent. It is shown that the expected $L_2$ error of the estimates converges to zero with rate
\[
n^{-\frac{p}{2p+d}
\]
(up to some logarithmic factor) in case that the regression function is p-times continuously differentiable. In case that the regression function satisfies the assumption of a p times continuously differentiable interaction model, i.e., in case that it is equal to a finite sum of functions where each function in the sum is a p-times continuously differentiable function applied to only $d^*$ of the d components of its input, we show that our estimate achieves the above rate of convergence with d replaced by $d^*$. The finite sample performance of the proposed estimate has been illustrated by simulations."]]></description>
<dc:subject>to:NB regression neural_networks learning_theory nonparametrics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:deab690bc7f0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://link.springer.com/article/10.1007/s11203-025-09329-6">
    <title>Statistical learning for $$psi $$ -weakly dependent processes | Statistical Inference for Stochastic Processes</title>
    <dc:date>2025-09-03T14:22:34+00:00</dc:date>
    <link>https://link.springer.com/article/10.1007/s11203-025-09329-6</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The purpose of this paper is to study the generalization performance of the Empirical Risk Minimization (ERM) algorithm from $\psi$-weakly dependent processes. These processes unify a large class of weak dependence conditions, including strong mixing and association. We first establish the exponential bound on the rate of relative uniform convergence and the consistency of the ERM algorithm. Secondly, we derive generalization bounds and provide the learning rate. Under some Hölder class of hypothesis, we obtain an asymptotic rate close to $O(n^{-1/2})$. Finally, we present some application and simulation results with examples of causal models within the context of time series prediction."]]></description>
<dc:subject>to:NB learning_theory mixing time_series</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:47b97e670aaa/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2505.00110">
    <title>[2505.00110] On the expressivity of deep Heaviside networks</title>
    <dc:date>2025-08-07T14:56:37+00:00</dc:date>
    <link>https://arxiv.org/abs/2505.00110</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We show that deep Heaviside networks (DHNs) have limited expressiveness but that this can be overcome by including either skip connections or neurons with linear activation. We provide lower and upper bounds for the Vapnik-Chervonenkis (VC) dimensions and approximation rates of these network classes. As an application, we derive statistical convergence rates for DHN fits in the nonparametric regression model."]]></description>
<dc:subject>to:NB neural_networks learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ed098f79a41e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://link.springer.com/article/10.1007/s10472-009-9148-3">
    <title>On the Vapnik-Chervonenkis dimension of computer programs which use transcendental elementary operations | Annals of Mathematics and Artificial Intelligence</title>
    <dc:date>2025-04-23T14:38:17+00:00</dc:date>
    <link>https://link.springer.com/article/10.1007/s10472-009-9148-3</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We exhibit upper bounds for the Vapnik-Chervonenkis (VC) dimension of a wide family of concept classes that are defined by algorithms using analytic Pfaffian functions. We give upper bounds on the VC dimension of concept classes in which the membership test for whether an input belongs to a concept in the class can be performed either by a computation tree or by a circuit with sign gates containing Pfaffian functions as operators. These new bounds are polynomial both in the height of the tree and in the depth of the circuit. As consequence we obtain polynomial VC dimension not also for classes of concepts whose membership test can be defined by polynomial time algorithms but also for those defined by well-parallelizable sequential exponential time algorithms."]]></description>
<dc:subject>to:NB learning_theory computational_complexity via:mraginsky</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:eeec04e7e149/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:computational_complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://openreview.net/forum?id=O0Lz8XZT2b">
    <title>A U-turn on Double Descent: Rethinking Parameter Counting in Statistical Learning | OpenReview</title>
    <dc:date>2025-04-01T20:46:09+00:00</dc:date>
    <link>https://openreview.net/forum?id=O0Lz8XZT2b</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Conventional statistical wisdom established a well-understood relationship between model complexity and prediction error, typically presented as a U-shaped curve reflecting a transition between under- and overfitting regimes. However, motivated by the success of overparametrized neural networks, recent influential work has suggested this theory to be generally incomplete, introducing an additional regime that exhibits a second descent in test error as the parameter count $p$ grows past sample size $n$ -- a phenomenon dubbed double descent. While most attention has naturally been given to the deep-learning setting, double descent was shown to emerge more generally across non-neural models: known cases include linear regression, trees, and boosting. In this work, we take a closer look at the evidence surrounding these more classical statistical machine learning methods and challenge the claim that observed cases of double descent truly extend the limits of a traditional U-shaped complexity-generalization curve therein. We show that once careful consideration is given to what is being plotted on the x-axes of their double descent plots, it becomes apparent that there are implicitly multiple, distinct complexity axes along which the parameter count grows. We demonstrate that the second descent appears exactly (and only) when and where the transition between these underlying axes occurs, and that its location is thus not inherently tied to the interpolation threshold $p=n$. We then gain further insight by adopting a classical nonparametric statistics perspective. We interpret the investigated methods as smoothers and propose a generalized measure for the effective number of parameters they use on unseen examples, using which we find that their apparent double descent curves do indeed fold back into more traditional convex shapes -- providing a resolution to the ostensible tension between double descent and traditional statistical intuition."

--- I'd toyed with the idea of doing something like this, but couldn't begin to figure out an actual concrete approach, so I'm really excited to read this.
--- ETA after reading the main paper but not the appendices: this is awesome.
--- ETA after reading the appendices: still awesome; this will change what I teach.]]></description>
<dc:subject>learning_theory regression interpolation_aka_memorizing_the_training_data to_teach:childs_garden_of_statistical_learning_theory via:rvenkat in_NB have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5c9e184baef1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interpolation_aka_memorizing_the_training_data"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:rvenkat"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://philsci-archive.pitt.edu/24910/">
    <title>The Uses and Limitations of Occam Algorithms: a response to Herrmann - PhilSci-Archive</title>
    <dc:date>2025-03-26T15:22:08+00:00</dc:date>
    <link>https://philsci-archive.pitt.edu/24910/</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In a recent paper, Daniel Herrman uses probably approximately correct (PAC) learning theory to argue that Occam algorithms do not justify a preference for simpler hypotheses. He claims to derive equally efficient "Anti-Occam" algorithms favouring the most complex hypotheses. We argue that Herrmann's analysis omits key elements of Occam algorithms, which eliminate the possibility of "Anti-Occam" algorithms and counter many of his arguments. These elements clarify the intrinsic connection of Occam algorithms to theories of learnability. Occam algorithms are not a failed epistemic justification of Occam's razor but rather a pragmatic base for practical algorithms"

--- If people are having this sort of argument, maybe I _should_ have turned [http://bactra.org/notebooks/occam-bounds-for-long-programs.html] into a paper (or at least put it on arxiv).]]></description>
<dc:subject>learning_theory occams_razor have_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:518cdda4fc1c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:occams_razor"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.nowpublishers.com/article/Details/MAL-112">
    <title>now publishers - Generalization Bounds: Perspectives from Information Theory and PAC-Bayes</title>
    <dc:date>2025-03-20T13:04:53+00:00</dc:date>
    <link>https://www.nowpublishers.com/article/Details/MAL-112</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A fundamental question in theoretical machine learning is generalization. Over the past decades, the PAC-Bayesian approach has been established as a flexible framework to address the generalization capabilities of machine learning algorithms and design new ones. Recently, it has garnered increased interest due to its potential applicability for a variety of learning algorithms, including deep neural networks. In parallel, an information-theoretic view of generalization has developed, wherein the relation between generalization and various information measures has been established. This framework is intimately connected to the PAC-Bayesian approach, and a number of results have been independently discovered in both strands.
"In this monograph, we highlight this strong connection and present a unified treatment of PAC-Bayesian and information- theoretic generalization bounds. We present techniques and results that the two perspectives have in common, and discuss the approaches and interpretations that differ. In particular, we demonstrate how many proofs in the area share a modular structure, through which the underlying ideas can be intuited. We pay special attention to the conditional mutual information (CMI) framework, analytical studies of the information complexity of learning algorithms, and the application of the proposed methods to deep learning. This monograph is intended to provide a comprehensive introduction to information-theoretic generalization bounds and their connection to PAC-Bayes, serving as a foundation from which the most recent developments are accessible. It is aimed broadly towards researchers with an interest in generalization and theoretical machine learning."]]></description>
<dc:subject>to:NB downloaded books:noted to_read learning_theory information_theory raginsky.maxim to_teach:childs_garden_of_statistical_learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:72659330abf1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:downloaded"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:raginsky.maxim"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2503.02113">
    <title>[2503.02113] Deep Learning is Not So Mysterious or Different</title>
    <dc:date>2025-03-16T19:30:19+00:00</dc:date>
    <link>https://arxiv.org/abs/2503.02113</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Deep neural networks are often seen as different from other model classes by defying conventional notions of generalization. Popular examples of anomalous generalization behaviour include benign overfitting, double descent, and the success of overparametrization. We argue that these phenomena are not distinct to neural networks, or particularly mysterious. Moreover, this generalization behaviour can be intuitively understood, and rigorously characterized using long-standing generalization frameworks such as PAC-Bayes and countable hypothesis bounds. We present soft inductive biases as a key unifying principle in explaining these phenomena: rather than restricting the hypothesis space to avoid overfitting, embrace a flexible hypothesis space, with a soft preference for simpler solutions that are consistent with the data. This principle can be encoded in many model classes, and thus deep learning is not as mysterious or different from other model classes as it might seem. However, we also highlight how deep learning is relatively distinct in other ways, such as its ability for representation learning, phenomena such as mode connectivity, and its relative universality."

--- Curious to see how "soft inductive bias" is not just a penalty or sieve.  (to_teach tag is very tentative.)]]></description>
<dc:subject>to:NB to_read neural_networks learning_theory to_teach:childs_garden_of_statistical_learning_theory to_teach:statistics_and_generative_ai</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7dc2f4d6c2dd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:statistics_and_generative_ai"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2502.20375">
    <title>[2502.20375] When does a predictor know its own loss?</title>
    <dc:date>2025-03-01T16:42:13+00:00</dc:date>
    <link>https://arxiv.org/abs/2502.20375</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Given a predictor and a loss function, how well can we predict the loss that the predictor will incur on an input? This is the problem of loss prediction, a key computational task associated with uncertainty estimation for a predictor. In a classification setting, a predictor will typically predict a distribution over labels and hence have its own estimate of the loss that it will incur, given by the entropy of the predicted distribution. Should we trust this estimate? In other words, when does the predictor know what it knows and what it does not know?
"In this work we study the theoretical foundations of loss prediction. Our main contribution is to establish tight connections between nontrivial loss prediction and certain forms of multicalibration, a multigroup fairness notion that asks for calibrated predictions across computationally identifiable subgroups. Formally, we show that a loss predictor that is able to improve on the self-estimate of a predictor yields a witness to a failure of multicalibration, and vice versa. This has the implication that nontrivial loss prediction is in effect no easier or harder than auditing for multicalibration. We support our theoretical results with experiments that show a robust positive correlation between the multicalibration error of a predictor and the efficacy of training a loss predictor."]]></description>
<dc:subject>to:NB prediction learning_theory via:mraginsky</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f05f155b04ee/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2411.00247">
    <title>[2411.00247] Deep Learning Through A Telescoping Lens: A Simple Model Provides Empirical Insights On Grokking, Gradient Boosting &amp; Beyond</title>
    <dc:date>2025-01-22T15:36:23+00:00</dc:date>
    <link>https://arxiv.org/abs/2411.00247</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Deep learning sometimes appears to work in unexpected ways. In pursuit of a deeper understanding of its surprising behaviors, we investigate the utility of a simple yet accurate model of a trained neural network consisting of a sequence of first-order approximations telescoping out into a single empirically operational tool for practical analysis. Across three case studies, we illustrate how it can be applied to derive new empirical insights on a diverse range of prominent phenomena in the literature -- including double descent, grokking, linear mode connectivity, and the challenges of applying deep learning on tabular data -- highlighting that this model allows us to construct and extract metrics that help predict and understand the a priori unexpected performance of neural networks. We also demonstrate that this model presents a pedagogical formalism allowing us to isolate components of the training process even in complex contemporary settings, providing a lens to reason about the effects of design choices such as architecture & optimization strategy, and reveals surprising parallels between neural network learning and gradient boosting."]]></description>
<dc:subject>to:NB neural_networks learning_theory statistics to_read via:mraginsky to_teach:statistics_and_generative_ai</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b500158ab0cc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:statistics_and_generative_ai"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2412.07684">
    <title>[2412.07684] The Pitfalls of Memorization: When Memorization Hurts Generalization</title>
    <dc:date>2025-01-01T15:54:07+00:00</dc:date>
    <link>https://arxiv.org/abs/2412.07684</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Neural networks often learn simple explanations that fit the majority of the data while memorizing exceptions that deviate from these this http URL behavior leads to poor generalization when the learned explanations rely on spurious correlations. In this work, we formalize the interplay between memorization and generalization, showing that spurious correlations would particularly lead to poor generalization when are combined with memorization. Memorization can reduce training loss to zero, leaving no incentive to learn robust, generalizable patterns. To address this, we propose memorization-aware training (MAT), which uses held-out predictions as a signal of memorization to shift a model's logits. MAT encourages learning robust patterns invariant across distributions, improving generalization under distribution shifts."]]></description>
<dc:subject>in_NB learning_theory interpolation_aka_memorizing_the_training_data</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9759291e2c99/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interpolation_aka_memorizing_the_training_data"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.di.ens.fr/~fbach/ltfp_book.pdf">
    <title>Learning Theory from First Principles (Bach, forthcoming [2024])</title>
    <dc:date>2024-12-11T16:37:03+00:00</dc:date>
    <link>https://www.di.ens.fr/~fbach/ltfp_book.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[--- Forthcoming w/ MIT Press]]></description>
<dc:subject>to:NB books:noted downloaded learning_theory bach.francis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5930b85a3c93/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:downloaded"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bach.francis"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2410.10101">
    <title>[2410.10101] Learning Linear Attention in Polynomial Time</title>
    <dc:date>2024-12-11T16:35:24+00:00</dc:date>
    <link>https://arxiv.org/abs/2410.10101</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Previous research has explored the computational expressivity of Transformer models in simulating Boolean circuits or Turing machines. However, the learnability of these simulators from observational data has remained an open question. Our study addresses this gap by providing the first polynomial-time learnability results (specifically strong, agnostic PAC learning) for single-layer Transformers with linear attention. We show that linear attention may be viewed as a linear predictor in a suitably defined RKHS. As a consequence, the problem of learning any linear transformer may be converted into the problem of learning an ordinary linear predictor in an expanded feature space, and any such predictor may be converted back into a multiheaded linear transformer. Moving to generalization, we show how to efficiently identify training datasets for which every empirical risk minimizer is equivalent (up to trivial symmetries) to the linear Transformer that generated the data, thereby guaranteeing the learned model will correctly generalize across all inputs. Finally, we provide examples of computations expressible via linear attention and therefore polynomial-time learnable, including associative memories, finite automata, and a class of Universal Turing Machine (UTMs) with polynomially bounded computation histories. We empirically validate our theoretical findings on three tasks: learning random linear attention networks, key--value associations, and learning to execute finite automata. Our findings bridge a critical gap between theoretical expressivity and learnability of Transformers, and show that flexible and general models of computation are efficiently learnable."]]></description>
<dc:subject>to:NB learning_theory large_language_models_(so_called)</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:632ce3a0b3f9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:large_language_models_(so_called)"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.jmlr.org/papers/v16/gammerman15b.html">
    <title>Alexey Chervonenkis's Bibliography: Introductory Comments</title>
    <dc:date>2024-12-11T16:00:42+00:00</dc:date>
    <link>https://www.jmlr.org/papers/v16/gammerman15b.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[--- For the bits about the early history of VC theory.]]></description>
<dc:subject>to:NB to_read learning_theory history_of_science via:mraginsky re:paradigm_formation_in_statistical_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5f41bff80bdd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:history_of_science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:paradigm_formation_in_statistical_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2411.00109">
    <title>[2411.00109] Prospective Learning: Learning for a Dynamic Future</title>
    <dc:date>2024-11-07T15:10:53+00:00</dc:date>
    <link>https://arxiv.org/abs/2411.00109</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In real-world applications, the distribution of the data, and our goals, evolve over time. The prevailing theoretical framework for studying machine learning, namely probably approximately correct (PAC) learning, largely ignores time. As a consequence, existing strategies to address the dynamic nature of data and goals exhibit poor real-world performance. This paper develops a theoretical framework called "Prospective Learning" that is tailored for situations when the optimal hypothesis changes over time. In PAC learning, empirical risk minimization (ERM) is known to be consistent. We develop a learner called Prospective ERM, which returns a sequence of predictors that make predictions on future data. We prove that the risk of prospective ERM converges to the Bayes risk under certain assumptions on the stochastic process generating the data. Prospective ERM, roughly speaking, incorporates time as an input in addition to the data. We show that standard ERM as done in PAC learning, without incorporating time, can result in failure to learn when distributions are dynamic. Numerical experiments illustrate that prospective ERM can learn synthetic and visual recognition problems constructed from MNIST and CIFAR-10."]]></description>
<dc:subject>in_NB learning_theory learning_under_dependence</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9aae6e7c7f2f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_under_dependence"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2304.06670">
    <title>[2304.06670] Do deep neural networks have an inbuilt Occam's razor?</title>
    <dc:date>2024-10-08T22:55:19+00:00</dc:date>
    <link>https://arxiv.org/abs/2304.06670</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The remarkable performance of overparameterized deep neural networks (DNNs) must arise from an interplay between network architecture, training algorithms, and structure in the data. To disentangle these three components, we apply a Bayesian picture, based on the functions expressed by a DNN, to supervised learning. The prior over functions is determined by the network, and is varied by exploiting a transition between ordered and chaotic regimes. For Boolean function classification, we approximate the likelihood using the error spectrum of functions on data. When combined with the prior, this accurately predicts the posterior, measured for DNNs trained with stochastic gradient descent. This analysis reveals that structured data, combined with an intrinsic Occam's razor-like inductive bias towards (Kolmogorov) simple functions that is strong enough to counteract the exponential growth of the number of functions with complexity, is a key to the success of DNNs."

--- I am skeptical from the abstract _alone_.  (Kolmogorov complexity is relative to a choice of universal Turing machine, for starters.)  More broadly, the idea that some form of Occam is automagically granted by (non-crazy) priors is very dubious, because it's vulnerable to essentially the same counter-argument as the one I gave in [http://bactra.org/notebooks/occam-bounds-for-long-programs.html] against the short-programs-generalize-well version of Occam.  Someone who re-arranged his prior to put a lot of probability on a _small_ set of really complex programs/functions would get the same sort of generalization guarantees...  I will, of course, be happy if this paper is actually very insightful and I need to eat all these words after reading it.]]></description>
<dc:subject>via:vaguery learning_theory neural_networks bayesianism to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f2d4bd730be9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:vaguery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bayesianism"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2407.20199">
    <title>[2407.20199] Emergence in non-neural models: grokking modular arithmetic via average gradient outer product</title>
    <dc:date>2024-09-19T20:01:34+00:00</dc:date>
    <link>https://arxiv.org/abs/2407.20199</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Neural networks trained to solve modular arithmetic tasks exhibit grokking, a phenomenon where the test accuracy starts improving long after the model achieves 100% training accuracy in the training process. It is often taken as an example of "emergence", where model ability manifests sharply through a phase transition. In this work, we show that the phenomenon of grokking is not specific to neural networks nor to gradient descent-based optimization. Specifically, we show that this phenomenon occurs when learning modular arithmetic with Recursive Feature Machines (RFM), an iterative algorithm that uses the Average Gradient Outer Product (AGOP) to enable task-specific feature learning with general machine learning models. When used in conjunction with kernel machines, iterating RFM results in a fast transition from random, near zero, test accuracy to perfect test accuracy. This transition cannot be predicted from the training loss, which is identically zero, nor from the test loss, which remains constant in initial iterations. Instead, as we show, the transition is completely determined by feature learning: RFM gradually learns block-circulant features to solve modular arithmetic. Paralleling the results for RFM, we show that neural networks that solve modular arithmetic also learn block-circulant features. Furthermore, we present theoretical evidence that RFM uses such block-circulant features to implement the Fourier Multiplication Algorithm, which prior work posited as the generalizing solution neural networks learn on these tasks. Our results demonstrate that emergence can result purely from learning task-relevant features and is not specific to neural architectures nor gradient descent-based optimization methods. Furthermore, our work provides more evidence for AGOP as a key mechanism for feature learning in neural networks."]]></description>
<dc:subject>to:NB learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1e37f2ea52ac/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://openreview.net/forum?id=ux9BrxPCl8">
    <title>Grokking Beyond Neural Networks: An Empirical Exploration with Model Complexity | OpenReview</title>
    <dc:date>2024-09-19T20:00:20+00:00</dc:date>
    <link>https://openreview.net/forum?id=ux9BrxPCl8</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In some settings neural networks exhibit a phenomenon known as \textit{grokking}, where they achieve perfect or near-perfect accuracy on the validation set long after the same performance has been achieved on the training set. In this paper, we discover that grokking is not limited to neural networks but occurs in other settings such as Gaussian process (GP) classification, GP regression, linear regression and Bayesian neural networks. We also uncover a mechanism by which to induce grokking on algorithmic datasets via the addition of dimensions containing spurious information. The presence of the phenomenon in non-neural architectures shows that grokking is not restricted to settings considered in current theoretical and empirical studies. Instead, grokking may be possible in any model where solution search is guided by complexity and error."]]></description>
<dc:subject>to:NB learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:594e324479e0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2401.14483">
    <title>[2401.14483] Four Facets of Forecast Felicity: Calibration, Predictiveness, Randomness and Regret</title>
    <dc:date>2024-09-17T17:59:19+00:00</dc:date>
    <link>https://arxiv.org/abs/2401.14483</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Machine learning is about forecasting. Forecasts, however, obtain their usefulness only through their evaluation. Machine learning has traditionally focused on types of losses and their corresponding regret. Currently, the machine learning community regained interest in calibration. In this work, we show the conceptual equivalence of calibration and regret in evaluating forecasts. We frame the evaluation problem as a game between a forecaster, a gambler and nature. Putting intuitive restrictions on gambler and forecaster, calibration and regret naturally fall out of the framework. In addition, this game links evaluation of forecasts to randomness of outcomes. Random outcomes with respect to forecasts are equivalent to good forecasts with respect to outcomes. We call those dual aspects, calibration and regret, predictiveness and randomness, the four facets of forecast felicity."]]></description>
<dc:subject>to:NB to_read prediction game_theory learning_theory low-regret_learning calibration</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fca0556a77fc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:game_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:calibration"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2310.20360">
    <title>[2310.20360] Mathematical Introduction to Deep Learning: Methods, Implementations, and Theory</title>
    <dc:date>2024-09-05T13:41:00+00:00</dc:date>
    <link>https://arxiv.org/abs/2310.20360</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This book aims to provide an introduction to the topic of deep learning algorithms. We review essential components of deep learning algorithms in full mathematical detail including different artificial neural network (ANN) architectures (such as fully-connected feedforward ANNs, convolutional ANNs, recurrent ANNs, residual ANNs, and ANNs with batch normalization) and different optimization algorithms (such as the basic stochastic gradient descent (SGD) method, accelerated methods, and adaptive methods). We also cover several theoretical aspects of deep learning algorithms such as approximation capacities of ANNs (including a calculus for ANNs), optimization theory (including Kurdyka-Łojasiewicz inequalities), and generalization errors. In the last part of the book some deep learning approximation methods for PDEs are reviewed including physics-informed neural networks (PINNs) and deep Galerkin methods. We hope that this book will be useful for students and scientists who do not yet have any background in deep learning at all and would like to gain a solid foundation as well as for practitioners who would like to obtain a firmer mathematical understanding of the objects and methods considered in deep learning."]]></description>
<dc:subject>neural_networks learning_theory books:noted in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:bdf0ef9b6702/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2202.06915">
    <title>[2202.06915] Stochastic linear optimization never overfits with quadratically-bounded losses on general data</title>
    <dc:date>2024-07-17T15:26:49+00:00</dc:date>
    <link>https://arxiv.org/abs/2202.06915</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This work provides test error bounds for iterative fixed point methods on linear predictors -- specifically, stochastic and batch mirror descent (MD), and stochastic temporal difference learning (TD) -- with two core contributions: (a) a single proof technique which gives high probability guarantees despite the absence of projections, regularization, or any equivalents, even when optima have large or infinite norm, for quadratically-bounded losses (e.g., providing unified treatment of squared and logistic losses); (b) locally-adapted rates which depend not on global problem structure (such as condition numbers and maximum margins), but rather on properties of low norm predictors which may suffer some small excess test error. The proof technique is an elementary and versatile coupling argument, and is demonstrated here in the following settings: stochastic MD under realizability; stochastic MD for general Markov data; batch MD for general IID data; stochastic MD on heavy-tailed data (still without projections); stochastic TD on Markov chains (all prior stochastic TD bounds are in expectation)."]]></description>
<dc:subject>in_NB learning_theory optimization telgarsky.matus</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f16b1331c21a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:telgarsky.matus"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2404.03774">
    <title>[2404.03774] Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning</title>
    <dc:date>2024-07-17T14:53:47+00:00</dc:date>
    <link>https://arxiv.org/abs/2404.03774</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Supervised learning is often computationally easy in practice. But to what extent does this mean that other modes of learning, such as reinforcement learning (RL), ought to be computationally easy by extension? In this work we show the first cryptographic separation between RL and supervised learning, by exhibiting a class of block MDPs and associated decoding functions where reward-free exploration is provably computationally harder than the associated regression problem. We also show that there is no computationally efficient algorithm for reward-directed RL in block MDPs, even when given access to an oracle for this regression problem.
"It is known that being able to perform regression in block MDPs is necessary for finding a good policy; our results suggest that it is not sufficient. Our separation lower bound uses a new robustness property of the Learning Parities with Noise (LPN) hardness assumption, which is crucial in handling the dependent nature of RL data. We argue that separations and oracle lower bounds, such as ours, are a more meaningful way to prove hardness of learning because the constructions better reflect the practical reality that supervised learning by itself is often not the computational bottleneck."]]></description>
<dc:subject>in_NB learning_theory reinforcement_learning computational_complexity</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2962e58071e6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:reinforcement_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:computational_complexity"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2404.06757">
    <title>[2404.06757] Language Generation in the Limit</title>
    <dc:date>2024-07-17T14:42:52+00:00</dc:date>
    <link>https://arxiv.org/abs/2404.06757</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings from the language that don't already appear in the training data. Here we ask what we can conclude about language generation using only this specification, without further assumptions. In particular, suppose that an adversary enumerates the strings of an unknown target language L that is known only to come from one of a possibly infinite list of candidates. A computational agent is trying to learn to generate from this language; we say that the agent generates from L in the limit if after some finite point in the enumeration of L, the agent is able to produce new elements that come exclusively from L and that have not yet been presented by the adversary. Our main result is that there is an agent that is able to generate in the limit for every countable list of candidate languages. This contrasts dramatically with negative results due to Gold and Angluin in a well-studied model of language learning where the goal is to identify an unknown language from samples; the difference between these results suggests that identifying a language is a fundamentally different problem than generating from it."]]></description>
<dc:subject>in_NB formal_languages learning_theory grammar_induction kleinberg.jon to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:064dd4cafd1e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:formal_languages"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:grammar_induction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kleinberg.jon"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2405.18055v1">
    <title>[2405.18055v1] Dimension-free uniform concentration bound for logistic regression</title>
    <dc:date>2024-06-10T14:16:59+00:00</dc:date>
    <link>https://arxiv.org/abs/2405.18055v1</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We provide a novel dimension-free uniform concentration bound for the empirical risk function of constrained logistic regression. Our bound yields a milder sufficient condition for a uniform law of large numbers than conditions derived by the Rademacher complexity argument and McDiarmid's inequality. The derivation is based on the PAC-Bayes approach with second-order expansion and Rademacher-complexity-based bounds for the residual term of the expansion."]]></description>
<dc:subject>to:NB to_read logistic_regression learning_theory to_teach:childs_garden_of_statistical_learning_theory via:?</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2fb188076270/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:logistic_regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:?"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2402.14987">
    <title>[2402.14987] On the Performance of Empirical Risk Minimization with Smoothed Data</title>
    <dc:date>2024-03-05T16:33:38+00:00</dc:date>
    <link>https://arxiv.org/abs/2402.14987</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In order to circumvent statistical and computational hardness results in sequential decision-making, recent work has considered smoothed online learning, where the distribution of data at each time is assumed to have bounded likeliehood ratio with respect to a base measure when conditioned on the history. While previous works have demonstrated the benefits of smoothness, they have either assumed that the base measure is known to the learner or have presented computationally inefficient algorithms applying only in special cases. This work investigates the more general setting where the base measure is \emph{unknown} to the learner, focusing in particular on the performance of Empirical Risk Minimization (ERM) with square loss when the data are well-specified and smooth. We show that in this setting, ERM is able to achieve sublinear error whenever a class is learnable with iid data; in particular, ERM achieves error scaling as Õ (comp()⋅T‾‾‾‾‾‾‾‾‾‾‾‾√), where comp() is the statistical complexity of learning  with iid data. In so doing, we prove a novel norm comparison bound for smoothed data that comprises the first sharp norm comparison for dependent data applying to arbitrary, nonlinear function classes. We complement these results with a lower bound indicating that our analysis of ERM is essentially tight, establishing a separation in the performance of ERM between smoothed and iid data."]]></description>
<dc:subject>learning_theory rakhlin.alexander optimization in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:59e6353bf8b8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:rakhlin.alexander"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-2/Minimax-rates-for-conditional-density-estimation-via-empirical-entropy/10.1214/23-AOS2270.short">
    <title>Minimax rates for conditional density estimation via empirical entropy</title>
    <dc:date>2024-03-05T14:57:19+00:00</dc:date>
    <link>https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-2/Minimax-rates-for-conditional-density-estimation-via-empirical-entropy/10.1214/23-AOS2270.short</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider the task of estimating a conditional density using i.i.d. samples from a joint distribution, which is a fundamental problem with applications in both classification and uncertainty quantification for regression. For joint density estimation, minimax rates have been characterized for general density classes in terms of uniform (metric) entropy, a well-studied notion of statistical capacity. When applying these results to conditional density estimation, the use of uniform entropy—which is infinite when the covariate space is unbounded and suffers from the curse of dimensionality—can lead to suboptimal rates. Consequently, minimax rates for conditional density estimation cannot be characterized using these classical results.
"We resolve this problem for well-specified models, obtaining matching (within logarithmic factors) upper and lower bounds on the minimax Kullback–Leibler risk in terms of the empirical Hellinger entropy for the conditional density class. The use of empirical entropy allows us to appeal to concentration arguments based on local Rademacher complexity, which—in contrast to uniform entropy—leads to matching rates for large, potentially nonparametric classes and captures the correct dependence on the complexity of the covariate space. Our results require only that the conditional densities are bounded above, and do not require that they are bounded below or otherwise satisfy any tail conditions."

--- Ungated: [https://arxiv.org/abs/2109.10461]]]></description>
<dc:subject>in_NB density_estimation learning_theory via:mraginsky</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0416eeb58e24/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:density_estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2110.11216">
    <title>[2110.11216] User-friendly introduction to PAC-Bayes bounds</title>
    <dc:date>2024-03-02T19:25:18+00:00</dc:date>
    <link>https://arxiv.org/abs/2110.11216</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Aggregated predictors are obtained by making a set of basic predictors vote according to some weights, that is, to some probability distribution.
"Randomized predictors are obtained by sampling in a set of basic predictors, according to some prescribed probability distribution.
"Thus, aggregated and randomized predictors have in common that they are not defined by a minimization problem, but by a probability distribution on the set of predictors. In statistical learning theory, there is a set of tools designed to understand the generalization ability of such procedures: PAC-Bayesian or PAC-Bayes bounds.
"Since the original PAC-Bayes bounds of D. McAllester, these tools have been considerably improved in many directions (we will for example describe a simplified version of the localization technique of O. Catoni that was missed by the community, and later rediscovered as "mutual information bounds"). Very recently, PAC-Bayes bounds received a considerable attention: for example there was workshop on PAC-Bayes at NIPS 2017, "(Almost) 50 Shades of Bayesian Learning: PAC-Bayesian trends and insights", organized by B. Guedj, F. Bach and P. Germain. One of the reason of this recent success is the successful application of these bounds to neural networks by G. Dziugaite and D. Roy.
"An elementary introduction to PAC-Bayes theory is still missing. This is an attempt to provide such an introduction."


--- Published version: [https://doi.org/10.1561/2200000100]]]></description>
<dc:subject>to:NB to_read learning_theory ensemble_methods to_teach:childs_garden_of_statistical_learning_theory alquier.pierre</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:27997bd5aeb9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:alquier.pierre"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2402.13285">
    <title>[2402.13285] Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measures</title>
    <dc:date>2024-02-27T20:03:04+00:00</dc:date>
    <link>https://arxiv.org/abs/2402.13285</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In statistical learning theory, a generalization bound usually involves a complexity measure imposed by the considered theoretical framework. This limits the scope of such bounds, as other forms of capacity measures or regularizations are used in algorithms. In this paper, we leverage the framework of disintegrated PAC-Bayes bounds to derive a general generalization bound instantiable with arbitrary complexity measures. One trick to prove such a result involves considering a commonly used family of distributions: the Gibbs distributions. Our bound stands in probability jointly over the hypothesis and the learning sample, which allows the complexity to be adapted to the generalization gap as it can be customized to fit both the hypothesis class and the task."]]></description>
<dc:subject>to:NB learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2031e4da5d2d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2402.01502">
    <title>[2402.01502] Why do Random Forests Work? Understanding Tree Ensembles as Self-Regularizing Adaptive Smoothers</title>
    <dc:date>2024-02-27T19:59:40+00:00</dc:date>
    <link>https://arxiv.org/abs/2402.01502</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Despite their remarkable effectiveness and broad application, the drivers of success underlying ensembles of trees are still not fully understood. In this paper, we highlight how interpreting tree ensembles as adaptive and self-regularizing smoothers can provide new intuition and deeper insight to this topic. We use this perspective to show that, when studied as smoothers, randomized tree ensembles not only make predictions that are quantifiably more smooth than the predictions of the individual trees they consist of, but also further regulate their smoothness at test-time based on the dissimilarity between testing and training inputs. First, we use this insight to revisit, refine and reconcile two recent explanations of forest success by providing a new way of quantifying the conjectured behaviors of tree ensembles objectively by measuring the effective degree of smoothing they imply. Then, we move beyond existing explanations for the mechanisms by which tree ensembles improve upon individual trees and challenge the popular wisdom that the superior performance of forests should be understood as a consequence of variance reduction alone. We argue that the current high-level dichotomy into bias- and variance-reduction prevalent in statistics is insufficient to understand tree ensembles -- because the prevailing definition of bias does not capture differences in the expressivity of the hypothesis classes formed by trees and forests. Instead, we show that forests can improve upon trees by three distinct mechanisms that are usually implicitly entangled. In particular, we demonstrate that the smoothing effect of ensembling can reduce variance in predictions due to noise in outcome generation, reduce variability in the quality of the learned function given fixed input data and reduce potential bias in learnable functions by enriching the available hypothesis space."]]></description>
<dc:subject>to_read ensemble_methods random_forests decision_trees learning_theory in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:afc37c93e049/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_forests"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:decision_trees"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2311.07013">
    <title>[2311.07013] A PAC-Bayesian Perspective on the Interpolating Information Criterion</title>
    <dc:date>2024-02-15T18:33:43+00:00</dc:date>
    <link>https://arxiv.org/abs/2311.07013</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Deep learning is renowned for its theory-practice gap, whereby principled theory typically fails to provide much beneficial guidance for implementation in practice. This has been highlighted recently by the benign overfitting phenomenon: when neural networks become sufficiently large to interpolate the dataset perfectly, model performance appears to improve with increasing model size, in apparent contradiction with the well-known bias-variance tradeoff. While such phenomena have proven challenging to theoretically study for general models, the recently proposed Interpolating Information Criterion (IIC) provides a valuable theoretical framework to examine performance for overparameterized models. Using the IIC, a PAC-Bayes bound is obtained for a general class of models, characterizing factors which influence generalization performance in the interpolating regime. From the provided bound, we quantify how the test error for overparameterized models achieving effectively zero training error depends on the quality of the implicit regularization imposed by e.g. the combination of model, optimizer, and parameter-initialization scheme; the spectrum of the empirical neural tangent kernel; curvature of the loss landscape; and noise present in the data."]]></description>
<dc:subject>information_criteria learning_theory mahoney.michael_w. in_NB interpolation_aka_memorizing_the_training_data</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b054db187920/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_criteria"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mahoney.michael_w."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interpolation_aka_memorizing_the_training_data"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2109.02224">
    <title>[2109.02224] On Empirical Risk Minimization with Dependent and Heavy-Tailed Data</title>
    <dc:date>2023-12-14T11:31:16+00:00</dc:date>
    <link>https://arxiv.org/abs/2109.02224</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this work, we establish risk bounds for the Empirical Risk Minimization (ERM) with both dependent and heavy-tailed data-generating processes. We do so by extending the seminal works of Mendelson [Men15, Men18] on the analysis of ERM with heavy-tailed but independent and identically distributed observations, to the strictly stationary exponentially β-mixing case. Our analysis is based on explicitly controlling the multiplier process arising from the interaction between the noise and the function evaluations on inputs. It allows for the interaction to be even polynomially heavy-tailed, which covers a significantly large class of heavy-tailed models beyond what is analyzed in the learning theory literature. We illustrate our results by deriving rates of convergence for the high-dimensional linear regression problem with dependent and heavy-tailed data."

--- NeurIPS version: https://proceedings.neurips.cc/paper_files/paper/2021/hash/4afa19649ae378da31a423bcd78a97c8-Abstract.html]]></description>
<dc:subject>to:NB to_read learning_theory mixing heavy_tails learning_under_dependence</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9123f4f94745/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heavy_tails"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_under_dependence"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2309.13786">
    <title>[2309.13786] Distribution-Free Statistical Dispersion Control for Societal Applications</title>
    <dc:date>2023-12-09T01:22:25+00:00</dc:date>
    <link>https://arxiv.org/abs/2309.13786</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Explicit finite-sample statistical guarantees on model performance are an important ingredient in responsible machine learning. Previous work has focused mainly on bounding either the expected loss of a predictor or the probability that an individual prediction will incur a loss value in a specified range. However, for many high-stakes applications, it is crucial to understand and control the dispersion of a loss distribution, or the extent to which different members of a population experience unequal effects of algorithmic decisions. We initiate the study of distribution-free control of statistical dispersion measures with societal implications and propose a simple yet flexible framework that allows us to handle a much richer class of statistical functionals beyond previous work. Our methods are verified through experiments in toxic comment detection, medical imaging, and film recommendation."]]></description>
<dc:subject>to:NB learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ff6def22a22f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2305.18887">
    <title>[2305.18887] How Does Information Bottleneck Help Deep Learning?</title>
    <dc:date>2023-12-09T01:20:24+00:00</dc:date>
    <link>https://arxiv.org/abs/2305.18887</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Numerous deep learning algorithms have been inspired by and understood via the notion of information bottleneck, where unnecessary information is (often implicitly) minimized while task-relevant information is maximized. However, a rigorous argument for justifying why it is desirable to control information bottlenecks has been elusive. In this paper, we provide the first rigorous learning theory for justifying the benefit of information bottleneck in deep learning by mathematically relating information bottleneck to generalization errors. Our theory proves that controlling information bottleneck is one way to control generalization errors in deep learning, although it is not the only or necessary way. We investigate the merit of our new mathematical findings with experiments across a range of architectures and learning settings. In many cases, generalization errors are shown to correlate with the degree of information bottleneck: i.e., the amount of the unnecessary information at hidden layers. This paper provides a theoretical foundation for current and future methods through the lens of information bottleneck. Our new generalization bounds scale with the degree of information bottleneck, unlike the previous bounds that scale with the number of parameters, VC dimension, Rademacher complexity, stability or robustness."]]></description>
<dc:subject>to:NB information_bottleneck neural_networks learning_theory to_teach:statistics_and_generative_ai</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:61af1aefcaa9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_bottleneck"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:statistics_and_generative_ai"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2311.03910">
    <title>[2311.03910] Structure of universal formulas</title>
    <dc:date>2023-12-08T19:04:39+00:00</dc:date>
    <link>https://arxiv.org/abs/2311.03910</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["By universal formulas we understand parameterized analytic expressions that have a fixed complexity, but nevertheless can approximate any continuous function on a compact set. There exist various examples of such formulas, including some in the form of neural networks. In this paper we analyze the essential structural elements of these highly expressive models. We introduce a hierarchy of expressiveness classes connecting the global approximability property to the weaker property of infinite VC dimension, and prove a series of classification results for several increasingly complex functional families. In particular, we introduce a general family of polynomially-exponentially-algebraic functions that, as we prove, is subject to polynomial constraints. As a consequence, we show that fixed-size neural networks with not more than one layer of neurons having transcendental activations (e.g., sine or standard sigmoid) cannot in general approximate functions on arbitrary finite sets. On the other hand, we give examples of functional families, including two-hidden-layer neural networks, that approximate functions on arbitrary finite sets, but fail to do that on the whole domain of definition."]]></description>
<dc:subject>to:NB learning_theory neural_networks approximation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:43e65eb23777/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:approximation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2309.17016">
    <title>[2309.17016] Efficient Agnostic Learning with Average Smoothness</title>
    <dc:date>2023-12-08T17:15:57+00:00</dc:date>
    <link>https://arxiv.org/abs/2309.17016</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study distribution-free nonparametric regression following a notion of average smoothness initiated by Ashlagi et al. (2021), which measures the "effective" smoothness of a function with respect to an arbitrary unknown underlying distribution. While the recent work of Hanneke et al. (2023) established tight uniform convergence bounds for average-smooth functions in the realizable case and provided a computationally efficient realizable learning algorithm, both of these results currently lack analogs in the general agnostic (i.e. noisy) case.
"In this work, we fully close these gaps. First, we provide a distribution-free uniform convergence bound for average-smoothness classes in the agnostic setting. Second, we match the derived sample complexity with a computationally efficient agnostic learning algorithm. Our results, which are stated in terms of the intrinsic geometry of the data and hold over any totally bounded metric space, show that the guarantees recently obtained for realizable learning of average-smooth functions transfer to the agnostic setting. At the heart of our proof, we establish the uniform convergence rate of a function class in terms of its bracketing entropy, which may be of independent interest."]]></description>
<dc:subject>in_NB nonparametrics learning_theory empirical_processes kith_and_kin kontorovich.aryeh hanneke.steve</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:372bb023a730/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:empirical_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kontorovich.aryeh"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hanneke.steve"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2305.11042">
    <title>[2305.11042] A unified framework for information-theoretic generalization bounds</title>
    <dc:date>2023-09-29T15:59:52+00:00</dc:date>
    <link>https://arxiv.org/abs/2305.11042</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper presents a general methodology for deriving information-theoretic generalization bounds for learning algorithms. The main technical tool is a probabilistic decorrelation lemma based on a change of measure and a relaxation of Young's inequality in Lψp Orlicz spaces. Using the decorrelation lemma in combination with other techniques, such as symmetrization, couplings, and chaining in the space of probability measures, we obtain new upper bounds on the generalization error, both in expectation and in high probability, and recover as special cases many of the existing generalization bounds, including the ones based on mutual information, conditional mutual information, stochastic chaining, and PAC-Bayes inequalities. In addition, the Fernique-Talagrand upper bound on the expected supremum of a subgaussian process emerges as a special case."]]></description>
<dc:subject>in_NB learning_theory information_theory raginsky.maxim</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:89c7fa1175e6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:raginsky.maxim"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1202.3699">
    <title>[1202.3699] Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search</title>
    <dc:date>2023-08-14T17:45:19+00:00</dc:date>
    <link>https://arxiv.org/abs/1202.3699</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Bayes-optimal behavior, while well-defined, is often difficult to achieve. Recent advances in the use of Monte-Carlo tree search (MCTS) have shown that it is possible to act near-optimally in Markov Decision Processes (MDPs) with very large or infinite state spaces. Bayes-optimal behavior in an unknown MDP is equivalent to optimal behavior in the known belief-space MDP, although the size of this belief-space MDP grows exponentially with the amount of history retained, and is potentially infinite. We show how an agent can use one particular MCTS algorithm, Forward Search Sparse Sampling (FSSS), in an efficient way to act nearly Bayes-optimally for all but a polynomial number of steps, assuming that FSSS can be used to act efficiently in any possible underlying MDP."]]></description>
<dc:subject>in_NB reinforcement_learning learning_theory littman.michael_l. via:?</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:db4b86ee8a65/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:reinforcement_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:littman.michael_l."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:?"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2007.13982">
    <title>[2007.13982] Distributionally Robust Losses for Latent Covariate Mixtures</title>
    <dc:date>2023-07-31T01:35:05+00:00</dc:date>
    <link>https://arxiv.org/abs/2007.13982</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["While modern large-scale datasets often consist of heterogeneous subpopulations -- for example, multiple demographic groups or multiple text corpora -- the standard practice of minimizing average loss fails to guarantee uniformly low losses across all subpopulations. We propose a convex procedure that controls the worst-case performance over all subpopulations of a given size. Our procedure comes with finite-sample (nonparametric) convergence guarantees on the worst-off subpopulation. Empirically, we observe on lexical similarity, wine quality, and recidivism prediction tasks that our worst-case procedure learns models that do well against unseen subpopulations."]]></description>
<dc:subject>to_read learning_theory re:codename:one_law_for_the_lion_and_ox_is_oppression algorithmic_fairness duchi.john via:rvenkat scooped? in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e92126446535/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:codename:one_law_for_the_lion_and_ox_is_oppression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:algorithmic_fairness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:duchi.john"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:rvenkat"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:scooped?"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2210.03458">
    <title>[2210.03458] PAC Privacy: Automatic Privacy Measurement and Control of Data Processing</title>
    <dc:date>2023-07-18T18:50:44+00:00</dc:date>
    <link>https://arxiv.org/abs/2210.03458</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose and study a new privacy definition, termed Probably Approximately Correct (PAC) Privacy. PAC Privacy characterizes the information-theoretic hardness to recover sensitive data given arbitrary information disclosure/leakage during/after any processing. Unlike the classic cryptographic definition and Differential Privacy (DP), which consider the adversarial (input-independent) worst case, PAC Privacy is a simulatable metric that quantifies the instance-based impossibility of inference. A fully automatic analysis and proof generation framework is proposed: security parameters can be produced with arbitrarily high confidence via Monte-Carlo simulation for any black-box data processing oracle. This appealing automation property enables analysis of complicated data processing, where the worst-case proof in the classic privacy regime could be loose or even intractable. Moreover, we show that the produced PAC Privacy guarantees enjoy simple composition bounds and the automatic analysis framework can be implemented in an online fashion to analyze the composite PAC Privacy loss even under correlated randomness. On the utility side, the magnitude of (necessary) perturbation required in PAC Privacy is not lower bounded by Theta(\sqrt{d}) for a d-dimensional release but could be O(1) for many practical data processing tasks, which is in contrast to the input-independent worst-case information-theoretic lower bound. Example applications of PAC Privacy are included with comparisons to existing works."]]></description>
<dc:subject>to:NB learning_theory privacy</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1bedb5604493/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:privacy"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2202.09889">
    <title>[2202.09889] Memorize to Generalize: on the Necessity of Interpolation in High Dimensional Linear Regression</title>
    <dc:date>2023-06-28T16:12:30+00:00</dc:date>
    <link>https://arxiv.org/abs/2202.09889</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>in_NB learning_theory interpolation_aka_memorizing_the_training_data</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b1a70c7be3e0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interpolation_aka_memorizing_the_training_data"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://notstatschat.rbind.io/2022/09/28/uniform-law-of-large-numbers/">
    <title>A plug-in uniform law of large numbers - Biased and Inefficient</title>
    <dc:date>2023-06-15T19:18:32+00:00</dc:date>
    <link>https://notstatschat.rbind.io/2022/09/28/uniform-law-of-large-numbers/</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>have_read ergodic_theory empirical_processes lumley.thomas learning_theory re:HEAS in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1dfcf0d1d3f9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ergodic_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:empirical_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:lumley.thomas"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:HEAS"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2305.17592">
    <title>[2305.17592] Approximation-Generalization Trade-offs under (Approximate) Group Equivariance</title>
    <dc:date>2023-06-05T02:40:59+00:00</dc:date>
    <link>https://arxiv.org/abs/2305.17592</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The explicit incorporation of task-specific inductive biases through symmetry has emerged as a general design precept in the development of high-performance machine learning models. For example, group equivariant neural networks have demonstrated impressive performance across various domains and applications such as protein and drug design. A prevalent intuition about such models is that the integration of relevant symmetry results in enhanced generalization. Moreover, it is posited that when the data and/or the model may only exhibit approximate or partial symmetry, the optimal or best-performing model is one where the model symmetry aligns with the data symmetry. In this paper, we conduct a formal unified investigation of these intuitions. To begin, we present general quantitative bounds that demonstrate how models capturing task-specific symmetries lead to improved generalization. In fact, our results do not require the transformations to be finite or even form a group and can work with partial or approximate equivariance. Utilizing this quantification, we examine the more general question of model mis-specification i.e. when the model symmetries don't align with the data symmetries. We establish, for a given symmetry group, a quantitative comparison between the approximate/partial equivariance of the model and that of the data distribution, precisely connecting model equivariance error and data equivariance error. Our result delineates conditions under which the model equivariance error is optimal, thereby yielding the best-performing model for the given task and data."]]></description>
<dc:subject>symmetry learning_theory in_NB have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7639b9f8db7b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:symmetry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://ieeexplore.ieee.org/document/21929">
    <title>Learning probabilistic prediction functions | IEEE Conference Publication | IEEE Xplore</title>
    <dc:date>2023-05-08T19:22:57+00:00</dc:date>
    <link>https://ieeexplore.ieee.org/document/21929</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The question of how to learn rules, when those rules make probabilistic statements about the future, is considered. Issues are discussed that arise when attempting to determine what a good prediction function is, when those prediction functions make probabilistic assumptions. Learning has at least two purposes: to enable the learner to make predictions in the future and to satisfy intellectual curiosity as to the underlying cause of a process. Two results related to these distinct goals are given. In both cases, the inputs are a countable collection of functions which make probabilistic statements about a sequence of events. One of the results shows how to find one of the functions, which generated the sequence, the other result allows to do as well in terms of predicting events as the best of the collection. In both cases the results are obtained by evaluating a function based on a tradeoff between its simplicity and the accuracy of its predictions."]]></description>
<dc:subject>in_NB learning_theory prediction have_read low-regret_learning probability cleaning_out_the_filing_cabinet_for_the_first_time_since_2005</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:19a5b745c5e5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cleaning_out_the_filing_cabinet_for_the_first_time_since_2005"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://dl.acm.org/doi/abs/10.5555/93025.93105">
    <title>Efficient unsupervised learning | Proceedings of the first annual workshop on Computational learning theory</title>
    <dc:date>2023-05-08T19:16:48+00:00</dc:date>
    <link>https://dl.acm.org/doi/abs/10.5555/93025.93105</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>to:NB learning_theory cleaning_out_the_filing_cabinet_for_the_first_time_since_2005 have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:23bb7536d7ad/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cleaning_out_the_filing_cabinet_for_the_first_time_since_2005"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2305.00322">
    <title>[2305.00322] Toward $L_infty$-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields</title>
    <dc:date>2023-05-05T01:47:16+00:00</dc:date>
    <link>https://arxiv.org/abs/2305.00322</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many machine learning applications require learning a function with a small worst-case error over the entire input domain, that is, the L∞-error, whereas most existing theoretical works only guarantee recovery in average errors such as the L2-error. L∞-recovery from polynomial samples is even impossible for seemingly simple function classes such as constant-norm infinite-width two-layer neural nets. This paper makes some initial steps beyond the impossibility results by leveraging the randomness in the ground-truth functions. We prove a polynomial sample complexity bound for random ground-truth functions drawn from Gaussian random fields. Our key technical novelty is to prove that the degree-k spherical harmonics components of a function from Gaussian random field cannot be spiky in that their L∞/L2 ratios are upperbounded by O(dlnk‾‾‾‾√) with high probability. In contrast, the worst-case L∞/L2 ratio for degree-k spherical harmonics is on the order of Ω(min{dk/2,kd/2})."

--- This sounds interesting, but it also seems to say that Gaussian random fields generate especially smooth functions (with high probability), casting doubt on their suitability as a general prior.  (Of course I think there's no such thing as a general
prior.)]]></description>
<dc:subject>approximation learning_theory random_fields in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fb73aea45ac1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_fields"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://proceedings.mlr.press/v206/bosch23a">
    <title>Random Features Model with General Convex Regularization: A Fine Grained Analysis with Precise Asymptotic Learning Curves</title>
    <dc:date>2023-04-27T14:42:18+00:00</dc:date>
    <link>https://proceedings.mlr.press/v206/bosch23a</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We compute precise asymptotic expressions for the learning curves of least squares random feature (RF) models with either a separable strongly convex regularization or the ℓ1 regularization. We propose a novel multi-level application of the convex Gaussian min max theorem (CGMT) to overcome the traditional difficulty of finding computable expressions for random features models with correlated data. Our result takes the form of a computable 4-dimensional scalar optimization. In contrast to previous results, our approach does not require solving an often intractable proximal operator, which scales with the number of model parameters. Furthermore, we extend the universality results for the training and generalization errors for RF models to ℓ1 regularization. In particular, we demonstrate that under mild conditions, random feature models with elastic net or ℓ1 regularization are asymptotically equivalent to a surrogate Gaussian model with the same first and second moments. We numerically demonstrate the predictive capacity of our results, and show experimentally that the predicted test error is accurate even in the non-asymptotic regime."]]></description>
<dc:subject>random_features learning_theory to_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f67c431b3165/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_features"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2107.04562">
    <title>[2107.04562] The Bayesian Learning Rule</title>
    <dc:date>2023-03-18T14:30:57+00:00</dc:date>
    <link>https://arxiv.org/abs/2107.04562</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We show that many machine-learning algorithms are specific instances of a single algorithm called the Bayesian learning rule. The rule, derived from Bayesian principles, yields a wide-range of algorithms from fields such as optimization, deep learning, and graphical models. This includes classical algorithms such as ridge regression, Newton's method, and Kalman filter, as well as modern deep-learning algorithms such as stochastic-gradient descent, RMSprop, and Dropout. The key idea in deriving such algorithms is to approximate the posterior using candidate distributions estimated by using natural gradients. Different candidate distributions result in different algorithms and further approximations to natural gradients give rise to variants of those algorithms. Our work not only unifies, generalizes, and improves existing algorithms, but also helps us design new ones."]]></description>
<dc:subject>to:NB learning_theory optimization bayesianism color_me_skeptical have_skimmed</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:928b90fa32e5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bayesianism"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:color_me_skeptical"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_skimmed"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2303.05369">
    <title>[2303.05369] Data-dependent Generalization Bounds via Variable-Size Compressibility</title>
    <dc:date>2023-03-18T13:51:32+00:00</dc:date>
    <link>https://arxiv.org/abs/2303.05369</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper, we establish novel data-dependent upper bounds on the generalization error through the lens of a "variable-size compressibility" framework that we introduce newly here. In this framework, the generalization error of an algorithm is linked to a variable-size 'compression rate' of its input data. This is shown to yield bounds that depend on the empirical measure of the given input data at hand, rather than its unknown distribution. Our new generalization bounds that we establish are tail bounds, tail bounds on the expectation, and in-expectations bounds. Moreover, it is shown that our framework also allows to derive general bounds on any function of the input data and output hypothesis random variables. In particular, these general bounds are shown to subsume and possibly improve over several existing PAC-Bayes and data-dependent intrinsic dimension-based bounds that are recovered as special cases, thus unveiling a unifying character of our approach. For instance, a new data-dependent intrinsic dimension based bounds is established, which connects the generalization error to the optimization trajectories and reveals various interesting connections with rate-distortion dimension of process, Rényi information dimension of process, and metric mean dimension."]]></description>
<dc:subject>information_theory learning_theory to_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:09b32ab25cd5/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2302.06005">
    <title>[2302.06005] Near-optimal learning with average Hölder smoothness</title>
    <dc:date>2023-02-24T03:27:08+00:00</dc:date>
    <link>https://arxiv.org/abs/2302.06005</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We generalize the notion of average Lipschitz smoothness proposed by Ashlagi et al. (COLT 2021) by extending it to Hölder smoothness. This measure of the ``effective smoothness'' of a function is sensitive to the underlying distribution and can be dramatically smaller than its classic ``worst-case'' Hölder constant. We prove nearly tight upper and lower risk bounds in terms of the average Hölder smoothness, establishing the minimax rate in the realizable regression setting up to log factors; this was not previously known even in the special case of average Lipschitz smoothness. From an algorithmic perspective, since our notion of average smoothness is defined with respect to the unknown sampling distribution, the learner does not have an explicit representation of the function class, hence is unable to execute ERM. Nevertheless, we provide a learning algorithm that achieves the (nearly) optimal learning rate. Our results hold in any totally bounded metric space, and are stated in terms of its intrinsic geometry. Overall, our results show that the classic worst-case notion of Hölder smoothness can be essentially replaced by its average, yielding considerably sharper guarantees."]]></description>
<dc:subject>to:NB learning_theory nonparametrics kontorovich.aryeh hanneke.steve</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:3454a701b130/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kontorovich.aryeh"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hanneke.steve"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2302.07263">
    <title>[2302.07263] Interpolation Learning With Minimum Description Length</title>
    <dc:date>2023-02-24T03:25:19+00:00</dc:date>
    <link>https://arxiv.org/abs/2302.07263</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We prove that the Minimum Description Length learning rule exhibits tempered overfitting. We obtain tempered agnostic finite sample learning guarantees and characterize the asymptotic behavior in the presence of random label noise."]]></description>
<dc:subject>mdl learning_theory in_NB interpolation_aka_memorizing_the_training_data</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:910225f7e41f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mdl"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interpolation_aka_memorizing_the_training_data"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2212.13556">
    <title>[2212.13556] Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization</title>
    <dc:date>2023-01-18T03:11:36+00:00</dc:date>
    <link>https://arxiv.org/abs/2212.13556</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["To date, no "information-theoretic" frameworks for reasoning about generalization error have been shown to establish minimax rates for gradient descent in the setting of stochastic convex optimization. In this work, we consider the prospect of establishing such rates via several existing information-theoretic frameworks: input-output mutual information bounds, conditional mutual information bounds and variants, PAC-Bayes bounds, and recent conditional variants thereof. We prove that none of these bounds are able to establish minimax rates. We then consider a common tactic employed in studying gradient methods, whereby the final iterate is corrupted by Gaussian noise, producing a noisy "surrogate" algorithm. We prove that minimax rates cannot be established via the analysis of such surrogates. Our results suggest that new ideas are required to analyze gradient descent using information-theoretic techniques."]]></description>
<dc:subject>to:NB optimization information_theory learning_theory minimax</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c922f5bb9181/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:minimax"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://hdsr.mitpress.mit.edu/pub/qixx99zn/release/1">
    <title>On Learnability Under General Stochastic Processes · Issue 4.4, Fall 2022</title>
    <dc:date>2022-12-09T20:08:14+00:00</dc:date>
    <link>https://hdsr.mitpress.mit.edu/pub/qixx99zn/release/1</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Statistical learning theory under independent and identically distributed (iid) sampling and online learning theory for worst case individual sequences are two of the best developed branches of learning theory. Statistical learning under general non-iid stochastic processes is less mature. We provide two natural notions of learnability of a function class under a general stochastic process. We show that both notions are in fact equivalent to online learnability. Our results hold for both binary classification and regression."

--- Ungated: [https://arxiv.org/abs/2005.07605]]]></description>
<dc:subject>to:NB learning_theory online_learning low-regret_learning to_read tewari.ambuj learning_under_dependence dawid.a._philip stochastic_processes to_teach:childs_garden_of_statistical_learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d8309e159972/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:tewari.ambuj"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_under_dependence"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:dawid.a._philip"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2105.12806">
    <title>[2105.12806] A Universal Law of Robustness via Isoperimetry</title>
    <dc:date>2022-11-14T15:14:12+00:00</dc:date>
    <link>https://arxiv.org/abs/2105.12806</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Classically, data interpolation with a parametrized model class is possible as long as the number of parameters is larger than the number of equations to be satisfied. A puzzling phenomenon in deep learning is that models are trained with many more parameters than what this classical theory would suggest. We propose a theoretical explanation for this phenomenon. We prove that for a broad class of data distributions and model classes, overparametrization is necessary if one wants to interpolate the data smoothly. Namely we show that smooth interpolation requires d times more parameters than mere interpolation, where d is the ambient data dimension. We prove this universal law of robustness for any smoothly parametrized function class with polynomial size weights, and any covariate distribution verifying isoperimetry. In the case of two-layers neural networks and Gaussian covariates, this law was conjectured in prior work by Bubeck, Li and Nagaraj. We also give an interpretation of our result as an improved generalization bound for model classes consisting of smooth functions."]]></description>
<dc:subject>learning_theory bubeck.sebastien in_NB interpolation_aka_memorizing_the_training_data</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5f42a23ae835/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bubeck.sebastien"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interpolation_aka_memorizing_the_training_data"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2202.04985">
    <title>[2202.04985] Generalization Bounds via Convex Analysis</title>
    <dc:date>2022-08-25T16:12:32+00:00</dc:date>
    <link>https://arxiv.org/abs/2202.04985</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Since the celebrated works of Russo and Zou (2016,2019) and Xu and Raginsky (2017), it has been well known that the generalization error of supervised learning algorithms can be bounded in terms of the mutual information between their input and the output, given that the loss of any fixed hypothesis has a subgaussian tail. In this work, we generalize this result beyond the standard choice of Shannon's mutual information to measure the dependence between the input and the output. Our main result shows that it is indeed possible to replace the mutual information by any strongly convex function of the joint input-output distribution, with the subgaussianity condition on the losses replaced by a bound on an appropriately chosen norm capturing the geometry of the dependence measure. This allows us to derive a range of generalization bounds that are either entirely new or strengthen previously known ones. Examples include bounds stated in terms of p-norm divergences and the Wasserstein-2 distance, which are respectively applicable for heavy-tailed loss distributions and highly smooth loss functions. Our analysis is entirely based on elementary tools from convex analysis by tracking the growth of a potential function associated with the dependence measure and the loss function."

--- Last tag is almost certainly too ambitious...]]></description>
<dc:subject>to:NB learning_theory information_theory convexity to_teach:childs_garden_of_statistical_learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:113aa8fd4ed1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:convexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2204.01119">
    <title>[2204.01119] Fitting an immersed submanifold to data via Sussmann's orbit theorem</title>
    <dc:date>2022-08-04T14:50:37+00:00</dc:date>
    <link>https://arxiv.org/abs/2204.01119</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper describes an approach for fitting an immersed submanifold of a finite-dimensional Euclidean space to random samples. The reconstruction mapping from the ambient space to the desired submanifold is implemented as a composition of an encoder that maps each point to a tuple of (positive or negative) times and a decoder given by a composition of flows along finitely many vector fields starting from a fixed initial point. The encoder supplies the times for the flows. The encoder-decoder map is obtained by empirical risk minimization, and a high-probability bound is given on the excess risk relative to the minimum expected reconstruction error over a given class of encoder-decoder maps. The proposed approach makes fundamental use of Sussmann's orbit theorem, which guarantees that the image of the reconstruction map is indeed contained in an immersed submanifold."]]></description>
<dc:subject>to:NB to_read re:codename:catherine_wheel manifold_learning learning_theory raginsky.maxim</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:21a9eb190fb7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:codename:catherine_wheel"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:manifold_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:raginsky.maxim"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2112.03626">
    <title>[2112.03626] Phase transitions in nonparametric regressions: a curse of exploiting higher degree smoothness assumptions in finite samples</title>
    <dc:date>2022-07-25T17:15:55+00:00</dc:date>
    <link>https://arxiv.org/abs/2112.03626</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["When the regression function belongs to a smooth class consisting of univariate functions with derivatives up to the (γ+1)th order bounded in absolute values for a finite γ, it is generally viewed that exploiting higher degree smoothness assumptions helps reduce the estimation error. This paper shows that the minimax optimal mean integrated squared error (MISE) increases in γ when the sample size n is small relative to the order of (γ+1)2γ+3, and decreases in γ when n is large relative to the order of (γ+1)2γ+3. In particular, this phase transition property is shown to be achieved by common nonparametric procedures. Consider γ1 and γ2 such that γ1<γ2, where the (γ2+1)th degree smoothness class is a subset of the (γ1+1)th degree class. What is surprising about our results is that they imply, if n is small relative to the order of (γ1+1)2γ1+3, the optimal rate achieved by the estimator constrained to be in the smoother class (to exploit the (γ2+1)th degree smoothness) is slower. In data sets with fewer than hundreds-of-thousands observations, our results suggest that one should not exploit beyond the third or fourth degree of smoothness. To some extent, our results provide a theoretical basis for the widely adopted practical recommendations given by Gelman and Imbens (2019).
"The building blocks of our minimax optimality results are a set of metric entropy bounds we develop in this paper for smooth function classes. Some of our bounds are original, and some of them improve and/or generalize the ones in the literature."

--- This is really surprising to me, so I ought to see what makes it work.  (On the plus side, if right, it makes me feel better about not teaching The Kids about higher-order smoothness assumptions!)]]></description>
<dc:subject>in_NB regression nonparametrics minimax learning_theory statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e1ba3a57ef77/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:minimax"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://jmlr.org/papers/v23/20-644.html">
    <title>Data-Derived Weak Universal Consistency</title>
    <dc:date>2022-07-19T13:56:11+00:00</dc:date>
    <link>https://jmlr.org/papers/v23/20-644.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many current applications in data science need rich model classes to adequately represent the statistics that may be driving the observations. Such rich model classes may be too complex to admit uniformly consistent estimators. In such cases, it is conventional to settle for estimators with guarantees on convergence rate where the performance can be bounded in a model-dependent way, i.e. pointwise consistent estimators. But this viewpoint has the practical drawback that estimator performance is a function of the unknown model within the model class that is being estimated. Even if an estimator is consistent, how well it is doing at any given time may not be clear, no matter what the sample size of the observations. In these cases, a line of analysis favors sample dependent guarantees. We explore this framework by studying rich model classes that may only admit pointwise consistency guarantees, yet enough information about the unknown model driving the observations needed to gauge estimator accuracy can be inferred from the sample at hand. In this paper we obtain a novel characterization of lossless compression problems over a countable alphabet in the data-derived framework in terms of what we term deceptive distributions. We also show that the ability to estimate the redundancy of compressing memoryless sources is equivalent to learning the underlying single-letter marginal in a data-derived fashion. We expect that the methodology underlying such characterizations in a data-derived estimation framework will be broadly applicable to a wide range of estimation problems, enabling a more systematic approach to data-derived guarantees."

--- Last tag is contingent on reading it and liking it, of course.  
]]></description>
<dc:subject>in_NB learning_theory statistics information_theory to_read to_teach:childs_garden_of_statistical_learning_theory</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7ba350217b53/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2202.04415">
    <title>[2202.04415] Towards Empirical Process Theory for Vector-Valued Functions: Metric Entropy of Smooth Function Classes</title>
    <dc:date>2022-06-13T17:00:24+00:00</dc:date>
    <link>https://arxiv.org/abs/2202.04415</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper provides some first steps in developing empirical process theory for functions taking values in a vector space. Our main results provide bounds on the entropy of classes of smooth functions taking values in a Hilbert space, by leveraging theory from differential calculus of vector-valued functions and fractal dimension theory of metric spaces. We demonstrate how these entropy bounds can be used to show the uniform law of large numbers and asymptotic equicontinuity of the function classes, and also apply it to statistical learning theory in which the output space is a Hilbert space. We conclude with a discussion on the extension of Rademacher complexities to vector-valued function classes."]]></description>
<dc:subject>to:NB learning_theory empirical_processes hilbert_space via:?</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fe711e83cc23/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:empirical_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hilbert_space"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:?"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2206.03515">
    <title>[2206.03515] How does overparametrization affect performance on minority groups?</title>
    <dc:date>2022-06-09T08:51:42+00:00</dc:date>
    <link>https://arxiv.org/abs/2206.03515</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The benefits of overparameterization for the overall performance of modern machine learning (ML) models are well known. However, the effect of overparameterization at a more granular level of data subgroups is less understood. Recent empirical studies demonstrate encouraging results: (i) when groups are not known, overparameterized models trained with empirical risk minimization (ERM) perform better on minority groups; (ii) when groups are known, ERM on data subsampled to equalize group sizes yields state-of-the-art worst-group-accuracy in the overparameterized regime. In this paper, we complement these empirical studies with a theoretical investigation of the risk of overparameterized random feature models on minority groups. In a setting in which the regression functions for the majority and minority groups are different, we show that overparameterization always improves minority group performance."]]></description>
<dc:subject>to:NB learning_theory random_features algorithmic_fairness re:codename:one_law_for_the_lion_and_ox_is_oppression</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:bac4cf470627/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_features"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:algorithmic_fairness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:codename:one_law_for_the_lion_and_ox_is_oppression"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2205.01593">
    <title>[2205.01593] Causal Regularization: On the trade-off between in-sample risk and out-of-sample risk guarantees</title>
    <dc:date>2022-05-11T16:49:40+00:00</dc:date>
    <link>https://arxiv.org/abs/2205.01593</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In recent decades, a number of ways of dealing with causality in practice, such as propensity score matching, the PC algorithm and invariant causal prediction, have been introduced. Besides its interpretational appeal, the causal model provides the best out-of-sample prediction guarantees. In this paper, we study the identification of causal-like models from in-sample data that provide out-of-sample risk guarantees when predicting a target variable from a set of covariates.
"Whereas ordinary least squares provides the best in-sample risk with limited out-of-sample guarantees, causal models have the best out-of-sample guarantees but achieve an inferior in-sample risk. By defining a trade-off of these properties, we introduce causal regularization. As the regularization is increased, it provides estimators whose risk is more stable across sub-samples at the cost of increasing their overall in-sample risk. The increased risk stability is shown to lead to out-of-sample risk guarantees. We provide finite sample risk bounds for all models and prove the adequacy of cross-validation for attaining these bounds."]]></description>
<dc:subject>to:NB causal_inference learning_theory prediction</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b92b191c8fa9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:causal_inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.4.013201">
    <title>Phys. Rev. Research 4, 013201 (2022) - Memorizing without overfitting: Bias, variance, and interpolation in overparameterized models</title>
    <dc:date>2022-05-10T13:14:41+00:00</dc:date>
    <link>https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.4.013201</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The bias-variance trade-off is a central concept in supervised learning. In classical statistics, increasing the complexity of a model (e.g., number of parameters) reduces bias but also increases variance. Until recently, it was commonly believed that optimal performance is achieved at intermediate model complexities which strike a balance between bias and variance. Modern deep learning methods flout this dogma, achieving state-of-the-art performance using “overparameterized models” where the number of fit parameters is large enough to perfectly fit the training data. As a result, understanding bias and variance in overparameterized models has emerged as a fundamental problem in machine learning. Here, we use methods from statistical physics to derive analytic expressions for bias and variance in two minimal models of overparameterization (linear regression and two-layer neural networks with nonlinear data distributions), allowing us to disentangle properties stemming from the model architecture and random sampling of data. In both models, increasing the number of fit parameters leads to a phase transition where the training error goes to zero and the test error diverges as a result of the variance (while the bias remains finite). Beyond this threshold, the test error of the two-layer neural network decreases due to a monotonic decrease in both the bias and variance as opposed to the classical bias-variance trade-off. We also show that in contrast with classical intuition, overparameterized models can overfit even in the absence of noise and exhibit bias even if the student and teacher models match. We synthesize these results to construct a holistic understanding of generalization error and the bias-variance trade-off in overparameterized models and relate our results to random matrix theory."

--- Not best-pleased to discover that the whole thing is an 18 pp. abstract of the supplementary materials, but I'll tackle those next, because the claimed results are cool.]]></description>
<dc:subject>learning_theory linear_regression neural_networks via:rvenkat in_NB random_features of_course_its_really_a_spin_glass interpolation_aka_memorizing_the_training_data have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:8af8a18b4806/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:linear_regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:rvenkat"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_features"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:of_course_its_really_a_spin_glass"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interpolation_aka_memorizing_the_training_data"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2103.14108">
    <title>[2103.14108] The Geometry of Over-parameterized Regression and Adversarial Perturbations</title>
    <dc:date>2022-05-10T13:13:10+00:00</dc:date>
    <link>https://arxiv.org/abs/2103.14108</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Classical regression has a simple geometric description in terms of a projection of the training labels onto the column space of the design matrix. However, for over-parameterized models -- where the number of fit parameters is large enough to perfectly fit the training data -- this picture becomes uninformative. Here, we present an alternative geometric interpretation of regression that applies to both under- and over-parameterized models. Unlike the classical picture which takes place in the space of training labels, our new picture resides in the space of input features. This new feature-based perspective provides a natural geometric interpretation of the double-descent phenomenon in the context of bias and variance, explaining why it can occur even in the absence of label noise. Furthermore, we show that adversarial perturbations -- small perturbations to the input features that result in large changes in label values -- are a generic feature of biased models, arising from the underlying geometry. We demonstrate these ideas by analyzing three minimal models for over-parameterized linear least squares regression: without basis functions (input features equal model features) and with linear or nonlinear basis functions (two-layer neural networks with linear or nonlinear activation functions, respectively)."]]></description>
<dc:subject>to:NB linear_regression neural_networks learning_theory your_favorite_deep_neural_network_sucks via:rvenkat adversarial_examples</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:af2e2e202d0c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:linear_regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:your_favorite_deep_neural_network_sucks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:rvenkat"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:adversarial_examples"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2204.02909v1">
    <title>[2204.02909v1] A Short Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists</title>
    <dc:date>2022-04-25T13:27:49+00:00</dc:date>
    <link>https://arxiv.org/abs/2204.02909v1</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This tutorial is based on lecture notes written for a class taught in the Statistics Department at Stanford in the Winter Quarter of 2017. The objective was to provide a working knowledge of some of the techniques developed over the last 40 years by theoretical physicists and mathematicians to study mean field spin glasses and their applications to high-dimenensional statistics and statistical learning."

--- Curious to see if I'm still physicist enough to find this frustrating!

--- Published version: [https://doi.org/10.1561/2200000105]]]></description>
<dc:subject>to_read spin_glasses statistical_mechanics learning_theory high-dimensional_statistics montanari.andrea via:rvenkat in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2b39f37fa8bf/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spin_glasses"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistical_mechanics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:high-dimensional_statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:montanari.andrea"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:rvenkat"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.jmlr.org/papers/v23/20-644.html">
    <title>Data-Derived Weak Universal Consistency</title>
    <dc:date>2022-03-27T15:54:29+00:00</dc:date>
    <link>https://www.jmlr.org/papers/v23/20-644.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many current applications in data science need rich model classes to adequately represent the statistics that may be driving the observations. Such rich model classes may be too complex to admit uniformly consistent estimators. In such cases, it is conventional to settle for estimators with guarantees on convergence rate where the performance can be bounded in a model-dependent way, i.e. pointwise consistent estimators. But this viewpoint has the practical drawback that estimator performance is a function of the unknown model within the model class that is being estimated. Even if an estimator is consistent, how well it is doing at any given time may not be clear, no matter what the sample size of the observations. In these cases, a line of analysis favors sample dependent guarantees. We explore this framework by studying rich model classes that may only admit pointwise consistency guarantees, yet enough information about the unknown model driving the observations needed to gauge estimator accuracy can be inferred from the sample at hand. In this paper we obtain a novel characterization of lossless compression problems over a countable alphabet in the data-derived framework in terms of what we term deceptive distributions. We also show that the ability to estimate the redundancy of compressing memoryless sources is equivalent to learning the underlying single-letter marginal in a data-derived fashion. We expect that the methodology underlying such characterizations in a data-derived estimation framework will be broadly applicable to a wide range of estimation problems, enabling a more systematic approach to data-derived guarantees."

]]></description>
<dc:subject>to:NB learning_theory information_theory to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c0172f9b465c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://direct.mit.edu/rest/article-abstract/101/5/743/58556/Choosing-among-Regularized-Estimators-in-Empirical?redirectedFrom=fulltext">
    <title>Choosing among Regularized Estimators in Empirical Economics: The Risk of Machine Learning | The Review of Economics and Statistics | MIT Press</title>
    <dc:date>2022-03-14T18:19:21+00:00</dc:date>
    <link>https://direct.mit.edu/rest/article-abstract/101/5/743/58556/Choosing-among-Regularized-Estimators-in-Empirical?redirectedFrom=fulltext</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many settings in empirical economics involve estimation of a large number of parameters. In such settings, methods that combine regularized estimation and data-driven choices of regularization parameters are useful. We provide guidance to applied researchers on the choice between regularized estimators and data-driven selection of regularization parameters. We characterize the risk and relative performance of regularized estimators as a function of the data-generating process and show that data-driven choices of regularization parameters yield estimators with risk uniformly close to the risk attained under the optimal (unfeasible) choice of regularization parameters. We illustrate using examples from empirical economics."]]></description>
<dc:subject>to:NB econometrics estimation statistics learning_theory to_teach:childs_garden_of_statistical_learning_theory re:HEAS downloaded cross-validation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:765356ad4562/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:econometrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:childs_garden_of_statistical_learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:HEAS"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:downloaded"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cross-validation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2201.10408">
    <title>[2201.10408] Beyond the Frontier: Fairness Without Accuracy Loss</title>
    <dc:date>2022-03-14T18:12:52+00:00</dc:date>
    <link>https://arxiv.org/abs/2201.10408</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Notions of fair machine learning that seek to control various kinds of error across protected groups generally are cast as constrained optimization problems over a fixed model class. For such problems, tradeoffs arise: asking for various kinds of technical fairness requires compromising on overall error, and adding more protected groups increases error rates across all groups. Our goal is to break though such accuracy-fairness tradeoffs.
"We develop a simple algorithmic framework that allows us to deploy models and then revise them dynamically when groups are discovered on which the error rate is suboptimal. Protected groups don't need to be pre-specified: At any point, if it is discovered that there is some group on which our current model performs substantially worse than optimally, then there is a simple update operation that improves the error on that group without increasing either overall error or the error on previously identified groups. We do not restrict the complexity of the groups that can be identified, and they can intersect in arbitrary ways. The key insight that allows us to break through the tradeoff barrier is to dynamically expand the model class as new groups are identified. The result is provably fast convergence to a model that can't be distinguished from the Bayes optimal predictor, at least by those tasked with finding high error groups.
"We explore two instantiations of this framework: as a "bias bug bounty" design in which external auditors are invited to discover groups on which our current model's error is suboptimal, and as an algorithmic paradigm in which the discovery of groups on which the error is suboptimal is posed as an optimization problem. In the bias bounty case, when we say that a model cannot be distinguished from Bayes optimal, we mean by any participant in the bounty program. We provide both theoretical analysis and experimental validation."

--- ETA: Comments http://bactra.org/notebooks/ethics-politics-data-mining.html#beyond-the-frontier]]></description>
<dc:subject>algorithmic_fairness learning_theory roth.aaron to_teach:data-mining kearns.michael in_NB blogged</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:a6689f803747/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:algorithmic_fairness"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:roth.aaron"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kearns.michael"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:blogged"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://ieeexplore.ieee.org/abstract/document/9724643">
    <title>On Optimal Learning With Random Features | IEEE Journals &amp; Magazine | IEEE Xplore</title>
    <dc:date>2022-03-08T14:46:23+00:00</dc:date>
    <link>https://ieeexplore.ieee.org/abstract/document/9724643</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider supervised learning in a reproducing kernel Hilbert space (RKHS) using random features. We show that the optimal rate is obtained under suitable regularity conditions, and at the same time improving on the existing bounds on the number of random features required. As a straightforward extension, distributed learning in the simple setting of one-shot communication is also considered that achieves the same optimal rate."]]></description>
<dc:subject>to:NB hilbert_space learning_theory random_features</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:99f1a282aa31/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hilbert_space"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_features"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>