Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach
cs.LG, cs.AI, cs.DM
Submitted: 2023-11-14
Updated: 2025-02-10
Comments: Accepted at TMLR
Journal ref: Transactions on Machine Learning Research, 2025
License: http://creativecommons.org/licenses/by/4.0/
The gist: Lattice reduction is a combinatorial optimization problem aimed at finding the most orthogonal basis in a given lattice.
Terminology
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.
Sources
- Layer Normalization
- Neural Combinatorial Optimization with Reinforcement Learning
- Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
- Distilling the Knowledge in a Neural Network
- Categorical Reparameterization with Gumbel-Softmax
- Adam: A Method for Stochastic Optimization
- Relaxed Quantization for Discretized Neural Networks
- Invariant and Equivariant Graph Networks
- Graph Neural Networks for Maximum Constraint Satisfaction
- Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis