acceptodds
Under review as a conference paper at ICLR 2027

Broximal Alignment for Global Non-Convex Optimization

Abstract

Most non-convex optimization theory is built around gradient dynamics, leaving global convergence largely unexplored. The dominant paradigm focuses on stationarity, certifying only that the gradient norm vanishes, which is often a weak proxy for actual optimization success. In practice, gradient norms can stagnate or even increase during training, and stationary points may be far from global solutions. In this work, we propose a new framework for global non-convex optimization that avoids gradient-based reasoning altogether. We revisit the Ball Proximal Point Method (BPM), a trust-region-style algorithm introduced by Gruntkowska et al. (2025), and propose a novel structural condition - Broximal Alignment - under which BPM provably converges to a global minimizer. Our condition requires no convexity, smoothness, or Lipschitz assumptions, and it permits multiple and disconnected global minima as well as non-optimal local minima. We show that this class generalizes standard non-convex frameworks such as quasiconvexity, star convexity, quasar convexity, and the aiming condition. Our results provide a new conceptual foundation for global non-convex optimization beyond stationarity.

Primary area:
optimization
Keywords:
non-convex optimization, global convergence, Ball Proximal Point Method

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_B38ROpenReview ↗
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
  1. Non-convex optimization is important and the paper proposes a condition that makes global convergence of an algorithm possible.
  2. 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
  1. 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.
  2. 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
  1. 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.
  2. 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 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.


the broximal oracle

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 ff 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\langle x_k-x_{k+1},x_\star-x_{k+1}\rangle\le 0 at non-optimal iterates, and the progress property ∣xk−xk+3∣>t\\|x_k-x_{k+3}\\|>t whenever xk+1x_{k+1} is not optimal (Lemma B.4). Any method whose iterates have similar properties can inherit the guarantees via an analogous argument.

Assumption 3.2

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.

the oracle in Example 1

Here the oracle is easy to compute exactly in closed form, since ff 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)2f(W)=(\\|Wa\\|^2-y)^2 with W∈Rk×dW\in\mathbb R^{k\times 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.

fairness of the comparison

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 tt 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 ff restricted to balls of certain radius tt, 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 tt.

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 f(W)=(∣∣Wa∣∣2−y)2f(W)=(||Wa||^2-y)^2 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?

Reviewer_Mi5XOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a new framework for global nonconvex optimization that foregoes gradient-based procedures and relies instead on the ball-proximal operator \operatorname{brox}_t^f(x) \coloneqq \underset{z \in \left\\{ y \in \mathbb{R}^d : \\|y - x\\|_X \leq t, X \succ \mathbf{0}\right\\}}{\arg\min} \\; f(z), for some t>0t > 0. In particular, the paper introduces a new structural property called ball-proximal (broximal) alignment and denotes the class of proper, closed functions f:Rd→R∪+∞f : \mathbb{R}^d \to \mathbb{R} \cup \\{+\infty\\} having minimizer set Xf\mathcal X_f and satisfying

\begin{align} \begin{cases} &\exists x_\star \in \mathcal X_f, \text{ s. t. } \forall x \in \operatorname{dom} (f) \setminus \{X_f + \left\{ z \in \mathbb{R}^d : \|z\|_X \leq t, X \succ \mathbf{0} \right\}\}, \; \forall u \in \operatorname{brox}_t^f(x), \; \langle x-u, x^\star-u \rangle_X \leq 0 \\[4mm] & \forall x \in \operatorname{dom} (f), \; \operatorname{brox}_t^f (x) = \{x\} \implies x \in \mathcal X_f \end{cases} \label{eq:def} \end{align}

for some t>0t > 0 as broximal-aligned functions. The paper further shows that this class of functions is closed under composition with strictly increasing functions and XX-orthogonal transformations.

Furthermore, the paper shows that for this function class, the simple iteration $ x_{k+1} \in \operatorname{brox}_{t_k}^f(x_k) $ achieves global convergence in a finite number of steps. Finally, the authors show that for any t>0t > 0 the class of broximal aligned functions includes several forms of benign non-convexity such as: strictly quasiconvex functions, pseudoconvex functions, ξ\xi-quasar convex functions w.r.t. x⋆∈Xfx_\star \in \mathcal X_f, and functions satisfying the aiming condition and having a unique global minimizer.

Importantly, the authors position their algorithmic contribution not as a practical one (due to the general intractability of the broximal operator), but as a means to isolate and study a novel type of non-convexity for which global convergence can be established.

Critical strengths
  • The developments are novel
  • The paper is very well written and has a rigorous, self-contained technical presentation
  • The mathematical statements are sound (while I did not verify the proofs in detail, I followed the main steps)
  • The related literature is appropriately covered, to the best of my knowledge, and the authors do a good job of positioning their work
  • The paradigm shift from gradient-based methods and stationarity-based optimization is worth re-exploring under this new framework (and, frankly, refreshing), even allowing for the general intractability of the broximal operator.
Critical weaknesses

(Please see related questions/comments in the next section)

  • My major concern with this work is its motivation, as currently stated, which relies unjustifiably much on the promise of addressing modern ML settings. Given that this paper seeks to introduce an alternative to the longstanding gradient-based optimization paradigms, its motivation should be particularly careful, and appropriately rooted in the current state of understanding in modern ML settings.
Questions for authors

(references in this section are at the end of the section)

  • Major concern:

    • Paper motivation: the authors return periodically to non-convexity in modern ML, and especially in neural architectures, as the main driver for exploring this new optimization framework: see lines 030 -- 032, 063 -- 066, 160 -- 166, 168 in conjunction with 175, 365 -- 368, 420, 457 -- 459. Leaving the intractability of the brox operator in such settings aside, my main concern for this motivation is twofold.

      i) The authors omit to provide even a simple neural network+data+loss triplet satisfying the broximal alignment condition. For example, can the authors provide a very simple one-hidden layer network (even with scalar parameters per layer), with an activation of their choice, and a training loss (e.g., squared) relative to a single data point, for which broximal alignment holds?

      ii) The links to existing works like [3] are rather weak: the aiming condition in [3] is shown either for a ball around the initialization, or a tube around the set of minimizers, and is hence a local property. In this light, the sentence "This yields a strictly larger class of functions, encompassing, for example, wide neural network losses (Liu et al., 2023)." is overstating the connection, for two reasons. First, Theorem 4.1 requires global broximal alignment, but in the scenario of [3] together with Thm 5.4 this would hold only locally. Second, Thm 5.4 requires a unique minimizer for the aiming function, which would prevent a solid link with [3] even when restricted to the tube around the minimizer set. Furthermore, the statement in line 161 "For example, one-layer neural networks have no spurious local minima" is, as written, too strong relative to what is actually shown by the cited papers [4,5,6] (the statement either does not hold as written, or holds for highly nonstandard architectures).

      I am open to any reframing of the paper's motivation that either addresses these issues head-on or circumvents them.

  • Minor issues / questions:

    • Lines 199, 217, 344, 360: lemma/theorem hyperlinks display as appendix results (letter-based indexing), however they point to main paper statements.

    • Some entries in Table 1 / Figure 2 are disonant relative to Section 5 statements, being potentially misleading. E.g., Table 1 highlights that quasiconvex functions can have non-unique global optima, however, Theorem 5.1 requires strict quasiconvexity which induces a unique optimum. The same holds for the aiming condition and associated result. Please adjust the table/figure and how they are referenced in the text to remove confusion.

    • Line 036: "Unlike convex optimization, where global minimizers can be efficiently found" --- the statment is too strong, convexity does not always imply tractability [1]

    • Line 055: "From the modeling perspective, however, stationarity-based guarantees are fundamentally misaligned with the goals of learning." --- the statement is too strong for modern ML settings, since modern models learn successfully without their optimization necessarily being successful in the rigorous sense, as evidenced by the authors themselves in lines 064-066. See further arguments in [2] and references therein. In other words, modern settings highlight that successful learning can happen without training/optimization convergence. In particular, I find that using modern ML as a motivation for this work to cause some rhetorical inconsistency, since the following 3 points clash: i) modern ML models are very successful in learning, ii) gradient norms stagnate or move away from zero at the end of training of modern ML models, iii) we introduce a framework motivated by modern ML models which guarantees finding global optima, hence points of zero gradient.

    • The authors show via Example 2 that some functions with disconnected global minima are covered by the class FIBA(t)\mathcal F^{\text{BA}}_{\mathbf{I}}(t). At the same time, aiming functions require a unique minimum for inclusion into FIBA(t)\mathcal F^{\text{BA}}_{\mathbf{I}}(t). Is the unique minimum condition necessary for this class or merely sufficient/convenient?

