Creates and keeps track of sets O and G for OAVI.

Manages the sets V, C and F for VCA.

Transforms SetsVCA.Fs into single matrix.

Creates and returns objective function, gradient and solution (through inversion) w.r.t. L2 loss.

Arguments

• 'data::Matrix{Float64}': evaluations of O_terms
• 'labels::Vector{Float64}': current border term evaluated
• 'lambda::Union{Float64, Int64}': regularization parameter
• 'data_squared::Matrix{Float64}': data' * data
• 'data_labels::Vector{Float64}': data' * labels
• 'labels_squared::Float64': labels' * labels
• 'datasquaredinverse::Union{Matrix{Float64}, Nothing}': inverse of data_squared for IHB, optional (default is nothing)

Returns

• 'solution::Vector{Float64}': solution to (unconstrained) minimization problem
• 'evaluate_function<:Function': objective function
• 'evaluate_gradient!<:Function': gradient of objective function, adjusted to FrankWolfe requirements

Transforms SetsVCA.Vs into single matrix.

Runs ABM algorithm to find coefficient vector and computes loss.

Arguments

• 'oracle_type::String': string denoting which oracle to construct
• 'data::Matrix{Float64}': data (O_evaluations)
• 'labels::Vector{Float64}': labels (term_evaluated)
• 'lambda::Union{Float64, Int64}': regularization parameter (if applicable)
• 'data_squared::Matrix{Float64}': squared data
• 'data_labels::Vector{Float64}': data' * labels
• 'labels_squared::Float64': labels' * labels
• 'datasquaredinverse::Union{Matrix{Float64}, Nothing}': inverse of data_squared (default is nothing)

Returns

• 'coefficient_vector::Vector{Float64}': coefficient vector minimizing ABM optimization problem
• 'loss::Float64': loss w.r.t. 'coefficient_vector'

applies the transformation corresponding to G to X_test

Applies transformation corresponding to V polynomials to X_test.

Computes sum (degree) of columns (terms) in A and returns output as (1 x size(A, 2)) matrix.

Returns coefficient_vector and loss found through CG-based algorithm fit to 'data'.

Arguments

• 'oracle_type::String': type of CG-based algorithm (choice from 'CG', 'BCG', 'BPCG')
• 'data::Matrix{Float64}': evaluations of O_terms
• 'labels::Vector{Float64}': current border term evaluated
• 'lambda::Union{Float64, Int64}': regularization parameter
• 'data_squared::Matrix{Float64}': data' * data
• 'data_labels::Vector{Float64}': data' * labels
• 'labels_squared::Float64': labels' * labels
• 'datasquaredinverse::Union{Matrix{Float64}, Nothing}': inverse of data_squared for IHB, optional (default is nothing)
• 'psi::Float64': vanishing parameter, optional (default is 0.1)
• 'epsilon::Float64': solver accuracy, optional (default is 0.001)
• 'tau::Float64': bound on coefficient_vector norm, optional (default is 1000.)
• 'inversehessianboost::String': whether or not to use IHB (choice from 'false', 'weak', 'full'), optional (default is 'false')

Returns

• 'coefficientvector::Vector{Float64}': coefficientvector minimizing L2Loss over L1Ball
• 'loss::Float64': loss w.r.t. 'coefficient_vector'

initializes SetsOandG instance w.r.t. X_train

Given the data X, this function constructs the intial state of 'SetsVCA'.

constructs the border of 'terms'

Arguments

• 'terms::Matrix{Int64}': Matrix with monomial terms as columns
• 'terms_evaluated::Matrix{Float64}': Matrix with evaluations of 'terms' over X
• 'X_train::Matrix{Float64}': data
• 'degree1terms::Matrix{Int64}': Matrix with degree 1 monomials as columns
• 'degree1termsevaluated::Matrix{Float64}': evaluations of 'degree1_terms' over X
• 'purging_terms::Matrix{Int64}': purge terms in 'terms' divisible by any of these

Returns

• 'bordertermsraw::Matrix{Int64}': non-purged border constructed from 'terms'
• 'borderevaluationsraw::Matrix{Float64}': non-purged evaluations of border terms over X
• 'nonpurgingindices::Vector{Int64}': array of non-purging indices
• 'raw_permutation::Vector{Int64}': array with deg-lex ordering permutation

constructs the border for current state of the algorithm.

Converts a term given as a vector denoting the exponents into LaTeX string

sorts matrix1 degree-lexicographically and matrix2 accordingly

Applies the OAVI feature transformation to X_test.

Evaluates the transformation corresponding to the polynomials in Gcoefficientvectors.

Arguments

• 'sets::SetsOandG': instance of SetsOandG, containing transformation

Returns

• 'totalnumberofzeros::Int64': Sum of all zero entries in coefficientvectors in Gcoefficientvectors.
• 'totalnumberofentries::Int64': Total number of entries in coefficientvectors in Gcoefficientvectors.
• 'avgsparsity::Float64': The average sparsity of coefficientvectors in Gcoefficientvectors.
• 'numberofpolynomials::Int64': Number of polynomials in G.
• 'numberofterms::Int64': Number of terms in O.
• 'degree::Float64': Average degree of polynomials in G.

