<?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://doi.org/10.1108/FTCIT-09-2025-0149"/>
	<rdf:li rdf:resource="https://hdsr.mitpress.mit.edu/pub/qixx99zn/release/1"/>
	<rdf:li rdf:resource="https://doi.org/10.1111/rssb.12425"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2003.10409"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.05442"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.07492"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.05207"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.02187"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1901.08082"/>
	<rdf:li rdf:resource="http://onlinelibrary.wiley.com/doi/10.1111/jtsa.12237/abstract"/>
	<rdf:li rdf:resource="http://www.mitpressjournals.org/doi/abs/10.1162/NECO_a_00906"/>
	<rdf:li rdf:resource="http://onlinelibrary.wiley.com/doi/10.1111/jofi.12121/abstract"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.02592"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1409.0031"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1407.3334"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1402.2594"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1307.8187"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1305.2505"/>
	<rdf:li rdf:resource="http://www.cas.mcmaster.ca/~gk/courses/Sarah/Incremental%20Clustering.pdf"/>
	<rdf:li rdf:resource="http://cseweb.ucsd.edu/~dasgupta/291/lec6.pdf"/>
	<rdf:li rdf:resource="http://www.cs.ucla.edu/~jenn/papers/lmsrcomplexity.pdf"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1208.3728"/>
	<rdf:li rdf:resource="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&amp;tid=13029"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1207.1965"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1206.6408"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1206.4633"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1206.4604"/>
	<rdf:li rdf:resource="http://www-stat.wharton.upenn.edu/~rakhlin/courses/stat928/stat928_notes.pdf"/>
	<rdf:li rdf:resource="http://www.cs.cmu.edu/~ggordon/calliess-gordon-aamas.pdf"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1204.5721"/>
	<rdf:li rdf:resource="http://www.nowpublishers.com/product.aspx?product=MAL&amp;doi=2200000018"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1202.3323"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/0810.3023"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1202.3079"/>
	<rdf:li rdf:resource="http://jmlr.csail.mit.edu/papers/v9/warmuth08a.html"/>
	<rdf:li rdf:resource="http://www.princeton.edu/~sbubeck/BubeckLectureNotes.pdf"/>
	<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://arxiv.org/abs/1112.0076"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1111.6082"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1110.6416"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1108.3154"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1107.4080"/>
	<rdf:li rdf:resource="http://jmlr.csail.mit.edu/papers/v12/vyugin11a.html"/>
	<rdf:li rdf:resource="http://infostructuralist.wordpress.com/2010/11/05/divergence-in-everything-bounding-the-regret-in-online-optimization/"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1327806"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1005.2296"/>
	<rdf:li rdf:resource="http://people.ee.duke.edu/~willett/papers/raginsky_marcia_silva_willett_ISIT09.pdf"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/0812.3973"/>
	<rdf:li rdf:resource="http://jmlr.csail.mit.edu/papers/v9/amit08a.html"/>
      </rdf:Seq>
    </items>
  </channel><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://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://doi.org/10.1111/rssb.12425">
    <title>AMF: Aggregated Mondrian forests for online learning - Mourtada - - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library</title>
    <dc:date>2021-05-20T13:53:05+00:00</dc:date>
    <link>https://doi.org/10.1111/rssb.12425</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Random forest (RF) is one of the algorithms of choice in many supervised learning applications, be it classification or regression. The appeal of such tree-ensemble methods comes from a combination of several characteristics: a remarkable accuracy in a variety of tasks, a small number of parameters to tune, robustness with respect to features scaling, a reasonable computational cost for training and prediction, and their suitability in high-dimensional settings. The most commonly used RF variants, however, are ‘offline’ algorithms, which require the availability of the whole dataset at once. In this paper, we introduce AMF, an online RF algorithm based on Mondrian Forests. Using a variant of the context tree weighting algorithm, we show that it is possible to efficiently perform an exact aggregation over all prunings of the trees; in particular, this enables to obtain a truly online parameter-free algorithm which is competitive with the optimal pruning of the Mondrian tree, and thus adaptive to the unknown regularity of the regression function. Numerical experiments show that AMF is competitive with respect to several strong baselines on a large number of datasets for multi-class classification."]]></description>
<dc:subject>to:NB to_read ensemble_methods random_forests regression classifiers to_teach:data-mining online_learning statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:42bd56d40bd2/</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:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_forests"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:classifiers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2003.10409">
    <title>[2003.10409] Online stochastic gradient descent on non-convex losses from high-dimensional inference</title>
    <dc:date>2021-05-12T18:27:24+00:00</dc:date>
    <link>https://arxiv.org/abs/2003.10409</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Stochastic gradient descent (SGD) is a popular algorithm for optimization problems arising in high-dimensional inference tasks. Here one produces an estimator of an unknown parameter from independent samples of data by iteratively optimizing a loss function. This loss function is random and often non-convex. We study the performance of the simplest version of SGD, namely online SGD, from a random start in the setting where the parameter space is high-dimensional.
