Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach
Authors: Giovanni Luca Marchetti
Gabriele Cesa
Kumar Pratik
Arash Behboodi
Venue: Accepted by TMLR ()

Abstract: Lattice reduction is a combinatorial optimization problem aimed at finding the most orthogonal basis in a given lattice. The Lenstra–Lenstra–Lovász (LLL) algorithm is the best algorithm in the literature for solving this problem. In light of recent research on algorithm discovery, in this work, we would like to answer this question: is it possible to parametrize the algorithm space for lattice reduction problem with neural networks and find an algorithm without supervised data? Our strategy is to use equivariant and invariant parametrizations and train in a self-supervised way. We design a deep neural model outputting factorized unimodular matrices and train it in a self-supervised manner by penalizing non-orthogonal lattice bases. We incorporate the symmetries of lattice reduction into the model by making it invariant to isometries and scaling of the ambient space and equivariant with respect to the hyperocrahedral group permuting and flipping the lattice basis elements.
We show that this approach yields an algorithm with comparable complexity and performance to the LLL algorithm on a set of benchmarks. Additionally, motivated by certain applications for wireless communication, we extend our method to a convolutional architecture which performs joint reduction of spatially-correlated lattices arranged in a grid, thereby amortizing its cost over multiple lattices.

Published in Transactions on Machine Learning Research (02/2025)
Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach
Giovanni Luca Marchetti' Royal Institute of Technology (KTH)
glma@kth.c
Stockholm
Gabriele Cesa, Pratik Kumar, Arash Bchboodi
goesaldtti www.eeutiiiuaorrmm.mmmmmm com kprakiks8qli qualcomoom. behboodi@gts
Qualcomm AI Research!
Amsterdam
qwalcomm. wtw.:eegii.qqgom......
com
Reviewed on OpenReview: https: openreviee..........mm net/ forum? id= YaXyRSI24b
Abstract
Lattice reduction a combinatorial optimization problem aimed at finding the most or- thogonal basis in a given lattice. The Leeitra-LLsttr--ovveee (LLL.) algorithm the best algorithm in the literature for solving this problem. In light of recent research on algorithm discovery, in this work, would like to answer this question: is it possible to parametrize the algorithm space for latlice reduction problem with neural networks and find an algorithm without supervised data? Our strategy is to use equivariant and invariant parametrizations and train in a self-supervised way. We design a deep neural model outputting factorized unimodular matrices and train it in a self-supervised manner by penalizing non-orthogonal lattice bases. We incorporate the symmetries of lattice reduction into the model by making invariant to isometries and scaling of the ambient space and equivariant with respect to the hyperocrahedral group permuting and flipping the lattice basis elements. We show that this approach yields an algorithm with comparable complexity and performance to the LLL algorithm on a set of benchmarks. Additionally, motivated by cortain applications for wire- less communication, we extend our method to a convolutional architecture which performs joint reduction of sparially-correlltted lattices arranged in a grid, thereby amortizing its cost over multiple lattices.
1 Introduction
Lattices are discrete geometric objects representing niigh-dimensional grids' that are ubiquitous mathe- matics and computer science. In particular, two fundamental computational problems are basod on lattices: the shortest vector problem (SVP) and the closesí vector problem (CVP). These arise in several areas, among which asymmetric post-quantum cryptography (Hoffstein et al. 1998 Regev 2009 and multi-input multi-
output (MIMO) digital signal decoding (Hassibi & Vikalo 2005
Worrall et al. 2022). Unfortunately, both
are known to be computationally hard and no efficient algorithms exist to address them exactly.
The above-mentioned problems are easier to solve on lattices with highly-orthogonal bases. This has moti- vated the introduction of lattice reduction another computational problem consisting of finding the most orthogonal basis for a given lattice. The problem is NP-hard, but can be solved approximately in polynomial time. The Lenstra-Lensti -ovász (L.LT.) algorithm (Lenstra al. 1982 is celebrated method for this discrete analogue of the
purpose, and can be thought
orthogonalizztiin procedure. LLL
has been the subject of many theoretical and experimental studies, see (Smart et al. 2003 Nguyen & Vallée
Smart et al. 2003 Galbraith
2012 Cohen
2013) for more details.
"Work done during the internship in Qualcomm Al rescarch.
1 QQalccomm AT Research is initiative Qualcomm Technologies, Tnc.

---

Published in Transactions on Machine Learning Research (02/2025)
B' BQ
E GL (R)
Q E GL,
Figure Our neural network maps a basis B of lattice to a reduced basis B' BQ, where Q is a unimodular base change.
However, in this work, we are adopting a different perspective. Considering the goal of lattice reduction algorithms is to construct more orthogonal basis, can we find new lattice reduction method by searching over space that is parametrized by a class of neural networks?
A motivation is that data-driven approaches are able to discover or leverage complex patterns, potentially leading to better solutions (in terms of complexity or performance) for a specific distribution than those found by generic classical algorithms. In general, one can even try to use data to tune the hand-crafted parameters of a classical algorithm, which may result in sub-optimal solutions. Another motivation the amortization capability of neural networks. When the lattice reduction needs to be appliod jointly to multiple correlated lattices, neural networks with their parallel computing can help to amortize the overall computation cost.
A prominent example is the integer least square problem and its application in multiple-input multiple- output (MIMO) detection problem (Hassibi & Boyd. 1998; Hassibi & Vikalo 2005), as lattice reduction is one of the main solutions to this problem. In digital communication, the messages are mapped to the points in a finite dimensional lattice, which are transmitted through the communication chain. Quadrature amplitude modulation (QAM) constellations are well known examples of such lattices, where 2* 2*-QAM for k up to 15 is used in various communication systems. With various techniques, the problem of recovering the transmitted messages boils down to finding the solution to noisy linear inverse problem the transmission lattice, which is an instance of integer least square problems. For multiple antenna systems, the transmission lattice is multi-dinensional complex valued lattice, and the respective inverse problem is known as MIMO detection or demapping. In modern wireless protocols, e.g. 5G New Radio (NR), commuicattin happens over a frequency-time grid (resource grid) where each grid point represents a communication channel for which the input lattice point needs to be recovered. Typically, this amounts to solving thousands of lattice reduction problems, thereby, incurring huge complexity cost. However, the channels for different grids are correlated thanks to the underlying physics of propagation: the correlation among adjacent lattices on the grid further motivates our deep learning approach which can leverage it to jointly reduce lattices the grid at reduced compute cost.
In this work, we develop a neural network model that outputs a base-change unimodular matrix given a lattice basis as input - see Figure [ There are two desiderata for our approach. First, we will not leverage supervised learning for training the model. We are just given a set of matrices and the goal, which is to roduce the orthogonality metric. This is a natural choice, as the ground truth for the change of basis is not known for many cases. In this work, we minimize measure of orthogonality for the output bases, and therefore the training objective is self-supervised.
Second, we would like to incorporate the symmetries of the problem into the model: this will provide hard guarantees about the generalization of the model under symmetric transformations. We show the limitations of including all the symmetries, particularly those related to the unimodular group. Nonetheless, we propose an architecture incorporating many symmetries of lattice reduction into the neural network. Specifically, we design deep model that is simultancously invariant and equivariant to the orthogonal group and to a finite subgroup of the unimodular group, respectively. Tn this sense, our approach is instance of geometric deep
2

---

Published in Transactions on Machine Learning Research (02/2025)
learning [Bronstein et al. 2021), and showcases how combination of discrete and continuous symmetries can be exploited for addressing combinatorial optimization tasks.
The contributions of this work can be summarized as follows:
We propose a novel deep learning model for lattice reduction outputting unimodular matrices via a self-supervised objective. The geometric architecture for the model incorporates inveriance and equivariance continuous and discrete groups respectively.
We implement and empirically compare our model with the classical LLL algorithm for lattice reduction. We show that we can achieve comparable results terms of complexity-performaen An intriguing insight from the result that, hypothetically, without the knowledge of LLL, one can employ self-supervised learning to discover lattice reduction algorithm.
We extend the network to convolutional model that jointly reduces lattices arranged in grid by leveraging the correlation between them. In that sense, the overall cost of reduction can be amortized thanks to the correlation between lattices.
2 Related Work
Deep Learning for Combinatorial Optimization. Addressing combinatorial optimization problems via deep learning constitutes growing line of rescarch - see Bengio ct al. 2021 for a comprehensive survey. In this context, models can be trained either by supervision on a dataset of optimal solutions (Vinyals et al. 2015 Prates et al., 2019: Lemos et al. 2019), or directly on the objective of the given combinatorial optimization problem (Toenshoff et al. 2019 Duan et al.j 2022 Bello et al. 2016). Even though the latter raises differentiability challenges due the discrete nature of the problems considered, it avoids data generation and allows the model to discover patterns autonomously. Our approach adheres to this paradigm since train the model directly on the objective of lattice reduction. Moreover, combinatorial optimization problems often exhibit discrete symmetrics typically with respect to permutations. This has motivated the deployment of invariant and equivariant neural archilectures, such as various incarnations of Graph Neural Networks (GNNs) - see Cappart et al. (2023) for an overview. On this note, the geometric nature of lattice reduction enables us to incorporate both continuous and discrete symmetries into our model.
A Applications of Lattice Reduction. Finding closest. shortest vectors in a high-dimensional lattice is crucial in several domains. For example, a popular public-key cryptographic protocol is based the hardness of the shortest vector problem (SVP) (Ajtai 1996 Hoffstein et al. 1998 Regev (209). Lattice reduction also has some interesting applications in number theory, see Simon (2010). Moreover, several practical applications rely on the closest vector problem: probably, the most prominent one is the multiple- input multiple output (MIMO) detection in wircless communication, which is a crucial component of existing wireless technologies (5G, WiFi, etc.). An instance integer least square, the problem about finding an integer vector of transmitted symbols transmitted from multiple antenna. There vast literature around the topic- for example see (Yang& & Hanzo 2015 Wubben et al. 2004 Hassibi & Vikalo 2005 Worrall et al. 2022 Taherzadeh el al.; 2007) examples Another application is carrier phase estimation in the Global
Positioning System (Hassibi & Boyd 1998). Since lattice reduction significantly mitigates the computational cost of lattice-based problems, it has seen extensive deployment in all of these domains.
3 Background
3.1 Lattices
Intuitively, lattices are grids in arbitrary dimensions. More formally: Definition 3.1. An v-dimensional lattice is a discrete subgroup of (R", +) maximal rank.
If A C RR is a lattice then there exists an isomorphism of groups A Z", Such an isomorphism determines basis of the lattice iee, set of Innealy-inndependent vectors b,,... hn R such that A Zhy @ i Zb,.
3

---

Published in Transactions on Machine Learning Research (02/2025)
A basis is succinctly described by an invertible matrix B E (L) whose columns are the basis vectors. Any two bases B, B' E (RR,(R) are related via (right) multiplication by an integral invertible matrix i.e. B' = BQ for some
E GL (2) = (Q E zn det(Q) = =1}.
(1)
Matrices belonging to GT, (8) deemed wnimodular.
Figure Two equivalent bases of two-dimensional lattice.
Latlices carry two fundamental computational problems.
Problem 3.2 (Shortest Vector Problem (SVP)). Given a basis B lallice A, find X E A AN minimizing the norm ||||-
Problem 3.3 (Closest Vector Problem (CVP)). Given basis B of lattice A and R,, find X A minimizing the distance || /x=
The SVP reduces to the CVP, even in their respective approximate relaxations (Goldreich et al. 1999) and the SVP is known to be NP-hard under randomized reductions (Ajtai 1998).
3.2 Lattice Reduction
Not all bases are created equal. The ideal bases are the orthogonal ones i.e., such that Bd B is diagonal. However, not all lattices admit orthogonal bases, and the amount by which a basis is not orthogonal is measured by the following quantity.
Definition 3.4. The orthogonality defect of B E (R) is
8(B) II, ||b:|| [B)
(2)
Indeed, 8(B) > 1 by Hadamard's incquality and 8(B) if, and only if, Bd is diagonal. The denominator of Equation 2 is the volume of the fundamental domain of A (i.e., the parallelepiped having the basis vectors as edges), and therefore it is independent of the basis.
The orthogonality defect is closely related to the SVP and the CVP. Indeed, the more orthogonal the given basis is, the casier these lattice problems become. In order to illustrate this, note that B is orthogonal then the shortest vector belongs the columns of B, while finding the closest vector given point reduces rounding the coordinates of the latter. For general (Nguyen 2009) that the shortest vector lics within bounds given by orthogonality defect 5(B), implying that the SVP simplifies for oighly-orthogonal lattices. Therefore, given lattice, it is convenient to find its most orthogonal basis operation referred to as reduction. This translates into the following computational problem.
can be proven via the Minkowski's theorem
Problem 3.5 (Lattice Reduction). Given B E GL,, (R), find Q E GL,, minimizing 8(BQ).
However, the above problem is again NP-hard and therefore unfeasible to solve directly. The celebrated Lenstra- Censtra-Lenstraai Manntraa-ooviae (LLL) algorithm (Lensrra et al.) 1982) an approximate algorithm for lattice re- duction that finds basis B' QB of an arbitrary lattice with orthogonality defect bounded by 5(B') S 2)(4-1)/4, The algorithm requires O(n log 3) clementary arithmetic operations, where S max; ||ball, and therefore has polynomial complexity (Galbraith) 2012). We discuss the details of the L.L. algorithm in
4

