Timezone: »

Poster
Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
Quoc Tran-Dinh · Nate H Pham · Lam Nguyen

Thu Jul 16 06:00 AM -- 06:45 AM &amp; Thu Jul 16 06:00 PM -- 06:45 PM (PDT) @ None #None
We develop two new stochastic Gauss-Newton algorithms for solving a class of non-convex stochastic compositional optimization problems frequently arising in practice. We consider both the expectation and finite-sum settings under standard assumptions, and use both classical stochastic and SARAH estimators for approximating function values and Jacobians. In the expectation case, we establish $\BigO{\varepsilon^{-2}}$ iteration-complexity to achieve a stationary point in expectation and estimate the total number of stochastic oracle calls for both function value and its Jacobian, where $\varepsilon$ is a desired accuracy. In the finite sum case, we also estimate $\BigO{\varepsilon^{-2}}$ iteration-complexity and the total oracle calls with high probability. To our best knowledge, this is the first time such global stochastic oracle complexity is established for stochastic Gauss-Newton methods. Finally, we illustrate our theoretical results via two numerical examples on both synthetic and real datasets.

#### Author Information

##### Nate H Pham (University of North Carolina at Chapel Hill)

I am a 3rd year PhD student in Operations Research in Department of Statistics and Operations Research at University of North Carolina at Chapel Hill. I am currently working on stochastic methods for non-convex optimization with applications in machine learning, deep learning, and reinforcement learning under supervision by Dr. Quoc Tran-Dinh. In addition, I am also collaborating with Dr. Lam M. Nguyen and Dr. Dzung T. Phan at IBM Thomas J. Watson Research Center. I come from Vietnam where I had my bachelor in Computer Engineering from Department of Computer Science and Engineering, Ho Chi Minh City University of Technology (Bach Khoa University). During my undergrad, I was a member of BKIT Hardware Club and participated in the Vietnam Robot Contest under BK4/BKIT Number One team in 2013. My hobbies are travelling with my wife and exploring new places.