Dmitriy Drusvyatskiy

Subgradient methods near active manifolds: saddle point avoidance, local convergence, and asymptotic normality

  • Damek Davis
  • Dmitriy Drusvyatskiy
  • Liwei Jiang
    • Categories Nonsmooth Optimization

    Nonsmooth optimization problems arising in practice, whether in signal processing, statistical estimation, or modern machine learning, tend to exhibit beneficial smooth substructure: their domains stratify into “active manifolds” of smooth variation, which common proximal algorithms “identify” in finite time. Identification then entails a transition to smooth dynamics, and permits the use of second-order information for … Read more

    Escaping strict saddle points of the Moreau envelope in nonsmooth optimization

  • Damek Davis
  • Mateo Díaz
  • Dmitriy Drusvyatskiy
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    Recent work has shown that stochastically perturbed gradient methods can efficiently escape strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms for nonsmooth optimization … Read more

    Active strict saddles in nonsmooth optimization

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Nonsmooth Optimization Tags , , ,

    We introduce a geometrically transparent strict saddle property for nonsmooth functions. This property guarantees that simple proximal algorithms on weakly convex problems converge only to local minimizers, when randomly initialized. We argue that the strict saddle property may be a realistic assumption in applications, since it provably holds for generic semi-algebraic optimization problems. ArticleDownload View … Read more

    Robust stochastic optimization with the proximal point method

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Convex Optimization, Stochastic Programming Tags , , , ,

    Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. In this work, we show that a wide class of such algorithms on strongly convex problems can be augmented with sub-exponential confidence bounds at an overhead cost that is only … Read more

    Stochastic algorithms with geometric step decay converge linearly on sharp functions

  • Vasileios Charisopoulos
  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Nonsmooth Optimization Tags , , , ,

    Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is called geometric step decay and proceeds by halving the step size after every few epochs. In … Read more

    Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence

  • Vasileios Charisopoulos
  • Damek Davis
  • Mateo Díaz
  • Dmitriy Drusvyatskiy
  • Yudong Chen
  • Lijun Ding
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    The task of recovering a low-rank matrix from its noisy linear measurements plays a central role in computational science. Smooth formulations of the problem often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension of the ambient space. In contrast, we here show that in a variety of concrete circumstances, … Read more

    Composite optimization for robust blind deconvolution

  • Vasileios Charisopoulos
  • Damek Davis
  • Mateo Díaz
  • Dmitriy Drusvyatskiy
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    The blind deconvolution problem seeks to recover a pair of vectors from a set of rank one bilinear measurements. We consider a natural nonsmooth formulation of the problem and show that under standard statistical assumptions, its moduli of weak convexity, sharpness, and Lipschitz continuity are all dimension independent. This phenomenon persists even when up to … Read more

    Inexact alternating projections on nonconvex sets

  • Dmitriy Drusvyatskiy
  • Adrian Lewis
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    Given two arbitrary closed sets in Euclidean space, a simple transversality condition guarantees that the method of alternating projections converges locally, at linear rate, to a point in the intersection. Exact projection onto nonconvex sets is typically intractable, but we show that computationally-cheap inexact projections may suffice instead. In particular, if one set is defined … Read more

    Stochastic model-based minimization under high-order growth

  • Damek Davis
  • Dmitriy Drusvyatskiy
  • Kellie J. MacPhee
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    Given a nonsmooth, nonconvex minimization problem, we consider algorithms that iteratively sample and minimize stochastic convex models of the objective function. Assuming that the one-sided approximation quality and the variation of the models is controlled by a Bregman divergence, we show that the scheme drives a natural stationarity measure to zero at the rate $O(k^{-1/4})$. … Read more

    Stochastic subgradient method converges on tame functions

  • Damek Davis
  • Dmitriy Drusvyatskiy
  • Jason D. Lee
  • Sham Kakade
    • Categories Nonsmooth Optimization Tags , , , ,

    This work considers the question: what convergence guarantees does the stochastic subgradient method have in the absence of smoothness and convexity? We prove that the stochastic subgradient method, on any semialgebraic locally Lipschitz function, produces limit points that are all first-order stationary. More generally, our result applies to any function with a Whitney stratifiable graph. … Read more