---

Published in Transactions on Machine Learning Research (02/2025)
the Appendix (Section A
Other approximate lattice reduction algorithms similar to LLL are the Ko- Korkine & Zolotareft 1877], which is slower and has worse orthogonality defect
Haine-Zolotare) algorithm bound, and the Seysen algorithm (Seysen 1993), which reduces the dual lattice simultaneously. Similarly to LLL, all of these algorithms are based on specific houristics, and therefore solve the lattice reduction problem approximately.
4 Method
Our goal to deploy (geometric) deep learning in order to approximate lattice reduction. To this end, we design model of the form
:: GL,, (R) (Z),
(3)
where the input represents basis B of lattice, while the output represents the base-change unimodular matrix Q. The objective of the model on datapoint B is minimizing the (logarithmic) orthogonality defect of the reduced basis B' BB(B) i.e., the loss is:
((B,0) 0) log ((B'(=()=
(4)
= Σ log |ل9||| log (dct(B') 2 0,
(5)
where 9 represents the parameters of p. As mentioned before, the determinant in the above expression is independent of the basis (d)t( = de)(B)) and therefore does not need to be optimized. In the following, we discuss two challenges related to the design of the model: outputting unimodular matrices and incorporating the symmetries of lattice reduction. Figure provides an overview of the method.
Lattice basis B E GL,
Neural Lattice
Reduced basis B' BQ
Reduction
x O(1)
B < BT
Normalized Gram matrix G BBB
Equivariant message passing
Extended Gauss move T GL,
Figure 3: Overview our method.
4.1 Unimodular Outputs
A first challenge is designing in order to output unimodular matrices. This is subtle since the desired matrix has to be simultaneously discrete and invertible. To this end, we begin by considering the special subgroup (Z) = (Q E z=x det(() = 13 C GL,, (Z). Since the orthogonality defect is invariant to multiplying a basis vector by -1 (which flips the sign of the determinant of the basis matrix), without loss of generality we will focus on outputting
element of ST, (Z). In the following, will call Gauss move non-zero element Qi,j away from the
Q SL, (Z) with on the diagonal (Qi, 1 for all i) and at most diagonal (i / j). The following is deep algebraic property of Gauss moves.
Theorem 4.1 (Carter & Keller (1983))
) For 2 3, SL, (2) is boundedly generated by Gauss moves. Specifically, every matriz in SL, (2) is a product of at most [3n2 - n) + 51 Gauss moves.
The above bound for the number of Gauss moves is not strict, and the optimal one is known. Based on Theorem 4.1 propose to design yo to output Gauss move and apply the model recursively to produce sequence of moves. That is, given priorly chosen & E N, the model 1é produces unimodular matrix Q as:
Q = ......Te Tkk
T BT. ... T(-1),
(6)

---

Published in Transactions on Machine Learning Research (02/2025)
where T. is Gauss move.
Since the output space of neural network is Euclidean, it is non-trivial to produce a Gauss move. To this end, we propose the following procedure. First, &p outputs a matrix M E Ruxx,, The absolute value of its n(n 1) 1) entries away from the diagonal are interpreted as logits for a probability distribution over indices (i,5) with # j. An index (i,j) then sampled via the Gumbel-Softmax trick (Jang et al. 2016), which is necessary to differentiate through sampling. The corresponding entry ma.j of M is used to build Gauss move with all the non-diagonal entries apart from mi,j vanishing. Finally, m4,j is discretized in order to lie in Z in differentiable manner. To this end, we adopt the procedure of stochastic rounding, which is popular in the network quantization literature (Gupta et al. 2015 Louizos et al. 2018). It consists of rounding mi, to one of the two closest integers by sampling from a. Bernoulli distribution with probability equal to (one minus) the rounding error. The sampling is performed via the Stumbel-Softmaa trick (technically, Gumbel- Sigmoid), making it differentiable. This discrctization procodure can be seen as an unbiased but stochastic version of the straight-through estimator (Yin et al. 2019
The above procedure produces one Gauss move time. This is however inefficient, potentially requiring long sequences. According to the (loose) bound from Theorem 4.1] k in Equation 6 should be chosen in the order of O(n²). In order to improve this, we propose to retain an entire row and column of M instead of a single entry. Specifically, after the index (i,j) has been sampled, a matrix is produced with 1 on the diagonal, the i-th row and the j-th column equal to the ones of M (except for the diagonal), and 0 elsewhere, i.e.:
m1.5
0
1
(7)
m4,1
ma
Ma,
0
Mnn
We refer to the above as an 'ertended' Gauss move. Extended Gauss moves enable yp to output a unimodular matrix with 2n - 3 non-trivial entries simultaneously. This lowers the number of moves required to O(n), as shown below.
Proposition 4.2. For 2 3, every matrix in SL,, (Z) is product of at most 4n 51 extended Gauss moves.
See Appendix (Section B for a proof. Again, the above bound is not only loose (especially for the additive constant), but might be mitigated on average for random lattices, as happens in practical scenarios. We provide an empirical investigation on the matter in Figure 5 In this case, the index (i.j) is sampled via Gumbel-Softmax using the logite" matrix Rt |M 1 + 1|M M). where is the n matrix containing all is and [M] is the entry-wise absolute value of the matrix M (assuming the diagonal of M to be zeroed-out beforehand).
Lastly, we remark that differentiating the recursive expression from Equation 6 w.r.t. i. (the parameters of) & can be compulationally challenging, especially from a memory perspective. In order to circumvent this, we propose to detach the gradients of the network's output T, at each step i, and to optimize cumulated As a consoquence, the model learns to output an optimal Gauss move given the current input lattice but the whole lattice reduction process is not optimized end-to-end.
loss Ein L(BT, .., T,,
4.2 Invariance and Equivariance
In this section, we discuss how to design & in order satisfy invariance and equivariance properties according to the symmetries of the lattice reduction problem. We start by discussing the symmetry properties of reduced
We have found important compute the logits matrix R from the matrix M to achieve stable convergence.

---

Published in Transactions on Machine Learning Research (02/2025)
To this end, suppose that B' BQ is a basis minimizing the orthogonality defect (Equation 2 for some B E (RR) The following symmetries hold:
bases.
If If BH for some H GL, (2), then = BQ minimizes the orthogonality defect for B, where
Q 2=H* =-
If B = BUB for some U (R), then BQ minimizes the orthogonality defect for B.
If B = aB for some a + e R, then BQ minimizes the orthogonality defect for B.
The first. above property comes from the fact that B and BH bases of the same lattices and therefore have the same reduced basis. Instead, the second property is grounded in the intuition that B and UB are bases of lattices related by an isometry in the ambient space IR" and therefore can be reduced via the same base-change matrix Q. Similarly, scaling a lattice doesn't change its shape and the angle between its basis elements; invariance to scaling is evident in the definition of the orthogonality defect.
Based on the properties above, we aim to design a model satisfying:
Right unimodular equivariance: (BH) H (BB) for H GL, (Z).
Left orthogonal invoriance: (UUB) (BB for U (R).
Scale invariance: c(aB) = (B) for + O
We first focus on left orthogonal invariance. This is straightforward to achieve: instead of inputting the basis matrix B, we input the Gram matrix GBB B. The latter exhibits the desired invariance since, intuitively, it encodes intrinsic metric features the lattice, which are preserved by isometries. what follows, we will abuse the notation for i and write both (BB) and p(G), depending on the input considered.
Similarly, address scale invariance by suitably normalizing the Gram matrix. A natural choice is nor- malizing by (the n-th root of) the delerminant of the basis, which is an invariant of the lattice shared by any of its bases. Unfortunately, this quantity is often particularly small for lattices with a large defect and, therefore, it can produce extremely large input features, potentially posing challenges in training deep learning architectures. Instead, we opt for normalizing the Gram matrix by its trace.
In order to address right unimodular equivariance, note first that G transforms as BH HH.H. Therefore, the model needs satisfy c(H property turns between input and output, but the unimodular group (Z), is algebraically subtle and understood only partially, due to its arithmetic nature. In order to circumvent this, we instead focus on a relevant finite subgroup of (Z): the hyperoctahedral group Hn. The latter consists of the 2"n! signed permutation matrices and can be thought as the group of isometries both the hypercube and the cross-polytope The hyperoctahedral group can also be interpreted as an arithmetic version of the orthogonal group, since Hn 1 GL,, (Z) n O, (IR) Then, signed permutation matrices are intuitively not far from general unimodular ones: due to singular value decomposition, elements in GR, are obtained from the ones in O, by rescaling basis vectors in given base. Therefore, equivariance to ryppeootaaeedral//tthogggo far from equivariance to the full general group; the missing symmetries correspond to unisotropic rescalings. Even further, the (isotropic) scale invariance (third bullet point above) we impose in our model partially amends to this.
H GG)) for H GLm(Z). However, the latter equivariance to be too challenging to be achieved. Not only it involves different transformations
group is not
Considering the hyperoctahedral subgroup simplifies the challenge of designing an equivariant & for a number of reasons. First, H, (R) and therefore H-1 HT for H E H,, Moreover, the orthogonality defect is invariant to the hyperoctahedral group ie., 6(BH) 8(B). Therefore, for the purpose of lattice reduction can consider the equivariance property
(HT (H"GH)= HT (G)H,
7

---

Published in Transactions on Machine Learning Research (02/2025)
which is natural tensorial transformation law and is compatible with the procedures described in Section 4.1 in the following sense. First, it accommodates the recursion from Equation i ie., Q inherits the equivariance property from sp. Second, the (stochastic) procedure to obtain extended Gauss moves is already equivariant (on average) in this sense i.., if M' = MH then the corresponding Gauss move transforms accordingly.
Figure 4: The hyperoctahedral group permutes and flips the sign of the basis vector.
In order to design model that equivariant as in Equation for signed permutation matrices H E Hn, we opt for the Graph Neural Network (GNN) introduced by Maron et al. (2019). These networks can approximate arbitrary message-passing GNNs (Maron et al.] 2018), which in turn are universal function approximators for functions over nodes of graphs (D (D'Inverno et al 2024h. In short, the computation per- formed by such GNN is the following. The entries of the Gram matrix G are interpreted as scalar features, which are then propagated by the GNN through a number of layers. Concretely, starting with the Gram matrix G = G E Raxnx] the 1-th layer takes in input a tensor G E Raxxxx and produces the tensor G++1 (G++)) imde11 Raxaxd+41 given by: )==1
(G'), V2 (G),, v (G)), (G)),"
where 1bf ... wy: Rd + Rdder are Multi-Tayer Perceptrons (MIPss that are applied to G entry-wise the n indices. The MLPs are required to be sign-oquivariant, which can be achieved by implementing sign-equivariant. activation functions e.g., the soft-threshold (xx ReLU(( - [6[) sign(r), where b is the bias of the MLP. After L iterations, the GNN outputs G² e R=xax1, which is interpreted as the matrix M from Section 41
4.3 Computational Complexity
The computational cost of a forward pass in our model with respect to the dimension n can be estimated as follows. First,, computing the Gram matrix G == Bd B has complexity O(n3). Next, the message- message-passing procedure of the GNN layer (Equation 9 can be implemented in O(n") as well. Lastly, the procedure from Scction 4.1 produce extended Gauss moves is casily seen to have complexity O(n²). Therefore, the overall complexity is (n²*),, where & is the number of extended Gauss moves deployed (see Equation 6). The latter has to scale as k = (n) according to the bound from Proposition 4.2 However, the bound is a (loose) worst- case estimate, and can therefore be mitigated even asymptotically on expectation for specific distributions of lattices, as happens in practice. Hence, the forward pass our model is at least as efficient as the LLL algorithm asymptotically which runs in O(n2) (sce Section 3.1. Still, the computational cost. of deep networks includes other constants related e.g. the number of channels, which can have important impact the runtime for low values of n. Using large models is understood to be very effective for optimization, and there exist many techniques (such pruning and knowledge distillation (Hinton 2015 Gou et al, 2021h) ) to subsequently reduce the computational cost with minimal loss in performance. Specifically, it is possible to distil a model trained with a large architecture and with a large value of k into another one with a small architecture, possibly factorizing the unimodular matrix Q in fewer than & matrices. The latter avoids running the model times at test time to produce the reduced lattice, amending for the computational cost inherent training with a large k. In this work, we mostly focus on the overall performance of our models prove their potential to tackle the lattice reduction problem and leave improving efficiency for future works.
8

---

Published in Transactions on Machine Learning Research (02/2025)
4.4 Joint Lattices Reduction
So far, we have focused above on the neural lattice reduction for a single lattice. In practice, there are cases where the goal is to reduce large number of correlated lattices. Although this can be done in parallel, the question is whether we can leverage the correlation between lattices to improve performance-comllextt trade-off.
Application to MIMO detection. A notable example of this scenario is multiple antenna wireless tochnology, called multiple-input multiplc-output (MIMO). In wireless communcattion, time and frequency are two physical resources which are used to multiplex information. In this technology, the transmission occurs over multiple time-frequency blocks. In each block, a lattice point, say x C", constrained within box in the underlying space, is sent using multiple antenna technology. The impact of electromagnetic propagation is captured via linear transformation, say the channel matrix B E (C). The signal detection, called MIM detection problem, boils down to solving the integer least-square problem y = Bx + .V, where N represents white noise and B is assumed to be known. Among other methods for solving this problem, we can apply lattice reduction to the channel matrix B (Wubben et al., 2004 Worrall et al., 2022). This step needs to be done for each fine-frequency block and incurs a substantial computational complexity in the processing chain. For example, in 5G, the fundamental resource block consists of 168 blocks (14 time and 12 frequency blocks). For transmission over 20 MHz bandwidth, in certain operation regimes, we need 106 of these blocks, which means 17808 parallel lattice reduction (Chen et al. 2021). However, the channel matrices share a strong correlation stemming from their adjacency in the time-frequenc, grid. This shared correlation over the grid can be leveraged to amortize some of the operations of our neural lattice reduction approach resulting in joint reduction of correlated lattices at a reduced cost. We review the basics of wireless communication more in Appendix D
Convolutional Neural Lattice Reduction In order to leverage the spatial correlation between neigh- boring lattices, we adapt the previous architecture by 1) endowing its activations with a local field of view to catch the spatial correlation between the lattices and by 2) adopting an hourglass design to amortize the reduction cost over the whole grid.
More precisely, each linear layer in the MLP used to build the equivariant message passing in Eq. 9 replaced with convolution layer with the same input and output. channels but with a 3 x 3 kernel size. Inspired by the U-Net architecture [Ronneberger et al. 2015), to reduce the computational cost, our model consists of first encoder which heavily down-samples the input grid via stridded-oonvolution and following decoder which up-samples the features to the original resolution using transposed convolution and nearest neighbor interpolation; we also adopt linear skip connections based on 1 x 1 convolution between feature maps at the same resolution to avoid losing information about the input lattices. Finally, a different extended Gauss move is predicted for each lattice in the grid by last small equivariant MLP.
While this architecture is more expensive than the single-lattice architecture proposed in the previons section, its cost is shared among all lattices within the input grid and, therefore, the cost per lattice is potentially reduced.
5 Experiments
5.1 Lattice Reduction Under Different Distributions
In this section, we study the performance of our method when trained on lattices generated from different distributions. In particular, we consider 4 different datasots:
Uniform. The entries of B E Rax are i.i.d. and sampled from the uniform distribution by ~ U(0,1) 1)
Exponential. We sample a matrix B E GL, by first sampling a matrix B' Uniform and, then, applying the matrix exponential B exp(0.5 B').
9

---

Published in Transactions on Machine Learning Research (02/2025)
n Distribution
Initial log (B)
LLL log (BLL))
MLP log 8 (LPP)
Our log ((Brrr))
Gap (%)
log 8 ( )-)))-nmm -1og 61 B(BL
log 6(.B
100%
4
Uniform
3.46 (1.33)
0.16 (0.08)
0.23 (0.27)
0.18 (0.17)
0.38 (0-10)
Exponential
0.98 (0.30)
0.30 (0.10)
0.31 (0.13)
0.28 (0.00)
-2.91 (15.6)
6
Uniform
5.74 (1.41)
0.48 (0.15)
0.79 (0.61)
0.52 (0.22)
0.73 (5.0)
Convex d=3
7.17 (1.37)
0.48 (0.14)
0.85 (0.59)
0.51 (0.20)
0.36 (8.9)
Ajtai 9=8
6,56 (4.39)
0.48 (o.16)
3.51 (2.10)
0.55 (0.32)
1.3 (8.6)
8
Uniform
8,02 (1.42)
1.00 (0.28)
2.78 (1.44)
1.16 (0.47)
2.05 7,04
Exponential
6.29 (0.98)
1.05 (0.20)
1.41 (0.45)
1.04 (0.21)
-0.27 (4.78)
Convex 3=3
9.78 (1.34)
1.01 (0.27)
2.17 (0.99)
1.18 (0.18)
1.72 (5-72)
Convex d=8
13.0 (1.56)
0.80 (0.22)
3.33 (1.08)
0.95 (0.49)
1.97 (4.13)
Convex d= 16
14.8 (1.37)
0.82 (0.22)
2.47 (1:16)
1.00 (0.59)
1.29 (9-81)
Ajtai 8=8
9.83 (0.36)
1.00 (0.28)
9.83 (0.35)
1.32 (0.76)
4.2 (11.7)
Table 1: Final log orthogonality defect achieved by LLJ,, an MLP baseline and our method on different lattice distributions. The table reports the average performance (and standard deviation) on 4000 lattices used for validation.
Convex. We first sample d < n² lattice bases {Bi ~ Uniform]; 1d. Then, a lattice basis is sampled as random convex linear combination of these df bases B Σ. w. By, with wy UO,
E,
Ajtai. Inspired by Ajtai 1996), we sample a lattice basis B' with i.ddd entries sampled uniformly in (g. 9-1 and then use the corresponding dual lattice, with basis B == B"T
A larger dimension n generally indicates harder datasets. The matrix exponential can increase the orthog- onality defect by introducing more correlation between different entries; however, the 0.5 factor used in the Exponential distribution attemuates this effect, generally leading to more orthogonal lattices than Uniform. The Convex distributions aim to simulate a form of mmanifold hypothesis', where the data lives in much lower dimension d < n² than the ambient feature space. With this distribution, we want to verify if our method can be fine-tuned on particular data distributions where deep learning solutions typically shine- to perform better than a ceneral-purpoct algorithm designed to work well in the average scenario. Finally, the dual lattices in the Ajtai distribution should not be harder to reduce than the original lattices; because the matrix B' has distribution similar to Uniform, these two datasets are expected to have a similar complexity.
In these experiments, we generate the training data procedurally by sampling random matrices from the distributions above. For evaluation, we sample once 4000 lattices from each distribution and use them to evaluate both our method and LLI. Additionally, to facilitate optimization, we find useful to increase the number of steps k gradually up to k = 2n during the training iterations.
Table D compares the performance of our method, trained on each distribution independently, with that of LLL (using the standard parameter 8 = 0.75) and of MLP baseline]] First, note that the performance of LLL is approximately constant over the Uniform, Convex and Ajtai distributions; these results are in line with the observations in the previous paragraph about the similar complexity of these datasets. Overall, we observe that our method approaches the performance of the classical algorithm in most settings, as indicated by the low relative performance gap in Table However, with respect to LLL, our method seems to improve in the Exponential setting but struggles more to find good solutions for the Ajtai lattices.
Indeed, the Exponential distribution turns out to be slightly harder for LLL, despite the initial lower defect; note that the initial defect is not necessarily good indicator of the complexity of the reduction, and we hypothesize that the matrix exponential still introduces certain additional correlations. Regarding the
Thhe MLP model adopts architccture similar to method, i.c. it samples & extended Gauss moves with the same recursive strategy, but replaces the equivariant layers with unconstrained linear layers and treats the n² entries the Gram matrix as a generic input feature vector.
10

---

Published in Transactions on Machine Learning Research (02/2025)
Ajtai lattices, while they not theoretically harder to reduce, the inverse matrix B'-T often contains wider range of values (occasionally up to 10") especially since B' takes values in [0, 1] resulting in potential challenges for a neural network, which justifies the poorer performance found. In the experiment with the Convex distribution, we observe that the gap between our method and LLL slightly decreases for lower values of d. In addition, the consistent performance gap between the MLP baseline and our method across all datasets Table I indicates the importance of adopting an equivariant design to efficiently learn solutions to this combinatorially hard problem.
Finally, Figure 5 shows how the number of steps k affects the performance of our models the Uniform datasets. In particular, we observe an asymptotic convergence towards the LLL performance as the number of steps increases, suggesting the performance gap could be closed provided enough steps are employed. Additionally, while using a larger number steps keeps improving performance monotonically, we observe a quick saturation after approximately k = n steps. This observation consistent with Proposition 4.2 which establish an upper- upper-bound bound of (n) steps to generate any unimodular matrix. Hence, we consider plausible that (n) steps are generally sufficient to achieve sulficiently low performance gap with respect to LLL.
n=8
1.75
LLL
3.0
LLL
LLL
1.50
Ours
Ours
Ours
2.5
(agbla))
1,00
1.25
2.0
legbled
3
0.75
1.5
0.50
1.0
0.25
0.5
0.00
10
Steps
Steps
Steps
Figure 5: Performance of our method at different steps vs LLL on n dimensional lattices from the Uniform distribution. The trends indicate that the performance of our models starts to saturate after about n steps; this is in line with the theoretical upper-bound of O(n) steps in Proposition 4.2
5.2 Joint Reduction of Correlated Lattices
In this section, we present results for joint reduction of correlated lattices arranged in grid, which has applications for MIMO detection as explained in Section 4.4
For data generation in our experiments, we used a 5G-compliant physical downlink shared channel (PDSCH) simulator implemented with MATLAB's 5G Toolbox [Inc. 2022b a). We used the standard wireless channel models to simulate the communication pipeline. For the sake of simplicity, we assume perfect channel estima- tion at the receiver. To get the perfect channel estimate, we used MATLAB's nrPerfectChann Estiimate function. We simulated tapped delay line (TDL) channel model with TDLA30 delay profile and Doppler shift of 100 Hx. This model represents a statistical model for the behavior that can be attributed to an indoor propagation environment. We simulated 2 x 2 and 4 x 4 MIMO system over a time-frequency grid of size 14x x 48 (i.e. 4 resource blocks stacked along the frequency axis). Since the channel matrices are complex valued, we are dealing with real-vale valued lattice basis of dimension 4 x and 8 x 8 for each time- frne-freeuency block in the 14 x 48 grid. For more details see Appendix D.3
Additionally, the MIMO detection problem is more challenging when the channel matrix B does not yield an orthogonal lattice. This happens because of the arrangements of transmit and receive antenna panels and characteristics of the propagation environment. In statistical models used for wireless communication, this effect is modelled by creating statistical correlations between rows and columns of the matrix B - see 3rd Generation Partnership Project (3GPP): ; Heath & Lozano (201)). Hence, we consider datasets generated under three correlations regimes (Low, Medium and High) using standard channel models for our evaluations.
In Table 2 we compare the convolutional model described in Section 1.4 with an LLL baseline. The bascline uses I.I.L to reduce each of the 14 x 48 lattices within a grid independently. Conversely, the encoder of our
11

---

Published in Transactions on Machine Learning Research (02/2025)
n
Correlation
Initial
LLL
Our
Low
0.99 (1.00)
0.185
0.133
Medium
2.38 (1.46)
0.117
0.123(0.126)
High
3.96 (1.80)
0.095 105)
(.131(o.16a)
Low
2.99 (1.37)
1.05 (3)33)
1.01 (0.43)
Medium
20.6 (3.34)
(..4()
4.14 (1.60)
High
23.4 (4.11)
0.56 (0.37)
6.36 (2.46)
Table 2: Performance of our convolutional model and LLL on the wireless channels lattices different correlations levels and dimensions. The table reports the average performance (and standard deviation) 10000 grids (each containing 12 x 48 correlated lattices) used for validation.
network down-samples the input grid to a 3 x 12 and, then, to a x 3 grid; finally, the decoder up-samples the intermediate features to the original resolution. During the training iterations, we gradually increase the number of steps & up to n + 1. For each experimental setting, we use a fixed training set of 20000 grids and evaluate the methods on a fixed set of 10000 grids.
Overall, our method outperforms the LLL baseline the Low correlation datasets and achieves comparable performance the other 4-dimensional datasets. Unfortunately, in the higher correlation 8- dimensional datasets, our model fails to match the LLL performance.
6 Conclusions, Limitations and Future Work
In this work, have addressed lattice reduction via deep learning methods. To this end, we have designed deep neural model outputting factorized unimodular matrices and trained it in a self-supervised manner. We have incorporated the symmetries of lattice reduction into the model by making it invariant with respect to the orthogonal group and scaling and cquivariant with respect to the hyperoctahedral group. We also proposed an archilecture to jointly reduce correlated lattices and applied it on wireless channel data.
While our neural method does not consistently outperform the popular LLL algorithm, this is the first work that demonstrates the feasibility and effectiueness of deep learning approach solve the NP-hard lattice reduction problem. The benefit of this approach is that it can be luned on specific data domains and that it can perform amortized reduction of multiple correlated lattices. Endowing classical algorithms for combinatorial optimization problems with these desirable properties is general and challenging program which finds applications in several areas. Hence, we hope that our work will inspire more research on applying neural networks to lattice problems.
Finally, our model not equivariant (on the right) the whole unimodular group but only to the hyperoc- tahedral subgroup. Therefore, do not leverage upon the complete spectrum of symmetries of the lattice reduction problem. The challenge of designing model equivariant to (Z) remains open, and represents another interesting line for future investigation.
7 Acknowledgements
We wish to thank Daniel Worral, Roberto Bondesan and Markus Peschl for their help and the insightful discussions.
12

---

Published in Transactions on Machine Learning Research (02/2025)
References
ETSI 3rd Generation Partnership Project (3GPP). Study channel model for frequency spectrum above 6 ghz. 3GPP TR 38.900, Jun, Tech. Rep., 2016.
Miklós Ajtai. Generating hard instances of lattice problems. In Proceedings of the twenty-eighth annual ACM sympostum on Theory of computing, pp. 99-108, 1996.
Miklós Ajtai. The shortest vector problem in 12 is NP-hard for randomized reductions. In Proceedings of the thirtieth onnual ACM symposium on Theory of computing, pp. 10-19, 1998.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. arXiv:1607.0644 500 2016.
Layer normalization. ar preprinl
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial opti- mization with reinforcement learning. arxiv preprint orXiv: arXim:1611.09% 1.099000 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost, Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290(2):405-221, 2021.
Michael Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.184 2021.
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph noural networks. Journal of Machine Learning Research, 24(130):1-61 61, 2023.
David Carter and Gordon Keller. Bounded elementary generation of sln (o). American Journal of Malhe- matics, pp. 673-683 073-687, 1983.
Wanshi Chen, Peter Gaal, Juan Montojo, and Haris Zisimopoulos. Fundamentals of 5G communications: connectivity for enhanced mobile broadband and beyond. McGraw-Hill New York, 2021. ISBN 978-1-260. 45999-9.
Henri Cohen. A course in computational algebraic number theory, volume 138. Springer Science & Business Media, 2013.
Haonan Duan, Pashootan Vaczipoor, Max Paulus, Yangjun Ruan, and Chris Maddison. Augment with care: Contrastive learning for combinatorial problems. In International Conference on Machine Learning, pp. 5627-5642. PMLR, 2022.
Giuseppe Alessio D'Inverno, Monica Bianchini, Maria Lucia Sampoli, and Franco Scarselli. On the ap- proximation capability of gnns in node dussificatioon/eegessss tasks. Soft Computing, 28(13) 8547, 2024.
Steven D Galbraith. Mathematics of public key cryptogrephy. Cambridge University Press, 2012.
Oded Goldreich, Daniele Micciancio, Shmuel Safra, and J-P Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Information Processing Letters, 71 1999.
Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. Knowledge distillation: A survey.
International Journal of Computer Vision, 17806)1188-1181,, 2021.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In International conference on machine learning, pp. 1737-1746. PMLR, 2015.
Arash Hassibi and Stephen Boyd. Integer parameter estimation in linear models with applications to gps.
IEEE Transactions on signal processing, 46(11):2938 2292)222,29922 1998.
Babak Hassibi and Haris Vikalo. On the sphere-decoding algorithm i. expected complexity. IEEE transactions on signal processing, 53(8):2806 2818, 2005.
13

---

Published in Transactions on Machine Learning Research (02/2025)
Robert W. Heath and Angel Lozano. Foundations of MIMO communscation. Cambridge University Press, Cambridge, United Kingdom: New York, NY, USA, 2019. ISBN 978-0-521-76228--1
Geoffrey Hinton. Distilling the knowledge in neural network. arXiv preprinl arXiv:1503.02531 2015.
Joffrey Hoffstein, Jill Pipher, and Joseph Silverman. Ntru: A ring-based public key cryptosystem. In International algorithmiic number theory symposium, pp- 267 288. Springer, 1998.
The MathWorks Inc. 5g toolbox (r2022b), 2022a. URL https: bthps://vinr wwwp://wwwwrrs..coooooooooooooie
html
The MathWorks Inc. Matlab version: 9.13.0 (r2022b), 2022b. URL
com
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint
arX:w:1611.0114, 2016.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1412. 6980, 2014.
ar preprint
A Korkine and G Zolotareff. Sur les formes quadratiques positives. Mathematische Annalen, 11(2):242 292, 1877.
Henrique Lemos, Marcelo Prates, Pedro Avelar, and Luis Lamb. Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems. In 2019 IEEE 31st International Conference Tools with Artificial Intelligence (ICTAI), pp. 879-885. IEEE, 2019.
Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational cocffi- cients. Mathemalische annalen, 261:515 034,,3344 1982.
Christos Louizos, Matthias Reisser, Tijmen Blankevoort, Eistratios Gavves, and Max Welling. Relaxed quantization for discretized neural networks. arXiv preprint arX1::1810.01875, 2018.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint Xin: 1812: 0.9902, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Morris Newman. Integral matrices. Academic Press, 1972.
Phong Q Nguyen. Hermite's constant and lattice algorithms. In The LLL Algorithm: Survey and Applica- lions, pp. 19 69. Springer, 2009.
Phong Q Nguyen and Brigitte Vallée. The LLL algorithm. Springer.
Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning solve up-complete problems: A graph neural network for decision tsp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4731-4738. 2019.
Oded Regev. On lattices, learning with errors, random lincar codes, and cryptography. Journal of the ACM (JACM), 56(6):1-40) 2009.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer- Assisted Citrrrentoo-MICC... 2015: 18th International Conference, Munich, Germany, October 5-9 2015, Proceedings, Part IIl 18, pp. 234 241. Springer, 2015.
Martin Seysen. Simultancous reduction of a lattice basis and its reciprocal basis. Combinatorica, 13(3): 363 376, 1993.
Denis Simon. Selected Applications of LLL in Number Theory, pp. 265-282 Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. ISBN 978-3-642-02295-11 doi: 10.1007 /978- 078-3-642----1 02295-1_7. URL https:
14

---

Published in Transactions on Machine Learning Research (02/2025)
Nigel Paul Smart al. Cryptography: introduction, volume 3. McGraw-Hil Hill New York, 2003.
M. Taherzadeh, A. Mobasher, and A. K. Khandani. LLL Reduction Achieves the Receive Diversity in MIMO Decoding, IEEE Transactions on Information Theory, 53(12): December 2007.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Run-csp: unsupervised learning of message passing networks for binary constraint satisfaction problems. CoRR, abs/1909.08355 2019.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advonces in neural information processing systems, 28, 2015.
Daniel E Worrall, Markus Peschl, Arash Behboodi, and Roberto Bondesan. Learning perturbations for soft- output linear mimo demappers. In GLOBECOM 2022-2022 IEEE Global Communications Conference, pp. 2218-5218. IEEE, 2022.
Dirk Wubben, Ronald Bohnke, Volker Kuhn, and K.-D. Kammeyer. MMSE-based lattice-reduction for near- ML detection of MIMO systems. In ITG Workshop on Smarl Antennas (TEEE Cal. No. 04EX802), pp. 106 113. JEEE, 2004.
Shaoshi Yang and Lajos Hanzo. Fifty Years MIMO Detection: The Road to Large-Scale MIMOs. IEEE Communications Surveys Tutorials, 17(4):1941 1988, 2015. ISSN 1553-877X.
Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Understanding straight-through estimator in training activation quantized neural nets. Xrvv preprint arXiv: 1903. 05662. 2019.
15

---

Published in Transactions on Machine Learning Research (02/2025)
A The LLL Algorithm
In this section, we describe the Lenstra-Lonstra-Lováss (LLL) algorithm for lattice reduction (Lenstra et al. 1982 in details. Let B E (R) be a basis of a lattice and denote by B the orthogonal basis of R" obtained via the Gram-Schmidt algorithm applied to B. For each i, consider moreover
Ma. = b, bj
(10)
|16]
Definition A.1. A basis B GL) is ridgeed if for all >> j:
I S 2
| 11
Size Condilion
Locász Condilion
The following is a bound on the orthogonality defect for Siegel-reduced bases. Lemma A.2 Lenstra et al. (9822) ) If Siegel-reduced then:
6(B) S u(n-1)
(11)
The LLL algorithm finds a Siegel-reduced basis of an intogral lattice A S Z" S R starting from an arbitrary basis B E GL,, (RR)2ax (see Algorithm [] It can be seen that the algorithm requires O(n" log 3) elementary arithmetic operations, where B max; [bil], and therefore has polynomial complexity (Corollary 17.5.4 in Galbraith 2202
Algorithm LLL Algorithm
Require: Basis of an (integral) lattice B GL, (R) Znxn
Ensure: Siegel-reduced basis B
3 Gram-Schmidt((B
k 2
while h < do
for j = k - to do
if
|k,l > 1/2 then
by - by [uR,s]b]
B" + (chmid)c
end if
end for if
1 Hi.--1) then
keko k-ki k+1
else
Swap by and b
+ max 2)
B* + Gram- Scham-)cmmd
end if end while
16