[1] De Klerk, Etienne, and Dmitrii V. Pasechnik. "Approximation of the stability number of a graph via copositive programming." SIAM Journal on Optimization 12.4 (2002): 875-892.

[2] Zhang, Jingzhao, et al. "Neural network weights do not converge to stationary points: An invariant measure perspective." International Conference on Machine Learning. PMLR, 2022.

[3] Chaoyue Liu, Dmitriy Drusvyatskiy, Misha Belkin, Damek Davis, and Yian Ma. Aiming towards the minimizers: fast convergence of SGD for overparametrized problems. Advances in neural information processing systems, 36:60748–60767, 2023

[4] Soheil Feizi, Hamid Javadi, Jesse Zhang, and David Tse. Porcupine neural networks: (almost) all local optima are global. arXiv preprint arXiv:1710.02196, 2017. (Cited on page 3)

[5] Benjamin D. Haeffele and Ren´e Vidal. Global optimality in neural network training. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4390–4398, 2017. doi: 10.1109/CVPR.2017.467. (Cited on page 3)

[6] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742–769, 2018. (Cited on page 3)

8 comments

We thank the reviewer for their constructive feedback and for recognizing the novelty and technical soundness of our work. We are also grateful for the helpful suggestions, which we believe will improve the paper. We address each point below, with the corresponding proofs provided at the end of the rebuttal.


A one-hidden-layer network satisfying broximal alignment

Take a single data point (a,y)(a,y) with a∈Rd∖0a\in\mathbb R^d\setminus\\{0\\}, y>0y>0, a hidden layer W∈Rk×dW\in\mathbb R^{k\times d} with rows wjw_j, quadratic activation, output weights fixed to one and squared loss: f(W)=(∑j=1k(wj⊤a)2−y)2=(∣Wa∣2−y)2.f(W)=\Big(\sum_{j=1}^k (w_j^\top a)^2-y\Big)^2=\big(\\|Wa\\|^2-y\big)^2 .

