5. Oracles¶

This section documents the constructors, properties, and methods of the Oracle and SpectralOracle classes. Hidden and inherited properties are not shown here for simplicity.

Warning

The oracle classes in this section inherit from the copyable handle class meaning that all assignments made on these objects will only hold references to the underlying data. In other words, more than one variable can refer to the same underlying object! For example, consider the following code:

a = Oracle;
a.f_s = @() 1;
b = a;
b.f_s = @() 10;
disp(a.f_s())

The above code will return a value of 10 to the terminal, instead of 1 because the underlying data of a was modified through b.

To make an explicit copy of an oracle object, without creating a reference to the original object, one must invoke the copy() function before the assignment. For example, consider the following code, which is a modification of the previous example:

a = Oracle;
a.f_s = @() 1;
b = copy(a);
b.f_s = @() 10;
disp(a.f_s())

The above code, this time, will return a value 1 to the terminal as a and b are now refering to different objects.

class src.oracles.Oracle(varargin)¶

Bases: matlab.mixin.Copyable, dynamicprops

An abstact oracle class for unconstrained composite optimization.

f_s¶

A zero argument function that, when evaluated, outputs \(f_s(x)\). Defaults to @() 0.

Type: function handle

grad_f_s¶

A zero argument function that, when evaluated, outputs \(\nabla f_s(x)\). Defaults to

Type: function handle

``@

