Timezone: »

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 & 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

Quoc Tran-Dinh (The University of North Carolina at Chapel Hill)
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.

Lam Nguyen (IBM Research, Thomas J. Watson Research Center)

More from the Same Authors