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 toNone
.- 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 propertiesf_s
,f_n
,grad_f_s
, andprox_f_n
filled by the corresponding inputs.Oracle(eval_fn)
creates an Oracle object which, when evaluated at a point \(x\), updates the propertiesf_s
,f_n
,grad_f_s
, andprox_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
, andgrad_f_s_at_prox_f_n
, if these are generated byeval_fn()
.
- eval(x)¶
Evaluates the oracle at a point
x
and updates the propertiesf_s
,f_n
,grad_f_s
, andprox_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
, andprox_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 propertiesf_s
,f_n
,grad_f_s
, andprox_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 propertiesf_s
,f_n
,grad_f_s
, andprox_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 pointx_hat
. That is, the propertiesf_s
,f_n
,grad_f_s
, andprox_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
, andprox_f_n
, where an additional argumentx
is added to the beginning of the of the list of function inputs. For example, the valuef = 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 namedspectral_eval()
that takes two arguments,{X, x}
, and updates \((f_s, f_n)\) withX
and \((f_{2,s}^{\cal V}, f_n^{\cal V})\) withx
separately. This can be helpful when the spectral vector \(\sigma(X)\) has already been computed. Ifx=[]
, the expected behavior is thatx
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}
whereD
is a diagonal matrix,P
andQ
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 propertiesf_s
,f_n
,grad_f_s
, andprox_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 tof_s
,f_n
,grad_f_s
, andprox_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
, andgrad_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.
- proxify(alpha, X_hat)¶
Modify the suboracles by multiplying by a positive constant
alpha
and then adding a prox term at a pointx_hat
. That is, the propertiesf_s
,f_n
,grad_f_s
, andprox_f_n
are updated as follows:f_s() = alpha * f_s() + (1 / 2) * norm_fn(x - x_hat) ^ 2; f_n() = alpha * f_n(); grad_f_s() = alpha * grad_f_s() + (x - x_hat); prox_f_n(lambda) = prox_f_n(alpha * lambda);
- 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}\]