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?

  • $\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$ Commented Dec 18, 2015 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.
    Commented Dec 18, 2015 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$ Commented Dec 18, 2015 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$ Commented Dec 18, 2015 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.
    Commented Dec 18, 2015 at 23:10

1 Answer 1


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.

  • $\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.
    Commented Dec 18, 2015 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.
    Commented Dec 19, 2015 at 0:22
  • $\begingroup$ I'm afraid $t$ is fixed and not under my control, so that won't work. $\endgroup$
    – D.W.
    Commented Dec 19, 2015 at 0:24
  • $\begingroup$ Okay. So $t$ is built into the oracle. Hmmm... $\endgroup$
    – H.S.
    Commented Dec 19, 2015 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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