För SGD-baserad distribuerad stokastisk optimering, beräknings komplexitet, mätt med konvergenshastigheten i fråga om antalet stokastiska gradientsamtal, och kommunikation komplexitet, mätt med antalet internode kommunikationsrundor, är två viktigaste prestandamått. Den klassiska dataparallell implementeringen av SGD över N-arbetare kan uppnå linjära hastigheter för dess konvergens, men drabbas av en internode kommunikation runt varje sats. Vi studerar nyttan av att använda dynamiskt ökande batchstorlekar i parallella SGD för stokastisk icke-konvex optimering genom att karakterisera den uppnådda konvergensen och det antal kommunikationsrundor som krävs. Vi visar att för stokastisk icke-konvex optimering under P-L-tillstånd, den klassiska data-parallell SGD med exponentiellt ökande batchstorlekar kan uppnå den snabbaste kända O(1/(N T )) konvergens med linjär speedup med endast log(T ) kommunikationsrundor. För allmän stokastisk icke-konvex optimering föreslår vi en katalyst-liknande algoritm för att uppnå den snabbaste kända O(1/ ε N T ) konvergens med endast O( ε N T log( T N )) kommunikationsrundor.
Resultatet av REF innebär att SGD med exponentiellt ökande batchstorlekar har ett liknande konvergensbeteende som fullfjädrad (icke-stokastisk) lutning nedstigning.
On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}