🤖 machine learning

Large-scale Testing Global Optimization Methods with Black-box Adversarial Attacks

This paper proposes black-box adversarial attacks as a large-scale, modern benchmark for global optimization to address the limitations of existing small-scale, outdated analytical function suites, demonstrating the effectiveness of various evolutionary algorithms and metaheuristics in solving these high-dimensional challenges.

Original authors: Wojciech Zarzecki, Jarosław Arabas

Published 2026-08-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wojciech Zarzecki, Jarosław Arabas

Original paper licensed under CC BY 4.0 (http://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

Imagine you are trying to teach a robot to recognize animals. You show it thousands of pictures of horses, cats, and dogs until it gets really good at guessing. But what if someone could trick the robot? What if they could add a tiny, invisible speck of "noise" to a picture of a horse, and suddenly the robot thinks it's looking at a cat? This is called an adversarial attack. It's like a magic trick for computers: the human eye sees a horse, but the computer's brain sees a cat because of a secret, mathematical nudge.

To figure out how to make these tricks work (or how to stop them), scientists need to test different "search strategies." Imagine you are in a giant, foggy mountain range looking for the deepest valley. Some search strategies are like walking in a straight line until you hit a wall; others are like sending out a swarm of bees to explore every nook and cranny. For decades, scientists tested these strategies using simple, made-up mountains (mathematical functions) that were easy to draw but maybe didn't look like the real world. The big question is: Are these old, simple tests good enough to tell us which search strategy is actually the best for the messy, complex world of modern AI?

This paper, written by Wojciech Zarzecki and Jarosław Arabas from the Warsaw University of Technology, says "No, they aren't." The authors argue that the problem of tricking an AI (the adversarial attack) is actually a perfect, real-world test for these search strategies. They treat the attack as a giant puzzle: find the smallest, most invisible change to an image that will fool the computer. They tested several different "swarm" search methods (like Evolutionary Algorithms and Grey Wolf Optimizers) to see which ones could solve this puzzle best.

Here is what they found:

The Puzzle is Tricky
First, the authors wanted to prove that this isn't a simple puzzle with just one answer. They used a local search method (a strategy that only looks at the immediate neighborhood) on thousands of images. They found that when they started from different random spots, they ended up with different "solutions." Some solutions changed a few pixels here, others changed a few pixels there. This proved that the landscape is "multimodal," meaning it has many different valleys and peaks, not just one. It's not a smooth slide to the bottom; it's a jagged, confusing mountain range where you can get stuck in a small dip that isn't the deepest one. This confirms that you need powerful "global" search methods to find the best trick.

The Searchers
The team put several different search algorithms to the test on two famous image datasets: CIFAR-10 (small, 32x32 pixel images) and ImageNet (huge, high-resolution images). They gave each algorithm a budget of how many times it could "peek" at the image to see if it was fooled.

The "Greedy" Searchers: Some methods, like the INFO optimizer, acted a bit like a greedy local search. They found solutions quickly but often got stuck with weaker tricks (lower success rates).
The "Swarm" Searchers: Methods like DE (Differential Evolution), GEN (Genetic Algorithm), and SHADE were much better. They explored the space more thoroughly. For example, on the CIFAR-10 dataset, when the allowed "noise" (perturbation) was set to 0.2, the GEN method successfully tricked the computer 97.40% of the time, while SHADE did it 89.61% of the time.
The "Wolf" Struggled: The GWO (Grey Wolf Optimizer) had a hard time when the rules were strict. Without a special "regularization" setting (a rule to keep the noise small), it only succeeded about 10–15% of the time. However, when the authors added a specific rule to balance the noise, the GWO caught up and performed much better.

The Size Matters
The size of the image made a huge difference. On the smaller CIFAR-10 images, even a tiny amount of allowed noise (0.01) was almost impossible to use; the algorithms failed almost completely. But on the massive ImageNet images, the same tiny noise was even harder to use (0% success for everyone). However, once they allowed a bit more noise (0.1 or 0.2), the algorithms became very effective. On ImageNet with 0.2 noise, the DE algorithm achieved a 100% success rate, meaning it could trick the computer on every single image it tried.

The Takeaway
The paper suggests that using these "black-box" adversarial attacks is a fantastic way to test how good global optimization methods really are. It's a harder, more realistic challenge than the old, simple math problems. The results show that while some methods are better than others, the field is still learning. The authors didn't claim to have found the "perfect" algorithm; instead, they provided a new playground where researchers can test their tools. They also noted that in the future, they might want to test not just on making the computer confused, but on making it pick a specific wrong answer, and they might use a different way to measure "noise" that looks more like what a human eye would notice.

In short, the authors successfully showed that tricking an AI is a complex, multi-peaked mountain climb, and while some search teams (like GEN and SHADE) are currently the best hikers, there is still a lot of territory to explore.

Technical Summary: Large-scale Testing Global Optimization Methods with Black-box Adversarial Attacks

Problem Definition
The authors identify a stagnation in the development of global optimization methods due to the reliance on benchmark suites composed of a limited number of analytical functions, many dating back to the 1970s and 1980s (e.g., Ackley, Griewank, Rosenbrock). These "synthetic" problems risk biasing method development. The paper proposes that Black-Box Adversarial Attacks (BBAA) on image classification models serve as a robust, high-dimensional global optimization benchmark.

In a BBAA scenario, an attacker seeks to find a perturbation vector $\delta$ added to an input image $x$ such that the model's classification changes (misclassification), while the perturbation remains imperceptible to humans. The problem is formulated as a bound-constrained minimization where the objective function $L(\delta)$ combines the negative log-probability of the ground-truth class with an $L_2$ regularization term to minimize perturbation magnitude:
$L(\delta) = -\log p_{c(x)}(x + \delta) - \alpha\|\delta\|_2^2$
The feasible set is a hypercube $[-\epsilon, \epsilon]^n$ , where $n$ corresponds to the number of pixels (e.g., 3,072 for CIFAR-10, 150,528 for ImageNet).

Methodology
To validate the BBAA as a global optimization problem, the authors first demonstrated its multimodality. They employed a local search method, Stochastic Growth Attack with Binary Search Refinement (SGA-BSR), across 100 independent runs with different random seeds per image. The results showed that independent runs converged to different perturbation vectors with varying objective values, confirming the existence of numerous local optima and the necessity of global search strategies.

The core experimental phase involved testing several metaheuristic global optimization algorithms on BBAA tasks using two datasets: CIFAR-10 and ImageNet. The models used were a standard pre-trained ResNet-18 for ImageNet and a custom VGG-like architecture for CIFAR-10. The optimization algorithms tested included:

Classical Evolutionary Algorithm (GEN)
Differential Evolution variants: DE, JADE, SADE, SHADE
Grey Wolf Optimizer (GWO)
INFO (Efficient Optimizer based on Weighted Mean of Vectors)

Experiments were conducted with varying hyperparameters:

$\epsilon$ (Maximum perturbation): 0.01, 0.1, 0.2
$\alpha$ (Regularization weight): 0.0, 0.1, 1.0, 10.0, 100.0
Budget: Population size of 500 and 500 iterations per run.

Key Results
The experiments yielded the following observations:

Multimodality: The SGA-BSR local search produced diverse solutions across runs, confirming that the BBAA landscape is highly multimodal.
Impact of Hyperparameters:
- The perturbation limit $\epsilon$ was the most decisive factor. At $\epsilon=0.01$ , most optimizers failed to succeed on both datasets. Success rates increased significantly at $\epsilon=0.1$ and $\epsilon=0.2$ .
- The regularization weight $\alpha$ had a non-monotonic effect. A moderate value ( $\alpha=0.1$ ) generally improved performance by balancing the decision boundary crossing with perturbation minimization.
Algorithm Performance:
- GEN (Genetic Algorithm) and SHADE consistently achieved high success rates while maintaining low perturbation strength ( $L_2$ norm).
- GWO performed poorly without regularization (near-zero success at low $\epsilon$ ) but improved significantly with $\alpha=0.1$ , catching up to other population-based methods.
- INFO behaved like a greedy local search, plateauing at lower success rates but demonstrating query efficiency.
- DE and GWO tended to drift toward the corners of the admissible area, likely due to a lack of self-adaptation mechanisms found in SADE, JADE, or SHADE.
Dataset Comparison: Attacks were uniformly easier on ImageNet than on CIFAR-10 at matched $(\epsilon, \alpha)$ settings. The authors attribute this to ImageNet's higher input dimensionality and larger label set, which statistically shrinks the margin to the nearest competing class.

Significance and Contributions
The paper claims to take a step toward aligning global optimization research with the challenges of modern machine learning. Its primary contributions are:

Benchmark Proposal: Establishing BBAA as a valuable, high-dimensional global optimization benchmark that moves beyond traditional synthetic functions.
Empirical Validation: Demonstrating that BBAA is a multimodal problem requiring global search capabilities, verified through local search experiments.
Performance Baseline: Providing a comparative efficiency analysis of several metaheuristics (including classical EAs, DE variants, GWO, and INFO) on BBAA tasks without extensive parameter tuning.
Open Framework: Releasing a framework to allow the community to test new optimization methods against these adversarial challenges.

The authors conclude that while current methods show promise, future work should involve tuning these methods for higher efficiency, expanding the portfolio of optimizers, and potentially reformulating the objective function to include perceptual loss terms that better reflect human-visible distortion.

More like this