<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (cshalizi)</title>
    <link>https://pinboard.in/u:cshalizi/public/</link>
    <description>recent bookmarks from cshalizi</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://arxiv.org/abs/2307.16895"/>
	<rdf:li rdf:resource="https://www.journals.uchicago.edu/doi/abs/10.1086/711587"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1910.10873"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.05442"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.02187"/>
	<rdf:li rdf:resource="http://projecteuclid.org/euclid.aos/1425398506"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1502.05934"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1409.3040"/>
	<rdf:li rdf:resource="http://www.pnas.org/content/111/Supplement_3/10826.abstract.html?etoc"/>
	<rdf:li rdf:resource="http://www.sciencedirect.com/science/article/pii/S0304407614000761"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1405.6076"/>
	<rdf:li rdf:resource="http://link.springer.com/article/10.1007/s10994-013-5418-8"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1403.3808"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1312.1277"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1310.4678"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1307.8187"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1307.5449"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1307.5944"/>
	<rdf:li rdf:resource="http://www.tandfonline.com/doi/abs/10.1080/01621459.2013.787184#.UdRPhxbPUlM"/>
	<rdf:li rdf:resource="http://jmlr.org/proceedings/papers/v30/Gofer13.html"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1304.3708"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1302.2672"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1303.0140"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1302.6927"/>
	<rdf:li rdf:resource="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1359987532"/>
	<rdf:li rdf:resource="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.bj/1358531747"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1301.1254"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1301.0534"/>
	<rdf:li rdf:resource="http://faculty.cs.gwu.edu/~cmontel/mssa11.pdf"/>
	<rdf:li rdf:resource="http://www.cs.cmu.edu/~dyogatam/Home_files/yogatama+etal.emnlp11.pdf"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1207.1965"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1206.6814"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1206.4604"/>
	<rdf:li rdf:resource="http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6191328"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1205.3845"/>
	<rdf:li rdf:resource="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1337268210"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1202.3323"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/0801.0327"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/math/0701419"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1202.4294"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1202.3079"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1201.5568"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1111.6337"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1110.6416"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1110.2755"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1110.2529"/>
	<rdf:li rdf:resource="http://pre.aps.org/abstract/PRE/v84/i4/e046702"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1103.0949"/>
	<rdf:li rdf:resource="http://jmlr.csail.mit.edu/papers/v12/vyugin11a.html"/>
	<rdf:li rdf:resource="http://pre.aps.org/abstract/PRE/v82/i5/e056206"/>
	<rdf:li rdf:resource="http://www.ncdc.noaa.gov/paleo/recons.html"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1008.4532"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1008.4232"/>
	<rdf:li rdf:resource="http://www.springerlink.com/content/68386v04t03752n1/"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/0903.2851v2"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1006.0475"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://arxiv.org/abs/2307.16895">
    <title>[2307.16895] Conformal PID Control for Time Series Prediction</title>
    <dc:date>2025-09-04T13:51:30+00:00</dc:date>
    <link>https://arxiv.org/abs/2307.16895</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the problem of uncertainty quantification for time series prediction, with the goal of providing easy-to-use algorithms with formal guarantees. The algorithms we present build upon ideas from conformal prediction and control theory, are able to prospectively model conformal scores in an online setting, and adapt to the presence of systematic errors due to seasonality, trends, and general distribution shifts. Our theory both simplifies and strengthens existing analyses in online conformal prediction. Experiments on 4-week-ahead forecasting of statewide COVID-19 death counts in the U.S. show an improvement in coverage over the ensemble forecaster used in official CDC communications. We also run experiments on predicting electricity demand, market returns, and temperature using autoregressive, Theta, Prophet, and Transformer models. We provide an extendable codebase for testing our methods and for the integration of new algorithms, data sets, and forecasting rules."]]></description>
<dc:subject>to:NB conformal_prediction time_series prediction tibshirani.ryan re:growing_ensemble_project have_skimmed</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2a99b91467ae/</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:conformal_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:tibshirani.ryan"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_skimmed"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.journals.uchicago.edu/doi/abs/10.1086/711587">
    <title>Metainduction over Unboundedly Many Prediction Methods: A Reply to Arnold and Sterkenburg | Philosophy of Science: Vol 88, No 2</title>
    <dc:date>2021-04-09T17:43:27+00:00</dc:date>
    <link>https://www.journals.uchicago.edu/doi/abs/10.1086/711587</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The universal optimality theorem for metainduction works for epistemic agents faced with a choice among finitely many prediction methods. Eckhart Arnold and Tom Sterkenburg objected that it breaks down for infinite or unboundedly growing sets of methods. In this article the metainductive approach is defended against this challenge by extending the optimality theorem (i) to unboundedly growing sets of methods whose number grows less than exponentially in time, (ii) to sequences of methods with an application to Goodman’s problem, and (iii) to infinite sets of methods whose number of predictive equivalence classes grows less than linearly in time."]]></description>
<dc:subject>to:NB to_read re:growing_ensemble_project induction philosophy_of_science</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:8581082149a2/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:induction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:philosophy_of_science"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1910.10873">
    <title>[1910.10873] Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition</title>
    <dc:date>2019-11-10T22:27:12+00:00</dc:date>
    <link>https://arxiv.org/abs/1910.10873</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the problem of switching-constrained online convex optimization (OCO), where the player has a limited number of opportunities to change her action. While the discrete analog of this online learning task has been studied extensively, previous work in the continuous setting has neither established the minimax rate nor algorithmically achieved it. We here show that T-round switching-constrained OCO with fewer than K switches has a minimax regret of Θ(TK√). In particular, it is at least T2K√ for one dimension and at least TK√ for higher dimensions. The lower bound in higher dimensions is attained by an orthogonal subspace argument. The minimax analysis in one dimension is more involved. To establish the one-dimensional result, we introduce the fugal game relaxation, whose minimax regret lower bounds that of switching-constrained OCO. We show that the minimax regret of the fugal game is at least T2K√ and thereby establish the minimax lower bound in one dimension. We next show that a mini-batching algorithm provides an O(TK√) upper bound, and therefore we conclude that the minimax regret of switching-constrained OCO is Θ(TK√) for any K. This is in sharp contrast to its discrete counterpart, the switching-constrained prediction-from-experts problem, which exhibits a phase transition in minimax regret between the low-switching and high-switching regimes. In the case of bandit feedback, we first determine a novel linear (in T) minimax regret for bandit linear optimization against the strongly adaptive adversary of OCO, implying that a slightly weaker adversary is appropriate. We also establish the minimax regret of switching-constrained bandit convex optimization in dimension n>2 to be Θ̃ (TK√)."]]></description>
