Optimistic Gradient Learning with Hessian Corrections for High-Dimensional Black-Box Optimization

Authors: Yedidya Kfir, Elad Sarafian, Yoram Louzoun, Sarit Kraus
Primary area: optimization
Keywords: Black box optimization, Derivative free optimization, Gradient free optimization, Large language model code geneation, Adversarial training

Abstract:
Black-box algorithms are designed to optimize functions without relying on their underlying analytical structure or gradient information, making them essential when gradients are inaccessible or difficult to compute. Traditional methods for solving black-box optimization (BBO) problems predominantly rely on non-parametric models and struggle to scale to large input spaces. Conversely, parametric methods that model the function with neural estimators and obtain gradient signals via backpropagation may suffer from significant gradient errors. A recent alternative, Explicit Gradient Learning (EGL), which directly learns the gradient using a first-order Taylor approximation, has demonstrated superior performance over both parametric and non-parametric methods. In this work, we propose two novel gradient learning variants to address the robustness challenges posed by high-dimensional, complex, and highly non-linear problems. Optimistic Gradient Learning (OGL) introduces a bias toward lower regions in the function landscape, while Higher-order Gradient Learning (HGL) incorporates second-order Taylor corrections to improve gradient accuracy. We combine these approaches into the unified OHGL algorithm, achieving state-of-the-art (SOTA) performance on the synthetic COCO suite. Additionally, we demonstrate OHGL’s applicability to high-dimensional real-world machine learning (ML) tasks such as adversarial training and code generation. Our results highlight OHGL's ability to generate stronger candidates, offering a valuable tool for ML researchers and practitioners tackling high-dimensional, non-linear optimization challenges.

Decision: reject
Reviewer scores: 6, 5, 5, 6

Reviews and discussion:
<thread>
creation date:
1729695801606

thread_type:
official_review

<thread_object>
creator: reviewer_3m45

<content>
summary:
This paper extends the gradient descent learning method by incorporating second-order Taylor corrections through the function's Hessian, enhancing robustness in complex, highly non-linear problems. The OGL, HGL, and OHGL algorithms are presented and validated on the synthetic COCO suite, as well as in two scenarios: adversarial attacks and code generation.

strengths:
1. The idea of Optimistic Gradient Learning and Higher-Order Gradient Learning is novel.
2. These new algorithms have achieved better results in experiments.

weaknesses:
1. The reference format is not uniform. I suggest the authors improve them.
2. There are some mistakes in this paper, for example, the CE loss in the title of Table 3 is not reflected in the table.
3. It seems that the most recommended algorithm in this paper, OHGL, has not been applied in real-world scenarios.

questions:
1. I think the experiments of HGL and OHGL in adversarial attacks and code generations can further enhance persuasiveness.
2. Format modification is necessary, reference and appendix are confusing.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730480433986

thread_type:
official_review

<thread_object>
creator: reviewer_euep

<content>
summary:
This work proposes an OHGL framework to solve black-box optimization. It improves the previous EGL framework by incorporating second-order Taylor corrections via the function’s Hessian and assigning higher weights to samples with lower objective values. Experiments on adversarial attack and code generation show its potential in high-dimension real-world problems.

strengths:
1. The proposed Hessian corrections and weighed gradient are well-motivated, effectively addressing the limitations of the previous EGL framework.
2. Real-world high-dimension examples, including adversarial attacks and code generation, demonstrate the scalability and efficiency of this framework.

weaknesses:
1. Compared to previous work, such as EGL or model-based methods [1], the theoretical understanding of the proposed Hessian corrections and weighted gradients is lacking. A more rigorous theoretical analysis would help justify the design choices

2. The work introduces several algorithm-level designs in Sec. 5, such as adaptive sampling size and trust-region management. The tolerance analysis in Section 6.2 suggests that the influence of these designs can accumulate over time, potentially leading to significant changes in performance. However, the paper does not provide clear guidance on how to tune these parameters for different black-box optimization tasks with a limited budget.

[1] Kumar, A., & Levine, S. (2020). Model inversion networks for model-based optimization. Advances in neural information processing systems, 33, 5126-5137.

questions:
1. The OHGL framework incorporates Hessian information during the training stage. However, it is unclear why the second-order information is not utilized when updating the next point (line 278).
2. Is the hyperparameter tuning process conducted for all baselines? 
3. Which design in the OHGL framework contributes the most to the observed performance improvements?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730714864892

thread_type:
official_review

<thread_object>
creator: reviewer_86mz

<content>
summary:
This paper proposes Optimistic Higher-Order Gradient Learning (OHGL), using second-order Taylor approximation, for solving black-box optimization (BBO) problems. Furthermore, the authors refine EGL's sampling strategy and loss function to improve its efficiency in high-dimensional settings. The proposed OHGL method is validated through experiments on the synthetic COCO suite and applied to two real-world machine learning tasks: adversarial training and code generation. The experimental results indicate that OHGL generates stronger candidate solutions, positioning it as a valuable tool for machine learning researchers and practitioners addressing high-dimensional, non-linear optimization challenges.

strengths:
1. The concept of enhancing Explicit Gradient Learning (EGL) with second-order corrections is both interesting and novel, to the best of my knowledge.
2. The paper is generally well-written and presents its ideas in a clear and accessible manner.

