acceptodds
Under review as a conference paper at ICLR 2027

Proximal basin hopping: global optimization with guarantees

Abstract

Global optimization is a challenging problem, with plenty of algorithms displaying empirical success, but scarce theoretical backing. In this work, we propose a new theoretical framework called Proximal Basin Hopping (PBH), carefully tailored to combine proximal optimization and local minimization. We use it to construct a practical algorithm that converges to the global minimizer with high probability, when using a finite amount of samples. Proximal Basin Hopping outperforms well known algorithms on standard synthetic hard functions for moderate dimensions, and on real problems like fitting scaling laws for deep learning. Furthermore, the higher the dimension, the better the performance.

Primary area:
optimization
Keywords:
Global optimization, non-convex optimization, machine learning, proximal optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_yw67OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

To the best of my understanding, the paper aims to construct an algorithm that has both proximal minimization elements and attraction basin hopping elements. I am sorry for the harsh review, but I have to say I stopped reading at Theorem 1, since the paper's text is simply extremely hard to follow. It uses notation before it is defined, and the notation is unclear and not obvious. It may be the case that I should have used AI to "parse through", but the point is that the paper should be readable to a human.

Critical strengths

None

Critical weaknesses

The entire paper is very hard to follow. Notation is either used before being defined, and even when defined, it is not obvious what it is. Examples:

  1. On line 107, the Att(⋅)Att(\cdot) operator is used without being defined. It's impossible to understand at this stage what is the meaning of the potential VxV_x and its relationship to the proximal operator w.r.t the solver TfT_f. The attractor set is defined only on line 155, much later.
  2. On line 165, what does Attˉ\bar{Att} mean? Is it the closure or the complement? I can guess it's the closure, but if it's not, then the entire meaning of subsequent things changes.
  3. On line 172, Eq (5), what does Att∘Att^{\circ} mean? Is it the polar set? If so - this assumption seems unreasonably strong - so strong that it is not even obvious why it should even hold somewhere. Requires explanation.
  4. In Eq (7) you have M on both sides of the equation. It appears meaningless. I can't even understand what it means.
  5. On line 195, what does "xx does not \emph{see} ..." mean? xx is a point. It doesn't see anything. What does it mean?
  6. In Lemma 1, if Attˉ(M)\bar{Att}(M) is the closure, a projection of a point outside the set is going to be on the boundary. So if the set of attractors open, then this intersection is always empty. What kind of function satisfy this assumption? Why is it reasonable?
  7. In Equation (8), inside Theorem 1, what is Mxk\mathcal{M}_{x_k}? You defined M\mathcal{M}, but what does it mean to be indexed by xkx_k? In the same theorem, γk\gamma_k is computed but not used anywhere - why is it useful?

At this stage I stopped reading, since I was not able to understand even the beginning of the paper. I believe it requires a serious re-writing - the authors need to turn the set of equations, symbols, and notations, theorems and lemmas into something people can read. With well-defined concepts, and not a huge number of those. It requires a serious work of eliciting the essence and presenting it coherently.

I do have optimization background, and especially in proximal minimization, but not basin hopping. So I believe a large intended audience will not find any use for this paper before serious revisions.

Questions for authors

NA

Reviewer_8t2UOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

he paper proposes Proximal Basin Hopping (PBH) for global optimization. It locally minimizes Gaussian samples, averages their outputs with weights favoring lower function values, and locally minimizes the average again. A potential based on basin distance connects this procedure to proximal optimization. Experiments cover synthetic functions and scaling-law fitting.

Critical strengths
  1. I find the basin-based view interesting. It considers both how low a minimum is and how far its basin is from the current point.

  2. The experiments cover several global optimization baselines and scaling-law fitting.

Critical weaknesses
  1. Table 1 reports ranks, but not objective gaps or variation across runs. It is hard to tell how close PBH gets to the global minimum and how reliably it does so.

  2. I am unsure about Theorem 5. Small improvements from an inexact local solver may continue indefinitely near a wrong local minimum. Then γ need not increase, although the proof relies on γ tending to infinity.

  3. There are a few small typos: “local minization” on p.1 should be “local minimization”, and “abalation study” on p.8 should be “ablation study”.

Questions for authors
  1. For scaling-law fitting, I wonder can authors also report the training Huber objective? Table 2 gives test MRE, which does not directly show how well the optimization objective was minimized.
Reviewer_8Ew5OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposed a framework called Proximal Basin Hopping(PBH), aiming to solve the global optimization problem under certain assumptions. PBH combines proximal algorithms and basin hopping algorithms to quantify the effect of sample size and inexactness on the convergence to the global minimizer.

Four different types of approximations are given: ideal basin selection, exact expectations, Monte Carlo approximation, and inexact local optimization. By allowing inexact computations of the proximal operator and of the local solver, a practical algorithm is proposed to solve for the global minimizer, given the structural assumption that the global minimizer is sufficiently different in function value from local minimizers. For each type of approximation, proofs of convergence to the global minimizer are provided.

Various numerical experiments on the proposed algorithm are given. PBH illustrates better performance in solving hard synthetic functions and fitting additive scaling laws than basin hopping and zeroth-order proximal baselines.

Limitations and future directions are also discussed, including improving stochastic exploration, investigating the impact of inexact local minimization, and developing a better strategy for setting the number of samples.

Critical strengths
  • Importance and novelty. The paper deals with a general, important problem in optimization—finding the global optimum of a non-convex problem. A hybrid algorithm named proximal basin hopping is proposed by combining two well-studied methods—proximal optimization and local minimization. As far as I know, such a synthesis is novel in the literature. Besides, the paper forms a progression from an ideal mathematical rule to an implementable algorithm: the ideal PBH that requires knowledge of local minima (a challenging global problem), the exact expectation PBH that computes the score with a weighted population average, the approximated expectation PBH that estimates those expectations using finite samples, and the approximated expectation & inexact local-solving PBH that also approximates the local solves. Such progression provides a clear chain of logic for understanding how local search and global exploration interact. It also gives a practical procedure to implement the algorithm. The numerical validation section provides a clear setup and results that outperform the state-of-the-art on different problems, demonstrating the advantage of the proposed algorithm. Overall, the paper formulates a useful mathematical framework for solving a range of non-convex problems effectively and efficiently; I would lean toward acceptance for this reason.
Critical weaknesses

The configuration of the experiments brings some uncertainty in two aspects:

(1) The effect of the aggregation mechanism is not verified. From the formulation, we know that PHB outperforms ZOP due to the local minimization step. PHB outperforms BH because of the batch-based procedure. However, we are not sure if averaging the local solutions could help; simply choosing the locally minimal one might be better.

(2) Identical initialization does not necessarily give an equally effective configuration. The concern is with ZOP. As PBH evaluates and weights locally optimized points, whereas ZOP evaluates and weights raw samples, they can have very different distributions of objective values. Also, keeping the number of samples constant could disadvantage ZOP as well.

Since the issues do not change the mathematical framework, and the paper has listed these explicitly as limitations, they do not have a major effect on the overall quality of the paper.

Questions for authors

None.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.