Title: Optimization in Combinatorial and Non-Convex ML: Positive and Negative Results

Speaker: Dr Jean Honorio

Summary:
Several modern machine learning (ML) problems are combinatorial and non-convex, for which theoretical guarantees are quite limited. My long-term research goal is to uncover the general foundations of ML and optimization that drives empirical success. I aim to develop a set of optimization-theoretic frameworks and tools to bridge the aforementioned gaps, to further our understanding of continuous (possibly non-convex) relaxations of combinatorial problems, as well as our knowledge of non-convexity.

In this talk, I first focus on invex (non-convex) optimization problems, with some motivation from exploratory research on fairness and mixed linear regression. I present a generalization of gradient descent for the family of invex (non-convex) problems, which provably converges to the global minimum in polynomial time. Finally, for general non-convex problems, I show that any gradient-based algorithm, requires an exponential number of gradients to find the global minimum.

Second, when stochastic gradients are biased, how can we obtain convergence to the global minima of a complex convex function? I propose a provably convergent algorithm that requires more computational effort as the algorithm progresses through several gradient descent iterations. Interestingly, more complex algorithms do not converge in this regime.

Third, I discuss a difficult combinatorial problem over directed graphs with acyclicity constraints. Interestingly, using the statistical principle of identifiability, one can reduce the search space, and propose provably correct sequential optimization algorithms.

Finally, I focus on problems with high-order relationships, usually formulated as tensor optimization problems. I propose a convex conic form relaxation. To this end, I carefully define the Caratheodory symmetric tensor cone, and discuss its benefits in optimization.

Biography:
Jean Honorio is a Senior Lecturer at the School of Computing and Information Systems at The University of Melbourne and Adjunct Professor at Purdue University. Previously, Jean was an Assistant Professor in the Computer Science Department at Purdue University, as well as in the Statistics Department (by courtesy). Prior to joining Purdue, Jean was a postdoctoral associate at MIT, working with Tommi Jaakkola. His Erdős number is 3. His work has been partially funded by NSF. He is an editorial board reviewer of JMLR, and has served as area chair of NeurIPS and ICML, senior PC member of AAAI and IJCAI, PC member of NeurIPS, ICML, AIStats among other conferences and journals.

MEETING ID: 873 1557 5255; PASSWORD: 778635

WED 21 AUGUST 2024 16:00-17:00 (AEST, Melbourne Time)