weaknesses:
1. My primary concern relates to the computational cost associated with Hessian computation or approximation, which may hinder the scalability of the proposed method. Given that memory- and computation-efficient Hessian approximation techniques are well-established in the literature, I strongly recommend that the authors evaluate their proposed method using more efficient approximations at larger scales.

2. The enhancements over EGL are attained through the integration of several design elements; however, a thorough ablation study is notably absent from the paper.

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731123531133

thread_type:
official_review

<thread_object>
creator: reviewer_yvhg

<content>
summary:
The paper introduces an enhanced method for black-box optimization (BBO) by specifically addressing challenges in high-dimensional and complex optimization landscapes. The proposed approach, termed Optimistic Higher-Order Gradient Learning (OHGL), builds on previous methods like Explicit Gradient Learning (EGL) by incorporating both optimistic gradient estimation and Hessian corrections. By leveraging second-order Taylor expansions and Hessian information, the method improves gradient accuracy. The authors propose a sampling profiler to reduce required samples and refine trust region adjustments for enhanced convergence efficiency. It demonstrates strong potential in machine learning tasks where gradient information is inaccessible or costly to compute.

strengths:
The paper appears to be well-grounded in both theoretical and experimental methodologies. The use of both first- and second-order gradient information for better accuracy in high-dimensional spaces is a technically sound choice, demonstrating an understanding of gradient approximation complexities in BBO.

The breakdown of components like Optimistic Gradient Learning and Higher-Order Gradient Learning helps clarify how each extension builds on EGL, and the inclusion of figures and empirical results assists in understanding performance benefits. However, a possible point for improvement might be adding more intuitive explanations or visual aids for readers less familiar with gradient learning concepts.

weaknesses:
1. Computational Complexity and Efficiency:
The inclusion of Hessian corrections, while beneficial for accuracy, introduces substantial computational cost, particularly in high-dimensional spaces. 

2. Generalization of Results:
The results focus heavily on the COCO test suite and two specific applications. However, broader generalizability to other complex, black-box settings, such as reinforcement learning or sequential decision-making tasks, remains unaddressed. 

3. Trust Region's Limitations:
The algorithm's handling of boundary conditions may slow down convergence in real-world, high-dimensional applications due to excessive shrinking, which could be inefficient in practice.

questions:
1. The inclusion of comparisons to more recent methods like Bayesian optimization frameworks or evolutionary algorithms would strengthen the claims regarding OHGL’s effectiveness.

2. The organization could be refined for flow, as several sections (like trust region management and adaptive sampling) feel slightly disjointed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731942457990

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response for reviewers

comment:
**To all reviewers**: 

We would like to thank the reviewers for their insightful feedback. To begin, we would like to provide preliminary responses to address key concerns and questions (as separate comments to each review). Over the coming days, we will incorporate your valuable suggestions into a revised version of the paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732787111431

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revised version of the paper

comment:
We want to thank the reviewers for their informative responses, we present a revised version of the paper with several key adjustments:
- Analytical Analysis: We now include a comprehensive analytical analysis of the algorithm, covering gradient accuracy and convergence rate. Additionally, we clarify the implications of this analysis and highlight the differences compared to the analysis presented in the EGL paper. This addition should alleviate concerns regarding the theoretical implications of each version of our algorithm. Additionally, it should also provide guidance for future research.
- Ablation Study: We conducted an ablation study to demonstrate the contribution of the core components of our work: the Hessian corrections and optimistic optimization compared to the technical improvements we applied to EGL. This study clearly shows that the majority of the improvement in the overall score is attributed to our core contribution.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732788858120

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revised version of the paper

comment:
In the revised version of the paper, we also address these concerns:
- HGL explanation: We provide a more detailed explanation of the rationale behind HGL in the appropriate section. Specifically, we clarify and explain why the Hessian is utilized exclusively during the training phase and is not involved in the actual optimization step. 
- Efficient Hessian Computation: We showed that detaching the Hessian from the computation graph and optimizing the network without backpropagating through the Hessian yields similar results. This approach leverages the second-order Taylor expansion more efficiently while significantly reducing memory usage. This important addition addresses the issue of the computational resource required for running hessian correction.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732790280319

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revised version of the paper

comment:
We wanted to mention a couple of extra points you can look for in the revised version:
- Adversarial Attack: Using the detached hessian mentioned in the previous comment, we conducted an adversarial attack and presented the corresponding results. Thus, presenting the utility of this method in real-world applications.
- We’ve added a more comprehensive study of the success rate of each algorithm. Using a performance graph, we show the success of each algorithm for different accuracy requirements.
- HP Tolerance: We delve deeper into picking the correct hyperparameters. We used the analytical analysis to show guidelines for picking the correct values. This change will allow readers who want to solve their unique problems a method to pick the appropriate hyper-parameters.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper propose OHGL (Optimistic Higher order Gradient learning ) that uses Hessian corrections for solving black box optimization problems.This is validated on synthetic benchmark COCO and in adversarial training and code generation. 

One of the main concerns with the paper is the computational complexity due to hessian computation and backpropagation through it,
 reviewer 86Mz provided a solution to this problem via detaching hessians from the computational graph, authors explored these ideas on the synthetic benchmark, with a reduction in computational time without incurring errors on the synthetic example. 

The paper clarity and rigor improved a lot in the revision and the rebuttal phase, nevertheless integrating speeding up the second order information is crucial for higher dimensional settings and further experimentation on the high dimensional examples  is needed to improve the scalability of the method. We encourage the authors to reproduce those experiments in the high dimensional case and include them in the paper.