Implementation of an Oracle-Structured Bundle Method for Distributed Optimization

Tetiana Parshakova, Fangzhao Zhang, Stephen Boyd

Abstract

We consider the problem of minimizing a function that is a sum of convex agent functions plus a convex common public function that couples them. The agent functions can only be accessed via a subgradient oracle; the public function is assumed to be structured and expressible in a domain-specific language (DSL) for convex optimization. We focus on the case when the evaluation of the agent oracles can require significant effort, which justifies the use of solution methods that carry out significant computation in each iteration. To solve this problem, we integrate multiple known techniques for bundle-type algorithms, obtaining a method which has a number of practical advantages over other methods compatible with our access methods, such as proximal subgradient methods. First, it is reliable and works well across a number of applications. Second, it has very few parameters that need to be tuned and works well with sensible default values. Third, it typically produces a reasonable approximate solution in just a few tens of iterations. This paper is accompanied by an open-source implementation of the proposed solver, OSBDO.

Introduction

In distributed optimization, the goal is often to minimize a global objective function composed of several local "agent" functions and a shared "public" function that enforces coupling constraints, such as budget limits or consensus requirements. A significant challenge arises when these agent functions are treated as "black boxes," accessible only through a subgradient oracle that returns a function value and a gradient for a given input.

In many real-world engineering and machine learning applications, evaluating these oracles is computationally expensive, involving complex simulations or large-scale internal optimizations. Standard first-order methods, such as proximal subgradient descent, often struggle in these settings because they require hundreds or thousands of iterations and sensitive hyperparameter tuning. This paper introduces OSBDO (Oracle-Structured Bundle Method for Distributed Optimization), a solver designed to minimize the number of expensive oracle calls by performing more sophisticated computation within each iteration.

The OSBDO Method

OSBDO assembles several advanced optimization techniques into a cohesive, robust algorithm designed for efficiency and ease of use.

Disaggregate Partially Exact Bundle Method

Unlike standard bundle methods that maintain a single global approximation of the objective, OSBDO utilizes a disaggregate approach. It maintains separate piecewise-linear lower bounds (minorants) for every individual agent function. Simultaneously, the "public" function is handled exactly. By assuming the public part of the problem is defined in a DSL like CVXPY or Convex.jl, the algorithm can exploit its known curvature and constraints rather than approximating them via gradients.

Diagonal Preconditioning

To handle variables that may exist on vastly different scales, OSBDO employs a diagonal preconditioning layer. This scales all variables to a similar range (typically 0 to 1). While conceptually simple, this implementation detail is often the difference between rapid convergence and failure to converge in a reasonable timeframe.

Proximal Parameter Discovery

A perennial challenge in bundle methods is the selection of the proximal parameter ($\rho$). OSBDO addresses this through an automated "discovery" phase. For the first 20 iterations, the solver runs a level bundle method to estimate a high-quality value for $ ho$. Once discovered, the algorithm switches to a standard proximal bundle method for the remainder of the execution. This makes the solver nearly parameter-free for the end user.

Bundle Compression

To ensure the internal subproblems—which are Quadratic Programs (QPs)—remain computationally tractable as iterations progress, OSBDO implements finite memory or bundle compression. This process prunes the bundle to keep only the most relevant historical gradients, preventing the per-iteration cost from growing indefinitely.

Numerical Experiments

The algorithm was evaluated using four complex problem instances designed to simulate diverse engineering and machine learning challenges:

  1. Supply Chain: A multi-stage trans-shipment network involving 5,275 variables.
  2. Resource Allocation: A problem distributing 50 resources among 500 participants across 50 groups.
  3. Multi-commodity Flow: Shipping 10 different goods over a network with 1,000 edges (10,000 public variables).
  4. Federated Learning: A distributed logistic regression problem with $\ell_1$ regularization across 10 locations.

Results

Across all test cases, OSBDO demonstrated remarkable speed to accuracy, reaching a 1% optimality guarantee in a very small number of iterations:

  • Multi-commodity Flow: 14 iterations
  • Resource Allocation: 47 iterations
  • Federated Learning: 53 iterations
  • Supply Chain: 80 iterations

Crucially, the solver achieved these results using default parameters, proving its reliability across disparate domains without the need for manual intervention.

Key Insights

  • Computation vs. Communication: OSBDO operates on the philosophy that if an oracle call is expensive, it is worth solving a relatively complex QP in every iteration to ensure each step is as productive as possible.
  • Exploiting Structure: By treating the public function as a structured object rather than a black box, the algorithm gains a significant advantage in handling constraints and curvature.
  • Automation: The automated parameter discovery phase removes the burden of hyperparameter tuning, making high-performance distributed optimization accessible to non-experts.

Limitations and Future Work

While OSBDO is highly effective for convex problems, it is not designed for non-convex objectives, such as those found in deep neural networks. Additionally, while bundle compression helps, the internal subproblem remains a QP that scales with the number of agents and variables; for extremely high-dimensional public variables, this could eventually become a bottleneck. Finally, the current implementation is synchronous, requiring all agents to report back before the next iteration. Future iterations of the solver may explore asynchronous updates to better handle "straggler" agents in distributed environments.

Conclusion

OSBDO provides a robust, efficient, and nearly parameter-free solution for distributed convex optimization. By combining disaggregate minorants with automated parameter discovery and structural exploitation, it offers a significant performance boost over standard subgradient methods. The implementation is open-source and available at https://github.com/cvxgrp/OSBDO.

Summary updated

Abstract

We consider the problem of minimizing a function that is a sum of convex agent functions plus a convex common public function that couples them. The agent functions can only be accessed via a subgradient oracle; the public function is assumed to be structured and expressible in a domain specific language (DSL) for convex optimization. We focus on the case when the evaluation of the agent oracles can require significant effort, which justifies the use of solution methods that carry out significant computation in each iteration. To solve this problem we integrate multiple known techniques (or adaptations of known techniques) for bundle-type algorithms, obtaining a method which has a number of practical advantages over other methods that are compatible with our access methods, such as proximal subgradient methods. First, it is reliable, and works well across a number of applications. Second, it has very few parameters that need to be tuned, and works well with sensible default values. Third, it typically produces a reasonable approximate solution in just a few tens of iterations. This paper is accompanied by an open-source implementation of the proposed solver, available at \url{https://github.com/cvxgrp/OSBDO}.
BibTeX
@inproceedings{parshakova2023implementation,
  author = {Tetiana Parshakova and Fangzhao Zhang and Stephen Boyd},
  title = {{Implementation of an Oracle-Structured Bundle Method for Distributed Optimization}},
  booktitle = {Optimization},
  year = {2023},
  doi = {10.1007/s11081-023-09859-z},
}
Figure