<?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.annualreviews.org/doi/abs/10.1146/annurev-statistics-040620-035329"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1901.08082"/>
	<rdf:li rdf:resource="http://jmlr.org/papers/v14/cesa-bianchi13a.html"/>
	<rdf:li rdf:resource="http://jmlr.org/proceedings/papers/v30/Gofer13.html"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1212.5637"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1202.3079"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=6094243&amp;arnumber=6015553&amp;tag=1"/>
	<rdf:li rdf:resource="http://www.labyrinthbooks.com/sale_detail.aspx?isbn=9780521841085"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://www.annualreviews.org/doi/abs/10.1146/annurev-statistics-040620-035329">
    <title>Online Learning Algorithms | Annual Review of Statistics and Its Application</title>
    <dc:date>2020-12-18T18:47:12+00:00</dc:date>
    <link>https://www.annualreviews.org/doi/abs/10.1146/annurev-statistics-040620-035329</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Online learning is a framework for the design and analysis of algorithms that build predictive models by processing data one at the time. Besides being computationally efficient, online algorithms enjoy theoretical performance guarantees that do not rely on statistical assumptions on the data source. In this review, we describe some of the most important algorithmic ideas behind online learning and explain the main mathematical tools for their analysis. Our reference framework is online convex optimization, a sequential version of convex optimization within which most online algorithms are formulated. More specifically, we provide an in-depth description of online mirror descent and follow the regularized leader, two of the most fundamental algorithms in online learning. As the tuning of parameters is a typically difficult task in sequential data analysis, in the last part of the review we focus on coin-betting, an information-theoretic approach to the design of parameter-free online algorithms with good theoretical guarantees."]]></description>
<dc:subject>to:NB low-regret_learning cesa-bianchi.nicolo information_theory prediction 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:3d76a7d2f1d0/</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:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<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/1901.08082">
    <title>[1901.08082] Cooperative Online Learning: Keeping your Neighbors Updated</title>
    <dc:date>2019-05-29T19:56:48+00:00</dc:date>
    <link>https://arxiv.org/abs/1901.08082</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study an asynchronous online learning setting with a network of agents. At each time step, some of the agents are activated, requested to make a prediction, and pay the corresponding loss. The loss function is then revealed to these agents and also to their neighbors in the network. When activations are stochastic, we show that the regret achieved by N agents running the standard Online Mirror Descent is (αT‾‾‾√), where T is the horizon and α≤N is the independence number of the network. This is in contrast to the regret Ω(NT‾‾‾√) which N agents incur in the same setting when feedback is not shared. We also show a matching lower bound of order αT‾‾‾√ that holds for any given network. When the pattern of agent activations is arbitrary, the problem changes significantly: we prove a Ω(T) lower bound on the regret that holds for any online algorithm oblivious to the feedback source."]]></description>
<dc:subject>to:NB social_learning online_learning low-regret_learning learning_theory cesa-bianchi.nicolo monteleoni.claire to_read re:democratic_cognition</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9b0852a6a733/</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:social_learning"/>
	<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:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:monteleoni.claire"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:democratic_cognition"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://jmlr.org/papers/v14/cesa-bianchi13a.html">
    <title>Random Spanning Trees and the Prediction of Weighted Graphs</title>
    <dc:date>2013-06-10T16:29:10+00:00</dc:date>
    <link>http://jmlr.org/papers/v14/cesa-bianchi13a.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in expectation the optimal mistake bound on any polynomially connected weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant expected amortized time and linear space. Experiments on real-world data sets show that our method compares well to both global (Perceptron) and local (label propagation) methods, while being generally faster in practice."]]></description>
