falkon.optim

Optimizer

class falkon.optim.Optimizer

Conjugate gradient methods

ConjugateGradient

class falkon.optim.ConjugateGradient(opt: Optional[falkon.options.ConjugateGradientOptions] = None)

FalkonConjugateGradient

class falkon.optim.FalkonConjugateGradient(kernel: falkon.kernels.kernel.Kernel, preconditioner: falkon.preconditioner.preconditioner.Preconditioner, opt: falkon.options.FalkonOptions, weight_fn=None)

Preconditioned conjugate gradient solver, optimized for the Falkon algorithm.

The linear system solved is

\[\widetilde{B}^\top H \widetilde{B} \beta = \widetilde{B}^\top K_{nm}^\top Y\]

where \(\widetilde{B}\) is the approximate preconditioner

\[\widetilde{B} = 1/\sqrt{n}T^{-1}A^{-1}\]

\(\beta\) is the preconditioned solution vector (from which we can get \(\alpha = \widetilde{B}\beta\)), and \(H\) is the \(m\times m\) sketched matrix

\[H = K_{nm}^\top K_{nm} + \lambda n K_{mm}\]
Parameters
  • kernel – The kernel class used for the CG algorithm

  • preconditioner – The approximate Falkon preconditioner. The class should allow triangular solves with both \(T\) and \(A\) and multiple right-hand sides. The preconditioner should already have been initialized with a set of Nystrom centers. If the Nystrom centers used for CG are different from the ones used for the preconditioner, the CG method could converge very slowly.

  • opt – Options passed to the CG solver and to the kernel for computations.

See also

falkon.preconditioner.FalkonPreconditioner

for the preconditioner class which is responsible for computing matrices T and A.