💻 computer science

Multiple approximate-response agents (MARA): Fast near-optimal primal recovery for distributed optimization

The paper proposes Multiple Approximate-Response Agents (MARA), a parallelizable primal recovery method that generates multiple bounded-suboptimal responses to dual price queries and combines them to rapidly achieve feasible, near-optimal solutions in distributed optimization without increasing wall-clock time.

Original authors: Tetiana Parshakova, Yicheng Bai, Garrett van Ryzin, Stephen Boyd

Published 2026-08-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tetiana Parshakova, Yicheng Bai, Garrett van Ryzin, Stephen Boyd

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern computing, some problems are simply too large to solve on a single machine. Imagine trying to coordinate the energy output of thousands of power plants, the flow of goods across a global supply chain, or the routing of data through a massive network. These are not just big puzzles; they are collections of smaller, independent decisions that must align perfectly to satisfy a shared set of rules. To tackle this, scientists use a strategy called distributed optimization. Instead of one supercomputer trying to hold the entire picture, the work is split among many smaller agents, each solving its own piece of the puzzle. They communicate by exchanging prices, which act as signals telling each agent how much to produce or consume to keep the whole system balanced. This approach is powerful because it allows these tasks to happen simultaneously, speeding up the process dramatically. However, there is a persistent snag: while the agents can easily agree on the prices, turning those prices back into a valid, working solution for the real world is notoriously difficult. Often, the agents' individual answers, when combined, violate the very rules they are supposed to follow, leaving the system in a state of imbalance that takes an impractical amount of time to fix.

A team of researchers has developed a new method to overcome this specific hurdle, a technique they call Multiple Approximate-Response Agents, or MARA. The core idea is a shift in how the agents respond to the price signals they receive. In traditional methods, when an agent is asked for a solution based on a specific price, it returns a single, best-effort answer. If that answer is slightly off, the whole system stumbles. MARA changes the game by asking every agent to provide not just one, but ten or more slightly different answers for the same price. These answers are not required to be perfect; they are allowed to be slightly imperfect, or "suboptimal," as long as they are close to the best possible choice. Because these multiple responses are independent of one another, the agents can generate them all at the same time, without slowing down the overall process. The system then takes this diverse collection of near-perfect answers and blends them together, like mixing different shades of paint to find the exact right color. By mathematically combining these multiple options, the method can construct a final solution that fits all the rules perfectly, even if none of the individual ingredients did.

The researchers tested this approach on four distinct types of complex problems, ranging from allocating resources among many users to managing the flow of different goods through a network. In every case, they compared MARA against standard methods that rely on a single response per agent. The results were striking. In one test involving resource allocation, the standard method was still struggling to find a valid solution after nearly a hundred attempts, with the system remaining significantly out of balance. In contrast, the MARA method found a solution that satisfied all the rules within just a few dozen attempts, and in some cases, as early as iteration 25. The new method was able to produce a working solution that was not only feasible but also very close to the best possible outcome, often within one percent of the ideal. This speed was achieved without sacrificing the parallel nature of the work; the extra computing power required to generate multiple answers was handled in the background, meaning the total time to reach a solution did not increase.

The beauty of this approach lies in its flexibility. The researchers showed that the method can be tuned to prioritize different goals. If the priority is speed, the system can be set to accept a wider range of imperfect answers, allowing it to find a valid solution almost instantly. If the priority is extreme precision, the system can be adjusted to demand higher-quality answers from the agents, which takes a bit more time but yields a result that is even closer to perfect. The team also found that remembering past answers and including them in the mix could further accelerate the process, helping the system find a valid solution even faster. This suggests that the method is not just a theoretical curiosity but a practical tool that can be adapted to the specific needs of different industries.

What makes this development particularly significant is that it works alongside existing algorithms rather than replacing them. It acts as a parallel side calculation, a safety net that catches the system when it starts to drift out of alignment. The researchers demonstrated that this works whether the underlying system is using a simple, step-by-step approach to find prices or a more complex, sophisticated method. In the simulations, the standard methods often failed to find a valid solution at all within the time limits, or they produced solutions that were so far off that they were useless. MARA, however, consistently delivered a solution that was both valid and high-quality. The method does not require the agents to change their internal logic or to communicate more frequently; it simply asks them to provide a few more options. This makes it a relatively easy addition to current systems, offering a way to unlock the full potential of distributed computing without the usual trade-off of losing control over the final result.

The implications of this work extend to any field where large-scale coordination is necessary. Whether it is balancing the electrical grid to prevent blackouts, optimizing the delivery of medical supplies, or managing the traffic flow in a smart city, the ability to quickly find a solution that works is critical. The researchers noted that while their method increases the total amount of computing work being done, it does not increase the time it takes to get an answer because the work happens in parallel. In an era where computing resources are abundant but time is scarce, this trade-off is often worth it. The method provides a way to use that extra computing power to ensure that the final solution is not just a mathematical abstraction, but a practical, working reality. By tolerating a small amount of imperfection in the individual steps, the system achieves a high degree of perfection in the final outcome, turning a chaotic collection of independent decisions into a harmonious, functioning whole.

Technical Summary: Multiple Approximate-Response Agents (MARA)

Problem Statement

Distributed optimization methods decompose large-scale problems into parallel subproblems (agents) linked by coupling constraints, typically solved via dual methods. While dual methods allow for parallel computation and scalability, they face a fundamental limitation: primal recovery.

In dual methods, agents respond to dual prices (Lagrange multipliers) by solving local subproblems. However, recovering a primal solution that satisfies the coupling constraints (primal feasibility) is challenging for two main reasons:

