%PDF-1.3 1 0 obj << /Kids [ 4 0 R 5 0 R 6 0 R 7 0 R 8 0 R 9 0 R 10 0 R 11 0 R 12 0 R ] /Type /Pages /Count 9 >> endobj 2 0 obj << /Subject (Neural Information Processing Systems http\072\057\057nips\056cc\057) /Publisher (Curran Associates) /Language (en\055US) /Created (2011) /Description-Abstract (Learning theory has largely focused on two main learning scenarios\072 the classical statistical setting where instances are drawn i\056i\056d\056 from a fixed distribution\054 and the adversarial scenario whereby at every time step the worst instance is revealed to the player\056 It can be argued that in the real world neither of these assumptions is reasonable\056 We define the minimax value of a game where the adversary is restricted in his moves\054 capturing stochastic and non\055stochastic assumptions on data\056 Building on the sequential symmetrization approach\054 we define a notion of distribution\055dependent Rademacher complexity for the spectrum of problems ranging from i\056i\056d\056 to worst\055case\056 The bounds let us immediately deduce variation\055type bounds\056 We study a smoothed online learning scenario and show that exponentially small amount of noise can make function classes with infinite Littlestone dimension learnable\056) /Producer (Python PDF Library \055 http\072\057\057pybrary\056net\057pyPdf\057) /Title (Online Learning\072 Stochastic\054 Constrained\054 and Smoothed Adversaries) /Date (2011) /Type (Conference Proceedings) /firstpage (1764) /Book (Advances in Neural Information Processing Systems 24) /Description (Paper accepted and presented at the Neural Information Processing Systems Conference \050http\072\057\057nips\056cc\057\051) /Editors (J\056 Shawe\055Taylor and R\056S\056 Zemel and P\056L\056 Bartlett and F\056 Pereira and K\056Q\056 Weinberger) /Author (Alexander Rakhlin\054 Karthik Sridharan\054 Ambuj Tewari) /lastpage (1772) >> endobj 3 0 obj << /Type /Catalog /Pages 1 0 R >> endobj 4 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 13 0 R /Resources << /ColorSpace 14 0 R /ExtGState 17 0 R /ProcSet [ /PDF /Text ] /Font 22 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 5 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 42 0 R /Resources << /ColorSpace 43 0 R /ExtGState 44 0 R /ProcSet [ /PDF /Text ] /Font 45 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 6 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 117 0 R /Resources << /ColorSpace 118 0 R /ExtGState 119 0 R /ProcSet [ /PDF /Text ] /Font 120 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 7 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 136 0 R /Resources << /ColorSpace 137 0 R /ExtGState 138 0 R /ProcSet [ /PDF /Text ] /Font 139 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 8 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 158 0 R /Resources << /ColorSpace 159 0 R /ExtGState 160 0 R /ProcSet [ /PDF /Text ] /Font 161 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 9 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 169 0 R /Resources << /ColorSpace 170 0 R /ExtGState 171 0 R /ProcSet [ /PDF /Text ] /Font 172 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 10 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 173 0 R /Resources << /ColorSpace 174 0 R /ExtGState 175 0 R /ProcSet [ /PDF /Text ] /Font 176 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 11 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 177 0 R /Resources << /ColorSpace 178 0 R /ExtGState 179 0 R /ProcSet [ /PDF /Text ] /Font 180 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 12 0 obj << /Parent 1 0 R /Rotate 0 /TrimBox [ 0 0 612 792 ] /Contents 181 0 R /Resources << /ColorSpace 182 0 R /ExtGState 183 0 R /ProcSet [ /PDF /Text ] /Font 184 0 R >> /MediaBox [ 0 0 612 792 ] /Type /Page /BleedBox [ 0 0 612 792 ] /ArtBox [ 0 0 612 792 ] >> endobj 13 0 obj << /Length 3597 /Filter /FlateDecode >> stream xZKs+ٔAN)\: ȅV Vӏ@UTYb==wi]CuOY_;ktwB4UEjuW&K?ϻ]5]e X1Nf;RL\2@KG5R]'23zw}_Z˔NT@"Ilw}EwmRIa)}poJa0