Min-Max Optimization에는 지수적으로 많은 쿼리가 필요함
요약
본 논문은 $[0,1]^d imes [0,1]^d$ 상의 비볼록-비오목(nonconvex-nonconcave) 함수 $f$의 min-max 최적화에 대한 쿼리 복잡도를 분석합니다. 오라클 접근을 통해 $f$와 그 기울기 $ abla f$를 사용할 수 있는 경우에도, $\varepsilon$-근사 정지점(stationary point)을 찾는 모든 알고리즘은 $1/\varepsilon$ 또는 차원 $d$에 대해 지수적인 횟수의 쿼리를 수행해야 함을 증명합니다.
핵심 포인트
- 비볼록-비오목 함수 $f$의 min-max 최적화는 높은 쿼리 복잡도를 가집니다.
- 함수 $f$와 그 기울기 $ abla f$에 대한 오라클 접근이 주어져도 지수적인 쿼리가 필요합니다.
- $\varepsilon$-근사 정지점을 찾는 알고리즘은 $1/\varepsilon$ 또는 차원 $d$에 대해 지수적 복잡도를 가집니다.
Computer Science > Data Structures and Algorithms
Title: Min-Max Optimization Requires Exponentially Many Queries
PDF 보기 초록: 우리는 $[0,1]^d \times [0,1]^d$ 상에서 비볼록-비오목 (nonconvex-nonconcave) 함수 $f$의 min-max 최적화 (min-max optimization)에 대한 쿼리 복잡도 (query complexity)를 연구합니다. 우리는 $f$와 그 기울기 (gradient) $\nabla f$에 대한 오라클 접근 (oracle access)이 주어졌을 때, $\varepsilon$-근사 정지점 ($\varepsilon$-approximate stationary point)을 찾는 모든 알고리즘은 $1/\varepsilon$ 또는 $d$에 대해 지수적인 (exponential) 횟수의 쿼리를 수행해야 함을 보여줍니다.
현재 탐색 컨텍스트:
서지 및 인용 도구
이 논사와 관련된 코드, 데이터 및 미디어
데모
추천 및 검색 도구
arXivLabs: 커뮤니티 협력자와 함께하는 실험적 프로젝트
arXivLabs는 협력자들이 우리 웹사이트에서 직접 새로운 arXiv 기능을 개발하고 공유할 수 있도록 하는 프레임워크입니다.
arXivLabs와 함께 활동하는 개인 및 조직은 개방성, 커뮤니티, 탁월함, 그리고 사용자 데이터 프라이버시라는 우리의 가치를 수용하고 받아들였습니다. arXiv는 이러한 가치에 전념하며, 이를 준수하는 파트너와만 협력합니다.
arXiv 커뮤니티에 가치를 더할 프로젝트 아이디어가 있습니까? arXivLabs에 대해 더 알아보기.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.LG의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기