컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0134 |
|---|---|
| 분류(Section) | Special Session |
| 분과(Session) | (SS-19) Optimization and Machine Learning (SS-19) |
| 발표시간(Time) | 19th-B-14:00 -- 14:30 |
| 영문제목 (Title(Eng.)) |
Exact optimal complexity of fixed-point iteration with possible infeasibility |
| 저자(Author(s)) |
Jisun Park1, Ernest K. Ryu1 Seoul National University1 |
| 초록본문(Abstract) | Despite the broad use of fixed-point iterations throughout applied mathematics, the optimal convergence rate of general fixed-point problems with nonexpansive nonlinear operators has not been established. One such example is the first-order optimization methods, on which the optimization solvers for large-scale optimization problems are based and built. Such general-purpose solvers must robustly detect infeasible or misspecified problem instances, but the computational complexity of first-order methods for doing so has yet to be formally studied. In this work, we present an acceleration mechanism for fixed-point iterations with nonexpansive operators, characterize the optimal accelerated rate of infeasibility detection, and provide a matching complexity lower bound to establish that is indeed the optimal accelerated rate. |
| 분류기호 (MSC number(s)) |
90C25 |
| 키워드(Keyword(s)) | Fixed-point iteration, first-order optimization methods, iteration complexity |
| 강연 형태 (Language of Session (Talk)) |
English |