---

Published in Transactions on Machine Learning Research (02/2025)
B Theoretical Results
B.1 Proof of Main Result
Proposition B.1. For n 2 3, every matriz in SLn is product of at most 4n+551 extended Gauss moves.
Proof. Pick Q (Z), Note first that the non-zero entries of each row and each column of Q are coprime since they can be arranged in an integral linear combination equal to det(Q) = 1. Next, consider the last row of Q, denoted by 01 = Qn. Un = Qn. We would like to show that the non-zero entries among u1.-." -4n-1 can be made coprime by multiplying Q on the right by most one (non-extended) Gauss move. If un O, this true already for Q by the above observation. Suppose that Un A If there are less than two indices 1 1 i such that u, # O, we replace one vanishing u, with un by multiplying Q on the right by (non-extended) Gauss move and obtain the desired result. Otherwise, assume without loss of generality that "n + 0 and consider some E Z such that:
t = mod all the primes dividing all the non-zero u, for i E
1}:
/ mod all the primes dividing all the non-zero uy for i E (2. , 1} but not dividing u1-
Then the non-zero integers among U1 tug ug Un-1 are coprime, desired.
We therefore assume that u1," Un coprime. By the Bézout's identity, there exist integers dn 0p-1 such that E; aru; 1 un- By multiplying Q on the right by the extended Gauss move
d1
0
:
(12)
we reduce to the case un 1. By further multiplying on the right by the extended Gauss move
1
(13)
0
M
we reduce to the case where the last row is (0, ... 0, 1). Similarly, by multiplying by another move on the left, the last column reduces -0,
0, 1), obtaining a matrix of the form:
(14)
0
... 0 1
where A (Z).
Putting everything together, via induction with 4n - 12 extended Gauss moves we arrive at matrix of the form A' @ J, where E (Z) and the identity matrix of dimcnsion n - 3. Since by Carter & Koller (1983) any matrix in SZy(Z) can written as a product 63 (non-extended) Gauss moves, this concludes the proof.
B.2 Constructing Equivariant Maps
In this section, we explore classes of maps that obey an equivariance property closely related our model. In particular, we prove impossibility result for multi-linear maps. To this end, recall that the input of our
17