"We develop nearly sharp thresholds for the number of samples needed for consistent estimation as one varies the dimension. Our thresholds depend only on an intrinsic property of the population loss which we call the information exponent. In particular, our results do not assume uniform control on the loss itself, such as convexity or uniform derivative bounds. The thresholds we obtain are polynomial in the dimension and the precise exponent depends explicitly on the information exponent. As a consequence of our results, we find that except for the simplest tasks, almost all of the data is used simply in the initial search phase to obtain non-trivial correlation with the ground truth. Upon attaining non-trivial correlation, the descent is rapid and exhibits law of large numbers type behavior.
"We illustrate our approach by applying it to a wide set of inference tasks such as phase retrieval, and parameter estimation for generalized linear models, online PCA, and spiked tensor models, as well as to supervised learning for single-layer networks with general activation functions."]]></description>
<dc:subject>optimization online_learning in_NB high-dimensional_statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e393fddff281/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:high-dimensional_statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.05442">
    <title>[1909.05442] Nonstationary Nonparametric Online Learning: Balancing Dynamic Regret and Model Parsimony</title>
    <dc:date>2019-10-29T21:56:45+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.05442</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["An open challenge in supervised learning is \emph{conceptual drift}: a data point begins as classified according to one label, but over time the notion of that label changes. Beyond linear autoregressive models, transfer and meta learning address drift, but require data that is representative of disparate domains at the outset of training. To relax this requirement, we propose a memory-efficient \emph{online} universal function approximator based on compressed kernel methods. Our approach hinges upon viewing non-stationary learning as online convex optimization with dynamic comparators, for which performance is quantified by dynamic regret.
"Prior works control dynamic regret growth only for linear models. In contrast, we hypothesize actions belong to reproducing kernel Hilbert spaces (RKHS). We propose a functional variant of online gradient descent (OGD) operating in tandem with greedy subspace projections. Projections are necessary to surmount the fact that RKHS functions have complexity proportional to time.
"For this scheme, we establish sublinear dynamic regret growth in terms of both loss variation and functional path length, and that the memory of the function sequence remains moderate. Experiments demonstrate the usefulness of the proposed technique for online nonlinear regression and classification problems with non-stationary data."]]></description>
<dc:subject>to:NB non-stationarity time_series online_learning statistics re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:20b6b272a1d4/</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:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.07492">
    <title>[1909.07492] On-line Non-Convex Constrained Optimization</title>
    <dc:date>2019-09-24T05:24:57+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.07492</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Time-varying non-convex continuous-valued non-linear constrained optimization is a fundamental problem. We study conditions wherein a momentum-like regularising term allow for the tracking of local optima by considering an ordinary differential equation (ODE). We then derive an efficient algorithm based on a predictor-corrector method, to track the ODE solution."]]></description>
<dc:subject>to:NB dynamical_systems optimization online_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7dd2191b3db5/</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:dynamical_systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.05207">
    <title>[1909.05207] Introduction to Online Convex Optimization</title>
    <dc:date>2019-09-15T17:21:31+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.05207</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This manuscript portrays optimization as a process. In many practical applications the environment is so complex that it is infeasible to lay out a comprehensive theoretical model and use classical algorithmic theory and mathematical optimization. It is necessary as well as beneficial to take a robust approach, by applying an optimization method that learns as one goes along, learning from experience as more aspects of the problem are observed. This view of optimization as a process has become prominent in varied fields and has led to some spectacular success in modeling and systems that are now part of our daily lives."]]></description>
<dc:subject>to:NB optimization convexity online_learning low-regret_learning hazan.elad</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:8296f9fd7e3e/</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:convexity"/>
	<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:hazan.elad"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.02187">
    <title>[1909.02187] More Adaptive Algorithms for Tracking the Best Expert</title>
    <dc:date>2019-09-10T16:37:08+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.02187</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper, we consider the problem of prediction with expert advice in dynamic environments. We choose tracking regret as the performance metric and derive novel data-dependent bounds by developing two adaptive algorithms. The first algorithm achieves a second-order tracking regret bound, which improves existing first-order bounds. The second algorithm enjoys a path-length bound, which is generally incomparable to the second-order bound but offers advantages in slowly moving environments. Both algorithms are developed under the online mirror descent framework and draw inspiration from existing algorithms that attain data-dependent bounds of static regret. The key idea is to use a clipped simplex in the updating step of online mirror descent. Finally, we extend our algorithms and analysis to the problem of online matrix prediction and provide the first data-dependent tracking regret bound for this problem."]]></description>
<dc:subject>to:NB online_learning low-regret_learning re:growing_ensemble_project to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4d09227a4513/</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:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</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://onlinelibrary.wiley.com/doi/10.1111/jtsa.12237/abstract">
    <title>A Robbins–Monro Algorithm for Non-Parametric Estimation of NAR Process with Markov Switching: Consistency - Fermin - 2017 - Journal of Time Series Analysis - Wiley Online Library</title>
    <dc:date>2017-04-27T17:27:07+00:00</dc:date>
    <link>http://onlinelibrary.wiley.com/doi/10.1111/jtsa.12237/abstract</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We approach the problem of non-parametric estimation for autoregressive Markov switching processes. In this context, the Nadaraya–Watson-type regression functions estimator is interpreted as a solution of a local weighted least-square problem, which does not admit a closed-form solution in the case of hidden Markov switching. We introduce a non-parametric recursive algorithm to approximate the estimator. Our algorithm restores the missing data by means of a Monte Carlo step and estimates the regression function via a Robbins–Monro step. We prove that non-parametric autoregressive models with Markov switching are identifiable when the hidden Markov process has a finite state space. Consistency of the estimator is proved using the strong α-mixing property of the model. Finally, we present some simulations illustrating the performances of our non-parametric estimation procedure."]]></description>
<dc:subject>time_series stochastic_approximation statistics online_learning markov_models state-space_models in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0b80a5c10fa1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:markov_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:state-space_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.mitpressjournals.org/doi/abs/10.1162/NECO_a_00906">
    <title>Online Reinforcement Learning Using a Probability Density Estimation | Neural Computation | MIT Press Journals</title>
    <dc:date>2017-01-17T13:23:30+00:00</dc:date>
    <link>http://www.mitpressjournals.org/doi/abs/10.1162/NECO_a_00906</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Function approximation in online, incremental, reinforcement learning needs to deal with two fundamental problems: biased sampling and nonstationarity. In this kind of task, biased sampling occurs because samples are obtained from specific trajectories dictated by the dynamics of the environment and are usually concentrated in particular convergence regions, which in the long term tend to dominate the approximation in the less sampled regions. The nonstationarity comes from the recursive nature of the estimations typical of temporal difference methods. This nonstationarity has a local profile, varying not only along the learning process but also along different regions of the state space. We propose to deal with these problems using an estimation of the probability density of samples represented with a gaussian mixture model. To deal with the nonstationarity problem, we use the common approach of introducing a forgetting factor in the updating formula. However, instead of using the same forgetting factor for the whole domain, we make it dependent on the local density of samples, which we use to estimate the nonstationarity of the function at any given input point. To address the biased sampling problem, the forgetting factor applied to each mixture component is modulated according to the new information provided in the updating, rather than forgetting depending only on time, thus avoiding undesired distortions of the approximation in less sampled regions."]]></description>
