SCOBO

This Python repo is for a comparison orcale based optimization algorithm introduced in [1], which is coined Sparsity-aware Comparison-Based Optimization (SCOBO).

[1] HanQin Cai, Daniel Mckenzie, Wotao Yin, and Zhenliang Zhang. A One-bit, Comparison-Based Gradient Estimator. Applied and Computational Harmonic Analysis, 60: 242-266, 2022.

To display math symbols properly, one may have to install a MathJax plugin. For example, MathJax Plugin for Github.

The Problem

We aim to minimize an objective function $f:\mathbb{R}^d \rightarrow \mathbb{R}$ via merely its noisy comparison orcales $\mathcal{C}_f(\cdot,\cdot):\mathbb{R}^d \times \mathbb{R}^d \rightarrow ${$-1,+1$}, where $$\mathbb{P}[\mathcal{C}_f(x,y)=\mathrm{sign}(f(y)-f(x))]=\theta(|f(y)-f(x)|)$$ with some monotonically increasing $\theta$ that $\theta(0)\geq 0.5$. In words, there is chance that the comparison orcale may return a wrong sign, but this chance is always less than $50$%. In addition, when comparing two more distinct points, the chance of getting a wrong sign is no worse than comparing two less distinct points.

Syntex

x, regret, tau_vec , c_num_queries = SCOBO(comparison, obj_fcn, num_iterations, default_step_size, x0, r, m, d, s, fixed_flip_rate, line_search, warm_started)

Input Description

1. comparison : handle of the comparison orcale
2. object_fcn : objective function, this is for recording regret only. not used for solving problem
3. num_iterations : number of iterations
4. default_step_size : default step size
5. x0 : initial iterate
6. r : sampling radius
7. m : number of samples per iteration
8. d : dimension of problem
9. s : sparsity level
10. fixed_flip_rate : ture if kappa==1, i.e., comparison orcale's flip rate is independent to |f(x)-f(y)|; otherwise false
11. line_search : wheather linesearch for step size. if not, use default step size
12. warm_started : wheather use warm start in linesearch

Output Description

1. x : estimated optimum point
2. regret : vector of errors f(x_k) - min f
3. tau_vec : tau_vec(k) = fraction of flipped measurements at k-th iteration
4. c_num_queries : cumulative number of queries.

Demo

Run test_sobo.py for demo. Therein, we include four test problems. More details about the test problems can be found in the paper.