Type: ) zeros(size(x)

f_n¶

A zero argument function that, when evaluated, outputs \(f_n(x)\). Defaults to @() 0.

Type: function handle

prox_f_n¶

A one argument function that, when evaluated at \(\lambda\), outputs

\[{\rm prox}_{\lambda f_n}(x) := {\rm argmin}_u \left\{\lambda f_n(u) + \frac{1}{2}\|u-x\|^2\right\}.\]

Defaults to @(lam) x.

Type: function handle

f_s_at_prox_f_n¶

A one argument function that, when evaluated at \(\lambda\), returns the value of \(f_s\) at the point given by the function prox_f_n at \(\lambda\). This is generally used to speed up certain algorithms (see src/solvers/ACG.m). Defaults to None.

Type: function handle

prod_fn¶

A two argument function that, when evaluated at \(\{a, b\}\), outputs the inner product \(\langle a,b \rangle\). Defaults to the Euclidean inner product, i.e. @(a,b) sum(dot(a, b)).

Type: function handle

norm_fn¶

A one function that, when evaluated at a point \(a\), outputs \(\|a\|\). Defaults to the Frobenius norm, i.e. norm(a, 'fro').

Type: function handle

Oracle(varargin)¶

The constructor for the Oracle class. It has three ways to initialize:

Oracle() creates an oracle that represents the zero function, i.e. \(f_s = f_n \equiv 0\).
Oracle(f_s, f_n, grad_f_s, prox_f_n) creates an Oracle object with the properties f_s, f_n, grad_f_s, and prox_f_n filled by the corresponding inputs.
Oracle(eval_fn) creates an Oracle object which, when evaluated at a point \(x\), updates the properties f_s, f_n, grad_f_s, and prox_f_n as follows:
```
f_s = eval_fn(x).f_s;
f_n = eval_fn(x).f_n;
grad_f_s = eval_fn(x).grad_f_s;
prox_f_n = eval_fn(x).prox_f_n;
```
Similar updates are made for f_s_at_prox_f_n, f_n_at_prox_f_n, and grad_f_s_at_prox_f_n, if these are generated by eval_fn().

eval(x)¶: Evaluates the oracle at a point x and updates the properties f_s, f_n, grad_f_s, and prox_f_n to be at this point.

add_smooth_oracle(other_obj)¶

Modified the suboracles by adding the smooth suboracles of an input oracle to the smooth suboracles of the current oracle. That is, the properties f_s, f_n, grad_f_s, and prox_f_n are updated as follows:

f_s(x) = f_s(x) + input_oracle.f_s(x);
grad_f_s(x) = grad_f_s(x) + input_oracle.grad_f_s(x);

scale(alpha)¶

Modified the suboracles by multiplying by a positive constant alpha. That is, the properties f_s, f_n, grad_f_s, and prox_f_n are updated as follows:

f_s(x) = alpha * f_s(x);
f_n(x) = alpha * f_n(x);
grad_f_s(x) = alpha * grad_f_s(x);
prox_f_n(x, lambda) = prox_f_n(x, alpha * lambda);

add_prox(x_hat)¶

Modified the suboracles by adding a prox term at a point x_hat. That is, the properties f_s, f_n, grad_f_s, and prox_f_n are updated as follows:

f_s(x) = f_s(x) + (1 / 2) * norm_fn(x - x_hat) ^ 2;
grad_f_s(x) = grad_f_s(x) + (x - x_hat);

proxify(alpha, x_hat)¶

Modify the suboracles by multiplying by a positive constant alpha and then adding a prox term at a point x_hat. That is, the properties f_s, f_n, grad_f_s, and prox_f_n are updated as follows:

f_s(x) = alpha * f_s(x) + (1 / 2) * norm_fn(x - x_hat) ^ 2;
f_n(x) = alpha * f_n(x);
grad_f_s(x) = alpha * grad_f_s(x) + (x - x_hat);
prox_f_n(x, lambda) = prox_f_n(x, alpha * lambda);

decompose()¶

A zero argument method that, when evaluated, returns variants of the properties f_s, f_n, grad_f_s, and prox_f_n, where an additional argument x is added to the beginning of the of the list of function inputs. For example, the value f = f_s(x), computed from the output function, is equivalent to:

my_oracle.eval(x);
f = my_oracle.f_s();

where my_oracle refers to the oracle object that is calling decompose().

class src.oracles.SpectralOracle(varargin)¶

Bases: src.oracles.Oracle

An abstact spectral oracle class for unconstrained spectral composite optimization.

Note

This oracle is specialized for solving nonconvex composite optimization problems in which \(f_s = f_{1,s} + f_{2,s}^{\cal V} \circ \sigma\) and \(f_n = f_{n}^{\cal V} \circ \sigma\) for absolutely symmetric functions \(f_{2,s}^{\cal V}\) and \(f_{n}^{\cal V}\). Here, \(\sigma()\) denotes operator that maps matrices to some form of type of spectral vector, e.g. a singular value vector.

Unlike the the usual Oracle object, this one has an additional method named spectral_eval() that takes two arguments, {X, x}, and updates \((f_s, f_n)\) with X and \((f_{2,s}^{\cal V}, f_n^{\cal V})\) with x separately. This can be helpful when the spectral vector \(\sigma(X)\) has already been computed. If x=[], the expected behavior is that x is computed from \(\sigma()\).

See also

Kong, W., & Monteiro, R. D. (2020). Accelerated Inexact Composite Gradient Methods for Nonconvex Spectral Optimization Problems. arXiv preprint arXiv:2007.11772.

spectral_grad_f2_s¶

A zero argument function that, when evaluated, outputs \(\nabla f_{2,s}^{\cal V}(x)\). Defaults to @() zeros(size(x)).

Type: function handle

spectral_prox_f_n¶

A one argument function that, when evaluated at \(\lambda\), outputs

\[{\rm prox}_{\lambda f_{n}^{\cal V}}(x) := {\rm argmin}_u \left\{\lambda f_n^{\cal V}(u) + \frac{1}{2}\|u-x\|^2\right\}.\]

Defaults to @(lam) x.

Type: function handle

f1_s¶

A zero argument function that, when evaluated, outputs \(f_{1,s}(X)\). Defaults to @() 0.

Type: function handle

f2_s¶

A zero argument function that, when evaluated, outputs \(f_{2,s}(X)\). Defaults to @() 0.

Type: function handle

grad_f1_s¶

A zero argument function that, when evaluated, outputs \(\nabla f_{1,s}(X)\). Defaults to @() zeros(size(X)).

Type: function handle

grad_f2_s¶

A zero argument function that, when evaluated, outputs \(\nabla f_{2,s}(X)\). Defaults to @() zeros(size(X)).

Type: function handle

decomp_fn¶

A one argument function that, when evaluated at \(X\), outputs three arguments {P, D, Q} where D is a diagonal matrix, P and Q are orthogonal matrices, and \(X=PDQ^*\). Defaults to @(X) svd(X, 'econ').

Type: function handle

SpectralOracle(varargin)¶

The constructor for the SpectralOracle class. It has three ways to initialize:

Oracle() creates an oracle that represents the zero function, i.e. \(f_s = f_n \equiv 0\).
Oracle(f_s, f_n, grad_f_s, prox_f_n) creates an Oracle object with the properties f_s, f_n, grad_f_s, and prox_f_n filled by the corresponding inputs.

Oracle(spectral_eval_fn) creates an Oracle object which, when spectrally evaluated at a pair {X, x}, updates the properties related to f_s, f_n, grad_f_s, and prox_f_n as follows:

% Update the suboracles
f_s = spectral_eval_fn(X, x).f_s;
f_n = spectral_eval_fn(X, x).f_n;
grad_f_s = spectral_eval_fn(X, x).grad_f_s;
prox_f_n = spectral_eval_fn(X, x).prox_f_n;
spectral_grad_f2_s = spectral_eval_fn(X, x).spectral_grad_f2_s;
spectral_prox_f_n = spectral_eval_fn(X, x).spectral_grad_f2_s;

Similar updates are made for f_s_at_prox_f_n, f_n_at_prox_f_n, and grad_f_s_at_prox_f_n, if these are generated by the underlying evaluator.

eval(X)¶: An alias for obj.spectral_eval(X, []).

spectral_eval(X, x)¶: Evaluates the spectral oracle at a pair {X, x} and updates all of the relevant properties at this pair.

scale(alpha)¶

Modified the suboracles by multiplying by a positive constant alpha. That is, the properties f_s, f_n, grad_f_s, and prox_f_n are updated as follows:

f_s(x) = alpha * f_s(x);
f_n(x) = alpha * f_n(x);
grad_f_s(x) = alpha * grad_f_s(x);
prox_f_n(x, lambda) = prox_f_n(x, alpha * lambda);

add_prox(x_hat)¶

Modified the suboracles by adding a prox term at a point x_hat. That is, the properties f_s, f_n, grad_f_s, and prox_f_n are updated as follows:

f_s(x) = f_s(x) + (1 / 2) * norm_fn(x - x_hat) ^ 2;
grad_f_s(x) = grad_f_s(x) + (x - x_hat);

vector_linear_proxify(alpha, x_hat)¶

Denoting \(\alpha = {\rm alpha}\) and \(\hat{x} = {\rm x\_hat}\), calling this method changes the underlying function of the oracle as follows:

\[\begin{split}f_{s}(x) & \gets\alpha f_{2,s}^{\cal V}(x)-\left\langle x,\hat{x}\right\rangle +\frac{1}{2}\|x\|^{2},\\ f_{n}(x) & \gets\alpha f_{n}^{\cal V}(x).\end{split}\]

This method is primarily used to convert the oracle from one that acts on a matrix space to one that acts on a vector space. It also makes sure that the eval() method is properly adjusted to take in vector inputs rather than matrix inputs.

redistribute_curvature(alpha)¶: Denoting \(\alpha = {\rm alpha}\), calling this method changes the underlying function of the oracle as follows:

\[\begin{split}f_{1,s}(X) & \gets f_{1,s}(X)-\frac{\alpha}{2}\|X\|_{F}^{2},\\ f_{2,s}(X) & \gets f_{2,s}(X)+\frac{\alpha}{2}\|X\|_{F}^{2},\\ f_{2,s}^{{\cal V}}(x) & \gets f_{2,s}^{{\cal V}}(x)+\frac{\alpha}{2}\|x\|^{2}.\end{split}\]

decompose()¶

A zero argument method that, when evaluated, returns variants of the properties f_s, f_n, grad_f_s, and prox_f_n, where an additional argument x is added to the beginning of the of the list of function inputs. For example, the value f = f_s(x), computed from the output function, is equivalent to:

my_oracle.eval(x);
f = my_oracle.f_s();

where my_oracle refers to the oracle object that is calling decompose().