Proposition 1. Let r:=y/∣a∣r:=\sqrt y/\\|a\\|. Then f∈FIBA(t)f\in\mathcal F^{\rm BA}_I(t) if and only if t≥rt\ge r.

The example lies outside every class in Table 1 except quadratic growth. Since dist(W,Xf)\mathrm{dist}(W,\mathcal X_f) is unbounded, the example is far from the trivial large-radius regime as well.

Proposition 2. ff is not pseudoconvex, does not satisfy the PŁ inequality, does not satisfy the aiming condition, is not quasiconvex, and not ζ\zeta-quasar convex (in particular not star-convex) with respect to any X⋆∈XfX_\star\in\mathcal X_f and ζ∈(0,1]\zeta\in(0,1].

Connection to Liu et al.

Our paragraph "The aiming condition is closely related to quasar convexity: while quasar convexity requires (4) to hold with respect to a fixed minimizer x⋆∈Xfx_\star\in\mathcal X_f, aiming permits the reference point xˉ\bar{x} to depend on xx. This yields a strictly larger class of functions, encompassing, for example, wide neural network losses" compares aiming with quasar convexity. It is not a statement about our theorems.

We do agree, however, with two corrections. First, [3] establishes aiming for wide networks only locally, whereas Definition 5.4 is global. Second, "Even so, aiming remains stronger than our assumptions" is established only for functions with a unique minimizer. Read together, the two sentences could suggest that our theory covers wide networks, which we did not intend. The whole passage will read: "The aiming condition is closely related to quasar convexity: while quasar convexity requires (4) to hold with respect to a fixed minimizer x⋆∈Xfx_\star\in\mathcal X_f, aiming permits the reference point xˉ\bar x to depend on xx. This makes the condition more flexible, and Liu et al. (2023) show that it holds locally for wide neural network losses. Even so, for functions with a unique minimizer, aiming is stronger than our assumptions."

An addition that narrows the gap is the fact that our global requirement can be localized. Under Assumption 3.1, iterates never leave BX(x⋆,∣x0−x⋆∣X)\mathcal B_X(x_\star,\\|x_0-x_\star\\|_X) before reaching Xf\mathcal X_f. It therefore suffices that Assumptions 3.1 and 3.2 hold on this ball.

Motivation

The reviewer suggests reframing the motivation, but we believe the original motivation remains appropriate, particularly in light of the improvements we will make to the paper following this review. First, our function class does contain neural network losses, and the possibility of localizing our results is consistent with the local regime in which [3] establishes aiming. Second, the fundamental motivation that stationarity can be a weak certificate of success in machine learning remains unchanged. This is also one of the motivations underlying the study of classes such as star-convexity, which was hypothesized to describe neural network losses based on empirical evidence and which our framework encompasses for every t>0t>0. Finally, our framework covers several other well-established and practically relevant function classes, including pseudoconvex, quasar-convex, aiming functions with a unique global minimizer, and strictly quasiconvex functions. The extensive literature studying these classes and their applications provides further evidence of the relevance of the broader function class captured by our framework. We therefore believe the original motivation is well-founded, while the small additions prompted by this review will make this even clearer.

Line 161

We agree. The sentence is revised to "under additional structure, one-layer neural networks have no spurious local minima..."

Table 1 and Figure 3

The entries of Table 1 describe properties of each class, not our inclusion results. We agree, however, that Figure 3 was slightly misleading. In the revision, the arrows indicating inclusion in our class are annotated with the conditions our results require (strict quasiconvexity, and a unique minimizer for aiming).

Line 036

We appreciate the reviewer highlighting this point. The original statement is a common simplification in optimization literature, and we agree that it was overly broad. We have revised it to include "under standard oracle models and mild regularity assumptions".

Line 055

We agree that successful learning in modern ML does not necessarily require convergence to a stationary point. This is not the claim of the paragraph, which is titled "Limitations of Stationarity-Based Non-convex Optimization Theory" and concerns optimization progress: it notes that a stationary point can be a global minimizer, a poor local minimizer or a saddle point, and concludes that "stationarity is a weak proxy for optimization progress". This is independent of whether learning can succeed without the optimization converging, which resolves the tension in (i)–(iii).

Is uniqueness needed for aiming functions?

Theorem 5.4 shows that it is sufficient. Whether it can be dropped from Theorem 5.4 altogether, i.e. whether every aiming function belongs to FIBA(t)\mathcal F^{\rm BA}_I(t), is open.


Proofs

A one-hidden-layer network with quadratic activation

Let a∈Rd∖0a\in\mathbb R^d\setminus\\{0\\}, y>0y>0 and f(W)=(∣Wa∣2−y)2f(W)=(\\|Wa\\|^2-y)^2 for W∈Rk×dW\in\mathbb R^{k\times d}. We use the Frobenius inner product ⟨A,B⟩=tr(A⊤B)\langle A,B\rangle=\mathrm{tr}(A^\top B) on Rk×d\mathbb R^{k\times d}, and ∣⋅∣\\|\cdot\\| denotes the Frobenius norm for matrices and the Euclidean norm for vectors. ∇f\nabla f is the gradient with respect to this inner product, B(W,t)\mathcal B(W,t) is the Frobenius ball, and dist\mathrm{dist} and broxft\mathrm{brox}^t_f are taken with X=IX=I. Let a^=a/∣a∣\hat a=a/\\|a\\|, r=y/∣a∣r=\sqrt y/\\|a\\|, and let P:Rk×d→Rk×dP:\mathbb R^{k\times d}\to\mathbb R^{k\times d} be the linear map PW:=Wa^a^⊤PW:=W\hat a\hat a^\top. We write e1e_1 for the first standard basis vector of Rk\mathbb R^k, and X⋆X_\star for elements of Xf\mathcal X_f, which are matrices here.

