Abstrakt. Vi introducerar ett ramverk för kvasi-Newton framåt-bakåt delning algoritmer (proximal kvasiNewton metoder) med en metrisk inducerad av diagonal ± rank-r symmetriska positiva bestämda matriser. Denna speciella typ av metriska möjliggör en mycket effektiv utvärdering av den proximala kartläggningen. Nyckeln till denna effektivitet är en allmän proximal analys i den nya mätmetoden. Genom att använda dualitet härleds formler som relaterar den proximala kartläggningen i en rank-r modifierad metrisk till den ursprungliga metrisken. Vi beskriver också effektiva implementeringar av närhetsberäkningen för en stor klass av funktioner; implementationerna utnyttjar bitvis det dubbla problemets linjära karaktär. Sedan tillämpar vi dessa resultat på acceleration av sammansatta konvexa minimeringsproblem, vilket leder till eleganta kvasi-Newton-metoder för vilka vi bevisar konvergens. Algoritmen testas på flera numeriska exempel och jämförs med en omfattande lista över alternativ i litteraturen. Vår kvasi-Newton uppdelningsalgoritm med den föreskrivna metriska jämförs gynnsamt mot state-of-the-art. Algoritmen har omfattande tillämpningar inklusive signalbehandling, sparsam återhämtning, maskininlärning och klassificering för att nämna några. Nyckelord. Framåtvänd delning, kvasi-Newton, proximal analys, dualitet. AMS-ämnesklassificeringar. 65K05, 65K10, 90C25, 90C31. 1. Vad är det för fel på dig? Inledning. Convex optimering har visat sig vara mycket användbar för alla kvantitativa vetenskapsgrenar. En vanlig trend inom modern vetenskap är ökningen av storleken på dataset, vilket driver behovet av effektivare optimeringssystem. För storskaliga okonsekventa konvexa problem, har två klasser av metoder sett de mest framgångsrika: begränsade minne kvasi-Newton metoder och icke-linjär konjugat gradient (CG) metoder. Båda dessa metoder överträffar i allmänhet enklare metoder, såsom lutning nedstigning. Men många problem i applikationer har begränsningar eller bör modelleras naturligt som icke-smooth optimeringsproblem. En problemstruktur som är tillräckligt bred för att täcka många tillämpningar inom maskininlärning, signalbehandling, bildbehandling, datorseende (och många andra) är minimeringen av summan av två konvexa funktioner, den ena är smidig och den andra är icke-smooth och "enkel" på ett visst sätt. Gradienten nedstigningsmetoden har en naturlig förlängning till dessa strukturerade icke-smooth optimeringsproblem, som kallas proximal lutning nedstigning (som inkluderar projected gradient nedstigning som en del-fall) eller framåt-bakåt delning [5]. Algoritmiskt, förutom en gradient steg med avseende på den smidiga termen av målet, generaliseringen kräver att lösa proximala subproblem med avseende på den icke-smooth termen av målet. Fastigheten "enkel" ovan avser de proximala subproblemen. I många situationer kan dessa subproblem lösas analytiskt eller mycket effektivt. Men en förändring av metriska, vilket är det viktigaste inslaget i kvasi-Newton metoder eller icke-linjära CG, leder ofta till beräknings svårt subproblem. Medan konvergensen av proximala kvasi-Newton metoder har analyserats i viss utsträckning i samband med variabla metriska proximal gradient metoder, ägnas liten uppmärksamhet åt en effektiv utvärdering av subproblemen i den nya metriska. I denna uppsats betonar vi det faktum att kvasiNewton metoder konstruera en metrisk med en speciell struktur: metrisken uppdateras successivt med hjälp av låg rang matriser. Vi utvecklar effektiva kalkylregler för en generell rank-r modifierad metriska. Detta gör det möjligt att effektivt tillämpa populära kvasi-Newton-metoder, såsom SR1 (symmetrisk rank-1) och L-BFGS-metoderna på strukturerade icke-smooth-problem. SR1-metoden genomför en rank-1-uppdatering av mätmetoden och L-BFGS-metoden använder en rank-2-uppdatering. Vi betraktar resultaten i detta dokument som ett stort steg mot tillämpligheten av kvasi-Newton
Nyligen har proximala kartläggningar med avseende på mått av typ "identitet plus/minus rank R" studerats i REF.
On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Computer Science', 'Mathematics']}