3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Nicholas Mancuso Dec 18 '15 at 3:15
  • $\begingroup$ @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$)? $\endgroup$ – D.W. Dec 18 '15 at 4:43
  • $\begingroup$ 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. $\endgroup$ – Nicholas Mancuso Dec 18 '15 at 17:16
  • $\begingroup$ 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. $\endgroup$ – Nicholas Mancuso Dec 18 '15 at 17:48
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Dec 18 '15 at 23:10
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.... $\endgroup$ – D.W. Dec 18 '15 at 23:05
  • $\begingroup$ Actually, would it be possible to figure out $\Phi_2(\mathbf{x})$ using the oracle by plugging in different $t$, using some bisecting algorithm? $\endgroup$ – H.S. Dec 19 '15 at 0:22
  • $\begingroup$ I'm afraid $t$ is fixed and not under my control, so that won't work. $\endgroup$ – D.W. Dec 19 '15 at 0:24
  • $\begingroup$ Okay. So $t$ is built into the oracle. Hmmm... $\endgroup$ – H.S. Dec 19 '15 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.