서지주요정보
Efficient and convergent gradient methods for structured nonconvex-nonconcave minimax problems = 구조화된 비볼록-비오목 최소 최대화 문제를 위한 효율적이고 수렴하는 경사 방법들
서명 / 저자 Efficient and convergent gradient methods for structured nonconvex-nonconcave minimax problems = 구조화된 비볼록-비오목 최소 최대화 문제를 위한 효율적이고 수렴하는 경사 방법들 / Sucheol Lee.
발행사항 [대전 : 한국과학기술원, 2022].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8038603

소장위치/청구기호

학술문화관(도서관)2층 학위논문

DMAS 22005

휴대폰 전송

도서상태

이용가능(대출불가)

사유안내

반납예정일

리뷰정보

초록정보

Modern minimax problems, such as generative adversarial network, adversarial training, and fair training, are usually under a nonconvex-nonconcave setting. There are mainly two types of gradient methods for solving minimax problems: single-step method and multi-step method. However, existing methods either converge slowly or are not guaranteed to converge. In specific, the best known rate for a single-step method is only O(1/k) under a considered structured nonconvex-nonconcave setting, and existing multi-step methods are not guaranteed to converge under the same setting. Therefore, this dissertation provides two new single-step and multi-step methods that have a faster rate and guarantee convergence, respectively, under the structured nonconvex-nonconcave setting. First, we propose an efficient single-step method, named fast extragradient (FEG) method, which, for the first time, achieves the optimal O(1/k$^2$) rate on the squared gradient norm, under the negative comonotonicity condition on the saddle gradient operator. Next, we propose a multi-step method, named semi-anchored multi-step gradient descent ascent (SA-MGDA) method. The SA-MGDA has O(1/k) rate on the squared gradient norm under the weak Minty variational inequality condition on the saddle gradient operator, which is weaker than the negative comonotonicity.

생성적 적대 신경망 학습, 적대적 학습, 그리고 공정한 학습과 같은 현대의 최소 최대화 문제들은 대개 비볼록-비오목 환경에 있다. 이러한 최소 최대화 문제들을 풀기 위해 크게 단일 단계 방법과 다단계 방법 두 가지로 분류되는 경사 방법들이 사용되지만, 느린 속도로 수렴하거나 수렴하지 않는 방법만이 알려져 있다. 구체적으로, 논문에서 고려하는 구조화된 비볼록-비오목 환경에서 알려진 단일 단계 방법의 가장 좋은 수렴 속도는 O(1/k) 정도에 그치며, 알려진 다단계 방법들은 이러한 환경에서 수렴성이 보장되지 않는다. 따라서 이 논문에서는 빠른 수렴 속도를 갖는 단일 단계 방법 그리고 수렴성을 보장하는 다단계 방법을 제시한다. 먼저, 빠른 추가경사법이라 불리는 효율적인 단일 단계 방법을 제안한다. 이 방법은 안장 경사 연산자가 음의 코모노토니시티(comonotonicity) 조건을 만족하는 환경에서 처음으로 경사 노름 제곱에 대한 최적 수렴 속도 O(1/k$^2$)를 달성한다. 다음으로 반고정 다단계 경사 하강 상승법이라 이름 붙인 다단계 방법을 제안한다. 제안된 방법은 안장 경사 연산자가 음의 코모노토니시티 조건보다도 일반적인 약한 민티(Minty) 변분부등식 조건을 만족하는 환경에서 경사 노름 제곱에 대해 O(1/k) 속도로 수렴한다.

서지기타정보

서지기타정보
청구기호 {DMAS 22005
형태사항 v, 55 p. : 삽화 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 이수철
지도교수의 영문표기 : Donghwan Kim
지도교수의 한글표기 : 김동환
Including appendix
학위논문 학위논문(박사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 48-53
QR CODE qr code

책소개

전체보기

목차

전체보기

이 주제의 인기대출도서