The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications

2025-02-04 · Kaja Gruntkowska, Hanmin Li, Aadi Rane, Peter Richtárik

Non-smooth and non-convex global optimization poses significant challenges across various applications, where standard gradient-based methods often struggle. We propose the Ball-Proximal Point Method, Broximal Point Method, or Ball Point Method (BPM) for short - a novel algorithmic framework inspired by the classical Proximal Point Method (PPM) (Rockafellar, 1976), which, as we show, sheds new light on several foundational optimization paradigms and phenomena, including non-convex and non-smooth optimization, acceleration, smoothing, adaptive stepsize selection, and trust-region methods. At the core of BPM lies the ball-proximal ("broximal") operator, which arises from the classical proximal operator by replacing the quadratic distance penalty by a ball constraint. Surprisingly, and in sharp contrast with the sublinear rate of PPM in the nonsmooth convex regime, we prove that BPM converges linearly and in a finite number of steps in the same regime. Furthermore, by introducing the concept of ball-convexity, we prove that BPM retains the same global convergence guarantees under weaker assumptions, making it a powerful tool for a broader class of potentially non-convex optimization problems. Just like PPM plays the role of a conceptual method inspiring the development of practically efficient algorithms and algorithmic elements, e.g., gradient descent, adaptive step sizes, acceleration (Ahn & Sra, 2020), and "W" in AdamW (Zhuang et al., 2022), we believe that BPM should be understood in the same manner: as a blueprint and inspiration for further development.

📄 PDF Abstract BibTeX arXiv:2502.02002

Code (0)

등록된 구현이 없습니다.

Tasks

global-optimization

Methods 이 논문이 사용한 방법론

AdamW AdamW is a stochastic optimization method that modifies the typical implementation of weight decay in Adam, by decoupling [weight…

Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization

2025-10-01 · Kaja Gruntkowska, Peter Richtárik arxiv

The recently proposed Broximal Point Method (BPM) [Gruntkowska et al., 2025] offers an idealized optimization framework based on iteratively minimizing the objective function over norm balls centered at the current itera…

Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold

2018-11-02 · Shixiang Chen, Shiqian Ma, Anthony Man-Cho So, Tong Zhang

We consider optimization problems over the Stiefel manifold whose objective function is the summation of a smooth function and a nonsmooth function. Existing methods for solving this kind of problems can be classified in…

Learning Proximal Operators to Discover Multiple Optima

2022-01-28 · Lingxiao Li, Noam Aigerman, Vladimir G. Kim, Jiajin Li 외

Finding multiple solutions of non-convex optimization problems is a ubiquitous yet challenging task. Most past algorithms either apply single-solution optimization methods from multiple random initial guesses or search i…

object-detection Object Detection

Neural Proximal/Trust Region Policy Optimization Attains Globally Optimal Policy

2019-06-25 · Boyi Liu, Qi Cai, Zhuoran Yang, Zhaoran Wang

Proximal policy optimization and trust region policy optimization (PPO and TRPO) with actor and critic parametrized by neural networks achieve significant empirical success in deep reinforcement learning. However, due to…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Neural Trust Region/Proximal Policy Optimization Attains Globally Optimal Policy

2019-12-01 · NeurIPS 2019 12 · Boyi Liu, Qi Cai, Zhuoran Yang, Zhaoran Wang

Deep Reinforcement Learning Reinforcement Learning Reinforcement Learning (RL)