<dc:subject>to:NB low-regret_learning non-stationarity re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:076a53edd186/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:non-stationarity"/>
	<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.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.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="http://projecteuclid.org/euclid.aos/1425398506">
    <title>Vogt , Dette : Detecting gradual changes in locally stationary processes</title>
    <dc:date>2015-03-30T00:39:04+00:00</dc:date>
    <link>http://projecteuclid.org/euclid.aos/1425398506</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In a wide range of applications, the stochastic properties of the observed time series change over time. The changes often occur gradually rather than abruptly: the properties are (approximately) constant for some time and then slowly start to change. In many cases, it is of interest to locate the time point where the properties start to vary. In contrast to the analysis of abrupt changes, methods for detecting smooth or gradual change points are less developed and often require strong parametric assumptions. In this paper, we develop a fully nonparametric method to estimate a smooth change point in a locally stationary framework. We set up a general procedure which allows us to deal with a wide variety of stochastic properties including the mean, (auto)covariances and higher moments. The theoretical part of the paper establishes the convergence rate of the new estimator. In addition, we examine its finite sample performance by means of a simulation study and illustrate the methodology by two applications to financial return data."

--- Open version: http://arxiv.org/abs/1310.4678]]></description>
<dc:subject>to_read non-stationarity re:growing_ensemble_project time_series statistics in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6c6fe391a75c/</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: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:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1502.05934">
    <title>[1502.05934] Achieving All with No Parameters: Adaptive NormalHedge</title>
    <dc:date>2015-03-02T13:17:27+00:00</dc:date>
    <link>http://arxiv.org/abs/1502.05934</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the classic online learning problem of predicting with expert advice, and propose a truly parameter-free and adaptive algorithm that achieves several objectives simultaneously without using any prior information. The main component of this work is an improved version of the NormalHedge.DT algorithm (Luo and Schapire, 2014), called AdaNormalHedge. On one hand, this new algorithm ensures small regret when the competitor has small loss and almost constant regret when the losses are stochastic. On the other hand, the algorithm is able to compete with any convex combination of the experts simultaneously, with a regret in terms of the relative entropy of the prior and the competitor. This resolves an open problem proposed by Chaudhuri et al. (2009) and Chernov and Vovk (2010). Moreover, we extend the results to the sleeping expert setting and provide two applications to illustrate the power of AdaNormalHedge: 1) competing with time-varying unknown competitors and 2) predicting almost as well as the best pruning tree. Our results on these applications significantly improve previous work from different aspects, and a special case of the first application resolves another open problem proposed by Warmuth and Koolen (2014) on whether one can simultaneously achieve optimal shifting regret for both adversarial and stochastic losses."]]></description>
<dc:subject>to:NB to_read learning_theory low-regret_learning re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0bbf76ee203c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1409.3040">
    <title>[1409.3040] Towards Optimal Algorithms for Prediction with Expert Advice</title>
    <dc:date>2014-09-11T14:49:29+00:00</dc:date>
    <link>http://arxiv.org/abs/1409.3040</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the classic problem of prediction with expert advice in the adversarial setting. Focusing on settings with a constant number of experts, we develop optimal algorithms and obtain precisely optimal regret values for the case of 2 and 3 experts. Further, we develop regret lower bounds for the multiplicative weights algorithm that exactly match the known upper bounds for an arbitrary number of experts k. This establishes a constant factor separation between the regrets achieved by the optimal algorithm and the multiplicative weights algorithm for a constant number of experts. 
"All prior work on this problem has been restricted to optimal algorithms for special cases of adversary, or, algorithms that are optimal only in the doubly asymptotic sense: when both the number of experts and the time horizon go to infinity. In contrast to these results, our algorithms are exactly optimal for the most general adversary. 
"Our main tool is the minimax principle which lets us analyze the optimal adversary to compute optimal regret values. While analyzing the optimal adversary, we establish deep connections with non-trivial aspects of random walk. We further use this connection to develop an improved regret bound for the case of 4 experts."]]></description>
<dc:subject>to_read low-regret_learning prediction minimax learning_theory re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:11e0011f5dd8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:minimax"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.pnas.org/content/111/Supplement_3/10826.abstract.html?etoc">
    <title>Recency, consistent learning, and Nash equilibrium</title>
    <dc:date>2014-07-29T15:03:39+00:00</dc:date>
    <link>http://www.pnas.org/content/111/Supplement_3/10826.abstract.html?etoc</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We examine the long-term implication of two models of learning with recency bias: recursive weights and limited memory. We show that both models generate similar beliefs and that both have a weighted universal consistency property. Using the limited-memory model we produce learning procedures that both are weighted universally consistent and converge with probability one to strict Nash equilibrium."]]></description>
<dc:subject>learning_in_games game_theory bounded_rationality non-stationarity re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d9520c5d957d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_in_games"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:game_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bounded_rationality"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://www.sciencedirect.com/science/article/pii/S0304407614000761">
    <title>Unpredictability in economic analysis, econometric modeling and forecasting</title>
    <dc:date>2014-06-27T20:32:21+00:00</dc:date>
    <link>http://www.sciencedirect.com/science/article/pii/S0304407614000761</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Unpredictability arises from intrinsic stochastic variation, unexpected instances of outliers, and unanticipated extrinsic shifts of distributions. We analyze their properties, relationships, and different effects on the three arenas in the title, which suggests considering three associated information sets. The implications of unanticipated shifts for forecasting, economic analyses of efficient markets, conditional expectations, and inter-temporal derivations are described. The potential success of general-to-specific model selection in tackling location shifts by impulse-indicator saturation is contrasted with the major difficulties confronting forecasting."]]></description>
<dc:subject>to:NB prediction non-stationarity econometrics statistics re:your_favorite_dsge_sucks re:growing_ensemble_project to_read via:djm1107</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7c82985eb9c0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:econometrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<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:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:djm1107"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1405.6076">
    <title>[1405.6076] Online Linear Optimization via Smoothing</title>
    <dc:date>2014-06-04T12:39:13+00:00</dc:date>
    <link>http://arxiv.org/abs/1405.6076</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We present a new optimization-theoretic approach to analyzing Follow-the-Leader style algorithms, particularly in the setting where perturbations are used as a tool for regularization. We show that adding a strongly convex penalty function to the decision rule and adding stochastic perturbations to data correspond to deterministic and stochastic smoothing operations, respectively. We establish an equivalence between "Follow the Regularized Leader" and "Follow the Perturbed Leader" up to the smoothness properties. This intuition leads to a new generic analysis framework that recovers and improves the previous known regret bounds of the class of algorithms commonly known as Follow the Perturbed Leader."]]></description>
