Nikita Doikov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Nikita Doikov has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Yurii Nesterov
Corvinus Centre for Operations Research at Corvinus Institute for Advanced Studies, Corvinus University of Budapest, 1093 Budapest, Hungary
11 shared publications - Martin Jaggi
EPFL EPFL EPFL
4 shared publications - Geovani Nunes Grapiglia
ICTEAM/INMA, Université Catholique de Louvain, Louvain-la-Neuve, Belgium
2 shared publications Konstantin Mishchenko
CNRS, ENS, Inria Sierra, 75005 Paris, France
2 shared publications- Sebastian U. Stich
CISPA Helmholtz Center for Information Security
2 shared publications - Anastasia Koloskova
Equal contribution
1 shared publication
Latest Publications
- Open Access
Universal Reduced-Operator Method and High-Order Global Curvature Bounds
In this paper, we develop a new concept of Global Curvature Bound for an arbitrary nonlinear operator between abstract metric spaces. We use this notion to characterize the global complexity of high-order algorithms solving composite variational problems, which include convex minimization and min-max problems. We develop the new universal Reduced-Operator Method, which automatically achieves the fastest universal rate within our class, while our analysis does not need any specific assumptions about smoothness of the target nonlinear operator. Every step of our universal method of order $p \geq 1$ requires access to the $p$-th order derivative of the operator and the solution of a strictly monotone doubly regularized subproblem. For $p = 1$, this corresponds to computing the standard Jacobian matrix of the operator and solving a simple monotone subproblem, which can be handled using different methods of Convex Optimization.Open AccessUniversal Reduced-Operator Method and High-Order Global Curvature Bounds
In this paper, we develop a new concept of Global Curvature Bound for an arbitrary nonlinear operator between abstract metric spaces. We use this notion to characterize the global complexity of high-order algorithms solving composite variational problems, which include convex minimization and min-max problems. We develop the new universal Reduced-Operator Method, which automatically achieves the fastest universal rate within our class, while our analysis does not need any specific assumptions about smoothness of the target nonlinear operator. Every step of our universal method of order $p \geq 1$ requires access to the $p$-th order derivative of the operator and the solution of a strictly monotone doubly regularized subproblem. For $p = 1$, this corresponds to computing the standard Jacobian matrix of the operator and solving a simple monotone subproblem, which can be handled using different methods of Convex Optimization. - Open Access
On the Complexity of Lower-Order Implementations of Higher-Order Methods
In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous $p$th-order derivatives, starting from $p \geq 1$. The method, however, only requires derivative information up to order $(p-1)$, since the $p$th-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of computing finite-difference approximations at every iteration, we reuse each approximation for $m$ consecutive iterations before recomputing it, with $m \geq 1$ as a key parameter. As a result, we obtain an adaptive method of order $(p-1)$ that requires no more than $O(ε^{-\frac{p+1}{p}})$ iterations to find an $ε$-approximate stationary point of the objective function and that, for the choice $m=(p-1)n + 1$, where $n$ is the problem dimension, takes no more than $O(n^{1/p}ε^{-\frac{p+1}{p}})$ oracle calls of order $(p-1)$. This improves previously known bounds for tensor methods with finite-difference approximations in terms of the problem dimension.Open AccessOn the Complexity of Lower-Order Implementations of Higher-Order Methods
In this work, we propose a method for minimizing non-convex functions with Lipschitz continuous $p$th-order derivatives, starting from $p \geq 1$. The method, however, only requires derivative information up to order $(p-1)$, since the $p$th-order derivatives are approximated via finite differences. To ensure oracle efficiency, instead of computing finite-difference approximations at every iteration, we reuse each approximation for $m$ consecutive iterations before recomputing it, with $m \geq 1$ as a key parameter. As a result, we obtain an adaptive method of order $(p-1)$ that requires no more than $O(ε^{-\frac{p+1}{p}})$ iterations to find an $ε$-approximate stationary point of the objective function and that, for the choice $m=(p-1)n + 1$, where $n$ is the problem dimension, takes no more than $O(n^{1/p}ε^{-\frac{p+1}{p}})$ oracle calls of order $(p-1)$. This improves previously known bounds for tensor methods with finite-difference approximations in terms of the problem dimension. - Open Access
- 24 September 2025
- Published by Springer Nature in Optimization Letters
- Vol. 19 (9) , 1759-1778
Lower complexity bounds for minimizing regularized functions
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 the objective. The smooth part has Hölder continuous gradient of degree $$\nu \in [0, 1]$$ and is accessible by a black-box local oracle. The composite part is a power of a norm. We prove that the best possible rate for the first-order methods in the large-scale setting for Euclidean norms is of the order $$O(k^{- p(1 + 3\nu ) / (2(p - 1 - \nu ))})$$ for the functional residual, where k is the iteration counter and $$p > 2$$ is the power of regularization. Our formulation covers several cases, including computation of the Cubically regularized Newton step by the first-order gradient methods, in which case the rate becomes $$O(k^{-6})$$ . It can be achieved by the fast gradient method. Thus, our result proves the latter rate to be optimal. We also discover lower complexity bounds for non-Euclidean norms.- 24 September 2025
- Published by Springer Nature in Optimization Letters
- Vol. 19 (9) , 1759-1778
Open AccessLower complexity bounds for minimizing regularized functions
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 the objective. The smooth part has Hölder continuous gradient of degree $$\nu \in [0, 1]$$ and is accessible by a black-box local oracle. The composite part is a power of a norm. We prove that the best possible rate for the first-order methods in the large-scale setting for Euclidean norms is of the order $$O(k^{- p(1 + 3\nu ) / (2(p - 1 - \nu ))})$$ for the functional residual, where k is the iteration counter and $$p > 2$$ is the power of regularization. Our formulation covers several cases, including computation of the Cubically regularized Newton step by the first-order gradient methods, in which case the rate becomes $$O(k^{-6})$$ . It can be achieved by the fast gradient method. Thus, our result proves the latter rate to be optimal. We also discover lower complexity bounds for non-Euclidean norms. - Open Access
- 12 August 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 219 (1-2) , 1-39
Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method
We study the composite convex optimization problems with a quasi-self-concordant smooth component. This problem class naturally interpolates between classic self-concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball optimization oracle. In this paper, we show that for minimizing quasi-self-concordant functions we can use instead the basic Newton method with gradient regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the dual Newton method, and based on it, develop the corresponding accelerated Newton scheme for this problem class. This scheme further improves the complexity factor of the basic method, matching—up to logarithmic factors—the state-of-the-art rates of accelerated methods achieved within the framework of the ball optimization oracle. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton method applied to several practical problems, including logistic regression, soft maximum, and matrix scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.
- 12 August 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 219 (1-2) , 1-39
Open AccessMinimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method
We study the composite convex optimization problems with a quasi-self-concordant smooth component. This problem class naturally interpolates between classic self-concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball optimization oracle. In this paper, we show that for minimizing quasi-self-concordant functions we can use instead the basic Newton method with gradient regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the dual Newton method, and based on it, develop the corresponding accelerated Newton scheme for this problem class. This scheme further improves the complexity factor of the basic method, matching—up to logarithmic factors—the state-of-the-art rates of accelerated methods achieved within the framework of the ball optimization oracle. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton method applied to several practical problems, including logistic regression, soft maximum, and matrix scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.
- Open Access
Gradient-Normalized Smoothness for Optimization with Approximate Hessians
In this work, we develop new optimization algorithms that use approximate second-order information combined with the gradient regularization technique to achieve fast global convergence rates for both convex and non-convex objectives. The key innovation of our analysis is a novel notion called Gradient-Normalized Smoothness, which characterizes the maximum radius of a ball around the current point that yields a good relative approximation of the gradient field. Our theory establishes a natural intrinsic connection between Hessian approximation and the linearization of the gradient. Importantly, Gradient-Normalized Smoothness does not depend on the specific problem class of the objective functions, while effectively translating local information about the gradient field and Hessian approximation into the global behavior of the method. This new concept equips approximate second-order algorithms with universal global convergence guarantees, recovering state-of-the-art rates for functions with Hölder-continuous Hessians and third derivatives, quasi-self-concordant functions, as well as smooth classes in first-order optimization. These rates are achieved automatically and extend to broader classes, such as generalized self-concordant functions. We demonstrate direct applications of our results for global linear rates in logistic regression and softmax problems with approximate Hessians, as well as in non-convex optimization using Fisher and Gauss-Newton approximations.
Open AccessGradient-Normalized Smoothness for Optimization with Approximate Hessians
In this work, we develop new optimization algorithms that use approximate second-order information combined with the gradient regularization technique to achieve fast global convergence rates for both convex and non-convex objectives. The key innovation of our analysis is a novel notion called Gradient-Normalized Smoothness, which characterizes the maximum radius of a ball around the current point that yields a good relative approximation of the gradient field. Our theory establishes a natural intrinsic connection between Hessian approximation and the linearization of the gradient. Importantly, Gradient-Normalized Smoothness does not depend on the specific problem class of the objective functions, while effectively translating local information about the gradient field and Hessian approximation into the global behavior of the method. This new concept equips approximate second-order algorithms with universal global convergence guarantees, recovering state-of-the-art rates for functions with Hölder-continuous Hessians and third derivatives, quasi-self-concordant functions, as well as smooth classes in first-order optimization. These rates are achieved automatically and extend to broader classes, such as generalized self-concordant functions. We demonstrate direct applications of our results for global linear rates in logistic regression and softmax problems with approximate Hessians, as well as in non-convex optimization using Fisher and Gauss-Newton approximations.
- Open Access
- 12 March 2025
- Published by Springer Nature in Journal of Scientific Computing
- Vol. 103 (1) , 1-30
First and Zeroth-Order Implementations of the Regularized Newton Method with Lazy Approximated Hessians
In this work, we develop first-order (Hessian-free) and zeroth-order (derivative-free) implementations of the Cubically Regularized Newton Method for solving general non-convex optimization problems. For that, we employ finite difference approximations of the derivatives. We use a special adaptive search procedure in our algorithms, which simultaneously fits both the regularization constant and the parameters of the finite difference approximations. It makes our schemes free from the need to know the actual Lipschitz constants. Additionally, we equip our algorithms with the lazy Hessian update that reuses a previously computed Hessian approximation matrix for several iterations. Specifically, we prove the global complexity bound of $$\mathcal {O}( n^{1/2} \epsilon ^{-3/2})$$ function and gradient evaluations for our new Hessian-free method, and a bound of $$\mathcal {O}( n^{3/2} \epsilon ^{-3/2} )$$ function evaluations for the derivative-free method, where n is the dimension of the problem and $$\epsilon $$ is the desired accuracy for the gradient norm. These complexity bounds significantly improve the previously known ones in terms of the joint dependence on n and $$\epsilon $$ , for the first-order and zeroth-order non-convex optimization.- 12 March 2025
- Published by Springer Nature in Journal of Scientific Computing
- Vol. 103 (1) , 1-30
Open AccessFirst and Zeroth-Order Implementations of the Regularized Newton Method with Lazy Approximated Hessians
In this work, we develop first-order (Hessian-free) and zeroth-order (derivative-free) implementations of the Cubically Regularized Newton Method for solving general non-convex optimization problems. For that, we employ finite difference approximations of the derivatives. We use a special adaptive search procedure in our algorithms, which simultaneously fits both the regularization constant and the parameters of the finite difference approximations. It makes our schemes free from the need to know the actual Lipschitz constants. Additionally, we equip our algorithms with the lazy Hessian update that reuses a previously computed Hessian approximation matrix for several iterations. Specifically, we prove the global complexity bound of $$\mathcal {O}( n^{1/2} \epsilon ^{-3/2})$$ function and gradient evaluations for our new Hessian-free method, and a bound of $$\mathcal {O}( n^{3/2} \epsilon ^{-3/2} )$$ function evaluations for the derivative-free method, where n is the dimension of the problem and $$\epsilon $$ is the desired accuracy for the gradient norm. These complexity bounds significantly improve the previously known ones in terms of the joint dependence on n and $$\epsilon $$ , for the first-order and zeroth-order non-convex optimization. - Open Access
On Convergence of Incremental Gradient for Non-Convex Smooth Functions
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 practical convergence behavior. However, their optimization properties in theory, especially for non-convex smooth functions, remain incompletely explored. This paper delves into the convergence properties of SGD algorithms with arbitrary data ordering, within a broad framework for non-convex smooth functions. Our findings show enhanced convergence guarantees for incremental gradient and single shuffle SGD. Particularly if $n$ is the training set size, we improve $n$ times the optimization term of convergence guarantee to reach accuracy $\varepsilon$ from $O(n / \varepsilon)$ to $O(1 / \varepsilon)$.Open AccessOn Convergence of Incremental Gradient for Non-Convex Smooth Functions
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 practical convergence behavior. However, their optimization properties in theory, especially for non-convex smooth functions, remain incompletely explored. This paper delves into the convergence properties of SGD algorithms with arbitrary data ordering, within a broad framework for non-convex smooth functions. Our findings show enhanced convergence guarantees for incremental gradient and single shuffle SGD. Particularly if $n$ is the training set size, we improve $n$ times the optimization term of convergence guarantee to reach accuracy $\varepsilon$ from $O(n / \varepsilon)$ to $O(1 / \varepsilon)$. - Open Access
Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions
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 finely-grained convergence statements -- particularly not for non-convex problems. Striving for a more intricate characterization of complexity, we introduce a unique concept termed graded non-convexity. This allows to partition the class of non-convex problems into a nested chain of subclasses. Interestingly, many traditional non-convex objectives, including partially convex problems, matrix factorizations, and neural networks, fall within these subclasses. As a second contribution, we propose gradient methods with spectral preconditioning, which employ inexact top eigenvectors of the Hessian to address the ill-conditioning of the problem, contingent on the grade. Our analysis reveals that these new methods provide provably superior convergence rates compared to basic gradient descent on applicable problem classes, particularly when large gaps exist between the top eigenvalues of the Hessian. Our theory is validated by numerical experiments executed on multiple practical machine learning problems.
Open AccessSpectral Preconditioning for Gradient Methods on Graded Non-convex Functions
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 finely-grained convergence statements -- particularly not for non-convex problems. Striving for a more intricate characterization of complexity, we introduce a unique concept termed graded non-convexity. This allows to partition the class of non-convex problems into a nested chain of subclasses. Interestingly, many traditional non-convex objectives, including partially convex problems, matrix factorizations, and neural networks, fall within these subclasses. As a second contribution, we propose gradient methods with spectral preconditioning, which employ inexact top eigenvectors of the Hessian to address the ill-conditioning of the problem, contingent on the grade. Our analysis reveals that these new methods provide provably superior convergence rates compared to basic gradient descent on applicable problem classes, particularly when large gaps exist between the top eigenvalues of the Hessian. Our theory is validated by numerical experiments executed on multiple practical machine learning problems.
- 3 January 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 34 (1) , 27-56
Super-Universal Regularized Newton Method
We analyze the performance of a variant of the Newton method with quadratic regularization for solving composite convex minimization problems. At each step of our method, we choose a regularization parameter proportional to a certain power of the gradient norm at the current point. We introduce a family of problem classes characterized by the Hölder continuity of either the second or third derivative. Then we present the method with a simple adaptive search procedure allowing an automatic adjustment to the problem class with the best global complexity bounds, without knowing specific parameters of the problem. In particular, for the class of functions with a Lipschitz continuous third derivative, we get the global [Formula: see text] rate, which was previously attributed to third-order tensor methods. When the objective function is uniformly convex, we justify an automatic acceleration of our scheme, resulting in a faster global rate and local superlinear convergence. The switching between the different rates (sublinear, linear, and superlinear) is automatic. Again, for that, no a priori knowledge of parameters is needed.
- 3 January 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 34 (1) , 27-56
Super-Universal Regularized Newton Method
We analyze the performance of a variant of the Newton method with quadratic regularization for solving composite convex minimization problems. At each step of our method, we choose a regularization parameter proportional to a certain power of the gradient norm at the current point. We introduce a family of problem classes characterized by the Hölder continuity of either the second or third derivative. Then we present the method with a simple adaptive search procedure allowing an automatic adjustment to the problem class with the best global complexity bounds, without knowing specific parameters of the problem. In particular, for the class of functions with a Lipschitz continuous third derivative, we get the global [Formula: see text] rate, which was previously attributed to third-order tensor methods. When the objective function is uniformly convex, we justify an automatic acceleration of our scheme, resulting in a faster global rate and local superlinear convergence. The switching between the different rates (sublinear, linear, and superlinear) is automatic. Again, for that, no a priori knowledge of parameters is needed.
- Open Access
Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method
We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball-minimization oracle. In this paper, we show that for minimizing Quasi-Self-Concordant functions we can use instead the basic Newton Method with Gradient Regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the Dual Newton Method, and based on it, develop the corresponding Accelerated Newton Scheme for this problem class, which further improves the complexity factor of the basic method. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton Method applied to several practical problems, including Logistic Regression, Soft Maximum, and Matrix Scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.
Open AccessMinimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method
We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball-minimization oracle. In this paper, we show that for minimizing Quasi-Self-Concordant functions we can use instead the basic Newton Method with Gradient Regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the Dual Newton Method, and based on it, develop the corresponding Accelerated Newton Scheme for this problem class, which further improves the complexity factor of the basic method. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton Method applied to several practical problems, including Logistic Regression, Soft Maximum, and Matrix Scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.