1
$\begingroup$

Quoting from Wikipedia:

A ridge function is any function $f:\mathbb{R}^d\rightarrow\mathbb{R}$ that can be written as the composition of a univariate function with an affine transformation, that is: $f(\mathbf{x})=g(\mathbf{x}\cdot\mathbf{a})$ for some $g:\mathbb{R}\rightarrow\mathbb{R}$ and $\mathbf{a}\in \mathbb{R}^d$.

This has the property that there are $d-1$ dimensions in which the ridge function is constant.

This led me to wonder the following questions:

What would be the most efficient algorithm to find $\hat{\mathbf{a}}=\mathbf{a}/|\mathbf{a}|$, the sole direction in which $f$ is not constant, when you can only query the function $f$; and what are the least restrictive conditions on $g$ to enable finding $\hat{\mathbf{a}}$? (The algorithm is also given a error bound $\epsilon\in\mathbb{R_{>0}}$, such that the algorithm is only required to find an $\hat{\mathbf{a}}_{approx}$ such that $|\hat{\mathbf{a}}_{approx} - \hat{\mathbf{a}}|<\epsilon$.)


I can imagine a gradient ascent on the magnitude of $h(x)=\partial f(\mathbf{y} + x\hat{\mathbf{x}})/\partial x$, as you vary $\hat{\mathbf{x}}\in \mathbb{R}^d$ (where $|\hat{\mathbf{x}}|=1$, $\mathbf{y}\in \mathbb{R}^d$ is fixed, and $x\ll |\mathbf{y}|$, $x\in\mathbb{R}$). In this case, the only requirement on $g$, then, is that its derivative is defined at $\mathbf{y}\cdot\mathbf{a}$.

But is there a more efficient algorithm, and how do the resources required for that algorithm scale with $d$ and error $\epsilon$?


(Side note: The problem is equivalent to determining the weights of a single-layer neural network whose single output neuron has a ridge activation function, solely by monitoring the single neuron's output.)

$\endgroup$
6
  • $\begingroup$ With no conditions on $g$, it is hopeless. Are there any particular kinds of conditions you are particularly interested in? Your gradient method can't be implemented with the assumptions listed here: you said all we can do is query the function $f$, so we can't compute the gradient and thus can't use that method. Should we assume that we also have the ability to query the gradient $\nabla f$? The problem of finding the neural network is much easier, as in that case $g$ is known and has a "nice" form. $\endgroup$
    – D.W.
    Apr 18 at 2:42
  • $\begingroup$ @D.W. The condition that $g$ is continuous in the neighborhood of a known point is interesting. Doesn't that alone allow us to estimate $\nabla f$ near that point, and therefore perform gradient descent? (As I described in the question?) If I am mistaken, it would be helpful to hear your thoughts answer. $\endgroup$ Apr 18 at 6:16
  • $\begingroup$ But I agree that the general case is hopeless, because $g$ can just e.g. multiply its input by zero. Hence, I was curious on the least restrictive condition on $g$, if such a thing can be reasoned about broadly. I'm willing to refine my question if it doesn't fall squarely in C.S. StackExchange's scope. $\endgroup$ Apr 18 at 6:19
  • 1
    $\begingroup$ No, continuity is not enough. You can use the $(f(x+\epsilon)-f(x))/\epsilon$ trick to estimate the gradient, but there's no way to know how small to make $\epsilon$; for any fixed $\epsilon$ chosen by the algorithm, an adversary can choose an $f$ that changes more rapidly to make $\epsilon$ much too large. Lipschitz with known Lipschitz constant $K$ might suffice, I don't know. $\endgroup$
    – D.W.
    Apr 18 at 15:35
  • $\begingroup$ @D.W. Good to know. It's perhaps not surprising that the precise answer depends a lot on what we know about $g$! If I wanted to rephrase the question asking for the minimum requirements on $g$ to guarantee gradient ascent, should I ask a separate question or edit this one? $\endgroup$ Apr 18 at 23:02

Your Answer

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

Browse other questions tagged or ask your own question.