\chisao{}: A GPU-Native Parallel Optimizer for Multimodal Black-Box Functions via Convergence-Anticonvergence Oscillation

• URL: http://arxiv.org/abs/2606.26164v1
• Date: Wed, 24 Jun 2026 06:33:29 GMT
• Title: \chisao{}: A GPU-Native Parallel Optimizer for Multimodal Black-Box Functions via Convergence-Anticonvergence Oscillation
• Abstract summary: chisao runs an entire sample batch simultaneously and exploits a deliberate convergence-anticonvergence cycle.<n>chisao achieves textbf100% mode recovery where all CPU baselines collapse at $d geq 8$ on the hardest multimodal functions.<n>The algorithm is available as a standalone open-source Python package on PyPI.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding all modes of a multimodal black-box function is a fundamental challenge in optimization, Bayesian inference, and scientific computing. Existing approaches -- basin-hopping, CMA-ES, multistart gradient descent -- operate sequentially and cannot exploit the massive parallelism of modern GPU hardware. We introduce \chisao{} (\textbf{C}onvergence-\textbf{H}alt-\textbf{I}nvert-\textbf{S}tick-\textbf{A}nd-\textbf{O}scillate), a GPU-native population optimizer that runs an entire sample batch simultaneously and exploits a deliberate convergence-anticonvergence oscillation cycle to escape local traps while freezing confirmed modes. The structural move is asymmetric: samples that reach true peaks are frozen (``stuck'') and preserved, while the rest keep exploring via momentum-based anti-convergence and stochastically smoothed gradients. Adaptive reseeding via two complementary strategies (Repulse Monkey and Golden Rooster) maintains population diversity throughout. On all 42 functions of the Simon Fraser University optimization benchmark suite across dimensions $d \in \{2, 4, 8, 16, 32, 64\}$, \chisao{} achieves \textbf{100\%} mode recovery where all CPU baselines collapse at $d \geq 8$ on the hardest multimodal functions, at up to \textbf{$34\times$} speedup over basin-hopping on functions where all methods succeed (Michalewicz $d=64$) and up to \textbf{$39\times$} on unimodal functions (Rotated Hyper-Ellipsoid $d=64$, pure GPU dividend). All benchmarks evaluate the objective by value alone -- gradients come from finite differences -- so the reported speedups are a derivative-free worst case. Under substantial likelihood noise ($σ_{\mathrm{noise}}$ up to 1.0), mode detection remains 100\% reliable. The algorithm is available as a standalone open-source Python package on PyPI.

Related papers

• Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator [41.84305838914204]
  We show that a novel MSVR estimator efficiently trace complexities to $mathcalO(1)$ blocks.<n>We also obtain improved dependence on $m$ when the outer function gradients are gradient.<n> Empirical studies on multi-task deep AUC demonstrate superior performance of the proposed linear estimators.
  arXiv  Detail & Related papers  (2026-09-14T15:21:32Z)
• Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization [0.0]
  We present a new type of nonconstrained Monte Carlo optimization for a single ergodic chain.<n>In particular, we address the projection-free setting using the generalized Carlo-Wolfevious gradient $MC-ALFCFC.<n>We show that the tuned method achieves expected sample complexity $widetildeO(_mathrmmix2G_+_mathrmmix5G_2)varepsilon-3+_mathrmmix5varepsilon-2.
  arXiv  Detail & Related papers  (2026-07-28T14:37:47Z)
• Decentralized Stochastic Nonconvex Optimization under the Relaxed Smoothness [21.090579632247707]
  We propose a novel algorithm called decentralized normalized gradient descent (DNS)<n>DNS can achieve an $bold$ilon point at each local agent.<n>We show the upper bounds on the sample complexity of $mathcal O(m-1(L_fsigma2Delta_fepsilon-4 + sigma2epsilon-2 + L_f-1)$ per agent.
  arXiv  Detail & Related papers  (2025-09-10T16:17:19Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  We provide a unified analysis of two-timescale gradient ascent (TTGDA) for solving structured non minimax optimization problems.<n>Our contribution is to design TTGDA algorithms are effective beyond the setting.
  arXiv  Detail & Related papers  (2024-08-21T20:14:54Z)
• Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
  This work considers the problem of finding first-order stationary point of a non atau function with potentially constant smoothness using a gradient. We develop a technique that allows us to prove $mathcalO(fracmathrmpolylog(T)sigmatT)$ convergence rates without assuming uniform bounds on the noise.
  arXiv  Detail & Related papers  (2023-02-13T18:13:36Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)
• Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
  In this paper, we revisit the constrained and continuous submodular iterations in both offline and online settings. We use the factorrevealing optimization equation to derive an optimal auxiliary function $F$ for problem $max_boldsymbolxinmathCf(boldsymbolx)$. In the online setting, we propose boosting a gradient feedback algorithm, achieving a regret of $sqrtD$ (where $D$ is the sum of delays of gradient feedback against $(fracgamma2)$ adversarial.
  arXiv  Detail & Related papers  (2022-01-03T15:10:17Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  We consider optimization with delayed gradients where, at each time stept$, the algorithm makes an update using a stale computation - d_t$ for arbitrary delay $d_t gradient. Our experiments demonstrate the efficacy and robustness of our algorithm in cases where the delay distribution is skewed or heavy-tailed.
  arXiv  Detail & Related papers  (2021-06-22T15:50:45Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  We consider the problem of learning the best-fitting single neuron as measured by the expected square loss. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$. For the ReLU activation, our population risk guarantee is $O(mathsfOPT1/2)+epsilon$.
  arXiv  Detail & Related papers  (2020-05-29T07:20:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.