Technical Summary: Constrained Variable Projection for Structured Problems

1. Problem Statement

Modern data science frequently involves fitting models with two distinct types of variables: a block of variables ($w$) that enters the loss function linearly (or quadratically), and a block of nonlinear variables ($\theta$) that control features, representations, or physical parameters. While classical Variable Projection (VarPro) methods effectively eliminate linear variables to reduce the dimensionality of separable nonlinear least-squares problems, they are primarily designed for unconstrained settings.

This paper addresses the gap in handling constrained scenarios where the remaining nonlinear variables $\theta$ are subject to convex constraints (e.g., sparsity, norm bounds, simplex constraints). These constraints are essential in applications like dictionary learning, blind deconvolution, and few-shot learning but render standard VarPro inapplicable. The core challenge is to eliminate the linear variable $w$ exactly while optimizing $\theta$ over a convex feasible set $C$, without resorting to naive joint optimization which suffers from poor conditioning and higher dimensionality.

2. Methodology

2.1 Bilevel Interpretation and Reduction

The authors reinterpret the constrained VarPro problem as a collapsed bilevel optimization problem:
$$\begin{aligned} \min_{\theta \in C} \quad & f_U(\hat{w}(\theta), \theta) \\ \text{s.t.} \quad & \hat{w}(\theta) \in \arg\min_{w} f_L(w, \theta) \end{aligned}$$
where the lower-level problem $f_L$ is a structured least-squares problem. Since the lower-level problem has a closed-form solution (via the Moore-Penrose pseudoinverse), the variable $w$ is eliminated, yielding a reduced objective function $f(\theta) = f_U(\hat{w}(\theta), \theta)$ defined solely on the constrained set $C$.

2.2 Reduced Gradient Derivation

A critical contribution is the derivation of exact reduced-gradient formulas (hypergradients) for the reduced objective. The authors avoid differentiating naively through ill-conditioned normal equations. Instead, they utilize:

1. Closed-form lower-level solutions: $\hat{w}(\theta) = M(\theta)^+ y(\theta)$.
2. Implicit differentiation: By differentiating the first-order stationarity conditions of the lower-level problem, they derive the sensitivity $\partial_\theta \hat{w}(\theta)$.
3. Vector-Jacobian Products (VJPs): The final gradient $\nabla f(\theta)$ is computed efficiently by combining the direct gradient of the upper-level objective with the chain rule term involving the Hessian of the lower-level problem, evaluated via automatic differentiation.

The derived gradient formula is:
$$\nabla f(\theta) = \nabla_\theta f_U|_{(\hat{w}, \theta)} - \nabla^2_{w\theta} f_L|_{(\hat{w}, \theta)}^\top (M_L^\top M_L)^{-\top} \left[ M_U M_L^+ y_L - y_U \right]$$
In the standard case where the upper and lower operators are identical, the coupling term vanishes, simplifying the gradient to the partial derivative with respect to $\theta$.

2.3 Algorithm: Constrained Regularized Variable Projection (CR-VarPro)

To solve the reduced constrained problem, the authors propose a projection-free conditional-gradient (Frank-Wolfe) method.

• Feasible Set Structure: The set $C$ is assumed to factorize as $C = C_A \times C_B$, where $C_A$ is compact and convex, and $C_B$ is unconstrained ($\mathbb{R}^{p_B}$).
• Block Linear Minimization Oracle (BLMO): Standard Frank-Wolfe methods fail on unbounded sets. The proposed BLMO handles this by:
  • Solving a linear minimization oracle over the compact set $C_A$.
  • Performing a normalized gradient descent step (minimizing over a unit ball) for the unconstrained block $C_B$.
• Convergence: The algorithm updates $\theta$ using a line search step size. Theoretical analysis establishes convergence to first-order stationary points under standard smoothness and compactness assumptions, with a convergence rate dependent on the Frank-Wolfe gap.

2.4 Extensions to Structured Variables

The framework is extended to cases where the eliminated variable $w$ is constrained to a lower-dimensional set $\mathcal{W}$ (e.g., an affine subspace or a differentiable manifold). The authors prove that for the lower-level solution map to be globally differentiable, the constraint set $\mathcal{W}$ must be affine. This ensures the validity of the gradient-based approach for structured problems like convolutional transforms.

3. Key Contributions

1. Formulation: The paper formulates constrained variable projection as a collapsed bilevel optimization problem, unifying VarPro with constrained optimization.
2. Gradient Formulas: It derives explicit, exact reduced-gradient formulas that leverage automatic differentiation and closed-form lower-level solvers, avoiding numerical instability associated with differentiating through normal equations.
3. Algorithm Design: It proposes a tailored conditional-gradient algorithm (CR-VarPro) that combines Frank-Wolfe steps for constrained blocks with normalized gradient steps for unconstrained blocks, ensuring the method is projection-free and efficient for sets where linear minimization is cheaper than projection.
4. Theoretical Guarantees: Convergence to first-order stationary points is established under standard assumptions.
5. Differentiability Analysis: A proposition characterizes the differentiability of the lower-level solution map, showing that global differentiability essentially requires the constraint set on the eliminated variable to be affine.

4. Experimental Results

The authors evaluate CR-VarPro against standard projected gradient descent on joint optimization baselines across four data-science applications:

• Sparse Autoencoding: On MNIST and CIFAR10, CR-VarPro achieved lower test reconstruction loss within a fixed wall-clock time budget compared to joint optimization, despite higher per-iteration costs.
• Dictionary Learning: For a problem with an $L_1$ constraint on the dictionary, CR-VarPro demonstrated superior convergence in terms of reconstruction loss versus time compared to projected gradient descent.
• Blind Deconvolution: Applied to signal recovery with a Frobenius norm constraint, the method showed improved efficiency in minimizing the objective function over time.
• Few-Shot Learning: Using a pretrained ResNet-18 backbone, the bilevel formulation (optimizing a linear head and a specific intermediate layer) achieved competitive test accuracy with fewer training steps and less time compared to standard fine-tuning approaches (Frozen Ridge, CE Linear Probe, LP-FT).

In all cases, the method demonstrated improvements in wall-clock efficiency and data efficiency (achieving better performance with fewer optimization steps or less time).

5. Significance and Claims

The paper claims that by interpreting variable projection through the lens of bilevel optimization, it is possible to extend the dimension-reduction benefits of VarPro to constrained settings common in modern machine learning. The significance lies in:

• Efficiency: Eliminating linear variables reduces the problem dimension and improves conditioning, while the projection-free algorithm avoids expensive Euclidean projections.
• Exactness: The use of exact reduced gradients (via implicit differentiation) avoids the approximations often required in bilevel optimization, leading to more stable convergence.
• Applicability: The framework is flexible enough to handle diverse structured problems, from sparse representations to few-shot learning, suggesting a general utility for data-science models with separable linear/nonlinear structures.

The authors conclude that while the method requires exact lower-level solves, it offers a robust alternative to joint optimization for structured problems, with future work planned for inexact lower-level solves and stochastic variants.