A restricted memory quasi-Newton bundle method for nonsmooth optimization on Riemannian manifolds
Pith reviewed 2026-05-24 03:32 UTC · model grok-4.3
The pith
A restricted memory quasi-Newton bundle method converges globally to stationary points for nonsmooth functions on Riemannian manifolds.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The method generates candidate directions via aggregated subgradients and quasi-Newton Hessian approximations in the tangent space, performs a Riemannian line search, and establishes that if only finitely many serious steps occur the final one is stationary, while otherwise every accumulation point of the serious sequence is stationary. A limited-memory variant further lowers storage and computation.
What carries the argument
Riemannian quasi-Newton bundle method with subgradient aggregation and Riemannian semismooth line search
If this is right
- The quasi-Newton updates speed up convergence of the bundle method.
- The aggregation technique cuts the cost of solving the quadratic programming subproblem.
- The methods outperform existing Riemannian optimization techniques on locally Lipschitz problems.
- The limited-memory version maintains performance with lower computational cost.
Where Pith is reading between the lines
- If the semismoothness holds for common nonsmooth functions like max or norms on manifolds, the line search becomes practical.
- Similar aggregation could reduce costs in other manifold optimization algorithms.
- Extending the framework to stochastic or online settings might preserve convergence while handling larger problems.
Load-bearing premise
The Riemannian line-search procedure terminates in finite steps under the proposed Riemannian semismoothness assumption.
What would settle it
A concrete function on a manifold, such as the distance to a nonsmooth set, where the line search loops infinitely or an accumulation point fails to be stationary despite satisfying the method's update rules.
read the original abstract
In this paper, a restricted memory quasi-Newton bundle method for minimizing a locally Lipschitz continuous function over a Riemannian manifold is proposed. The curvature information of the objective function is approximated by applying a Riemannian version of the quasi-Newton updating formulas. A Riemannian subgradient aggregation technique is proposed and used to significantly reduce the computations in the quadratic programming subproblem when calculating the candidate descent direction. Moreover, a Riemannian line-search procedure is proposed to generate the stepsizes, and the process is finitely terminated under the assumption of a newly proposed Riemannian semismoothness. Global convergence of the proposed method is established: if the serious iteration steps are finite, then the last serious iterate is stationary; otherwise, every accumulation point of the serious iteration sequence is stationary. In addition, a modified algorithm with limited-memory quasi-Newton updates is presented to further reduce the computational cost. Finally, numerical experiments demonstrate that (i) the quasi-Newton updates accelerate the convergence of the bundle method, (ii) the aggregation technique significantly reduces the computational cost for solving the quadratic programming subproblem, and (iii) the proposed methods outperform the compared state-of-the-art Riemannian optimization methods for locally Lipschitz continuous functions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes a restricted memory quasi-Newton bundle method for minimizing locally Lipschitz continuous functions on Riemannian manifolds. It incorporates Riemannian quasi-Newton updating formulas for curvature approximation, a Riemannian subgradient aggregation technique to reduce the size of the quadratic programming subproblem, and a Riemannian line-search whose finite termination is asserted under a newly introduced Riemannian semismoothness assumption. Global convergence is claimed: if the number of serious steps is finite then the last serious iterate is stationary; otherwise every accumulation point of the serious sequence is stationary. A limited-memory variant is also presented, and numerical experiments are reported to show acceleration from the quasi-Newton updates, cost reduction from aggregation, and outperformance versus existing Riemannian methods for nonsmooth problems.
Significance. If the convergence theorem is valid and the new semismoothness condition holds for the intended problem class, the combination of bundle methods with restricted-memory quasi-Newton updates and aggregation on manifolds would constitute a useful algorithmic advance for nonsmooth Riemannian optimization. The explicit reduction in QP subproblem size via aggregation and the limited-memory option address practical computational bottlenecks. The numerical claims of outperformance, however, rest on experiments whose statistical robustness and problem specifications are not fully detailed in the provided abstract.
major comments (2)
- [section describing the Riemannian line-search procedure and the associated semismoothness assumption] The global convergence statement (abstract and main theorem) requires that the Riemannian line-search procedure terminates after finitely many trials. This termination is asserted only under the newly proposed Riemannian semismoothness condition. The manuscript does not establish that this condition holds for the class of locally Lipschitz functions under consideration, nor does it supply verifiable sufficient conditions or examples confirming its plausibility; consequently the convergence guarantee is conditional on an assumption whose scope remains unverified.
- [numerical experiments section] Numerical experiments claim that the proposed methods outperform state-of-the-art Riemannian optimization methods for locally Lipschitz functions and that quasi-Newton updates accelerate convergence while aggregation reduces QP cost. These claims are presented without reported error bars, number of random trials, or precise dataset/problem specifications, which weakens the empirical support for the practical advantages asserted in the abstract.
minor comments (2)
- [abstract and conclusion] The abstract enumerates three numerical observations with (i), (ii), (iii); the concluding section should mirror this enumeration for consistency.
- [preliminaries] Notation for the Riemannian metric, exponential map, and parallel transport should be introduced once with explicit references to standard manifold references to aid readers unfamiliar with the geometric setting.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will incorporate revisions to strengthen the paper.
read point-by-point responses
-
Referee: [section describing the Riemannian line-search procedure and the associated semismoothness assumption] The global convergence statement (abstract and main theorem) requires that the Riemannian line-search procedure terminates after finitely many trials. This termination is asserted only under the newly proposed Riemannian semismoothness condition. The manuscript does not establish that this condition holds for the class of locally Lipschitz functions under consideration, nor does it supply verifiable sufficient conditions or examples confirming its plausibility; consequently the convergence guarantee is conditional on an assumption whose scope remains unverified.
Authors: We agree that the new Riemannian semismoothness assumption requires further clarification to make the convergence result more applicable. In the revised manuscript we will add a dedicated subsection providing verifiable sufficient conditions (e.g., when the function is convex or when the manifold is Euclidean) under which the assumption holds, together with explicit examples of locally Lipschitz functions on manifolds that satisfy the condition. This will directly address the scope of the assumption without altering the main theorem statement. revision: yes
-
Referee: [numerical experiments section] Numerical experiments claim that the proposed methods outperform state-of-the-art Riemannian optimization methods for locally Lipschitz functions and that quasi-Newton updates accelerate convergence while aggregation reduces QP cost. These claims are presented without reported error bars, number of random trials, or precise dataset/problem specifications, which weakens the empirical support for the practical advantages asserted in the abstract.
Authors: We acknowledge that the experimental section would benefit from greater statistical detail. In the revision we will expand the numerical results to include the exact number of independent random trials, report performance means accompanied by standard deviations or error bars, and provide complete specifications of all test problems (including manifold dimensions, function definitions, and initialization procedures). These additions will strengthen the empirical claims while preserving the existing figures and tables. revision: yes
Circularity Check
No circularity: convergence is conditional on stated assumptions without reduction to inputs by construction
full rationale
The paper proposes a bundle method with Riemannian quasi-Newton updates, aggregation, and line-search, then proves global convergence (if serious steps finite then last iterate stationary; else accumulation points stationary) under the explicit assumption that the line-search terminates finitely when the objective satisfies the newly introduced Riemannian semismoothness. This is a standard conditional proof structure resting on algorithmic construction and the semismoothness hypothesis; the result does not redefine itself, rename a fitted quantity as a prediction, or reduce via self-citation chain to an unverified prior claim by the same authors. No equations or steps are exhibited that equate the claimed convergence to its own inputs by definition. The derivation remains self-contained against the listed assumptions.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Riemannian semismoothness (newly proposed)
Reference graph
Works this paper leans on
-
[1]
Princeton University Press, Princeton, NJ (2009) 29
Absil, P.A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Mat rix Manifolds. Princeton University Press, Princeton, NJ (2009) 29
work page 2009
-
[2]
In: Seyedehsomayeh Hosseini, A.U
Absil, P.A., Hosseini, S.: A collection of nonsmooth Riemannian optimiza tion problems. In: Seyedehsomayeh Hosseini, A.U. Boris S. Mordukhovic h (ed.) Non- smooth Optimization and Its Applications, International Series of N umerical Mathematics vol. 170, pp. 1–15. Birkh¨ auser, Cham (2019)
work page 2019
-
[3]
T o appear with Cambridge University Press, Cambridge (2022)
Boumal, N.: An Introduction to Optimization on Smooth Manifolds. T o appear with Cambridge University Press, Cambridge (2022). http://www.nicolasboumal. net/book
work page 2022
-
[4]
Journal of the Operations Research Society of China 8(2), 199–248 (2020)
Hu, J., Liu, X., Wen, Z.W., Yuan, Y.X.: A brief introduction to manifold o pti- mization. Journal of the Operations Research Society of China 8(2), 199–248 (2020)
work page 2020
-
[5]
Sato, H.: Riemannian Optimization and Its Applications. Springer, S witzerland (2021)
work page 2021
-
[6]
Journal of Optimization Theory and Applications 37(2), 177–219 (1982)
Gabay, D.: Minimizing a differentiable function over a differential man ifold. Journal of Optimization Theory and Applications 37(2), 177–219 (1982)
work page 1982
-
[7]
Fields in stitute communications 3(3), 113–135 (1994)
Smith, S.T.: Optimization techniques on Riemannian manifolds. Fields in stitute communications 3(3), 113–135 (1994)
work page 1994
-
[8]
SIAM Journal on Optimization 22(2), 596–627 (2012)
Ring, W., Wirth, B.: Optimization methods on Riemannian manifolds and their application to shape space. SIAM Journal on Optimization 22(2), 596–627 (2012)
work page 2012
-
[9]
SIAM Journal on Optimization 25(3), 1660–1685 (2015)
Huang, W., Gallivan, K.A., Absil, P.A.: A Broyden class of quasi-Newton methods for Riemannian optimization. SIAM Journal on Optimization 25(3), 1660–1685 (2015)
work page 2015
-
[10]
SI AM Journal on Optimization 28(1), 470–495 (2018)
Huang, W., Absil, P.-A., Gallivan, K.A.: A Riemannian BFGS method witho ut differentiated retraction for nonconvex optimization problems. SI AM Journal on Optimization 28(1), 470–495 (2018)
work page 2018
-
[11]
Computational Optimization and Applicat ions 77(3), 811–830 (2020)
Sakai, H., Iiduka, H.: Hybrid Riemannian conjugate gradient meth ods with global convergence properties. Computational Optimization and Applicat ions 77(3), 811–830 (2020)
work page 2020
-
[12]
Journal of Optimization Theory and Applications 190(1), 130–150 (2021)
Sakai, H., Iiduka, H.: Sufficient descent riemannian conjugate gr adient methods. Journal of Optimization Theory and Applications 190(1), 130–150 (2021)
work page 2021
-
[13]
Journal of Functional A nalysis 220(2), 304–361 (2005)
Azagra, D., Ferrera, J., L´ opez-Mesas, F.: Nonsmooth analys is and Hamilton– Jacobi equations on Riemannian manifolds. Journal of Functional A nalysis 220(2), 304–361 (2005)
work page 2005
-
[14]
Nonlinear Analysis: Theory, Me thods & Applications 74(12), 3884–3895 (2011) 30
Hosseini, S., Pouryayevali, M.: Generalized gradients and charac terization of epi- Lipschitz sets in Riemannian manifolds. Nonlinear Analysis: Theory, Me thods & Applications 74(12), 3884–3895 (2011) 30
work page 2011
-
[15]
Journal of Optimization Theory and Applications 158, 328–342 (2013)
Hosseini, S., Pouryayevali, M.R.: Nonsmooth optimization techniqu es on Rieman- nian manifolds. Journal of Optimization Theory and Applications 158, 328–342 (2013)
work page 2013
-
[16]
Journal of Optimization Theory and Applications 97(1), 93–104 (1998)
Ferreira, O.P., Oliveira, P.R.: Subgradient algorithm on Riemannian m anifolds. Journal of Optimization Theory and Applications 97(1), 93–104 (1998)
work page 1998
-
[17]
Optimization 68(4), 713–729 (2019)
Ferreira, O.P., Louzeiro, M.S., Prudente, L.F.: Iteration-comple xity of the sub- gradient method on Riemannian manifolds with lower bounded curvatu re. Optimization 68(4), 713–729 (2019)
work page 2019
-
[18]
Advances in Computational Mathematics 42(2), 333–360 (2016)
Grohs, P., Hosseini, S.: ε-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds. Advances in Computational Mathematics 42(2), 333–360 (2016)
work page 2016
-
[19]
IMA Journal of Numerical Analys is 36(3), 1167–1192 (2016)
Grohs, P., Hosseini, S.: Nonsmooth trust region algorithms for lo cally lipschitz functions on riemannian manifolds. IMA Journal of Numerical Analys is 36(3), 1167–1192 (2016)
work page 2016
-
[20]
SIAM Journal on Optimizatio n 28(1), 596–619 (2018)
Hosseini, S., Huang, W., Yousefpour, R.: Line search algorithms f or locally Lips- chitz functions on Riemannian manifolds. SIAM Journal on Optimizatio n 28(1), 596–619 (2018)
work page 2018
-
[21]
SIAM Journal on Optimization 27(1), 173–189 (2017)
Hosseini, S., Uschmajew, A.: A Riemannian gradient sampling algorit hm for nons- mooth optimization on manifolds. SIAM Journal on Optimization 27(1), 173–189 (2017)
work page 2017
-
[22]
SIAM Jour nal on Optimization 29(4), 2853–2880 (2019)
Hosseini, S., Uschmajew, A.: A gradient sampling method on algebr aic vari- eties and application to nonsmooth low-rank optimization. SIAM Jour nal on Optimization 29(4), 2853–2880 (2019)
work page 2019
-
[23]
SIAM Journal on Optimization 30(1), 210–239 (2020)
Chen, S., Ma, S., Man-Cho So, A., Zhang, T.: Proximal gradient me thod for nonsmooth optimization over the stiefel manifold. SIAM Journal on Optimization 30(1), 210–239 (2020)
work page 2020
-
[24]
Mathe matical Programming 194(1-2), 371–413 (2022)
Huang, W., Wei, K.: Riemannian proximal gradient methods. Mathe matical Programming 194(1-2), 371–413 (2022)
work page 2022
-
[25]
Mathematical Programming, 1–61 (2022)
Zhou, Y., Bao, C., Ding, C., Zhu, J.: A semismooth newton based au g- mented lagrangian method for nonsmooth optimization on matrix man ifolds. Mathematical Programming, 1–61 (2022)
work page 2022
-
[26]
Optimization methods and software 17(1), 1–29 (2002)
M¨ akel¨ a, M.: Survey of bundle methods for nonsmooth optimization. Optimization methods and software 17(1), 1–29 (2002)
work page 2002
-
[27]
Bagirov, A., Karmitsa, N., M¨ akel¨ a, M.M.: Introduction to Nonsmooth Optimiza- tion: Theory, Practice and Software vol. 12. Springer, New York ( 2014) 31
work page 2014
-
[28]
Numerische Mathematik 1, 253–268 (1959)
Cheney, E.W., Goldstein, A.A.: Newton’s method for convex progr amming and Tchebycheff approximations. Numerische Mathematik 1, 253–268 (1959)
work page 1959
-
[29]
Jr: The cutting-plane method for solving convex pro grams
Kelley, J.E. Jr: The cutting-plane method for solving convex pro grams. Journal of the society for Industrial and Applied Mathematics 8(4), 703–712 (1960)
work page 1960
-
[30]
Mathematical Programming 46(1-3), 105–122 (1990)
Kiwiel, K.C.: Proximity control in bundle methods for convex nondiff erentiable minimization. Mathematical Programming 46(1-3), 105–122 (1990)
work page 1990
-
[31]
SIAM Journal on Optimization 20(5), 2442–2473 (2010)
Hare, W., Sagastiz´ abal, C.: A redistributed proximal bundle met hod for noncon- vex optimization. SIAM Journal on Optimization 20(5), 2442–2473 (2010)
work page 2010
-
[32]
Mathematical Progr amming 148, 241–277 (2014)
Oliveira, W., Sagastiz´ abal, C., Lemar´ echal, C.: Convex proximalbundle methods in depth: a unified analysis for inexact oracles. Mathematical Progr amming 148, 241–277 (2014)
work page 2014
-
[33]
Journal of Global Optimization 70(3), 517–549 (2018)
Lv, J., Pang, L., Meng, F.: A proximal bundle method for constra ined nonsmooth nonconvex optimization with inexact information. Journal of Global Optimization 70(3), 517–549 (2018)
work page 2018
-
[34]
Journal of Industrial a nd Management Optimization 15(2), 757–774 (2019)
Tang, C.M., Jian, J.B., Li, G.Y.: A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial a nd Management Optimization 15(2), 757–774 (2019)
work page 2019
-
[35]
Computation al Optimization and Applications 74(2), 443–480 (2019)
Hoseini Monjezi, N., Nobakhtian, S.: A new infeasible proximal bun dle algorithm for nonsmooth nonconvex constrained optimization. Computation al Optimization and Applications 74(2), 443–480 (2019)
work page 2019
-
[36]
SIAM Journal on Optimization 2(1), 121–152 (1992)
Schramm, H., Zowe, J.: A version of the bundle idea for minimizing a n onsmooth function: conceptual idea, convergence analysis, numerical res ults. SIAM Journal on Optimization 2(1), 121–152 (1992)
work page 1992
-
[37]
SIAM Journal on Optimization 19(1), 281–306 (2008)
Apkarian, P., Noll, D., Prot, O.: A trust region spectral bundle me thod for non- convex eigenvalue optimization. SIAM Journal on Optimization 19(1), 281–306 (2008)
work page 2008
-
[38]
C omputa- tional Optimization and Applications 72(2), 391–412 (2019)
Liu, S.: A simple version of bundle method with linear programming. C omputa- tional Optimization and Applications 72(2), 391–412 (2019)
work page 2019
-
[39]
Mathematical Programming 69(1-3), 111–147 (1995)
Lemar´ echal, C., Nesterov, Y., Nemirovskii, A.: New variants of b undle methods. Mathematical Programming 69(1-3), 111–147 (1995)
work page 1995
-
[40]
Optimization Methods and Software 29(6), 1180–1209 (2014)
Oliveira, W., Sagastiz´ abal, C.: Level bundle methods for oracles with on-demand accuracy. Optimization Methods and Software 29(6), 1180–1209 (2014)
work page 2014
-
[41]
Mathematical Programming 149, 1–45 (2015) 32
Lan, G.: Bundle-level type methods uniformly optimal for smoot h and nonsmooth convex optimization. Mathematical Programming 149, 1–45 (2015) 32
work page 2015
-
[42]
Optimizat ion Letters 16(8), 2405–2434 (2022)
Tang, C., Li, Y., Jian, J., Zheng, H.: A new restricted memory level bundle method for constrained convex nonsmooth optimization. Optimizat ion Letters 16(8), 2405–2434 (2022)
work page 2022
-
[43]
Journal of Optimization Th eory and Applications 102(3), 593–613 (1999)
Lukˇ san, L., Vlˇ cek, J.: Globally convergent variable metric met hod for convex nonsmooth unconstrained minimization1. Journal of Optimization Th eory and Applications 102(3), 593–613 (1999)
work page 1999
-
[44]
Journal of Optimizatio n Theory and Applications 111(2), 407–430 (2001)
Vlˇ cek, J., Lukˇ san, L.: Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization. Journal of Optimizatio n Theory and Applications 111(2), 407–430 (2001)
work page 2001
-
[45]
Mathematic al Program- ming 109(1), 181–205 (2007)
Haarala, N., Miettinen, K., M¨ akel¨ a, M.M.: Globally convergent limite d memory bundle method for large-scale nonsmooth optimization. Mathematic al Program- ming 109(1), 181–205 (2007)
work page 2007
-
[46]
Pacific Journal of Optimization 18(2), 367– 393 (2022)
Tang, C., Chen, H., Jian, J., Liu, S.: A bundle-type quasi-Newton m ethod for nonconvex nonsmooth optimization. Pacific Journal of Optimization 18(2), 367– 393 (2022)
work page 2022
-
[47]
IMA Jo urnal of Numerical Analysis 43(1), 293–325 (2023)
Hoseini Monjezi, N., Nobakhtian, S., Pouryayevali, M.R.: A proxima l bundle algorithm for nonsmooth optimization on riemannian manifolds. IMA Jo urnal of Numerical Analysis 43(1), 293–325 (2023)
work page 2023
-
[48]
Society for In dustrial and Applied Mathematics, Philadelphia, PA (1990)
Clarke, F.H.: Optimization and Nonsmooth Analysis. Society for In dustrial and Applied Mathematics, Philadelphia, PA (1990)
work page 1990
-
[49]
Lecture Notes in Mathematics 1133
Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization . Lecture Notes in Mathematics 1133. Springer, Berlin (1985)
work page 1985
-
[50]
Lang, S.: Fundamentals of Differential Geometry vol. 191. Sprin ger, New York (1999)
work page 1999
-
[51]
Sakai, T.: Riemannian Geometry vol. 149. American Mathematical Soc., Provi- dence, RI (1992)
work page 1992
-
[52]
Mathematical Programming 150(2), 179–216 (2015)
Huang, W., Absil, P.-A., Gallivan, K.A.: A riemannian symmetric rank-o ne trust- region method. Mathematical Programming 150(2), 179–216 (2015)
work page 2015
-
[53]
Jour nal of Mathe- matical Extension 5(2.1), 23–29 (2011)
Ghahraei, E.: Semismooth function on riemannian manifolds. Jour nal of Mathe- matical Extension 5(2.1), 23–29 (2011)
work page 2011
-
[54]
Mathematics of Operations Research 2(2), 191–207 (1977)
Mifflin, R.: An algorithm for constrained optimization with semismoot h functions. Mathematics of Operations Research 2(2), 191–207 (1977)
work page 1977
-
[55]
Rendiconti del Circolo Matematico di Paler mo Series 2 71(1), 299–323 (2022) 33
Malmir, F., Barani, A.: Generalized submonotonicity and approxima tely convex- ity in riemannian manifolds. Rendiconti del Circolo Matematico di Paler mo Series 2 71(1), 299–323 (2022) 33
work page 2022
-
[56]
Jou rnal of Opti- mization Theory and Applications 44, 545–568 (1984)
Bihain, A.: Optimization of upper semidifferentiable functions. Jou rnal of Opti- mization Theory and Applications 44, 545–568 (1984)
work page 1984
-
[57]
SIAM Journal on Control and Optimization 15(6), 959–972 (1977)
Mifflin, R.: Semismooth and semiconvex functions in constrained op timization. SIAM Journal on Control and Optimization 15(6), 959–972 (1977)
work page 1977
-
[58]
Pacific Journal of Op timization 10(2), 415–434 (2014)
Yang, W.H., Zhang, L.-H., Song, R.: Optimality conditions for the no nlinear programming problems on riemannian manifolds. Pacific Journal of Op timization 10(2), 415–434 (2014)
work page 2014
-
[59]
In: Proceedings of the 18th European Symp osium on Artificial Neural Networks (2010)
Borckmans, P.B., Absil, P.A.: Oriented bounding box computation u sing parti- cle swarm optimization. In: Proceedings of the 18th European Symp osium on Artificial Neural Networks (2010)
work page 2010
-
[60]
Numerische Math ematik 136, 523–543 (2017) 34
Huang, W., Absil, P.-A., Gallivan, K.A.: Intrinsic representation of t angent vec- tors and vector transports on matrix manifolds. Numerische Math ematik 136, 523–543 (2017) 34
work page 2017
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.