Introduction
Generalized Linear Models (GLMs) are foundational tools in statistical regression, spanning applications from simple linear regression to logistic and Poisson models. A critical requirement in traditional GLM implementation is the pre-specification of a "link function"—such as the sigmoid function in logistic regression—which maps linear predictors to observed data. However, selecting an incorrect link function can lead to significant bias in parameter estimates. While methods exist to learn the link function, they often result in non-convex optimization problems prone to local minima.
This paper, originally presented at AISTATS 2015, introduces a novel framework that allows for parameter estimation even when the link function is unknown, all while maintaining global convexity.
Methodology: Jointly-Convex Optimization
The authors propose a jointly-convex, regularized loss functional where the link function is treated as a variable to be optimized alongside the weight vector. This approach relies on several key technical components:
- Matching Bregman Divergences: These are used to construct a loss function that remains convex despite changes in the link function.
- H¨older Convex Functions: The search space for the link function is restricted to functions with H¨older continuous gradients, providing a flexible but regularized space.
- GradMaPr Algorithm: The "Gradients by Marginalization and Projection" algorithm manages the infinite-dimensional space of potential link functions.
To ensure computational efficiency, the framework utilizes the Pool Adjacent Violators (PAV) algorithm and the Alternating Direction Method of Multipliers (ADMM). This keeps the cost per iteration at $O(N \log N)$, comparable to standard GLM solvers.
The optimization can be performed using standard first-order methods. The authors provide specific implementations for Gradient Descent and its accelerated counterpart to achieve optimal convergence rates.
Experimental Evaluation
The proposed method was evaluated across two distinct domains:
- UCI Regression Benchmarks: Tasks including communities, concrete, housing, parkinsons, and winequality were used to measure Root Mean Square Error (RMSE).
- Learning to Rank (LETOR 4.0): The MQ2007 dataset served as a real-world test case where the exact link function for relevance scores is typically unknown.
Key Results and Insights
The most significant finding is the proof of joint convexity, guaranteeing that gradient-based methods will reach a global optimum. Furthermore, the model naturally identifies an interval of permissible values for predictions due to the unknown nature of the link; simple averaging of this interval provides a robust point estimate.
On the MQ2007 ranking task, the method achieved high Normalized Discounted Cumulative Gain (NDCG) scores, outperforming or matching state-of-the-art baselines like SlIsotron. In UCI regression tasks, the performance was competitive with standard logistic regression even without prior knowledge of the "correct" link function.
Limitations and Future Directions
While powerful, the vast space of possible link functions introduces a risk of overfitting on small datasets. Future work may involve quantifying how the function space should scale with dataset size. Additionally, while the current heuristic of averaging predicted intervals is effective, exploiting specific analytic properties (such as smoothness) of the link function could further improve convergence and prediction accuracy.
Summary updated