Minimizing oracle-structured composite functions
From MaRDI portal
Abstract: We consider the problem of minimizing a composite convex function with two different access methods: an oracle, for which we can evaluate the value and gradient, and a structured function, which we access only by solving a convex optimization problem. We are motivated by two associated technological developments. For the oracle, systems like PyTorch or TensorFlow can automatically and efficiently compute gradients, given a computation graph description. For the structured function, systems like CVXPY accept a high level domain specific language description of the problem, and automatically translate it to a standard form for efficient solution. We develop a method that makes minimal assumptions about the two functions, does not require the tuning of algorithm parameters, and works well in practice across a variety of problems. Our algorithm combines a number of well-known ideas, including a low-rank quasi-Newton approximation of curvature, piecewise affine lower bounds from bundle-type methods, and two types of damping to ensure stability. We illustrate the method on stochastic optimization, utility maximization, and risk-averse programming problems, showing that our method is more efficient than standard solvers when the oracle function contains much data.
Recommendations
- Gradient methods for minimizing composite functions
- Implementation of an oracle-structured bundle method for distributed optimization
- Oracle complexity separation in convex optimization
- Composite convex optimization with global and local inexact oracles
- Fast gradient descent for convex minimization problems with an oracle producing a ( , L)-model of function at the requested point
Cites work
- A bundle-Newton method for nonsmooth unconstrained minimization
- A Class of Methods for Solving Nonlinear Simultaneous Equations
- A descent algorithm for nonsmooth convex optimization
- A doubly stabilized bundle method for nonsmooth convex optimization
- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
- A globally convergent proximal Newton-type method in nonsmooth convex optimization
- A new low rank quasi-Newton update scheme for nonlinear programming
- A quasi-Newton approach to nonsmooth convex optimization problems in machine learning
- A quasi-second-order proximal bundle algorithm
- A Rapidly Convergent Descent Method for Minimization
- A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines
- A strongly convergent proximal bundle method for convex minimization in Hilbert spaces
- A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
- Bundle method for non-convex minimization with inexact subgradients and function values
- Bundle methods for regularized risk minimization
- Coherent risk measures in inventory problems
- Conditional value-at-risk: optimization approach
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Convex proximal bundle methods in depth: a unified analysis for inexact oracles
- CVXPY: a Python-embedded modeling language for convex optimization
- Disciplined convex programming
- Efficiency of proximal bundle methods
- Exponential series estimator of multivariate densities
- Fat tails, VaR and subadditivity
- Generalized Bundle Methods
- Goodness of fit tests via exponential series density estimation
- Gradient methods for minimizing composite functions
- Graphical models, exponential families, and variational inference
- scientific article; zbMATH DE number 3619637 (Why is no real title available?)
- scientific article; zbMATH DE number 6982909 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Incremental bundle methods using upper models
- Inexact proximal Newton methods for self-concordant functions
- Inexact successive quadratic approximation for regularized optimization
- Introduction to nonsmooth optimization. Theory, practice and software
- Minimization of functions having Lipschitz continuous first partial derivatives
- New variants of bundle methods
- On quasi-Newton forward-backward splitting: proximal calculus and convergence
- Optimal portfolio allocation under the probabilistic VaR constraint and incentives for financial innovation
- Practical inexact proximal quasi-Newton method with global complexity analysis
- Proximal Newton-type methods for minimizing composite functions
- Proximal quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates
- Proximity control in bundle methods for convex nondifferentiable minimization
- Quasi-Newton Bundle-Type Methods for Nondifferentiable Convex Optimization
- Quasi-Newton Methods, Motivation and Theory
- Representations of quasi-Newton matrices and their use in limited memory methods
- Variable metric bundle methods: From conceptual to implementable forms
- Variable Metric Method for Minimization
This page was built for publication: Minimizing oracle-structured composite functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6173766)
