Algorithms
==========

This section summarizes the core algorithms implemented in
:mod:`uniPairs.estimator`.

------------------------------------------------------------

Summary
-------

We describe three procedures:

- **TripletScan**: interaction screening via Triplet regressions
- **uniPairs-2stage**: implemented in ``UniPairsTwoStage``
- **uniPairs**: implemented in ``UniPairsOneStage``

------------------------------------------------------------

TripletScan
-----------

.. admonition:: Algorithm: TripletScan
   :class: note

   **Input**

   - Standardized design matrix :math:`X \in \mathbb{R}^{n \times p}`
   - Response vector :math:`Y \in \mathbb{R}^n`
   - Pair index set :math:`\mathcal{P}`

   **Procedure**

   1. For each :math:`(j,k) \in \mathcal{P}`:
   
      - Fit the local regression

        .. math::

           Y = \beta_{0,jk} + \beta_{j,jk} X_j + \beta_{k,jk} X_k + \beta_{jk,jk} (X_j \odot X_k) + \varepsilon
        
      - Record the two-sided *t*-test p-value :math:`p_{jk}` for
        :math:`\beta_{jk,jk}`.

   2. Sort p-values increasingly and define
      :math:`\ell_r = \log \widehat p_{(r)}`.

   3. Apply the largest log-gap rule:

      .. math::

         \widehat r
         = \arg\max_{1 \le r < M}
           \left( \ell_{r+1} - \ell_r \right),
         \quad
         \widehat{\Gamma}
         = \{ (j,k) \in \mathcal{P} :
         p_{jk} \le p_{(\widehat r)} \}

   **Output**

   - Selected interaction set :math:`\widehat{\Gamma}`

------------------------------------------------------------

uniPairs-2stage
---------------

.. admonition:: Algorithm: uniPairs-2stage
   :class: note

   **Input**

   - Design matrix :math:`X \in \mathbb{R}^{n \times p}`
   - Response :math:`Y \in \mathbb{R}^n`
   - Hierarchy level
     :math:`h \in \{\text{strong}, \text{weak}, \text{none}\}`

   **Procedure**

   1. Standardize each column of :math:`X`.

   2. Fit **UniLasso** on :math:`(X, Y)` to obtain:
      - Main-effects active set :math:`\widehat S_M`
      - Prevalidated predictions :math:`\widehat Y^{(1)}_{\mathrm{PV}}`

   3. Run **TripletScan** on :math:`(X, Y)` to obtain
      :math:`\widehat{\Gamma}`.

   4. Restrict eligible interaction pairs
      :math:`\mathcal{E}` according to hierarchy level :math:`h`
      and :math:`\widehat S_M`.

   5. Compute residuals:

      .. math::

         R = Y - \widehat Y^{(1)}_{\mathrm{PV}} .

   6. Fit a **Lasso** of :math:`R` on selected interactions

      .. math::

         \{ X_j \odot X_k :(j,k) \in \widehat{\Gamma} \cap \mathcal{E} \}.

   7. Recover coefficients on the original scale and obtain
      final active sets
      :math:`\widehat S_M^{\text{final}}` and
      :math:`\widehat S_I^{\text{final}}`.

   **Output**

   The predictive function

   .. math::

      \widehat f(x)
      = \widehat\alpha_0
      + \sum_{j \in \widehat S_M^{\text{final}}}
        \widehat\alpha_j x_j
      + \sum_{(j,k) \in \widehat S_I^{\text{final}}}
        \widehat\alpha_{jk} x_j x_k .

------------------------------------------------------------

uniPairs (one-stage)
--------------------

.. admonition:: Algorithm: uniPairs
   :class: note

   **Input**

   - Design matrix :math:`X \in \mathbb{R}^{n \times p}`
   - Response :math:`Y \in \mathbb{R}^n`

   **Procedure**

   1. Standardize each column of :math:`X`.

   2. Run **TripletScan** on :math:`(X, Y)` to obtain
      :math:`\widehat{\Gamma}`.

   3. Form the augmented design matrix

      .. math:: \widetilde X = [X, X_{\widehat{\Gamma}}], \quad X_{\widehat{\Gamma}} = \{ X_j \odot X_k : (j,k) \in \widehat{\Gamma} \}

   4. Fit **UniLasso** on :math:`(\widetilde X, Y)`.

   5. Recover coefficients on the original scale and obtain
      active sets :math:`\widehat S_M` and :math:`\widehat S_I`.

   **Output**

   The predictive function

      .. math:: \widehat f(x) = \widehat\alpha_0 + \sum_{j \in \widehat S_M} \widehat\alpha_j x_j + \sum_{(j,k) \in \widehat S_I} \widehat\alpha_{jk} x_j x_k .

------------------------------------------------------------

Practical Recommendation
------------------------

In practice, **uniPairs-2stage** is recommended as the default choice
when main effects are believed to be present and strong or weak hierarchy
assumptions are appropriate.

The **uniPairs** one-stage procedure provides a flexible alternative
when departures from hierarchy are expected.