Abstract
In convex optimization, Proximal Gradient (PG) methods are essential for solving composite objective functions consisting of a smooth loss and a non-smooth penalty. However, the efficiency of these methods is highly sensitive to the choice of stepsize. While scalar stepsizes like the Barzilai-Borwein (BB) method are computationally cheap, they often fail to account for the local geometry of ill-conditioned problems. Conversely, second-order methods that utilize the Hessian are computationally prohibitive for large-scale applications. This paper introduces the Diagonal Barzilai-Borwein (DBB) stepsize for the Variable Metric Proximal Gradient (VM-PG) method. By utilizing a diagonal matrix update with a closed-form solution, the DBB method captures essential geometric information at a cost comparable to scalar methods. Empirical results on synthetic and real-world datasets demonstrate that VM-PG with DBB achieves 10–40% faster convergence and improved robustness to ill-conditioning.
Introduction
Optimization problems in machine learning often involve "composite" functions: a smooth part (such as a logistic loss) combined with a non-smooth part (such as an $\ell_1$ penalty for sparsity). Proximal Gradient (PG) methods are the standard approach for these tasks. The performance of PG methods is largely dictated by the stepsize strategy.
Traditional scalar stepsizes, such as the classic Barzilai-Borwein (BB) method, are efficient to compute but treat every dimension identically. This uniformity is inefficient when the objective function is ill-conditioned or "stretched" along certain dimensions. While Newton-type methods address this by using the Hessian to capture local geometry, the computational overhead of computing and inverting a full Hessian is impractical for high-dimensional data. This research addresses the gap by proposing a method that captures more geometric information than a scalar, without the massive overhead of a full Hessian.
The Diagonal Barzilai-Borwein (DBB) Method
The authors propose a Variable Metric Proximal Gradient (VM-PG) method that utilizes a diagonal metric, $U^k$, instead of a scalar stepsize $\alpha$. The core innovation lies in the calculation of this diagonal matrix through a small optimization problem at each iteration.
The DBB Update
The diagonal matrix is designed to satisfy three primary criteria:
- Secant Condition: The matrix acts as a rough diagonal approximation of the Hessian ($U^k s^k \approx y^k$).
- Consistency: A hyperparameter $\mu$ controls how much the metric changes between steps, ensuring stability.
- Boundedness: Values are kept within the range of standard scalar BB stepsizes to prevent numerical instability.
Crucially, the authors derived a closed-form solution for this update, maintaining a computational complexity of $O(n)$—identical to the simple scalar version. To ensure global convergence, the algorithm also incorporates a non-monotonic line search.
Experimental Evaluation
The researchers evaluated the DBB method against standard PG (BB) and the popular Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) using both synthetic and real-world benchmarks:
- Synthetic Data: Ill-conditioned Quadratic Programming (QP), Least Squares (LS), and Logistic Regression (LR) problems.
- Real-World Data: Subsets of the MNIST handwritten digit dataset and the CIFAR-10 object recognition dataset.
The experiments focused on "small $N$, large $n$" scenarios, where the number of features significantly exceeds the number of samples, a regime where standard optimization algorithms often struggle.
Key Results and Insights
The DBB method demonstrated significant advantages in both speed and stability:
- Convergence Speed: The method consistently outperformed scalar BB, showing a 10% to 40% improvement in both iteration count and total CPU time.
- Robustness: On synthetic problems with high condition numbers (up to $\kappa = 10^5$), DBB proved more stable and faster than standard proximal gradient methods.
- Coordinate Scaling: The diagonal metric effectively performs automatic coordinate re-scaling, making the algorithm less sensitive to features with disparate scales.
While FISTA is often considered the gold standard for accelerated first-order methods, VM-PG with DBB performed comparably or better on Least Squares problems, exhibiting fewer oscillations during the convergence process.
Conclusion and Future Work
The Diagonal Barzilai-Borwein stepsize offers a powerful middle ground between simple scalar methods and expensive second-order methods. While the parameter $\mu$ requires some tuning to balance Hessian "memory" with local adaptation, the method's $O(n)$ complexity makes it highly attractive for large-scale machine learning. Future research may explore automated tuning for $\mu$ and the implementation of DBB in distributed computing environments to further leverage its diagonal structure.
Summary updated