<?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://www.argmin.net/p/lore-laundering-machines"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2105.12806"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1805.10204"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1202.3079"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://www.argmin.net/p/lore-laundering-machines">
    <title>Lore Laundering Machines - by Ben Recht - arg min</title>
    <dc:date>2025-10-24T14:57:50+00:00</dc:date>
    <link>https://www.argmin.net/p/lore-laundering-machines</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>re:gopnikism large_language_models_(so_called) have_read recht.benjamin bubeck.sebastien re:the_singer_of_tales_and_the_house_of_intellect</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:095dd8285fcb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:gopnikism"/>
	<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:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:recht.benjamin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bubeck.sebastien"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:the_singer_of_tales_and_the_house_of_intellect"/>
</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/1805.10204">
    <title>[1805.10204] Adversarial examples from computational constraints</title>
    <dc:date>2018-05-29T16:35:21+00:00</dc:date>
    <link>https://arxiv.org/abs/1805.10204</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Why are classifiers in high dimension vulnerable to "adversarial" perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due to computational constraints. 
"First we prove that, for a broad set of classification tasks, the mere existence of a robust classifier implies that it can be found by a possibly exponential-time algorithm with relatively few training examples. Then we give a particular classification task where learning a robust classifier is computationally intractable. More precisely we construct a binary classification task in high dimensional space which is (i) information theoretically easy to learn robustly for large perturbations, (ii) efficiently learnable (non-robustly) by a simple linear separator, (iii) yet is not efficiently robustly learnable, even for small perturbations, by any algorithm in the statistical query (SQ) model. This example gives an exponential separation between classical learning and robust learning in the statistical query model. It suggests that adversarial examples may be an unavoidable byproduct of computational limitations of learning algorithms."]]></description>
<dc:subject>adversarial_examples computational_complexity machine_learning classifiers have_read bubeck.sebastien in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:350dcb0c5a44/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:adversarial_examples"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:computational_complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:classifiers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1202.3079">
    <title>[1202.3079] Towards minimax policies for online linear optimization with bandit feedback</title>
    <dc:date>2012-02-15T13:24:07+00:00</dc:date>
    <link>http://arxiv.org/abs/1202.3079</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order $sqrt{d n log N}$ for any finite action set with $N$ actions, under the assumption that the instantaneous loss is bounded by 1. This shaves off an extraneous $sqrt{d}$ factor compared to previous works, and gives a regret bound of order $d sqrt{n log n}$ for any compact set of actions. Without further assumptions on the action set, this last bound is minimax optimal up to a logarithmic factor. Interestingly, our result also shows that the minimax regret for bandit linear optimization with expert advice in $d$ dimension is the same as for the basic $d$-armed bandit with expert advice. Our second contribution is to show how to use the Mirror Descent algorithm to obtain computationally efficient strategies with minimax optimal regret bounds in specific examples. More precisely we study two canonical action sets: the hypercube and the Euclidean ball. In the former case, we obtain the first computationally efficient algorithm with a $d sqrt{n}$ regret, thus improving by a factor $sqrt{d log n}$ over the best known result for a computationally efficient algorithm. In the latter case, our approach gives the first algorithm with a $sqrt{d n log n}$ regret, again shaving off an extraneous $sqrt{d}$ compared to previous works."]]></description>
<dc:subject>online_learning decision_theory optimization re:growing_ensemble_project cesa-bianchi.nicolo kakade.sham bubeck.sebastien in_NB bandit_problems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d3172d33e293/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:decision_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kakade.sham"/>
	<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:bandit_problems"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>