Lemma 1. (a) P2=PP^2=P, ⟨PW,V⟩=⟨W,PV⟩\langle PW,V\rangle=\langle W,PV\rangle, and range(P)≠{0}\mathrm{range}(P)\neq\{0\}. In particular, PP is an orthogonal projection, so ∣PW∣≤∣W∣\\|PW\\|\le\\|W\\|.

(b) ∣Wa∣=∣a∣ ∣PW∣\\|Wa\\|=\\|a\\|\,\\|PW\\|, hence f(W)=∣a∣4(∣PW∣2−r2)2f(W)=\\|a\\|^4(\\|PW\\|^2-r^2)^2 and ∇f(W)=4∣a∣4(∣PW∣2−r2)PW\nabla f(W)=4\\|a\\|^4(\\|PW\\|^2-r^2)PW.

(c) Xf={W:∣PW∣=r}\mathcal X_f=\{W:\\|PW\\|=r\} and dist(W,Xf)=∣∣PW∣−r∣\mathrm{dist}(W,\mathcal X_f)=\big|\\|PW\\|-r\big|.

Proof. (a) P2W=Wa^(a^⊤a^)a^⊤=PWP^2W=W\hat a(\hat a^\top\hat a)\hat a^\top=PW, ⟨PW,V⟩=tr(a^a^⊤W⊤V)=tr(W⊤Va^a^⊤)=⟨W,PV⟩\langle PW,V\rangle=\mathrm{tr}(\hat a\hat a^\top W^\top V)=\mathrm{tr}(W^\top V\hat a\hat a^\top)=\langle W,PV\rangle, and e1a^⊤∈range(P)∖0e_1\hat a^\top\in\mathrm{range}(P)\setminus\\{0\\} since P(e1a^⊤)=e1(a^⊤a^)a^⊤=e1a^⊤≠0P(e_1\hat a^\top)=e_1(\hat a^\top\hat a)\hat a^\top=e_1\hat a^\top\neq 0. An idempotent self-adjoint linear map is an orthogonal projection, hence nonexpansive.

(b) ∣PW∣2=tr(a^(Wa^)⊤(Wa^)a^⊤)=∣Wa^∣2 tr(a^a^⊤)=∣Wa^∣2\\|PW\\|^2=\mathrm{tr}\big(\hat a(W\hat a)^\top(W\hat a)\hat a^\top\big)=\\|W\hat a\\|^2\,\mathrm{tr}(\hat a\hat a^\top)=\\|W\hat a\\|^2. Hence ∣Wa∣=∣a∣ ∣Wa^∣=∣a∣ ∣PW∣\\|Wa\\|=\\|a\\|\,\\|W\hat a\\|=\\|a\\|\,\\|PW\\|, and since y=∣a∣2r2y=\\|a\\|^2r^2 by the definition of rr, f(W)=(∣a∣2∣PW∣2−∣a∣2r2)2=∣a∣4(∣PW∣2−r2)2f(W)=(\\|a\\|^2\\|PW\\|^2-\\|a\\|^2r^2)^2=\\|a\\|^4(\\|PW\\|^2-r^2)^2. For the gradient, let g(W)=∣PW∣2g(W)=\\|PW\\|^2, which equals ⟨W,PW⟩\langle W,PW\rangle by (a). Then g(W+H)=g(W)+2⟨PW,H⟩+⟨H,PH⟩g(W+H)=g(W)+2\langle PW,H\rangle+\langle H,PH\rangle by self-adjointness, so ∇g(W)=2PW\nabla g(W)=2PW, and the chain rule gives ∇f(W)=2∣a∣4(g(W)−r2)∇g(W)=4∣a∣4(∣PW∣2−r2)PW\nabla f(W)=2\\|a\\|^4(g(W)-r^2)\nabla g(W)=4\\|a\\|^4(\\|PW\\|^2-r^2)PW.

