Algorithm for group distributionally robust linear regression using block Lewis weights to achieve (1+ε) optimality in Õ(min{rank(A), m}^{1/3} ε^{-2/3}) linear-system solves.
Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We show that Newton's method converges globally at a linear rate for objective functions whose Hessians are stable. This class of problems includes many functions which are not strongly convex, such as logistic regression. Our linear convergence result is (i) affine-invariant, and holds even if an (ii) approximate Hessian is used, and if the subproblems are (iii) only solved approximately. Thus we theoretically demonstrate the superiority of Newton's method over first-order methods, which would only achieve a sublinear $O(1/t^2)$ rate under similar conditions.
verdicts
UNVERDICTED 2representative citing papers
INTHOP is a second-order method that bounds the difference between an approximate positive definite Hessian and the exact one within an interval, reuses the approximation when iterates stay inside it, and proves global convergence while showing fewer evaluations than steepest descent or quasi-Newton
citing papers explorer
-
INTHOP: A Second-Order Globally Convergent Method for Nonconvex Optimization
INTHOP is a second-order method that bounds the difference between an approximate positive definite Hessian and the exact one within an interval, reuses the approximation when iterates stay inside it, and proves global convergence while showing fewer evaluations than steepest descent or quasi-Newton