  For solving large-scale non-convex problems, we propose inexact variants of
trust region and adaptive cubic regularization methods, which, to increase
efficiency, incorporate various approximations. In particular, in addition to
approximate sub-problem solves, both the Hessian and the gradient are suitably
approximated. Using rather mild conditions on such approximations, we show that
our proposed inexact methods achieve similar optimal worst-case iteration
complexities as the exact counterparts. Our proposed algorithms, and their
respective theoretical analysis, do not require knowledge of any unknowable
problem-related quantities, and hence are easily implementable in practice. In
the context of finite-sum problems, we then explore randomized sub-sampling
methods as ways to construct the gradient and Hessian approximations and
examine the empirical performance of our algorithms on some real datasets.
