# Learning Hierarchical Interactions at Scale: A Convex Optimization Approach

arXiv: https://arxiv.org/abs/1902.01542 · HTML: https://mlsanity.com/paper/1902.01542/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2019.

## Built on by (most cited first, 4 of 4)

- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [Predicting Census Survey Response Rates With Parsimonious Additive Models and Structured Interactions](https://mlsanity.com/paper/2108.11328/) (2021)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [Efficient Model Selection for Predictive Pattern Mining Model by Safe Pattern Pruning](https://mlsanity.com/paper/2306.13561/) (2023)

## Abstract (arXiv)

In many learning settings, it is beneficial to augment the main features with pairwise interactions. Such interaction models can be often enhanced by performing variable selection under the so-called strong hierarchy constraint: an interaction is non-zero only if its associated main features are non-zero. Existing convex optimization based algorithms face difficulties in handling problems where the number of main features p ~ 103 (with total number of features ~ p2). In this paper, we study a convex relaxation which enforces strong hierarchy and develop a highly scalable algorithm based on proximal gradient descent. We introduce novel screening rules that allow for solving the complicated proximal problem in parallel. In addition, we introduce a specialized active-set strategy with gradient screening for avoiding costly gradient computations. The framework can handle problems having dense design matrices, with p = 50,000 (~ 109 interactions)---instances that are much larger than current state of the art. Experiments on real and synthetic data suggest that our toolkit hierScale outperforms the state of the art in terms of prediction and variable selection and can achieve over a 4900x speed-up.