Cauchy-Schwarz Regularizers
Authors: Sueda Taner
Ziyi Wang
Christoph Studer
Venue: ICLR 2025 Poster (2025)
Keywords: Regularizer
optimization
discretization
quantization
Primary area: optimization
TL;DR: We propose a new family of regularization functions that can be used to discretize vectors.

Abstract: We introduce a novel class of regularization functions, called Cauchy–Schwarz (CS) regularizers, which can be designed to induce a wide range of properties in solution vectors of optimization problems. To demonstrate the versatility of CS regularizers, we derive regularization functions that promote discrete-valued vectors, eigenvectors of a given matrix, and orthogonal matrices. The resulting CS regularizers are simple, differentiable, and can be free of spurious stationary points, making them suitable for gradient-based solvers and large-scale optimization problems. In addition, CS regularizers automatically adapt to the appropriate scale, which is, for example, beneficial when discretizing the weights of neural networks. To demonstrate the efficacy of CS regularizers, we provide results for solving underdetermined systems of linear equations and weight quantization in neural networks. Furthermore, we discuss specializations, variations, and generalizations, which lead to an even broader class of new and possibly more powerful regularizers.

Published as a conference paper at ICLR 2025
CAUCHY-SCHWARZ REGULARIZERS
Sueda Taner
Ziyi Wang
ETH Zurich, Switzerland
ETH Zurich, Switzerland zi ziywangestudent.cm .ch
taners@ is s.ssees ee. ethz.
Christoph Studer
ETH Zurich, Switzerland studer@ethz
ABSTRACT
We introduce novel class of regularization functions, called Cauchy-SShware (CS) regularizers, which can designed to induce a wide range of properties solution vectors of optimization problems. To demonstrate the versatility of CS regularizers, we derive regularization functions that promote discrete-valued vectors, eigenvec- of given matrix, and orthogonal matrices. The resulting CS regularizers are simple, differentiable, and can be free of spurious stationary points, making them suitable for gradient-based solvers and large-scale optimization problems. In addition, CS regularizers automatically adapt to the appropriate scale, which is, for example, beneficial when discretizing the weights of neural networks. To demonstrate the efficacy of CS regularizers, provide results for solving under- determined systems of linear equations and weight quantization neural networks. Furthermore, we discuss specializations, variations, and generalizations, which lead to an even broader class of new and possibly more powerful regularizers.
INTRODUCTION
We focus on the design of novel regularization functions é: N + Rz0 that promote certain pre-defined properties on the solution vector(s) R.N of regularized optimization problems
x arg min f(x) Xl(x).
XER
where f: RV + R is an objective function and À E Rz0 a regularization parameter. One instance of such optimization problem arises in the binarization of neural-network weights, where the solution(s) of are the network's weights that should be binary-valued & E {-a,+a +a) but with the appropriate scale a l automatically chosen by the regularizer-the scale can then be absorbed into the activation function.
1.1 CONTRIBUTIONS
We propose Cauchy-Schwarz (CS) regularizers, novel class of regularization functions that can be designed to impose wide range of properties. We derive concrete examples of CS regularization functions that promote discrete-valued vectors (e.g.. binary- and ternary-valued vectors), eigenvectors of given matrix, and matrices with orthogonal columns. The resulting regularizers are (i) simple, (ii) automatically determine the appropriate scale, (iii) often free of any spurious stationary points, and (iv) differentiable, which enables the use of (stochastic) gradient- make them suitable to be used in large-scale optimization problems. In addition, we discuss variety of specializations, variations, and generalizations, which allow for the design an even broader class of new and possibly more powerful regularization functions. Finally, we showcase the efficacy and versatility of CS regularizers for solving underdetermined systems linear equations and neural network weight binarization and ternarization. All proofs and additional experimental results relegated to the appendices in the supplementary material. The code for our numerical experiments is available under https:: /tt:::///ttttt Saapa//II-Grro/SS..S.
numerical solvers that
ari zers

---

Published as a conference paper at ICLR 2025
1.2 NOTATION
Column vectors and matrices are written in boldface lowercase and uppercase letters, respectively, The entries of vector E RR- are [x]n In. n 1, I.... ., N, and transposition is x² The N- dimensional all-zeros vector is Oy, and the all-ones vector Iv: we omit the dimension N it is clear from the context. The inner product between the vectors x, y IN is (x. = x"y, and linear dependence is denoted by
x~y 3(a1, 02) E {2\((0,0)) a1x a2y.
For p 2 1, the p-norm of vector x E RRN is ||I|| - CE I.n p)1// and we will frequently use the shorthand notation [x]] - Σn Th (note the absence of absolute values). The entry on the with row and kth column of matrix X is Xn,s, the Frobenius norm is ||]]|e and columnwise vectorization is vec(X). The N x N identity matrix is Ly and the M x N all-zero matrix is 0 0M N
1.3 RELEVANT PRIOR ART
Semidefinite relaxation (SDR) can be used for solving optimization problems with binary-valued solutions (Luo et al. 2010). Since SDR requires lifting (i.e., increasing the dimension of the original problem size), solving such problems quickly results in prohibitive complexity, even for moderate- sized problems. As remedy, non-lifting-basse
SDR approximations were proposed in (Shah et al., 2016 Castañeda et al. 2017). These methods utilize biconvex relaxation that scales better to larger optimization problems. Convex non non-lifting- based approaches were also proposed for recovering binary-valued solutions from linear measurements using -norm regularization (Mangasarian & Rechi 2011). In contrast such methods, the proposed CS regularizers are (i) differentiable, which enables their use together with differentiable objective functions and any (stochastic) gradient-based numerical solver, and (ii) can be specialized to impose a wider range of different structures.
Vector discretization is widely used for neural network parameter quantization (Hubara et al. 201 8). Regularization-free approaches, e-g., the method from Rastegari et (2016), perform neural network binarization by simply quantizing the weights and adapting their scale to their average absolute value. Approaches that utilize projections onto discrete sets within gradient-descent--assee methods have been proposed in Hou et al. (2016); [Lng et al. (2018). In contrast, the proposed CS regularizers are differentiable and automatically adapt their scale to the appropriate magnitude of the solution vectors.
The prior art describes numerous vector discretization methods that rely on regularization functions. The methods in Hung et al. (2015]; TTag et al.
(201)); Wess et al. (2018); Bai et al. (2019); Darabi
et al.] (2019); Choi et al. (2020): Yang et al. 202T): Razani et al. (2021) Xuu et al. (2023) use
regularization functions related to the form E(x, 3) Em=1 (1 3)² for N N-dimensional vectors
N and either fix the magnitude 8 (e.g.. 8 = 1) or learn this additional parameter during gradient descent. Another strain regularization functions that utilizes trigonometric functions related
to the form (x,3) ()) = ΣM 1 sin 2 (BTz,) have been proposed in Naumov et al. (2018); Elthakeb et al. (2020); Solodskikh et al. (2022). In contrast to all of the above regularization functions, the proposed CS regularizers (i) do not introduce additional trainable parameters while still being able to
automatically adapt their scale to the vectors' magnitude and (ii) can be designed to promote a wider range of structures. Furthermore, the proposed CS regularizers include the regularization functions of Tang ct al. (2017); Darabi et al. (2019) as a special case; see App. B.3
The recovery of matrices with orthogonal columns finds, for example, use in the orthogonal Procrustes problem: X arg minx |AAA- B/|: subject X Ix for given matrices A and B. closed-form solution to this problem is given by X UV where U and V are the left- and right-singular matrices, respectively, of the matrix BAT (Schönemann 1966). Notably, this formulation constrains the columns of X to be orthonormal. A more general problem that relaxes this constraint to orthogonal columns with arbitrary norms was introduced in Everson (1998) along
'ome methods, e.g., Darabi et al. (2019). use non-differreniiabl regularizers with ||..|| O instead of
( 3)2. while others, e.g.. Xu al. (2023 use regularizers of the form ?||x sign(x)) and introduce additional scaling factors.
'The method in Naumov et al. 2018 fixes the scale, while Elthakeb et al. 2020) utilizes trainable parameter; the regularizer in Solodskikh et al. (022) introduces an additional differentiable regularizer that imposes finite range.
2

---

Published as a conference paper at ICLR 2025
with iterative solution algorithms. In contrast to these approaches, CS regularizers can be used to solve Procrustes problems for matrices with orthogonal columns of arbitrary scale, without relying on matrix decomposition methods, such as the singular value, polar, or QR decomposition.
Promoting cigenvectors matrix is useful in applications where aligning a vector with these eigen- vectors is desirable. For example, in principal component analysis (Jolliffe) (002). data is projected onto the principal eigenvectors for dimensionality reduction. Encouraging this alignment can aid feature selection and thus improve dimensionality reduction. In this context, CS regularizers offer an advantage by promoting eigenvectors without explicitly computing eigenvalues or eigenvectors.
An instance of CS regularizer was proposed in Ehrhardt & Arridge 20144,, which is regularization function based on the gradients of two vector-valued functions to measure how far these functions are from being parallel. contrast, we present general framework for designing a broad class of CS regularizers, encompassing the one from Ehrhardt & Arridge (2014) as special case.
We finally note that the CS divergence (Principe) 2010) was used as a regularizer for improving variational autoencoders in Tran et al. (2022) and for promoting fairness in machine learning models Li et al. (2025). contrast, we use the CS inequality (Steele) (004) to design new regularization functions that can amo-- many other structures-be used to promote discrete-valuee vectors (e.g.. binary or ternary), eigenvectors to given matrix, and matrices with orthogonal columns.
2 CAUCHY-SCHWARZ REGULARIZERS
In this section, we introduce the general recipe for deriving CS regularizers. We then use this recipe to design specific CS regularization functions that promote discrete-valued (e.g.. binary and ternary) vectors, eigenvectors a given matrix, and matrices with orthogonal columns.
2.1
THE RECIPE
The following result is immediate consequence of the CS inequality (Steele 2004) and provides recipe for the design of a wide range of regularization functions; short proof is provided in App. A.]
Proposition 1. Fix two vector-valued fuctorvvaluedduunctioos functions g, h RN + RM and define the set
X { g(x) ~ h(x)}-
(3)
Then, the nonnegative regularization function
{(x) e g(x) (g(x),, h(x)))
(4)
zero if and only (iff) x X.
We call regularization functions derived from Proposition I CS regularizers. While CS regularizers are guaranteed to be (i) nonnegative and (ii) zero iff x E X, it is also desirable for maddient-based numerical solvers that these regularizers do not exhibit any spurious stationary points.
Definition 1. A spurious stationary point is a vector & X for which V((x) 0.
Note that functions that do not have any spurious stationary points are also known as invex (Ben-Israel & Mond 1986). In other words, all stationary points of invex functions are also global minima; this property can be useful to develop problem-specifie algorithms and to analyze their convergence (see, e.g., Barik Barik et al. (2023): Pinilla al. (2022) and the references therein).
Whether or not CS regularizer has spurious stationary points depends on the specific choice of the two functions g and h. Nonetheless, even a CS regularizer has spurious stationary points, it may still accomplish the desired goal. We conclude by noting that any vector x for which g(x) = 0 or h(x) will minimize (4p.
The following result will be useful below when we analyze properties of specific CS regularizers; short proof given App.
Lemma 1. Fix two vector-valued functions g, h . RRM. Then, the following equalities hold:
((x) = llg(x))l3 min [18g(x) h(x) 112 = [|b(x)]] min
|lg(x) (lh(x))13
(5)
BER
BER
3

---

Published as a conference paper at ICLR 2025
Lemma] | will be used to highlight the important auto-scale property CS regularizers, since setting to its optimal value in (5) leads exactly to the regularization function in (4), as the optimization problem in 3 is continuous, quadratic, and has closed-form solution.
2.2 RECOVERING DISCRETE- VALUED VECTORS
From Proposition] I we can derive a range of differentiable CS regularizers that, when minimized, promote discrete-valued vectors. This can be accomplished by using entry-wise polynomials for the functions g and h. We next show three concrete and practically useful examples.
2.2.1 SYMMETRIC BINARY
Define g(x) A [a. 22y" and h(x) A 1x. Then, Proposition yields the following CS regularizer that promotes symmetric binary-valued vectors; App. A.3 for the derivation. Regularizer (Symmetric Binary). Let x E IR- and define
(xin(X) - -[x]*- ([x]))²
(6)
Then, the nonnegative function (6) is only zero for symmetric binary-valued vectors, iee, iff x E aaa,aatt +a} for any E R. Furthermore, (x) does not have any spurious stationary points.
To gain insight into Regularizer we invoke Lemma obtain
Epin (x) = N min HER
Σn ((x, (B)(I, + vB))²
This equivalence implies that, for given vector x, Regularizer is the right-hand-side total square error in (7). but with optimally chosen scale & vB; this is the auto-scale property of CS regularizers. In other words, the CS regularizer implicitly and automatically adapts its scale a to the scale of every argument x. Furthermore, this CS regularizer is zero iff {-a, ) for some
R, only In = +a or = aa for n = 1,..., .N allows the right-hand hand-side of to be zero.
We showcase the efficacy of foin for the recovery of binary-valued solutions in Section 3.1 and compare its advantages to existing binarizing regularizers (cf. Section [.3). such as being differentiable, scale- adaptive, and free of additional optimization parameters, App. C.1
2.2.2 ONE-SIDED BINARY
Define g(x) [af II and h(x) [fI...., INI". Then, Proposition yields the following CS regularizer that promotes one-sided binary-valued vectors; see App. A.4 for the derivation. Regularizer 2 (One-Sided Binary). Let R.N and define
(omb(x) [x] -(x]x))
(8)
Then, the nonnegative function in 8 is only zero for one-sided binary-valued vectors, i.e., iff x a) for any a E Furthermore, lust(x) dues not have any spurious stationary points.
To gain insight into Regularizer 2 we invoke Lemma Cemmaaanne and obtain
Los (x) = [x]]
min ΣM BER
1 (Ix (xn - =))
Once again, we observe this CS regularizer's auto-scale property and see that only vectors of the form {0,a)* for some E E minimize (9).
2.2.3 SYMMETRIC TERNARY
Define g(x) [of I and hxx) CS regularizer that promotes symmetric teruary-valued vectors; see App. A.5 for the derivation. Regularizer 3 (Symmetric Ternary). Let x E NN and define
INJ" Then, Proposition yields the following
(x)(x) |x| ([x]
(10)
Then, the nonnegative function in (70) only zero for symmetric ternary-valued vectors, i.e. iff {-a,00 0, +a) N for any a R. Furthermore, (x) does not have any spurious stationary points.
4

---

Published as a conference paper at ICLR 2025
To gain insight into Regularizer we invoke Lemma I and obtain
(x)
[x]² min Σm= (In (I) + vB))
(11)
BERz0
As above, we observe this regularizer's auto-scale property and see that only vectors of form {-a, 0, +a} A for some R minimize (11.
The CS regularizers introduced so far promote binary- or ternayyvvalue vectors; a visualization of their loss landscapes in two dimensions is provided in App. F In App. B.I we detail an approach that generalizes CS regularizers to a symmetric, discrete-val valued set with 2 equispaced entries. In addition, all of the CS regularizers introduced above involve polynomials of higher (e.g., quartic) order, leading to potential numerical stability issues. In App. [.2] we propose alternative symmetric binarization regularizers that avoid such issues; similar alternative regularization functions can be derived for the other discretization regularizers.
2.3 RECOVERING EIGENVECTORS OF A GIVEN MATRIX
All CS regularizers introduced so far promote vectors with discrete-valued entries. In order to demonstrate the versatility of Proposition | we now propose a CS regularizer that promotes vectors that are eigenvectors of a given (and fixed) matrix E RNNN
Define g(x) - Cx and hxx) = x. Then, Proposition 1 yields the following CS regularizer that promotes eigenvectors of the matrix C; see App. A.6 for the derivation.
Regularizer (Eigenvector). Fix R N ler x E RN,, and define
feig (x)
Cx
(x" Cx)²
(12)
Then, the nonnegative function in (22 only zero for eigenvectors of C and the all-zeros vector.
To gain insight into Regularizer we invoke Lemma and obtain
feig (x) [x]
min Cx 3x1
(13)
As above, observe this CS regularizer's auto-scale property and that only scaled eigenvectors of the matrix C minimize (13)
2.4 RECOVERING MATRICES WITH ORTHOGONAL COLUMNS
Finally, we demonstrate that Proposition | can also be used promote structure in matrices. The following CS regularizer promotes matrices X E R with K < N to have orthogonal columns.
vec(X*) X) and h(x) A vec(Ix). Then, Proposition yields the following CS regularizer that promotes matrices with orthogonal columns; see App. A.7 for the derivation.
Define gXX) A
Regularizer (Matrix with Orthogonal Columns). Ler X E N with K S N and define
Com (X) A K XXXX X | |
(14)
Let X USVT be the singular value decomposition of X. Then, we equivalently have,
SK (Ex -
Laml X) & K
(15)
which is the symmetric binarizer from
(6) applied to the singular values X The nonnegative
X with pairwise orthogonal columns of equal length, i.e., iff function in (14) is only zero for matrices
X alg for a > 0. Furthermore, Pom (X) does not have any spurious stationary points.
To gain insight into Regularizer we invoke Lemma and obtain
Lom (X)
K min HER
vec(X" Bvec(Ix)]3.
(16)
Once again, we observe this CS regularizer's auto-scale property and see that only matrices X with orthogonal columns of the same promotes the same norm for all columns of X for simplicity. However, one could modify h(x) to promote, for example, certain user-defined ratio between the norms of the columns.
minimize (16). Note that have developed regularizer that
5

---

Published as a conference paper at ICLR 2025
2.5 GENERALIZATIONS AND VARIATIONS
Proposition aan the underlying ideas enable the design of a much broader range of regularizers. We now propose one possible generalization, where replace the CS inequality utilized in Proposition [ with Hölder's ' inequality (Hölder 1889), resulting in the following recipe for Hölder regularizers.
Proposition 2. Fix two vector-valued functions h: RN - R and define X as in LLt q 1
that P =1 and let >> O. Then, the nonnegative function functiiooo
[(x) & |lg())l[ -Kg((),
(17)
zero iff x E
Note that Proposition] 1 is special case of Proposition by setting p -=
We include more generalizations and variations in App. Specifically, we propose CS regularizer promoting vectors with symmetric equispaced discrete values in App. B.I bounded CS regularizers for vector binarization in App. B.2 CS regularizers for discrete-valued vectors with fixed scale in App. B.3 non-di non-differentiable variants of CS regularizers regularizers that is invariant to the scale of the functions g and h in App. B.5 We conclude by noting that many other CS or Hölder regularizers can derived when combining the above ideas and those put forward in App. B We also note that most of these results can be generalized to complex-valued vectors. detailed investigation of such generalizations and variations is left for future work.
App. [B.4] and generalization of CS
3 APPLICATION EXAMPLES
We now show several application examples for CS regularizers for vector discretization, recovery of eigenvectors of a given matrix, recovering matrices with orthogonal columns, and quantization of neural network weights.
3.1 RECOVERING DISCRETE- DISLEEDE-VALUED VECTORS
The proposed CS regularizers enable the recovery of binary- and ternary-valued vectors from un- derdetermined linear systems of equations. To this end, solve systems of linear equations of the form = Ax, where A E M has i.i.d, standard normal entries and M < N. We create vectors x* E V whose entries binary and from {0, +1} for one-sided binary, and with probability 0.25, 0.5, 0.25 from {-1, O, +1}. respectively, for ternary-valued vectors. Then, we calculate b Axx, and we try recover the vector x" from b by solving optimization problems of the form
chosen i.i.d. with uniform probability from {-1,+1] +1] for symmetric
& E arg min ((x) subject to b = Ax REEN
(18)
FISTA with backtracking (Beck & [3] Here, {(x) are the CS regularizers from Section 2.2 We fix N = 100 and vary M7 between 30 and 90 We declare success for recovering x* if the returned solution & satisfies || X=||2/||x*| [|l//||=||2 1|2 < 10-2, Fig. shows the success probabilities with respect to the undersampling ratio y along with eтror bars calculated from the standard error of the mean.
using projected gradient descent gegorithm--ppccfiiee
Teboulle 2009 Goldstein
Symmetric Binary We first recover symmetric binary-valued solutions using Regularizer D with bii from (6). For this scenario, Mangasarian & Recht (201T) showed that for -norm minimiza- tion recovers the binary-valued solution long as y M / satisfies 7 > 0.5 and N approaches infinity. Thus, our baseline is 8o -norm minimization, which we solve with Douhlas-Rachford splitting (Eckstein & Bertsekas) T992) as in [tuder al. (2015). Fig. Ta shows the success rate for foin and -nom minimization with respect to the undersampling ratio y. For Eoin minimization, we observed that different initializations have an impact on the success rate since the objective is non-convex. Thus, allow at most 10 random initializations of projected gradient descent. We note
A We run projected gradient descent and baseline algorithms for a maximum of 10 iterations.
We also study the impact of the sparsity of x* while the number of measurements M is fixed in App. C.4 For each M, randomly generate 1000 problem instances and report the average success prohability.

---

Published as a conference paper at ICLR 2025
Eyrs
68
63
1
24
eitccoss rade
BULCORSS rate
Statcess
04
144
03
04
0.6
0.7
5.5
35
07
05
M/N
M/N
M/N
(a) Symmetric binary
(h) Onc-sided binary
Symmetric ternary
Figure 1: Probability of success for recovering vectors with (a) binary, (b) one-sided binary, and (c)
symmetric ternary values dependent on the undersampling ratio M/N.
that multiple initializations of -orm minimization do not affect its success rate the problem convex. We see from Fig. Ia that 4in minimization has, for any undersampling ratio y, higher probability of successfully recovering the true solution than -orm minimization.
We discuss the advantages of lai over existing binarizing regularizers App. C.1 We also provide a comparison of the success rates of fii and f -norm minimization with existing binarizing regularizers in App. C.2 and observe that lin achieves the highest success rate. Moreover, in App. C.3 we provide the success of other binarizing CS regularizer variants (e.g., the Hölder, non-differentiable, and scale-invariant regularizers), where fin- once again, achieves best performance.
In App. C.7 showcase yet another application for the lhin regularizer. Specifically, find approximate solutions to the weighted maximum cut (MAX-CUT) problem (Commander (2009). Our simulation results in App. show that our approach does not identify optimal solutions for large graphs, but significantly improves the objective values compared to the initialization.
it to
One-Sided Binary We now recover vectors with one-sided binary-valued entries using Regular- izer with bosb from (8. In this experiment, we projected gradient descent for only random initialization. Our baseline for this scenario is El f--norm minimization (Cai et al. 2009), as the gener- ated vectors are sparse with half of the entries being nonzero (on average). We solve the --omorm minimization problem with Douglas-Rachford splitting. Fig. Tb demonstrates that Losb minimization significantly outperforms él -norm minimization for all undersampling ratios.
Symmetric Ternary We also recover vectors with symmetric ternary-valued entires using Reg- ularizer 3 with for from (10). In this experiment, we ran projected gradient descent for only one random initialization. We use f--norm minimization
our baseline as the generated vectors sparse with half of the entries being nonzero (on average). Fig. I dedeonsttate that fier minimization significantly outperforms él -nom minimization for all undersampling ratios.
We provide similar simulation results for symmetric two-bit-valued solution recovery in App. C.5
3.2 RECOVERING EIGENVECTORS OF MATRIX
The proposed CS regularizers also enable the recovery of eigenvectors of given (and fixed) matrix. We once again consider a system of linear equations of the form = Ax, where A E MxX has i.idd. standard normal entries and M N. We create vectors x* E R by uniform randomly choosing an eigenvector of a matrix C E N with i.i.d. standard normal entries. We calculate b Ax* and solve 118 using Regularizer with leig- As a baseline, we consider minimizing (x, fi) A CC f subject to b = Ax, similarly to 18 with an additional optimization parameter (i.e., ( compared to minimizing Leig (x). We FISTA as in Section 3.1 for both algorithms. Fig. 7 in
App.(c C.6ommmnstttttss that the success rate of L remains to be consistently above 0.8, approaching 1 N-rtio of 01.5, and surpassing that of the baseline that minimizes e,..
7

---

Published as a conference paper at ICLR 2025
3.3 RECOVERING MATRICES WITH ORTHOGONAL COLUMNS
We now demonstrate that the proposed regularizers can also impose structure to matrices. To this end, consider system of linear equations AX B. where A R has i.i.d. standard normal
entries with M < N, and E BRNK with X = Ig- We solve
X E arg min XERNEX K
(om( subject to AX B
(19)
using FISTA as in Section 3.1 with a maximum number of 1000 iterations. We have observed that for N K 10 and N = 100 and for values of M such that M/N E [0.1, 1), the output of
FISTA was always an orthogonal matrix, i.e., the success rate is always one.
3.4 QUANTIZING NEURAL NETWORK WEIGHTS
We now provide another application example for binarizing and ternarizing neural network weights. Our goal is to further highlight the simplicity, versatility, and effectiveness of CS regularizers.
3.4.1 METHOD
Our weight quantization procedure consists of three steps: (i) training with CS regularizers, (ii) weight quantization, and (iii) continued training of remaining parameters. We detail these steps below. In order to demonstrate solely the impact of CS regularizers, we neither modify the neural network architecture (e.g.. we do not alter the layers activations) nor the stages, since we do not introduce any non-differentiable operations during training.
propagation
Step 1: Regularized Training Let O denote the set of all parameters of neural network and L(0) the loss function for learning the network's ' task. We solve the following optimization problem:
0 = arg ara mjn L(O) + +
E(Os).
(20)
Here, À E R20 is regularization parameter, 02 is vector consisting of the network weights which should share a common scaling factor (this can, for example, be an entire layer, one convolution kernel, or any other subset of network parameters), 77 the associated normalization factor (e.g.. the reciprocal value of the dimension of 0z), and l can be any CS regularizer (e.g., bnin or her)
After training the network parameters with the CS regularizers for given number of epochs, the weights contained in the vectors 0₂ will be concentrated around { {-or,, or for symmetric binary- valued regularization or {-ag, 0, 0x } for symmetric temaay-vvlued regularization for some ag > 0.
Step 2: Quantization The goal is to quantize the regularized weights {0 from the previous step. In what follows, we describe the quantization procedure for one weight vector w = O₁.
We binarize the regularized weight vector w according to A arg arg l|w x|| with
Xpin _ [x E (-a, a.N a E } as Rastegari al. 2016). which given by i a* sign(w.). n I....,N, with |w||1/N.
(21)
We teraaiize the regularized weight vector w + ON according to w arg min ||w - x11 with Xuur {x E a.
R) as in Li et al. (2016), which is accomplished as follows: Let I, = (i: w 2 r). Then, find the threshold that determines which entries of w are nonzero as max TE (EW
arg
[Z1 (ZiEz, [w:l)²
(22)
Finally, compute the ternarized vector as ax* sign(wa), |wa| 2 7' otherwise.
D 0.
n1 = I,...,N, with a" = 1
[. Eiet, |wyl.
(23)
Step 3: Training with Quantized Weights After weight quantization, the number of trainable parameters is significantly reduced since we now have only one scale factor for a vector of quantized weights. Hence, we fix the signs of the weights and continue training only their shared scale factors alongside other tunable network parameters (e.g., biases, batch normalization parameters, etc.) without the use of CS regularizers and for small number of epochs.
8

---

Published as a conference paper at ICLR 2025
3.4.2 EXPERIMENTAL RESULTS
We conduct experiments on the benchmark datasets ImageNet (ILSVRCI2) (Deng et al. CIFAR-10 (Krizhevsky) (009) for image classification using PyTorch (Paszke et al. 2019). classical data augmentation strategies as detailed in App. D.I
2009) and
We follow
Implementation As in Rastegari al. (2016); Qin et al. 2020) He al. (2020), we regularize and quantize all network layers except for the first convolutional layer and the last fully-connected layer. For convolutional layers, we apply the CS regularizer to vectors consisting of the weights in all kernels that produce one output channel; this leads to one scaling factor for each output channel following the approach from Rastegari et al. (2016). For fully- colly-connected layers, we use one CS regularizer for each row of the weight matrix; this leads to one scaling factor for each output feature. We set the weights 7/ (2 to the reciprocal of the dimension of the corresponding weight vector O,.
For ImageNet, we use ResNet-18 (He et al., 2016), initialize the weights with a pretrained full- precision model from PyTorch, and train the network for 40 and 20 epochs in Steps and 3, respectively, with batch size of 1024. For CIFAR-IO, 10, we use ResNet-20. initialize the weights with a pretrained full- full-precision model from Idelbayev (202T) similarly to Qin et al. (2020), and train the network for 400 and 20 epochs in Steps 1 and 3, respectively, with batch size of 128. For both datasets, we set x= = 10 for binarization and X = 10s for ternarization. We use the Adam optimizer (Kingma & Ba 2017) with its learning rate initialized by 0.001 and the cosine annealing learning rate scheduler Loshchilov & Hutter 2016).
Weight Distribution Fig. illustrates the impact of CS regularizers on the network weights with histograms for one output channel of one convolutional layer based training ResNet-18 on ImageNet. We observe in Fig. aa that the weight distribution of the pretrained network resembles that of zero-mean Gaussian distribution. Figures 2b) and (c) reveal, as expected, that the weights are becoming more concentrated around binary values after 5 and 20 epochs of training with the regularizer Enin. respectively. Figures dd) and (e) reveal a similar behavior when using ler-
provide the top-1 accuracy for our methods Performance Evaluation In App. D.3 Tables 8 10
along with the full-precision baseline and various SOTA baselines that binarize or ternarize the weights of the network while the activations are left in full precision. All SOTA top-1 accuracy results in Tables
10 are taken from the corresponding papers.
For ImageNet, we observe from Tables 8 and Table that for binary-valued weights, our approach outperforms SQ-BWN (Dong et al. 2017). BWN (Rastegari et al. (0066), HWGQ (Cai et al. 2017). PCCN (Gu et al. 2019). . and the ternary TWN (Li et al.] 20166). while the accuracy we achieve is 4.9% lower than the best SOTA method ProxyBNN (He et al. 2020). For ternary-valued weights, our approach outperforms TWN and SQ-TWN (Dong et al. 2017). while the accuracy we achieve is 2.8% lower than the SOTA method QIL (Jung et al. 2019).
For CIFAR-10, we observe from Table TO that for binary-valuce weights, our approach outperforms DoReFa-Net by small margin and achieve the same performance as LQ-Net (Zhang et al.) 2018).
while the accuracy of our approach is 0.9% lower than the SOTA methods DAQ (Kim et al. 2021 )
and I.CR-BN (Shang et al.) 2022): these two methods are also the only methods outperforming our telnery-valued approach by 0.2%
While some of the SOTA methods achieve better accuracy than our approach, results (i) require simpler training procedureJann and (ii) showcase the potential of CS regularizers: We only have one step of regularized training with full-precisin training with fewer parameters; this procedure does not require any additional storage at any stage of training. In contrast, all of the baseline methods retain both the quantized and full-precision values for the weights during training, and use the quantized weights in forward and backward propagation while the full-precision values updated with the gradients calculated with respect to the quantized values. This results in additional storage. Moreover, to reduce the guantization error or to alleviate
weights, quantization step, and second step of
'We chose the regularization parameter empirically based on using 1 1/10th of the training sets for validation. We have observed that changes by factor of 10 in do not have substantial impact on the resulting accuracies. Please see Tables 3 o App. [22 for an ablation study for varying X.
'llease Table for the advantages/disadvaaaagss of our training strategy compared the SOTA methods

---

Published as a conference paper at ICLR 2025
count
160
count
120-
count
180
count
100
count
140
80
60
90
50
70
2
-0.05
0.00 weight values
0.004
0.06 weight values
0.05
weight values
weight values
weight values
Pretrained
(b) Paias 5 epachs
(c) Aain: 20 epochs
(d) Perrs
epochs
(c) Euer 20 epochs
Figure 2: Neural network weight histograms of one output channel of a convolutional layer in the pretrained ResNet-18 model and the model after regularized training with bain or fie over ImageNet.
the mismatch between forward and backward propagation, references Gu et al. 2019); ; Hu et al. (2018); Kim et al. (202I); ; He et al. (2020); Yang et al. (2019); Zhang et al. (2018) uugg et al. (2019) introduce more trainable parameters and Shang et al. 2022) proposes a regularization method that requires the construction of matrices that scale with the square of the number of features in one layer. Please see Table in App. D.3 for a comparison the additional variables introduced by each SOTA
method.
We conclude by noting that the proposed CS regularizers could be combined with any of these existing approaches for possible further accuracy improvements.
LIMITATIONS
While the proposed CS regularizers provide recipe for designing regularization functions with wide variety of properties, they suffer from range of limitations that we summarize next.
First and foremost, CS regularizers are typically nonconvex. While we have been able to prove that some of the proposed nonconvex CS regularizers are free of any spurious stationary points (and thus are invex), convergence to global minimum depends on the combination of the objective, regularizer, and optimization algorithm. Thus, multiple random restarts of the optimizer might be necessary. Depending on the specific regularizer, a solution algorithm that exploits invexity, such as the one presented in Barik et al. (203)), could be utilized instead.
Furthermore, some the CS regularizers involve higher-order polynomials (e.g., the ternarization regularizer in (10) involves eighth-order polynomials), which result in poor convergence behavior, especially around their minimum. To counteract this issue, one can either resort to scale-invariant non-differentiable variants outlined in App. B.4 In addition, utilizing adaptive step-size selection methods and schedules that adapt (e.g.. increase) the regularization parameter À over iterations could also be used improve convergence.
versions as outlined in App. B.5
Finally, we have only scratched the surface of many of the generalizations and variations put forward in Section 2.5 and in App. B Besides that, we have investigated the efficacy of CS regularizers with only four example tasks, i.e., solving underdetermined systems of linear equations for recovering discrete-valued solutions, eigenvectors, and matrices with orthogonal columns, and neural network weight quantization with simple training recipe, in Section 3 A thorough theoretical analysis and simulative study of alternative CS regularizers in a broader range of applications, as well as combining CS regularizers with sophisticated SOTA quantized neural network training procedures, such as the ones in He et al. 20200; Jung et al. (2019), are left for future work.
5 CONCLUSIONS
We have proposed can designed to promote a wide range properties. We have derived example regularization functions that promote discrete-valued vectors, eigenvectors to matrices, matrices with orthogonal columns, and we have outlined range of specializations, variations, and generalizations that lead to an even broader class of new and possibly more powerful regularizers. For solving underdetermined systems of linear equations, we have shown that CS regularizers can outperform well-established baseline methods, such fo -n-m or eo-norm minimization. For weight quantization of neural networks, we have shown that utilizing CS regularizers enables one to achieve competitive accuracy to existing quantization methods while using simple training procedure.
(CS) regularizers, a novel class of regularization functions that
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Yu Bai, Yu-Xiang Wang, and Edo Liberty. ProxQuant:
Quantized neural networks via proximal operators. In International Conference on Learning Representations, ICLR, 2019.
Adarsh Barik, Suvrit Sra, and Jean Honorio. Invex programs: First order algorithms and their convergence. arXiv preprint arXiv:2307.04456, 2023.
Amir Beck and Mare Teboulle. Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Transactions on Image Processing, 18(1 (C(1))241-24444 January 2009.
A. Ben-Israel and B. Mond. What invexity? J. Aust. Math. Soc. Ser. Appl. Math., 28(1):1-9, July 1986. doi: 10. 10100775033420000005144
T. Tony Cai, Guangwu Xu, and Jun Zhang. On recovery of sparse signals via formm minimization. IEEE Transactions on Information Theory, 35(7))3388-339) June 2009.
Zhaowei Cai, Xiaodong He, Jian Sun, and Nuno Vasconcelos. Deep learning with low precision by half-waye Gaussian quantization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017.
Oscar Castañeda, Sven Jacobsson, Giuseppe Durisi, Mikael Coldrey, Tom Goldstein, and Christoph Studer. 1-bit massive MU-MIMO precoding in VLSI. IEEE J. Emerging Sel. Topics Circuits Syst., 7(4):508-522 522, December 2017.
Yoojin Choi, Mostafa El-Khamy, and Jungwon Lee. Learning sparse low-precision neural networks with learnable regularization. IEEE Access, 1996933-96774, 2020.
Clayton W. Commander. Maximum cut problem, MAX-CUT, pp. 1991-1999, Springer US, Boston, MA, 2009, ISBN 978-0-337-74755--0 doi: 10.
358. URL https?
358
Sajad Darabi, Mouloud Belbahri, Matthieu Courbariaux, and Vahid Partovi Nia. Regularized binary network training. arXiv preprint arXiv:1812.11888 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proc. IEEE Conf. Comp. Vision and Patt. Recog., pp. 248-255, May 2009. doi: 10.
Yinpeng Dong, Jianguo Li, and Renkun Ni. Learning accurate low-bit deep neural networks with stochastic quantization. In BMVC, 01 2017. doi: 10.524//C.31.189)
Jonathan Eckstein and Dimitri P. Bertsekas. On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55: 293-318, 1992.
Matthias Joachim Ehrhardt and Simon R. Arridge. Vector-valued image processing by parallel level sets. IEEE Transactions on Image Processing, 23(1)99-18, 2014. doi: 10. 10.1109/1P22001.227777
Ahmed T Elthakeh, Prannoy Pilligundla, Fatemehsadat Mireshghallah, Tarek Elgindi, Charles-Alban Deledalle, and Hadi Esmaeilzadeh. WaveQ: Gradient- based deep quantization of neural networks through sinusoidal adaptive regularization. arXiv preprint arXiv:2003.00144 2020.
Richard Everson. Orthogonal, but not orthonormal, Procrustes problems. Advancee Advances in Comp. Math.,
3(4), 1998.
Tom Goldstein. fasta- Accessed: 2024-03-30.
Ruihao Gong, Xianglong Liu, Shenghu Jiang, Tianxiang Li, Peng Hu, Jiazhen Lin, Fengwei Yu, and Junjie Yan. Differentiable soft quantization: Bridging full frel-precision and low-bit neural networks. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4852-4861, 2019.
11

---

Published as a conference paper at ICLR 2025
Jiaxin Gu, Ce Li, Baochang Zhang, Jungong Han, Xianbin Cao, Jianzhuang Liu, and David Doermann. Projection convolutional neural networks for 1-bit CNNs via discrete back propagation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 8344-8351, July 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. IEEE Conf. on Comp. Vision and Pattern Recognition (CVPR), pp. 770-778, June 2016. doi: 10.1109/CVPR.2066990.
Xiangyu He, Zitao Mo, Ke Cheng, Weixiang Xu, Qinghao Hu, Peisong Wang, Qingshan Liu, and Jian Cheng. ProxyBNN: Learning binarized neural networks via proxy matrices. In European Conference Computer Vision, pp. 223-2422211111 Springer, August 2020.
Otto Hölder. Ueber einen Mittelwerthssatz. Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg- Georg-Augusts- Leee--uuuuss--uvvennnee Universität zu Göttingen, (2):38 47, 1889.
Lu Hou, Quanming Yao, and James T Kwok. Loss-aware binarization of deep networks. arXiv preprint arXiv:1611.01600 2016.
Qinghao Hu, Peisong Wang, and Jian Cheng. From hashing CNNs: Training binary weight networks via hashing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, April 2018
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran EI- Yaniv, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. Journal of Machine Learning Research, 18(187):1-30, 2018.
Pei-Hen Hung, Chia-Han Lee, Shao-Wen Yang, V Srinivasa Somayazulu, Yen-Kuang Chen, and Shao-Yi Yi Chien. Bridge deep learning the physical world: An efficient method to quantize network. In IEEE Workshop on Signal Processing Systems (SiPS). IEEE, 2015.
Yerlan Idelbayev. Proper ResNet implementation for CIFAR1O/CIFAR 100 in PyTorch. https //github. cow.//kkmmmtttee/ttorr..... hewptoorcc_reeee.tee resnet cifarl0 2021.
Accessed: 2024-04-
30.
Ian T Jolliffe. Principal component analysis for special types of data. Springer, 2002.
Sangil Jung, Changyong Son, Scohyung Lee, Jinwoo Son, Jac-Joon Han, Youngjun Kwak, Sung Ju Hwang, and Changkyu Choi. Learning to quantize deep networks by optimizing quantization intervals with task loss. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4350-4359, 2019.
Dohyung Kim, Junghyup Lee, and Bumsub Ham. Distance-aware quantization. In JEEE/CVF International Conference on Computer Vision (ICCV), pp. 5251-5260, October 2021. doi: 10.110 9/ICCV48922.2021 202200
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, January 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009. URL https: s/api.semantt.cccholaar wwtp::ooooooo::i.2e5555552
Cong Leng, Zesheng Dou, Hao Li, Shenghuo Zhu, and Rong Jin. Extremely low bit neural net- work: Squeeze the last bit out with admm. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Fengfu Li, Zhang, and Bin Liu. Ternary weight networks, arXiv preprint 1805::600.044 2016.
Yezi Liu, Hanning Chen, Wenjun Huang, Yang Ni, and Mohsen Imani. Cauchy-schwarz fairness regularizer, 2025, URL htttps:///ppereee///
forum ? -iddJooQ2NNK-R
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts, arXiv preprint orXiv:/608 039883, 2016.
12

---

Published as a conference paper at ICLR 2025
Zhi- quan Luo, Wing-kin Ma. Anthony Man-cho So, Yinyu Ye, and Shuzhong Zhang. Semidefinite relaxation of quadratic optimization problems. IEEE Signal Processing Magazine, 27(3):20-34, May 2010.
Olvi L. Mangasarian and Benjamin Recht. Probability of unique integer solution to a system of linear equations. Eur. J. Oper. Res., 214(1): October 2011.
Yoshiki Matsuda. Benchmarking the MAX-CU proble on the simulated bifurcattonn machine, 2019.
cut-pz oblem- on the a http://:ww.....i..eooeoooaaaaonr
URL Qtt.s///eeeaaaa.a.....oaaaaaaaaa
Accessed:
2024-06-27.
Maxim Naumov, Utku Diril, Jongsoo Park, Benjamin Ray. Jedrzej Jablonski, and Andrew Tul- loch. On periodic functions regularizers for quantization of neural networks. arXiv preprint arXiv: /8/ 1.09862, 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch An imperative style, high-performant deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035, 2019.
Samuel Pinilla, Tingting Mu, Neil Bourne, and Jeyan Thiyagalingam. Improved imaging by invex regularizers with global optima guarantees. Advances in Neural Information Processing Systems, 15:10780-10794, 2022.
Jose C Principe.
Information theoretic learning: Renyi's entropy and kernel perspectives. Springer Science & Business Media, 2010.
Haotong Qin, Ruihao Gong, Xianglong Liu, Mingzhu Shen, Ziran Wei, Fengwei Yu, and Jingkuan Song. Forward and backward information retention for accurate binary neural networks. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2247-2256, June 2020. doi: 10. N0.1009/CVPR44-0022000.000
Mohammad Rastegari, Vicente Ordonez, Joseph Redmon, and Ali Farhadi. Xnor-net: ImageNet classification using binary convolutional neural networks. In European Conference on Computer Vision, pp. 525-542. Springer, 2016.
Ryan Razani, Gregoire Morin, Eyyub Sari, and Vahid Partovi Nia. Adaptive binary-ternary quantiza- tion. In Proc. IEEE/CVF Conf. on Computer Vision and Pattern Recognition (CVPR) Workshops, pp. 4613-4618, June 2021.
Peter H Schönemann. A generalized solution of the orthogonal Procrustes problem. Psychomelrika, 31(1):1-10, 1966.
Sohil Shah, Abhay Kumar Yadav, Carlos D Castillo, David W Jacobs, Christoph Studer, and Tom Goldstein. Biconvex relaxation for semidefinite programming in computer vision. pp. 717-735, September 2016.
Yuzhang Shang, Dan Xu, Bin Duan, Ziliang Zong, Liqiang Nie, and Yan Yan. Lipschitz continuity retained binary neural network. In European Conference on Computer Vision, pp. 603-619. Springer, October 2022.
Kirill Solodskikh, Vladimir Chikin, Ruslan Aydarkhanov, Dehua Song, Irina Zhelavskaya, and Jiansheng Wei. Towards accurate network quantization with equivalent smooth regularizer. In European Conference on Computer Vision, pp. 727-742. Springer, 2022.
J. Michael Steele. The Cauchy-Schware Master Class: an Introduction to the Art of Mathematical Inequalities. Cambridge University Press, 2004.
Christoph Studer. Tom Goldstein, Wotao Yin, and Richard G. Baraniuk. Democratic representations. arXiv: 1401.44034400 April 2015.
13

---

Published as a conference paper at ICLR 2025
Sueda Taner and Christoph Studer. 8"-f"- minimization for joint precoding and -oak-to-vverage power ratio reduction. In Proc. Asilomar Conf. Signals, Syst., Comput., pp. 237-442, October 2021.
Wei Tang, Gang Hua, and Liang Wang. How train compact binary neural network with high accuracy? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Linh Tran, Maja Pantic, and Marc Peter Deisenroth. Cauchy-Schwarz regularized autoencoder.
Journal of Machine Learning Research, 23(115):1-37, 2022.
Matthias Wess, Sai Manoj Pudukotai Dinakarrao, and Axel Jantsch. Weighted quantization- regularization in DNNs for weight memory minimization toward HW implementation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(11):2929-2939
2018.
Sheng Xu, Yanjing Li, Teli Ma, Mingbao Lin, Hao Dong, Baochang Zhang, Peng Gao, and Jinhu Lu. Resilient binary neural network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 10620-10628, 2023.
Huanrui Yang, Lin Duan, Yiran Chen, and Hai Li. BSQ: Exploring bit-level sparsity for mixed- precision neural network quantization. arXiv preprint arXiv:2102.10466 2021.
Jiwei Yang. Xu Shen, Jun Xing. Xinmei Tian, Houqiang Li, Bing Deng, Jianqiang Huang, and Xian- sheng Hua. Quantization networks. In Proceedings of the IEEF/CVF Conference on Computer Vision and Patlern Recognition, pp. 7308-7316, 2019.
Dongqing Zhang, Jiaolong Yang, Dongqiangzi Ye, and Gang Hua. LQ-nets: Learned quantization for highly accurate and compact deep neural networks. In Proceedings of the European conference on computer vision (ECCV), pp. 365-382, 2018.
Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou. Dorefa-net: Train- ing low bitwidth convolutional neural networks with low bitwidth gradients. arXiv preprint 1rX1v:1606.06166, 2016.
14

---

Published as a conference paper at ICLR 2025
Appendix: Cauchy-Schwarz Regularizers
A PROOFS AND DERIVATIONS
A. PROOF OF PROPOSITION 1
From the Cauchy-Sehwarn Schwarz inequality (Steele 2004) follows that
(g((), h(x)) S llg [xxx)]22-
(24)
Squaring both sides of (24 and rearranging terms leads to
[g(x)]] ||2 [ - (g((), hxx)) ((x).
(25)
Equality in 24 holds iff g(x) h(x). for which ((x) = 0.
A.2 PROOF OF LEMMA 1
Assume that h(x) + 0. Then,
i Ølgg(x) - (1(x))1 = 0 8 (g(x). h(x))
(26)
0B
[
Plugging the right-hand-side into llg(x) (h(x))1 yields
|| [x) (h(x) 112 llg(x))1 (g).), h(x))l
min
(27)
BER
[ 12
Multiplying both sides by ||(xx)] results in f(x)
|lh(x)
min llg(x) ph(x)
(28)
PER
If hxx) = then 28 still holds. By swapping g(x) with h(x), the equalities in
5
follow.
A.3 DERIVATION OF REGULARIZER
Regularizer is minimized by vectors E TRN that satisfy the linear dependence condition g(x)
h(x) for the specific choices g(x) !n? a2]" [T and h(x) 1x. We have
g(x) h(x) + 3(a1, 02) e R ((000))) a1 = 02. n = N.
(29)
If 01 + 0, then // 02/a; 01 which implies = ta, = 1...., N. for some a E R. If a1 0 then 02 * so the condition aΙd 02 cannot be satisfied; this implies that the only vectors that satisfy fain (x) = from (6) are in the following set:
Xoi (x [-a,a] a a R..
(30)
The same result would also follow directly from the inspection of
To establish the fact that Regularizer [ does have any spurious stationary points (thus, that the regularizer is invex), we need to show that V (x) = 0 iff x E X To this end, we inspect
06 (x) 4Nr3 4[x]2x, 4x, (N [x] 0. n 1= N. Ba
(31)
Clearly, every vector x E Voin satisfics 31I. For any other vector, the gradient is nonzero. To prove this, it is sufficient to show that the derivative is nonzero for two-dimensional, vector, because any vector with a non-bine binaaryvallee subvector is coan--inay--allue (and any non- binary-valued vector has non-binary-valuue subvector). To this end, let x [a,, T for B a + -B, and a, 3 + 0. Then, we have
cam-binary-value
8t [x]
4a(2a² - (a2 (2))) 4a(a² - -B²) 40,
(32)
8x1
which concludes our proof.
15

---

Published as a conference paper at ICLR 2025
A.4 DERIVATION OF REGULARIZER| 2
Regularizer is minimized by vectors x E RR that satisfy the linear dependence condition g(x) ~
h(x) for the specific choices g(x) | ... x If and h(x) = x. We have
g(x) hxx) = 3 02) E IR (((,0) -1 azIn: n === 1.....,,N N. (33)
If zn = 0, then the condition a = az is trivially satisfied. If In + O, then we inspect
a ag. If * 0, then I,, 02/ /1/ which implies I, for some E IR. If aj = 0 then
02 7 0. so the condition an = d2 cannot be satisfied; this implies that the only vectors that satisfy
(x) 0 from (8) are in the following set:
Noab = {& E {0, :a E R)
(34)
The same result would also follow directly from the inspection of
To establish the fact that Regularizer does not have any spurious stationary points (thus, that the regularizer is invex), we need to show that Vles (x) 0 iff x E Xosh To this end, we inspect
Dla(x) 2zn ([x] + 2x [x]2 3x, [x] 0, I,.....,
(35)
Ba
Clearly, every vector x E Kasu satisfies 35 For any other vector, the gradient is nonzero. To prove this, it is sufficient to show that the derivative is nonzero for two-dimensional, non-one-sided- binary-valued (non-OSB) vector, because any vector with a non-OSB subvector is non-OSB (and any non-OSB vector has a non-OSB subvector). Assume = [a, 3|" for a A and a, 3 A Then 06 = 20.32 (2ax B) 3), and by symmetry, 0lax(x) 2n 20a - 2.3 - f); this implies 822
88 (xx) and ((x)()) cannot be zero simultaneously.
that 801
A.5 DERIVATION OF REGULARIZER 3
Regularizer 3 is minimized by vectors x E TR.N that satisfy the linear dependence condition g(x) ~
h(x) for the specific choices g(x) = .i..... ... 2y)
.N g(x) ~ hxx) - 3(01, 02) E ((0,0)))) a1= = azIn: n = I....NN.
IT and h(x) = x. We have
(36)
If F. 0, then the condition a 0g trivially satisfied. If v. + O, then we inspect
a1æ, t = a2. If 01 * 0. then 2 02/01, which implies In =a for some E R. If 01 = 0 then
a2 * 0. the condition "Ι 02 cannot be satisfied; this implies that the only vectors that satisfy Last = 0 from 10) are in the following set:
X = {x E {-a, 0, a a E ]..
(37)
The same result would also follow directly from the inspection of
To establish the fact that Regularizer doees not have any spurious stationary points (thus, that the regularizer is invex), we need to show that V (x) = 0 iff x E Xer- To this end, we inspect
(x) Oa 2x [[x] 6 + 3[x]=xx]
x = 0, n = I,..,..
(38)
Clearly, every vector x Xer satisfies 38 For any other vector, the derivative is nonzero. To prove this, it is sufficient to show that the derivative is nonzero for a two-dimensional, non-ternary-valuee vector, because any vector with a non-ternary-valuee subvector non-ternary-valuee (and, any non-ternar--valued vector has a non-ternary-valuee subvector). Assume x [a,, B] for + B,
+ 3 and a, 3 + Then (x,(() 2a:52(3a2 {²2 52), and, by symmetry, Brg
Slm(x))
dz)
2a 202 (. ) this implies that (x=(x) and (x,()) cannot be zero simultaneously. 8m. ang
A.6 DERIVATION OF REGULARIZER 4
Regularizer 4 is minimized by vectors N that satisfy the linear dependence condition g(x) h(() for the specific choices gxx) = Cx and h(x) = x. By definition, we have that g(x) ~ h(x) and only if x is an eigenvector of C.
For the sake of completeness, we provide the stationary point analysis of Regularizer 4 below: (x)e = 2 +
[Cxll 2(xT [RT)xx)xx 0x-
(39)
Clearly, every eigenvector of C satisfies (39 While it appears to be unlikely that any other would satisfy (3). we are unable to provide formal proof that rules out the existence of other solutions. Therefore, we refrain from claiming that Regularizer has no spurious stationary points.
16

---

Published as a conference paper at ICLR 2025
A.7 DERIVATION OF REGULARIZER 5
Regularizer is minimized by matrices X E I NxX that satisfy the linear dependence condition
g(x) ~ h(x) for the specific choices g X - vec ('X) and h(x) _ vec(Ix)
To establish the fact that Regularizer 5 does not have any spurious stationary points (thus, that the regularizer is invex), we need to show that om (x) = iff x E Xom- To this end, we inspect
Vx L (X) = 4NXX - 4 X X - 0
(40)
XX(XX'X - X I =
(41)
XX |X I
(42)
which implies that X must have orthogonal columns of equal length.
A.8 PROOF OF PROPOSITION 2
From the triangle inequality and Hölder's inequality (Hölder 1889) follows that
(g(x)), h(x))l Σ [[g(()),,, [x()) S [l)))(()))
(43)
where p. q 2 so that + 1. Raising the left-hand and the right- sides of (43 to the power ofr > and rearranging terms leads to
|x) | h(x) - (g((x) h(x))l & ε(x))
(44)
Both inequalities in 433 hold iff gxx) hxx), for which t(x) 0.
B GENERALIZATIONS AND VARIATIONS OF CS REGULARIZERS
B.1 BEYOND VECTOR T'ENARIIATIONN
We now show one approach that generalizes CS regularizers symmetric, discrete-valued set with 2 equispaced entries. The idea behind this approach is as follows: (i) decompose x E R into sum of B auxiliary vectors Σ -=1 yo with ys RN and (ii) apply one regularization function to the auxiliary vectors yo, = ...... B.
Define g( ((y)))m)))) hi (y1y))) ..... (y using h, (y) 'I'... Then, Proposition yields the following CS regularizer that promotes symmetric equispaced-valuee vectors; see App. B.I.I for the derivation.
[i(( TT ..... )( using g(y) = b....... If and h((r))
Regularizer 6 (Symmetric Equispaced). Let yo E RN for b = -,...,, B and define
Cogu ((r))=)) & KN (Etn
1 1y
(45)
with K A >B 12( Then, the nonnegative function (45) is only zero for vectors Yb (-2b-la, ar, 26-1 aa) 1O I...., B. for any a E IR; this implies that the sum of these vectors 12n-1 with (Kqull = 2B, Furthermore, legu does not x Eb=13 is in the set Xequ 2 (+(2 - 1
have any spurious stationary points.
To gain insight into Regularizer
6 we invoke Lemma I and obtain
Loqu ((ro) KN min BER
Σ ((1x)) - 2 V3)((xo) + (3))² 6=1
(46)
We also observe this CS regularizer's auto-scale property and only vectors of the form ys (-2b-la a, 26-1a) a for some a E IR minimize (46). This implies that the vectors x are of the form x (- 1)a,..., 3a, -a, 3a...., (2 1)a} for some R.
In contrast to the initially introduced binarization and ternarization regularizers, Regularizer introduces additional optimization parameters, multiplying the number of the optimization parameters by B. We provide an example use case Regularizer 6 with simulation results for recovering two-bit solutions to underdetermined linear systems in App.
17

---

Published as a conference paper at ICLR 2025
B.1.1 DERIVATION OF REGULARIZER 6
Regularizer
6
minimized by vectors {yo that satisty the linear dependence condition
g((yb) B
h(1)))))) for the specific choices g((v))=)) (g(y)). ................................ B(y n)]" using
g(y) = lyi...., v and h ((yo) = (n((y))......bf... .....)]])]]] using h(yb) = 46- Iy. We have
g ((y)))m))) ~ h((v))))
3(aI, a2) E R,a [(0,0) 0)} : aive.n - a24"11, b b= 1, 1...., B, 1 I....,N. N.
(47)
If + O, then Vn = ds 4-1 which implies Yo.h 0 yh. ta2
1, N,
b = .,... B, for some a R. a = then 02 + 0, so the condition aivi, = a24 cannot be
satisfied; this implies that the only vectors ys that satisfy Lequ ((yb)an) 0 from 455 are in the following set:
aa 1122"1,,2" 2,,"" a] UON,
(48)
with yu E V.ba.b = I,.... for any a E R. The same result would also follow directly from the inspection of (46). Then, the vectors x = Σb= Yt are in the following set:
Kegu = {x Ex (-2-1a..... a..-........ 3a, - a, a 30,..., 2..,,,-aa) c
(49)
To establish the fact that Regularizer does not have any spurious stationary points (thus, that the regularizer is invex), we need show that (Vb = 0, b 1...., iff yo E Vo.a. 1....
for any E R. To this end, we inspect
R Dlegu (yr 1=1)
4(yoJn (KN(())))) - - 1 Ebe 4 (-y') = 0
(50)
aly olyiin
for n = 1...., N and b = 1,..,, B. Clearly, Ys E Vo b = 1..... B satisfies (50). For set of
vectors in any other form, the derivative is nonzero. To prove this, sufficient to show that the
derivative is nonzero for pair of scalars (i.e., N = 1) (vb, vv for yb * 0, 0,1y * 2 and
|yw- 2 2 |a because any pair of vectors including these entries would not satisfy (50 (and any set of vectors that do not satisfy (50) must have such a pair of entries). We have that
Heeg (Vb, Ybr)
4214
(07 4 #0,
(51)
Oy:
which concludes our proof.
B.2 BOUNDED CS REGULARIZERS FOR VECTOR BINARIZATION
We now propose alternative binarization regularizers that avoid potential numerical issues caused by higher-order polynomials.
Define b(x) (1 + =²)-1 and g(x) A [b(x1)...., b(Tx)] Furthermore, let h(x) 1N. Then, Proposition D yiells the following CS regularizer that promotes symmetric binary-valued vectors. Regularizer 7 (Bounded Symmetric Binarizer). Lerx N. and define
Lvbin (x) NEW (1+=2)²
- -EN
(52)
Then, the nonnegative function in (52) is only zero for one-sided binary-valued vectors, i.e., iff x E {=a,a) aN for any a E R. Furthermore, lxbin does not have any spurious stationary points.
An alternative binarization regularizer can be obtained as follows. Define b(x) A e- and g(x) e (b(z))...,,b b(xx)]' Furthermore, let h(x) A 1N. Then, Proposition 1 yields the following CS regularizer that promotes symmetric binary-valued vectors.
Regularizer (Alternative Bounded Symmetric Binarizer). Let X E N and define
Coinexp (x) & N
2. -ENN e-=,e-22,)
(53)
Then, the nonnegative function in 53 is only zero for one-sided binary-valued vectors, i.e., iff
x E {0, a for any a E R.
Note that by normalizing 52 and is bounded from above by T.
53
with 1/N?, the maximum value of the resulting CS regularizer
18

---

Published as a conference paper at ICLR 2025
B.2.1 DERIVATION OF REGULARIZER FROM APP. B.2
Regularizer is minimized by vectors RR that satisfy the linear dependence condition g(x) h(x) for the specific choices g(x) - [1 + +1) ..... (1 + xN) and h(x) = 1N.. We have
g(x) ~ h(x) = E(. 02) E ((. a1 x,)² 02. n = I....,,
(54)
If 01 * O, then (1+ =n,)² 02/a1 which implies nn Ia, 1, , NN, for some R. If a1 = then d2 * 0, so the condition (1 + xx,)² = 42 cannot be satisfied; this implies that the only vectors that satisfy (nain
from 52) are in Xnin-
To establish the fact that Regularizer 7 does not have any spurious stationary points (thus, that the regularizer is invex), need show that Vissin (x) iff x E Xin To this end, inspect
M 4(1 + =
Ex=1 1+o!! = 0, n = I.
(55)
I+
Clearly, every vector x E Abin satisfies (55). while the derivative nonzero for any other vector, similarly to p1...
B.2.2 DERIVATION OF REGULARIZER FROM APP.
Regularizer 8 is minimized by vectors x E T that satisfy the linear dependence condition g(x) ~ h(x) for the specific choices g(x) je je-
+x IT and h(x) 1x. We have
g(x) ~ h(x) = 3(1,, a2) E ((0,0) are 02 n n= 1. N. (56)
If a1 * 0, then ? 02/a1 which implies Vn, =a, n l...., NN for some a E R. If 01 then a2 * 0, so the condition are= = = 02 cannot be satisfied; this implies that the only vectors that satisfy fhin.exp (x)
from 53 are in Xhin-
To establish the fact that Regularizer does not have any spurious stationary points (thus, that the regularizer is invex), need show that Vesineyp (x) 0 iff Xnin- To this end, inspect
(fmeep()) Ban
=4( DNe-Neete 2e=2 + - = 0,
N.
(57)
Clearly, every vector x E Abin satisfies (57), while the derivative is nonzero for any other vector, similarly to (T...
B.3 CS REGULARIZERS FOR DISCRETE- VALUED VECTORS WITH FIXED SCALE
If one is, for example, interested in promoting binary-valued vectors with predefined scale, i.c.. {-a, a. but for given fixed value of a, then one can use g(x) - [s]..... a²),,,"]] and h(x) A IN+1 in (4). We note, however, that this particular binarization regularizer with a has been utilized before in Tang et al.] (2017); similar regularizers can be found in HHng et al. (2015): Darabi et al. (2019). In general, the idea of augmenting the functions g and h with constants removes the auto-scale property of CS regularizers.
B.4 NON-DIFFERENTIABLEE CS REGULARIZERS
One can also develop non-differentiable variants of CS regularizers. For example, by defining g(x) A
and h(x) IN in Proposition 1 one obtains the CS regularizer
P (x) [x]] |xx||
(58)
which also promotes symmetric bilury- entries. Intriguingly, this regularizer is equal to the scaled empirical variance of the entry-wise absolute values of R i.e., loin (x) N2 Var ([x)). One could also combine the idea of (58) with Proposition Jusing p = q = 2 and = to obtain
hin (x)
/N||x||2 ||x||
(59)
which also promotes symmetric binury-valued entries. Such alternative versions might result in better empirical convergence if, for example, they are used within mnto-differentiation frameworks that allow for non-differentiable functions. We conclude by noting that the specific regularizer in (58) has been used in Taner & Studer (202T) for dynamic-range reduction of complex-valueee data in wireless systems.
19

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of regularizers for vector binarization. Advantages are designated by (+) and disadvantages by (-).
Regularizer
Differentiable
Scalc-adaptive
Requires additional opti-
(+)
(+)
mization variables (-)
[[xn]
1)2
No
No
No
n
m (1zg)
8)2
No
Yes
Yes
(x
1)2
Yes
No
No
(a 8)2
Yes
Yes
Yes
Ours (fbin)
Yes
Yes
No
B.5 SCALE-INVARIANT HÖLDER REGULARIZER
By slightly modifying the proof of Proposition one can also develop Hölder regularizers that are innee-invariant, i.e., in which scaling the entire vector-valued function g(x) or h(x) with nonzero constant has impact the regularizer's function value.
Proposition 3. Fix two vector-valued functions g, h: RN + RR and define X as in 33 Letp. q 1 so that = 1 and let r > O. Furthermore, sel e 2 0. Then, the nonnegative function
[I l 1 +E -1 [[g(x), h()))lr +e
((x)
(60)
zero iff x E
The proof of Proposition 3 follows that of App.
A.8 but where we first add > to the left-hand and right-hand sides of (43. followed by division by (g(x), h(x)) + e and rearranging terms to arrive
(xx in 60).
Such scale-invariant regularization functions require special attention. First, while the parameter 0 prevents the denominator in (60) from becoming zero, only
leads to scale-invariant regularizer. Second, regularizers derived from Proposition 3 may have significantly more spurious stationary points than those obtained via Proposition 2 Third, evaluating the gradient of regularizers derived from (60) is typically more involved. Nonetheless, their (approximately) scale-invariant property might turn be useful in some applications and outweigh the above drawbacks. We note that scale-invariant versions of CS regularizers can also be obtained as special case of Proposition 3
B.6 VECTORS IN THE NULLSPACE OF GIVEN MATRIX
As last regularizer, we propose variant that promotes unit-norm vectors in the nullspace of given
(and fixed) matrix C M Define g(x) & [(Cx)], | 1, and h(x) & [0 [ 0, 1J". Then, Proposition [ yields the following CS regularizer that promotes unit-norm vectors in the nullspace of C.
Regularizer (Nullspace Vector). Fix C E M with M 2 N and let x E N Define
e (x)
|C + (|xx - 1)²
(61)
Then, the nonnegative function in (6] is zero for only unit-norm vectors x in the nullspace of C. i.e..
iff Cx Oιx1 with ||x|3
C ADDITIONAL. RESULTS
C.1 COMPARISON OF THE BINARIZING CS REGULARIZER WITH EXISTING REGULARIZERS
Table I summarizes the key properties of existing regularizers from Section I.3 and how regu- larizer can be superior to those, i.c., by being differentiable, scale-adaptive, and avoiding additional optimization parameters.
20

---

Published as a conference paper at ICLR 2025
0.8
Success rate
0.6
Eain
0.4
0.2
god
M
M/N
Figure 3: Probability success in binary solution recovery with the CS regularizer 4i and three baselines.
success rate
Ciin
0.6
Crin. H
E
Loin
loin erpp
0.2
820
0.0
0.3
0.4
0.5
0.6
0.7
0.8
0.9
M/N
Figure 4: Probability of success in binary solution recovery with five CS regularizer variants and an g -orm minimization baseline.
C.2 COMPARISONS WITH BASELINES FOR BINARY RECOVERY
We follow the same experimental setup in Section 3.1 and provide experiments for two additional
baselines: (i) assuming that the scale 3 is known and fixed constant and (ii) letting 3 be separate (and explicit) optimization parameter (that learned together with the entries of the vector). As
mentioned Section 1.3 we use f A Σ E
(x) - 3)² with known and fixed 3 = 1, and (2 3)2 with additional optimization parameter 3.
Fig. we observe that both these baseline methods achieve comparable recovery performance, but CS regularizers have the advantages of (i) not requiring know the scale a- a-priori and (ii) not introducing additional optimization parameters.
C.3 ADDITIONAL RESULTS FOR MORE CS REGULARIZERS FOR BINARY RECOVERY
We follow the same experimental setup as Section 3.1 and provide experiments for four additional
variants of CS regularizers: Here, boin refers the Hölder CS regularizer from (17) with p = 2
2, r = 1, binnsi to the scale-invariant Hölder CS regularizer from (60) with 2, = 1, Eoin to the non-differentiable CS regularizer from (58) and hninesp to the bounded CS regularizer from (53)
In Fig. 4 we observe that while 4 has comparable success rate to liin the remaining variants are outperformed by the baseline -ormm
21

---

Published as a conference paper at ICLR 2025
10000200
0.8
rate
0.8
Success rate
0.6
0.6
0.2
0.2
0
0.2
0.4
0.5
0.7
0.8
0.2
0.4
0.5
0.6
0.7
0.8
K/N
K/N
(a) One-sided binary
(b) Symmetric ternary
Figure 5: Probability of success for recovering vectors with (a) one-sided binary and (b) symmetric ternary values dependent on the density ratio K/N.
C.4 ADDITIONAL RESULTS FOR SPARSE RECOVERY
In this subsection, we slightly modify our experimental setup from Section 3.1 in order to compare the solution recovery performance of losd and Ger fe-miiiizzttinn to that of l -norm minimization with respect the sparsity of x*. We fix N 100 and M 75. We create vectors x* E RR- with fixed number of K uniform randomly chosen nonzero entries; these nonzero entries are +1 for one-sided binary vectors, and are chosen i.i.d. with uniform probability from (-1, for ternary vectors. We vary K from 20 to 80. For each K, we randomly generate 1000 problem instances and report the average success probability and the standard deviation from mean. We only allow one random initialization, and the remaining details of the setup the same those presented in Section 3.1
Fig. demonstrates the success rate (a) Losh minimmiizznion and (b) fie miniiiiiiooioon compared to ll -n-orm minimization with respect to the density ratio of x* given by 8 = K/N. In Fig. (a), we observe that while the success rate of gl -normm minimization reduces with > 0.3 and almost reaches 0
0.5, the success rate of los maiimiiiizztoon is almost always 1 for any density ratio. In Fig. (b), we observe that f--oorm minimization follows the same trend as in Fig. 5 expected, while the success rate of minimiiiioo increases with density. The success rate of Ma--iiiiizotionn surpasses that of et-norm minimization for > 0.4.
C.5 SIMULATION RESULTS FOR TWO-BIT SOLUTION RECOVERY FOR REGULARIZER 6
We provide example those of the binary and ternary regularizers from Section 3.1 To this end, we consider systems of linear equations
of the symmetric equispaced regularizer from 455 similarly to
Ax, where A E x has i.i.d. standard normal entries and M < N. For two-bit-valued solution vector recovery, we create two vectors y E R and y2 E IRN whose entries are chosen i.i.d. with uniform probability from {-1, +1} and f-2, +22, respectively, and calculate x* = y1 + y2. Then, we calculate Ax", and we try to recover the vector x" from b by solving optimization problems of the form
ý1. 82 E arg min legu (51,82) + AIIA($1 + +22) - bbl
(62)
using a gradient descent algorithm specificaclii......c... FISTA with backtracking (Beck Teboulle 2009. Goldstein) for a maximum of 10a iterations. We fix N 10, 10-b and vary M between 3 and 9. For each M, we randomly generate 1000 problem instances, with at most 10 random initializations each, and report the average success probability. We declare success for recovering x* the returned solution satisfies | x=||//||x x S 10 Fig. shows the success probabilities with respect to the undersampling ratio along with (negligibly small) error bars calculated from the standard error of the mean. Here, we observe that legu can recover symmetric two-bit vectors for large undersampling ratios with reasonable success probability.
22

---

Published as a conference paper at ICLR 2025
Epps
success rate
0.6
0.4
0.2
M/N
Figure 6: Two-bit solution recovery for N = 10 with CS regularizer loqu.
C.6 SIMULATION RESULTS FOR EIGENVECTOR RECOVERY FROM SECTION 3.2
Please see Fig. 7 Here, we observe that minimizing Lei provides a higher success rate than the baseline Eps which requires an additional optimization parameter compared to feig.
0.8
SUccess rate
Exig Ey
0.3
0.4
0.5
0.6
0.7
M/N
Figure 7: Eigenvector recovery 100 with the regularizers leig and baseline by. where y must also be learned in the baseline method.
C.7 APPROXIMATING MAXIMUM-CI CUT PROBLEMS WITH CS REGULARIZERS
We now showcase another application in which CS regularizers can be utilized. Specifically, CS regularizers can be used to find approximate solutions to the well-known weighted maximum cut (MAX-CUT) problem [Commander 2009). MAX-CUT of graph is the partition of a graph's vertices into two disjoint sets such that the total weight of the edges between these two sets is maximized. For an undirected weighted graph G = (V, E), this maximization problem can be formulated as the following integer quadratic programming problem:
maximize xE(-1,+1J
Wiy (1 - 2TT,))
(63)
ISiCJNN
(x)
Here, Fy E i= N, denotes the binary set label for the ith vertex of the graph, N is the number of vertices, and way R denotes the weight of the edge between the ith and jth vertices.
The MAX-CUT problem is NP-hard, and many approximations have been proposed in the literature. Classical approximations based semidefinite and continuous relaxation; see, e.g, Commander (2009) and the references therein. Here, we propose a continuous reformulation that utilizes CS regularizers:
E arg min -MMc(x) + Al (x) subject to | S 1,
(64)
XERM
23

---

Published as a conference paper at ICLR 2025
which we attempt to solve using projected gradient descent, similarly to Section 2.2 with fixed maximum number of iterations.
To evaluate this approximate approach, initializations for 10 trials. First, we considered small graphs; here, we set
projected gradient descent algorithm with random
1.
For the 5, = 7 graph from Matsuda 2019), we recovered the MAX-CUT solution in less than 300 iterations in each of the 10 trials with random initializations.
For a graph with N 4 vertices, E 5 edges, and weights w12 10. W13 20, wh4 30. U24 = 40, and w34 50, we recovered the MAX-CUT in less than 40 iterations in each of the 10 trials.
Second, we considered the larger graphs, where way E {-1,1}, given in Matsuda (2019) for benchmarking; here, we set À = 10-? The table below demonstrates the graph ID, the average cut values Exc for the initializations and recovered solutions across 10 trials, and the maximum values from Matsuda 2019).
Table 2: Comparison of Our Cut and Known Maximum Cut (Matsuda 2019) for Different Graphs
Graph ID
Initial Cut
Our Cut
Known Maximum Cut (Matsuda 2019)
G10
57.4
1769.1
2000
G11
7.2+
482.0+ 10.46
564
G12
-0.2+424.3
+3.77
556
G13
22.6+25.11
494.2:8.11
582
Our approach struggles to recover the MAX-CUT for large graphs; nonetheless, it significantly improves the objective value compared to the initialization, demonstrating its potential. Moreover, with notable computational advantages over the method in Matsuda (2019), our approach shows promise and could inspire future research.
D DETAILS OF NEURAL NETWORK QUANTIZATION EXPERIMENTS FROM SECTION 3.4
D.1 DATASETS AND PREPROCESSING
ImageNet has over 1.2 M training images and 50 k validation images from 1000 object classes. We train and evaluate our network on the training and validation splits, respectively, and report the top-1 accuracy for performance evaluation. We adopt a typical data augmentation strategy on the training images as resizing the shorter side the images to 256 pixels, taking a random crop of size 224x 224, and applying random horizontal flip. For validation, we apply the same resizing and take the center 224x224 crop.
CIFAR-10 10 (Krizhessky) 2009) consists of over 50 training images and 10 testing images from 10 object classes. We adopt a typical data-augmentation strategy on the training images as padding by pixels, taking random 32x crop, and applying a random horizontal flip. For testing, we use the original images.
D.2 THE IMPACT OF VARYING THE REGULARIZATION PARAMETER ON THE CLASSIFICATION ACCURACIES
In Tables 3 provide the average accuracy and standard deviation across 10 runs for various values of A. The chosen values are emphasized in bold. Here, we observe that changing the value of X by factor of 10 does not have substantial impact on the accuracies.
24

---

Published as a conference paper at ICLR 2025
Table 3: Top-1 accuracy of binarized ResNet-18 ImageNet for regularized training for various values of X.
0.1
10
100
1000
Top-1 %
51.5:0012
59.6=0.11
62.8:10.09
62.4=0.10
59.5:10.08
Table Top-1 accuracy of temariizdd ResNet-18 on ImageNet for regularized training for various values of X.
A
le3
le4
le5
le6
1c7
Top-1 %
63.5:0.12
64.8:1.10
65.3
65.3
64.6=10.17
D.3 PERFORMANCE COMPARISON WITH SOTA BINARIZED AND TERNARIZED NEURAL. NETWORKS FROM SECTION B.4.2 3.4.2
In 7 we provide comparison of the advantages/disadvaatags of our training strategy compared the SOTA methods. We remark that our approach is the only method that does not introduce any additional variables.
we provide a comparison the image classification accuracy of our methods compared to the SOTA methods. Here, report the average accuracy and standard deviation for 10 random initializations training. remark that the accuracy of our methods is comparable that of the SOTA methods.
In Tables I0
E COMPUTATIONAL RESOURCES
For underdetermined linear systems experiments in Section 3.1 maximum number 10a iterations, projected gradient descent and Douglas- Rachford splitting algorithms each took approximately
used MATLAB. For the
second at most.
For our neural network weight quantization experiments in Section 3.4 we use PyTorch (Paszke et al. 2019). We note that using CS regularizers does not ineur significant additional cost in training; to this end, we measure the time it takes to train for one epoch in the following three scenarios one NVIDIA RTX 4090 GPU: (i) training with full-precision weights without regularizer, (ii) regularized training with full-precision weights (Step in Section 3.2.1). and (iii) training with measured
quantized weights (Step 3 Section 3.2.1). For these three scenarios with ResNet-18, 660 s, 680s s, and 650 respectively; with ResNet-20, we measured 4.1 s, 5.2 s, and 3.8 s. These numbers demonstrate that, while the calculation of the CS regularizers naturally results in some overhead in Step 1, the training might be even faster than full- full-precision training in Step 3, depending on the size of the network and the training dataset. Therefore, depending on the ratio between number of epochs in Steps and 3. CS-regularizer-base training could be quicker than full-precision training (and thus, all the other SOTA methods) for the same total number of epochs.
F REGULARIZATION FUNCTION LANDSCAPES
Fig. 8 illustrates the loss landscapes of Regularizer Regularizer and Regularizer in R2. Here, clearly the global minima of each function.
25

---

Published as a conference paper at ICLR 2025
Table 5: Top-1 accuracy of binarized ResNet-20 CIFARIO for regularized training for various
values of X.
0.1
10
100
1000
Top-1 %
87.1+:0.17
89.5-0.20
90.3:1..23
89.7=10.18
88.4-10.24
Table 6: Top-1 accuracy of temarized ResNet-20 on CIFAR10 for regularized training for various values of X.
le3
le4
le5
le6
1e7
Top-1 90.5:10.1
90.7=0.17
91.0:10.13
91.0=1.10
90.8:10.17
Table Comparison of variables that are required by SOTA neural network quantization methods and CS regularizers (ours) for training. Each column represents variables that are required in addition to (unquantized) full-precision neural network training.
Method
Trainable variables
-on-trainable variables
Tunable hyper- parameters
SQ-BWN (Dog et al.
2017
Yes
Yes
0
BWN Rastegan et al.
2016
No
Yes
0
HWGQ (Cai et al. 201
No
Yes
0
PCCN Gu et al.
2019)
Yes
Yes
O
BWHN Hu
a 2018
No
Yes
0
ADMM Leng et al. 2018
Yes
No
IR-Net QQin et al. (0200
No
Yes
0
ACR-BNN (Shang et al.
2022
No
Yes
2
DAQ (Kim al. (021))
No
Yes
ProxyBNN (He et al.
2020
Yes
Yes
TWN (Li al.) 2016
No
Yes
QNet (Yang et 2019
No
Yes
QIL (Jung et al. (2019)
Yes
Yes
O
DoReFa-Net (Zhou al.
2016
No
Yes
0
LQ (Zhang et al. 2018)
Yes
Yes
0
DSQ (Gong et 2019
Yes
Yes
0
Ours (fnin and (er)
No
No
Method
Top-I (%)
ResNet-18 (FP)
69.8
SQ-BWN Dong et al.
2017
58.4
BWN Rastegar et al.
2016
60.8
HWGQ Cai et al. 201
61.3
PCCN Gu ct al.
2019
63.5
BWHN (Hu et 2018
64.3
ADMM (Leng et al.
2018
64.8
IR-Net (On et 2020)
66.5
LCR-BNN (Shang et al.
2022
66.9
DAQ (Kim et al. 2021
67.2
ProxyBNN (He et al. 2020
67.7
Ours (foin)
62.8+10.9
Table Top-1 accuracy of ResNet- 18 with binary-valued weights on ImageNet. FP stands for the full-precision model accuracy.
26

---

Published as a conference paper at ICLR 2025
Method
Top-1 (%)
ResNet-18 18 (FP)
69.8
TWN (Li ct al. 2016
61,8
SQ-TWN (ong et
2017)
63.8
Qet Yang et al. 2019
66.5
ADMM (Lng al. 2018
67.0
LQ ZZang et al.
2018
68.0
QIL Jung et al.
2019
68.1
Ours (Egr)
65.3:10.08
Table Top-1 accuracy of ResNet-18 with ternary-valued weights on ImageNet. FP stands for the full full-precision model accuracy.
Method
Top-1 1 (%)
ResNet-20 (FP)
91.7
DoReFa-Net (Zouu et
2016)
90.0
LQ (Zhang et al. 2018)
90.1
DSQ (Gong et al. 2019
90.2
IR-Net (Qnn al 2020
90.8
DAQ (Kim et al. 2021)
91.2
LCR-BNN (Shang et al.
2022
91.2
Ours (Bvin)
90.3
Ours (Eeer)
91.0++0.11
Table 10: Top-1 accuracy of ResNet-20 on CIFAR-10 (c) with binary- and ternary-valued weights FP stands for the full-precision model accuracy.
(a) Symmetric binary
(b) One-sided binary
(c) Symmetric ternary
Figure 8: Two-dimensional loss landscape of CS regularizers in logarithmic scale.
27


Reviews:
[{"review_id": "HFMz7kb7Oa", "reviewer": "Reviewer_X82h", "summary": "The paper introduces Cauchy–Schwarz (CS) regularizers. These regularizers can be designed to impose various structural properties in the solution vectors of optimization problems, such as promoting discrete-valued vectors, eigenvectors of a given matrix, or orthogonal matrices. The CS regularizers are differentiable, adapt automatically to appropriate scales, and avoid spurious critical points, making them suitable for gradient-based solvers and large-scale optimization tasks. The authors validate the proposed CS regularizers through applications in under-determined linear systems and neural network weight quantization.", "questions": "I suggest adding experiments to evaluate the performance of CS regularizers in other machine learning contexts beyond neural network quantization,. This could further illustrate the broader applicability of the proposed framework.\n\nIt would be helpful to either provide convergence guarantees for specific cases of CS regularizers or at least include empirical evidence demonstrating reliable convergence across multiple trials.\n\nThe regularization can be non-convex, e.g., Symmetric Binary case in Sec. 3.1. Using multiple starting points will increase the computational cost and this may be a bottleneck for some large-scale problems.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduction of CS regularizers is the contribution of this paper. The versatility is demonstrated effectively through several concrete examples, including weight quantization and underdetermined linear systems.\n\nSpecific CS regularizer examples for various optimization problems are given to make reader easier to follow and use.", "weaknesses": "While the applications demonstrated are valuable, they are limited to weight quantization and linear systems. It would have been beneficial to explore other potential applications of CS regularizers in broader machine learning problems. \n\nThe paper mentions the nonconvex nature of the proposed regularizers and briefly discusses the presence of spurious critical points for some variants. However, the convergence properties of the optimization algorithm in the presence of these regularizers are not analyzed. More rigorous theoretical or empirical analysis regarding convergence would strengthen the argument for their practical viability.", "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": "", "extra_scores": {}}, {"review_id": "1oq1AESGyt", "reviewer": "Reviewer_WyH1", "summary": "This paper introduces a novel class of regularization functions, called Cauchy–Schwarz (CS) regularizers, which can be designed to induce a wide range of properties in solution vectors of optimization problems. The resulting regularizers are (i) simple, (ii) automatically determine the appropriate scale, (iii) free of any spurious critical points, and (iv) differentiable, which enables the use of (stochastic) gradient-based numerical solvers that make them suitable to be used in large-scale optimization problems. Furthermore, the authors also discuss specializations, variations, and generalizations, which lead to an even broader class of new and possibly more powerful regularizers.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The tool used in this paper is the CS inequality from (Steele, 2004)\n\n2. The authors introduces a novel class of regularization functions, called Cauchy–Schwarz (CS) regularizers.", "weaknesses": "1.There are too many refereces in lines 80-84. If you don't compare and explain them one by one, the literature is superfluous.\n\n2.The tool in this paper is the CS inequality from (Steele, 2004). Is there any other advance tools that can be used to desigh such regularization? The authors should compare these methods to show the superiority of CS inequality.\n\n3.The propositon 1 is a known conclusion. A literature is necessary here.", "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": "", "extra_scores": {}}, {"review_id": "DDy8ORH7Md", "reviewer": "Reviewer_ck6X", "summary": "The paper introduces a class of regularizers which they coin Cauchy-Schwarz regularizers. This class is fairly general and special cases can be used for promoting binary vectors or eigenvectors. They prove a few properties of these regularizers, e.g. some have no spurious critical points. Numerical experiments then showcase the potential of these regularizers for various applications.", "questions": "- The property of no spurious critical points is also called invexity. What can be said about minimization of invex functions over convex domains? My guess would be that this is still invex, so the property could be preserved by the constrained formulation. In contrast, if we add a convex data fidelity term, I am certain that this will not lead to an invex problem, hence the usual nonconvex issues arise (as also discussed in the paper)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is original in its idea and clear its description. It builds upon a broad basis of related research but has its own clear novelty. Both the theoretical and numerical contributions are interesting. Modelling a-priori knowledge into regularizers is not a very timely topic but in my view still important as it gives users more freedom what can easily be incorporated e.g. into training ML models. The discussion is well-written and comprehensive.", "weaknesses": "- It is not clear how much impact the proposed work will have. In my view this is a bit niche. This is because, 1) the applications are likely fairly limited and 2) the field has largely moved on from explicit regularizers. That being said, I don't mind that.\n\n- CS regularizers are very related to a branch in imaging inverse problems where structural similar images are encouraged, see e.g. https://royalsocietypublishing.org/doi/full/10.1098/rsta.2020.0205 for an overview. \n\nKey papers in this context are:\n\nGallardo LA, Meju MA. 2003 Characterization of heterogeneous near-surface materials by joint 2D inversion of DC resistivity and seismic data. Geophys. Res. Lett. 30, 1658. (doi:10.1029/2003GL017370)\n\nHaber E, Holtzman Gazit M. 2013 Model fusion and joint inversion. Surv. Geophys. 34, 675–695. (doi:10.1007/s10712-013-9232-4) \n\nEhrhardt MJ, Thielemans K, Pizarro L, Atkinson D, Ourselin S, Hutton BF, Arridge SR. 2015 Joint reconstruction of PET-MRI by exploiting structural similarity. Inverse Prob. 31, 015001. (doi:10.1088/0266-5611/31/1/015001)\n\nThat being said, both approaches are absolutely complementary, so this does not reduce any novelty but could be mentioned for completeness.\n\n- The first paper gives a fairly slow and repetitive start, e.g. abstract and contributions read very similar and are just a paragraph apart.", "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": "", "extra_scores": {}}, {"review_id": "Map5RRXutz", "reviewer": "Reviewer_LeuY", "summary": "The author(s) study a class of regularization functions that aims to discretize vectors, but also in other cases to find solutions to constrained problems. The derivation is flexible and returns differentiable regularizers (apart from some motivated examples in the appendix). From the idea, some theoretical and practical examples are discussed. This is done especially for cases in which finding discretized versions of solution vectors is of interest, e.g. Neural Network quantization.", "questions": "- line 097-098: Why would an alternative solution to the orthogonal Procrustres problem be needed? I do not understand the justification. \n- figure 4: why is $\\ell_{\\infty}$ beating some methods? \n- why do we observe the \"non-convexity of regularizers\"-problem only in the bad performance of $\\ell_{ter}$ in figure 5? I mean, why not everywhere else? I understand that the ternary regularization is more unstable, but are there other evident reasons?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written. Derivation of the regularizers is from first principles. The discussion brought forward after presenting the method has the right balance between practical examples and theoretical examples. It is a nice conference paper idea and looks like there is room for theoretical extensions. Experiments and plots are well exposed. Also, the limitations discussion is very honest.", "weaknesses": "- the computational cost might be very high; \n- from the paper, one big question/weakness I have (but I will place it here), is: what is the class of constraints that this method can give? This is not discussed in the text, as only explicit examples are shown. We can see it discretizes vectors, we can see it finds solutions to Procrustres-type problems, and we can see it finds eigenvalues. What else?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)