(c) By (b), f≥0f\ge 0, and f(W)=0f(W)=0 if and only if ∣PW∣=r\\|PW\\|=r. This value is attained, e.g. at re1a^⊤re_1\hat a^\top. Hence f⋆=0f_\star=0 and Xf={W:∣PW∣=r}\mathcal X_f=\{W:\\|PW\\|=r\}. For Z∈XfZ\in\mathcal X_f, nonexpansiveness and linearity of PP and the reverse triangle inequality give ∣W−Z∣≥∣PW−PZ∣≥∣∣PW∣−∣PZ∣∣=∣∣PW∣−r∣\\|W-Z\\|\ge\\|PW-PZ\\|\ge\big|\\|PW\\|-\\|PZ\\|\big|=\big|\\|PW\\|-r\big|. This bound is attained. If PW≠0PW\neq 0, take Z=W−PW+rPW/∣PW∣Z=W-PW+rPW/\\|PW\\|. Then ∣W−Z∣=∣PW−rPW/∣PW∣∣=∣∣PW∣−r∣\\|W-Z\\|=\\|PW-rPW/\\|PW\\|\\|=\big|\\|PW\\|-r\big|, and PZ=PW−P2W+rP2W/∣PW∣=rPW/∣PW∣PZ=PW-P^2W+rP^2W/\\|PW\\|=rPW/\\|PW\\| by (a), so ∣PZ∣=r\\|PZ\\|=r and Z∈XfZ\in\mathcal X_f. If PW=0PW=0, take Z=W+rEZ=W+rE with E∈range(P)E\in\mathrm{range}(P), ∣E∣=1\\|E\\|=1. Then ∣W−Z∣=r=∣∣PW∣−r∣\\|W-Z\\|=r=\big|\\|PW\\|-r\big|, and PZ=PW+rPE=rEPZ=PW+rPE=rE, since PE=EPE=E for E∈range(P)E\in\mathrm{range}(P), so ∣PZ∣=r\\|PZ\\|=r and Z∈XfZ\in\mathcal X_f.

Proposition 2. ff belongs to the class of broximal aligned functions with radius tt if and only if t≥rt\ge r. If t≥rt\ge r, Assumption 3.1 holds with every X⋆∈XfX_\star\in\mathcal X_f.

Proof. The function ff is continuous and finite, hence proper and closed, and Xf≠∅\mathcal X_f\neq\emptyset by Lemma 1(c). We use repeatedly that PE=EPE=E for E∈range(P)E\in\mathrm{range}(P) and that ∣V∣2=∣PV∣2+∣V−PV∣2\\|V\\|^2=\\|PV\\|^2+\\|V-PV\\|^2 for all VV, since PP is an orthogonal projection. In particular, ∣PV∣=∣V∣\\|PV\\|=\\|V\\| if and only if V∈range(P)V\in\mathrm{range}(P).

Assumption 3.2, any t>0t>0: Let W∉XfW\notin\mathcal X_f. If PW=0PW=0, take E∈range(P)E\in\mathrm{range}(P) with ∣E∣=1\\|E\\|=1 and s∈(0,min⁡{t,r})s\in(0,\min\{t,r\}). Then W+sE∈B(W,t)W+sE\in \mathcal B(W,t) and P(W+sE)=sEP(W+sE)=sE, so by Lemma 1(b) f(W+sE)=∣a∣4(s2−r2)2<∣a∣4r4=f(W)f(W+sE)=\\|a\\|^4(s^2-r^2)^2<\\|a\\|^4r^4=f(W), where the inequality uses 0<r2−s2<r20<r^2-s^2<r^2. If PW≠0PW\neq 0, then also ∣PW∣≠r\\|PW\\|\neq r by Lemma 1(c), so ∇f(W)≠0\nabla f(W)\neq 0 by Lemma 1(b), and f(W−η∇f(W))<f(W)f(W-\eta\nabla f(W))<f(W) for all sufficiently small η>0\eta>0, with W−η∇f(W)∈B(W,t)W-\eta\nabla f(W)\in \mathcal B(W,t). In both cases WW does not minimize ff over B(W,t)\mathcal B(W,t), so broxft(W)≠W\mathrm{brox}^t_f(W)\neq\\{W\\}.

Assumption 3.1, t≥rt\ge r: Let dist(W,Xf)>t\mathrm{dist}(W,\mathcal X_f)>t. If ∣PW∣≤r\\|PW\\|\le r, Lemma 1(c) gives dist(W,Xf)=r−∣PW∣≤r≤t\mathrm{dist}(W,\mathcal X_f)=r-\\|PW\\|\le r\le t, giving a contradiciton. Hence dist(W,Xf)=∣PW∣−r>t\mathrm{dist}(W,\mathcal X_f)=\\|PW\\|-r>t. Let N=PW/∣PW∣N=PW/\\|PW\\|, so that ∣N∣=1\\|N\\|=1 and PN=NPN=N. For V∈B(W,t)V\in \mathcal B(W,t), ∣PV∣≥∣PW∣−∣P(V−W)∣≥∣PW∣−∣V−W∣≥∣PW∣−t.\\|PV\\|\ge\\|PW\\|-\\|P(V-W)\\|\ge\\|PW\\|-\\|V-W\\|\ge\\|PW\\|-t. This lower bound is attained in the ball by U:=W−tNU:=W-tN. Indeed, ∣U−W∣=t\\|U-W\\|=t, and PU=PW−tPN=(∣PW∣−t)NPU=PW-tPN=(\\|PW\\|-t)N, so ∣PU∣=∣PW∣−t\\|PU\\|=\\|PW\\|-t. By Lemma 1(b), f(V)=∣a∣4(∣PV∣2−r2)2f(V)=\\|a\\|^4(\\|PV\\|^2-r^2)^2, and s↦(s2−r2)2s\mapsto(s^2-r^2)^2 is strictly increasing on (r,∞)(r,\infty). Hence VV minimizes ff over B(W,t)\mathcal B(W,t) if and only if ∣PV∣=∣PW∣−t\\|PV\\|=\\|PW\\|-t, i.e. if and only if equality holds throughout. The third equality means ∣V−W∣=t\\|V-W\\|=t. The second means V−W∈range(P)V-W\in\mathrm{range}(P). The first, ∣PW+P(V−W)∣=∣PW∣−∣P(V−W)∣\\|PW+P(V-W)\\|=\\|PW\\|-\\|P(V-W)\\|, where ∣P(V−W)∣≤t<∣PW∣\\|P(V-W)\\|\le t<\\|PW\\|, means P(V−W)=−μPWP(V-W)=-\mu PW for some μ≥0\mu\ge 0 (both sides are nonnegative, so squaring shows that the equality is equivalent to ⟨PW,P(V−W)⟩=−∣PW∣ ∣P(V−W)∣\langle PW,P(V-W)\rangle=-\\|PW\\|\,\\|P(V-W)\\|, the equality case of Cauchy–Schwarz). Together, V−W=P(V−W)=−μPWV-W=P(V-W)=-\mu PW with ∣V−W∣=t\\|V-W\\|=t, so V−W=−tNV-W=-tN. Hence broxft(W)=U\mathrm{brox}^t_f(W)=\\{U\\}. For any X⋆∈XfX_\star\in\mathcal X_f and for all ZZ, we have ⟨N,Z⟩=⟨PN,Z⟩=⟨N,PZ⟩\langle N,Z\rangle=\langle PN,Z\rangle=\langle N,PZ\rangle and ∣PX⋆∣=r\\|PX_\star\\|=r, so by Cauchy–Schwarz ⟨W−U,X⋆−U⟩=t(⟨N,PX⋆⟩−⟨N,PU⟩)≤t(r−(∣PW∣−t))<0,\langle W-U,X_\star-U\rangle=t\big(\langle N,PX_\star\rangle-\langle N,PU\rangle\big)\le t\big(r-(\\|PW\\|-t)\big)<0, where the first inequality uses Cauchy–Schwarz, ⟨N,PX⋆⟩≤∣N∣ ∣PX⋆∣=r\langle N,PX_\star\rangle\le\\|N\\|\,\\|PX_\star\\|=r together with ⟨N,PU⟩=∣PW∣−t\langle N,PU\rangle=\\|PW\\|-t.

