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