Approximate Vanishing Ideal Computations at Scale
Authors: Elias Samuel Wirth
Hiroshi Kera
Sebastian Pokutta
Venue: ICLR 2023 poster (2023)
Keywords: approximate vanishing ideal
convex optimization
conditional gradients algorithms
Hessian matrix

Abstract: The vanishing ideal of a set of points $X = \{\mathbf{x}_1, \ldots, \mathbf{x}_m\}\subseteq \mathbb{R}^n$ is the set of polynomials that evaluate to $0$ over all points $\mathbf{x} \in X$ and admits an efficient representation by a finite subset of generators. In practice, to accommodate noise in the data, algorithms that construct generators of the approximate vanishing ideal are widely studied but their computational complexities remain expensive. In this paper, we scale up the oracle approximate vanishing ideal algorithm (OAVI), the only generator-constructing algorithm with known learning guarantees. We prove that the computational complexity of OAVI is not superlinear, as previously claimed, but linear in the number of samples $m$. In addition, we propose two modifications that accelerate OAVI's training time: Our analysis reveals that replacing the pairwise conditional gradients algorithm, one of the solvers used in OAVI, with the faster blended pairwise conditional gradients algorithm leads to an exponential speed-up in the number of features $n$. Finally, using a new inverse Hessian boosting approach, intermediate convex optimization problems can be solved almost instantly, improving OAVI's training time by multiple orders of magnitude in a variety of numerical experiments.

Published as a conference paper at ICLR 2023
APPROXIMATE VANISHING IDEAL COMPUTATIONS AT SCALE
Elias Wirth Institute of Mathematics
Hiroshi Kera
Graduate School of Engineering Chiba University
Berlin Institute of Technology
Berlin, Germany wirthemath. tu
Chiba, Japan kera hiroshi @gmail com
Sebastian Pokutta
Institute of Mathematics & Al in Society, Science, and Technology Berlin Institute of Technology & Zuse Institute Berlin Berlin, Germany
pokutta@zib.dde
ABSTRACT
The vanishing ideal of a set of points X (xI...., Xm] S R" is the set of polynomials that evaluate to 0 over all points x E X and admits an efficient rep- resentation by a finite subset of generators. In practice, to accommodate noise the data, algorithms that construct generators of the approximate vanishing ideal are widely studied but their computational complexities remain expensive. In this paper, we scale up the oracle approximate vanishing ideal algorithm (OAVI), algorithm with known learning guarantees. We
the only prove that the computational complexity of QAVI is not superlinear, as previously claimed, but linear in the number of samples m. In addition, we propose two mod- ifications that accelerate OAVI'S 's training time: Our analysis reveals that replacing the pairwise conditional gradients algorithm, one of the solvers used in OAVI, with the faster blended pairwise conditional gradients algorithm leads to an expo- nential speed-up up in the number of features n. Finally, using a new inverse Hessian boosting approach, intermediate convex optimization problems can be solved al- most instantly, improving OAVI's 's training time by multiple orders of magnitude in a variety of numerical experiments.
INTRODUCTION
High-quality features are essential for the success of machine-learning algorithms (Guyon & Elis- seeff, 2003) and as consequence, feature transformation and selection algorithms are important area of research (Kusiak, 2001; Van Der Maaten et al., 2009; Abdi & Williams, 2010; Paul et al., 2021: Manikandan & Abirami, 2021; Carderera al., 2021). A recently popularized technique for extracting nonlinear features from data is the concept of the vanishing ideal (Heldt et al., 2009; Livni al., 2013), which lies at the intersection of machine learning and computer algebra. Unlike ventional machine learning, which relies on manifold assumption. vanishing ideal computations are based on an algebraic set' assumption, for which powerful thcoretical guarantees are known (Vidal et al., 2005; Livni et al., 2013; Globerson et al., 2017). The core concept of vanishing ideal computations that any data set X (x1,.. ... Xm, C Rd can be described by its vanishing ideal, Ix = {g E P (xx) 0 for all x E X}. where P is the polynomial ring over IR in variables. De- spite Ix containing infinitely many polynomials, there exists finite number of generators of Ix. 91....,94 9h E Ix with E N, such that any polynomial h E Ix can be written as h = E gih,, where h4 E P for all i E (1, (1.....k) k} (Cox et al., 2013). Thus, the generators share any sample x E X as a common root, capture the nonlinear structure of the data, and succinctly represent the vanishing ideal Zx. Due to noise in empirical data, we are interested in constructing generators of
AA set X C R" is algehraic if it the set of common of finite of polynomials.

---

Published as a conference paper at ICLR 2023
the approximate vanishing ideal, the ideal generated by the set of polynomials that approximately evaluate to 0 for a E X and whose leading term coefficient is 1, see Definition 2.2. For classifica- tion tasks, constructed generators can, for example, be used to transform the features of the data set X S RD such that the data becomes linearly separable (Livni et al., 2013) and training a linear ker- nel support vector machine (SVM) (Suykens & Vandewalle, 1999) on the feature-transformee data results in excellent classification accuracy. Various algorithms for the construction of generators of the approximate vanishing ideal exist (Heldt et al., 2009; Fassino, 2010; Limbeck, 2013; Livni al., 2013: Iraji & Chitsaz, 2017; Kera & Hasegawa, 2020; Kera, 2022), but among them, the oracle approximate vanishing ideal algorithm (CAVI) (Wirth & Pokutta, 2022) is the only one capable of constructing sparse generators and admitting learning guarantees. More specifically, CGAVI (OAVI with Frunk- Wolfe algorithms (Frank & Wolfe, 1956), a.k.a. conditional gradients algorithms (CG) (Levitin & Polyak, 1966) as solver) exploits the sparsity-iduucing properties of CG to construct sparse generators and, thus, a robust and interpretable corresponding feature transformation. Fur- thermore, generators constructed with CGAVI vanish on out-sample data and the combined approach of transforming features with CGAVI for subsequently applied linear kernel SVM inherits the mar- gin bound of the SVM (Wirth & Pokutta, 2022). Despite OAVI's various appealing properties, the computational complexities of vanishing ideal algorithms for the construction of generators of the approximate vanishing ideal are superlinear in the number of samples m. With training times that increase at least cubically with m, vanishing ideal algorithms have yet to be applied to large-scale machine-leammnn leahming problems.
1.1 CONTRIBUTIONS
In this paper, we improve and study the scalability of OAVI.
Linear computational complexity in m. Up until now, the analysis of computational complexities of approximate vanishing ideal algorithms assumed that generators need to vanish exactly, which gave an overly pessimistic estimation of the computational cost. For OAVT, we exploit that genera- tors only have to vanish approximately and prove that the computational complexity of CAVI is not superlinear but linear in the number of samples m and polynomial in the number of features n. Solver improvements. OAVI repeatedly calls solver of quadratic convex optimization problems to construct generators. By replacing the pairwise conditional gradients algorithm (PCG) (Lacoste- Julien & Jaggi, 2015) with the faster blended pairwise conditional gradients algorithm (BPCG) (Tsuji et al., 2022), we improve the dependence of the time complexity of OAVI on the number of features in the data set by an exponential factor.
Inverse Hessian boosting (IHB), OAVI solves a series of quadratic convex optimization problems that differ only slightly and we can efficiently maintain and update the inverse of the corresponding Hessians. Inverse Hessian boosting (THB) then refers to the procedure of passing starting vector, computed with inverse Hessian information, close to the optimal solution to the convex solver used in OAVI. Empirically, IHB speeds up the training time of OAVI by multiple orders of magnitude. Large-scale numerical experiments. We perform numerical experiments on data sets of up to two million samples, highlighting that OAVI is an excellent large-scale feature transformation method.
1.2 RELATED WORK
The Buchberger- algorithm was the first method for constructing generators of the vanish- ing ideal (Möller & Buchberger, 1982). Its high susceptibility to noise was addressed by Heldt et al. (2009) with the approximate vanishing ideal algorithm (AVI), see also Fassino (2010); Lim- beck (2013). The latter introduced two algorithms that construct generators term by term instead of degree-wise such as AVI, the approximate Buchberger-Müller algorithm (ABM) and the border bases approximate Buchberger-Möüne MMöler algorithm. The aforementioned algorithms are monomial- aware, that is, they require an explicit ordering of terms and construct generators as linear combi- nations of monomials. However, monomial-awarenes is an unattractive property: Changing the order of the features changes the outputs of the algorithms. Monomial-agnostic approaches such as vanishing component analysis (VCA) (Livni et al., 2013) do not suffer from this shortcoming, as they construct generators linear combinations of polynomials. VCA found success in hand posture recognition, solution selection using genetic programming, principal variety analysis for nonlinear data modeling, and independent signal estimation for blind source separation (Zhao & Song, 2014; Kera & lba. 2016; Iraji & Chitsaz, 2017; Wang & Ohtsuki, 2018). The disadvantage of foregoing the term ordering is that VCA sometimes constructs multiple orders of magnitude more generators
2

