Novel Optimization Algorithms for Data Science Applications
Abstract
A variety of applications in data science and machine learning can be formulated as large-scale nonconvex optimization problems. In general, these problems exhibit multiple locally optimal solutions that are not globally optimal. To tackle large-scale nonconvex problems in reasonable CPU times, there exist two main approaches- (i) utilize highly efficient heuristics that often provide good enough solutions in practice but forgo any guarantee on the quality of the solution; (ii) solve convex relaxations of the nonconvex problem perhaps followed by a rounding step and subsequently study suitable regimes under which these relaxations recover the solution of the original problem. In the context of data science applications, the aforementioned convex relaxations are generic semidefinite programming (SDP) relaxations which in spite of their polynomial time complexity are too slow and hence impractical for large-scale problems. This project aims at bridging this gap by developing scalable linear programming (LP) relaxations with theoretical performance guarantees for several nonconvex problems in clustering, joint object matching, Boolean matrix-tensor factorization, and sparse regression. By building upon and combining ideas from discrete and continuous optimization along with careful probabilistic analysis, the proposed research will provide scalable optimization algorithms with theoretical performance guarantees for these applications. In essence, this project illustrates the vital role of optimization techniques in modern data science applications.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 29, 2024
- Source ID
- FA95502310123
Entities
People
- Aida Khajavirad
Organizations
- Air Force Office of Scientific Research
- Lehigh University
- United States Air Force