<dc:subject>to:NB online_learning density_estimation statistics reinforcement_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e05b3a828630/</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:density_estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:reinforcement_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://onlinelibrary.wiley.com/doi/10.1111/jofi.12121/abstract">
    <title>Sequential Learning, Predictability, and Optimal Portfolio Returns - JOHANNES - 2014 - The Journal of Finance - Wiley Online Library</title>
    <dc:date>2016-12-01T20:13:09+00:00</dc:date>
    <link>http://onlinelibrary.wiley.com/doi/10.1111/jofi.12121/abstract</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper finds statistically and economically significant out-of-sample portfolio benefits for an investor who uses models of return predictability when forming optimal portfolios. Investors must account for estimation risk, and incorporate an ensemble of important features, including time-varying volatility, and time-varying expected returns driven by payout yield measures that include share repurchase and issuance. Prior research documents a lack of benefits to return predictability, and our results suggest that this is largely due to omitting time-varying volatility and estimation risk. We also document the sequential process of investors learning about parameters, state variables, and models as new data arrive."]]></description>
<dc:subject>to:NB finance prediction time_series online_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:290a269e6015/</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:finance"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.02592">
    <title>[1507.02592] Fast rates in statistical and online learning</title>
    <dc:date>2015-08-05T14:42:40+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.02592</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The pursuit of fast rates in online and statistical learning has led to the conception of many conditions in learning theory under which fast learning is possible. We show that most of these conditions are special cases of a single, unifying condition, that comes in two forms: the central condition for 'proper' learning algorithms that always output a hypothesis in the given model, and stochastic mixability for online algorithms that may make predictions outside of the model. We show that, under surprisingly weak conditions, both conditions are, in a certain sense, equivalent. The central condition has a re-interpretation in terms of convexity of a set of pseudoprobabilities, linking it to density estimation under misspecification. For bounded losses, we show how the central condition enables a direct proof of fast rates and we prove its equivalence to the Bernstein condition, itself a generalization of the Tsybakov-Mammen margin condition, which has played a central role in obtaining fast rates in statistical learning. Yet, while the Bernstein condition is two-sided, the central condition is one-sided, making it more suitable to deal with unbounded losses. In its stochastic mixability form, our condition generalizes both a stochastic exp-concavity condition identified by Juditsky, Rigollet and Tsybakov, and Vovk's notion of mixability. Our unifying conditions thus provide a significant step towards a characterization of fast rates in statistical learning, similar to how classical mixability characterizes constant regret in the sequential prediction with expert advice setting."]]></description>
<dc:subject>to:NB learning_theory low-regret_learning grunwald.peter williamson.robert_c. reid.mark online_learning 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:9a9575fa6302/</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:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:grunwald.peter"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:williamson.robert_c."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:reid.mark"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<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="http://arxiv.org/abs/1409.0031">
    <title>[1409.0031] Tracking Dynamic Point Processes on Networks</title>
    <dc:date>2015-01-23T12:52:34+00:00</dc:date>
    <link>http://arxiv.org/abs/1409.0031</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Cascading chains of events are a salient feature of many real-world social, biological, and financial networks. In social networks, social reciprocity accounts for retaliations in gang interactions, proxy wars in nation-state conflicts, or Internet memes shared via social media. Neuron spikes stimulate or inhibit spike activity in other neurons. Stock market shocks can trigger a contagion of volatility throughout a financial network. In these and other examples, only individual events associated with network nodes are observed, usually without knowledge of the underlying dynamic relationships between nodes. This paper addresses the challenge of tracking how events within such networks stimulate or influence future events. The proposed approach is an online learning framework well-suited to streaming data, using a multivariate Hawkes point process model to encapsulate autoregressive features of observed events within the social network. Recent work on online learning in dynamic environments is leveraged not only to exploit the dynamics within the underlying network, but also to track that network structure as it evolves. Regret bounds and experimental results demonstrate that the proposed method performs nearly as well as an oracle or batch algorithm."]]></description>
<dc:subject>network_data_analysis point_processes time_series online_learning statistics willett.rebecca_m. in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:657579f08ffc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:point_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:willett.rebecca_m."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1407.3334">
    <title>[1407.3334] Offline to Online Conversion</title>
    <dc:date>2015-01-20T01:20:13+00:00</dc:date>
    <link>http://arxiv.org/abs/1407.3334</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider the problem of converting offline estimators into an online predictor or estimator with small extra regret. Formally this is the problem of merging a collection of probability measures over strings of length 1,2,3,... into a single probability measure over infinite sequences. We describe various approaches and their pros and cons on various examples. As a side-result we give an elementary non-heuristic purely combinatoric derivation of Turing's famous estimator. Our main technical contribution is to determine the computational complexity of online estimators with good guarantees in general."]]></description>
<dc:subject>to:NB information_theory statistics learning_theory online_learning hutter.marcus</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c4d013debd91/</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_theory"/>
	<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:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hutter.marcus"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1402.2594">
    <title>[1402.2594] Online Nonparametric Regression</title>
    <dc:date>2014-02-20T00:56:00+00:00</dc:date>
    <link>http://arxiv.org/abs/1402.2594</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We establish optimal rates for online regression for arbitrary classes of regression functions in terms of the sequential entropy introduced in (Rakhlin, Sridharan, Tewari, 2010). The optimal rates are shown to exhibit a phase transition analogous to the i.i.d./statistical learning case, studied in (Rakhlin, Sridharan, Tsybakov 2013). In the frequently encountered situation when sequential entropy and i.i.d. empirical entropy match, our results point to the interesting phenomenon that the rates for statistical learning with squared loss and online nonparametric regression are the same. 
