Source-linked AI summary
Adversarially Robust Optimization with Gaussian Processes
Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, Volkan Cevher
TL;DR
Standard GP optimization does not account for adversarial perturbations of the returned point, a concern when functions differ between optimization and implementation or when seeking regions of good inputs. The paper introduces confidence-bound-based STABLEOPT and analyzes its sample requirements. It reports rigorous guarantees and experimental improvements over natural baselines.
Problem
GP optimization typically seeks a high-valued returned point, but the paper considers settings where that point may be adversarially perturbed or where a region of good inputs is desired.
Source: §1 · p. 1Method
STABLEOPT uses confidence bounds for adversarially robust GP optimization, with a sample-complexity analysis and an algorithm-independent lower bound.
Source: §1 · p. 2Results
Takeaways & Limitations
The framework applies to several max-min optimization formulations, and experiments show STABLEOPT finding stable maximizers where several baselines fail.
Source: §1 · p. 2, §4 · p. 6, §6 · p. 9Whether wide maxima in hyperparameter space improve generalization remains to be established.
Source: §6 · p. 9
Abstract
from arXiv · showhide
In this paper, we consider the problem of Gaussian process (GP) optimization with an added robustness requirement: The returned point may be perturbed by an adversary, and we require the function value to remain as high as possible even after this perturbation. This problem is motivated by settings in which the underlying functions during optimization and implementation stages are different, or when one is interested in finding an entire region of good inputs rather than only a single point. We show that standard GP optimization algorithms do not exhibit the desired robustness properties, and provide a novel confidence-bound based algorithm StableOpt for this purpose. We rigorously establish the required number of samples for StableOpt to find a near-optimal point, and we complement this guarantee with an algorithm-independent lower bound. We experimentally demonstrate several potential applications of interest using real-world data sets, and we show that StableOpt consistently succeeds in finding a stable maximizer where several baseline methods fail.
1 Introduction
Standard GP optimization can face mismatches between the modeled and true functions or time-varying objectives. This paper studies GP optimization when the returned point must remain valuable under adversarial perturbation, and introduces STABLEOPT with theoretical guarantees and experimental evaluation.
1 Introduction
- The robustness objective is relevant both when optimization and implementation functions differ and when the goal is a region of good inputs rather than a single point.The paper also connects it to related max-min optimization settings.Source: §1 · p. 1
- Prior GP robustness work treats unreliable outliers, uncertain sampled points, or failed batch outcomes; the cited uncertain-sampling methods are random and lack theoretical results.Level-set estimation also seeks regions of good points rather than a single point.Source: §1 · p. 2
- Unlike related robust optimization that assumes a known objective, this problem learns an unknown objective through noisy point evaluations, or bandit feedback.The paper relates its formulation to non-convex robust optimization and adversarial training.Source: §1 · p. 2
- STABLEOPT addresses adversarially perturbed recommendations with a new algorithm, sample-complexity guarantees, an algorithm-independent lower bound, and experiments where it succeeds as several baselines fail.The framework also includes variations of its max-min formulation and theory.Source: §1 · p. 2
2 Problem Setup
The setup seeks a recommendation whose function value remains high across allowed perturbations, rather than simply maximizing the function at the returned point. It specifies noisy GP observations and explains why a standard maximizer may be unstable.
2 Problem Setup
- The model observes noisy evaluations of an unknown reward function at queried points and returns a recommendation after T rounds.Each observation is the function value plus Gaussian noise.Source: §2 · p. 2
- The analysis assumes a known kernel and a function with bounded norm in its associated RKHS, an assumption that permits GP confidence bounds.The kernel is normalized so k(x, x) = 1; squared exponential and Matérn kernels are noted as common choices.Source: §2 · p. 2
- The objective is low ϵ-regret: choose a point whose worst function value over its allowed perturbations is close to the best such stable value.The perturbation set is specified by a stability parameter ϵ and a distance-like function d; d need not be a mathematical distance.Source: §2 · p. 3
- With norm-based perturbations, low ϵ-regret favors broad peaks over narrow ones, especially as ϵ increases.The paper also notes that other max-min settings fit its framework.Source: §2 · p. 3
- GP-UCB can select a point that nearly maximizes f yet is suboptimal under the ϵ-stable objective, a limitation shared by methods targeting the non-robust global maximum.The accompanying example identifies the wider local maximum as the optimal ϵ-stable decision.Source: §2 · pp. 3–4
3 Proposed Algorithm and Theory
STABLEOPT selects a candidate with the highest stable upper confidence bound, then accounts pessimistically for adversarial perturbations when choosing where to sample. The paper bounds its sample requirements and gives an algorithm-independent lower bound, with scope-dependent differences between the two.
3 Proposed Algorithm and Theory
- STABLEOPT combines optimistic candidate selection with pessimistic evaluation of the adversarial perturbation when choosing a query.It selects the point with the highest stable upper confidence bound and queries a perturbation chosen to minimize the lower confidence bound.Source: §3 · p. 4
3.1 Upper bound on ϵ-regret
- For any f ∈ Fk(B), STABLEOPT with βt set as in Lemma 1 achieves rϵ(x(T)) ≤ η after T rounds with probability at least 1 − ξ; this holds for general kernels and finite or continuous D.Source: §3.1 · p. 5
3.2 Lower bound on ϵ-regret
- Theorem 2 gives a lower-bound result for epsilon-regret on [0,1]^p under Euclidean distance, considering an algorithm that guarantees r_epsilon(x(T)) ≤ eta after T rounds with probability at least 1−xi.The proof constructs difficult functions with narrow negative valleys that the adversary can perturb the reported point into, but that are hard to identify until many samples have been taken. B and xi are sufficiently small.Source: §3.2 · p. 5
- For constant B and σ², the SE-kernel lower bound nearly matches STABLEOPT’s upper bound, while larger gaps remain for Matérn, as in non-robust GP optimization.The lower-bound result is more restricted than the upper bound; general-kernel and general-domain lower bounds remain open even in the non-robust setting.Source: §3.2 · p. 5, §3.1 · p. 5
4 Variations of STABLEOPT
STABLEOPT extends beyond robustness to perturbations of the returned input, covering uncertain parameters, robust estimation, and group identification. The framework also extends to Bayesian optimization and preserves corresponding robust guarantees.
4 Variations of STABLEOPT
- The framework applies to robust max-min settings beyond perturbations within an ϵ-ball, including robustness to parameters and group identification.These variations are obtained by substituting choices of distance and stability radius into the algorithm and theorem.Source: §4 · pp. 6–7
- In the Bayesian setting, STABLEOPT and its variations apply when f is drawn from a GP, with the exploration parameter changed to the Bayesian choice.The proof relies on confidence bounds.Source: §4 · p. 6
- For robustness to unknown parameters, a composite kernel models the function over both x and θ, and the objective seeks an x robust to possible θ values.Applications described include parameters that become uncontrollable at implementation and hyperparameter tuning across related data types.Source: §4 · p. 6
- With an estimated coefficient θ̄, robust estimation accounts for uncertainty by optimizing against perturbations δθ around that estimate.The resulting guarantee compares the selected input’s worst-case value with the best worst-case value over the input domain.Source: §4 · p. 6
- For robust group identification, the reported group is judged by its minimum function value and compared with the best group’s minimum value.The groups partition the input space into disjoint subsets.Source: §4 · pp. 6–7
5 Experiments
Across synthetic and real-world tasks, STABLEOPT outperforms the tested baselines on robust objectives, including finding the optimal movie group when the other methods do not. The experiments also show that optimizing for the ordinary global maximum can yield points that are suboptimal under ϵ-regret.
Experimental setup
- STABLEOPT samples a perturbed point but reports the sampled candidate with the highest worst-case lower confidence bound; the baselines are heuristic and lack near-optimal-stability guarantees.The evaluation metric is ϵ-regret; the authors omit other standard GP methods because their performance is comparable to GP-UCB and they share its pitfalls.Source: §5 · p. 7
Synthetic function
- Across 100 runs, STABLEOPT significantly outperformed the baselines on the synthetic function, whose baselines later reported points near the global optimizer but suboptimal in ϵ-regret.The performance comparison is shown in Figure 2; the experiment used 100 sampling rounds.Source: §5 · p. 8, Figure 2 · p. 8
Lake data
- In the supplementary Lake Zürich chlorophyll experiment, STABLEOPT again performed best.Source: §5 · p. 8
Robust robot pushing
- In robust robot pushing with two possible target locations, STABLEOPT noticeably outperformed competitors except in some very early rounds.The comparison averaged results over 30 random pairs of objectives; apparent curve discontinuities came from hyperparameter re-estimation.Source: §5 · p. 8, Figure 3 · p. 9
Group movie recommendation
- Among GP-UCB, MAXIMIN-GP-UCB, and STABLEOPT, only STABLEOPT found the optimal movie group, while average ϵ-regret decreased rapidly after a few rounds.The average was taken over 500 test users.Source: §5 · p. 9
6 Conclusion
The conclusion presents STABLEOPT as a robust GP optimization method with rigorous guarantees and reports improvements over natural baselines in experimental examples.
6 Conclusion
- The paper introduces GP optimization requiring stability to adversarial perturbations and presents STABLEOPT with rigorous guarantees.Source: §6 · p. 9
- The framework applies naturally to several max-min optimization formulations, with significant improvements over some natural baselines in experimental examples.Source: §6 · p. 9
A Illustration of STABLEOPT’s Execution
- After 15 steps in the running example, STABLEOPT’s ϵ-stable point corresponds to x∗.Source: Figure 4 · p. 12
B.1 Proof of Theorem 1 (upper bound)
The upper-bound proof controls the selected point’s robust regret using confidence bounds and information gain, then returns the iterate with the smallest computable pessimistic regret estimate.
B.1 Proof of Theorem 1 (upper bound)
- The analysis bounds a pessimistic estimate of the selected point’s ϵ-regret by 2β^1/2.Source: §B.1 · p. 13
- Because the first term of the pessimistic regret estimate is independent of time, the algorithm selects x(T) to minimize that estimate.Source: §B.1 · p. 13
- The information-gain bound yields a sufficient sample condition TβTγT ≥ C1, with C1 = 8/log(1 + σ−2).Source: §B.1 · p. 13
B.2 Proof of Theorem 2 (lower bound)
The lower-bound proof adapts a narrow-bump construction into a valley whose ϵ-neighborhood makes many candidate points robustly poor, and compares an arbitrary deterministic optimizer against a finite function family.
B.2 Proof of Theorem 2 (lower bound)
- A narrow positive bump is ineffective for the stable-regret lower bound because nearby adversarial perturbations can make surrounding points nearly zero-valued.Source: §B.2 · p. 14
- The proof instead uses a narrow valley of depth −2η, making every point within ϵ of its minimizer robustly attain −2η.Source: §B.2 · p. 14
B.2.1 Preliminaries
- The lower bound considers an arbitrary deterministic optimizer whose sampling and final decisions depend on the noisy observation sequence.Source: §B.2.1 · p. 14
- The proof lower-bounds worst-case ϵ-regret using the average regret over a finite collection of constructed functions.Source: §B.2.1 · p. 14
- The construction shifts a common function to grid centers, with bounded RKHS norm and a width w outside which values exceed −η.Source: §B.2.1 · pp. 14–15
B.2.2 Analysis of the average ϵ-stable regret
The analysis establishes a sample-horizon necessity for low average ϵ-stable regret and extends the same form of necessity to high-probability guarantees.
B.2.2 Analysis of the average ϵ-stable regret
- The regret remains Ω(η) unless the sample horizon meets the theorem’s necessary threshold.Source: §B.2.2 · p. 17
- The theorem’s conditions on T are necessary to achieve average regret E[rϵ(x(T))] = O(η) with a sufficiently small implied constant.Source: §B.2.2 · p. 17
B.2.3 From average to high-probability regret
The lower bound on the sample count needed for average regret also applies to high-probability regret under the stated meaning of “high probability.” The paper also shows how varied max-min formulations fit within STABLEOPT’s general framework.
B.2.3 From average to high-probability regret
- The same-form sample lower bound remains necessary for high-probability ϵ-regret, when success probability is sufficiently close to one.The argument uses the bounded regret range and a reverse Markov inequality.Source: §B.2.3 · pp. 17–18
- The high-probability claim does not establish a lower bound for any particular specified success probability.The probability is sufficiently close to one as a function of ϵ, p, and kernel parameters, but constant with respect to T and η.Source: §B.2.3 · p. 18
C Details on Variations from Section 4
- Choosing arbitrary d(·,·) makes unknown-parameter, robust-estimation, and grouped max-min formulations special cases of Algorithm 1 and Theorem 1.The corresponding variations follow by substituting their distance-function and stability-parameter choices.Source: C Details on Variations from Section 4 · p. 18
D Lake Data Experiment
On the Lake Zürich dataset, STABLEOPT is the only method to report a near-optimal ϵ-stable point in later rounds, although STABLE-GP-UCB has the smallest ϵ-regret early on. The experiment targets high-concentration regions of a specified size.
D Lake Data Experiment
- Using 2,024 in-situ chlorophyll measurements from Lake Zürich, the experiment seeks fixed-size regions with high concentration throughout, unlike threshold-region detection [7].The stated motivation is that high concentration matters when spread across a sufficiently wide area.Source: D Lake Data Experiment · pp. 18–19
- In later rounds, STABLEOPT alone reports a near-optimal ϵ-stable point, while STABLE-GP-UCB has the smallest ϵ-regret early on.Figure 7 shows the later-round result on the Zürich lake dataset.Source: Figure 7 · p. 19, D Lake Data Experiment · p. 19
- Algorithms were evaluated over 120 rounds on a 50 × 50 posterior grid, with 100 random initializations and stability parameters ϵD=1.0 and ϵL=100.0.The experiment used a Matérn-5/2 ARD kernel whose hyperparameters were set using a smaller dataset.Source: D Lake Data Experiment · p. 19