Provable and Practical Methods for Nonconvex Optimazation
Event details
| Date | 25.02.2019 |
| Hour | 10:00 › 12:00 |
| Speaker | Fatih Sahin |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Martin Jaggi
Thesis advisor: Prof. Volcan Cevher
Co-examiner: Prof. Daniel Kuhn
Abstract
Due to its capability of handling large scale problems, nonlinear and nonconvex optimization has increased in popularity in the last decade. Modern applications in signal processing, statistics and machine learning exhibits distinguished performance with the nonconvex models. These models often offer reduced prediction times and can better capture the problem structure. Therefore, it is of high importance to design practical and efficient algorithms for this class of problems. The challenge in contemporary nonconvex optimization is to establish global convergence guarantees. In this proposal, we are going to discuss three papers which focuses on these challenges. First paper proposes a conditional gradient framework which is a combination of homotopy and smoothing techniques for a composite convex minimization template. Even though it is a convex method, it can efficiently deal large scale semidefinite programming(SDP) problems in small space via sketching. Second paper theoretically analyzes the convergence properties of a powerful yet experimental splitting method for solving large scale SDP's. The last paper provides a primal dual Lagrangian-based method for a wider class of problems beyond SDP's. However, the authors does not demonstrate any experimental results. Finally, we conclude with our research proposal on how to address the aforementioned challenges while maintaining some key aspects of the discussed papers.
Background papers
A Conditional Gradient Framework for Composite Convex Minimizationwith Applications to Semidefinite Programming, by Yurtsever, A., et al.
Local Minima and Convergencein Low-Rank Semidefinite Programming, by Burer, S., Monteiro, R.
Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence by Bolte, J., et al.
Exam president: Prof. Martin Jaggi
Thesis advisor: Prof. Volcan Cevher
Co-examiner: Prof. Daniel Kuhn
Abstract
Due to its capability of handling large scale problems, nonlinear and nonconvex optimization has increased in popularity in the last decade. Modern applications in signal processing, statistics and machine learning exhibits distinguished performance with the nonconvex models. These models often offer reduced prediction times and can better capture the problem structure. Therefore, it is of high importance to design practical and efficient algorithms for this class of problems. The challenge in contemporary nonconvex optimization is to establish global convergence guarantees. In this proposal, we are going to discuss three papers which focuses on these challenges. First paper proposes a conditional gradient framework which is a combination of homotopy and smoothing techniques for a composite convex minimization template. Even though it is a convex method, it can efficiently deal large scale semidefinite programming(SDP) problems in small space via sketching. Second paper theoretically analyzes the convergence properties of a powerful yet experimental splitting method for solving large scale SDP's. The last paper provides a primal dual Lagrangian-based method for a wider class of problems beyond SDP's. However, the authors does not demonstrate any experimental results. Finally, we conclude with our research proposal on how to address the aforementioned challenges while maintaining some key aspects of the discussed papers.
Background papers
A Conditional Gradient Framework for Composite Convex Minimizationwith Applications to Semidefinite Programming, by Yurtsever, A., et al.
Local Minima and Convergencein Low-Rank Semidefinite Programming, by Burer, S., Monteiro, R.
Nonconvex Lagrangian-Based Optimization: Monitoring Schemes and Global Convergence by Bolte, J., et al.
Practical information
- General public
- Free