---

Published as a conference paper at ICLR 2023
than monomial-awan algorithms (Wirth & Pokutta, 2022). Furthermore, VCA is susceptible to the spurious vanishing problem: Polynomials that do not capture the nonlinear structure of the data but whose coefficient vector entries are small become generators, and, conversely, polynomials that capture the data well but whose coefficient vector entries are large get treated as non-vanishing. The problem partially addressed by Kera & Hasegawa (2019; 2020; 2021).
PRELIMINARIES
Throughout, let k; m, N. We denote vectors in bold and let 0 R" denote the O-vector. Sets of polynomials are denoted by capital calligraphic letters. We denote the set of terms (or monomials) and the polynomial ring over R n variables by and P. respectively. For r 2 0, a polynomial
9 = Σi= City E P with c = (c..... CT)T is said to be r b-buudddd in the & norm if the l -nomm of its coefficient vector is bounded by that is, if ||l|| == |||||| S т. Given a polynomial g E P, let (cg(g) denote its degree. The sets polynomials in n variables of and up to degree d E N are denoted by Pa and P&d. respectively. Similarly, for set of polynomials 9 S P, let Ga = GnP, and Gga 9 E Pga. We often assume that X - fx,,..., xm} C [0, 1|". a form that can be realized, for example, via min-max feature scaling. Given polynomial g P and a set of polynomials G = {aI..... C P, define the evaluation vector of and evaluation matrix of G over X as g(X) (g(x)..... g( E RT and (X) (g) (X), (........ 9 (X)) Rm** respectively.
Further, define the mean squared error of over X as mse(g, X)= = |x (x) = m ll)(x))
OAVI sequentially processes terms according to a so-called term ordering, as is necessary for any monomial-aware algorithm. For ease of presentation, we restrict our analysis the degree- lexicographical ordering of terms (DegLex) (Cox et al., 2013), denoted by <a. For example, given the terms t, u, V E Th, DegLex works as follows: 1 <a t <o u <a V <a t2 <a t <o t v <o 2 <a u <a 22 <a + <a ..... where 1 denotes the constant-1 term. Given a set of terms O= [t,.... ................................ t ST, , the subscript indicates that ti Ka Ea tg.
Definition 2.1 (Leading term (coefficient)). g
ctt, E P with o R and t, E T for all .k. }} such that tú >o tú for all i E {I.....k) \ {i}. Then, ty and e are called leading term and leading term coefficient of g, denoted by lt(g) ty and Itc(g) cj. respectively.
i E [L.....k) b} and let j {l....,k
We thus define approximately vanishing polynomials via the mean squared error as follows.
Definition 2.2 (Approximately vanishing polynomial). Let X {XI..... ... X C RR" v 2 and
T 2 2. A polynomial E P is v-approximaatel vanishing (over X) if mso X) S vb. If also Ite(g) and || S T, then g is called (v,, 1, approximately vanishing (over X).
In the definition above, we fix the leading term coefficient of polynomials address the spurious vanishing problem, and the requirement that polynomials are -bounded in the -norr is necessary for the learning guarantees of OAVI to hold.
Definition 2.3 (Approximate vanishing ideal). Let X fx,,..,,,,,
xm C R", v 2 0, and 2 The (w), appprooxie vanishing ideal (over X), Ix is the ideal generated by all (v), 1, r)- approximately vanishing polynomials over X.
For * 0 and oo, it holds that - Ix. that is, the approximate vanishing ideal becomes the vanishing ideal. Finally, we introduce the generator-coonsraction problem addressed by OAVI.
Problem 2.4 (Setting). Let X = (xI...., xm, C R", v/ 2 0, and t 2 2. Construct a set of (v), 1, appprxiixiiy vanishing generators of I
Recall that for t, u E T, t divides (or is a divisor of) u, denoted by t u, if there exists U E T such that t 8 u. If does not divide u, we write t u. OAVI constructs generators of the approximate vanishing ideal of degree d E IN by checking whether terms of degree d are leading terms of an approximately vanishing generator. As explained in Wirth & Pokutta (2022), OAVI does not have to consider all terms of degree d but only those contained in the subset defined below.
Definition 2.5 (Border). Let O C T. The (degree-d) border O is defined as 0₂0 = {u E Ta te O Osa-1 for all /. Tsa-1 such that u).
3

---

Published as a conference paper at ICLR 2023
Algorithm 1:
Oracle approximate vanishing ideal algorithm (OAVI)
Input : data set = (xI...... ..m.................. C R" and parameters & 2 0 and r 2 2.
Output: set of polynomials g _ and a set of monomials O C T.
f- 1, }o 0 {1).. 9 f- 0
while 0₂O = {ui..... to + 0 do
for 1, I,..., 1 do
f |O| E N. A t ((X) Rmxt, b (X)) E RT", Py R
TT- 1T-1)
E argminyee
1 Ay + bll D call convex aptimization oracle
m
9 Ej=e Gjly + Uj
if Msmoogg X) S then
check whether 9 vanishes
9 + UU (g)
else
0= te410 (OU
11
end
end
13
d + d +1
14
end
ORACLE APPROXIMATE VANISHING IDEAL ALGORITHM (OAVI)
In this section, we recall the oracle approximate vanishing ideal algorithm (OAVI) (Wirth & Pokutta, 2022) in Algorithm method for solving Problem 2.4.
3.1 ALGORITIM OVERVIEW
OAVI takes as input data set set X _x Xm S R" vanishing parameter vb 2 0, and tolerance = 2 such that the constructed generators are r-bounded in the fnorm. From a high- level perspective, OAVI constructs a finite set of (v), 1, apprroxmtttll vanishing generators of the (apprrappo vanishing ideal I by solving series of constrained convex optimiza- tion problems. OAVI tracks the set of terms O C T such that there does not exist (v, 1, 7)- approximately vanishing generator of I with terms only in O and the set of generators g S P of I For every degree d 2 OAVI computes the border OgO Line 2. Then, in Lines 3-12, for every term u E O₂O, OAVI determines whether there exists a (v), 1, approxxmimtt vanish- ing generator of I with It(g) the constrained convex optimization problem in Line in Line 8. Otherwise, the term gets appended to O in Line 10. OAVI terminates when degree E N is reached such that 0₂0 = For ease of exposition, unless noted otherwise, we ignore that the optimization problem in Line 5 of OAVI is addressed only up certain accuracy 0. Throughout, we denote the output of OAVI by G and O, that is, (9, O) = OAVI v. T). We replace the first letter CAVI with the abbreviation corresponding optimization problem in Line 5. For example, OAVI with solver CG is referred to as CGAVI.
and other terms only in O via oracle access to solver of If such g exists, it gets appended to g
the solver used solve the
3.2 PREPROCESSING WITH OAVI IN A CLASSIFICATION PIPELINE
OAVI can be used as a feature transformation method for a subsequently applied linear kernel sup- port vector machine (SVM). Let X' C Rd and y (1...., k} be an input and output space, respec- tively. We are given a training sample S = {x11 V1)...., (xm: Wm)} E (X x y)m drawn i.i.d. from some unknown distribution D. Our task is to determine hypothesis h: X
with small generalization error IP (xx.))).D [x(x) * y). For each class i E (1....,Ad k), let X = (x, E X y) = i} C X = (xi,.... ) denote the subset of samples corresponding to class i and construct a set of (1b, 1, approxiaaayyll vanishing generators G' of the -.prroopiiii vanishing ideal I = OAVI(X', tb T). We combine the sets of generators corresponding
via OAVI, that is, to the different classes obtain g (g1.....99
U G which encapsulates the feature
4

---

Published as a conference paper at ICLR 2023
2.2
0.600
0,30
1.2
2.0
0,375
0.45
6.1
Thee
Tite
0:300
0,00
0.30
Number sumpplss
Number
sstpplss
Number comples
Nuntax sompliox
(a) Bank.
(b) Htru.
(c) Skin.
(d) Synthetic.
Figure I: Training time comparisons with fixed tb = 0.005, averaged over ten random runs with shaded standard deviations. On all data sets except skin, BPCGAVI is faster than PCGAVI.
transformation we are about to apply to data set X. As proposed in Livni et al. (2013), we transform the training sample X via the feature transformation
Xj + x (1g) (x;)l, ..., (x,))) E R
(FT)
for j = 1,...,m, The motivation behind this feature transformation is that polynomial g E g vanishes approximately over all over points x X X We then train a linear kernel SVM on the feature-transformee data = ((,,,9)),-. (Xm, ym)} with & ezreeuuaaiizttion to promote sparsity. e = 0, t = oo, and the underlying classes of S belong disjoint algebraic sets, then the different classes become lin- early separable in the feature space corresponding to transformation (FT) and perfect classification accuracy is achieved with the linear kernel SVM (Livni al., 2013).
X and (hopefully) attains values that are far from zero
3.3 SOLVING THE OPTIMIZATION PROBLEM IN LINE 5 OAVI
Setting co, the optimization problem in Line 5 becomes unconstrained and can, for example, be addressed with accelerated gradient descent (AGD) (Nesterov, 1983). If, however, T < oo, OAVI satisfies two generalization bounds. Indeed, assuming that the data is of the form X [0, 1]". the generators in G are guaranteed to also vanish on out-sample data. Furthermore, the combined approach of using generators obtained via OAVI to preprocess the data for subsequently applied linear kernel SVM inherits the margin bound of the SVM (Wirth & Pokutta, 2022).
OAVI AT SCALE
Here, we address the main shortcoming vanishing ideal algorithms: time, space, and evaluation complexities that depend superlinearly m, where m is the number of samples in the data set X
C RR. Recall the computational complexity of OAVI for xc.
O. == oc, and (G, 0) OAVI(X, T). Let TOraEle and SERACLE be the time and space complexities required to solve the convex optimization problem in Line 5 of OAVI, respectively. number model, the time and space complexities of OAVI are O([IG+
Theorem 4.1 (Complexity (Wirth & Pokutta, 2022)). Let X = (xi,....xX) xm) C
the real + (IG) 1O1)TaOl and ( + |Ol)m + Susacue), respectively. The evaluation vectors of all polynomials in g over set = Zz....., 2g) R" can be computed in time O((lg) 2
Under mild assumptions, Wirth & Pokutta (2022) proved that O[l) + |O) = O(m)), imply- ing that OAVI's computational complexity is superlinear in m. In this work, we improve OAVI's computational complexity both with tighter theoretical analysis and algorithmic modifications.
4.1 NUMBER-OF-SAMPLES--COO
BOUND ON |G] + |0|
For s > O, OAVI, ABM, AVI, and VCA construct approximately vanishing generators the (th, r)- approximate vanishing ideal. Despite being designed for the approximate setting (1) > 0), so far,
the analysis these algorithms was only conducted for the exact setting (v/ = 0). Below, we exploit that v in OAVI and obtain the first munber-ffsamplee-gnoott bound the size of
5

