REVIEW 2 major objections 4 minor 33 references
A Cubic Regularization Method for Multiobjective Optimization
T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper claims a cubic regularization method using approximate gradients and Hessians and a nonmonotone acceptance rule reaches an $\epsilon$-approximate Pareto critical point in at most $O(C\epsilon^{-3/2})$ iterations, with explicit…
desk verdict A solid multiobjective cubic regularization paper with a genuine algorithmic novelty and correct main complexity bound, but the abstract's derivative-free dimension exponents don't match the proofs and need correcting. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the regularized model $M_{x,\sigma}(y)=\max_{j\in\mathcal{J}} M^j_{x,\sigma}(y)$, with $M^j_{x,\sigma}(y)=\langle \bar\nabla F_j(x),y-x\rangle+\tfrac12\langle \bar\nabla^2 F_j(x)(y-x),y-x\rangle+\tfrac{\sigma}{6}\|y-x\|^3$, together with the approximate KKT conditions (3.2) on subproblem (1.3). The cubic term makes the model coercive, so a solution exists, and it yields the key decrease inequality (2.9), which converts Taylor-model error and finite-difference derivative errors into a step-size-dependent decrease. The nonmonotone acceptance test (3.3) then raises $\sigma$ (and tightens the derivative-error tolerances (3.1)) until that inequality holds, producing the telescoping sum that gives the $\epsilon^{-3/2}$ iteration bound.
What would settle it
On a smooth nonconvex multiobjective instance with known Lipschitz constants, run the method for a sequence of tolerances $\epsilon$ and record the first iteration where $\|\sum_j \lambda_t^j \nabla F_j(x_t)\le \epsilon$; the central claim predicts the count grows at most like a constant times $\epsilon^{-3/2}$, so observing a steeper growth rate, or a failure of the inner solver to meet (3.2), would refute the theorem.
Extended reading notes
Core claim
The central claim is that the scalar cubic-regularization paradigm survives the passage to several objectives: a point $(x_{t+1},\lambda_{t+1})$ generated from an approximate KKT point of subproblem (1.3) decreases every component of $F$ by an amount controlled by the cubic step, and this decrease is strong enough to make the weighted gradient sums $\sum_j \lambda_t^j \nabla F_j(x_t)$ tend to zero. Consequently all limit points of the sequence are Pareto critical, and an $\epsilon$-approximate Pareto critical point is certified in at most $O(C\epsilon^{-3/2})$ outer iterations under assumptions (A1)-(A2). When derivatives are unavailable, the paper shows that central finite-difference formulas with step proportional to $\|x_t-x_{t-1}\|/n^\beta$ satisfy the required error conditions, leading to $O(n^{1-\beta}\epsilon^{-3/2})$ iterations and $O(mn^{3-\beta}\epsilon^{-3/2})$ function evaluations for the derivative-free variant. Under the local convexity assumption (A3), the same sequence is shown to converge to a local Pareto solution, superlinearly if gradients are exact and quadratically if both gradients and Hessians are exact.
Load-bearing premise
The analysis assumes that every iteration can call a subroutine that returns an approximate solution of the cubic subproblem satisfying the fixed tolerance conditions (3.2), and that all objective Hessians are globally Lipschitz; if either fails, the stated iteration bounds are not guaranteed.
Editorial extensions
If this is right
- If the central claim is right, smooth nonconvex multiobjective problems can be solved with provable worst-case guarantees using only approximate gradients and Hessians, matching the scalar cubic-regularization rate of $O(\epsilon^{-3/2})$.
- The derivative-free variant makes the cost of missing analytic derivatives explicit: with $\beta\in[0,1]$ controlling the finite-difference step, the iteration count is $O(n^{1-\beta}\epsilon^{-3/2})$ and the function-evaluation count is $O(mn^{3-\beta}\epsilon^{-3/2})$, allowing a trade-off between larger steps (fewer, cheaper iterations) and smaller steps (more reliable derivative approximations
- Under local convexity the method does not sacrifice speed: exact gradients give superlinear convergence, and exact gradients plus Hessians give quadratic convergence, so the inexactness controls mainly affect the earlier, global phase of the run.
- Because the acceptance rule is nonmonotone and parameter-free, the algorithm can be used as a black-box stop when the weighted gradient norm, or its finite-difference proxy, falls below a tolerance, without pre-tuning a sufficient-decrease parameter.
Reading between the lines
- The practical cost of the derivative-free variant is dominated by the shrinking finite-difference step: as the iterates approach a Pareto critical point, $\|x_t-x_{t-1}\|\to 0$, so $h\to 0$ and function evaluations eventually suffer cancellation; choosing $\beta$ close to $1$ keeps $h$ larger but weakens the iteration bound, so the experimental choice $\beta=1/2$ is a plausible middle point.
- Subproblem (1.3) has a strictly feasible point and satisfies a constraint qualification, so any generic nonlinear programming solver that returns a point meeting (3.2) can be substituted for the augmented-Lagrangian solver used in the experiments; the method's guarantees are solver-agnostic.
- The error conditions (3.1) only require that gradient and Hessian errors decay with the previous step, so subsampled or randomized derivative estimators could plausibly be plugged in place of finite differences, at the price of probabilistic versions of Lemmas 3.9-3.14.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a multiobjective cubic regularization method (M-CRM) for nonconvex unconstrained multiobjective optimization. At each outer iteration, the algorithm constructs cubic-regularized models from approximate gradients and Hessians of the objective components, solves the resulting subproblem approximately in the KKT sense, and adjusts both the regularization parameter and the derivative-approximation accuracy through a nonmonotone line search. The main theoretical results are an O(C ε^{-3/2}) iteration bound for reaching an ε-approximate Pareto critical point under globally Lipschitz Hessians and bounded-below objectives, finite-difference variants of the algorithm, global convergence to weak Pareto critical points, and local superlinear or quadratic convergence under strong convexity of the objectives on a level set. Numerical experiments compare exact and inexact versions of the method against a safeguarded multiobjective Newton method, and a derivative-free variant is applied to a regularized logistic regression problem.
Significance. If the stated complexity claims are corrected, this is a valuable contribution. The exact-derivative version delivers the expected O(ε^{-3/2}) complexity for multiobjective cubic regularization, the joint adaptive control of the regularization parameter and derivative accuracy is a useful algorithmic idea, and the numerical study is reasonably extensive for a methods paper. The paper also contains careful proofs of global convergence and local rates, and the derivative-free implementation is accompanied by detailed finite-difference error bounds. The main weakness is that the abstract and introduction advertise finite-difference complexity exponents that are stronger than what the proofs establish; the correct exponents already appear in Remarks 3.13 and 3.15, so the discrepancy is internally visible and, in principle, fixable by rewriting the advertised claims.
major comments (2)
- [Abstract, Section 1, and Remark 3.15] The derivative-free complexity claims in the Abstract and Section 1 are not supported by the proof. Lemma 3.9 gives κ̄_G = L n^{(1-2β)/2} and Lemma 3.14 gives κ̄_H = L n^{1-β} for the finite-difference gradient and Hessian. Substituting these into Δ_0 in Eq. (3.6), the dominant term for β<1 is α(2κ̄_H)/2 ~ L n^{1-β}, so Δ_0 ~ n^{3(1-β)/2}. Theorem 3.3 therefore yields O(n^{3(1-β)/2} ε^{-3/2}) iterations, and multiplying by the O(m n^2) function evaluations per inner iteration (Lemma 3.2) gives O(m n^{(7-3β)/2} ε^{-3/2}) function evaluations. These are exactly the bounds stated in Remark 3.15, but they contradict the Abstract's O(n^{1-β} ε^{-3/2}) iterations and O(m n^{3-β} ε^{-3/2}) function evaluations. The advertised exponents are off by a factor of (3/2) in the iteration exponent and by n^{1/2} in the evaluation exponent; the Abstract and Section 1 should be corrected to match Remark 3.15, unless a different finite-difference step choice can justify the stronger bound.
- [Section 1 and Remark 3.13] The same dimension-exponent error appears in the claim for exact gradients with Hessians computed by finite differences based on gradient values. Section 1 states an iteration bound of O(n^{(1-2β)/2} ε^{-3/2}) and O(m n^{(3-2β)/2}) function and gradient evaluations for β∈[0,1/2]. However, Lemma 3.12 gives κ̄_H = L n^{(1-2β)/2}; with κ̄_G = 0, Eq. (3.6) gives Δ_0 ~ n^{3(1-2β)/4}, so Theorem 3.3 yields O(n^{3(1-2β)/4} ε^{-3/2}) iterations and, with O(m n) evaluations per inner iteration, O(m n^{(7-6β)/4} ε^{-3/2}) total evaluations. These are precisely the bounds stated in Remark 3.13. The Section 1 claims again omit the 3/2 power on the dimension-dependent factor and should be corrected.
minor comments (4)
- [Lemma 3.12, Eq. (3.38)] The displayed formula for the central-difference Hessian appears to have a typo in the last column: it reads ∇F_j(x+he_n) - ∇F_j(x-he_1), which should presumably be ∇F_j(x+he_n) - ∇F_j(x-he_n).
- [Lemma 3.9 and Algorithm 2] The expression for the step size h in Lemma 3.9 is typeset ambiguously: h := √6‖x_t-x_{t-1}‖/(n^β α^{(i-1)})^{1/2} should be written as h = sqrt(6) ‖x_t-x_{t-1}‖ / (n^β α^{i-1})^{1/2}, and the same ambiguity affects Algorithm 2's definition of h. The derivation in Appendix A confirms the intended exponent, but the notation should be clarified.
- [Lemma 3.2, Eq. (3.5)] The formula for δ_T has an unbalanced parenthesis: it should read δ_T ≤ δ[2T + log_α(2(L + 3α(2κ̄_G + κ̄_H)) + σ_1) - log_α(σ_1)].
- [Figure 2 and Section 4.2] The caption of Figure 2 refers to 'M-CRM-I-DF2' while the text consistently calls the method 'M-CRM-I-DF'; the caption should be made consistent.
Circularity Check
No load-bearing circularity; the finite-difference exponent mismatch in the abstract is an internal arithmetic error, not a circular derivation.
full rationale
Walking the derivation chain, the central complexity bound is not an input in disguise. Theorem 3.3 obtains the sum-of-cubes bound (3.7) by telescoping the nonmonotone sufficient-decrease condition (3.3); that condition is proved in Corollary 2.3 solely from assumption (A1), the error tolerances (3.1), and the cubic subproblem conditions (3.2). The constants Delta_0 and Delta_1 in (3.6) are explicit combinations of L, theta, kappa_G, kappa_H, sigma_1, alpha, and the initial gap F_j(x_1) - F_j^*, with no parameter fitted to the target epsilon-approximate Pareto-critical output. The derivative-free variant rests on Lemmas 3.9 and 3.14, which give kappa_G = L n^{(1-2beta)/2} and kappa_H = L n^{1-beta} from Taylor bounds; substituting into Delta_0 yields the O(n^{3(1-beta)/2} epsilon^{-3/2}) iteration bound and O(m n^{(7-3beta)/2} epsilon^{-3/2}) evaluation bound stated in Remark 3.15. The self-citations ([20], [21], [22], [24]) are related-work pointers, an experimental baseline, and a consistency comparison; the statement in Remark 3.13 that the scalar case recovers the complexity results of the CRM from [24] is a check against an independent derivation, not a load-bearing premise. No uniqueness theorem or ansatz is imported from prior work by the same authors. I therefore find no circular reduction. Separately, the abstract and Section 1 advertise O(n^{1-beta} epsilon^{-3/2}) iterations and O(m n^{3-beta} epsilon^{-3/2}) evaluations, which are not supported by Remark 3.15's proof; this is an arithmetic/expository inconsistency in the advertised exponents, not circularity.
Assumptions & free parameters
free parameters (5)
- beta =
0.5 in Algorithm 2 experiments
- alpha =
2 in experiments
- theta =
0.9 for M-CRM-I, 10^-8/||...||^2 for M-CRM-E
- sigma_1 =
2e-2 in experiments
- kappaG_bar and kappaH_bar =
derived from L and n for finite differences; user inputs in general
assumptions (6)
- domain assumption A1: Hessians of all objective components are globally L_j-Lipschitz continuous
- domain assumption A2: Each objective F_j is bounded below
- domain assumption A3: Each F_j is strongly convex on a relevant level set (for local rates)
- domain assumption A4: Exact gradients and Hessian error bounded by a multiple of min(||x_t - x_{t-1}||, zeta||g_t||) (for local rates)
- domain assumption At every iteration, an approximate KKT point of the subproblem can be computed satisfying (3.2)
- standard math Standard Taylor expansion bounds for functions with Lipschitz Hessians
Cite this review
Pith. "Pith review of A Cubic Regularization Method for Multiobjective Optimization." pith.science (2026). https://pith.science/paper/TTVNI27L
@misc{pith2026250608181,
author = {Pith},
title = {Pith review of: A Cubic Regularization Method for Multiobjective Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/TTVNI27L}},
note = {Machine review of arXiv:2506.08181}
}
abstract
This work introduces a new cubic regularization method for nonconvex unconstrained multiobjective optimization problems. At each iteration of the method, a model associated with the cubic regularization of each component of the objective function is minimized. This model allows approximations for the first- and second-order derivatives, which must satisfy suitable error conditions. One interesting feature of the proposed algorithm is that the regularization parameter of the model and the accuracy of the derivative approximations are jointly adjusted using a nonmonotone line search criterion. Implementations of the method, where derivative information is computed using finite difference strategies, are discussed. It is shown that, under the assumption that the Hessians of the objectives are globally Lipschitz continuous, the method requires at most $\mathcal{O}(C\epsilon^{-3/2})$ iterations to generate an $\epsilon$-approximate Pareto critical. In particular, if the first- and second-order derivative information is computed using finite differences based solely on function values, the method requires at most $\mathcal{O}(n^{1-\beta}\epsilon^{-3/2})$ iterations, corresponding to $\mathcal{O}\left(mn^{3-\beta}\varepsilon^{-\frac{3}{2}}\right)$ function evaluations, where \(n\) is the dimension of the domain of the objective function, $m$ is the number of objectives, and $\beta \in [0,1]$ is a constant associated with the stepsize used in the finite-difference approximation. We further discuss the global convergence and local convergence rate of the method. Specifically, under the local convexity assumption, we show that the method achieves superlinear convergence when the first derivative is computed exactly, and quadratic convergence when both first- and second-order derivatives are exact.
Reference graph
Works this paper leans on
-
[1]
R. Andreani, E. G. Birgin, J. M. Mart\' i nez, and M. L. Schuverdt , On A ugmented L agrangian methods with general lower-level constraints , SIAM J. Optim., 18 (2008), pp. 1286--1309
work page 2008
-
[2]
P. B. Assun c \ a o, O. P. Ferreira, and L. F. Prudente , Conditional gradient method for multiobjective optimization , Comput. Optim. Appl., 78 (2021), pp. 741--768, https://doi.org/10.1007/s10589-020-00260-5
-
[3]
S. Bellavia, G. Gurioli, and B. Morini , Adaptive cubic regularization methods with dynamic inexact Hessian information and applications to finite-sum minimization , IMA J. Numer. Anal., 41 (2020), pp. 764--799
work page 2020
-
[4]
S. Bellavia, G. Gurioli, B. Morini, and P. L. Toint , Quadratic and cubic regularisation methods with inexact function and random derivatives for finite-sum minimisation , in In: Proceedings of the 21st International Conference on Computational Science and Its Applications, 2021, pp. 258--267
work page 2021
-
[5]
Y. Bello-Cruz, L. R. Lucambio P\'erez, and J. G. Melo , Convergence of the projected gradient method for quasiconvex multiobjective optimization , Nonlinear Anal. Theory Methods Appl., 74 (2011), pp. 5268 -- 5273
work page 2011
-
[6]
Y. Bello-Cruz, J. G. Melo, and R. V. G. Serra , A proximal gradient splitting method for solving convex vector optimization problems , Optimization, 71 (2022), pp. 33--53
work page 2022
-
[7]
G. C. Bento, J. X. Cruz-Neto, and A. Soubeyran , A proximal point-type method for multicriteria optimization , Set-Valued Var Anal., 22 (2014), pp. 557--573
work page 2014
-
[8]
E. Birgin and J. Martinez , Practical Augmented Lagrangian Methods for Constrained Optimization , SIAM, Philadelphia, 2014
work page 2014
Show all 33 references
-
[9]
E. G. Birgin, J. L. Gardenghi, J. M. Mart \' nez, S. A. Santos, and P. L. Toint , Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models , Math. Program., 163 (2017), pp. 359--368
2017
-
[10]
Bonnel, A
H. Bonnel, A. N. Iusem, and B. F. Svaiter , Proximal methods in vector optimization , SIAM J. Optim., 15 (2005), pp. 953--970
2005
-
[11]
Calder \'o n, M
L. Calder \'o n, M. A. Diniz-Ehrhardt, and J. M. Mart \' nez , On high-order model regularization for multiobjective optimization , Optim. Methods Softw., 37 (2022), pp. 175--191
2022
-
[12]
Cartis, N
C. Cartis, N. I. M. Gould, and P. L. Toint , On the complexity of steepest descent, N ewton's and regularized newton's methods for nonconvex unconstrained optimization problems , SIAM J. Optim., 20 (2010), pp. 2833--2852
2010
-
[13]
Doikov and G
N. Doikov and G. N. Grapiglia , First and zeroth-order implementations of the regularized N ewton method with lazy approximated hessians , 2023, https://arxiv.org/abs/2309.02412
2023 arXiv
-
[14]
Fliege, L
J. Fliege, L. M. Gra \ n a Drummond, and B. F. Svaiter , N ewton's method for multiobjective optimization , SIAM J. Optim., 20 (2009), pp. 602--626
2009
-
[15]
Fliege and B
J. Fliege and B. F. Svaiter , Steepest descent methods for multicriteria optimization , Math. Method. Oper. Res., 51 (2000), pp. 479--494
2000
-
[16]
E. H. Fukuda and L. M. G. Drummond , Inexact projected gradient method for vector optimization , Comput. Optim. Appl., 54 (2013), pp. 473--493
2013
-
[17]
E. H. Fukuda and L. M. Gra \ n a Drummond , On the convergence of the projected gradient method for vector optimization , Optimization, 60 (2011), pp. 1009--1021
2011
-
[18]
E. H. Fukuda, H. Tanabe, and N. Yamashita , Proximal gradient methods for multiobjective optimization and their applications , Comput. Optim. Appl., 72 (2019), pp. 339--361
2019
-
[19]
E. H. Fukuda, H. Tanabe, and N. Yamashita , An accelerated proximal gradient method for multiobjective optimization , Comput. Optim. Appl., 86 (2023), pp. 421--455
2023
-
[20]
D. S. Gon c alves, M. L. N. Gon c alves, and J. G. Melo , An away-step frank-wolfe algorithm for constrained multiobjective optimization , Comput. Optim. Appl., 88 (2024), pp. 759--781
2024
-
[21]
M. L. N. Gon c alves , Subsampled cubic regularization method for finite-sum minimization , Optimization, 0 (2024), pp. 1--24
2024
-
[22]
M. L. N. Gon c alves, F. S. Lima, and L. F. Prudente , Globally convergent N ewton-type methods for multiobjective optimization , Comput. Optim. Appl., 83 (2022), pp. 403--434
2022
-
[23]
L. M. Gra \ n a Drummond and B. F. Svaiter , A steepest descent method for vector optimization , J. Comput. Appl. Math., 175 (2005), pp. 395 -- 414
2005
-
[24]
G. N. Grapiglia, M. L. N. Gon c alves, and G. N. Silva , A cubic regularization of N ewton's method with finite difference hessian approximations , Numer. Algorithms, 90 (2022), pp. 607--630
2022
-
[25]
Griewank , The modification of N ewton method for unconstrained optimization by bounding cubic terms
A. Griewank , The modification of N ewton method for unconstrained optimization by bounding cubic terms. , Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics. University of Cambridge, Cambridge (1981)
1981
-
[26]
Kohler and A
J. Kohler and A. Lucchi , Sub-sampled cubic regularization for non-convex optimization , in In Proceedings of the 34th International Conference on Machine Learning (ICML 2017), vol. 70, 2017, pp. 1895 -- 1904
2017
-
[27]
M. S. Louzeiro, G. N. Silva, J. Yuan, and D. Zhang , An adaptive cubic regularization quasi- N ewton method on R iemannian manifolds , 2024, https://arxiv.org/abs/2402.12464
2024 arXiv
-
[28]
L. R. Lucambio P\'erez and L. F. Prudente , Nonlinear conjugate gradient methods for vector optimization , SIAM J. Optim., 28 (2018), pp. 2690--2720
2018
-
[29]
Nesterov and B
Y. Nesterov and B. T. Polyak , Cubic regularization of N ewton method and its global performance , Math. Program., 184 (2006), pp. 177--205
2006
-
[30]
Nocedal and S
J. Nocedal and S. J. Wright , Numerical Optimization , Springer-Verlag, 2 ed., 2006
2006
-
[31]
Street, W
W. Street, W. Wolberg, and O. Mangasarian , Nuclear feature extraction for breast tumor diagnosis , in IS&T/SPIE 1993 International Symposium on Electronic Imaging: Science and Technology, vol. 1905, San Jose, CA, 1993
1993
-
[32]
Z. Wang, Y. Zhou, Y. Liang, and G. Lan , A note on inexact gradient and hessian conditions for cubic regularized N ewton's method , Oper. Res. Lett., 47 (2019), pp. 146--149
2019
-
[33]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTION or pop #1 'skip if FUNCTION new.block.check...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.