<dc:subject>to:NB optimization smoothing low-regret_learning re:growing_ensemble_project tewari.ambuj via:mraginsky</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9b6c44b72573/</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:smoothing"/>
	<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:tewari.ambuj"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://link.springer.com/article/10.1007/s10994-013-5418-8">
    <title>Regret bounded by gradual variation for online convex optimization - Machine Learning</title>
    <dc:date>2014-04-07T12:12:40+00:00</dc:date>
    <link>http://link.springer.com/article/10.1007/s10994-013-5418-8</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Recently, it has been shown that the regret of the Follow the Regularized Leader (FTRL) algorithm for online linear optimization can be bounded by the total variation of the cost vectors rather than the number of rounds. In this paper, we extend this result to general online convex optimization. In particular, this resolves an open problem that has been posed in a number of recent papers. We first analyze the limitations of the FTRL algorithm as proposed by Hazan and Kale (in Machine Learning 80(2–3), 165–188, 2010) when applied to online convex optimization, and extend the definition of variation to a gradual variation which is shown to be a lower bound of the total variation. We then present two novel algorithms that bound the regret by the gradual variation of cost functions. Unlike previous approaches that maintain a single sequence of solutions, the proposed algorithms maintain two sequences of solutions that make it possible to achieve a variation-based regret bound for online convex optimization.
"To establish the main results, we discuss a lower bound for FTRL that maintains only one sequence of solutions, and a necessary condition on smoothness of the cost functions for obtaining a gradual variation bound. We extend the main results three-fold: (i) we present a general method to obtain a gradual variation bound measured by general norm; (ii) we extend algorithms to a class of online non-smooth optimization with gradual variation bound; and (iii) we develop a deterministic algorithm for online bandit optimization in multipoint bandit setting."]]></description>
<dc:subject>to_read learning_theory low-regret_learning individual_sequence_prediction optimization re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:63c75a023a08/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t: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: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:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1403.3808">
    <title>[1403.3808] Detecting Gradual Changes in Locally Stationary Processes</title>
    <dc:date>2014-03-22T19:26:38+00:00</dc:date>
    <link>http://arxiv.org/abs/1403.3808</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In a wide range of applications, the stochastic properties of the observed time series change over time. The changes often occur gradually rather than abruptly: the prop- erties are (approximately) constant for some time and then slowly start to change. In such situations, it is frequently of interest to locate the time point where the properties start to vary. In contrast to the analysis of abrupt changes, methods for detecting smooth or gradual change points are less developed and often require strong paramet- ric assumptions. In this paper, we develop a fully nonparametric method to estimate a smooth change point in a locally stationary framework. We set up a general procedure which allows to deal with a wide variety of stochastic properties including the mean, (auto)covariances and higher-order moments. The theoretical part of the paper estab- lishes the convergence rate of the new estimator. In addition, we examine its finite sample performance by means of a simulation study and illustrate the methodology by applications to temperature and financial return data."]]></description>
<dc:subject>change-point_problem non-stationarity time_series statistics re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d46ab7c9133b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:change-point_problem"/>
	<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:statistics"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1312.1277">
    <title>[1312.1277] Bandits and Experts in Metric Spaces</title>
    <dc:date>2014-01-02T17:56:44+00:00</dc:date>
    <link>http://arxiv.org/abs/1312.1277</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. The goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. 
"In this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a Lipschitz condition with respect to the metric. We refer to this problem as the "Lipschitz MAB problem". We present a solution for the multi-armed bandit problem in this setting. That is, for every metric space we define an isometry invariant which bounds from below the performance of Lipschitz MAB algorithms for this metric space, and we present an algorithm which comes arbitrarily close to meeting this bound. Furthermore, our technique gives even better results for benign payoff functions. We also address the full-feedback ("best expert") version of the problem, where after every round the payoffs from all arms are revealed."]]></description>
<dc:subject>to:NB low-regret_learning bandit_problems optimization decision_theory re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1b8cc839aa66/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bandit_problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:decision_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1310.4678">
    <title>[1310.4678] Detecting smooth changes in locally stationary processes</title>
    <dc:date>2013-10-23T19:50:24+00:00</dc:date>
    <link>http://arxiv.org/abs/1310.4678</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In a wide range of applications, the stochastic properties of the observed time series change over time. It is often realistic to assume that the properties are approximately the same over short time periods and then gradually start to vary. This behaviour is well modelled by locally stationary processes. In this paper, we investigate the question how to estimate time spans where the stochastic features of a locally stationary time series are the same. We set up a general method which allows to deal with a wide variety of features including the mean, covariances, higher moments and the distribution of the time series under consideration. In the theoretical part of the paper, we derive the asymptotic properties of our estimation method. In addition, we examine its finite sample performance by means of a simulation study and illustrate the methodology by an application to financial data."]]></description>
<dc:subject>non-stationarity time_series statistics re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7ba82472aa34/</dc:identifier>
<taxo:topics><rdf:Bag>	<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:statistics"/>
	<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: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/1307.5449">
    <title>[1307.5449] Non-stationary Stochastic Optimization</title>
    <dc:date>2013-07-26T23:55:27+00:00</dc:date>
    <link>http://arxiv.org/abs/1307.5449</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider a non-stationary variant of a sequential stochastic optimization problem, where the underlying cost functions may change along the horizon. We propose a measure, termed variation budget, that controls the extent of said change, and study how restrictions on this budget impact achievable performance. We identify sharp conditions under which it is possible to achieve lon-grun-average optimality and more refi?ned performance measures such as rate optimality that fully characterize the complexity of such problems. In doing so, we also establish a strong connection between two rather disparate strands of literature: adversarial online convex optimization; and the more traditional stochastic approximation paradigm (couched in a non-stationary setting). This connection is the key to deriving well performing policies in the latter, by leveraging structure of optimal policies in the former. Finally, tight bounds on the minimax regret allow us to quantify the "price of non-stationarity," which mathematically captures the added complexity embedded in a temporally changing environment versus a stationary one."]]></description>
<dc:subject>to_read optimization low-regret_learning re:growing_ensemble_project non-stationarity machine_learning in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5a8c89b70f44/</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:optimization"/>
	<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:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_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/1307.5944">
    <title>[1307.5944] Online Optimization in Dynamic Environments</title>
    <dc:date>2013-07-24T12:19:05+00:00</dc:date>
    <link>http://arxiv.org/abs/1307.5944</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Online optimization methods are often designed to have a total accumulated loss comparable to that achievable by some comparator, such as a batch algorithm with access to all the data and infinite computational resources. In many settings, this comparator is allowed to vary with time, and the associated "tracking regret" bounds scale with the overall variation of the comparator sequence. However, in practical scenarios ranging from motion imagery to network analysis, the environment is nonstationary and comparator sequences with small variation are quite weak, resulting in large losses. This paper describes a "dynamic mirror descent" method which addresses this challenge, yielding low regrets bounds for comparators with small deviations from a given dynamical model. This approach is then used within a broader class of online learning methods to simultaneously track the best dynamical model and form predictions based on that model. This concept is demonstrated empirically in the context of sequential compressed sensing of a dynamic scene, solar flare detection from satellite data with missing elements, and tracking a dynamic social network."]]></description>