"In addition to a non-algorithmic study of minimax regret, we exhibit a generic forecaster that enjoys the established optimal rates. We also provide a recipe for designing online regression algorithms that can be computationally efficient. We illustrate the techniques by deriving existing and new forecasters for the case of finite experts and for online linear regression."]]></description>
<dc:subject>to:NB regression online_learning nonparametrics statistics rakhlin.alexander to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c2fb63c1b188/</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:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:rakhlin.alexander"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1307.8187">
    <title>[1307.8187] Online Learning with Unknown Time Horizon</title>
    <dc:date>2013-09-03T13:21:35+00:00</dc:date>
    <link>http://arxiv.org/abs/1307.8187</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider online learning when the time horizon is unknown. We apply a minimax analysis, beginning with the fixed horizon case, and then moving on to two unknown-horizon settings, one that assumes the horizon is chosen randomly according to some known distribution, and the other which allows the adversary full control over the horizon. For the random horizon setting with restricted losses, we derive a fully optimal minimax algorithm. And for the adversarial horizon setting, we prove a nontrivial lower bound which shows that the adversary obtains strictly more power than when the horizon is fixed and known. Based on the minimax solution of the random horizon setting, we then propose a new adaptive algorithm which "pretends" that the horizon is drawn from a distribution from a special family, but no matter how the actual horizon is chosen, the worst-case regret is of the optimal rate. Furthermore, our algorithm can be generalized in many ways, including handling other unknown information and other online learning settings. Experiments show that our algorithm outperforms many other existing algorithms in an online linear optimization setting."]]></description>
<dc:subject>re:growing_ensemble_project online_learning low-regret_learning machine_learning learning_theory to_read schapire.robert_e. in_NB entableted</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:76c3b8b1ad09/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<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:machine_learning"/>
	<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:schapire.robert_e."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:entableted"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1305.2505">
    <title>[1305.2505] On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions</title>
    <dc:date>2013-05-15T15:44:47+00:00</dc:date>
    <link>http://arxiv.org/abs/1305.2505</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper, we study the generalization properties of online learning based stochastic methods for supervised learning problems where the loss function is dependent on more than one training sample (e.g., metric learning, ranking). We present a generic decoupling technique that enables us to provide Rademacher complexity-based generalization error bounds. Our bounds are in general tighter than those obtained by Wang et al (COLT 2012) for the same problem. Using our decoupling technique, we are further able to obtain fast convergence rates for strongly convex pairwise loss functions. We are also able to analyze a class of memory efficient online learning algorithms for pairwise learning problems that use only a bounded subset of past training samples to update the hypothesis at each step. Finally, in order to complement our generalization bounds, we propose a novel memory efficient online learning algorithm for higher order learning problems with bounded regret guarantees."]]></description>
<dc:subject>relational_learning machine_learning learning_theory online_learning low-regret_learning to_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4d13d2a90b7f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:relational_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<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:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cas.mcmaster.ca/~gk/courses/Sarah/Incremental%20Clustering.pdf">
    <title>INCREMENTAL CLUSTERING AND DYNAMIC INFORMATION RETRIEVAL</title>
    <dc:date>2013-04-04T18:06:05+00:00</dc:date>
    <link>http://www.cas.mcmaster.ca/~gk/courses/Sarah/Incremental%20Clustering.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model called incremental clustering which is based on a careful analysis of the requirements of the information retrieval application, and which should also be useful in other applications. The goal is to efficiently maintain clusters of small diameter as new points are inserted. We analyze several natural greedy algorithms and demonstrate that they perform poorly. We propose new deterministic and randomized incremental clustering algorithms which have a provably good performance, and which we believe should also perform well in practice. We complement our positive results with lower bounds on the performance of incremental algorithms. Finally, we consider the dual clustering problem where the clusters are of fixed diameter, and the goal is to minimize the number of clusters."]]></description>
<dc:subject>to:NB clustering online_learning computational_complexity machine_learning information_retrieval to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ffcfdd7bc20f/</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:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<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:information_retrieval"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://cseweb.ucsd.edu/~dasgupta/291/lec6.pdf">
    <title>Lecture 6 — Online and streaming algorithms for clustering</title>
    <dc:date>2013-04-04T18:05:18+00:00</dc:date>
    <link>http://cseweb.ucsd.edu/~dasgupta/291/lec6.pdf</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>to_read online_learning clustering machine_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:187eaebf31bf/</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:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cs.ucla.edu/~jenn/papers/lmsrcomplexity.pdf">
    <title>Complexity of Combinatorial Market Makers</title>
    <dc:date>2012-10-01T12:33:19+00:00</dc:date>
    <link>http://www.cs.ucla.edu/~jenn/papers/lmsrcomplexity.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We analyze the computational complexity of market maker pricing algorithms for combinatorial prediction markets. We focus on Hanson’s popular logarithmic market scoring rule market maker (LMSR). Our goal is to implicitly main- tain correct LMSR prices across an exponentially large out- come space. We examine both permutation combinatorics, where outcomes are permutations of objects, and Boolean combinatorics, where outcomes are combinations of binary events. We look at three restrictive languages that limit what traders can bet on. Even with severely limited lan- guages, we find that LMSR pricing is #P-hard, even when the same language admits polynomial-time matching with- out the market maker. We then propose an approximation technique for pricing permutation markets based on an al- gorithm for online permutation learning. The connections we draw between LMSR pricing and the literature on online learning with expert advice may be of independent interest."]]></description>
<dc:subject>to_read computational_complexity economics via:nikete online_learning approximation in_NB re:in_soviet_union_optimization_problem_solves_you</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b7b0c2f61b15/</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:computational_complexity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:economics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:nikete"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:in_soviet_union_optimization_problem_solves_you"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1208.3728">
    <title>[1208.3728] Online Learning with Predictable Sequences</title>
    <dc:date>2012-08-24T11:27:03+00:00</dc:date>
    <link>http://arxiv.org/abs/1208.3728</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We present methods for online linear optimization that take advantage of benign (as opposed to worst-case) sequences. Specifically if the sequence encountered by the learner is described well by a known "predictable process", the algorithms presented enjoy tighter bounds as compared to the typical worst case bounds. Additionally, the methods achieve the usual worst-case regret bounds if the sequence is not benign. Our approach can be seen as a way of adding prior knowledge about the sequence within the paradigm of online learning. The setting is shown to encompass partial and side information. Variance and path-length bounds can be seen as particular examples of online learning with simple predictable sequences. 
