Abstrakt. År 1963 föreslog Polyak ett enkelt tillstånd som är tillräckligt för att visa en global linjär konvergenshastighet för lutning nedstigning. Detta villkor är ett specialfall av Lojasiewicz ojämlikhet föreslås under samma år, och det kräver inte stark konvexitet (eller ens konvexitet). I detta arbete visar vi att denna mycket äldre polyak-Lojasiewicz (PL) ojämlikhet faktiskt är svagare än de viktigaste villkor som har undersökts för att visa linjär konvergens utan stark konvexitet under de senaste 25 åren. Vi använder också PL ojämlikhet för att ge nya analyser av randomiserade och giriga koordinat nedstigningsmetoder, tecken-baserade lutning nedstigningsmetoder, och stokastiska lutningsmetoder i den klassiska inställningen (med minskande eller konstant steg-storlekar) samt variansreducerad inställning. Vi föreslår vidare en generalisering som gäller proximal-gradient metoder för icke-smooth optimering, vilket leder till enkla bevis på linjär konvergens av dessa metoder. Längs vägen ger vi enkla konvergensresultat för en mängd olika problem i maskininlärning: minst kvadrater, logistisk regression, öka, motståndskraftig backpropagation, L1-regularisering, stöd vektor maskiner, stokastisk dubbel koordinat stigning, och stokastisk varians-reducerad gradient metoder.
Till exempel visade REF att ojämlikheten i polyak-Lojasiewicz (PL) räcker för att garantera en global linjär konvergens för (proximal) lutning nedstigningsmetoder.
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-\L{}ojasiewicz Condition
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}