---

Published as a conference paper at ICLR 2023
1.0
1,5
0.4
088
Time ia scoeecs
Tipe la sccceess
Time Ee ecocplds
0.5
1lae
0.00
1022
0.0
0.2
0.1
0.0
000
1500
3000
10001
19000
100000
200000
115
1.0
Namber suuplox
Samber of sunglox
Nonber of sunplex
Number Semples x
(a) Bank.
(b) Htru.
Skin.
(d) Synthetic.
Figure 2: Training time comparisons with fixed v = 0.005, averaged over ten random runs with shaded standard deviations. CGAVI-IHB is faster than BPCGAVI-WIHB, which is faster than BPCGAVI.
pnnerattor-onstructtne algorithm's 's output. The result below also highlights the connection between the size of OAVI's output [ + | and the extent of vanishing vi: Large vé implies small [9] + |O|
and small & implies large [g] + |O|
Theorem 4.2 (Bound on |g] + JOD. Let X = fxi..... xm) S [0. vp E 10,1/ D
logg(())/ (og(())) 2 (3/2) and (g, CAVI(X, 1/ r). Then, OAVI terminates after having constructed generators of degree D. Thus, + 10| S (D)").
The proof of Theorem 4.2 presented in Appendix A. When TORACIE and SCRACLE are linear in m and polynomial in | the time and space complexities of OAVI are linear in and polynomial in n. Furthermore, the evaluation complexity OAVI is independent of m and polynomial in n.
4.2 BLENDED PAIRWISE CONDITIONAL GRADIENTS ALGORITHM (BPCG)
Wirth & Pokutta (2022) solved the optimization problem in Line 5 of OAVI with the pairwise con- ditional gradients algorithm (PCG). this section, we replace PCG with the blended pairwise condi- tional gradients algorithm (BPCG) (Tsuji et al., 2022), yielding an exponential improvement in time complexity of OAVI in the number of features n in the data set (xI..... x S 1)
Let P C R², l e N, be a polytope of diameter > O and pyramidal width w > 0, see Appendix D for details, and let f: R > IR be a μ-strongly convex and L-smooth function. PCG and BPCG address constrained convex optimization problems of the form
y" E argmin f(y).
(4.1)
With (P) denoting the set of vertices of P, the convergence rate of PCG for solving (4.1) is fyr) - f(y") < (f(yo) f(y"))e Pec:T" where yo E P is the starting point, y* is the opti- mal solution to (4.1), and Ppcs ano2/(4652()) vert(P)) + 1)) (Lacoste-Julien & Jaggi, 2015). The dependence of PCG's time complexity on |vrr( is due to swap steps, which shift weight from the away to the Frank-Wolfe vertex but do not lead to a lot of progress. Since the problem dimension is |O], which can be of similar order of magnitude as |9] + |O]. PCG can require number of iterations that is exponential in | + [0] to reach e-accuracy. BPCG does not per- form swap steps and its convergence rate is f(Y)) - -(y") S (f(yo) - f(y")) - where Peece 1/2 min {1/2, (1245522(4448) /(4L82)) (Tsuji et al., 2022). Thus, to reach c-aceuracy, BPCG re- quires a number of iterations that is only polynomial in | |O]. For the optimization problem in Line 5 of OAVI, A = O(X) E RRaxt and and L are the smallest and largest eigenvalues of matrix 2 ATA E R respectively. Since the pyramidal width of the ball of radius
is least (T 1)/v (Lemma D.I), ignoring dependencies on L, e, and T, and updating ATA and ATb explained the proof of Theorem C. the computational complexity of BPCGAVI (OAVI with solver BFCG) is as summarized below.
m
0.T 2, and (G.0) BPCGAVI(X, e) T). In the real number model, the time and space complexities of BPCGAVI are 0(([g) + 2 2m (19) jOly") and O(([g) + +10))n mm (19) (1))2,, respectively.
Corollary 4.3 (Complexity). Let X (xI...., Xm) C RD

---

Published as a conference paper at ICLR 2023
-A- CONI DIE
0.15
XIM
BOOA (IB)
0.443
0.00
0.23
Thpe
0.01
Tine
0.02
0.05
0.1
0.12
0.01
0.00
790
10001
7630
10020
1500
1003201
200000
0.5
1.0
1.5
20
Number aafempple
Number of semple
Namder sumples
Namier of suuggie x
(a) Bank.
(b) Htru.
(c) Skin.
(d) Synthetic.
Figure 3: Training time comparisons, averaged over ten random runs with shaded standard devia- tions. For small data sets, ABM and VCA, are faster than OAVI, but for synthetic, the training times of ABM and VCA scale worse than OAVI's, 's. See Appendix F.2 for details.
The results in Figure see Appendix F.1 for details, show that replacing PCG with BPCG in OAVI often speeds up the training time of OAVI. For the data set skin in Figure 1c, see Table for an overview of the data sets, it not fully understood why BPCGAVI is slower than PCGAVI.
4.3 INVERSE HESSIAN BOOSTING (IHB)
We introduce inverse Hessian boosting (IHB) to speed up the training time of CAVI by multiple orders of magnitudes by exploiting the structure the optimization problems solved in OAVI.
For ease of exposition, assume for now that T = oo, in which case we would use AGD to solve the problem in Line 5 of OAVI. Letting JO], A O(X) RT b (X) E RT and f(y)
1 |Ay + bll2. the optimization problem in Line 5 of OAVI takes the form E argminy yer f Then, the gradient and Hessian of f at y R are Vf(y) 2 AT + b) R and f²f(y)
m
ATA e RExt respectively. By construction, the columns of A O(X) are linearly independent. Hence, A ReXÉ is positive definite and invertible, f strongly convex, and the optimal solution to the optimization problem in Line of CAVI is unique. Further, for y E R we have V fy()) 0 and only if y = c. Instead of using AGD to construct an e-accurate solution to the optimization (ATA) AT R Since
m
problem in Line 5 of OAVI. we could compute the optimal solution matrix inversions are numerically unstable, relying on them directly would make OAVI less robust, and approximately vanishing polynomials might not be correctly detected. Instead, capitalize on the fact that the number of iterations of AGD to reach an 6-minimizer depends on the Euclidean distance between the starting vector and the optimal solution. IHB refers the procedure of passing Yo (ATA)-1A ATb E RR to AGD as a starting vector. Then, AGD often reaches e-accuracy in one iteration. In case A) is not computed correctly due to floating- poating-point errors, AGD still guarantees an c-accurate solution to the optimization problem. Thus, IHB can also be thought of as performing one iteration of Newton's 's method starting with iterate O, see, for example, Galántai (2000), and passing the resulting vector starting iterate to AGD. We stress that the dimension of see Theorem 4.2.
A E R is
IHB also works for oc, in which case we use CG variants to address the optimization problem Line 5 of OAVI that takes the form e E argminyep f(y), where P = (y E ||y|| S 1}. In the problematic case
> 1
(INF)
polynomial g = - C,ty+ uu constructed in Line 6 of CAVI might vanish approximately even though there exists P with l1(h) = us, lte(h) 1, non-leading terms only in O, and [/]]] that vanishes exactly over X. Thus, mse(h, X) 0 < & mse(y. X) and OAVI does not append to G and instead updates O + (OU [u,)), and A + (A, b) E (f+()+)), Since mso(h, X) 0, we just appended a linearly dependent column to A. making A rank-deficient, A) ill-defined, could select 7 adaptively, but this would invalidate the learning guarantees of OAVI that rely on being a constant. In practice we fix 2 (INF) holds for the first time, preserving the generalization bounds of OAVI. Through careful updates (ATA) the discussion in Appendix C.I implies the following complexity result for CGAVT-THR (CGAVI with THB).
and IHB no longer applicable. To address this problem,
and stop using THB