Assumption 3.1 fails if t<rt<r: Fix X⋆∈XfX_\star\in\mathcal X_f. By Lemma 1(c), dist(0,Xf)=r>t\mathrm{dist}(0,\mathcal X_f)=r>t. For V∈B(0,t)V\in B(0,t), ∣PV∣≤∣V∣≤t<r\\|PV\\|\le\\|V\\|\le t<r, and s↦(s2−r2)2s\mapsto(s^2-r^2)^2 is strictly decreasing on [0,r)[0,r). Hence VV minimizes ff over B(0,t)B(0,t) if and only if ∣PV∣=t\\|PV\\|=t, i.e. ∣PV∣=∣V∣=t\\|PV\\|=\\|V\\|=t, so broxft(0)=V∈range(P):∣V∣=t\mathrm{brox}^t_f(0)=\\{V\in\mathrm{range}(P):\\|V\\|=t\\}. This set contains U:=−tPX⋆/rU:=-tPX_\star/r, since U∈range(P)U\in\mathrm{range}(P) and ∣U∣=t∣PX⋆∣/r=t\\|U\\|=t\\|PX_\star\\|/r=t. Since ⟨PX⋆,X⋆⟩=⟨P2X⋆,X⋆⟩=∣PX⋆∣2=r2\langle PX_\star,X_\star\rangle=\langle P^2X_\star,X_\star\rangle=\\|PX_\star\\|^2=r^2 by Lemma 1(a), ⟨0−U,X⋆−U⟩=−⟨U,X⋆⟩+∣U∣2=tr+t2>0.\langle 0-U,X_\star-U\rangle=-\langle U,X_\star\rangle+\\|U\\|^2=tr+t^2>0 . As X⋆∈XfX_\star\in\mathcal X_f was arbitrary, Assumption 3.1 fails, and f∉FIBA(t)f\notin\mathcal F^{\rm BA}_I(t). □\square

Proposition 2. (a) For X⋆∈XfX_\star\in\mathcal X_f, the point X⋆′=X⋆−2PX⋆X_\star'=X_\star-2PX_\star lies in Xf\mathcal X_f and f(12(X⋆+X⋆′))=y2>0f\big(\tfrac12(X_\star+X_\star')\big)=y^2>0. Hence ff is not quasiconvex, and not ζ\zeta-quasar convex (in particular not star-convex) with respect to any X⋆∈XfX_\star\in\mathcal X_f and ζ∈(0,1]\zeta\in(0,1]. (b) Every WW with Wa=0Wa=0 satisfies ∇f(W)=0\nabla f(W)=0 and f(W)=y2>0f(W)=y^2>0. Hence ff is not pseudoconvex, does not satisfy the PŁ inequality, and does not satisfy the aiming condition.

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

This paper introduces the class of Broximal Aligned functions, and then proves that the Ball Proximal Point Method (BPM) converges to a global minimizer within this class. Broximal Aligned functions satisfy two properties. First, for a fixed class parameter t>0, there exists a global minimum x* such that for all x not in the t-radius ball neighborhood of the global minima, all local minima returned by the Broximal oracle for x lie in the ball of diameter |x-x*| centered midway between x and x*. Second, if x is itself the only point returned by the Broximal oracle, then x must be a global minimum. The goal of introducing this class is to provide a new view of global convergence analysis without relying on unrealistic assumptions for many ML problems, such as convexity and connectedness of minima, while moving away from stationarity as a convergence criterion. It is shown that several commonly used classes of functions are also Broximal Aligned. Finally, a brief discussion of potential feasible approximations of the Broximal oracle is presented.

