An Inexact Preconditioned Zeroth-order Proximal Method for Composite Optimization

Shanglin Liu, Lei Wang, Nachuan Xiao, Xin LiuarXiv 2024 · DOI · arXiv

TL;DR

The paper introduces IPZOPM, a new derivative-free optimization method designed for composite problems where the objective function is a mix of a smooth "black-box" loss and a non-smooth regularizer. By cleverly estimating the diagonal of the Hessian using the same function evaluations already needed for the gradient, the authors provide a "free" second-order preconditioner that significantly accelerates convergence without increasing the per-iteration computational cost.

What Problem Does This Paper Address?

In many fields—ranging from tuning hyperparameters in machine learning to designing complex circuits—researchers face "black-box" optimization problems. In these scenarios, we can calculate the value of a function $f(x)$, but we don't have an analytical formula for its gradient ($\nabla f$) or its curvature (Hessian $\nabla^2 f$).

Standard Zeroth-Order (ZO) methods estimate the gradient by poking the function at various points (finite differences). However, these methods are notoriously slow because they lack curvature information. While some "second-order" ZO methods exist, they typically require a massive number of function evaluations ($O(n^2)$) to estimate the full Hessian matrix, making them impractical for high-dimensional problems. The challenge is: how do we get the speed of second-order optimization without the prohibitive cost of derivative-free Hessian estimation?

Methods

The authors propose the Inexact Preconditioned Zeroth-order Proximal Method (IPZOPM). Its core innovation lies in the way it estimates information:

  1. The "Two-for-One" Estimate: To estimate a gradient in $n$ dimensions using central finite differences, you must evaluate the function at $2n$ points: $\{x \pm \delta e_i\}$. The authors realized that these exact same points can be used to estimate the diagonal entries of the Hessian.
  2. Preconditioning: Instead of a standard gradient step, IPZOPM uses these diagonal estimates as a preconditioner. This scales the step size for each coordinate based on the local curvature, much like a diagonal version of Newton's method.
  3. Inexact Proximal Mapping: For composite optimization (where you have a non-smooth term like $\ell_1$ regularization), the algorithm solves a "proximal subproblem." The "Inexact" part of the name means the algorithm doesn't need to solve this subproblem perfectly every time, which saves even more computation in practice.
  4. Theoretical Guarantees: The authors prove that the method achieves global convergence and has a worst-case complexity of $O(n\epsilon^{-2})$ function evaluations to reach an $\epsilon$-stationary point.

Datasets

The researchers evaluated IPZOPM against the standard Zeroth-Order Proximal Gradient (ZOPG) method using:

  • Synthetic LASSO Problems: High-dimensional linear regression with sparsity constraints.
  • Real-world Binary Classification: Using a non-convex sigmoid loss function on four standard datasets from the LIBSVM library:
  • a4a (4,781 samples, 122 features)
    • a9a (32,561 samples, 123 features)
    • w4a (7,366 samples, 300 features)
    • w8a (49,749 samples, 300 features)

Key Insights and Ideas

  • Curvature for Free: The most striking insight is that diagonal second-order information is essentially "sitting there" for free within the function evaluations used for first-order estimates. Capturing this diagonal curvature provides a significant boost in efficiency for almost zero extra cost.
  • Separability is Key: When the non-smooth regularization term (like the $\ell_1$ norm) is separable, the preconditioned subproblem can be solved coordinate-wise. This leads to closed-form solutions for the update step, making the "preconditioning" step extremely fast.
  • Robustness to Non-convexity: Unlike many classical methods that assume convexity, the authors establish convergence for non-convex loss functions, which is critical for modern machine learning applications like neural network adversarial attacks.

Key Results

  • Faster Convergence: In all experiments (LASSO and binary classification), IPZOPM reached lower loss values in significantly fewer iterations than the standard ZOPG method.
  • Efficiency: Because it uses the same $2n$ points per iteration as first-order methods but converges in fewer iterations, the total "budget" of function evaluations required to solve a problem is much lower.
  • Scalability: The method handles datasets with tens of thousands of samples and hundreds of features effectively, demonstrating its potential for large-scale black-box optimization.

Limitations and Future Work

  • Diagonal Only: The method only captures diagonal curvature. While this is computationally efficient, it ignores off-diagonal correlations between variables, which a full Hessian (or a better approximation) might capture.
  • Parameter Sensitivity: The method relies on a few hyperparameters (like the finite-difference step size $\delta$ and the regularization parameter $\sigma$). While the authors provide heuristics, these might need tuning for specific niche problems.
  • Future Directions: The authors suggest extending this framework to Quasi-Newton methods (like BFGS) to capture more complex curvature without $O(n^2)$ evaluations. They also aim to adapt the method for optimization on Riemannian manifolds, which would open doors to applications like sparse Principal Component Analysis (PCA).

Summary updated

Abstract

In this paper, we consider the composite optimization problem, where the objective function integrates a continuously differentiable loss function with a nonsmooth regularization term. Moreover, only the function values for the differentiable part of the objective function are available. To efficiently solve this composite optimization problem, we propose a preconditioned zeroth-order proximal gradient method in which the gradients and preconditioners are estimated by finite-difference schemes based on the function values at the same trial points. We establish the global convergence and worst-case complexity for our proposed method. Numerical experiments exhibit the superiority of our developed method.
BibTeX
@misc{liu2024inexact,
  author = {Shanglin Liu and Lei Wang and Nachuan Xiao and Xin Liu},
  title = {{An Inexact Preconditioned Zeroth-order Proximal Method for Composite Optimization}},
  year = {2024},
  eprint = {2401.03565},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.03565},
}
Figure