<dc:subject>to:NB network_data_analysis prediction low-regret_learning cesa-bianchi.nicolo gentile.claudio</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1d06e823d1e4/</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:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:gentile.claudio"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://jmlr.org/proceedings/papers/v30/Gofer13.html">
    <title>Regret Minimization for Branching Experts</title>
    <dc:date>2013-05-25T13:41:51+00:00</dc:date>
    <link>http://jmlr.org/proceedings/papers/v30/Gofer13.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study regret minimization bounds in which the dependence on the number of experts is replaced by measures of the realized complexity of the expert class. The measures we consider are defined in retrospect given the realized losses. We concentrate on two interesting cases. In the first, our measure of complexity is the number of different “leading experts”, namely, experts that were best at some point in time. We derive regret bounds that depend only on this measure, independent of the total number of experts. We also consider a case where all experts remain grouped in just a few clusters in terms of their realized cumulative losses. Here too, our regret bounds depend only on the number of clusters determined in retrospect, which serves as a measure of complexity. Our results are obtained as special cases of a more general analysis for a setting of branching experts, where the set of experts may grow over time according to a tree-like structure, determined by an adversary. For this setting of branching experts, we give algorithms and analysis that cover both the full information and the bandit scenarios."]]></description>
<dc:subject>to_read low-regret_learning machine_learning bandit_problems re:growing_ensemble_project cesa-bianchi.nicolo in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6a6d53de54af/</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:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bandit_problems"/>
	<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:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1212.5637">
    <title>[1212.5637] Random Spanning Trees and the Prediction of Weighted Graphs</title>
    <dc:date>2012-12-27T18:40:57+00:00</dc:date>
    <link>http://arxiv.org/abs/1212.5637</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We investigate the problem of sequentially predicting the binary labels on the nodes of an arbitrary weighted graph. We show that, under a suitable parametrization of the problem, the optimal number of prediction mistakes can be characterized (up to logarithmic factors) by the cutsize of a random spanning tree of the graph. The cutsize is induced by the unknown adversarial labeling of the graph nodes. In deriving our characterization, we obtain a simple randomized algorithm achieving in expectation the optimal mistake bound on any polynomially connected weighted graph. Our algorithm draws a random spanning tree of the original graph and then predicts the nodes of this tree in constant expected amortized time and linear space. Experiments on real-world datasets show that our method compares well to both global (Perceptron) and local (label propagation) methods, while being generally faster in practice."]]></description>
<dc:subject>to:NB classifiers network_data_analysis machine_learning cesa-bianchi.nicolo</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b53ac46892d9/</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:classifiers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
</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>
<item rdf:about="http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=6094243&amp;arnumber=6015553&amp;tag=1">
    <title>IEEE Xplore - Online Learning of Noisy Data</title>
    <dc:date>2011-12-06T21:58:47+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=6094243&amp;arnumber=6015553&amp;tag=1</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study online learning of linear and kernel-based predictors, when individual examples are corrupted by random noise, and both examples and noise type can be chosen adversarially and change over time. We begin with the setting where some auxiliary information on the noise distribution is provided, and we wish to learn predictors with respect to the squared loss. Depending on the auxiliary information, we show how one can learn linear and kernel-based predictors, using just 1 or 2 noisy copies of each example. We then turn to discuss a general setting where virtually nothing is known about the noise distribution, and one wishes to learn with respect to general losses and using linear and kernel-based predictors. We show how this can be achieved using a random, essentially constant number of noisy copies of each example. Allowing multiple copies cannot be avoided: Indeed, we show that the setting becomes impossible when only one noisy copy of each instance can be accessed. To obtain our results we introduce several novel techniques, some of which might be of independent interest."]]></description>
<dc:subject>to:NB online_learning filtering kernel_methods machine_learning cesa-bianchi.nicolo low-regret_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:07e7db063157/</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:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:filtering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kernel_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.labyrinthbooks.com/sale_detail.aspx?isbn=9780521841085">
    <title>Prediction, Learning, and Games - Cesa-Bianch and Lugosi (@Labyrinth)</title>
    <dc:date>2008-01-07T23:34:38+00:00</dc:date>
    <link>http://www.labyrinthbooks.com/sale_detail.aspx?isbn=9780521841085</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[How to predict an individual sequence nearly as well as the best possible predictor would, without any probabilistic assumptions.
]]></description>
<dc:subject>books:recommended statistics machine_learning universal_prediction information_theory learning_in_games cesa-bianchi.nicolo lugosi.gabor</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:201890caa2e0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:recommended"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:universal_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_in_games"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:lugosi.gabor"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>