Critical strengths
  1. The paper introduces a general class of functions that moves away from the problematic notion of stationarity as a global convergence criterion, while allowing multiple local minima and disconnected minimizer sets. In addition, it subsumes classes defined by restrictive properties in modern neural network training such as strict quasiconvexity, pseudoconvexity, quasar convexity, and aiming. If a plausible link to current practice could be established, such as the Muon analogy, this notion could lead to a new way to think about global convergence.
Critical weaknesses
  1. As of now, it is unclear whether the introduced class is actually meaningful. As noted by the paper, any function is Broximal Aligned for sufficiently large t, and increasing it is the only way to avoid bad local minima being detectable at a scale of radius t. This suggests that the notion simply burdens the oracle with the intrinsic hardness of the general problem, as evidenced by the sampling strategy suggested to approximately implement the oracle, which is essentially the best you can do in that case (i.e., the Nemirovski-Yudin complexity lower bounds). The paper concedes this point, but does not address it. Rather than making connections with standard function classes, it would be really important to argue convincingly, with a concrete example, that the proposed notion could realistically lead to a new way of thinking about global convergence.
Questions for authors
  1. Can you exhibit a realistic example of a problem in the proposed class where t is small in the global scale, so that the ball doesn't trivially contain the minimizer?
3 comments

We thank the reviewer for finding the paper informative, clear, and technically sound, and for recognizing the potential of our framework as a new way to think about global convergence. The weakness and the question raised both concern the same issue, namely whether broximal alignment is a meaningful restriction for realistic values of tt, so we address them together.


The meaningful quantity in our framework is the smallest radius tt for which a function is broximally aligned. That every function is aligned for a large enough tt does not make the class trivial, in the same way that every C2C^2 function has a Lipschitz gradient on a bounded set for a large enough LL, yet LL-smoothness is still meaningful, and one typically thinks of it in terms of the smallest constant satisfying the defining inequality. Our guarantees likewise depend on tt explicitly, as Theorem 4.1 needs O(∣x0−x⋆∣X2/t2)O(\\|x_0-x_\star\\|_X^2/t^2) oracle calls.

Importantly, increasing tt until the ball covers a global minimizer is not the only (or the best) way to handle local minima. Assumption 3.2 only asks that every non-global local minimum have another point with no larger value within distance tt. This is a necessary condition for the method to make progress. Indeed, it would be unreasonable to expect escape from a local minimum without any restriction on how far away the nearest point that is at least as good lies.

A very simple illustration is given in Example 1 of the paper, where the function has infinitely many non-global local minima, yet belongs to the class for t=2πt=2\pi, the period of the oscillation. The required radius is governed by the scale of the spurious structures, which can be arbitrarily small compared to ∣x0−x⋆∣\\|x_0-x_\star\\|.

Numerous other realistic examples in which tt is (arbitrarily) small relative to the global scale are already covered by our results. In particular, the function classes considered in Theorems 5.1-5.4 (pseudoconvex, quasar-convex, aiming functions with a unique global minimizer, strictly quasiconvex functions) are all contained in our class for every t>0t>0. These classes have been extensively studied in the literature and have found applications in machine learning and beyond. Our function class generalizes these well-established classes, while allowing the radius tt to be arbitrarily small.

For landscapes with spurious stationary points, we added in response to Reviewer Mi5X the one-hidden-layer network with quadratic activation f(W)=(∣Wa∣2−y)2f(W)=(\\|Wa\\|^2-y)^2 with W∈Rk×dW\in\mathbb R^{k\times d}. Here, dist(W,Xf)\mathrm{dist}(W,\mathcal X_f) is unbounded, yet ff belongs to the class if and only if t≥y/∣a∣t\ge \sqrt y/\\|a\\|. Moreover, BPM steps have closed form solution, and the ball contains no minimizer until the last step.

Regarding the oracle, our goal is mainly conceptual: to identify which structural properties of the objective enable global guarantees beyond stationarity, with BPM as the canonical method through which to study them. The proximal point method is analogous. 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 many practical approximations. We would also like to highlight that Theorem 4.1 does not transfer the hardness of the general problem to the oracle. It localizes the problem: one search over a ball of radius ∣x0−x⋆∣\\|x_0-x_\star\\| becomes O(∣x0−x⋆∣2/t2)O(\\|x_0-x_\star\\|^2/t^2) searches over balls of radius tt, whose difficulty is governed by tt instead of the distance to the solution, and to which a local subsolver can be applied.


We believe these clarifications and additional examples address all concerns raised in the review. They demonstrate that broximal alignment is a meaningful structural property that captures a broad range of relevant objective functions, and establish a useful new perspective on global convergence beyond stationarity. Given that we have addressed the concerns raised, and in light of the reviewer's positive assessment of the paper's clarity, technical soundness, and potential, we would be grateful if the reviewer would consider increasing their overall score.

AuthorsOpenReview ↗

Additional response

1. A fixed-radius example beyond quasiconvexity and quasar convexity.