"We further extend our methods and results to include competing with a set of possible predictable processes (models), that is "learning" the predictable process itself concurrently with using it to obtain better regret guarantees. We show that such model selection is possible under various assumptions on the available feedback. Our results suggest a promising direction of further research with potential applications to stock market and time series prediction."]]></description>
<dc:subject>online_learning learning_theory machine_learning time_series re:AoS_project rakhlin.alexander low-regret_learning in_NB heard_the_talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f9c66b95f97b/</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:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:AoS_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:rakhlin.alexander"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heard_the_talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&amp;tid=13029">
    <title>Foundations of Machine Learning - The MIT Press</title>
    <dc:date>2012-08-15T16:03:13+00:00</dc:date>
    <link>http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&amp;tid=13029</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This graduate-level textbook introduces fundamental concepts and methods in machine learning. It describes several important modern algorithms, provides the theoretical underpinnings of these algorithms, and illustrates key aspects for their application. The authors aim to present novel theoretical tools and concepts while giving concise proofs even for relatively advanced topics.
"Foundations of Machine Learning fills the need for a general textbook that also offers theoretical details and an emphasis on proofs. Certain topics that are often treated with insufficient attention are discussed in more detail here; for example, entire chapters are devoted to regression, multi-class classification, and ranking. The first three chapters lay the theoretical foundation for what follows, but each remaining chapter is mostly self-contained. The appendix offers a concise probability review, a short introduction to convex optimization, tools for concentration bounds, and several basic properties of matrices and norms used in the book.
"The book is intended for graduate students and researchers in machine learning, statistics, and related areas; it can be used either as a textbook or as a reference text for a research seminar."

Review: http://bactra.org/reviews/foml.html]]></description>
<dc:subject>machine_learning learning_theory statistics in_NB books:recommended kernel_methods regression classifiers online_learning grammar_induction dimension_reduction reinforcement_learning books:reviewed books:owned</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:66002e8be186/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<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:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:recommended"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kernel_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:classifiers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:grammar_induction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:dimension_reduction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:reinforcement_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:reviewed"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:owned"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1207.1965">
    <title>[1207.1965] Forecasting electricity consumption by aggregating specialized experts</title>
    <dc:date>2012-07-10T10:31:56+00:00</dc:date>
    <link>http://arxiv.org/abs/1207.1965</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider the setting of sequential prediction of arbitrary sequences based on specialized experts. We first provide a review of the relevant literature and present two theoretical contributions: a general analysis of the specialist aggregation rule of Freund et al. (1997) and an adaptation of fixed-share rules of Herbster and Warmuth (1998) in this setting. We then apply these rules to the sequential short-term (one-day-ahead) forecasting of electricity consumption; to do so, we consider two data sets, a Slovakian one and a French one, respectively concerned with hourly and half-hourly predictions. We follow a general methodology to perform the stated empirical studies and detail in particular tuning issues of the learning parameters. The introduced aggregation rules demonstrate an improved accuracy on the data sets at hand; the improvements lie in a reduced mean squared error but also in a more robust behavior with respect to large occasional errors."]]></description>
<dc:subject>have_read individual_sequence_prediction online_learning mixture_models machine_learning prediction re:growing_ensemble_project in_NB to:blog</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:aeab63e18d74/</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:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixture_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:blog"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1206.6408">
    <title>[1206.6408] Sequential Nonparametric Regression</title>
    <dc:date>2012-07-09T18:13:08+00:00</dc:date>
    <link>http://arxiv.org/abs/1206.6408</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We present algorithms for nonparametric regression in settings where the data are obtained sequentially. While traditional estimators select bandwidths that depend upon the sample size, for sequential data the effective sample size is dynamically changing. We propose a linear time algorithm that adjusts the bandwidth for each new data point, and show that the estimator achieves the optimal minimax rate of convergence. We also propose the use of online expert mixing algorithms to adapt to unknown smoothness of the regression function. We provide simulations that confirm the theoretical results, and demonstrate the effectiveness of the methods."]]></description>
<dc:subject>regression online_learning statistics nonparametrics in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c8851921daf7/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1206.4633">
    <title>[1206.4633] Fast Bounded Online Gradient Descent Algorithms for Scalable Kernel-Based Online Learning</title>
    <dc:date>2012-06-23T13:54:42+00:00</dc:date>
    <link>http://arxiv.org/abs/1206.4633</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Kernel-based online learning has often shown state-of-the-art performance for many online learning tasks. It, however, suffers from a major shortcoming, that is, the unbounded number of support vectors, making it non-scalable and unsuitable for applications with large-scale datasets. In this work, we study the problem of bounded kernel-based online learning that aims to constrain the number of support vectors by a predefined budget. Although several algorithms have been proposed in literature, they are neither computationally efficient due to their intensive budget maintenance strategy nor effective due to the use of simple Perceptron algorithm. To overcome these limitations, we propose a framework for bounded kernel-based online learning based on an online gradient descent approach. We propose two efficient algorithms of bounded online gradient descent (BOGD) for scalable kernel-based online learning: (i) BOGD by maintaining support vectors using uniform sampling, and (ii) BOGD++ by maintaining support vectors using non-uniform sampling. We present theoretical analysis of regret bound for both algorithms, and found promising empirical performance in terms of both efficacy and efficiency by comparing them to several well-known algorithms for bounded kernel-based online learning on large-scale datasets."]]></description>
