%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\054 Inc\056) /Language (en\055US) /Created (2015) /EventType (Poster) /Description-Abstract (We study the performance of standard online learning algorithms when the feedback is delayed by an adversary\056 We show that \134texttt\173online\055gradient\055descent\175 and \134texttt\173follow\055the\055perturbed\055leader\175 achieve regret \044O\050\134sqrt\173D\175\051\044 in the delayed setting\054 where \044D\044 is the sum of delays of each round\047s feedback\056 This bound collapses to an optimal \044O\050\134sqrt\173T\175\051\044 bound in the usual setting of no delays \050where \044D \075 T\044\051\056 Our main contribution is to show that standard algorithms for online learning already have simple regret bounds in the most general setting of delayed feedback\054 making adjustments to the analysis and not to the algorithms themselves\056 Our results help affirm and clarify the success of recent algorithms in optimization and machine learning that operate in a delayed feedback model\056) /Producer (PyPDF2) /Title (Online Learning with Adversarial Delays) /Date (2015) /ModDate (D\07220151218143723\05508\04700\047) /Published (2015) /Type (Conference Proceedings) /firstpage (1270) /Book (Advances in Neural Information Processing Systems 28) /Description (Paper accepted and presented at the Neural Information Processing Systems Conference \050http\072\057\057nips\056cc\057\051) /Editors (C\056 Cortes and N\056D\056 Lawrence and D\056D\056 Lee and M\056 Sugiyama and R\056 Garnett and R\056 Garnett) /Author (Kent Quanrud\054 Daniel Khashabi) /lastpage (1278) >> endobj 3 0 obj << /Type /Catalog /Pages 1 0 R >> endobj 4 0 obj << /Contents 13 0 R /Parent 1 0 R /Resources 14 0 R /MediaBox [ 0 0 612 792 ] /Annots [ 64 0 R 65 0 R 66 0 R 67 0 R 68 0 R 69 0 R 70 0 R 71 0 R 72 0 R 73 0 R 74 0 R 75 0 R 76 0 R ] /Type /Page >> endobj 5 0 obj << /Contents 77 0 R /Parent 1 0 R /Resources 78 0 R /MediaBox [ 0 0 612 792 ] /Annots [ 83 0 R 84 0 R 85 0 R 86 0 R 87 0 R 88 0 R 89 0 R 90 0 R 91 0 R 92 0 R 93 0 R 94 0 R 95 0 R 96 0 R 97 0 R 98 0 R 99 0 R ] /Type /Page >> endobj 6 0 obj << /Contents 100 0 R /Parent 1 0 R /Resources 101 0 R /MediaBox [ 0 0 612 792 ] /Annots [ 106 0 R 107 0 R 108 0 R 109 0 R 110 0 R 111 0 R 112 0 R 113 0 R 114 0 R 115 0 R 116 0 R 117 0 R 118 0 R ] /Type /Page >> endobj 7 0 obj << /Contents 119 0 R /Parent 1 0 R /Resources 120 0 R /MediaBox [ 0 0 612 792 ] /Annots [ 125 0 R 126 0 R 127 0 R 128 0 R 129 0 R ] /Type /Page >> endobj 8 0 obj << /Contents 130 0 R /Parent 1 0 R /Resources 131 0 R /MediaBox [ 0 0 612 792 ] /Annots [ 144 0 R 145 0 R 146 0 R ] /Type /Page >> endobj 9 0 obj << /Contents 147 0 R /Parent 1 0 R /Resources 148 0 R /MediaBox [ 0 0 612 792 ] /Annots [ 153 0 R 154 0 R 155 0 R ] /Type /Page >> endobj 10 0 obj << /Contents 156 0 R /Parent 1 0 R /Resources 157 0 R /MediaBox [ 0 0 612 792 ] /Annots [ 158 0 R 159 0 R 160 0 R 161 0 R 162 0 R ] /Type /Page >> endobj 11 0 obj << /Contents 163 0 R /Parent 1 0 R /Resources 164 0 R /MediaBox [ 0 0 612 792 ] /Annots [ 169 0 R 170 0 R 171 0 R 172 0 R 173 0 R 174 0 R 175 0 R ] /Type /Page >> endobj 12 0 obj << /Contents 176 0 R /Parent 1 0 R /Type /Page /Resources 177 0 R /MediaBox [ 0 0 612 792 ] >> endobj 13 0 obj << /Length 3840 /Filter /FlateDecode >> stream xZ[ȕ~Rf]X`xă&dؒDH IM'K"j_"^S-ϲ|X.b}xʙJm>ӳ>{@"">0Ը4sbqY%?.72ϒK.EU}5U7"Kʶm\mry Wf 4a6@l_^/.uFܾT*0:_/euizJI],Max߲Lq*(7ބ*_|*UiRunri myml9O}7몬% ÁZ|@
ToeIU
4(O(
"K ؕ8Op5~c_3^YH,8_ X#% WP dr5Τev. Vf焠U(ISwBh L[XoF22p\" @T\\_Fn|c(:FOKpH/Q꾭VK(^!ͦZT:{!ž
b".KRiZ0ܴbsW0pbOq=8]hKe]M-Gx65R:FK;
M~ߧ A eأǎ)aCǫgN7fycЕ{PG`FK-@i[?rpj*1̄z{ @;eh 43QTgI#7:!`<FCj?g`g#
41T&@&M,a`KPI9iךˇpeSwՆRzJ2 3A X_r:;
aP:R9.n0-f0lS(;~l*9c{Q`E1_ܥ!:9vؐhIym{y ܒPmlFcM:=yT)/ߑ+eɕGK @)J:q٘X>T4U: ,aG62S}đprJuI0T#YAfQ 'aǍnF5i؞ZT4FazacԸdMVL