---

Published as a conference paper at ICLR 2023
Table 1: Overview of data sets, All data sets binary classification data sets and are retrieved from the UCI Machine Learning Repository (Dua & Graff, 2017) and additional references are provided.
Data set
Full name
# of samples
# of features
bank credit htru
banknote authentication
1.372
default of credit cards (Yeh & Lien, 2009)
30,000
22
HTRU2 (Lyon et al., 2016)
17,898
skin
skin (Bhatt & Dhall, 2010)
245,057
3
spam
spambase
4,601
57
synthetic
synthetic, see Appendix E
2,000,000
Corollary 4.4 (Complexity). Let X {xI...., .m) R" v 0. 2 2 large enough such that (INF) never holds, and (g. O) = CGAVI-IHB(X, v, T). Assuming CG terminates after constant number of iterations due to IHB, the time and space complexities of CGAVI-IHB are O((I))+ + 10))2m - + (19) + (01)3) and O([[g) + 10 (19) + + respectively.
In Appendix C.2, we introduce weak inverse Hessian boosting (WIHB), a variant of IHB that speeds up CGAVI variants while preserving details, we observe that CCAVI-IHE is faster than BPCGAVI-WIHH which is faster than BP CGAVI. In Figure 3, see Appendix F.2 for details, we compare the training times of OAVI-IHB to ABM and VCA. In Figure 3d, we observe that OAVI-IHB'S training time scales better than ABM's and VCA's 's.
inducing properties. In Figure see Appendix F.1 for
NUMERICAL EXPERIMENTS
Unless noted otherwise, the setup for the numerical experiments applies to all experiments in the paper. Experiments are implemented in PYTHON and performed on an Nvidia GeForce RTX 3080 GPU with 10GB RAM and an Intel Core i7 11700K 8x CPU at 3.60GHz with 64 GB RAM. Our code is publicly available GitHub.
We implement CAVI as in Algorithm 1 with convex solvers CG, PCG, BPCG, and AGD and refer to the resulting algorithms CGAVI, PCGAVI, BPCGAVI, and AGDAVI, respectively. Solvers run for up to 10,000 iterations. For the CG variants, we set 7 = 1, 000. The CG variants are run up accuracy e 0.01 & and terminated early when less than 0.0001 & progress is made in the difference between function values, when the coefficient vector of generator is constructed, or if we have guarantee that no coefficient vector of generator can be constructed. AGD is terminated early if less than 0.0001 1/ progress is made in the difference between function values for 20 iterations in a row or the coefficient vector of generator constructed. OAVI implemented with WIHB or THE is referred to as OAVI-WTHH HB or CAVT-THB, respectively. We implement ARM as in Limbeck (2013) but instead of applying the singular value decomposition (SVD) to the matrix corresponding to A = O(X) in CAVI, we apply the SVD to AT A in case this leads to faster training time and we employ the border as in Definition 2.5. We implement VCA as in Livni et al. (2013) but instead of applying the SVD the matrix corresponding to A O(X) in CAVI, we apply the SVD to AT A in case this leads to a faster training time. We implement polynomial kernel SVM with a one- versus-rest approach using the SCIKIT-LEARN software package (Pedregosa al., 2011) and the polynomial kernel SVM with 6-regularriztion up to tolerance 10-3 or for up to 10,000 iterations.
We preprocess with OAVI, ARM, and VCA for a linear kernel SVM in Section 3.2 and refer the combined approaches as OAVI*, ABM", and VCA", respectively. The linear kernel SVM is imple- mented using the SCIKIT-LEARN software package and run with ee-penalized squared hinge loss up to tolerance 10-4 or for up to 10,000 iterations. For OAVI*, ABM", and VCA", the hyperparameters are the vanishing tolerance & and the f.rreullarization coefficient of the linear kernel SVM. For the polynomial kernel SVM, the hyperparameters are the degree and the Ey-regllarization coefficient. Table and 3 contain overviews of the data sets and hyperparameter values, respectively.
5.1 EXPERIMENT: PERFORMANCE
We compare the performance CCAVI-IHB', EPCGAVI-WIHD* AGDAVI-IHB", ABM", VCA", and polynomial kernel SVM the data sets credit, htru, skin, and spam.
8

---

