Learning Hierarchical Interactions at Scale: A Convex Optimization Approach
In many learning settings, it is beneficial toaugment the main features with pairwise in-teractions. Such interaction models can beoften enhanced by performing variable selec-tion under the so-calledstrong hierarchycon-straint: an interaction is non-zero only if itsassociated main features...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
International Machine Learning Society
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130384 |
| _version_ | 1826201222517882880 |
|---|---|
| author | Hazimeh, Hussein Mazumder, Rahul |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Hazimeh, Hussein Mazumder, Rahul |
| author_sort | Hazimeh, Hussein |
| collection | MIT |
| description | In many learning settings, it is beneficial toaugment the main features with pairwise in-teractions. Such interaction models can beoften enhanced by performing variable selec-tion under the so-calledstrong hierarchycon-straint: an interaction is non-zero only if itsassociated main features are non-zero. Ex-isting convex optimization-based algorithmsface difficulties in handling problems wherethe number of main featuresp∼103(withtotal number of features∼p2). In this pa-per, we study a convex relaxation which en-forces strong hierarchy and develop a highlyscalable algorithm based on proximal gradi-ent descent. We introduce novel screeningrules that allow for solving the complicatedproximal problem in parallel. In addition,we introduce a specialized active-set strategywith gradient screening for avoiding costlygradient computations. The framework can handle problems having dense design matri-ces, withp= 50,000 (∼109interactions)—instances that are much larger than state ofthe art. Experiments on real and syntheticdata suggest that our toolkithierScaleout-performs the state of the art in terms of pre-diction and variable selection and can achieveover a 4900x speed-up. |
| first_indexed | 2024-09-23T11:48:08Z |
| format | Article |
| id | mit-1721.1/130384 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:48:08Z |
| publishDate | 2021 |
| publisher | International Machine Learning Society |
| record_format | dspace |
| spelling | mit-1721.1/1303842022-10-01T06:09:25Z Learning Hierarchical Interactions at Scale: A Convex Optimization Approach Hazimeh, Hussein Mazumder, Rahul Sloan School of Management Massachusetts Institute of Technology. Operations Research Center In many learning settings, it is beneficial toaugment the main features with pairwise in-teractions. Such interaction models can beoften enhanced by performing variable selec-tion under the so-calledstrong hierarchycon-straint: an interaction is non-zero only if itsassociated main features are non-zero. Ex-isting convex optimization-based algorithmsface difficulties in handling problems wherethe number of main featuresp∼103(withtotal number of features∼p2). In this pa-per, we study a convex relaxation which en-forces strong hierarchy and develop a highlyscalable algorithm based on proximal gradi-ent descent. We introduce novel screeningrules that allow for solving the complicatedproximal problem in parallel. In addition,we introduce a specialized active-set strategywith gradient screening for avoiding costlygradient computations. The framework can handle problems having dense design matri-ces, withp= 50,000 (∼109interactions)—instances that are much larger than state ofthe art. Experiments on real and syntheticdata suggest that our toolkithierScaleout-performs the state of the art in terms of pre-diction and variable selection and can achieveover a 4900x speed-up. United States. Office of Naval Research (Grants ONR-N000141512342, ONR-N000141812298) National Science Foundation (U.S.) (Grant NSF-IIS1718258) 2021-04-06T13:49:15Z 2021-04-06T13:49:15Z 2020-06 2021-04-05T15:15:07Z Article http://purl.org/eprint/type/ConferencePaper 2640-3498 https://hdl.handle.net/1721.1/130384 Hazimeh, Hussein and Rahul Mazumder. “Learning Hierarchical Interactions at Scale: A Convex Optimization Approach.” Paper in the Proceedings of Machine Learning Research, 108, 23rd International Conference on Artificial Intelligence and Statistics (AISTATS) 2020, Palermo,Italy, June 3-5 2020, International Machine Learning Society © 2020 The Author(s) en http://proceedings.mlr.press/v108/hazimeh20a.html Proceedings of Machine Learning Research Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf International Machine Learning Society Proceedings of Machine Learning Research |
| spellingShingle | Hazimeh, Hussein Mazumder, Rahul Learning Hierarchical Interactions at Scale: A Convex Optimization Approach |
| title | Learning Hierarchical Interactions at Scale: A Convex Optimization Approach |
| title_full | Learning Hierarchical Interactions at Scale: A Convex Optimization Approach |
| title_fullStr | Learning Hierarchical Interactions at Scale: A Convex Optimization Approach |
| title_full_unstemmed | Learning Hierarchical Interactions at Scale: A Convex Optimization Approach |
| title_short | Learning Hierarchical Interactions at Scale: A Convex Optimization Approach |
| title_sort | learning hierarchical interactions at scale a convex optimization approach |
| url | https://hdl.handle.net/1721.1/130384 |
| work_keys_str_mv | AT hazimehhussein learninghierarchicalinteractionsatscaleaconvexoptimizationapproach AT mazumderrahul learninghierarchicalinteractionsatscaleaconvexoptimizationapproach |