10 papers
Primal Acceleration of Newton's Method
Nikita Doikov
We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one…
On Optimization Complexity of Second-Order Certified Unlearning
Nikita Doikov, Anastasia Koloskova
We study machine unlearning: the removal of memorized training data from a trained model. Specifically, we investigate the algorithmic complexity of certified unlearning from an op…
PACER: Acyclic Causal Discovery from Large-Scale Interventional Data
Ramon Viñas Torné, SÃlvia Fà bregas Salazar, Soyon Park +4
Inferring the structure of directed acyclic graphs (DAGs) from data is a central challenge in causal discovery, particularly in modern high-dimensional settings where large-scale i…
Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
El Mahdi Chayti, Nikita Doikov, Martin Jaggi
We study stochastic Cubic Newton methods for solving general possibly non-convex minimization problems. We propose a new framework, which we call the helper framework, that provide…
Universal Reduced-Operator Method and High-Order Global Curvature Bounds
Nikita Doikov, Yurii Nesterov
In this paper, we develop a new concept of Global Curvature Bound (GCB) for an arbitrary nonlinear operator between abstract metric spaces. We use this notion to characterize the g…
On the Complexity of Lower-Order Implementations of Higher-Order Methods
Nikita Doikov, Geovani Nunes Grapiglia
In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous th-order derivatives, starting from . The method, however, only require…