Published as a conference paper at ICLR 2023
Table Numerical results averaged over ten random 60%/40% train/test partitions with best results in bold. For approaches other than BPCAAVI-WIHE spar (g) < 0.01 and we omit the results.
Data sets
Algorithms
credit
htru
skin
spam
CGAVI-IHB'
18.08
2.09
0.23
6.69
AGDAVI-IHB"
18.08
2.09
0.23
6.69
Error
BPCGAVI-WIHB*
17.98
2.05
0.22
6.71
ABM"
18.36
2.09
0.43
6.67
VCA'
19.85
2.11
0.24
7.15
SVM
18.34
2.08
2.25
7.13
CGAVI-IHB"
1.3 x 10a
2.3 10'
1.0 102
8.3 x 10'
AGDAVI-IHB"
1.9 X 10a
2.8 X 10a
1.1 10a
3.1 X 10a
Time
BPCGAVI-WIHE*
3.7 x 103
8.0 x 10
5.6 X 10a
4.2 x 10a
ABM"
1.2 x 102
2.4 10a
10t
1.7 x 102
VCA*
2.4 10
6.2 X 10
1.4 10"
6.5 x 10
SVM
8.9 x 10a
4.1 X 10
7.1 x 10a
2.2 X 10
CGAVI-THB'
82.40
27.90
39.00
786.60
(SPAR) |9 + O
AGDAVI-IHB"
82.40
27.90
39.00
786.60
BPCGAVI-WIHB*
106.40
55.20
39.00
653.00
ABM'
51.40
28.70
19.30
261.00
VCA*
49.80
19.00
12.40
1766.40
BPCGAVI-WIHE*
0.67
0.52
0.03
0.71
Setup. We the hyperparameters on the training data using threefold cross-validation. We retrain on the entire training data set using the best combination of hyperparameters and evaluate the classification eтror on the test set and the hyperparameter optimization time. For the generator- constructing methods, we also compare [9] + (O), where |g| Σ, 1 |01 = Σ, 101s and
(g', O²) is the output of applying ceneratoo-conssrucctie algorithm to samples belonging to class i and the sparsity of the feature transformation U, G", which defined as
spar(g)
E 9t) ge) E [0.
(SPAR)
BEG
9EG
where for a polynomial = E5= + with It(g) = 1, 9r = k and 92 = Me = o e
{I....,k), k, that is, Je and are the number of non-leading and the number of zero coefficient vector entries of g, respectively. Results are averaged over ten random 60%/40% train/test partitions.
The results are presented in Table 2. DAVI* * admits excellent test-set classification ac- curacy. BPCGAVI-WIHB', in particular, admits the best test-set classification error on all data sets but one. Hyperparameter tuning for OAVI* is often slightly slower than for ABM and VCA". Since BPCGAVI-WIHE* does not employ IHB, the approach is always slower than CGAVI-IHE* and AGDAVI-IHB". For all data sets but credit and skin, the hyperparameter optimization time for the SVM is shorter than for the other approaches. On skin, since the training time of the polynomial ker- nel SVM is superlinear in m, the hyperparameter training for the polynomial kernel SVM is slower than for the other approaches. For data sets with few features n. the magnitude of | + |O] is often the smallest for V However, for spam, data set with n 57. as already pointed out by Kera & Hasegawa (2019) as the spurious vanishing problem, we observe VCA's 's tendency to create unnecessary generators. Finally, only BPCGAVI-WIHH" constructs sparse feature transformations, potentially explaining the excellent test-set classification accuracy of the approach.
Results.
In conclusion, the numerical results justify considering OAVI as the generator- constructing algo- rithm of choice, as it is the only approximate vanishing ideal algorithm with known learning guar- antees and, in practice, performs better than or similar to related approaches.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We would like to thank Gabor Braun for providing us with the main arguments for the proof of the lower bound on the pyramidal width of the 11-bal. This research was partially funded by the Deutsche Forschungsgemeinschatf (DFG, German Research Foundation) under Germany's 's Ex- cellence Strategy The Berlin Mathematics Research Center MATH* + (EXC-2046/1, project ID 390685689, BMS Stipend) and JST, ACT-X Grant Number JPMJAX200F, Japan.
REFERENCES
Hervé Abdi and Lynne Williams. Principal component analysis. Wiley Interdisciplinary Reviews: Computational Statisties, 2(4):433-459) 2010.
Maurice S Bartlett. An inverse matrix adjustment arising in discriminant analysis. The Annals of
Muthematical Statistics, 22(1):107-111, 1951.
Rajen Bhatt and Abhinav Dhall. Skin segmentation dataset. UCI Machine Learning Repository, 2010.
Alejandro Carderera, Sebastian Pokutta, Christof Schütte, and Martin Weiser. Cindy: Condi- tional gradient- based identification non-linear dynamies-noise-robust recovery. arXiv preprint arXiv:2101.02630, 2021.
David Cox, John Little, and Donal O'Shea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media, 2013.
Dheeru Dua and Casey Graff. UCI machine learning repository. 2017.
Claudia Fassino. Almost vanishing polynomials for sets of limited precision points. Journal of Symbolic Computation, 45(1):19-37, 2010.
Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2)955-100, 1956.
Aurel Galántai. The theory of newton's method. Journal of Computational and Applied Mathemat- ics, 124(1-2):25 -4, 2000.
Amir Globerson, Roi Livni, and Shai Shalev-Shwarde Effective semisupervised learning mani- folds. In Proceedings of the Conference on Learning Theory, pp. 978-1003, 2017.
Isabelle Guyon and André Elisseeff. An introduction to variable and feature selection. Journal of Machine Learning Research, 3(Mar): 2003.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192, 2007.
Daniel Heldt, Martin Kreuzer, Sebastian Pokutta, and Hennie Poulisse. Approximate computation of zero-dimensional polynomial ideals. Journal of Symbolic Computation, 44(11):1566-1591, 2009.
Reza Iraji and Hamidreza Chitsaz. Principal variety analysis. In Proceedings of the Conference on Robot Learming, pp. 97-108, 2017.
Hiroshi Kera. Border basis computation with suudient-weighte normalization. In Proceedings of the International Symposium Symbolic and Algebraic Computation, ISSAC'22, pp. 225-234, 2022.
Hiroshi Kera and Yoshihiko Hasegawa. Spurious vanishing problem in approximate vanishing ideal.
IEEE Access, 7:178961
2019.
Hiroshi Kera and Yoshihiko Hasegawa. Gradient boosts the approximate vanishing ideal. In Pro-
ceedings of the Conference Artificial Intelligence, number 04, pp. 4428 4435, 2020.
10

---

Published as a conference paper at ICLR 2023
Hiroshi Kera and Yoshihiko Hasegawa. Monomial-agnostic computation of vanishing ideals. arXiv preprint (xXiv:2101.0024:: 2021.
Hiroshi Kera and Hitoshi lba. Vanishing ideal genetic programming. IEEE Congress on Evolu- fionary Computation, pp. 5018-5025, 2016.
Andrew Kusiak. Feature transformation methods in data mining. IEEE Transactions Electronics Packaging Manufacturing. 24(3):114-221, 2001.
Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of Frank-Wolfe opti-
mization variants. In Proceedings of Advances in Neural Information Processing Systems, pp- 496-504, 2015.
Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 6(5):1-50, 1966.
Jan Limbeck. Computation of approximate border bases and applications. 2013.
Roi Livni, David Lehavi, Sagi Schein, Hila Nachliely, Shai Shalev-Shwartz. and Amir Glober- son. Vanishing component analysis. In Proceedings of the International Conference on Machine Learning, pp. 597-605. PMLR, 2013.
Robert J Lyon, BW Stappers, Sally Cooper, John Martin Brooke, and Joshua Knowles. Fifty years of pulsar candidate selection: from simple filters to a new principled real-time classification approach. Monthly Notices of the Royal Astronomical Society, 459 104-11024 1123, 2016.
Manikandan and S Abirami. Feature selection important: state-of-the-art methods and ap- plication domains of feature selection high-dimensional data. In Applications in Ubiquitous Computing, pp. 177-196. Springer, 2021.
Michael Möller and Bruno Buchberger. The construction of multivariate polynomials with preas-
signed zeros. In European Computer Algebra Conference, pp. 24-31. Springer, 1982.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of conver- gence ( In Doklady an USSR, volume 269, pp. 543-547, 1983.
Dipanjyoti Paul, Anushree Jain, Sriparna Saha, and Jimson Mathew. Multi-objective pso based online feature selection for multi-label classification. Knowledge-Based Systems, 222: 106966, 2021.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning in python. Journal of Machine Learning Research, 12:2825-2838 2011.
Javier Pena and Daniel Rodriguez. Polytope conditioning and linear convergence of the frank wolfe algorithm. Mathematics of Operations Research, 44(1):1-18, 2019.
Jack Sherman and Winifred Morrison. Adjustment of an inverse matrix corresponding to a change in one element of given matrix. The Annals of Mathematical Statistics, 21(1):224-127, 1950.
Johan AK Suykens and Joos Vandewalle. Least squares support vector machine classifiers. Neural Processing Letters, 93):2933300, 1999.
Kazuma K Tsuji, Ken ichiro Tanaka, and Sebastian Pokutta. Pairwise conditional gradients without swap steps and sparser kernel herding. In Proceedings of the International Conference on Machine Learning, pp. 21864-21881 21833. PMLR, 2022.
Laurens Van Der Maaten, Eric Postma, Jaap Van den Herik, et al. Dimensionality reduction: comparative. Journal Machine Learning Research, 10(66-71):13. 2009.
Rene Vidal, Yi Ma. and Shankar Sastry. Generalized principal component analysis (gpca). IEEE Transactions on Pattern Analysis and Machine Intelligence, 1915))):944-999)) 2005.
Lu Wang and Tomoaki Ohtsuki. Nonlinear blind source separation unifying vanishing component analysis and temporal structure. IEEE Access, 6:42837-42850, 2018.