<dc:subject>low-regret_learning non-stationarity time_series prediction individual_sequence_prediction heard_the_talk re:growing_ensemble_project have_read in_NB willett.rebecca_m.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cee6cdfb34f9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<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:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heard_the_talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<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:willett.rebecca_m."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.tandfonline.com/doi/abs/10.1080/01621459.2013.787184#.UdRPhxbPUlM">
    <title>Taylor &amp; Francis Online :: Heteroscedasticity and Autocorrelation Robust Structural Change Detection - Journal of the American Statistical Association - Volume 108, Issue 502</title>
    <dc:date>2013-07-03T16:36:41+00:00</dc:date>
    <link>http://www.tandfonline.com/doi/abs/10.1080/01621459.2013.787184#.UdRPhxbPUlM</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The assumption of (weak) stationarity is crucial for the validity of most of the conventional tests of structure change in time series. Under complicated nonstationary temporal dynamics, we argue that traditional testing procedures result in mixed structural change signals of the first and second order and hence could lead to biased testing results. The article proposes a simple and unified bootstrap testing procedure that provides consistent testing results under general forms of smooth and abrupt changes in the temporal dynamics of the time series. Monte Carlo experiments are performed to compare our testing procedure with various traditional tests. Our robust bootstrap test is applied to testing changes in an environmental and a financial time series and our procedure is shown to provide more reliable results than the conventional tests."]]></description>
<dc:subject>to:NB change-point_problem time_series bootstrap non-stationarity re:growing_ensemble_project statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2992583a29ae/</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:change-point_problem"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bootstrap"/>
	<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:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://jmlr.org/proceedings/papers/v30/Gofer13.html">
    <title>Regret Minimization for Branching Experts</title>
    <dc:date>2013-05-25T13:41:51+00:00</dc:date>
    <link>http://jmlr.org/proceedings/papers/v30/Gofer13.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study regret minimization bounds in which the dependence on the number of experts is replaced by measures of the realized complexity of the expert class. The measures we consider are defined in retrospect given the realized losses. We concentrate on two interesting cases. In the first, our measure of complexity is the number of different “leading experts”, namely, experts that were best at some point in time. We derive regret bounds that depend only on this measure, independent of the total number of experts. We also consider a case where all experts remain grouped in just a few clusters in terms of their realized cumulative losses. Here too, our regret bounds depend only on the number of clusters determined in retrospect, which serves as a measure of complexity. Our results are obtained as special cases of a more general analysis for a setting of branching experts, where the set of experts may grow over time according to a tree-like structure, determined by an adversary. For this setting of branching experts, we give algorithms and analysis that cover both the full information and the bandit scenarios."]]></description>
<dc:subject>to_read low-regret_learning machine_learning bandit_problems re:growing_ensemble_project cesa-bianchi.nicolo in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6a6d53de54af/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bandit_problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1304.3708">
    <title>[1304.3708] Advice-Efficient Prediction with Expert Advice</title>
    <dc:date>2013-04-23T18:11:18+00:00</dc:date>
    <link>http://arxiv.org/abs/1304.3708</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Advice-efficient prediction with expert advice (in analogy to label-efficient prediction) is a variant of prediction with expert advice game, where on each round of the game we are allowed to ask for advice of a limited number $M$ out of $N$ experts. This setting is especially interesting when asking for advice of every expert on every round is expensive. We present an algorithm for advice-efficient prediction with expert advice that achieves $O(\sqrt{\frac{N}{M}T\ln N})$ regret on $T$ rounds of the game."]]></description>
<dc:subject>low-regret_learning individual_sequence_prediction re:growing_ensemble_project in_NB bartlett.peter_l.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f69f84a4e327/</dc:identifier>
<taxo:topics><rdf:Bag>	<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: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:bartlett.peter_l."/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1302.2672">
    <title>[1302.2672] Competing With Strategies</title>
    <dc:date>2013-03-06T15:30:46+00:00</dc:date>
    <link>http://arxiv.org/abs/1302.2672</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the problem of online learning with a notion of regret defined with respect to a set of strategies. We develop tools for analyzing the minimax rates and for deriving regret-minimization algorithms in this scenario. While the standard methods for minimizing the usual notion of regret fail, through our analysis we demonstrate existence of regret-minimization methods that compete with such sets of strategies as: autoregressive algorithms, strategies based on statistical models, regularized least squares, and follow the regularized leader strategies. In several cases we also derive efficient learning algorithms."]]></description>
<dc:subject>low-regret_learning game_theory rakhlin.alexander re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b4230d85278b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:game_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:rakhlin.alexander"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1303.0140">
    <title>[1303.0140] Second-Order Non-Stationary Online Learning for Regression</title>
    <dc:date>2013-03-04T01:58:28+00:00</dc:date>
    <link>http://arxiv.org/abs/1303.0140</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The goal of a learner, in standard online learning, is to have the cumulative loss not much larger compared with the best-performing function from some fixed class. Numerous algorithms were shown to have this gap arbitrarily close to zero, compared with the best function that is chosen off-line. Nevertheless, many real-world applications, such as adaptive filtering, are non-stationary in nature, and the best prediction function may drift over time. We introduce two novel algorithms for online regression, designed to work well in non-stationary environment. Our first algorithm performs adaptive resets to forget the history, while the second is last-step min-max optimal in context of a drift. We analyze both algorithms in the worst-case regret framework and show that they maintain an average loss close to that of the best slowly changing sequence of linear functions, as long as the cumulative drift is sublinear. In addition, in the stationary case, when no drift occurs, our algorithms suffer logarithmic regret, as for previous algorithms. Our bounds improve over the existing ones, and simulations demonstrate the usefulness of these algorithms compared with other state-of-the-art approaches."]]></description>
<dc:subject>to_read non-stationarity low-regret_learning time_series machine_learning re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:533ccaa7cb2b/</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:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_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:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1302.6927">
    <title>[1302.6927] Online Learning for Time Series Prediction</title>
    <dc:date>2013-02-28T03:44:06+00:00</dc:date>
    <link>http://arxiv.org/abs/1302.6927</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper we address the problem of predicting a time series using the ARMA (autoregressive moving average) model, under minimal assumptions on the noise terms. Using regret minimization techniques, we develop effective online learning algorithms for the prediction problem, without assuming that the noise terms are Gaussian, identically distributed or even independent. Furthermore, we show that our algorithm's performances asymptotically approaches the performance of the best ARMA model in hindsight."]]></description>
