Implementation of Bregman distances

[kohr-h]

As the discussion in #1267 goes, we may need to revise the way Bregman distances work in ODL. The discussion should continue here, please fill in the details.

[adler-j]

Copying the comments by @mehrhardt

odl/odl/solvers/functional/functional.py

Lines 235 to 239 in 3b8428c

	subgrad : `Operator`, optional
	A subgradient operator. Operator which that takes an element in
	`functional.domain` and returns a subdifferential of the functional
	in that point.
	Default: ``functional.gradient``.

When I define the Bregman distance, I normally would like to give a specific subgradient and not a subgradient operator that would compute one.

odl/odl/solvers/functional/functional.py

Line 253 in 3b8428c

D_f(x, y) = f(x) - f(y) - \\langle \partial f(y), x - y \\rangle.

The notation here is non-standard. Usually, one would pick a single subgradient p from the subdifferential \partial f(y) and define D_f^p(x, y) = f(x) - f(y) - \langle p, x - y \rangle.

[aringh]

Since we would like this for a 0.7 release in not to long, let's reactivate the discussion :-)

Regarding the comments from @mehrhardt, do we want to be able to send either an operator or a specific subgradient, or only a subgradient?

Also, is this the only change we want for the Bregman functional? What about changing "base point", or are we sticking with that one need to reinitialize a new functional in this case?

[kohr-h]

What about changing "base point", or are we sticking with that one need to reinitialize a new functional in this case?

I don't think there's a way around this, since set of subgradients directly depends on the base point.

Regarding the comments from @mehrhardt, do we want to be able to send either an operator or a specific subgradient, or only a subgradient?

My current favorite is to make this work similarly to derivative that you provide a point and get a Bregman distance, where the default subgradient is the gradient at that point. An optional subgradient can be supplied, which is an element of the functional domain (assuming Hilbert spaces). It's the duty of the user to make sure that the subgradient really is one.

But I don't know too much about this topic and would certainly listen to more informed opinions.

[mehrhardt]

I agree with everything you said @kohr-h. Do we have a flag if a functional is differentiable? For differentiable functions it should be exactly as you said and for non-differentiable ones, the user needs to provide the subgradient. However, it would be good if for non-differentiable ones, ODL does not try to "guess" a subgradient or something of this sort.

[mehrhardt]

Forgot to mention that I am really supportive of pushing this into ODL as soon as possible! :)

[kohr-h]

Do we have a flag if a functional is differentiable? For differentiable functions it should be exactly as you said and for non-differentiable ones, the user needs to provide the subgradient. However, it would be good if for non-differentiable ones, ODL does not try to "guess" a subgradient or something of this sort.

No, we don't have that flag, and I'd rather keep it out. It's another flag that requires tracking (although rules are simple), without really adding a lot of value. I prefer the logic "differentiable = derivative implemented".

[aringh]

What about changing "base point", or are we sticking with that one need to reinitialize a new functional in this case?

I don't think there's a way around this, since set of subgradients directly depends on the base point.

I am not sure I follow your line of though here... currently we can write functional.bregman(point), and if the function is differentiable it will return the bregman distance of the functional based in the given point, i.e., the subgradient is the gradient of the functional in the given point. My question is with respect to the fact if we now want to change the point in which we have the bregman distance, should one have to do functional.bregman(new_point), or should we allow

bregman_func = my_functional.bregman(point)
[other code]
bregman_func.point = new_point

My current favorite is to make this work similarly to derivative that you provide a point and get a Bregman distance, where the default subgradient is the gradient at that point.

This is exactly how it currently works. Currently one can also supply a optional subgrandient operator, which must of course be done if the function is not differentiable. As I understand @mehrhardt, he would rather like to supply a specific subgradient corresponding to the point. So my question is: keep the option to supply an operator and add the possibility to supply a specific subgradient, or remove the operator option and only supply a specific subgradient?

Keeping the operator is especially nice if one want so be able to update base point as above, using .point = new_point. Otherwise I do not think it matters that much.

[mehrhardt]

I would vote for the simplest option that one cannot change the base_point. Then the Bregman distance has two arguments: base_point and sub_grad. If the latter is not provided ODL tries to take a normal gradient.