Evaluates the transformation corresponding to the polynomials in V w.r.t. the functions in F and C

Arguments

• 'sets::SetsVCA': instance of SetsVCA.

Returns

• 'totalnumberofzeros::Int64': Sum of all zero entries in coefficientvectors in Vcoefficientvectors.
• 'totalnumberofentries::Int64': Total number of entries in coefficientvectors in Vcoefficientvectors.
• 'avgsparsity::Float64': The average sparsity of coefficientvectors in Vcoefficientvectors.
• 'numberofpolynomials::Int64': Number of polynomials in Vcoefficientvectors.
• 'numberofterms::Int64': Number of non-vanishing terms.
• 'degree::Float64': Average degree of polynomials in V.

Evaluates transformation corresponding to the polynomials in V.

Finds first non-zero entry in each column and returns a list of the indices. In case of a zero-column returns first index.

Finds last non-zero entry in each column and returns a list of the indices. In case of a zero-column returns last index.

Performs FindRangeNull (using SVD) for VCA. Reference: https://proceedings.mlr.press/v28/livni13.html

Arguments

• 'F::Matrix{Float64}': evaluation of F polynomials
• 'C::Matrix{Float64}': evaluation of C polynomials
• 'psi::Float64': vanishing parameter

Returns

• 'Vcoefficientvectors::Matrix{Float64}': Coefficient vectors of polynomials we append to V.
• 'Vevaluationvectors::Matrix{Float64}': Evaluation vectors of polynomials we append to V.
• 'Fcoefficientvectors::Matrix{Float64}': Coefficient vectors of polynomials we append to F.
• 'Fevaluationvectors::Matrix{Float64}': Evaluation vectors of polynomials we append to F.

Creates OAVI feature transformation fitted to X_train

Arguments

• 'X_train::Matrix{Float64}': training data
• 'max_degree::Int64': max degree of polynomials computed (default 10)
• 'psi::Float64': vanishing extent (default 0.1)
• 'epsilon::Float64': accuracy for convex optimizer (default 1.0e-7)
• 'tau::Union{Float64, Int64}': upper bound on norm of coefficient vector
• 'lambda::Float64': regularization parameter
• 'oracle::Union{String, <:Function}': string denoting which predefined constructor to use OR constructor function. (external constructor function MUST have 'data' and 'labels' as varargs)
• 'max_iters::Int64': max number of iterations in oracle
• 'inversehessianboost::String': whether or not to use IHB. Choose from "false", "weak" or "full".
• 'oracle_kwargs::Vector': Array containing keyword arguments for external constructor functions

Returns

• 'Xtraintransformed::Matrix{Float64}': transformed X_train
• 'sets::SetsOandG': instance of 'SetsOandG' keeping track of important sets

This function creates and applies a VCA transformation fitted to X.

Arguments

• 'X::Matrix{Float64}': data, stored row-wise
• 'psi::Float64': vanishing parameter
• 'max_degree::Int64': maximum degree to consider

Returns

• 'Xtraintransformed::Matrix{Float64}': X transformed according to transformation found by VCA
• 'sets_vca::SetsVCA': instance of SetsVCA containing relevant sets for VCA

finds unique columns in matrix x1 and returns only those columns in x1, as well as corresponding columns in x2.

Projects x onto the L1 Ball with radius 'radius'.

Reference: "Efficient Projections onto the ℓ1-Ball for Learning in High Dimensions", https://stanford.edu/~jduchi/projects/DuchiShSiCh08.pdf

Obtains orthogonal projections of vector projected onto vectors.

Prints the polynomials obtained through OAVI as a LaTeX string.

'digits' can be used to determine how many decimal places you want to round to. Terms with rounded coefficient values 0.0 are omitted and coefficients with value 1.0 are omitted.

'ret' can be used to return vector with poly strings, instead of printing the polynomials

purges each term in 'terms' that is divisible by at least one term 'purging_terms'

Arguments

• 'terms::Matrix{Int64}': Matrix with monomial terms as columns
• 'terms_evaluated::Matrix{Float64}': evaluations of 'terms' over data
• 'purging_terms::Matrix{Int64}': Matrix with purging terms as columns

Returns

• 'terms[:, inidces]::Matrix{Int64}': purged version of terms
• 'terms_evaluated[:, indices]::Matrix{Float64}': purged evaluations
• 'indices::Vector{Int64}': array with non-purging indices

reconstructs border for O_test

Given A, A.T.A and (A.T.A)^-1 efficiently compute B = [A, a], B.T.B and (B.T.B)^-1. Necessary for fast inverse hessian boosting.

updates C

updates F sets

updates G sets

updates O sets

updates V sets.

updates border sets

Appends polynomial with coefficient vector based on coefficientvector and term to Gcoefficient_vectors.

updates leading terms

updates permutations