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.
Introduction
Modern optimization problems often exhibit a dual nature. On one hand, we have "oracle" functions—typically data-driven components like loss functions in machine learning—where we can efficiently compute values and gradients using automatic differentiation frameworks like PyTorch or TensorFlow. On the other hand, we have "structured" functions—constraints or penalties that encode domain knowledge, such as risk measures or physical constraints—which are best handled by domain-specific languages (DSLs) like CVXPY.
The challenge lies in the fact that these two components are often treated separately. Standard second-order solvers like MOSEK or ECOS struggle when the oracle function involves millions of data points, as the cost of computing and factorizing a full Hessian becomes prohibitive. Conversely, first-order methods, while scalable, often fail to exploit the rich structure of the non-smooth or constrained parts of the objective, leading to slow convergence or requiring extensive hyperparameter tuning.
The Oracle-Structured Minimization Method (OSMM)
To bridge this gap, we introduce the Oracle-Structured Minimization Method (OSMM). OSMM is designed to minimize a composite convex function $h(x) = f(x) + g(x)$, where $f$ is an oracle function and $g$ is a structured function. The core idea is to construct a sophisticated surrogate of $f$ at each iteration that captures both its local curvature and its global non-smooth behavior.
The Surrogate Model
At each iteration $k$, OSMM approximates $f(x)$ with a surrogate $\hat{f}_k(x)$: $$\hat{f}_k(x) = l_k(x) + \frac{1}{2}(x-x^k)^T H_k (x-x^k)$$ This surrogate consists of two main components:
- The Bundle ($l_k(x)$): A piecewise affine lower bound constructed from the gradients of the $M$ most recent iterations. This "bundle" captures the non-smooth shape of the function more effectively than a simple linear approximation.
- The Curvature ($H_k$): A low-rank quasi-Newton approximation of the Hessian. This provides second-order acceleration without the memory overhead of a full Hessian matrix.
Algorithmic Update and Stability
The next iterate $x^{k+1}$ is found by solving the subproblem: $$\min_x \hat{f}_k(x) + g(x) + \frac{\lambda_k}{2} \|x - x^k\|_2^2$$ where $\lambda_k$ is an adaptive trust-region parameter. Because $\hat{f}_k$ is structured and $g$ is provided via a DSL, this subproblem can be efficiently solved by standard interior-point solvers like ECOS. To ensure stability and convergence, OSMM employs an Armijo-type line search.
One of the most significant advantages of OSMM is that it is "tuning-free." Empirical results show that a fixed memory size ($M=20$) and rank ($r=20$) for the curvature approximation work consistently well across a wide range of problem types.
Applications and Performance
We evaluated OSMM on several large-scale stochastic optimization problems, each involving $10^6$ data samples. These problems represent typical use cases in finance, supply chain, and statistics:
- Kelly Gambling: A resource allocation problem where the goal is to maximize the expected growth rate of wealth.
- CVaR Portfolio Optimization: Minimizing the Conditional Value-at-Risk for a large portfolio of assets.
- Exponential Family Density Fitting: A statistical task of fitting a probability density using Legendre polynomials.
- Vector News Vendor: A supply chain management problem involving Entropic Value-at-Risk (EVaR).
Key Results
The performance gains of OSMM over traditional solvers are substantial. For the Kelly Gambling problem with $10^6$ samples, OSMM reaches high accuracy in just 0.64 seconds. In contrast, MOSEK requires 890 seconds, and ECOS takes over 20,000 seconds. Similarly, for CVaR optimization, OSMM completes the task in 6.3 seconds, while MOSEK takes 1,900 seconds.
Crucially, OSMM demonstrates excellent scaling. While the solve time for standard solvers grows linearly or worse with the number of samples $N$, OSMM's solve time remains nearly constant. This is because the "heavy lifting" associated with the data is offloaded to fast gradient evaluations in the oracle framework, while the size of the structured subproblem remains independent of $N$.
Conclusion
OSMM offers a powerful framework for solving composite optimization problems by leveraging the strengths of both oracle-based automatic differentiation and structured DSL solvers. By combining bundle methods with quasi-Newton curvature estimates, it provides a robust, tuning-free algorithm that outperforms state-of-the-art solvers on large-scale data-heavy problems. Future work includes extending OSMM to non-convex objectives and developing a stochastic version that utilizes mini-batches for even greater scalability in deep learning contexts.
Summary updated