---

Published in Transactions on Machine Learning Research (02/2025)
model is (invertible) matrix, which can be seen element of the representation R of GL, which the latter acts by right matrix multiplication. Therefore, it is convenient, to describe the equivariant maps in this context.
Proposition B.2. Consider (Z) -qquivvarrri map & R + R Then there crists a map / Raxx + gn such that the i-th column of (BB) is given by
flb.. bn bi. bb-
(15)
where b. denotes the corresponding column of B. Moreower, f satisfies the following two conditions for all B = (b,," .. ::
f(bi," .n) (bb,,b2," d,. bi + dz- b242. for all S < n,
f(b ,b)) + f(bn,b, br. "h,,",,,-))) f(b1 + buy b.. ,a))
Any equivariant map yp is obtained from an f satisfying the above conditions.
Proof. It is well-known that GLm (Z) is generated as group by the following two matrices
Newmaan
1972
0
0
0
1
0
1 0
0
0
0
0
0
S
0
1
T
0
0
(16)
Given a matrix E R"xn BS cycles the columns of from right to left, while BT replaces the second column with itself summed with the first one. Now, pick map y : RRxn RRax and consider its column- wise components ii i.e, p(B); (B(B), where the subscript denotes the column of the matrix. Equivariance w.r.t. to S is equivalent to sp; (B) coinciding with Φ1 computed on B with its columns cycled by i steps. This implies the existence of f as in the statement. Equivariance w.r.t. T is then equivalent to the two conditions in the statement.
Therefore, the problem of classifying equivariant maps reduces to solving the functional equations for f from Proposition B.2 Some solutions can be found by forcing f to be linear and dependent only on the first column i..,, J(B) = fbb,) ) by abuse of notation, with f linear. These are all the maps that are equivariant the whole (R). The next step looking for multi-linear f which is dependent on the first column alone. In this the two conditions translate in the following ones:
f(b1, b., . ,,, by, bit11 ... bn) = for all 1 isi< n,
f(bn, b.... ...
bh-1)) f(b, be. b.).
The second condition above implies inductively that O, meaning that there are no non-trivial multi-linear equivariant maps.
18

