TL;DR
The paper introduces OSBDO, a robust and nearly parameter-free bundle method for solving distributed optimization problems where local "agent" functions are expensive to evaluate. By combining disaggregate minorants, diagonal preconditioning, and an automated parameter discovery phase, the authors provide a solver that achieves modest accuracy in just a few dozen iterations, significantly outperforming standard subgradient methods.
What Problem Does This Paper Address?
In distributed optimization, we often want to minimize a global objective function that is the sum of several local functions (belonging to "agents") plus a shared "public" function that couples them together (like a budget constraint or a consensus requirement).
The challenge arises when:
- Agent functions are "black boxes": We only have access to them via a subgradient oracle (we give it a point, it returns the function value and a gradient).
- Evaluation is expensive: Calculating that gradient might involve solving a complex internal simulation or a large-scale sub-optimization problem.
- Standard methods fail: Simple methods like proximal subgradient descent often require hundreds or thousands of iterations and painful manual tuning of step sizes to converge.
The authors address the need for a "high-efficiency" solver—one that does more heavy lifting in each iteration to ensure the total number of expensive oracle calls remains as low as possible.
Methods
The authors assemble several sophisticated techniques into a single, cohesive algorithm:
- Disaggregate Partially Exact Bundle Method: Instead of building one global approximation of the objective, the solver maintains separate piecewise-linear lower bounds (minorants) for every single agent. Meanwhile, the "public" function is handled exactly because its structure is known (e.g., via a language like CVXPY).
- Diagonal Preconditioning: This is a "thin layer" that scales all variables to a similar range (typically 0 to 1). This simple step is often the difference between an algorithm that converges in 50 iterations and one that takes 5,000.
- Proximal Parameter Discovery: One of the biggest headaches in bundle methods is choosing the proximal parameter ($\rho$). OSBDO solves this by running a "level bundle" method for the first 20 iterations to "discover" a good value for $\rho$, then switching to a standard proximal bundle method for the remainder of the run.
- Finite Memory (Bundle Compression): To prevent the internal subproblems from becoming too large and slow as iterations increase, the method can "compress" the bundle, keeping only the most relevant historical gradients.
Datasets
The paper evaluates the algorithm using four complex, simulated problem instances designed to mimic real-world engineering and ML challenges:
- Supply Chain: A multi-stage trans-shipment network with 5,275 variables.
- Resource Allocation: Distributing 50 resources among 500 participants across 50 groups.
- Multi-commodity Flow: Shipping 10 different goods over a network with 1,000 edges (10,000 public variables).
- Federated Learning: A distributed logistic regression problem with $\ell_1$ regularization across 10 locations.
The code and data to reproduce these experiments are available in their open-source Julia package: https://github.com/cvxgrp/OSBDO.
Key Insights and Ideas
- Spend Computation to Save Communication: The core philosophy is that if an oracle call is expensive, you should be willing to solve a relatively complex Quadratic Program (QP) in every iteration if it helps you take a better step.
- Structure is a Superpower: By assuming the "public" part of the problem is written in a Domain Specific Language (DSL) like CVXPY, the algorithm can exploit the exact curvature of the constraints rather than guessing them via gradients.
- The "Aha" of Parameter Discovery: Most researchers spend days tuning hyperparameters. By using the first few iterations to automatically estimate the optimal proximal weight, the authors make the tool much more accessible to non-experts.
Key Results
- Speed to Accuracy: Across all examples, OSBDO reached a 1% optimality guarantee in very few iterations:
- Supply Chain: 80 iterations.
- Resource Allocation: 47 iterations.
- Multi-commodity Flow: 14 iterations.
- Federated Learning: 53 iterations.
- Reliability: The "default" parameters worked across vastly different problem types (from network flows to machine learning) without manual intervention.
- Preconditioning Impact: The authors note that without diagonal scaling, convergence is significantly slower, proving that "boring" implementation details are often as important as the core theory.
Limitations and Future Work
- Convexity Required: The method relies heavily on the theory of convex minorants; it is not designed for non-convex problems (like deep neural networks).
- Subproblem Scaling: While finite memory helps, the internal subproblem is still a QP that grows with the number of agents and variables. For extremely high-dimensional public variables, the per-iteration cost might eventually become a bottleneck.
- Synchronous Updates: The current implementation assumes all agents report back before the next step is taken. Future work could explore asynchronous versions where the solver doesn't have to wait for the "slowest" agent.
Summary updated