<dc:subject>to_read re:growing_ensemble_project time_series low-regret_learning in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d350b288d013/</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:time_series"/>
	<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://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1359987532">
    <title>Vogt : Nonparametric regression for locally stationary time series</title>
    <dc:date>2013-02-18T19:06:33+00:00</dc:date>
    <link>http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1359987532</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper, we study nonparametric models allowing for locally stationary regressors and a regression function that changes smoothly over time. These models are a natural extension of time series models with time-varying coefficients. We introduce a kernel-based method to estimate the time-varying regression function and provide asymptotic theory for our estimates. Moreover, we show that the main conditions of the theory are satisfied for a large class of nonlinear autoregressive processes with a time-varying regression function. Finally, we examine structured models where the regression function splits up into time-varying additive components. As will be seen, estimation in these models does not suffer from the curse of dimensionality."]]></description>
<dc:subject>to:NB regression nonparametrics non-stationarity statistics time_series re:growing_ensemble_project to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1661b57a1be4/</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:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<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="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.bj/1358531747">
    <title>Zhao , Li : Inference for modulated stationary processes</title>
    <dc:date>2013-01-20T21:25:52+00:00</dc:date>
    <link>http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.bj/1358531747</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study statistical inferences for a class of modulated stationary processes with time-dependent variances. Due to non-stationarity and the large number of unknown parameters, existing methods for stationary, or locally stationary, time series are not applicable. Based on a self-normalization technique, we address several inference problems, including a self-normalized central limit theorem, a self-normalized cumulative sum test for the change-point problem, a long-run variance estimation through blockwise self-normalization, and a self-normalization-based wild bootstrap. Monte Carlo simulation studies show that the proposed self-normalization-based methods outperform stationarity-based alternatives. We demonstrate the proposed methodology using two real data sets: annual mean precipitation rates in Seoul from 1771–2000, and quarterly U.S. Gross National Product growth rates from 1947–2002."]]></description>
<dc:subject>to:NB to_read time_series statistics non-stationarity change-point_problem re:your_favorite_dsge_sucks re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5b844735a73f/</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:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:change-point_problem"/>
	<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:growing_ensemble_project"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1301.1254">
    <title>[1301.1254] Dynamical Models and Tracking Regret in Online Convex Programming</title>
    <dc:date>2013-01-09T00:47:43+00:00</dc:date>
    <link>http://arxiv.org/abs/1301.1254</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper describes a new online convex optimization method which incorporates a family of candidate dynamical models and establishes novel tracking regret bounds that scale with the comparator's deviation from the best dynamical model in this family. Previous online optimization methods are designed to have a total accumulated loss comparable to that of the best comparator sequence, and existing tracking or shifting regret bounds scale with the overall variation of the comparator sequence. In many practical scenarios, however, the environment is nonstationary and comparator sequences with small variation are quite weak, resulting in large losses. The proposed Dynamic Mirror Descent method, in contrast, can yield low regret relative to highly variable comparator sequences by both tracking the best dynamical model and forming predictions based on that model. This concept is demonstrated empirically in the context of sequential compressive observations of a dynamic scene and tracking a dynamic social network."]]></description>
<dc:subject>low-regret_learning optimization re:growing_ensemble_project have_read in_NB willett.rebecca_m.</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d46c02a3c7c3/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-regret_learning"/>
	<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:have_read"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1301.0534">
    <title>[1301.0534] Follow the Leader If You Can, Hedge If You Must</title>
    <dc:date>2013-01-07T23:07:12+00:00</dc:date>
    <link>http://arxiv.org/abs/1301.0534</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Follow-the-Leader (FTL) is an intuitive sequential prediction strategy that guarantees constant regret in the stochastic setting, but has terrible performance for worst-case data. Other hedging strategies have better worst-case guarantees but may perform much worse than FTL if the data are not maximally adversarial. We introduce the FlipFlop algorithm, which is the first method that provably combines the best of both worlds. 
"As part of our construction, we develop AdaHedge, which is a new way of dynamically tuning the learning rate in Hedge without using the doubling trick. AdaHedge refines a method by Cesa-Bianchi, Mansour and Stoltz (2007), yielding slightly improved worst-case guarantees. By interleaving AdaHedge and FTL, the FlipFlop algorithm achieves regret within a constant factor of the FTL regret, without sacrificing AdaHedge's worst-case guarantees. 
"AdaHedge and FlipFlop do not need to know the range of the losses in advance; moreover, unlike earlier methods, both have the intuitive property that the issued weights are invariant under rescaling and translation of the losses. The losses are also allowed to be negative, in which case they may be interpreted as gains."]]></description>
<dc:subject>to_read individual_sequence_prediction low-regret_learning learning_theory re:growing_ensemble_project grunwald.peter in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:46c837991e65/</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:individual_sequence_prediction"/>
	<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:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:grunwald.peter"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://faculty.cs.gwu.edu/~cmontel/mssa11.pdf">
    <title>TRACKING CLIMATE MODELS</title>
    <dc:date>2012-11-19T23:36:13+00:00</dc:date>
    <link>http://faculty.cs.gwu.edu/~cmontel/mssa11.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Climate models are complex mathematical models designed by meteorologists, geophysicists, and climate scientists, and run as computer simulations, to predict climate. There is currently high variance among the predictions of 20 global climate models, from various laboratories around the world, that inform the Intergovernmental Panel on Climate Change (IPCC). Given temperature predictions from 20 IPCC global climate models, and over 100 years of historical temperature data, we track the changing sequence of which model predicts best at any given time. We use an algorithm due to Monteleoni and Jaakkola that models the sequence of observations using a hierarchical learner, based on a set of generalized Hidden Markov Models, where the identity of the current best climate model is the hidden variable. The transition probabilities between climate models are learned online, simultaneous to tracking the temperature predictions.
"On historical global mean temperature data, our online learning algorithm’s average prediction loss nearly matches that of the best performing climate model in hindsight. Moreover its performance surpasses that of the average model prediction, which is the default practice in climate science, the median prediction, and least squares linear regression. We also experimented on climate model predictions through the year 2098. Simulating labels with the predictions of any one climate model, we found significantly improved performance using our online learning algorithm with respect to the other climate models, and techniques. To complement our global results, we also ran experiments on IPCC global climate model temperature predictions for the specific geographic regions of Africa, Europe, and North America. On historical data, at both annual and monthly time-scales, and in future simulations, our algorithm typically outperformed both the best climate model per region, and linear regression. Notably, our algorithm consistently outperformed the average prediction over models, the current benchmark."