<dc:subject>to:NB kernel_methods online_learning machine_learning optimization low-regret_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:804ac705229f/</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:kernel_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1206.4604">
    <title>[1206.4604] Learning the Experts for Online Sequence Prediction</title>
    <dc:date>2012-06-23T13:45:07+00:00</dc:date>
    <link>http://arxiv.org/abs/1206.4604</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Online sequence prediction is the problem of predicting the next element of a sequence given previous elements. This problem has been extensively studied in the context of individual sequence prediction, where no prior assumptions are made on the origin of the sequence. Individual sequence prediction algorithms work quite well for long sequences, where the algorithm has enough time to learn the temporal structure of the sequence. However, they might give poor predictions for short sequences. A possible remedy is to rely on the general model of prediction with expert advice, where the learner has access to a set of $r$ experts, each of which makes its own predictions on the sequence. It is well known that it is possible to predict almost as well as the best expert if the sequence length is order of $log(r)$. But, without firm prior knowledge on the problem, it is not clear how to choose a small set of {em good} experts. In this paper we describe and analyze a new algorithm that learns a good set of experts using a training set of previously observed sequences. We demonstrate the merits of our approach by applying it on the task of click prediction on the web."]]></description>
<dc:subject>to_read re:growing_ensemble_project individual_sequence_prediction machine_learning time_series online_learning in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:8e7e455d30c4/</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:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www-stat.wharton.upenn.edu/~rakhlin/courses/stat928/stat928_notes.pdf">
    <title>Statistical Learning Theory and Sequential Prediction</title>
    <dc:date>2012-06-05T12:24:22+00:00</dc:date>
    <link>http://www-stat.wharton.upenn.edu/~rakhlin/courses/stat928/stat928_notes.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[Rakhlin + Sridharan; apparently (?) the summer tome for the statistical learning reading group.]]></description>
<dc:subject>to_read statistics machine_learning learning_theory optimization learning_in_games low-regret_learning individual_sequence_prediction regression classifiers empirical_processes ensemble_methods online_learning in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:92e251d24aeb/</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:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<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:learning_in_games"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:classifiers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:empirical_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cs.cmu.edu/~ggordon/calliess-gordon-aamas.pdf">
    <title>No-Regret Learning and a Mechanism for Distributed Multiagent Planning</title>
    <dc:date>2012-05-08T12:37:20+00:00</dc:date>
    <link>http://www.cs.cmu.edu/~ggordon/calliess-gordon-aamas.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We develop a novel mechanism for coordinated, distributed multiagent planning. We consider problems stated as a col- lection of single-agent planning problems coupled by com- mon soft constraints on resource consumption. (Resources may be real or fictitious, the latter introduced as a tool for factoring the problem). A key idea is to recast the dis- tributed planning problem as learning in a repeated game between the original agents and a newly introduced group of adversarial agents who influence prices for the resources. The adversarial agents benefit from arbitrage: that is, their incentive is to uncover violations of the resource usage con- straints and, by selfishly adjusting prices, encourage the original agents to avoid plans that cause such violations. If all agents employ no-regret learning algorithms in the course of this repeated interaction, we are able to show that our mechanism can achieve design goals such as social op- timality (efficiency), budget balance, and Nash-equilibrium convergence to within an error which approaches zero as the agents gain experience. In particular, the agents’ average plans converge to a socially optimal solution for the original planning task. We present experiments in a simulated net- work routing domain demonstrating our method’s ability to reliably generate sound plans."]]></description>
<dc:subject>online_learning economics markets_as_collective_calculating_devices re:knightian_uncertainty gordon.geoff to:NB low-regret_learning re:in_soviet_union_optimization_problem_solves_you</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:579ed235a9b9/</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:economics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:markets_as_collective_calculating_devices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:knightian_uncertainty"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:gordon.geoff"/>
	<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:re:in_soviet_union_optimization_problem_solves_you"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1204.5721">
    <title>[1204.5721] Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems</title>
    <dc:date>2012-04-26T03:12:16+00:00</dc:date>
    <link>http://arxiv.org/abs/1204.5721</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Multi-armed bandit problems are the most basic examples of sequential decision problems with an exploration-exploitation trade-off. This is the balance between staying with the option that gave highest payoffs in the past and exploring new options that might give higher payoffs in the future. Although the study of bandit problems dates back to the Thirties, exploration-exploitation trade-offs arise in several modern applications, such as ad placement, website optimization, and packet routing. Mathematically, a multi-armed bandit is defined by the payoff process associated with each option. In this survey, we focus on two extreme cases in which the analysis of regret is particularly simple and elegant: i.i.d. payoffs and adversarial payoffs. Besides the basic setting of finitely many actions, we also analyze some of the most important variants and extensions, such as the contextual bandit model."]]></description>
<dc:subject>to:NB individual_sequence_prediction online_learning bandit_problems re:knightian_uncertainty low-regret_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:631fe225f62c/</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:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bandit_problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:knightian_uncertainty"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.nowpublishers.com/product.aspx?product=MAL&amp;doi=2200000018">
    <title>Online Learning and Online Convex Optimization</title>
    <dc:date>2012-03-30T14:24:09+00:00</dc:date>
    <link>http://www.nowpublishers.com/product.aspx?product=MAL&amp;doi=2200000018</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Online learning is a well established learning paradigm which has both theoretical and practical appeals. The goal of online learning is to make a sequence of accurate predictions given knowledge of the correct answer to previous prediction tasks and possibly additional available information. Online learning has been studied in several research fields including game theory, information theory, and machine learning. It also became of great interest to practitioners due the recent emergence of large scale applications such as online advertisement placement and online web ranking. In this survey we provide a modern overview of online learning. Our goal is to give the reader a sense of some of the interesting ideas and in particular to underscore the centrality of convexity in deriving efficient online learning algorithms. We do not mean to be comprehensive but rather to give a high-level, rigorous yet easy to follow, survey."

