- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper proposes a new condition for non-convex optimization called "broximal alignment", under which, an algorithm called "broximal point method" converges to a global optimum. Broximal alignment is implied by many established conditions for non-convex optimization.
Critical strengths
- Non-convex optimization is important and the paper proposes a condition that makes global convergence of an algorithm possible.
- The paper feels almost exclusively human-written and devotes serious effort to explain the intuition behind the main results (like Theorem 4.1). This is certainly appreciated.
Critical weaknesses
- Global convergence is guaranteed for a relatively unknown algorithm (at least to me) from Gruntkowska et al., which looks more of a template for an algorithm than an algorithm itself. More precisely, it assumes access to an oracle which solves an arbitrarily hard sub-problem in a closed ball. Such an oracle seems completely contradictory with any non-convex optimization problems that really matters in practice, and the authors do not argue otherwise or provide examples.
- Assumption 3.2 feels like we get rid of the local minima problem artificially. More precisely, one assumes that if we are in a ball where x is the only optimum, then x must be the global optimum of the whole function. Thus, if x is a local optimum in the aforementioned ball, then there is also another local optimum and the algorithm escapes x and recenters to a new ball where further progress can happen. I see that there is some nice recursive argument in 216-223, but I still perceive this as something essentially equivalent to "if I encounter a local minimum then I can escape it".
Questions for authors
- How do you solve the broximal oracle in Example 1? The only things I can think of is some line search, as we are in one dimension. This cannot be generalized to larger dimensions and in any case is almost equivalent with solving the problem from scratch.
- In what sense the comparison of broximal alignment with quasar convexity, Aiming etc. is fair? The latter are conditions that guarantee convergence of gradient methods, while broximal alignment guarantees convergence for the broximal algorithm. To rephrase, if you use a gradient method to solve the broximal oracle, then you will most probably fall back to conditions like Aiming to guarantee convergence for the sub-problem.
5 comments
We hope these clarifications address the reviewer's concerns about the oracle, the role of our assumptions, and the comparison with existing non-convexity conditions. In light of the clarifications above, and given the reviewer's positive assessment of the novelty, technical soundness, and importance of the work, we believe the current overall rating significantly understates the merits of the paper. We therefore respectfully ask the reviewer to reconsider their overall assessment.
[1] K. Gruntkowska, H. Li, A. Rane, and P. Richtárik, 2025. The Ball-Proximal (=" Broximal") Point Method: a new algorithm, convergence theory, and applications. arXiv preprint arXiv:2502.02002.
[2] Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y. T. Lee, A. Sidford, and K. Tian. Acceleration with a ball optimization oracle. Advances in Neural Information Processing Systems, 33:19052–19063, 2020.
[3] Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference on Learning Theory, pp. 866–882. PMLR, 2021.
[4] H. Asi, Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Stochastic bias-reduced gradient methods. Advances in Neural Information Processing Systems, 34:10810–10822, 2021.
Thanks for the clarifications, it is now clearer to me where the paper stands. In my view the decisive contribution would be to find at least one sufficiently interesting non-convex function, for which the broximal oracle can be solved efficiently. To my knowledge, there are interesting non-convex function where the proximal oracle can be solved efficiently, so this criticism does not apply to proximal point methods. The example in the paper or have indeed broximal oracles that can be solved in closed form, but we can also solve the original problem in closed form, so the broximal method does not seem to give any advantage. Is there an example of a non-convex function where the broximal oracle can be solved efficiently and using the broximal method might have an advantage over other algorithms/processes?
We thank the reviewer for constructive feedback, and particularly for recognizing the novelty and technical soundness of our work, as well as the effort devoted to explaining the intuition behind our results. We understand that the main reservations concern the role of the broximal oracle, the strength and interpretation of Assumption 3.2, and the practical relevance of the resulting framework. We address these concerns below, providing additional examples and clarifying both the scope of our results and their relationship to existing approaches. In particular, we show that the framework is not limited to an abstract oracle construction, as it captures concrete non-convex objectives.
We agree that the exact oracle is strong, and the paper says so explicitly. This is a deliberate choice. Our goal is conceptual, to understand which structural properties of the objective enable global convergence guarantees beyond stationarity, with BPM as the canonical method through which to study them. BPM becomes practical when its trajectory is approximated, either by replacing f with a local model or by solving the subproblem approximately (Section 6, [1], and papers referencing it). Ball oracles are also an established primitive (see, e.g., [2,3,4]).
The same criticism could be raised against the proximal point method. In non-convex settings its exact subproblems can be as hard as the original problem, yet its theory has shaped decades of research and inspired a large family of practical algorithms and approximations. We view BPM in the same way.
Moreover, the analysis itself is not tied to BPM. The proof of Theorem 4.1 uses the iterates only through two properties: the alignment inequality ⟨xk−xk+1,x⋆−xk+1⟩≤0 at non-optimal iterates, and the progress property ∣xk−xk+3∣>t whenever xk+1 is not optimal (Lemma B.4). Any method whose iterates have similar properties can inherit the guarantees via an analogous argument.
We respectfully disagree that it removes local minima artificially. It can be viewed as playing an analogous role that "every stationary point is a global minimizer" plays for gradient methods, which pseudoconvexity, PŁ, star- and quasar convexity and aiming all impose. At the same time, it is much weaker than that analogue, allowing local minima.
Here the oracle is easy to compute exactly in closed form, since f has explicit critical points. The purpose of Example 1 is to give the reader intuition through a simple, low-dimensional function that our assumptions capture and that can be visualized. It is not meant to illustrate the tractability of the oracle (which indeed can be implemented for some function classes but is intractable in general). For a higher-dimensional example where the oracle is also explicit, consider the one-hidden-layer network with quadratic activation added in response to Reviewer Mi5X, f(W)=(∣Wa∣2−y)2 with W∈Rk×d. Its broximal step is explicit in any dimension. Moreover, this function has non-optimal stationary points, so it lies outside pseudoconvexity, PŁ and aiming.
Section 5 compares function classes, not algorithms. Its purpose is to show that our function class is general, containing many well-known non-convex classes from prior work, and for suitable t it also contains functions outside all of them, with non-global local minima (Example 1) or non-optimal stationary points (the network example above). On such functions any deterministic gradient method started at a non-optimal stationary point stays there. Comparing classes is meaningful regardless of the algorithm each was originally designed for.
Regarding the subproblem, we agree that if the broximal step were solved by a gradient method, the corresponding theory would require additional conditions on the subproblem. These concern only f restricted to balls of certain radius t, a different requirement from the global conditions of Section 5. Our results make precise what such an approximation must achieve: by the remark in our answer to the first weakness, any inexact variant whose iterates keep the alignment and progress properties inherits Theorem 4.1, which gives a concrete target for future analyses of inner solvers. Gradient methods are also not the only option here. Conditions like aiming therefore enter only through a particular choice of inner solver, and only on local balls of radius t.