Precision Requirements: Achieving primal feasibility often requires dual prices of extremely high precision, necessitating many dual iterations that can erode the time gains from parallelization.
Non-Strict Convexity: For important problem classes like linear models (or generally non-strictly convex problems), even optimal dual prices do not guarantee that the agents' primal responses will satisfy the coupling constraints. In such cases, the primal solution may remain infeasible indefinitely, or standard techniques like primal averaging may converge too slowly or yield poor quality solutions.

Methodology: MARA

The authors propose Multiple Approximate-Response Agents (MARA), a primal recovery method designed to rapidly reduce primal infeasibility by tolerating a controlled degree of suboptimality. MARA is designed as a "side calculation" that can be appended to any dual algorithm without altering the underlying price discovery mechanism or increasing the wall-clock time of the dual iterations.

Core Mechanism

Instead of requesting a single primal response from each agent per dual iteration, MARA requires agents to generate multiple approximate primal responses. These responses are computed in parallel, meaning the wall-clock time remains equivalent to a single response.

The method consists of two primary components:

1. Multiple Approximate-Response Oracles

MARA utilizes two distinct methods to generate a set of $N$ near-optimal responses $\{z_1, \dots, z_N\}$ for a given price vector $y$ :

Value Suboptimality Oracle: Agents solve a convex problem to find points where the objective value $f(z) - y^T z$ is within a bounded suboptimality $\epsilon_v$ of the optimal value. This requires modifying the agent subproblems.
Price Perturbation Oracle: Agents solve the standard subproblem but with perturbed prices $y + \delta$ , where $\delta$ is sampled from a bounding box. This generates responses that are $\epsilon_p$ -suboptimal with respect to the original price $y$ . This method does not require modifying the agent subproblems.

2. Primal Recovery via Convex Combination

Once the multiple responses are collected, MARA constructs a new primal solution $\bar{x}$ by forming a convex combination of these responses. This is achieved by solving a small auxiliary Linear Program (LP):

Objective: Minimize the sum of primal residuals ( $r_p$ ) and complementary slackness residuals ( $r_c$ ).
Constraints: The solution $\bar{x}$ must be a convex combination of the agents' multiple responses ( $\bar{x}_i = Z_i u_i$ , where $Z_i$ contains the $N$ responses for agent $i$ and $u_i$ are convex weights).

Because the LP operates on the collected responses and is independent of the dual algorithm's main loop, it can be executed in parallel.

Variations and Extensions

The paper outlines several flexible variations:

Objective Modification: The LP can be modified to minimize only primal residuals ( $r_p$ ) if the suboptimality of the candidate points is already known to be tolerable.
Historical Data: The candidate set can be expanded to include responses from previous iterations (history $H$ ) to search a larger polytope for feasibility.
Suboptimality Mixing: Different levels of suboptimality ( $\epsilon$ ) can be mixed across the response budget to balance the trade-off between speed of convergence and solution quality.

Key Contributions

Novel Primal Recovery Framework: MARA introduces a method that decouples primal feasibility from the precision of dual prices by leveraging a diverse set of near-optimal responses.
Parallel Efficiency: By generating multiple responses in parallel, MARA achieves rapid reduction in primal residuals without increasing the wall-clock time of the underlying dual algorithm.
Algorithm Agnosticism: The method is agnostic to how dual prices are computed (e.g., subgradient methods, cutting-plane methods, localization methods) and can enhance any existing dual algorithm.
Controllable Trade-offs: The method provides hyperparameters (number of responses $N$ , suboptimality threshold $\epsilon$ , and history $H$ ) that allow users to explicitly control the trade-off between convergence speed, computational budget, and the degree of suboptimality in the final feasible solution.

Numerical Results

The authors tested MARA on four problem classes: Resource Allocation, Assignment Problem (convex relaxation), Multi-commodity Flow, and Shipment Problem (Optimal Transport). Experiments were conducted using two dual methods: Projected Dual Subgradient and Homogeneous Analytic Center Cutting-Plane Method (ACCPM).

Key Findings:

Rapid Convergence: MARA typically converges to a feasible, near-optimal solution within a few tens of iterations, whereas the underlying dual algorithm's raw primal output ( $x_k$ ) and standard primal averaging often remain infeasible or highly suboptimal even after 100+ iterations.
Performance Gaps:
- In the Resource Allocation problem, MARA found a feasible point with 0.1% suboptimality at iteration 92, while the raw dual solution remained 16.7% infeasible.
- In the Assignment Problem, MARA achieved feasible points with suboptimality < 4% by iteration 22, while competing methods showed suboptimality > 23%.
- In the Shipment Problem, MARA recovered feasibility at iteration 16 (suboptimality 15.5%), while competing methods failed to find any feasible point within 100 iterations.
Hyperparameter Sensitivity:
- Suboptimality ( $\epsilon$ ): Larger $\epsilon$ (e.g., 10%) leads to faster discovery of feasible points but slightly higher final suboptimality compared to smaller $\epsilon$ (e.g., 1%).
- Number of Responses ( $N$ ): Increasing $N$ (e.g., from 10 to 50) accelerates the reduction of residuals, finding feasible points significantly faster.
- History: Incorporating historical responses ( $H > 1$ ) accelerates the identification of feasible points, though it may slightly increase the final suboptimality.

Significance and Claims

The paper claims that MARA addresses a major barrier to the adoption of distributed optimization: the difficulty of recovering primal feasibility. By tolerating a small degree of suboptimality in agent responses and leveraging parallel computation to blend these responses, MARA can produce high-quality, feasible solutions quickly.

The authors emphasize that MARA is particularly valuable in modern computing environments where large computational budgets are available. It allows practitioners to trade increased computational resources (parallel calls) for significantly reduced wall-clock time to reach a feasible solution. The method is presented as a flexible, modular enhancement to existing dual algorithms, with future work suggested for extending the approach to non-convex agents with integrality constraints.