---

Published as a conference paper at ICLR 2023
Elias Wirth and Sebastian Pokutta. Conditional gradients for the approximate vanishing ideal. arXiv preprint arXiv:2202.03349, 2022.
I-Cheng Yeh and Che-Hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2): 2473-2480, 2009.
Yan-Guo Zhao and Zhan Song. Hand posture recognition using approximate vanishing ideal gen- erators. Proceedings of the International Conference on Image Processing, pp. 1529. IEEE, 2014.
12

---

Published as a conference paper at ICLR 2023
A MISSING PROOFS
Proof of Theorem 4.2. Let X = fxi,..., Xm) C [0. 1 and let fi....,ty iu Ti be the degree-1 monomials. Suppose that during OAVI's execution, for some degree d E N, OAVI checks whether the term | 13 E 0₂O, where ~ー=1 aj d and aj N for all j E (l....,nk is the leading term of (v, 1, aapappppxxii vanishing generator with non-leading terms only in O. Let
2 2
h
II 1=1
(A.1)
where 1 denotes the constant-1 monomial, that is, 1(x) = 1 for all x E R". Note that ||h|] s (2) d
be constructed in Lines 5-6 of CAVI. Since u 0aO, for any term E T such that t and t & u, it holds that O and thus, h is polynomial with Itc(h) = 1, lt(h) = u, and other terms only in O. Under the assumption that the convex optimization oracle in OAVI is accurate, mse(h, X) 2 mse(g, X), where is the polynomial constructed during Lines and 6 of OAVI. Hence, proving that / vanishes approximately implies that vanishes approximately.
т, guaranteeing that
Note that for all X and E Ti, holds that t(x) [0, 1]. and, thus, [8(x) 1 S z.2 We obtain
mse(g, X) - (h, X)
[1xX)11 m
1 1xx) ty(x)
as
x
/=1
2
< max x j=l
II
ty(x)
2
4-
Since mse(g, X) < 4- < & is satisfied for d D
log($)
OAVI terminates after reaching
Tog(dj
degree D. Thus, the end of OAVI'S execution,
O
D4n
(D+n)
B BLENDED PAIRWISE CONDITIONAL GRADIENTS ALGORITHM (BPCG)
The blended pairwise conditional gradients algorithm (BPCG) (Tsuji et al., 2022) is presented in Algorithm 2.
C ADDITIONAL INFORMATION ON IHB
We discuss the computational complexity of IHB in Appendix C. and WIHB in Appendix C.2.
C.1 COMPUTATIONAL COMPLEXITY OF IHB
The main cost of THB is the inversion of the matrix A E RÉxE, which generally requires O(E2) elementary operations. Since OAVI solves series quadratic convex optimization problems that differ from each other only slightly, we can maintain and update (AT A)- using ( instead of ( elementary operations.
Theorem C.1 (THR update cost). Let A E Rmxt, MAERee case [b|| 0 and bt (TA(AA))- A ATb # bb
and b E RR be given. In
Ā = (A,b) E (++(++1)
ÄT E R((+1)x((+1)
(ĀT (((+1)x(++1) (C.1)
can be constructed in O(em (2) elementary operations.
13

---

Published as a conference paper at ICLR 2023
Algorithm 2: Blended pairwise conditional gradients algorithm (BPCG)
Input : A smooth and convex function f, a starting vertex Yo E vert(P). Output: point yr P.
S()) t {yu}
Xye <-1
(0) 0 for vert(P) {yo) Ayo
for f = O...., -- do (V((r)) 2)
a, argmax
away vertex D. local FW vertex
q: E argmin f(r),, 8.
W: E argmin (V/(),),
FW vertex
(V.(),, - vt) 2 (V)(y)): qe a.) then
d, < 9:- a " E argmin 7 fly: + 7d:)
10
1 -110 for E veri(P) \ fa, 4p
11
((+1) + Xa1 -
(++1) t Auc + +
13
14
else
d, - Wt - Yt
" E argmin, [(ye + 7d))
16
((+1) + (1 (1) for v E vert(P) \ {w,}
17
18
Aw. + (1 -
-1--7))am 7o) +
19
end
((++1) {u vert(P) ((+1)] 0}
21
Yet1 < yt + nd
22
end
Proof. Let B = ATA E RÊxE, B = ÄTÄ E (((+1)x((+1) == BB1 E Réxt and Ñ = B-1 (ÁT E ((++))x(--1) In ((m)) elementary operations, we can construct ATb E RC, bTb [|b||2 E R, and Ā = bA E Rmx(f+1) and in additional O((*) elementary operations, we can construct
=
A = ÄT =
B ATb
[bbl E [((++))((+1)
bTA
We can then compute operations. We write
Ñ B-1 (ĀT (ÁTÁ)-L (((+I)x((+)) in additional ((2) elementary
N n2 Ñ
e ((++))(++))
ng
where N1 E Rext igg RR, and ng E R. Then, it has to hold that
BN =
ATD
na
= I I ((++)x((++1)
AT
b
izy
where / is the identity matrix. Note that bT Añ
+ b 1. Thus,
1 bT Año
E R,
(C.2)
|b
which is well-defined due the assumption |/bl| > O. Since A is already computed, once i
is computed, the computation of ñg requires only additional (()) elementary operations. Similarly,
we have that
Büg
A'b 0 E R!
(C.3)
14

---

Published as a conference paper at ICLR 2023
Plugging (C.2) into (C.3), obtain (B
ATbbTA blij
Ang
.4 Thus, [
ATbbTA A
ATb
ng B
|
|b12
The existence of (B ATbb" A y follows from the Sherman-Morrison formula (Sherman & Mor- |
rison, 1950; Bartlett, 1951) and the assumption that bT ((ATA)--AAT + ||bll Then, again using the Therman-Morrison formula.
B ATb. AB
ATb
n2 B B-1+
|b] - bTAB-LATb
|
which be computed using additional ( elementary operations. Finally, we construct Ni, which is determined by BÑ1 + ATbū? = Réxé, Thus, N₂ B-1 A-A ReXx, which be computed in additional ((e2) elementary operations since B-1 R² is already computed. In summary, we require Offm + (²) elementary operations. Note that even if we do not
compute (ÁT ()=A)_ we still require O + e elementary operations.
In the remark below, we discuss the literature related IHB.
Remark C.2 (Work related IHB). The proof of Theorem C.1 is similar to the proof that the inverse of the Hessian can be updated efficiently in the online Newton algorithm (Hazan et al., 2007). Both proofs rely on the Sherman- CogrmannMMrrison formula (Sherman & Morrison, 1950; Bartlett, 1951). However, in our setting, the updates occur column-wise instead of row-wise. Updating (ATA)-1 column-wise for generator-construucingg algorithms was already discussed Limbeck (2013) using QR decompositions without addressing the numerical instability of inverse matrix updates.
Next, we prove that Theorem C.1 implies the improved computational complexity of CGAVI-THB in Corollary 4.4.
Proof of Corollary 4.4. Suppose that CGAVI-IHB is currently executing Lines 5-11 of Algorithm
for a particular term u, E OaO and recall the associated notations O). A = O(X) E RT b = u, (X), f(y) II + bll2, and P = {y E IR Ilyll S 1}. Then, the optimization problem in Line of Algorithm takes the form
C CE argmin f(y).
We first prove that the violation of any of the two assumptions of Theorem C.1 implies the exis- tence of (v/, 1, -ppprxxxxiyy vanishing generator g. We prove this claim by treating the two assumptions separately:
1. If |lb|l2 = 0, it holds that mse(u;, X) O. By the assumption that 2 2 is large enough to guarantee that (INF) never holds, CGAVI-IHR constructs a (v), 1, approxxmata van- ishing generator in Line 6.
2. bf A(AT
[bll it holds that f(-(ATA)-1ATT) 0. Thus, by the assump- tion that + 2 is large enough to guarantee that (INF) never holds, CGAVI-IHB constructs (v, apprrxxiaaay vanishing generator in Line 6.
Since an update of (ATA)-1 is necessary only if Line 10 is executed, that is, when there does not exist a (Φ), 1, approooiiiil vanishing generator g. we never have to update (AT (AT when the assumptions of Theorem C.I are violated. Thus, by Theorem C. we can always update A, ATA and (AT A) in O + (2) < O([ =10)) (lg) + [O])²) elementary operations using space ObEm + 82) < O((lg) + O )m + +[9]+
Then, since we run CG for a constant number of iterations, the time and space complexities of Lines 5-11 are ToRacLE O(((g [O])m + ((9)
2) and STRACIE O 00)mm + (Ig) + ())2), respectively.
Note that the time and space complexities in Comolarr 4.4 also hold for AGDAVT-THR with
15

---

Published as a conference paper at ICLR 2023
Algorithm 3: Blended pairwise conditional gradients approximate vanishing ideal algorithm
with weak inverse Hessian boosting (BPCGAVI-WIHB)
Input : A data set X = (xI..... X,n] R" and parameters v 2 E and 2. Output: set of polynomials 9 _ P and a set of monomials O C T.
+ 1, 0 = {ti Jo + {1] G f- 0
while 0₂0 {ui...... 1 # do
for 2 I..... k do
L - |O| E IN, A t ((X) E Rmxt b t (x(X) - Yo - (ATA) (ATA)-IATb ATb E Rt
E Rm, P (y E R |lyl11 ST-1)
Solve c E argminyee I + b up to tolerance e using CG with starting vector yo- > a non-sparse polynomial check whether vanishes Solve E argminyeP : 4y + bl2 up to tolerance c using BPCG and a vertex of P starting vector.
- bj=10tt + Uu
if Uss(gg S & then
10
h Ej=1dtt + uj
D a sparse polynomial check whether h vanishes
11
mse X) < & then
g + g {h}
13
else
g g {g}
15
end
16
else
O 1,, ( + (OU (
t441/
18
end
19
end
d d +
end
C.2 WEAK INVERSE HESSIAN BOOSTING (WIHB)
So far, have introduced IHB drastically speed-up training of AGDAVI and CGAVI. A draw- back of using CGAVI-IHB is that the initialization CG variants with a non-sparse initial vector such Yo (ATA)-IATH ATb leads to the construction of generally non-sparse generators. In this section, we explain how to combine the speed-up of THB with the sparsity-inducing properties of CG variants, referring the resulting technique as weak inverse Hessian boosting (WTHB). Specifi- cally, we present WIHB with BPCGAVI (OAVI with solver BPCG), referred to as BP BPCGAVI-WIHB in Algorithm 3.
The high-level idea of BPCGAVI-WIHB is to use IHB and vanilla CG to quickly check whether (vh, 1. apprxxxaatl vamishing generator exists. it does, then use BPCG to try and construct 1, ( approximately vanishing generator that is also sparse.
We proceed by giving detailed overview of BPOGAVI-WIHB. In Line 5 of BPCGAVI-RIHB, we construct yo- Then, in Line 6, we solve E argmin in Al bl2 up to tolerance using CG with starting vector Yo (ATA)-1 ATb. Since yo is well-educated guess for the solution to the constrained optimization problem argminger 1 |l + bll in Line 6, CG often runs for only very few iterations. The drawback of using the non-sparse Yo starting vector is that constructed Line and constructed Line are generally non-sparse. We alleviate the issue of non-sparsity of g in Lines 8-18. In Line 8, we first check whether g is (1/, 1, apppoxximiia vanishing generator of X. If does not vanish approximately, we know that there does not exist an approximately vanishing generator with leading term u; and we append u, to O in Line 17. If, however, msc(g, X) < v,, we solve the constrained convex optimization problem in Line again in Line 9 up to tolerance e using BPCG and vertex of the ball P as starting vector. This has two consequences:
n
The vector constructed Line 9 tends to be sparse, as corroborated by the results in Table 2.
16

---

Published as a conference paper at ICLR 2023
2. The execution of Line 9 tends to take longer than the execution of Line 6 since BPCG's starting vector is not necessarily close in Euclidean distance to the optimal solution.
(v/, 1, -)- approximately vanishing generator, we append the sparse h 9 in Line 12. If it happens that mse(g, X) S xb < mse(h, X), we append the non-sparse to G in Line 14. Following the discus- sion of Section 4.3, should (INF) ever hold, that is, |o -
Then, in Line 10, we construct the polynomial h, which tends to be sparse. If
can no longer proceed with BPCGAVI-WIHE as can longer guarantee that the inverse of A A exists. In that case, we proceed with vanilla BPCGAVI for all terms remaining the current and upcoming borders.
The discussion above illustrates that SPCGAVI-WIHH solves argmin yer 1, ll + b with BPCG [g] times as opposed to BP BPCGAVI, which solves argminye |l bll with BPCG [ O times. Thus, BPCCAVI WIIHB combines the of THB without any of THB's drawbacks. The speed-up of BPCGAVI-WI compared to BPCGAVI evident from the numerical experiments in Figure 2 and the results of Table indicate that the sparsity-inducing properties of BPCG are successfully exploited.
properties BPCG with the speed-up
D PYRAMIDAL WIDTH OF THE L -BAL
Pena & Rodriguez (2019) showed that the pyramidal width of the b--all of radius т, that is, P = (x Ré ||x|| I C R is given by
min w Fefaors (P),0FFPP
dist (F, (ver(ve) F)),
where, for a polytope C Re, faces (P) denotes the set of faces of P and vert(P) denotes the set of vertices of P. for set F RR, conv(F") is the convex hull of F, and for two disjoint sets F,G S R dist (F, G) is the Euclidean distance between and G.
Lemma D.1 (Pyramidal width of the (-ball), The pyramidal width of the b--ball of radius T, that is, {x R ||||| S T) S R,, is lower bounded by Z VI-I"
Proof. Let ( E denote the ith unit vector. Note that a non-trivial face of P conv (ore() ..... t R that is not P itself cannot contain both Te( and ( for any i [1,...,f). Thus, due to symmetry, we can assume that any non-trivial face of P that is not P itself is of the form = conv((re!! 7e(k)) for some k: E (1,...,, 1}. Then,
G = conv(vert(P)) F) = conv (1) ..... -ee (k) tre (k+1) ..... (Te
We have that
dist (F,
min Uc F.G
|| - w1|2
min uc F.EG
(w: - u;)2 +
j 1++
min F.GG
(w: - 223)
since 0f 20 all j fk + 1....,.}
min ueF
since 8; 5 uy for all i {1,....
k
Since /
22
F is minimized for k E (l...., 1} as large possible, it follows that 2 -
17

---

Published as a conference paper at ICLR 2023
Table Hyperparameter ranges for numerical experiments.
Hyperparameters
Values
V
0.1, 0.05, 0.01, 0.005, 0.001, 0.0005, 0.0001
Regularization coefficient for SVMs
0.1, 10
Degree for polynomial kernel SVM
1, 1,
E THE SYNTHETIC DATA SET
The synthetic data set consists of three features and contains two different classes. The samples x that belong to the first class generated such that they satisfy the equation
o + 0.01x + + -1
and samples that belong the second class are generated such that they satisfy the equation
+ 2 1.3 0.
The samples perturbed with additive Gaussian noise with mean 0 and standard deviation 0.05.
F ADDITIONAL NUMERICAL EXPERIMENTS
In this section, we provide details for the numerical experiments conducted in Figures 1, 2, and 3.
F.1 EXPERIMENT: SPEEDING CGAVI
We compare the training times of PCGAVI, BPCGAVI, BPCGAVI-WIHB, and CGAVI-IHB on the data sets bank, htru, skin, and synthetic.
Setup. For single run, we randomly split the data into subsets of varying sizes. Then, for fixed vi = 0.005, we run the generator-construccinng algorithms on subsets of the full data set of varying sizes and plot the training times, which are the times required run PCCAVI, BP CGAVI, BPC BPCGAVI-WIAB, and CGAVI-IHB once for each class. The results are averaged over ten random runs and standard deviations are shaded Figures and 2.
Results. The results are presented in Figures and 2. In Figure 1, we observe that the training times for BPCGAVI are often shorter than for PCGAVI, except for the skin data set. In Figure 2, we observe that THB not only leads to theoretically better training times but also speeds up training in practice: CGAVI-IHB always faster than BPCGAVI. Furthermore, WIHB indeed the best of both worlds: BPCGAVI-WIH is always faster than BPCGAVI but preserves the sparsity-inducing properties of BPCG. The latter can also be seen in Table 2, where BPCGAVI-WIHB* the only algorithmic approach that constructs sparse generators.
F.2 EXPERIMENT: SCALABILITY COMPARISON
We compare the training times of CGAVI-THP, AGD-THB, ABM, and VCA on the data sets bank, htru, skin, and synthetic.
Setup. For single run, at most 10,000 samples of the data set, we tune the hyperparameters of generator-constructin algorithms OAVI, ABM, and VCA and a subsequently applied linear kernel SVM using threefold cross-validation. Then, using the determined hyperparameters. we only the
algorithms on subsets the full data set of varying sizes and plot the training times, which the times required to CGAVI-IHB, ACD-IHB, ABM, and VCA once for each class. The results are averaged over ten random runs and standard deviations are shaded in Figure 3.
18

---

Published as a conference paper at ICLR 2023
Results. The results presented in Figure 3. For small data sets, observe that ABM and VCA are faster than OAVI. However, when the number of samples in the data set is large, as in the syn- thetic data set, OAVI can be trained faster than ABM and VCA. AGDAVI-IHE is slower than CGAVI- THE because AGD cannot use the Frank-Wolfe gap as an early termination criterion to quickly decide that solution close enough the optimum is reached.
19


Reviews:
[{"review_id": "V8_u0_rqxU", "reviewer": "Reviewer_thxT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper extends the recent spur of research on VCA. In particular, it provides theoretical properties on the computational complexity of OAVI by utilizing the fact that the ideals must only vanish approximately and not exactly and improve the training time by clever tricks in the optimization.", "summary_of_the_review": "The paper tackles a relevant problem and makes progress both from a theoretical and from a practical perspective. The main insights could be better highlighted in the paper though. \nMoreover, the experiments are well-designed and correct but focus on too many 'easy' problems that do not reveal the capabilities of the proposed approaches well enough.", "strength_and_weaknesses": "Strengths:\n* VCA is an intuitive and promising concept that suffers from some limitations in practice. This paper makes an important contribution to approximate versions thereof (namely OAVI) in that it shows that the complexity is actually linear in the number of samples (and not superlinear as believed hitherto)\n* The paper further proposes practical improvements (PCG and BPCG) and inverse Hessian boosting for the optimization steps involved.\n* The contributions are well-explained and comprehensible and related to prior work\n\nWeaknesses:\n* The empirical evaluation shows a slight benefit of the proposed method; yet, for many experiments, the advantages in comparison to the classical VCA algorithm are less clear. My experiences were that VCA suffers particularly from sample-complexity whenever higher order polynomials are required (because of the large amount of generators that might be generated). This alligns well with the experiments in Figure 3 and suggests that the benefit of the proposed method becomes relevant only for more complex problems. I am afraid though that the experiments performed are not sufficient for making a particularly strong point for the OAVI type algorithms. I think that including more complex datasets (similar to spam) would really highlight the benefits.\n* The proof of Theorem 4.2 (a crucial piece of the paper) relies on the assumption that the oracle in OAVI is accurate. This seems to be a relative hand waving argument and -- at least for me -- it is not obvious if or under which conditions this is the case\n* The paper has a strong theoretical flavor. Yet, the most important contributions are completely hidden in the appendix. At the very least it would be desirable to have a brief summary of the proofs in the main part of the paper and to link to the respective proofs. For example, found it unnecessary tedious to look through the whole appendix for the proof of Th 4.2 without any pointer (only to finally find it under \"missing proofs\").", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SpBNhZDYvY", "reviewer": "Reviewer_qggK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a modified version of the OAVI algorithm for computing the generators of the set of polynomials who has a given dataset as roots - called the ideal. They show theoretically that their proposed modified algorithm yields significant savings in computational complexity. They then use these ideals to solve a classification task and show good test set performance. ", "summary_of_the_review": "I am not an expert in this field and my limited understanding based on reading the paper is that it seems to be a worthy publication given the experimental results. \n\nAfter rebuttal: \n\nThank you for your responses and clarifications. I strongly suggest the authors to write their modified algorithm explicitly in a separate algorithmic environment. After a closer look, I found the first paragraph of page 15 (in appendix) to appreciate the steps they had to take to accommodate for the change they did to line 5's optimization problem. It will greatly help the readers to compare with the existing work. Since there is no option of 7 as a score, and I cannot justify an 8 in terms of novelty and impact (no comparison with other classifiers in the experiments), I will keep my score of 6 (weak accept). ", "strength_and_weaknesses": "The algorithm seems to require a lot of hand-holding and might be hard to tune in practice. For example, the numerical instabilities that come with matrix inversion need to be handled carefully, as pointed out by the authors. \n\nExperimental results seem impressive in general, but it would be good to understand why the method suffers in one particular dataset. \n\nExperiments in section 5 do not seem to report runtime results unless I am missing them. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GU_dDIiPMbQ", "reviewer": "Reviewer_298L", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The key contribution of the paper is providing a faster algorithm (with improved dimension dependence) for computing generators of the approximate vanishing ideal of a set of points. To this end, it provides (1) a novel analysis of an existing algorithm for this purpose (\"OAVI\" by Wirth and Pokutta), and (2) a simple modification to accelerate OAVI. The notion of vanishing ideals is used as a core technique in several classical machine learning tasks like feature selection and transformation. Efficient algorithms for this subroutine are, therefore, a problem of clear interest to ICLR. \n\n", "summary_of_the_review": "My preliminary review is, unfortunately, to reject the paper: I believe the problem studied is important, and I am ready to believe the (theoretical) claims made, but I think there is plenty of room for improvement in the clarity. I am, however, happy to raise my score and change my opinion if the authors can submit a rebuttal clarifying notation and providing intuition for the main proof. \n\n----- AFTER THE REBUTTAL PHASE --- \n\nI am convinced of the importance of the paper's contributions and vote to accept the paper. I do strongly recommend that the authors incorporate into this version the following (1) a plain description (in words) of what the steps in the algorithm are doing, and (2) intuition for why their new methods improve upon the prior analysis (i.e., the explanations they provided in the rebuttal). Doing so would significantly increase readability. \n\n", "strength_and_weaknesses": "Strength: The scalability of an existing algorithm for an important problem \n\nWeakness: \n\n1. I am not sure how standard the notation used in the paper is (I wasn't familiar with it), and the description in the Preliminaries section was not enough for me to clearly follow the details. For instance, the notion of degree-lexicographical term ordering could be motivated better; I found the notation too succinct for my taste. I think this could be rectified by providing a working example for the reader. Along the same lines, since the paper builds heavily upon the OAVI algorithm and its notation, it might be useful to the reader to better motivate all the key concepts therein. \n\n2. The paper could provide some intuition for the proof of Theorem 4.2, which shows the runtime improvement: What exactly is the analysis doing differently from that of Wirth and Pokutta? What step, exactly, makes the prior work's analysis sub-optimal? I believe answering these questions would make the paper more insightful and the concepts more broadly applicable.  \n\n------ AFTER THE REBUTTAL PHASE ---- \n\nThe above weaknesses have been adequately addressed. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster