Stochastic lutning nedstigning (SGD) är en enkel och populär metod för att lösa stokastiska optimeringsproblem som uppstår i maskininlärning. För starkt konvexa problem var dess konvergensgrad känd för att vara O(log(T)/T ), genom att köra SGD for T iterations och returnera den genomsnittliga punkten. De senaste resultaten visade dock att man med hjälp av en annan algoritm kan få en optimal O(1/T ) hastighet. Detta kan få en att tro att standard SGD är suboptimal, och kanske även bör ersättas som en metod för val. I den här artikeln undersöker vi hur optimalt SGD är i en stokastisk miljö. Vi visar att för smidiga problem, algoritmen uppnår optimal O(1/T ) hastighet. Men för icke-smooth problem, konvergensen med genomsnitt kan verkligen vara  och detta är inte bara en artefakt av analysen. (log(T ) / T ), och detta är inte bara en artefakt av analysen. På flip-sidan visar vi att en enkel ändring av medelsteget räcker för att återställa O(1/T ) hastigheten, och ingen annan ändring av algoritmen är nödvändig. Vi presenterar också experimentella resultat som stöder våra resultat och pekar på öppna problem.
På senare tid har forskarna förbättrat den tidigare gränsen för det starkt konvexa förlustfunktionsfallet till O(1/T ) genom att använda α-Suffix medelvärde REF, vilket innebär att algoritmen kommer att returnera genomsnittet av den sista α-fraktionen av den tidigare erhållna sekvensen av prediktorer.
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}