# Mathematical optimization with thresholded optimization function

Gradient descent can be used to minimize an objective function $\Phi:\mathbb{R}^d \to \mathbb{R}$, if we know how to evaluate $\Phi$ on any input of our choice.

However, my situation is a little different. I have an objective function $\Phi$ of the form

$$\Phi(x) = \Phi_1(x) + \Phi_2(x),$$

where I can evaluate $\Phi_1$ on any input of my choice, but I don't have the ability to do that for $\Phi_2$. Instead, for $\Phi_2$, I have only a thresholded (quantized) version of $\Phi_2$: I can evaluate $f_2:\mathbb{R}^d \to \{0,1\}$ on any input of my choice, where $f_2$ is defined by

$$f_2(x) = \begin{cases} 0 &\text{if } \Phi_2(x)\le t\\ 1 &\text{if } \Phi_2(x) > t\\ \end{cases}$$

and $t$ is fixed. You can assume that $\Phi_2$ is smooth and has all the nice properties you might like, but I can only evaluate $f_2$, not $\Phi_2$. How can I search for an $x$ that's likely to make $\Phi(x)$ as small as possible, in this situation? Is there any way to adapt gradient descent or other mathematical optimization method to this setting?

Why I think there might be some hope: if we find $x',\delta \in \mathbb{R}^d$ such that $f(x')=0$ and $f(x'+\delta)=1$, where $x' \approx x$ and $\delta \approx 0$, then we've learned some information about $\Phi_2$, e.g., that the partial derivative of $\Phi_2$ is likely to be large in the $\delta$ direction. It seems like it might be possible to build an algorithm to exploit this kind of information. Are there any techniques to handle this kind of situation?

• Is it possible to use a sub-gradient method? What would happen if you used $f_2$ in the objective, but stepped using subgradients over $\Phi_2$ where $f_2$ isn't differentiable. Namely at $t$. – Nicholas Mancuso Dec 18 '15 at 3:15
• @NicholasMancuso, fascinating! I hadn't heard of the subgradient method before this. Looking at a tutorial on the subgradient method, it appears that the objective function needs to be convex (otherwise the subgradient isn't even defined). Unfortunately $f_2$ is not convex. Do you see any way to apply the subgradient method here despite that challenge? What would you use as the subgradient at the point where $f_2$ isn't differentiable (i.e., at $t$)? – D.W. Dec 18 '15 at 4:43
• I'll have to give it some thought. At first glance it looks like you're solving some regularized optimization problem; which I know has been amenable to sub-gradient approaches for non-differentiable functions (i.e. soft-thresholding for LASSO). I will be honest in that I'm not an expert in this field; however I will spend some time thinking about it more. I don't know if sub-gradient still gives local optima when the objective isn't convex. Intuition would say yes, but intuition is often wrong. – Nicholas Mancuso Dec 18 '15 at 17:16
• Are there other surrogate functions you can use to approximate $\Phi_2$? If you can find a convex relaxation you should be able to use either the sub-gradient method, or something with stronger guarantees like Majorize-Minimize Algorithm. – Nicholas Mancuso Dec 18 '15 at 17:48
• Thank you, @NicholasMancuso, that sounds helpful. I'll go read more about the MM algorithm. Here's one other direction that occurred to me. If $f(x)=1$, define $g(x,v)= \min\{c \in \mathbb{R}^+ : f(x+cv)=0\}$. Then $-1/g(x,v)$ looks like a plausible estimate for the partial derivative of $\Psi_2$ at $x$ in the direction $v$. In this way perhaps one can approximate $\nabla \Psi_2$ by computing $g(x,v)$ for a bunch of $v$'s (even though we can't evaluate $\Psi_2$ directly) and thus estimate $\nabla \Psi$, and then apply the gradient method from there. – D.W. Dec 18 '15 at 23:10

I guess $f_2(x)$ is some sort of oracle that tells you if $\Phi_2(x)$ is greater than $t$? If the set $\{\mathbf{x} : \Phi_2(x) \le t\}$ is convex, then I think projected gradient algorithm might be helpful. Could you provide more information on $\Phi_2(x)$? The question is kinda confusing with the information provided.
• Yes, that's exactly right, that's what $f_2$ is. I think the set $S=\{x : \Phi_2(x) \le t\}$ might indeed be convex, so the projected gradient method sounds helpful -- thank you for the suggestion. Unfortunately, I currently don't know how to project onto $S$, i.e., given a point $x$, I don't know how to find the closest point $x' \in S$, so I'm not sure if I'm going to be able to apply this -- but it sounds intriguing. Off to learn about the projected gradient method.... – D.W. Dec 18 '15 at 23:05
• Actually, would it be possible to figure out $\Phi_2(\mathbf{x})$ using the oracle by plugging in different $t$, using some bisecting algorithm? – H.S. Dec 19 '15 at 0:22
• I'm afraid $t$ is fixed and not under my control, so that won't work. – D.W. Dec 19 '15 at 0:24
• Okay. So $t$ is built into the oracle. Hmmm... – H.S. Dec 19 '15 at 0:26