Ungated version (via shivak): http://www.cs.huji.ac.il/~shais/papers/OLsurvey.pdf]]></description>
<dc:subject>online_learning individual_sequence_prediction optimization learning_theory machine_learning learning_in_games low-regret_learning in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c9de70393195/</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:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_in_games"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<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.3323">
    <title>[1202.3323] A new look at shifting regret</title>
    <dc:date>2012-02-29T18:16:29+00:00</dc:date>
    <link>http://arxiv.org/abs/1202.3323</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[We investigate extensions of well-known online learning algorithms such as fixed-share of Herbster and Warmuth (1998) or the methods proposed by Bousquet and Warmuth (2002). These algorithms use weight sharing schemes to perform as well as the best sequence of experts with a limited number of changes. Here we show, with a common, general, and simpler analysis, that weight sharing in fact achieves much more than what it was designed for. We use it to simultaneously prove new shifting regret bounds for online convex optimization on the simplex in terms of the total variation distance as well as new bounds for the related setting of adaptive regret. Finally, we exhibit the first logarithmic shifting bounds for exp-concave loss functions on the simplex.]]></description>
<dc:subject>online_learning to_read individual_sequence_prediction non-stationarity re:growing_ensemble_project in_NB low-regret_learning have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ade1de531f10/</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:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<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:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/0810.3023">
    <title>[0810.3023] Iterated Regret Minimization: A More Realistic Solution Concept</title>
    <dc:date>2012-02-15T15:53:34+00:00</dc:date>
    <link>http://arxiv.org/abs/0810.3023</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["For some well-known games, such as the Traveler's Dilemma or the Centipede Game, traditional game-theoretic solution concepts--and most notably Nash equilibrium--predict outcomes that are not consistent with empirical observations. In this paper, we introduce a new solution concept, iterated regret minimization, which exhibits the same qualitative behavior as that observed in experiments in many games of interest, including Traveler's Dilemma, the Centipede Game, Nash bargaining, and Bertrand competition. As the name suggests, iterated regret minimization involves the iterated deletion of strategies that do not minimize regret."

--- Quite astonishingly, no mention at all of low-regret learning!]]></description>
<dc:subject>game_theory online_learning have_read in_NB halpern.joseph_y. re:knightian_uncertainty low-regret_learning</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ec42f726a8be/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:game_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<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:li rdf:resource="https://pinboard.in/u:cshalizi/t:halpern.joseph_y."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:knightian_uncertainty"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
</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://jmlr.csail.mit.edu/papers/v9/warmuth08a.html">
    <title>Randomized Online PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension</title>
    <dc:date>2012-02-05T18:57:40+00:00</dc:date>
    <link>http://jmlr.csail.mit.edu/papers/v9/warmuth08a.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We design an online algorithm for Principal Component Analysis. In each trial the current instance is centered and projected into a probabilistically chosen low dimensional subspace. The regret of our online algorithm, that is, the total expected quadratic compression loss of the online algorithm minus the total quadratic compression loss of the batch algorithm, is bounded by a term whose dependence on the dimension of the instances is only logarithmic.
"We first develop our methodology in the expert setting of online learning by giving an algorithm for learning as well as the best subset of experts of a certain size. This algorithm is then lifted to the matrix setting where the subsets of experts correspond to subspaces. The algorithm represents the uncertainty over the best subspace as a density matrix whose eigenvalues are bounded. The running time is O(n2) per trial, where n is the dimension of the instances."]]></description>
<dc:subject>to:NB online_learning dimension_reduction machine_learning learning_theory warmuth.manfred principal_components low-regret_learning random_projections</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:53e62cb05d95/</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:dimension_reduction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:warmuth.manfred"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:principal_components"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_projections"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.princeton.edu/~sbubeck/BubeckLectureNotes.pdf">
    <title>Introduction to Online Optimization (Bubeck)</title>
    <dc:date>2011-12-23T21:22:29+00:00</dc:date>
    <link>http://www.princeton.edu/~sbubeck/BubeckLectureNotes.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["to_teach" tag a sudden brainstorm for how to make next year's statistical computing class either unbeatably awesome or an absolute disaster]]></description>
<dc:subject>online_learning regression individual_sequence_prediction optimization machine_learning learning_theory via:mraginsky to_read to_teach:statcomp re:freshman_seminar_on_optimization in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5b8e6bad6c1d/</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:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<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:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:statcomp"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:freshman_seminar_on_optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</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://arxiv.org/abs/1112.0076">
    <title>[1112.0076] Bandit Market Makers</title>
    <dc:date>2011-12-03T18:47:40+00:00</dc:date>
    <link>http://arxiv.org/abs/1112.0076</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a flexible framework for profit-seeking market making by combining cost function based automated market makers with bandit learning algorithms. The key idea is to consider each parametrisation of the cost function as a bandit arm, and the minimum expected profits from trades executed during a period as the rewards. This allows for the creation of market makers that can adjust liquidity and bid-asks spreads dynamically to maximise profits."]]></description>
<dc:subject>to:NB online_learning financial_markets della_penna.nicholas bandit_problems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:504c414c8369/</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:financial_markets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:della_penna.nicholas"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bandit_problems"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1111.6082">
    <title>[1111.6082] Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints</title>
    <dc:date>2011-12-01T14:38:37+00:00</dc:date>
    <link>http://arxiv.org/abs/1111.6082</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>online_learning optimization low-regret_learning in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0ac32e6e3a19/</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:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1110.6416">
    <title>[1110.6416] Adaptive Hedge</title>
    <dc:date>2011-10-31T01:35:45+00:00</dc:date>
    <link>http://arxiv.org/abs/1110.6416</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Most methods for decision-theoretic online learning are based on the Hedge algorithm, which takes a parameter called the learning rate. In most previous analyses the learning rate was carefully tuned to obtain optimal worst-case performance, leading to suboptimal performance on easy instances, for example when there exists an action that is significantly better than all others. We propose a new way of setting the learning rate, which adapts to the difficulty of the learning problem: in the worst case our procedure still guarantees optimal performance, but on easy instances it achieves much smaller regret. In particular, our adaptive method achieves constant regret in a probabilistic setting, when there exists an action that on average obtains strictly smaller loss than all other actions. We also provide a simulation study comparing our approach to existing methods."]]></description>