---

Published in Transactions on Machine Learning Research (02/2025)
C Implementation Details
We implement the model described by Equation where ui are simple MLPs which include single lincar layer (without bias) followed by a soft-chresoold activation a(x) = [eLU([ - [6]) sign(x).
Because the n elements on the diagonal of the Gram matrix and of the intermediate features G are sign- invariant, we also add Equation a simple message passing layer between them similar Deep-Set: [G++ 2 ((G)))) vy are simple MLPs, including a normal linear layer followed by a standard ReLU activation.
E ('c byy); where [G']s: is the i-th element in the diagonal of G' while v/g and
The single lattice architecture inchudes message passing layers and a final 2-layers MLP processing the features of each of the n² entries output the extended Gauss move. All intermediate features use channels for each of the n² entries.
In the convolutional architectures, downsampling is performed in two message passing layers which employ convolution with stride 4; upsampling is also performed in two steps by interlcaving two message passing layers using transposed convolution with stride 2 and two nearest neighbors interpolations. All intermediate features use at most 10 channels for each of the n² entries in each pixel in the grid.
To improve expressiveness, we augment the imput features with a matrix containing the projection coefficients bi and matrix containing their quantization [pt]]-
Pi
b
Moreover, in order to mitigate the instability due to discretization when sampling an extended Gauss move, we include normalization layer (Ba et al. 2016)] in the socond-last activations. The number of extended Gauss moves is set & 2n in the single lattice experiments and k n++ in the joint lattice reduction ones. Training is performed via the Adam optimizer (Kingma & Ba 2014
19

---

Published in Transactions on Machine Learning Research (02/2025)
D Lattice Reduction in Wireless Communication
We review the basic building blocks a conventional wireless communication system and discuss where lattice reduction fits into the problem.
D.1 Wireless Processing Chains
The transmitter maps the binary data to the constellation points using modulator block that exploits certain modulation scheme, such as Quadrature Amplitude Modulation (QAM). The most frequently used QAM constellations consists of points arranged in a square grid with equal vertical and horizontal spacing, for e.g,, 4-QAM, 16-QAM, and 64-QAM, see Fig. 6
GAH4
QAM-16
GAM-64
Fm
Im
Ins
Figure 6: An example of QAM constellations
The QAM symbols at time slot are mapped individual resources on the resource grid as in Fig.
One slot
Resource Element (1.) Resource Grid
Blook seboorreers
Resource of Nesourve
timm--oots
Figure An example of time-frequency resource grids used in wireless technology which includes three resource blocks.
20

---

Published in Transactions on Machine Learning Research (02/2025)
In the case of MIMO, symbols from QAM constellation Ω gets mapped to each of the individual resources
the grid, which are then transmitted over antennas on the transmit side. Fig. g depicts 2 x 2 MIMO system, where x E S22 represents the transmit vector for an individual resource element, consisting of QAM constellation symbols pertaining to each of the transmit antennas.
Rx
Tx
y
B
X
b
Y1
X1
b21
b12
2/2
X2
b22
Receive antennas
Transmit antennas
Figure 8: An example of MTMO communication system
D.2 Lattice Reduction for MIMO Detection
Consider a MIMO system with n, transmit and n, receive antennas. For simplicity, we assume n; = 72 n. The transmit vector the modulated bit-stream using a constellation (see above). Therefore, the transmit vector is given by 1 The wireless processing chain maps to signal that is transmitted over n antennas. On the receiver side, after some processing, the effect of the channel can represented by the channel matrix 3 which relates the observed vector y to x as:
== Bx + N,
where is the additive noise N(O, T²)). The goal is find x the constellation using the above equation. There are various approaches in the literature, but we sketch linear solution based on lattice reduction, The classical linear solution to this problem is the minimum-mean squared error (MMSE) solution, namcly:
SMSE = On B B)
where Qg quantizes its input to the nearest constellation point. The MMSE linear MIMO detection has in general large performance gap with respect the Maximum Likelihood (MT.) solution. However, it has been shown that the lattice reduced version of B provides closed performance the ML solution (Wubben et al. 2004). It is enough to find the unimodular matrix U such that - is the lattice-reduced version of B. Then we plug BU-1 to the linear MMSE solution and quantized to the transformed lattice UΩ:
& MMSE = Qn (U-'Qun ("
Not only this improves the performance, measured in terms of bit error rate, but it has been shown that it can achieve asymptotic information thcoretic optimality (Taherzadeh et al. 2007). This is the main motivation for using lattice reduction in MTMO setting.
Ii wireless literaturee, the channel typically denated by However, be consistent. with our lattice notation, we
21

---

Published in Transactions on Machine Learning Research (02/2025)
D.3 Wireless Simulation
For our simulation, we have used the standard TDLA30 channel model as specified in the 3GPP document TS 38.101-4 Annex B.2.1 with a Doppler shift of 100 Hz. In this model, the wireless channel is modelled by its impulse response. The impulse response of the channel is specified by a fixed number of delays, each corresponding to communication path, and their respective gain. TDLA30 has 12 distinct paths with maximum delay as 290ns. Each path gain follows Rayleigh distributiin with the power gain specified in Table B.2.1.1-2. The correlations are modelled using the Kronecker model. Each correlation profile is specified by reccive and transmit side correlation matrix Ryz and Rix- The correlated channel is given
R B(R
We use the pre-defined channel profiles for our experiments.
22


Reviews:
[{"review_id": "XHOoqWWjYZ", "reviewer": "Reviewer_457A", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper is extremely well-written an organized. The presentation is well-reasoned, well-organized, and cleanly written.\n- The paper features a good balance of new pure theoretical developments with Prop 4.2 and the developments of section 4.2.\n- The numerical results give support to the use of self-supervised learning to solve this combinatorial problem. In some settings, the self-supervised model is competitive with the LLL method.\n- I quite like how the authors designed a geometric network that is invariant/equivariant w.r.t. the algebraically interesting group $GL_n(\\mathbb Z)$. There is a lot of geometric ML work on groups that are less algebraically subtle (e.g. $SO_n(\\mathbb R)$), and this reviewer appreciates that the authors were up to the challenge.\n\nWeaknesses\n- The benefits of using the proposed self-supervised method over the state-of-the-art are nebulous. The actual performance of the trained network is at best 'in the same ball park' as the state of the art method and, at worse, considerably worse (Table 1).\n- The authors ultimately fail to construct a network that is equivariant/invariant w.r.t. the full group of interest (Right unimodular equivariance). This is a minor criticism, however, given the algebraic subtlety of $GL_n(\\mathbb Z)$, as discussed in the strengths section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the application of a self-supervised deep neural network to the problem of lattice reduction, where the network has bespoke invariance/equivariance modes built-in that suit the lattice reduction problem.  More specifically, they propose a novel deep learning model which is invariant and equivariant to various discrete groups for lattice reduction outputting unimodular matrices via a self-supervised objective. They compare their method to the state-of-the-art method the Lenstra–Lenstra–Lovász method, a non-ML method. Finally they show that they show that their network may be trained simultaneously on on several lattices in parallel which may yield a good performance/complexity tradeoff if the lattices are correlated.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think that the work would be strengthened with a discussion of difficulties working over $GL_n(\\mathbb Z)$ and, in particular what the 'gap' is between full right modular equivariance and hyperoctahedral equivariance. What are some elements of the $GL_n(\\mathbb Z)$ that are 'far away' from elements of $H_n$? What properties of $GL_n(\\mathbb Z)$ (specifically) make it subtle or hard to design around? Indeed it does seem to be a subtle group, but some exploration of its subtleties and why they lead to difficulties would be a valuable addition.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "F7UYJJeK34", "reviewer": "Reviewer_sW3q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- The paper develops a differentiable approach to solve a problem in combinatorial optimization\n- The paper clearly describes how various symmetries involved with lattice reduction can be used to design a differentiable architecture (I am specifically talking about Section 4.2)\n- The experiments using wireless communications could be of interest to the applied members of the TMLR community\n\n# Weaknesses\n\n- The empirical results provided in Table 1 suggests that using machine learning may not be the best approach for lattice reduction. Is the poor performance due to the size of the models considered in the paper? Is the bad performance due to a fundamental limitation? \n\n- The proposed method (or algorithm) is highly specialized due to the various assumptions involved in the lattice reduction problem considered in the paper. As a result, I am not convinced about the general message that the TMLR audience might take away after reading the paper. I understand that the paper claims that the proposed method is the first to apply learning to lattice reduction but the learning component seems to be very problem-specific and task-specific. \n\n- The proposed method is not computationally any less burdensome than the baseline LLL approach.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper describes a method for lattice reduction using a differentiable model that includes a learnable graph neural network (GNN. Lattice reduction refers to a mapping from general linear group over reals to general linear group over integers. The neural model is optimized in a self-supervised manner by minimizing the orthogonality defect of basis vectors of a lattice. The paper uses symmetries of lattice reduction to come up with an implementation that works on small-scale problems. The paper empirically analyzes the proposed algorithm with synthetic datasets and on a setup that involves wireless communications.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Are the poor performance results of the proposed method due to model size limitation, data limitation or something fundamental?\n\n2. Why would knowledge distillation noted in the paper be a good method to simplify computational burden? Especially in light of Question 1 above.", "broader_impact_concerns": "No concerns were noted in the paper. However, the reviewer believes this maybe unnecessary although the authors are encouraged to consider including a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3HIivXNzGD", "reviewer": "Reviewer_YZRS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors propose an interesting approach to solve a highly relevant problem in practice. As far as I can tell, the methodology is sound, and there are a few places where novel ideas are introduced for designing the architecture tailored to this specified problem. The paper is also well-written and easy to follow.\n\nIn terms of weaknesses, the authors insist on the benefit of not using data. But I imagine there are data simply already existing for any particular application, or in a database collected by mathematicians online. It seems to me rather wasteful to not use these information for e.g., learning better Gauss moves or other places where heuristic choices are made if one has access to some $(B,Q)$ pairs. Even warm-starting from the output of LLL and fine-tuning with NN seems like a good idea. I'm a bit missing on the motivation of not using any data or existing knowledge about the solution at all, and training in a fully agnostic way, which also requires retraining for new problems / hard to generalize across instances.\n\nThe performance of the algorithm, as judging from e.g., Table 1, isn't much better than LLL, which seems to suggest either more inductive bias in the architecture is required to aid the optimization, or some form of ``supervised learning\" is needed for the NN-based methodology to work (also related to my previous point).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors consider solving the lattice reduction problem, a combinatorial optimization problem, with deep learning. Namely, given a lattice basis as input, train a neural network to output a base-change uni-modular matrix, where the reduced basis is as close to orthogonal as possible. The crucial feature of the setup is (1) the algorithm does not rely on solved problem solution during the learning process; (2) equivariant and invariant symmetry in the mapping is baked into the architecture which form a better ansatz for neural network parametrization.\n\nThe approach involves minimizing the orthogonality defect for $B\\varphi_\\theta(B)$ where $\\varphi_\\theta(B)$ is the output of a parametrized NN which is a discrete uni-modular matrix acting on a given basis $B$ of a lattice. In order for the output to be valid,  the $\\varphi$ is modeled as a sequence of successive Gauss moves with appropriate rounding. Additionally, three types of invariance/equivariance properties are incorporated by either input transformation or leveraging the GNN architecture and restricting to the hyperoctahedral group. \n\nThe result is compared against LLL, a classical algorithm for approximately solving the problem and extension that can jointly solve multiple correlated instances to amortize the computation cost is discussed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "If $\\varphi$ is the GNN as defined in Section 4.2, and $Q$ is a product of recursive transformations as defined in eqn (6), doesn't backpropagation requires unrolling all the updates and is memory-intensive, at least if the whole pipeline is trained end-to-end? I'd appreciate some clarification.\n\nGiven that (1) there are various relaxations made so one can work with optimizing over discrete state space; (2) Proposition 4.2 is only a representation result, and not about whether the algorithm will find the best matrix for objective eqn (5) in such a space, any guarantee on the output given by the proposed algorithm with the chosen parametrization / approximation is desirable. To me, computational complexity such as those given in Section 4.3 is a bit out of context without any quantification on such an error.\n\nMinor comment:\n\n- Section 2: \"rises differentiability challenges\" -> raises\n\n- Figure 3, I think you are missing a normalization block after the Gram matrix block\n\n- Last sentence before Section 5: you probably mean \"the cost per lattice is\npotentially reduced\"", "broader_impact_concerns": "No concerns involved.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers are generally satisfied after the discussion process and recommend acceptance. They do note that the performance of the proposed method is not very high and that results with a supervised neural network baseline/upper bound is missing.
Decision: Accept (poster)