%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 (2011) /Description-Abstract (Increasingly\054 optimization problems in machine learning\054 especially those arising from high\055dimensional statistical estimation\054 have a large number of variables\056 Modern statistical estimators developed over the past decade have statistical or sample complexity that depends only weakly on the number of parameters when there is some structure to the problem\054 such as sparsity\056 A central question is whether similar advances can be made in their computational complexity as well\056 In this paper\054 we propose strategies that indicate that such advances can indeed be made\056 In particular\054 we investigate the greedy coordinate descent algorithm\054 and note that performing the greedy step efficiently weakens the costly dependence on the problem size provided the solution is sparse\056 We then propose a suite of methods that perform these greedy steps efficiently by a reduction to nearest neighbor search\056 We also devise a more amenable form of greedy descent for composite non\055smooth objectives\073 as well as several approximate variants of such greedy descent\056 We develop a practical implementation of our algorithm that combines greedy coordinate descent with locality sensitive hashing\056 Without tuning the latter data structure\054 we are not only able to significantly speed up the vanilla greedy method\054 but also outperform cyclic descent when the problem size becomes large\056 Our results indicate the effectiveness of our nearest neighbor strategies\054 and also point to many open questions regarding the development of computational geometric techniques tailored towards first\055order optimization methods\056) /Producer (Python PDF Library \055 http\072\057\057pybrary\056net\057pyPdf\057) /Title (Nearest Neighbor based Greedy Coordinate Descent) /Date (2011) /ModDate (D\07220140423103819\05507\04700\047) /Published (2011) /Type (Conference Proceedings) /firstpage (2160) /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 (Inderjit S\056 Dhillon\054 Pradeep K\056 Ravikumar\054 Ambuj Tewari) /lastpage (2168) >> endobj 3 0 obj << /Type /Catalog /Pages 1 0 R >> endobj 4 0 obj << /Contents 13 0 R /Rotate 0 /Resources << /XObject << /Im0 14 0 R >> /Font << /T1_4 15 0 R /T1_5 16 0 R /T1_2 17 0 R /T1_3 18 0 R /T1_0 19 0 R /T1_1 20 0 R >> /ProcSet [ /PDF /Text /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 5 0 obj << /Contents 21 0 R /Rotate 0 /Resources << /XObject << /Im0 22 0 R >> /Font << /T1_4 23 0 R /T1_2 24 0 R /T1_3 25 0 R /C0_0 26 0 R /T1_1 31 0 R /T1_0 32 0 R >> /ProcSet [ /PDF /Text /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 6 0 obj << /Contents 33 0 R /Rotate 0 /Resources << /XObject << /Im0 34 0 R >> /Font << /T1_4 35 0 R /T1_5 36 0 R /T1_2 37 0 R /T1_3 38 0 R /T1_0 39 0 R /T1_1 40 0 R /C0_0 41 0 R >> /ProcSet [ /PDF /Text /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 7 0 obj << /Contents 43 0 R /Rotate 0 /Resources << /XObject << /Im0 44 0 R >> /Font << /T1_1 45 0 R /T1_2 46 0 R /T1_3 47 0 R /C0_0 48 0 R /T1_0 50 0 R >> /ProcSet [ /PDF /Text /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 8 0 obj << /Contents 51 0 R /Rotate 0 /Resources << /XObject << /Im0 52 0 R >> /Font << /T1_6 53 0 R /T1_7 54 0 R /T1_4 55 0 R /T1_5 56 0 R /T1_2 57 0 R /T1_3 58 0 R /T1_0 59 0 R /T1_1 60 0 R /C0_0 61 0 R >> /ProcSet [ /PDF /Text /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 9 0 obj << /Contents 63 0 R /Rotate 0 /Resources << /XObject << /Im0 64 0 R >> /Font << /T1_6 65 0 R /T1_7 66 0 R /T1_4 67 0 R /T1_5 68 0 R /T1_2 69 0 R /T1_3 70 0 R /T1_0 71 0 R /T1_1 72 0 R /C0_0 73 0 R >> /ProcSet [ /PDF /Text /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 10 0 obj << /Contents 75 0 R /Rotate 0 /Resources << /XObject << /Im0 76 0 R >> /Font << /T1_6 77 0 R /T1_7 78 0 R /T1_4 79 0 R /T1_5 80 0 R /T1_2 81 0 R /T1_3 82 0 R /T1_0 83 0 R /T1_1 84 0 R /C0_0 85 0 R >> /ProcSet [ /PDF /Text /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 11 0 obj << /Contents 87 0 R /Rotate 0 /Resources << /XObject << /Im0 88 0 R >> /Font << /T1_4 89 0 R /T1_5 90 0 R /T1_2 91 0 R /T1_3 92 0 R /T1_0 93 0 R /T1_1 94 0 R /C0_0 95 0 R >> /ProcSet [ /PDF /Text /ImageB /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 12 0 obj << /Contents 97 0 R /Rotate 0 /Resources << /XObject << /Im0 98 0 R >> /Font << /T1_4 99 0 R /T1_2 100 0 R /T1_3 101 0 R /T1_0 102 0 R /T1_1 103 0 R >> /ProcSet [ /PDF /Text /ImageC ] >> /CropBox [ 0 0 612 792 ] /Parent 1 0 R /MediaBox [ 0 0 612 792 ] /Type /Page >> endobj 13 0 obj << /Length 5638 /Filter /FlateDecode >> stream HWKϯ4~wDC=/wO>]WW_}q' -0J0K=][\|~}`Vf/)F~vx.v2]J 9¼P##ie3G֛ H/q1{{ {]`a(tOȂ,,QC柦x+=|*{ I 5h~L[X-w4V19NMWL|Dpk$X.9ʄ(KMARA$w'3|h!Bjʨgo,8?yn.lvI.ĽN VH,|kVí|<`Ls%8;?3\n]^n&H A֍jJ4a_X' Pݿn}~e~!Jccp%>O8{D\2#U!#BwOIuK]0WN 9Aj]dNO*j =J۴5T'c\;e Oսkuo $GB`LA`L*KSES 1{58`fЋø,)iǰ1{MDN'(hn)TTBn{>,Xvh.(a}I R͆TJpc!U.yNkܟaHD͂Iė.o09CFHMU^!FR
IS' $m~nvV\:NjiYgtEst#+Pܼs%IdEp,Tn%SV<h[x,Οoe>}JwϔI۟[]*XphAruf eNJKJ
z>6aMԥcJX&XS{L$ז1}MȊ8z87C+و0#sCpZɴzzҔHdØpl6's7T:Uh[sy%eh
Q(s߯UZ+V+.VNP]9\ 1_ƦT:>I0fc M.>U{$݁<6uo
>IPyr=CdaHeOH+V$VjS,=%a!!+3<I:òo3ux{
W}1c_4&`ƤNAvyoRܥS}kV`0BfBj.DSb2^C}|ܖX |xF}ByĶ~XER%YXpW,>i5n:Da@!6cj9B!o26cMIr$
]RO&C,EDԓfzV3'% Qwgs,Ǫ"*+DKf*/oT ~ttfxp4?Hi)95^
uUn-yeh:M&2쐀\pst'1zO0Yh`h"ԋA-GZNh`,se6d
i
%29;Ci֮.M5P!ol`@I7㬜T
xqB=igh ۺSeoPtd@w2h