Sammanfattning När det gäller att lösa ett konvext konkav bilinjärt sadelpunktsproblem (SPP) har det varit många arbeten med att studera komplexiteten hos första ordningens metoder. Dessa resultat handlar om övre komplexitetsgränser, som på sin höjd kan avgöra hur många insatser som skulle garantera en lösning med önskad noggrannhet. I detta dokument strävar vi efter motsatt riktning genom att få fram lägre komplexitetsgränser för första ordningens metoder för storskaliga SPP. Våra resultat gäller de metoder vars iterater ligger i den linjära spännvidden av tidigare första ordningens information, liksom mer generella metoder som producerar sina iterater på ett godtyckligt sätt baserat på första ordningens information. Vi arbetar först med den affint begränsade smidiga konvexa optimeringen som är ett specialfall av SPP. O(1/t) till O(1/t 2 ), och dessutom är O(1/t) optimal för konvexa problem. Dessutom visar vi att för starkt konvexa problem är O(1/t 2 ) den bästa möjliga konvergenshastigheten, medan det är känt att gradientmetoder kan ha linjär konvergens på obehindrade problem. Sedan utvidgar vi dessa resultat till allmänna SPP. Det visar sig att våra lägre komplexitetsgränser stämmer överens med flera etablerade övre komplexitetsgränser i litteraturen, och därmed är de snäva och indikerar att flera befintliga första ordningens metoder är optimala.
• När f är konvex nonsmooth med bilinjär sadelpunkt struktur, är den lägre komplexiteten bunden O(1/ε) REF.
Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Mathematics']}