Consider the one-hidden-layer network ha,w(z)=a((wz)2−1)h_{a,w}(z)=a((wz)^2-1), with both scalar weights trainable, and squared loss on (z,y)=(1,0)(z,y)=(1,0): F(a,w)=a2(w2−1)2.F(a,w)=a^2(w^2-1)^2. Its global minimizers form XF={a=0}∪{w=1}∪{w=−1}.\mathcal X_F=\lbrace a=0\rbrace\cup\lbrace w=1\rbrace\cup\lbrace w=-1\rbrace. This set is nonconvex and is not star-shaped about any point. Hence FF is neither quasiconvex nor quasar convex about any minimizer.

Nevertheless, both alignment assumptions hold with the fixed reference minimizer (0,0)(0,0) for every t≥1t\ge1. Here is a direct verification. If dist⁡(θ,XF)>t≥1\operatorname{dist}(\theta,\mathcal X_F)>t\ge1, then the center θ=(a,w)\theta=(a,w) satisfies ∣a∣>t|a|>t and ∣w∣>t+1|w|>t+1. Thus every point u=(A,W)u=(A,W) in the ball has A≠0A\ne0 and ∣W∣>1|W|>1. At any ball minimizer, the nonzero gradient satisfies ∇F(u)=λ(θ−u)\nabla F(u)=\lambda(\theta-u) with λ>0\lambda>0. Therefore,

=\frac{2A^2(W^2-1)(3W^2-1)}{\lambda}>0.$$ This proves Assumption 3.1. At every nonoptimal point, $\partial_aF=2a(w^2-1)^2\ne0$, so a strictly improving point exists in every positive-radius ball, proving Assumption 3.2. Now start at $\theta^0=(R,R+1)$. Then $$\operatorname{dist}(\theta^0,\mathcal X_F)=R.$$ We may keep $t=1$ while taking $R$ arbitrarily large. Thus $t/\operatorname{dist}(\theta^0,\mathcal X_F)\to0$, and the first ball contains no solution when $R>1$. The radius is set by a fixed feature of the activation, independently of initialization. This is a minimal zero-target example, with its special structure stated explicitly. There is also an example using ReLU: $G(a,w)=a^2\max(0,w)^2$ satisfies both assumptions for every $t>0$. Its homogeneity, $G(s\theta)=s^4G(\theta)$, proves alignment by moving a purportedly misaligned ball minimizer slightly toward the origin. Here too, $\operatorname{dist}((R,R),\mathcal X_G)=R$. This example is star-convex; the preceding one establishes additional coverage. **2. A nonconvex family with a tractable ball oracle.** Let $g$ be regularized logistic regression, $$g(x)=\frac1n\sum_i\log(1+\exp(-b_i a_i^\top x)) +\frac{\mu}{2}||x||^2,\qquad\mu>0,$$ and set $c=g(0)+1$, $f=(g-c)^3$. Strict monotonicity of the scalar cubic gives $$\operatorname{brox}_f^t(x)=\operatorname{brox}_g^t(x)$$ for every $x$ and $t>0$. Consequently, every ball subproblem is strongly convex and can be solved to prescribed accuracy using projected gradient descent or other convex solvers. The global optimizer is generally not available in closed form. Yet $f$ is nonconvex and has nonoptimal stationary points on $g=c$, since $$\nabla f=3(g-c)^2\nabla g.$$ Gradient descent initialized on this level set cannot move, whereas every exact Brox step strictly improves the objective. The transformation changes gradient geometry while leaving the ball minimizers unchanged. The same invariance permits the full convex Brox geometry to survive a nonconvex change of objective scale. This is a constructed family with hidden convexity; directly minimizing $g$ is also possible. It establishes tractability of a concrete subclass and a specific advantage over gradient descent on $f$, rather than an empirical speedup over all competing methods. Finite-precision inner solves require an inexact analysis. **3. Scope and a correction to our earlier wording.** A sufficiently large ball containing a solution guarantees termination from that particular center. It does not imply that every function satisfies the globally quantified alignment condition for some finite radius on an unbounded domain. We will correct that statement. We also agree that localization alone does not establish a complexity improvement: small-radius subproblems can remain hard, and their cost must be analyzed for the function class in question. The examples above provide explicit separation between radius and global distance, and a separate tractable-oracle construction. They strengthen the conceptual contribution without asserting that arbitrary neural-network losses admit efficient global optimization.

We would like to kindly follow up as the discussion period is coming to a close. We have made a substantial effort to address all the concerns raised in your reviews, including providing additional explanations and examples to clarify and strengthen the paper.

We believe that our responses have satisfactorily addressed your concerns. In particular, given your positive initial assessment of the soundness and clarity of the work, we would be grateful if you could reconsider your overall score in light of the additional clarifications.

Thank you again for your time and consideration!

Comments on the paper

1 comment

Dear Reviewers,

Thank you again for taking the time to review our paper and provide your feedback.

We have carefully addressed all the concerns raised in the reviews in our rebuttal, providing additional explanations, clarifications, and justifications where needed. We believe that our responses have resolved the questions raised and addressed the main points underlying the reviewers' assessments.

As the discussion period is approaching its end, we would really appreciate it if you could take another look at our rebuttal and reconsider your evaluations in light of our responses. In particular, if our clarifications have addressed your concerns, we would be grateful if you could reflect this in your updated scores.

We would also be very happy to clarify any remaining questions or concerns.

Thank you again for your time and consideration.

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.