Minimizing oracle-structured composite functions

Xinyue Shen, Alnur Ali, Stephen Boyd

TL;DR

The authors introduce OSMM (Oracle-Structured Minimization Method), a "tuning-free" algorithm designed to solve convex optimization problems that combine data-heavy functions (like those in PyTorch) with complex, structured constraints or penalties (like those in CVXPY). By merging quasi-Newton curvature estimates with bundle methods, OSMM outperforms standard commercial solvers by orders of magnitude on large-scale stochastic problems.

What Problem Does This Paper Address?

In modern optimization, we often face a "split personality" problem. We want to minimize a function $h(x) = f(x) + g(x)$, where:

  1. $f(x)$ is an "Oracle" function: It involves massive amounts of data (e.g., a sample average over $10^6$ points). We can easily get its value and gradient using automatic differentiation (like PyTorch or TensorFlow), but it’s too data-heavy for traditional second-order solvers.
  2. $g(x)$ is a "Structured" function: It might be non-smooth or involve complex constraints (e.g., a probability simplex or a risk measure). We can describe it easily in domain-specific languages like CVXPY, but it doesn't have a simple "proximal operator" that first-order methods usually require.

Standard solvers (like MOSEK or ECOS) try to handle the whole problem at once, but they choke when $f(x)$ contains too much data. Conversely, standard first-order methods struggle with the complexity of $g(x)$. The authors aim to bridge this gap with a method that leverages the strengths of both software ecosystems.

Methods

The authors propose the Oracle-Structured Minimization Method (OSMM). It is a descent method that forms a sophisticated surrogate of the oracle function $f$ at each step.

  • The Surrogate: Instead of a simple linear approximation, OSMM uses a quadratic model: $\hat{f}_k(x) = l_k(x) + \frac{1}{2}(x-x^k)^T H_k (x-x^k)$.
  • $l_k(x)$ (The Bundle): A piecewise affine lower bound (minorant) built from the gradients of the last $M$ iterations. This captures the non-smooth "shape" of the function better than a single gradient.
  • $H_k$ (The Curvature): A low-rank quasi-Newton approximation of the Hessian. This provides "second-order" acceleration without the massive memory cost of a full Hessian matrix.
  • The Update: In each iteration, OSMM solves a subproblem: $\min \hat{f}_k(x) + g(x) + \text{trust penalty}$. Because $\hat{f}_k$ is structured and $g$ is provided via a DSL, this subproblem is handed off to an efficient structured solver (like ECOS).
  • Stability: The algorithm uses an Armijo-type line search and an adaptive trust-region parameter ($\lambda_k$) to ensure convergence without requiring the user to manually tune hyperparameters.

Datasets and Applications

The paper evaluates OSMM on several classic and modern stochastic optimization problems. While they don't use "datasets" in the sense of ImageNet, they use large-scale synthetic problem instances that mimic real-world data scenarios:

  • Kelly Gambling: A resource allocation problem with up to $1,000,000$ possible outcomes.
  • CVaR Portfolio Optimization: Minimizing "Conditional Value-at-Risk" for a portfolio of 300 assets (stocks and derivatives) over $1,000,000$ price change samples.
  • Exponential Family Density Fitting: Fitting a probability density to $1,000,000$ samples using Legendre polynomials.
  • Vector News Vendor: A supply chain problem involving Entropic Value-at-Risk (EVaR) with $1,000,000$ demand/price simulations.

Key Insights and Ideas

  • Hybrid Access is the Future: The "Aha!" moment is realizing that we don't need to treat the whole objective as a black box. By separating the "data-heavy" part from the "structure-heavy" part, we can use the best tool for each.
  • Bundle + Quasi-Newton: Combining these two ideas is powerful. The bundle method handles the "flat" parts of the function, while the quasi-Newton term handles the "curved" parts.
  • Tuning-Free Performance: The authors found that a fixed memory ($M=20$) and rank ($r=20$) work remarkably well across totally different problem types. This makes the algorithm practical for non-experts.
  • Exploiting DSLs: By using CVXPY to solve the subproblem, the algorithm automatically benefits from any structural optimizations (like cone programming) built into those systems.

Key Results

The quantitative speedups are dramatic, especially as the number of data samples ($N$) increases:

  • Kelly Gambling ($N=10^6$): OSMM reaches high accuracy in 0.64 seconds. MOSEK takes 890 seconds, and ECOS takes 20,000 seconds.
  • CVaR Optimization ($N=10^6$): OSMM takes 6.3 seconds, while MOSEK takes 1,900 seconds.
  • Scaling: For standard solvers, the time to solve grows linearly (or worse) with the number of samples $N$. For OSMM, the solve time is nearly constant because the "heavy lifting" of the data is handled by a fast gradient evaluation in PyTorch, while the subproblem size remains small.

Limitations and Future Work

  • Convexity Requirement: The method strictly requires $f$ and $g$ to be convex. While many machine learning problems are non-convex, this method is targeted at the high-reliability world of operations research and finance.
  • Subproblem Overhead: If the "structured" part $g(x)$ is itself extremely large or complex, the time spent in the CVXPY subsolver could become a bottleneck.
  • Exact Gradients: The current version of OSMM assumes we can compute the full gradient of $f$. A promising future direction would be a stochastic version of OSMM that works with mini-batches, further increasing its applicability to massive-scale deep learning.

Summary updated

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.
BibTeX
@inproceedings{shen2022minimizing,
  author = {Xinyue Shen and Alnur Ali and Stephen Boyd},
  title = {{Minimizing oracle-structured composite functions}},
  booktitle = {Optimization},
  year = {2022},
  doi = {10.1007/s11081-021-09705-0},
}
Figure