Peter Ochs

Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems

  • Shida Wang
  • Jalal Fadili
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , ,

    \(\) In this paper, we propose two regularized proximal quasi-Newton methods with symmetric rank-1 update of the metric (SR1 quasi-Newton) to solve non-smooth convex additive composite problems. Both algorithms avoid using line search or other trust region strategies. For each of them, we prove a super-linear convergence rate that is independent of the initialization of … Read more

    A Generalization Result for Convergence in Learning-to-Optimize

  • Michael Sucker
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , ,

    Convergence in learning-to-optimize is hardly studied, because conventional convergence guarantees in optimization are based on geometric arguments, which cannot be applied easily to learned algorithms. Thus, we develop a probabilistic framework that resembles deterministic optimization and allows for transferring geometric arguments into learning-to-optimize. Our main theorem is a generalization result for parametric classes of potentially … Read more

    A Markovian Model for Learning-to-Optimize

  • Michael Sucker
  • Peter Ochs
    • Categories Optimization in Data Science, Stochastic Approaches, Stochastic Programming Tags , , , ,

    We present a probabilistic model for stochastic iterative algorithms with the use case of optimization algorithms in mind. Based on this model, we present PAC-Bayesian generalization bounds for functions that are defined on the trajectory of the learned algorithm, for example, the expected (non-asymptotic) convergence rate and the expected time to reach the stopping criterion. … Read more

    Learning-to-Optimize with PAC-Bayesian Guarantees: Theoretical Considerations and Practical Implementation

  • Michael Sucker
  • Jalal Fadili
  • Peter Ochs
    • Categories Optimization in Data Science, Other Topics Tags ,

    We use the PAC-Bayesian theory for the setting of learning-to-optimize. To the best of our knowledge, we present the first framework to learn optimization algorithms with provable generalization guarantees (PAC-Bayesian bounds) and explicit trade-off between convergence guarantees and convergence speed, which contrasts with the typical worst-case analysis. Our learned optimization algorithms provably outperform related ones … Read more

    Accelerated Gradient Dynamics on Riemannian Manifolds: Faster Rate and Trajectory Convergence

  • Tejas Natu
  • Camille Castera
  • Jalal Fadili
  • Peter Ochs
    • Categories Convex Optimization, Optimization in Data Science Tags , , ,

    In order to minimize a differentiable geodesically convex function, we study a second-order dynamical system on Riemannian manifolds with an asymptotically vanishing damping term of the form \(\alpha/t\). For positive values of \(\alpha\), convergence rates for the objective values and convergence of trajectory is derived. We emphasize the crucial role of the curvature of the … Read more

    Near-optimal closed-loop method via Lyapunov damping for convex optimization

  • Camille Castera
  • Peter Ochs
    • Categories Convex Optimization, Systems governed by Differential Equations Optimization, Unconstrained Optimization Tags , , ,

    We introduce an autonomous system with closed-loop damping for first-order convex optimization. While, to this day, optimal rates of convergence are only achieved by non-autonomous methods via open-loop damping (e.g., Nesterov’s algorithm), we show that our system is the first one featuring a closed-loop damping while exhibiting a rate arbitrarily close to the optimal one. … Read more

    Fixed-Point Automatic Differentiation of Forward–Backward Splitting Algorithms for Partly Smooth Functions

  • Sheheryar Mehmood
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

    A large class of non-smooth practical optimization problems can be written as minimization of a sum of smooth and partly smooth functions. We consider such structured problems which also depend on a parameter vector and study the problem of differentiating its solution mapping with respect to the parameter which has far reaching applications in sensitivity … Read more

    An abstract convergence framework with application to inertial inexact forward-backward methods

  • Silvia Bonettini
  • Peter Ochs
  • Marco Prato
  • Simone Rebegoldi
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this paper we introduce a novel abstract descent scheme suited for the minimization of proper and lower semicontinuous functions. The proposed abstract scheme generalizes a set of properties that are crucial for the convergence of several first-order methods designed for nonsmooth nonconvex optimization problems. Such properties guarantee the convergence of the full sequence of … Read more

    Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms

  • Mahesh Chandra Mukkamala
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , ,

    Matrix Factorization is a popular non-convex objective, for which alternating minimization schemes are mostly used. They usually suffer from the major drawback that the solution is biased towards one of the optimization variables. A remedy is non-alternating schemes. However, due to a lack of Lipschitz continuity of the gradient in matrix factorization problems, convergence cannot … Read more

    Convex-Concave Backtracking for Inertial Bregman Proximal Gradient Algorithms in Non-Convex Optimization

  • Mahesh Chandra Mukkamala
  • Peter Ochs
  • Thomas Pock
  • Shoham Sabach
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , ,

    Backtracking line-search is an old yet powerful strategy for finding better step size to be used in proximal gradient algorithms. The main principle is to locally find a simple convex upper bound of the objective function, which in turn controls the step size that is used. In case of inertial proximal gradient algorithms, the situation … Read more