--- Appears to supersede the MS. of the same title at http://www1.ccls.columbia.edu/~cmontel/mss10.pdf

--- Re teaching in "Data over Space and Time", I'm mostly thinking of the data sets.]]></description>
<dc:subject>re:growing_ensemble_project non-stationarity time_series climate_change statistics individual_sequence_prediction monteleoni.claire in_NB have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6c35cd76ad26/</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:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:climate_change"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:monteleoni.claire"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.cs.cmu.edu/~dyogatam/Home_files/yogatama+etal.emnlp11.pdf">
    <title>Predicting a Scientific Community’s Response to an Article</title>
    <dc:date>2012-10-08T21:47:40+00:00</dc:date>
    <link>http://www.cs.cmu.edu/~dyogatam/Home_files/yogatama+etal.emnlp11.pdf</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider the problem of predicting measurable responses to scientific articles based primarily on their text content. Specifically, we consider papers in two fields (economics and computational linguistics) and make predictions about downloads and within-community citations. Our approach is based on generalized linear models, allowing interpretability; a novel extension that captures first-order temporal effects is also presented. We demonstrate that text features significantly improve accuracy of predictions over metadata features like authors, topical categories, and publication venues."]]></description>
<dc:subject>to:NB non-stationarity prediction text_mining bibliometry smith.noah to_teach:data-mining re:growing_ensemble_project regression o'connor.brendan</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:935dd2cb9577/</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:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:text_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bibliometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:smith.noah"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:o'connor.brendan"/>
</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.6814">
    <title>[1206.6814] An Empirical Comparison of Algorithms for Aggregating Expert Predictions</title>
    <dc:date>2012-07-02T18:17:42+00:00</dc:date>
    <link>http://arxiv.org/abs/1206.6814</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Predicting the outcomes of future events is a challenging problem for which a variety of solution methods have been explored and attempted. We present an empirical comparison of a variety of online and offline adaptive algorithms for aggregating experts' predictions of the outcomes of five years of US National Football League games (1319 games) using expert probability elicitations obtained from an Internet contest called ProbabilitySports. We find that it is difficult to improve over simple averaging of the predictions in terms of prediction accuracy, but that there is room for improvement in quadratic loss. Somewhat surprisingly, a Bayesian estimation algorithm which estimates the variance of each expert's prediction exhibits the most consistent superior performance over simple averaging among our collection of algorithms."]]></description>
<dc:subject>to:NB ensemble_methods machine_learning re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:30384d9f628c/</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:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
</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://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6191328">
    <title>Interior-Point Methods for Full-Information and Bandit Online Learning</title>
    <dc:date>2012-06-12T22:03:59+00:00</dc:date>
    <link>http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6191328</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the problem of predicting individual sequences with linear loss with full and partial (or bandit) feedback. Our main contribution is the first efficient algorithm for the problem of online linear optimization in the bandit setting which achieves the optimal ${tilde{O}}(sqrt{T})$ regret. In addition, for the full-information setting, we give a novel regret minimization algorithm. These results are made possible by the introduction of interior-point methods for convex optimization to online learning."]]></description>
<dc:subject>to:NB individual_sequence_prediction optimization machine_learning rakhlin.sasha re:growing_ensemble_project bandit_problems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0f20090d6199/</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:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:rakhlin.sasha"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bandit_problems"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1205.3845">
    <title>[1205.3845] Forecasting with Historical Data or Process Knowledge under Misspecification: A Comparison</title>
    <dc:date>2012-05-20T20:48:05+00:00</dc:date>
    <link>http://arxiv.org/abs/1205.3845</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["When faced with the task of forecasting a dynamic system, practitioners often have available historical data, knowledge of the system, or a combination of both. While intuition dictates that perfect knowledge of the system should in theory yield perfect forecasting, often knowledge of the system is only partially known, known up to parameters, or known incorrectly. In contrast, forecasting using previous data without any process knowledge might result in accurate prediction for simple systems, but will fail for highly nonlinear and chaotic systems. In this paper, the authors demonstrate how even in chaotic systems, forecasting with historical data is preferable to using process knowledge if this knowledge exhibits certain forms of misspecification. Through an extensive simulation study, a range of misspecification and forecasting scenarios are examined with the goal of gaining an improved understanding of the circumstances under which forecasting from historical data is to be preferred over using process knowledge."]]></description>
<dc:subject>to_read prediction time_series misspecification re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:694f865b7228/</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:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:misspecification"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1337268210">
    <title>Wang , Phillips : A specification test for nonlinear nonstationary models</title>
    <dc:date>2012-05-18T20:57:38+00:00</dc:date>
    <link>http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1337268210</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We provide a limit theory for a general class of kernel smoothed U-statistics that may be used for specification testing in time series regression with nonstationary data. The test framework allows for linear and nonlinear models with endogenous regressors that have autoregressive unit roots or near unit roots. The limit theory for the specification test depends on the self-intersection local time of a Gaussian process. A new weak convergence result is developed for certain partial sums of functions involving nonstationary time series that converges to the intersection local time process. This result is of independent interest and is useful in other applications. Simulations examine the finite sample performance of the test."]]></description>
<dc:subject>time_series non-stationarity statistics misspecification model_checking in_NB re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:878a70280929/</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:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:misspecification"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:model_checking"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
</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/0801.0327">
    <title>[0801.0327] Nonparametric sequential prediction of time series</title>
    <dc:date>2012-02-25T23:13:27+00:00</dc:date>
    <link>http://arxiv.org/abs/0801.0327</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Time series prediction covers a vast field of every-day statistical applications in medical, environmental and economic domains. In this paper we develop nonparametric prediction strategies based on the combination of a set of 'experts' and show the universal consistency of these strategies under a minimum of conditions. We perform an in-depth analysis of real-world data sets and show that these nonparametric strategies are more flexible, faster and generally outperform ARMA methods in terms of normalized cumulative prediction error."]]></description>
<dc:subject>time_series nonparametrics prediction statistics to_teach:undergrad-ADA re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:577bfd8f7476/</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:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:undergrad-ADA"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/math/0701419">
    <title>[math/0701419] Strategies for prediction under imperfect monitoring</title>
    <dc:date>2012-02-21T04:13:36+00:00</dc:date>
    <link>http://arxiv.org/abs/math/0701419</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose simple randomized strategies for sequential prediction under imperfect monitoring, that is, when the forecaster does not have access to the past outcomes but rather to a feedback signal. The proposed strategies are consistent in the sense that they achieve, asymptotically, the best possible average reward. It was Rustichini (1999) who first proved the existence of such consistent predictors. The forecasters presented here offer the first constructive proof of consistency. Moreover, the proposed algorithms are computationally efficient. We also establish upper bounds for the rates of convergence. In the case of deterministic feedback, these rates are optimal up to logarithmic terms."]]></description>
