Damek Davis
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Damek Davis has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Dmitriy Drusvyatskiy
Department of Mathematics, U. Washington, Seattle, USA
3 shared publications Dmitriy Drusvyatskiy
Department of Mathematics, University of Washington, Seattle, Washington 98195
2 shared publications- Vasileios Charisopoulos
Department of Operations Research & Information Engineering Cornell University 14853 Ithaca NY
2 shared publications Aleksandr Aravkin
Department of Applied Mathematics, University of Washington, Seattle, Washington 98195
1 shared publication- Aleksandr Aravkin
Department of Applied Mathematics University of Washington Seattle WA USA
1 shared publication - Benjamin Grimmer
Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, USA
1 shared publication
Latest Publications
- 1 August 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (3) , 1678-1709
A Superlinearly Convergent Subgradient Method for Sharp Semismooth Problems
Subgradient methods comprise a fundamental class of nonsmooth optimization algorithms. Classical results show that certain subgradient methods converge sublinearly for general Lipschitz convex functions and converge linearly for convex functions that grow sharply away from solutions. Recent work has moreover extended these results to certain nonconvex problems. In this work, we seek to improve the complexity of these algorithms by asking the following question. Is it possible to design a superlinearly convergent subgradient method? We provide a positive answer to this question for a broad class of sharp semismooth functions. Funding: The research of D. Davis was supported by the Division of Mathematical Sciences [Grant 2047637] and the Alfred P. Sloan Foundation.
- 1 August 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (3) , 1678-1709
A Superlinearly Convergent Subgradient Method for Sharp Semismooth Problems
Subgradient methods comprise a fundamental class of nonsmooth optimization algorithms. Classical results show that certain subgradient methods converge sublinearly for general Lipschitz convex functions and converge linearly for convex functions that grow sharply away from solutions. Recent work has moreover extended these results to certain nonconvex problems. In this work, we seek to improve the complexity of these algorithms by asking the following question. Is it possible to design a superlinearly convergent subgradient method? We provide a positive answer to this question for a broad class of sharp semismooth functions. Funding: The research of D. Davis was supported by the Division of Mathematical Sciences [Grant 2047637] and the Alfred P. Sloan Foundation.
- 14 June 2024
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 25 (3) , 943-1024
A Local Nearly Linearly Convergent First-Order Method for Nonsmooth Functions with Quadratic Growth
- 14 June 2024
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 25 (3) , 943-1024
A Local Nearly Linearly Convergent First-Order Method for Nonsmooth Functions with Quadratic Growth
- Open Access
- 7 June 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 200 (2) , 629-631
Special Issue: International Symposium on Mathematical Programming 2022
- 7 June 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 200 (2) , 629-631
Open AccessSpecial Issue: International Symposium on Mathematical Programming 2022
- 1 February 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 209-231
Graphical Convergence of Subgradients in Nonconvex Optimization and Learning
We investigate the stochastic optimization problem of minimizing population risk, where the loss defining the risk is assumed to be weakly convex. Compositions of Lipschitz convex functions with smooth maps are the primary examples of such losses. We analyze the estimation quality of such nonsmooth and nonconvex problems by their sample average approximations. Our main results establish dimension-dependent rates on subgradient estimation in full generality and dimension-independent rates when the loss is a generalized linear model. As an application of the developed techniques, we analyze the nonsmooth landscape of a robust nonlinear regression problem.
- 1 February 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 209-231
Graphical Convergence of Subgradients in Nonconvex Optimization and Learning
We investigate the stochastic optimization problem of minimizing population risk, where the loss defining the risk is assumed to be weakly convex. Compositions of Lipschitz convex functions with smooth maps are the primary examples of such losses. We analyze the estimation quality of such nonsmooth and nonconvex problems by their sample average approximations. Our main results establish dimension-dependent rates on subgradient estimation in full generality and dimension-independent rates when the loss is a generalized linear model. As an application of the developed techniques, we analyze the nonsmooth landscape of a robust nonlinear regression problem.
- 30 January 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (1) , 375-410
Variance reduction for root-finding problems
- 30 January 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (1) , 375-410
Variance reduction for root-finding problems
- 21 June 2021
- Published by Springer Nature in Set-Valued and Variational Analysis
- Vol. 30 (2) , 453-463
Conservative and Semismooth Derivatives are Equivalent for Semialgebraic Maps
- 21 June 2021
- Published by Springer Nature in Set-Valued and Variational Analysis
- Vol. 30 (2) , 453-463
Conservative and Semismooth Derivatives are Equivalent for Semialgebraic Maps
- Top Cited Papers
- 28 January 2021
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 21 (6) , 1505-1593
Low-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence
- 28 January 2021
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 21 (6) , 1505-1593
Top Cited PapersLow-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence
- Open Access
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.
Open AccessStochastic 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 February 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 45 (1) , 292-322
Trimmed Statistical Estimation via Variance Reduction
In this paper, we show how to transform any optimization problem that arises from fitting a machine learning model into one that (1) detects and removes contaminated data from the training set while (2) simultaneously fitting the trimmed model on the uncontaminated data that remains. To solve the resulting nonconvex optimization problem, we introduce a fast stochastic proximal-gradient algorithm that incorporates prior knowledge through nonsmooth regularization. For data sets of size n, our approach requires O(n2/3/ℇ) gradient evaluations to reach ℇ-accuracy, and when a certain error bound holds, the complexity improves to O(κn2/3 log(1/ℇ)), where κ is a “condition number.” These rates are n1/3 times better than those achieved by typical, nonstochastic methods.
- 1 February 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 45 (1) , 292-322
Trimmed Statistical Estimation via Variance Reduction
In this paper, we show how to transform any optimization problem that arises from fitting a machine learning model into one that (1) detects and removes contaminated data from the training set while (2) simultaneously fitting the trimmed model on the uncontaminated data that remains. To solve the resulting nonconvex optimization problem, we introduce a fast stochastic proximal-gradient algorithm that incorporates prior knowledge through nonsmooth regularization. For data sets of size n, our approach requires O(n2/3/ℇ) gradient evaluations to reach ℇ-accuracy, and when a certain error bound holds, the complexity improves to O(κn2/3 log(1/ℇ)), where κ is a “condition number.” These rates are n1/3 times better than those achieved by typical, nonstochastic methods.
- Open Access
Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems
In this paper, we introduce a stochastic projected subgradient method for weakly convex (i.e., uniformly prox-regular) nonsmooth, nonconvex functions---a wide class of functions which includes the additive and convex composite classes. At a high-level, the method is an inexact proximal point iteration in which the strongly convex proximal subproblems are quickly solved with a specialized stochastic projected subgradient method. The primary contribution of this paper is a simple proof that the proposed algorithm converges at the same rate as the stochastic gradient method for smooth nonconvex problems. This result appears to be the first convergence rate analysis of a stochastic (or even deterministic) subgradient method for the class of weakly convex functions.
Open AccessProximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems
In this paper, we introduce a stochastic projected subgradient method for weakly convex (i.e., uniformly prox-regular) nonsmooth, nonconvex functions---a wide class of functions which includes the additive and convex composite classes. At a high-level, the method is an inexact proximal point iteration in which the strongly convex proximal subproblems are quickly solved with a specialized stochastic projected subgradient method. The primary contribution of this paper is a simple proof that the proposed algorithm converges at the same rate as the stochastic gradient method for smooth nonconvex problems. This result appears to be the first convergence rate analysis of a stochastic (or even deterministic) subgradient method for the class of weakly convex functions.