26 citations · 91 across the 27 of their papers we have counts for
29 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…
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…
Gradient-Normalized Smoothness for Optimization with Approximate Hessians
Andrei Semenov, Martin Jaggi, Nikita Doikov
In this work, we develop new optimization algorithms that use approximate second-order information combined with the gradient regularization technique to achieve fast global conver…
Improving Stochastic Cubic Newton with Momentum
El Mahdi Chayti, Nikita Doikov, Martin Jaggi
We study stochastic second-order methods for solving general non-convex optimization problems. We propose using a special version of momentum to stabilize the stochastic gradient a…
Cubic regularized subspace Newton for non-convex optimization
Jim Zhao, Aurelien Lucchi, Nikita Doikov
This paper addresses the optimization problem of minimizing non-convex continuous functions, which is relevant in the context of high-dimensional machine learning applications char…
Complexity of Minimizing Regularized Convex Quadratic Functions
Daniel Berg Thomsen, Nikita Doikov
In this work, we study the iteration complexity of gradient methods for minimizing convex quadratic functions regularized by powers of Euclidean norms. We show that, due to the uni…
Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions
Nikita Doikov, Sebastian U. Stich, Martin Jaggi
The performance of optimization methods is often tied to the spectrum of the objective Hessian. Yet, conventional assumptions, such as smoothness, do often not enable us to make fi…
First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians
Nikita Doikov, Geovani Nunes Grapiglia
In this work, we develop first-order (Hessian-free) and zero-order (derivative-free) implementations of the Cubically regularized Newton method for solving general non-convex optim…
Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method
Nikita Doikov
We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functio…
On Convergence of Incremental Gradient for Non-Convex Smooth Functions
Anastasia Koloskova, Nikita Doikov, Sebastian U. Stich +1
In machine learning and neural network optimization, algorithms like incremental gradient, and shuffle SGD are popular due to minimizing the number of cache misses and good practic…
Linearization Algorithms for Fully Composite Optimization
Maria-Luiza Vladarean, Nikita Doikov, Martin Jaggi +1
This paper studies first-order algorithms for solving fully composite optimization problems over convex and compact sets. We leverage the structure of the objective by handling its…
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…
Polynomial Preconditioning for Gradient Methods
Nikita Doikov, Anton Rodomanov
We study first-order methods with preconditioning for solving structured nonlinear convex optimization problems. We propose a new family of preconditioners generated by symmetric p…
Second-order optimization with lazy Hessians
Nikita Doikov, El Mahdi Chayti, Martin Jaggi
We analyze Newton's method with lazy Hessian updates for solving general possibly non-convex optimization problems. We propose to reuse a previously seen Hessian for several iterat…
Super-Universal Regularized Newton Method
Nikita Doikov, Konstantin Mishchenko, Yurii Nesterov
We analyze the performance of a variant of Newton method with quadratic regularization for solving composite convex minimization problems. At each step of our method, we choose reg…
Lower Complexity Bounds for Minimizing Regularized Functions
Nikita Doikov
In this paper, we establish lower bounds for the oracle complexity of the first-order methods minimizing regularized convex functions. We consider the composite representation of t…
Gradient Regularization of Newton Method with Bregman Distances
Nikita Doikov, Yurii Nesterov
In this paper, we propose a first second-order scheme based on arbitrary non-Euclidean norms, incorporated by Bregman distances. They are introduced directly in the Newton iterate…
Optimization Methods for Fully Composite Problems
Nikita Doikov, Yurii Nesterov
In this paper, we propose a new Fully Composite Formulation of convex optimization problems. It includes, as a particular case, the problems with functional constraints, max-type m…
Affine-invariant contracting-point methods for Convex Optimization
Nikita Doikov, Yurii Nesterov
In this paper, we develop new affine-invariant algorithms for solving composite convex minimization problems with bounded domain. We present a general framework of Contracting-Poin…
Convex optimization based on global lower second-order models
Nikita Doikov, Yurii Nesterov
In this paper, we present new second-order algorithms for composite convex optimization, called Contracting-domain Newton methods. These algorithms are affine-invariant and based o…
Stochastic Subspace Cubic Newton Method
Filip Hanzely, Nikita Doikov, Peter Richtárik +1
In this paper, we propose a new randomized second-order optimization algorithm---Stochastic Subspace Cubic Newton (SSCN)---for minimizing a high dimensional convex function . Ou…