<dc:subject>to:NB prediction individual_sequence_prediction learning_in_games re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:8a46f026681f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_in_games"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1202.4294">
    <title>[1202.4294] Prediction of quantiles by statistical learning and application to GDP forecasting</title>
    <dc:date>2012-02-21T03:43:03+00:00</dc:date>
    <link>http://arxiv.org/abs/1202.4294</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper, we tackle the problem of prediction and confidence intervals for time series using a statistical learning approach and quantile loss functions. In a first time, we show that the Gibbs estimator (also known as Exponentially Weighted aggregate) is able to predict as well as the best predictor in a given family for a wide set of loss functions. In particular, using the quantile loss function of Koenker and Bassett (1978), this allows to build confidence intervals. We apply these results to the problem of prediction and confidence regions for the French Gross Domestic Product (GDP) growth, with promising results."]]></description>
<dc:subject>to_read prediction confidence_sets learning_theory re:your_favorite_dsge_sucks re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:711f1ae24c8f/</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:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:confidence_sets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<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:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1202.3079">
    <title>[1202.3079] Towards minimax policies for online linear optimization with bandit feedback</title>
    <dc:date>2012-02-15T13:24:07+00:00</dc:date>
    <link>http://arxiv.org/abs/1202.3079</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We address the online linear optimization problem with bandit feedback. Our contribution is twofold. First, we provide an algorithm (based on exponential weights) with a regret of order $sqrt{d n log N}$ for any finite action set with $N$ actions, under the assumption that the instantaneous loss is bounded by 1. This shaves off an extraneous $sqrt{d}$ factor compared to previous works, and gives a regret bound of order $d sqrt{n log n}$ for any compact set of actions. Without further assumptions on the action set, this last bound is minimax optimal up to a logarithmic factor. Interestingly, our result also shows that the minimax regret for bandit linear optimization with expert advice in $d$ dimension is the same as for the basic $d$-armed bandit with expert advice. Our second contribution is to show how to use the Mirror Descent algorithm to obtain computationally efficient strategies with minimax optimal regret bounds in specific examples. More precisely we study two canonical action sets: the hypercube and the Euclidean ball. In the former case, we obtain the first computationally efficient algorithm with a $d sqrt{n}$ regret, thus improving by a factor $sqrt{d log n}$ over the best known result for a computationally efficient algorithm. In the latter case, our approach gives the first algorithm with a $sqrt{d n log n}$ regret, again shaving off an extraneous $sqrt{d}$ compared to previous works."]]></description>
<dc:subject>online_learning decision_theory optimization re:growing_ensemble_project cesa-bianchi.nicolo kakade.sham bubeck.sebastien in_NB bandit_problems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d3172d33e293/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:online_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:decision_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:optimization"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cesa-bianchi.nicolo"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kakade.sham"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bubeck.sebastien"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bandit_problems"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1201.5568">
    <title>[1201.5568] Dynamic trees for streaming and massive data contexts</title>
    <dc:date>2012-01-28T16:52:06+00:00</dc:date>
    <link>http://arxiv.org/abs/1201.5568</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Data collection at a massive scale is becoming ubiquitous in a wide variety of settings, from vast offline databases to streaming real-time information. Learning algorithms deployed in such contexts must rely on single-pass inference, where the data history is never revisited. In streaming contexts, learning must also be temporally adaptive to remain up-to-date against unforeseen changes in the data generating mechanism. Although rapidly growing, the online Bayesian inference literature remains challenged by massive data and transient, evolving data streams. Non-parametric modelling techniques can prove particularly ill-suited, as the complexity of the model is allowed to increase with the sample size. In this work, we take steps to overcome these challenges by porting standard streaming techniques, like data discarding and downweighting, into a fully Bayesian framework via the use of informative priors and active learning heuristics. We showcase our methods by augmenting a modern non-parametric modelling framework, dynamic trees, and illustrate its performance on a number of practical examples. The end product is a powerful streaming regression and classification tool, whose performance compares favourably to the state-of-the-art."]]></description>
<dc:subject>to:NB machine_learning non-stationarity statistics data_mining to_read re:growing_ensemble_project</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ddf28bc950ae/</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:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1111.6337">
    <title>[1111.6337] Regret Bound by Variation for Online Convex Optimization</title>
    <dc:date>2011-12-01T14:04:08+00:00</dc:date>
    <link>http://arxiv.org/abs/1111.6337</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In citep{Hazan-2008-extract}, the authors showed that the regret of online linear optimization can be bounded by the total variation of the cost vectors. In this paper, we extend this result to general online convex optimization. We first analyze the limitations of the algorithm in citep{Hazan-2008-extract} when applied it to online convex optimization. We then present two algorithms for online convex optimization whose regrets are bounded by the variation of cost functions. We finally consider the bandit setting, and present a randomized algorithm for online bandit convex optimization with a variation-based regret bound. We show that the regret bound for online bandit convex optimization is optimal when the variation of cost functions is independent of the number of trials."]]></description>
<dc:subject>to_read re:growing_ensemble_project learning_theory individual_sequence_prediction in_NB bandit_problems</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2dacf3479f48/</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:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<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://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/1110.2755">
    <title>[1110.2755] Efficient Tracking of Large Classes of Experts</title>
    <dc:date>2011-10-13T12:35:00+00:00</dc:date>
    <link>http://arxiv.org/abs/1110.2755</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In the framework for prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different "base" expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy %(with an arbitrary number of switches) selected in hindsight for the particular sequence to be predicted. In this paper we construct %strongly sequential (i.e., horizon-independent) prediction strategies of low computational cost for the case where the set of base experts is large. In particular we derive a family of efficient tracking algorithms that, for any prediction algorithm $A$ designed for the base class, can be implemented with time and space complexity $O(n^{gamma} log n)$ times larger than that of $A$, where $n$ is the time horizon and $gamma ge 0$ is a parameter of the algorithm. With $A$ properly chosen, our algorithm achieves a regret bound of optimal order for $gamma>0$, and only $O(log n)$ times larger than the optimal order for $gamma=0$ for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters, our method achieves the optimal $O(log n)$ regret rate with time complexity $O(n^{1+gamma}log n)$ for any $gammain (0,1)$."]]></description>
