Lazy Queries Can Reduce Variance in Zeroth-Order Optimization

Quan Xiao, Qing Ling, Tianyi Chen

TL;DR

This paper introduces LAZO, a novel zeroth-order (ZO) optimization method that intelligently reuses past function queries to reduce gradient estimation variance. This "lazy querying" approach allows LAZO to achieve competitive or superior performance in terms of regret and query complexity compared to existing methods, even when function evaluations are expensive.

What Problem Does This Paper Address?

Zeroth-order (ZO) optimization methods are crucial when gradients are unavailable, but they often suffer from high query complexity, meaning they require many function evaluations to converge. This is particularly problematic in applications like reinforcement learning or adversarial attacks where each query can be costly. Existing ZO methods face a trade-off: querying fewer points per iteration can increase gradient variance, leading to more iterations, while querying more points per iteration directly increases query cost. The paper aims to break this trade-off by developing a method that reduces variance without necessarily increasing query count per iteration.

Methods

The core innovation is the LAZO (Lazy Queries Zeroth-Order) method. Instead of always querying new points, LAZO adaptively decides whether to reuse old queries or make new ones. It does this by checking the "informativeness" of past queries based on defined "temporal variation" metrics.

  • LAZOa and LAZOb: Two variants are proposed. They differ in how they check the temporal variation and decide whether to query one or two points. LAZOa uses a more accurate temporal variation estimation, while LAZOb is computationally simpler.
  • Adaptive Querying: The key idea is to query new points only when the function's behavior suggests that old queries might lead to high-variance gradient estimates. This is achieved by comparing temporal variations against a threshold D.
  • Theoretical Guarantees: The authors provide theoretical analysis showing that LAZO achieves optimal regret bounds (O(√dT)) for convex optimization and competitive iteration complexity for nonconvex optimization, outperforming existing methods.

Datasets

The paper evaluates LAZO on three applications:

  • LQR control: A non-stationary Linear Quadratic Regulator problem.
  • Resource allocation: A non-stationary resource allocation problem.
  • Black-box adversarial attacks: Generating adversarial examples for a deep neural network classifier on the MNIST dataset.

No new benchmarks were introduced; existing problem settings were used for evaluation.

Key Insights and Ideas

  • Lazy Queries as a Variance Reduction Tool: The most significant insight is that intelligently reusing past queries, rather than always querying new points, can effectively reduce the variance of gradient estimates in ZO settings.
  • Adaptive Decision-Making: The paper demonstrates that an adaptive strategy for deciding when to query new points is crucial for balancing query cost and gradient accuracy.
  • Breaking the Query Complexity Trade-off: LAZO offers a way to achieve good regret bounds and iteration complexity without the prohibitive query costs often associated with high-performing ZO methods.
  • Generalizability: The core idea of lazy querying is presented as a general technique that can be extended to other ZO methods, including multi-point variants.

Key Results

  • Regret Bounds: LAZO achieves optimal O(√dT) regret for convex optimization, matching the performance of symmetric two-point methods but with potentially fewer queries.
  • Query Complexity: In experiments, LAZO consistently outperforms one-point residual and two-point methods in terms of query complexity, often requiring significantly fewer queries to achieve comparable or better results. For instance, in black-box attacks, LAZOa and LAZOb required only 40% and 67% of queries, respectively, to achieve the first successful attack.
  • Performance Gain: LAZO variants showed better convergence performance and more stable results (smaller error bars) across various tasks compared to baseline methods.
  • Computational Overhead: The adaptive rules of LAZO introduce minimal computational overhead and can even lead to slight runtime savings compared to two-point methods due to fewer function evaluations.

Limitations and Future Work

  • Asymmetric Probability: While Assumption 4 (asymptotic symmetricity of the active region of lazy rules) is supported by simulations, it's an assumption that might not hold in all scenarios.
  • Extension to Decentralized Settings: The authors suggest extending LAZO to decentralized optimization settings as a future research direction.
  • Extension to Various ZO Variants: The paper also proposes extending LAZO to other types of zeroth-order optimization methods.
  • Multi-point LAZO: The paper introduces a multi-point LAZO variant for further variance reduction, suggesting its potential for more complex scenarios.

Summary updated

Abstract

A major challenge of applying zeroth-order (ZO) methods is the high query complexity, especially when queries are costly. We propose a novel gradient estimation technique for ZO methods based on adaptive lazy queries that we term as LAZO. Different from the classic one-point or two-point gradient estimation methods, LAZO develops two alternative ways to check the usefulness of old queries from previous iterations, and then adaptively reuses them to construct the low-variance gradient estimates. We rigorously establish that through judiciously reusing the old queries, LAZO can reduce the variance of stochastic gradient estimates so that it not only saves queries per iteration but also achieves the regret bound for the symmetric two-point method. We evaluate the numerical performance of LAZO, and demonstrate the low-variance property and the performance gain of LAZO in both regret and query complexity relative to several existing ZO methods. The idea of LAZO is general, and can be applied to other variants of ZO methods.
BibTeX
@article{xiao2023lazy,
  author = {Quan Xiao and Qing Ling and Tianyi Chen},
  title = {{Lazy Queries Can Reduce Variance in Zeroth-Order Optimization}},
  journal = {IEEE TSP},
  year = {2023},
  doi = {10.1109/tsp.2023.3316887},
}
Figure