<dc:subject>to_read re:growing_ensemble_project online_learning prediction grunwald.peter low-regret_learning in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5a4a6e4a2df0/</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:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:grunwald.peter"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1108.3154">
    <title>[1108.3154] Stability Conditions for Online Learnability</title>
    <dc:date>2011-08-17T13:30:39+00:00</dc:date>
    <link>http://arxiv.org/abs/1108.3154</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>stability_of_learning online_learning in_NB to_read learning_theory low-regret_learning</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4aaade82738f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stability_of_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_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:low-regret_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1107.4080">
    <title>[1107.4080] On the Universality of Online Mirror Descent</title>
    <dc:date>2011-07-21T13:19:32+00:00</dc:date>
    <link>http://arxiv.org/abs/1107.4080</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We show that for a general class of convex online learning problems, Mirror Descent can always achieve a (nearly) optimal regret guarantee."
]]></description>
<dc:subject>optimization learning_theory online_learning low-regret_learning</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1a51f37e822f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://jmlr.csail.mit.edu/papers/v12/vyugin11a.html">
    <title>Online Learning in Case of Unbounded Losses Using Follow the Perturbed Leader Algorithm</title>
    <dc:date>2011-02-04T07:36:05+00:00</dc:date>
    <link>http://jmlr.csail.mit.edu/papers/v12/vyugin11a.html</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>individual_sequence_prediction online_learning learning_theory re:growing_ensemble_project in_NB low-regret_learning</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cd208d1b9202/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://infostructuralist.wordpress.com/2010/11/05/divergence-in-everything-bounding-the-regret-in-online-optimization/">
    <title>Divergence in everything: bounding the regret in online optimization « The Information Structuralist</title>
    <dc:date>2010-11-21T23:05:18+00:00</dc:date>
    <link>http://infostructuralist.wordpress.com/2010/11/05/divergence-in-everything-bounding-the-regret-in-online-optimization/</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>information_theory individual_sequence_prediction online_learning raginsky.maxim have_read</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d63f6e631541/</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:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:raginsky.maxim"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1327806">
    <title>IEEE Xplore - On the generalization ability of on-line learning algorithms</title>
    <dc:date>2010-07-01T14:15:30+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1327806</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["how to extract a hypothesis with small risk from the ensemble of hypotheses generated by an arbitrary on-line learning algorithm run on [IID data]. ... a simple large deviation argument [proves] tight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic Mn associated with the on-line performance of the ensemble. Via sharp pointwise bounds on Mn, we then obtain risk tail bounds for kernel perceptron algorithms in terms of the spectrum of the empirical kernel matrix. ... A distinctive feature of our approach is that the key tools for our analysis come from the model of prediction of individual sequences; i.e., a model making no probabilistic assumptions on the source generating the data. In fact, these tools turn out to be so powerful that we only need very elementary statistical facts to obtain our final risk bounds."  Bounced off this 2004; try again.
]]></description>
<dc:subject>learning_theory large_deviations online_learning individual_sequence_prediction via:djm1107 re:your_favorite_dsge_sucks re:XV_for_mixing ensemble_methods have_read low-regret_learning</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:45e79ffb4005/</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:large_deviations"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:djm1107"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:your_favorite_dsge_sucks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:XV_for_mixing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ensemble_methods"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1005.2296">
    <title>[1005.2296] Online Learning of Noisy Data with Kernels</title>
    <dc:date>2010-05-14T16:25:26+00:00</dc:date>
    <link>http://arxiv.org/abs/1005.2296</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study online learning when individual instances are corrupted by random noise. We assume the noise distribution is unknown, and may change over time with no restriction other than having zero mean and bounded variance. Our technique relies on a family of unbiased estimators for non-linear functions, which may be of independent interest. We show that a variant of online gradient descent can learn functions in any dot-product (e.g., polynomial) or Gaussian kernel space with any analytic convex loss function. Our variant uses randomized estimates that need to query a random number of noisy copies of each instance, where with high probability this number is upper bounded by a constant. Allowing such multiple queries cannot be avoided: Indeed, we show that online learning is in general impossible when only one noisy copy of each instance can be accessed."
]]></description>
<dc:subject>learning_theory regression online_learning kernel_methods</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9a3253ef1032/</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:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kernel_methods"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://people.ee.duke.edu/~willett/papers/raginsky_marcia_silva_willett_ISIT09.pdf">
    <title>Sequential Probability Assignment Via Online Convex Programming Using Exponential Families (Raginsky, Marcia, Silva and Willett)</title>
    <dc:date>2009-10-27T04:26:29+00:00</dc:date>
    <link>http://people.ee.duke.edu/~willett/papers/raginsky_marcia_silva_willett_ISIT09.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[Today's seminar.  Very cool.
]]></description>
<dc:subject>have_read statistics statistical_inference_for_stochastic_processes exponential_families information_theory prediction minimax optimization to:blog raginsky.maxim online_learning in_NB willett.rebecca_m. low-regret_learning</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ccb45ba35efd/</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:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistical_inference_for_stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:exponential_families"/>
	<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:minimax"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:blog"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:raginsky.maxim"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:willett.rebecca_m."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/0812.3973">
    <title>[0812.3973] Revisiting R\'ev\'esz's stochastic approximation method for the estimation of a regression function</title>
    <dc:date>2009-01-01T21:11:16+00:00</dc:date>
    <link>http://arxiv.org/abs/0812.3973</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[A recursive/on-line kernel regression estimator, with proofs that it's about as efficient as the off-line/batch-mode Nadaraya-Watson estimator.  Sounds cool...
]]></description>
<dc:subject>nonparametrics regression stochastic_approximation online_learning to_read to_teach:data-mining kernel_smoothing</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:3001f6797c78/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kernel_smoothing"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://jmlr.csail.mit.edu/papers/v9/amit08a.html">
    <title>Online Learning of Complex Prediction Problems Using Simultaneous Projections</title>
    <dc:date>2008-07-31T21:35:47+00:00</dc:date>
    <link>http://jmlr.csail.mit.edu/papers/v9/amit08a.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["framework for online classification where each online trial consists of multiple prediction tasks that are tied together"
]]></description>
<dc:subject>machine_learning classifiers prediction online_learning to_read</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:529a0bd11e6a/</dc:identifier>
<taxo:topics><rdf:Bag>	<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:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>