TL;DR
This paper introduces a novel family of Barzilai-Borwein (BB) steplengths for gradient descent optimization methods, derived from the perspective of scaled total least squares (STLS). This new family offers improved performance and flexibility, particularly when a carefully chosen parameter is used, outperforming classical BB steplengths in various numerical experiments.
What Problem Does This Paper Address?
Gradient descent is a fundamental optimization algorithm, but its efficiency heavily relies on the choice of the steplength parameter. The Barzilai-Borwein (BB) steplengths are popular choices that have shown excellent performance, especially for quadratic functions. However, existing BB steplengths are derived from ordinary or data least squares, which might not fully capture the complexities of real-world data where both the model and observations can be noisy. This paper aims to address this by developing a more robust family of BB steplengths by considering the scaled total least squares (STLS) framework, which accounts for errors in both the data matrix and the observation vector.
Methods
The core contribution of this paper is the derivation of a new family of BB steplengths based on the scaled total least squares (STLS) problem. The authors first review the concepts of ordinary least squares (LS), data least squares (DLS), and total least squares (TLS). They then unify these into the STLS framework, which involves minimizing an objective function with a parameter $\gamma$. By applying STLS to the simplified quasi-Newton equations used in BB methods, they derive a new family of steplengths parameterized by $\gamma$.
The paper also establishes theoretical convergence properties for this new family of steplengths, showing R-superlinear convergence for 2D strictly convex quadratic functions and R-linear convergence for general finite-dimensional strictly convex quadratic functions. For nonquadratic problems, they combine the new steplengths with a non-monotonic line search technique to ensure global convergence.
Datasets
The paper does not introduce new datasets. Instead, it uses standard test functions for evaluation:
- Strictly convex quadratic functions: Used for theoretical analysis and some numerical experiments.
- Planar Rosenbrock function: A classical benchmark for optimization algorithms.
- Various nonquadratic and potentially nonconvex functions: A collection of 15 functions from a previous study [27] used for comprehensive testing.
Key Insights and Ideas
- Bridging Least Squares and BB Steplengths: The paper elegantly connects the well-known BB steplengths to ordinary and data least squares, then extends this connection to the more general scaled total least squares (STLS) framework. This provides a fresh perspective on the origin and potential improvements of BB steplengths.
- The Power of Scaled Total Least Squares: By incorporating STLS, the new steplength family can better handle situations where both the model parameters and the observed data are subject to noise, making it more robust for real-world applications.
- Parameter $\gamma$ as a Flexibility Lever: The introduction of the parameter $\gamma$ in the STLS framework creates a family of steplengths. This allows for tuning the steplength's behavior, with specific values of $\gamma$ recovering existing BB steplengths (e.g., $\gamma \to 0$ for ordinary LS, $\gamma \to \infty$ for DLS, and $\gamma=1$ for TLS).
- Performance Gains with Optimal $\gamma$: Numerical experiments demonstrate that a carefully selected $\gamma$ can lead to significantly better performance (fewer iterations) compared to classical BB steplengths and even other state-of-the-art methods.
Key Results
- Theoretical Convergence: The proposed BB steplengths are proven to achieve R-superlinear convergence for 2D strictly convex quadratic functions and R-linear convergence for general strictly convex quadratic functions.
- Numerical Performance:
- For quadratic functions, the performance profiles show that certain values of $\gamma$ (e.g., 20 or 50 for n=100, and 20 for n=1000) yield superior results, outperforming the $\gamma=1$ (TLS) case and the limits corresponding to LS and DLS.
- On the planar Rosenbrock function, the new steplength with $\gamma=1.5$ demonstrated the best performance, and $\gamma=1$ was notably more efficient than the classical BB steplengths.
- On a collection of nonquadratic test functions, the steplength with $\gamma=1$ (TLS) was found to be very efficient, often requiring fewer iterations than other methods, and further improvements were observed with optimized $\gamma^*$ values.
- Robustness: The paper suggests that the new family of steplengths, particularly with a well-chosen $\gamma$, offers a robust and efficient approach for optimization problems.
Limitations and Future Work
- Problem-Dependent Optimal $\gamma$: The paper acknowledges that the optimal choice of $\gamma$ is problem-dependent. Identifying this optimal $\gamma^*$ efficiently remains a critical issue for future research.
- Dynamic Selection of $\gamma$: While the paper demonstrates the benefits of a fixed, carefully selected $\gamma$, future work could explore dynamic strategies for selecting $\gamma$ during the optimization process to adapt to problem characteristics.
- Extension to Other Methods: The paper focuses on gradient descent. Extending the application of this new steplength family to other optimization algorithms could be a fruitful area of future research.
Summary updated