Vi studerar minimeringen av en konvex funktion f (X) över uppsättningen n × n positiva semi-definita matriser, men när problemet omarbetas som minU g (U ) := f (U U ), med U (U U ), R n×r och r ≤ n. Vi studerar prestanda lutning nedstigning på g-som vi refererar till som Factored Gradient Descent (Fgd)-under standardantaganden på den ursprungliga funktionen f. Vi ger en regel för att välja stegstorlek och, med detta val, visar att den lokala konvergensen av Fgd speglar som standard lutning nedstigning på den ursprungliga f : d.v.s., efter k steg, felet är O(1/k) för slät f, och exponentiellt liten i k när f är (begränsad) starkt konvex. Dessutom tillhandahåller vi ett förfarande för att initiera Fgd för (begränsade) starkt konvexa mål och när man bara har tillgång till f via en första ordning orakel; för flera problemfall leder en sådan korrekt initialisering till globala konvergensgarantier. Fgd och liknande förfaranden används i stor utsträckning i praktiken för problem som kan ses som matris factorization. Såvitt vi vet är detta det första dokumentet som ger exakta konvergensgarantier för allmänna konvexa funktioner enligt standardiserade konvexa antaganden.
Trots denna begränsning är REF det första papper som bevisligen löser det oöverskådliga omparametriserade problemet i (2) för generiska konvexa funktioner f, enligt gemensamma konvexa antaganden.
Dropping Convexity for Faster Semi-definite Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}