Dmitriy Drusvyatskiy
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
Research Interests
Dmitriy Drusvyatskiy has a total of 57 co-authors. Here are the top co-authors by number of shared publications:
Damek Davis
School of ORIE, Cornell University, Ithaca, USA
10 shared publications- Aris Daniilidis
Institut für Stochastik und Wirtschaftsmathematik, VADOR E105-04 TU Wien, Wien, Austria
5 shared publications - Henry Wolkowicz
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada
4 shared publications - Alexander D. Ioffe
Department of Mathematics, Technion-Israel Institute of Technology, Haifa, Israel
3 shared publications - Damek Davis
School of Operations Research and Information Engineering, Cornell University, Ithaca, USA
3 shared publications Adrian S. Lewis
2 shared publications
Latest Publications
- Open Access
- 22 October 2025
- Published by Springer Nature in Mathematical Programming
- p. 1-66
Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth
A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers. In this work, we argue that this belief is inaccurate. We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function that merely exhibits fourth-order growth away from its minimizer. The adaptive stepsize we propose arises from an intriguing decomposition theorem: any such function admits a smooth manifold around the optimal solution—which we call the ravine—so that the function grows at least quadratically away from the ravine and has constant order growth along it. The ravine allows one to interlace many short gradient steps with a single long Polyak gradient step, which together ensure rapid convergence to the minimizer. We illustrate the theory and algorithm on the problems of matrix sensing and factorization and learning a single neuron in the overparameterized regime.
- 22 October 2025
- Published by Springer Nature in Mathematical Programming
- p. 1-66
Open AccessGradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth
A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers. In this work, we argue that this belief is inaccurate. We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function that merely exhibits fourth-order growth away from its minimizer. The adaptive stepsize we propose arises from an intriguing decomposition theorem: any such function admits a smooth manifold around the optimal solution—which we call the ravine—so that the function grows at least quadratically away from the ravine and has constant order growth along it. The ravine allows one to interlace many short gradient steps with a single long Polyak gradient step, which together ensure rapid convergence to the minimizer. We illustrate the theory and algorithm on the problems of matrix sensing and factorization and learning a single neuron in the overparameterized regime.
- Top Cited Papers
- 22 January 2025
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 26 (2) , 779-861
Active Manifolds, Stratifications, and Convergence to Local Minima in Nonsmooth Optimization
- 22 January 2025
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 26 (2) , 779-861
Top Cited PapersActive Manifolds, Stratifications, and Convergence to Local Minima in Nonsmooth Optimization
- Top Cited Papers
- 10 January 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 35 (1) , 157-179
Stochastic Optimization Over Proximally Smooth Sets
We introduce a class of stochastic algorithms for minimizing weakly convex functions over proximally smooth sets. As their main building blocks, the algorithms use simplified models of the objective function and the constraint set, along with a retraction operation to restore feasibility. All the proposed methods come equipped with a finite time efficiency guarantee in terms of a natural stationarity measure. We discuss consequences for nonsmooth optimization over smooth manifolds and over sets cut out by weakly convex inequalities.
- 10 January 2025
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 35 (1) , 157-179
Top Cited PapersStochastic Optimization Over Proximally Smooth Sets
We introduce a class of stochastic algorithms for minimizing weakly convex functions over proximally smooth sets. As their main building blocks, the algorithms use simplified models of the objective function and the constraint set, along with a retraction operation to restore feasibility. All the proposed methods come equipped with a finite time efficiency guarantee in terms of a natural stationarity measure. We discuss consequences for nonsmooth optimization over smooth manifolds and over sets cut out by weakly convex inequalities.
- 1 April 2024
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 13 (2)
Flat minima generalize for low-rank matrix recovery
Empirical evidence suggests that for a variety of overparameterized nonlinear models, most notably in neural network training, the growth of the loss around a minimizer strongly impacts its performance. Flat minima—those around which the loss grows slowly—appear to generalize well. This work takes a step towards understanding this phenomenon by focusing on the simplest class of overparameterized nonlinear models: those arising in low-rank matrix recovery. We analyse overparameterized matrix and bilinear sensing, robust principal component analysis, covariance matrix estimation and single hidden layer neural networks with quadratic activation functions. In all cases, we show that flat minima, measured by the trace of the Hessian, exactly recover the ground truth under standard statistical assumptions. For matrix completion, we establish weak recovery, although empirical evidence suggests exact recovery holds here as well. We complete the paper with synthetic experiments that illustrate our findings.
- 1 April 2024
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 13 (2)
Flat minima generalize for low-rank matrix recovery
Empirical evidence suggests that for a variety of overparameterized nonlinear models, most notably in neural network training, the growth of the loss around a minimizer strongly impacts its performance. Flat minima—those around which the loss grows slowly—appear to generalize well. This work takes a step towards understanding this phenomenon by focusing on the simplest class of overparameterized nonlinear models: those arising in low-rank matrix recovery. We analyse overparameterized matrix and bilinear sensing, robust principal component analysis, covariance matrix estimation and single hidden layer neural networks with quadratic activation functions. In all cases, we show that flat minima, measured by the trace of the Hessian, exactly recover the ground truth under standard statistical assumptions. For matrix completion, we establish weak recovery, although empirical evidence suggests exact recovery holds here as well. We complete the paper with synthetic experiments that illustrate our findings.
- 5 September 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 207 (1-2) , 145-190
Stochastic algorithms with geometric step decay converge linearly on sharp functions
- 5 September 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 207 (1-2) , 145-190
Stochastic algorithms with geometric step decay converge linearly on sharp functions
- 14 July 2023
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 151 (11) , 4751-4756
The slope robustly determines convex functions
We show that the deviation between the slopes of two convex functions controls the deviation between the functions themselves. This result reveals that the slope—a one dimensional construct—robustly determines convex functions, up to a constant of integration.
- 14 July 2023
- Published by American Mathematical Society (AMS) in Proceedings of the American Mathematical Society
- Vol. 151 (11) , 4751-4756
The slope robustly determines convex functions
We show that the deviation between the slopes of two convex functions controls the deviation between the functions themselves. This result reveals that the slope—a one dimensional construct—robustly determines convex functions, up to a constant of integration.
- Open Access
Stochastic Optimization under Distributional Drift
We consider the problem of minimizing a convex function that is evolving according to unknown and possibly stochastic dynamics, which may depend jointly on time and on the decision variable itself. Such problems abound in the machine learning and signal processing literature, under the names of concept drift, stochastic tracking, and performative prediction. We provide novel non-asymptotic convergence guarantees for stochastic algorithms with iterate averaging, focusing on bounds valid both in expectation and with high probability. The efficiency estimates we obtain clearly decouple the contributions of optimization error, gradient noise, and time drift. Notably, we identify a low drift-to-noise regime in which the tracking efficiency of the proximal stochastic gradient method benefits significantly from a step decay schedule. Numerical experiments illustrate our results.
Open AccessStochastic Optimization under Distributional Drift
We consider the problem of minimizing a convex function that is evolving according to unknown and possibly stochastic dynamics, which may depend jointly on time and on the decision variable itself. Such problems abound in the machine learning and signal processing literature, under the names of concept drift, stochastic tracking, and performative prediction. We provide novel non-asymptotic convergence guarantees for stochastic algorithms with iterate averaging, focusing on bounds valid both in expectation and with high probability. The efficiency estimates we obtain clearly decouple the contributions of optimization error, gradient noise, and time drift. Notably, we identify a low drift-to-noise regime in which the tracking efficiency of the proximal stochastic gradient method benefits significantly from a step decay schedule. Numerical experiments illustrate our results.
- Top Cited Papers
- 1 May 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48 (2) , 954-998
Stochastic Optimization with Decision-Dependent Distributions
Stochastic optimization problems often involve data distributions that change in reaction to the decision variables. This is the case, for example, when members of the population respond to a deployed classifier by manipulating their features so as to improve the likelihood of being positively labeled. Recent works on performative prediction identify an intriguing solution concept for such problems: find the decision that is optimal with respect to the static distribution that the decision induces. Continuing this line of work, we show that, in the strongly convex setting, typical stochastic algorithms—originally designed for static problems—can be applied directly for finding such equilibria with little loss in efficiency. The reason is simple to explain: the main consequence of the distributional shift is that it corrupts algorithms with a bias that decays linearly with the distance to the solution. Using this perspective, we obtain convergence guarantees for popular algorithms, such as stochastic gradient, clipped gradient, prox-point, and dual averaging methods, along with their accelerated and proximal variants. In realistic applications, deployment of a decision rule is often much more expensive than sampling. We show how to modify the aforementioned algorithms so as to maintain their sample efficiency when performing only logarithmically many deployments. Funding: This work was supported by the Division of Computing and Communication Foundations [Grant 1740551] and Division of Mathematical Sciences [Grant 1651851].
- 1 May 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48 (2) , 954-998
Top Cited PapersStochastic Optimization with Decision-Dependent Distributions
Stochastic optimization problems often involve data distributions that change in reaction to the decision variables. This is the case, for example, when members of the population respond to a deployed classifier by manipulating their features so as to improve the likelihood of being positively labeled. Recent works on performative prediction identify an intriguing solution concept for such problems: find the decision that is optimal with respect to the static distribution that the decision induces. Continuing this line of work, we show that, in the strongly convex setting, typical stochastic algorithms—originally designed for static problems—can be applied directly for finding such equilibria with little loss in efficiency. The reason is simple to explain: the main consequence of the distributional shift is that it corrupts algorithms with a bias that decays linearly with the distance to the solution. Using this perspective, we obtain convergence guarantees for popular algorithms, such as stochastic gradient, clipped gradient, prox-point, and dual averaging methods, along with their accelerated and proximal variants. In realistic applications, deployment of a decision rule is often much more expensive than sampling. We show how to modify the aforementioned algorithms so as to maintain their sample efficiency when performing only logarithmically many deployments. Funding: This work was supported by the Division of Computing and Communication Foundations [Grant 1740551] and Division of Mathematical Sciences [Grant 1651851].
- Open Access
The slope robustly determines convex functions
We show that the deviation between the slopes of two convex functions controls the deviation between the functions themselves. This result reveals that the slope -- a one dimensional construct -- robustly determines convex functions, up to a constant of integration.
Open AccessThe slope robustly determines convex functions
We show that the deviation between the slopes of two convex functions controls the deviation between the functions themselves. This result reveals that the slope -- a one dimensional construct -- robustly determines convex functions, up to a constant of integration.
- Open Access
Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization
We show that the subgradient method converges only to local minimizers when applied to generic Lipschitz continuous and subdifferentially regular functions that are definable in an o-minimal structure. At a high level, the argument we present is appealingly transparent: we interpret the nonsmooth dynamics as an approximate Riemannian gradient method on a certain distinguished submanifold that captures the nonsmooth activity of the function. In the process, we develop new regularity conditions in nonsmooth analysis that parallel the stratification conditions of Whitney, Kuo, and Verdier and extend stochastic processes techniques of Pemantle.
Open AccessActive manifolds, stratifications, and convergence to local minima in nonsmooth optimization
We show that the subgradient method converges only to local minimizers when applied to generic Lipschitz continuous and subdifferentially regular functions that are definable in an o-minimal structure. At a high level, the argument we present is appealingly transparent: we interpret the nonsmooth dynamics as an approximate Riemannian gradient method on a certain distinguished submanifold that captures the nonsmooth activity of the function. In the process, we develop new regularity conditions in nonsmooth analysis that parallel the stratification conditions of Whitney, Kuo, and Verdier and extend stochastic processes techniques of Pemantle.