Distributed Derivative-Free Optimization Using Inexact ADMM and Trust-Region Methods
Damilola Fasiku, Wentao Tang · 2025
Read Distributed Derivative-Free Optimization Using Inexact ADMM and Trust-Region Methods by Damilola Fasiku, Wentao Tang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-27396.txt.
Introduction
Damilola Fasiku and Wentao Tang split a hard tuning problem across many machines in this 2025 paper. The problem is derivative-free optimization: tuning a black-box system whose slopes are unknown. The goal splits into parts held by different machines, tied by shared rules. Exact solves at each step are too costly to demand.
Their scheme builds on ADMM, a method that swaps messages between parts until they agree. A two-level design handles the shared rules: an inner loop updates each part, an outer loop pushes a slack value to zero. Each part is solved loosely by a trust-region solver, one that trusts its local model only near the current point. The slack allowed shrinks in a controlled way. They prove the method settles near a true answer and beats one-machine approaches on hard tests.
Catalog record
| CREATOR | Damilola Fasiku, Wentao Tang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-27396
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Distributed Derivative-Free Optimization Using Inexact ADMM and Trust-Region Methods Damilola Fasiku, Wentao Tang Abstract To reduce complexity and achieve scalable performance in high-dimensional black-box settings, we propose a distributed method for nonconvex derivative-free optimization (DFO) of continuous variables with an additively separable objective, subject to linear equality constraints. The approach is built upon the alternating direction method of multipliers (ADMM) as the distributed optimization framework. To handle general, potentially complicating linear equality constraints beyond the standard ADMM formulation, we employ a two-level ADMM structure : an inner layer that performs sequential ADMM updates, and an outer layer that drives an introduced slack variable to zero via the method of multipliers. In addition, each subproblem is solved inexactly using a derivative-free trust-region solver , ensuring suboptimality within a decreasing, theoretically controlled error tolerance. This inexactness is critical for both computational efficiency and practical applicability in black-box settings, where exact solutions are impractical or overly expensive. We establish theoretical convergence of the proposed approach to an approximate solution, building on analyses in related work, and demonstrate improved computational efficiency over monolithic DFO approaches on challenging high-dimensional benchmarks, as well as effective performance on a distributed learning problem. keywords Derivative-free optimization, Distributed optimization, Alternating direction method of multipliers (ADMM), Trust-region method 1 Introduction 1.1 Background Arguably, derivative information, when available, generally facilitates the convergence of iterative optimization methods, as this information is crucial to identifying effective search directions Liang et al. 2024 . However, cases where derivative information is unavailable are not uncommon in scientific and engineering applications, including machine learning (e.g., hyperparameter tuning), process engineering (e.g., flowsheet design, computational fluid dynamics), and chemical/material computational design Conn et al. 2009 ; Boukouvala and Ierapetritou 2014 ; Bergstra et al. 2011 ; Zaryab et al. 2022 ; Terayama et al. 2021 . This can be due to the lack of an explicit mathematical model of the objective function, discontinuities, or non-differentiability at certain points, the unreliability of derivatives from noisy objective functions, and the unknown analytical form of the derivative Larson et al. 2019 . Optimization in this sense is called derivative-free optimization (DFO) or black-box optimization—an area of increasing research interest over the past two decades Conn et al. 2009 ; Boukouvala and Ierapetritou 2014 ; Larson et al. 2019 ; Powell 2003 . The DFO methods in the literature can be broadly categorized into direct search and model-based methods Larson et al. 2019 ; Boukouvala et al. 2016 . Direct search methods iteratively explore the search space by comparing objective function values evaluated at strategically selected sample points. This category includes techniques such as Random Search, which evaluates the objective function at randomly chosen points within the domain, and the Nelder-Mead Simplex method, which adjusts a simplex of points toward lower function values Rios and Sahinidis 2013 . Model-based DFO methods involve constructing approximate models of the objective function based on available data points. A popular optimization method in this category is Bayesian Optimization, a probabilistic approach that uses a Gaussian process to model the objective function and an acquisition function to select new evaluation points with a balance between exploration of uncertain regions with exploitation of promising ones Frazier 2018 ; Shahriari et al. 2015 . The application of Bayesian optimization in engineering has been shown in molecular modeling and design, additive manufacturing, controller tuning, and bubble column technology Wang and Dowling 2022 ; Lu et al. 2020 ; Kudva et al. 2022 , but its theoretical convergence largely remains an open question. The trust-region (TR) methods , when extended to derivative-free settings, form another class of model-based DFO methods. Here, surrogate models are constructed using function values within a defined trust region, and optimization steps are guided by these approximations, eliminating the need for derivative information Liang et al. 2024 ; Larson et al. 2019 ; Eason and Biegler 2016 ; Bajaj et al. 2018 ; Conn et al. 2000 . The global convergence of trust-region (TR) methods in derivative-free settings to first- and second-order critical points for smooth black-box functions has been established in Conn et al. 2009 . This represents an improvement over the earlier TR-based method proposed in Powell 2003 , which demonstrated good practical performance but lacked theoretical convergence guarantees. In Shashaani et al. 2018 , ASTRO-DF was introduced as a trust-region-based derivative-free optimization algorithm for stochastic settings, leveraging adaptive sampling to efficiently converge to first-order critical points. In Ghanbari and Scheinberg 2017 , a trust-region-based derivative-free optimization (TR-DFO) method was compared to Bayesian optimization methods in machine learning applications, demonstrating superior performance in optimizing noisy functions, including the Area Under the Receiver Operating Characteristic Curve (AUC), with fewer evaluations. The trust-region method in Conn et al. 2009 was extended in Garmanjani et al. 2016 to handle both smooth and nonsmooth functions, with worst-case complexity and convergence guarantees. However, the smoothing-based approach in Garmanjani et al. 2016 is only effective when the source of the nonsmoothness is known, limiting its applicability in pure black-box settings. Inspired by bundle methods, Liuzzi et al. 2019 introduced a trust-region method suitable for black-box nonsmooth functions, with global convergence guarantees. The techniques and results from Liuzzi et al. 2019 will be discussed later in this work. However, it should be noted that scalability of DFO methods to higher-dimensional problems remains an open area of research. The direct use of existing methods often struggles in these settings due to the increase in computational and sample complexity, known as “the curse of dimensionality” Rios and Sahinidis 2013 ; Ling et al. 2017 , which frequently arises in applications such as drug discovery He et al. 2021 and materials design Ling et al. 2017 . In the derivative‐free optimization literature, high‐dimensional problems are typically addressed via two strategies: (i) reducing dimensionality through variable selection or subspace embeddings, under the assumption of low intrinsic dimensionality Qian et al. 2016 ; Wang et al. 2016 ; Song et al. 2022 ; and (ii) exploiting structural properties of the objective function, such as additivity, partial separability, or overlapping group structures Rolland et al. 2018 ; Porcelli and Toint 2022 . In the spirit of the second strategy above, this paper shows how an ADMM-based distributed optimization framework can be employed to solve high-dimensional DFO problems with structured objectives by decomposing the monolithic problem into manageable subproblems. Historically, the list of decomposition strategies includes Dantzig-Wolfe decomposition Dantzig and Wolfe 1960 , which is suitable for large-scale linear programming problems, and Bender’s decomposition Benders 1962 , suitable for mixed-integer linear programming problems. These methods leverage duality in a structured way to decompose a problem into more manageable parts. However, dual decomposition methods require relatively strong assumptions, such as differentiability of the objective function, and often suffer from slow convergence when subgradient methods are used Boyd et al. 2011 . The method of multipliers relaxes these assumptions while improving convergence stability by introducing a quadratic penalty term for constraint violations. However, this penalty term couples the primal variables, thereby preventing decomposition across subproblems Boyd et al. 2011 ; Zaryab et al. 2022 . ADMM combines the decomposability of dual decomposition with the convergence stability introduced by the quadratic regularization of the Method of Multipliers Boyd et al. 2011 ,