<dc:subject>to_read re:growing_ensemble_project learning_theory individual_sequence_prediction lugosi.gabor in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:80aeab90a23a/</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:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:lugosi.gabor"/>
	<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.2529">
    <title>[1110.2529] The Generalization Ability of Online Algorithms for Dependent Data</title>
    <dc:date>2011-10-13T12:33:26+00:00</dc:date>
    <link>http://arxiv.org/abs/1110.2529</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the generalization performance of arbitrary online learning algorithms trained on samples coming from a dependent source of data. We show that the generalization error of any stable online algorithm concentrates around its regret--an easily computable statistic of the online performance of the algorithm--when the underlying ergodic process is $beta$- or $phi$-mixing. We show high probability error bounds assuming the loss function is convex, and we also establish sharp convergence rates and deviation bounds for strongly convex losses and several linear prediction problems such as linear and logistic regression, least-squares SVM, and boosting on dependent data. In addition, our results have straightforward applications to stochastic optimization with dependent data, and our analysis requires only martingale convergence arguments; we need not rely on more powerful statistical tools such as empirical process theory."]]></description>
<dc:subject>learning_theory individual_sequence_prediction ergodic_theory mixing re:growing_ensemble_project re:XV_for_mixing stability_of_learning concentration_of_measure have_read re:your_favorite_dsge_sucks in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:0891bd9c9846/</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:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ergodic_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:XV_for_mixing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stability_of_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:concentration_of_measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<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:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://pre.aps.org/abstract/PRE/v84/i4/e046702">
    <title>Phys. Rev. E 84, 046702 (2011): Nonparametric segmentation of nonstationary time series</title>
    <dc:date>2011-10-12T15:46:30+00:00</dc:date>
    <link>http://pre.aps.org/abstract/PRE/v84/i4/e046702</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The nonstationary evolution of observable quantities in complex systems can frequently be described as a juxtaposition of quasistationary spells. Given that standard theoretical and data analysis approaches usually rely on the assumption of stationarity, it is important to detect in real time series intervals holding that property. With that aim, we introduce a segmentation algorithm based on a fully nonparametric approach. We illustrate its applicability through the analysis of real time series presenting diverse degrees of nonstationarity, thus showing that this segmentation procedure generalizes and allows one to uncover features unresolved by previous proposals based on the discrepancy of low order statistical moments only."]]></description>
<dc:subject>statistics change-point_problem time_series nonparametrics re:growing_ensemble_project in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1bef9442e0c0/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:change-point_problem"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<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:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1103.0949">
    <title>[1103.0949] Adapting to Non-stationarity with Growing Expert Ensembles</title>
    <dc:date>2011-03-07T01:28:00+00:00</dc:date>
    <link>http://arxiv.org/abs/1103.0949</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>self-promotion individual_sequence_prediction non-stationarity re:growing_ensemble_project ensemble_methods time_series to_teach:data_over_space_and_time</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f2d8cecf5a2c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:self-promotion"/>
	<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:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data_over_space_and_time"/>
</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://pre.aps.org/abstract/PRE/v82/i5/e056206">
    <title>Phys. Rev. E 82, 056206 (2010): Forecasting the evolution of nonlinear and nonstationary systems using recurrence-based local Gaussian process models</title>
    <dc:date>2010-11-22T21:48:28+00:00</dc:date>
    <link>http://pre.aps.org/abstract/PRE/v82/i5/e056206</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["...combining nonparametric Gaussian process (GP) modeling with certain local topological considerations ... for prediction (one-step look ahead) of ... nonlinear and nonstationary dynamics. ... partition ... trajectories into multiple near-stationary segments by aligning the boundaries of the partitions with those of the piecewise affine projections of the underlying dynamic system...  alignment is achieved through the consideration of recurrence and other local topological properties ...  forecasting in Lorenz system under different levels of induced noise and nonstationarity, synthetic heart-rate signals, and a real-world time-series from an industrial operation known to exhibit highly nonlinear and nonstationary dynamics. ... local Gaussian process can significantly outperform not just classical system identification, neural network and nonparametric models, but also the sequential Bayesian Monte Carlo methods in terms of prediction accuracy and computational speed."
]]></description>
<dc:subject>time_series prediction non-stationarity gaussian_processes re:growing_ensemble_project to_read</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:304d78ce8e48/</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:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:non-stationarity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:gaussian_processes"/>
	<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="http://www.ncdc.noaa.gov/paleo/recons.html">
    <title>World Data Center for Paleoclimatology - Climate Reconstructions</title>
    <dc:date>2010-09-17T14:25:49+00:00</dc:date>
    <link>http://www.ncdc.noaa.gov/paleo/recons.html</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>climate_change to_teach re:growing_ensemble_project data_sets climatology time_series to_teach:data_over_space_and_time</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fae80986aabd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:climate_change"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_sets"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:climatology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data_over_space_and_time"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1008.4532">
    <title>[1008.4532] Switching between Hidden Markov Models using Fixed Share</title>
    <dc:date>2010-08-27T15:15:12+00:00</dc:date>
    <link>http://arxiv.org/abs/1008.4532</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>re:growing_ensemble_project markov_models to_read</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ba3440970142/</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:markov_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1008.4232">
    <title>[1008.4232] Online Learning in Case of Unbounded Losses Using the Follow Perturbed Leader Algorithm</title>
    <dc:date>2010-08-26T16:47:22+00:00</dc:date>
    <link>http://arxiv.org/abs/1008.4232</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>re:growing_ensemble_project to_read</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ee3082a7df34/</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:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.springerlink.com/content/68386v04t03752n1/">
    <title>Extracting certainty from uncertainty: regret bounded by variation in costs</title>
    <dc:date>2010-07-21T15:19:22+00:00</dc:date>
    <link>http://www.springerlink.com/content/68386v04t03752n1/</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[Cool, but not sure it works really for our setting.
]]></description>
<dc:subject>learning_theory individual_sequence_prediction ensemble_methods re:growing_ensemble_project have_read</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fc1525f12ba1/</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:individual_sequence_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/0903.2851v2">
    <title>[0903.2851v2] A parameter-free hedging algorithm</title>
    <dc:date>2010-07-15T16:48:09+00:00</dc:date>
    <link>http://arxiv.org/abs/0903.2851v2</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>ensemble_methods re:growing_ensemble_project</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b3ecf8331a56/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1006.0475">
    <title>[1006.0475] Prediction with Advice of Unknown Number of Experts</title>
    <dc:date>2010-06-03T11:42:19+00:00</dc:date>
    <link>http://arxiv.org/abs/1006.0475</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In the framework of prediction with expert advice, we consider a recently introduced kind of regret bounds: the bounds that depend on the effective instead of nominal number of experts. In contrast to the NormalHedge bound, which mainly depends on the effective number of experts and also weakly depends on the nominal one, we obtain a bound that does not contain the nominal number of experts at all. We use the defensive forecasting method and introduce an application of defensive forecasting to multivalued supermartingales."
]]></description>
<dc:subject>prediction learning_theory re:growing_ensemble_project</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:d6e352807a0f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:growing_ensemble_project"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>