REVIEW 2 major objections 5 minor 1 cited by
Objective-Function Free Multi-Objective Optimization: Rate of Convergence and Performance of an Adagrad-like algorithm
T0 review · 2 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read The paper claims that multi-objective optimization can be done without ever evaluating objective functions, using an Adagrad-style adaptive step, and still converge to Pareto critical points at rate O(1/√k).
desk verdict A useful MO-Adagrad algorithm with a clean O(1/√k) rate proof, except the main theorem's proof has a threshold gap for the practical ς<1/2 range; worth refereeing but needs a fix. 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 load-bearing object is the common descent direction -g^s_k, where g^s_k is the unique minimal-Euclidean-norm vector in the convex hull of the gradients at x_k, obtained by solving the small convex subproblem Ω(x_k); if this vector is zero, x_k is Pareto critical. The step is s_k = -g^s_k / w_k with w_k = √(ς + Σ_{ℓ≤k}∥g^s_ℓ∥²), an Adagrad-norm accumulator that makes the stepsize adaptive. The key identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k) shows that the same quantity measures both criticality and the local decrease of the max objective Φ, which lets the convergence proof proceed without evaluating Φ or any f_j. A descent lemma for Φ then yields the telescoping sum whose careful accoun
What would settle it
Run MO-Adagrad on a smooth bi-objective problem, solving the subproblem exactly or with a certified tolerance, and plot min_{ℓ≤k}∥g^s_ℓ∥ against √(θ/(k+1)) with θ from Theorem 15; a persistent violation of that bound would refute the theorem. A cheaper check is to evaluate the identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k) at every iterate: if it fails by more than numerical noise, the descent argument in Lemma 10 is invalid.
Extended reading notes
Core claim
The central result is Theorem 15: if MO-Adagrad is run on a smooth multi-objective problem whose gradients are Lipschitz and for which max_j f_j is bounded below, then the average over the first k+1 iterates of the squared norm of the common descent direction g^s_ℓ is at most θ/(k+1), where θ depends only on the initial gap in the max objective, the Lipschitz constants, and the parameter ς. Consequently the minimum of ∥g^s_ℓ∥ over ℓ ≤ k is at most √(θ/(k+1)), an O(1/√(k+1)) global rate for the norm of the common descent direction. The proof rests on the identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k), which connects the minimal-norm convex combination of gradients to the steepest common descen
Load-bearing premise
The proof assumes the convex subproblem that produces the common descent direction is solved exactly at every iteration; if it is only solved approximately, the key identity ∥g^s_k∥² = -max_j ∇f_j(x_k)ᵀ(-g^s_k) can fail, and the paper gives no bound on how this error affects the O(1/√k) rate.
Editorial extensions
If this is right
- A multi-objective optimizer can drive all objectives toward a Pareto critical point using only gradient information; objective values are never needed, so the method applies when function evaluations are noisy, expensive, or unavailable.
- The stepsize is fully automatic: past gradient norms set the learning rate, so no line search and no knowledge of Lipschitz constants is required, matching the simplicity of single-objective Adagrad.
- The convergence guarantee is global and explicit: after k iterations the best common descent direction found has norm at most √(θ/(k+1)), so the worst-case iteration count to reach criticality ε is O(1/ε²).
- In the paper's experiments, MO-Adagrad solved more of the 124 bi-objective test instances than the line-search descent method (89% versus 77%), and under added noise its identified critical points stayed closer to the noise-free solutions.
- On the two small multi-task classification problems, MO-Adagrad reached comparable test accuracy roughly three times faster than the line-search method, because it never evaluates the losses.
Reading between the lines
- A natural testable extension is to allow approximate solutions of the subproblem and quantify how the approximation error enters θ; the current proof requires the exact minimal-norm convex combination, while the experiments use a finite-precision solver.
- The average-type rate implies that a uniformly random iterate among the first k is near-critical in the Cesàro sense; this could support cheap front exploration by multistart, an extension the paper flags but does not develop.
- The robustness to noise seen in the preliminary experiments suggests that a stochastic version using gradient estimates could inherit the same adaptive-stepsize structure; providing high-probability rates in that setting is a natural next step not covered in the paper.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes MO-Adagrad, an Adagrad-norm-type method for unconstrained multi-objective optimization. At each iteration it computes a common descent direction -g^s_k by solving the convex subproblem that minimizes the norm of a convex combination of gradients, then takes a step -g^s_k / w_k, where w_k accumulates past values of ||g^s_ℓ||. The method never evaluates objective functions and does not use line search or knowledge of Lipschitz constants. The main theoretical result, Theorem 15, gives an O(1/√(k+1)) bound on the average of ||g^s_ℓ||², hence on the criticality measure ω, under smoothness and boundedness of Φ = max_j f_j. Numerical experiments on CUTEst-based bi-objective instances, noisy variants, and two multi-task classification problems compare MO-Adagrad with a line-search steepest-descent method.
Significance. If the rate theorem is correct, the paper provides a clean function-free, line-search-free multi-objective method with essentially the same O(1/√k) worst-case criticality rate as standard first-order methods, extending objective-function-free Adagrad theory to the multi-objective setting. Strengths include self-contained proofs of the relation between the subproblem solution and the criticality measure (Lemmas 9–10), a concise descent analysis (Lemma 11), and broad numerical validation including a noisy setting. The main theorem, however, has a proof gap in the parameter regime actually used in the experiments; the gap is fixable and does not appear to threaten the rate itself. The analysis also assumes exact subproblem solutions while the implementation uses approximate ones, an issue that should be addressed.
major comments (2)
- [Theorem 15 / proof of Eqs. (15)–(16)] The proof assumes that S := Σ_{ℓ=0}^k ||g^s_ℓ||² ≥ max{ς, ς² e^{2Γ0/Lmax}} implies Γ0 ≤ (Lmax/2) log(2S/ς). This implication requires S ≥ (ς/2) e^{2Γ0/Lmax}. For ς < 1/2, ς² e^{2Γ0/Lmax} < (ς/2) e^{2Γ0/Lmax}, so (15) does not imply (16). Example: ς=0.01, Γ0=Lmax=1, S=0.02 satisfies (15) but (16) gives 1 ≤ 0.5 log(4) ≈ 0.693, which is false. Since Algorithm 1 is run with ς=10^{-2} in Section 4, this is the operative parameter regime, and the stated θ is not proven. The fix is to replace the threshold by max{ς, (ς/2)e^{2Γ0/Lmax}} and the second term of θ by (ς/2)e^{2Γ0/Lmax}; alternatively, one can apply Lemma 13 directly to (14) with b=Γ0, avoiding (16) entirely and yielding a smaller constant. The O(1/√k) rate is preserved, but Theorem 15 as written is not proven.
- [Algorithm 1, Step 2 and Theorem 15] The convergence analysis assumes that (Ω(x_k)) is solved exactly at every iteration: Lemma 10's identity ||g^s_k||² = -max_j ∇f_j(x_k)^T(-g^s_k) and Lemma 11's descent inequality use the exact minimizer g^s_k. In the experiments, (Ω) is solved with fmincon to finite tolerance, and no account is taken of the resulting inexactness. The numerical section therefore does not directly validate the theorem, and the algorithm as implemented is not covered by the rate guarantee. Please either analyze the inexact case (for example, with a subproblem tolerance criterion that preserves the descent bound) or clearly state and discuss the assumption and its practical implications.
minor comments (5)
- [Section 2, after Definition of weak efficiency] The sentence 'any efficient point for (MOP) is also efficient for (MOP)' should read 'also weakly efficient for (MOP)'.
- [Abstract] The phrase 'does not require neither knowledge of Lipschitz constants nor the use of line search procedures' contains a double negative; use 'requires neither ... nor' or 'does not require either ... or'.
- [Footnote 3] The definition of O uses a limit, but ratios of sequences need not have a limit; limsup is the standard notion and avoids excluding oscillating cases.
- [Theorem 15 proof, after Eq. (19)] The constant '64² Lmax⁴ / ς²' is easy to misread after OCR; please write it explicitly as '4096 Lmax⁴ / ς²' for clarity.
- [Section 4.2, Table 2] The text says both algorithms solve the 5 benchmark problems for all noise levels, but Table 2 includes CUTEst instances with failures; please clarify the distinction between the benchmark set and the CUTEst-based set.
Circularity Check
No significant circularity: the O(1/√k) bound is derived from the algorithm's own descent inequality and problem constants; the sole self-citation affects only a parameter choice.
full rationale
The central convergence claim, Theorem 15, is a self-contained descent-based complexity argument. It starts from the mean-value descent inequality in Lemma 11 (Eqs. (10)–(11)), uses the Adagrad-style weight recursion w_k^2 = w_{k-1}^2 + ||g^s_k||^2, and invokes Lemma 14 to bound the logarithmic sum. The constants in θ = max{ς, ς²e^{2Γ0/Lmax}, 2048Lmax^4/ς} depend only on the user parameter ς and problem data (Lmax and Γ0 = Φ(x0) − Φlow). Nothing in the proof is fitted to the quantity being bounded; the bound is on the algorithm's own criticality measure ω(xℓ) = ||g^s_ℓ||², which is legitimate because Pareto criticality is independently characterized by ω(x) = 0 (Lemma 4). The identity ||g^s_k||² = −max_j ∇f_j(x_k)ᵀ(−g^s_k) in Lemma 10 is proved via convex duality, not assumed as an input. The only self-citation, [33], appears in the numerical section for the choice ς = 10^{-2} — 'we set ς = 10^{-2} (see e.g. [21, 33])' — and is not load-bearing for the theoretical result. Concerns about exact subproblem solves versus the fmincon finite-tolerance implementation, and the threshold-gap concern in the proof of Theorem 15, are correctness/robustness issues rather than circularity: they do not reduce the claimed rate to the paper's own assumptions or fitted values.
Assumptions & free parameters
free parameters (1)
- ς (initial weight parameter) =
10^-2 in numerical experiments; any value in (0,1) in theory
assumptions (6)
- domain assumption Each f_j is continuously differentiable with L-Lipschitz gradients (for some Lj>0).
- domain assumption The MOP has at least one weakly efficient point, so Φ(x)=max_j f_j(x) is bounded below (Lemma 1).
- domain assumption At each iteration the subproblem (Ω(x_k)) is solved to exact optimality.
- standard math Lemma 13 (au ≤ b + c log u ⇒ u ≤ max{e^{b/c}, 4c^2/a^2}) holds.
- standard math Lemma 14: Σ c_j/(ξ+Σ_{ℓ≤j} c_ℓ) ≤ log(1 + (1/ξ) Σ c_j).
- standard math KKT conditions and Slater/strong duality hold for the convex subproblems (mgrad'(x)), (pgrad'(x)).
Cite this review
Pith. "Pith review of Objective-Function Free Multi-Objective Optimization: Rate of Convergence and Performance of an Adagrad-like algorithm." pith.science (2026). https://pith.science/paper/QIZC3PAQ
@misc{pith2026260205893,
author = {Pith},
title = {Pith review of: Objective-Function Free Multi-Objective Optimization: Rate of Convergence and Performance of an Adagrad-like algorithm},
year = {2026},
howpublished = {\url{https://pith.science/paper/QIZC3PAQ}},
note = {Machine review of arXiv:2602.05893}
}
abstract
We propose an Adagrad-like algorithm for multi-objective unconstrained optimization that relies on the computation of a common descent direction only. Unlike classical local algorithms for multi-objective optimization, our approach does not rely on the dominance property to accept new iterates, which allows for a flexible and function-free optimization framework. New points are obtained using an adaptive stepsize that does not require neither knowledge of Lipschitz constants nor the use of line search procedures. The rate of convergence is analyzed and is shown to be $\mathcal{O}(1 / \sqrt{ k+1})$ with respect to the norm of the common descent direction. The method is extensively validated on a broad class of unconstrained multi-objective problems and simple multi-task learning instances, and compared against a first-order line search algorithm. Additionally, we present a preliminary study of the behavior under noisy multi-objective settings, highlighting the robustness of the method.
Figures
Forward citations
Cited by 1 Pith paper
-
LemmaBench: A Live, Research-Level Benchmark to Evaluate LLM Capabilities in Mathematics
A live benchmark auto-extracts self-contained lemmas from recent arXiv papers and finds top LLMs solve only 10–15% at pass@1.
Reference graph
Works this paper leans on
-
[1]
Fast stochas- tic second-order adagrad for nonconvex bound-constrained op timization
Stefania Bellavia, Serge Gratton, Benedetta Morini, and Philippe L Toint. Fast stochas- tic second-order adagrad for nonconvex bound-constrained op timization. arXiv preprint arXiv:2505.06374, 2025
arXiv 2025
-
[2]
An objective- function-free algorithm for general smooth constrained optimiza tion
Stefania Bellavia, Serge Gratton, Benedetta Morini, and Philippe L Toint. An objective- function-free algorithm for general smooth constrained optimiza tion. In preparation, 2026
2026
-
[3]
A TE-SG: Alternate through the epochs stochastic gradient for multi-task neural ne tworks
Stefania Bellavia, Francesco Della Santa, and Alessandra Papini. A TE-SG: Alternate through the epochs stochastic gradient for multi-task neural ne tworks. arXiv preprint arXiv:2312.16340, 2025
arXiv 2025
-
[4]
Christopher M. Bishop. Pattern Recognition and Machine Learning . Springer, New York,
-
[5]
Regina Burachik, C. Yalcin. Kaya, and M. M. Rizvi. A new scalarizatio n technique and new algorithms to generate pareto fronts. SIAM Journal on Optimization , 27(2):1010–1034, 2017
2017
-
[6]
Variable metric method for unconstrained mul- tiobjective optimization problems
Jian Chen, Gao-Xi Li, and Xin-Min Yang. Variable metric method for unconstrained mul- tiobjective optimization problems. Journal of the Operations Research Society of China , 11:409–438, 2022
2022
-
[7]
On the convergence of steepest descent methods for multiobjective optimization
Guido Cocchi, Giampaolo Liuzzi, Stefano Lucidi, and Marco Sciandro ne. On the convergence of steepest descent methods for multiobjective optimization. Computational Optimization and Applications, 77:1–27, 2020
2020
-
[8]
Direct multisearch for multiobjective optimization
Ana Lu ´ ısa Cust´ odio, JF Aguilar Madeira, A Ismael F Vaz, and Lu ´ıs Nunes Vicente. Direct multisearch for multiobjective optimization. SIAM Journal on Optimization , 21(3):1109– 1140, 2011
2011
Show all 42 references
-
[9]
Benchmarking optimization software with performance profiles
Elizabeth D Dolan and Jorge J Mor´ e. Benchmarking optimization software with performance profiles. Mathematical programming, 91(2):201–213, 2002
2002
-
[10]
Adaptive subgradien t methods for online learning and stochastic optimization
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradien t methods for online learning and stochastic optimization. Journal of machine learning research , 12(7), 2011
2011
-
[11]
Proximity measures based o n KKT points for con- strained multi-objective optimization
Gabriele Eichfelder and Leo Warnow. Proximity measures based o n KKT points for con- strained multi-objective optimization. Journal of Global Optimization , 80:63–86, 2020
2020
-
[12]
Gra˜ na Drummond, and Benar Fux S Svaiter
J¨ org Fliege, L.M. Gra˜ na Drummond, and Benar Fux S Svaiter. N ewton’s method for mul- tiobjective optimization. SIAM Journal on Optimization , 20(2):602–626, 2009
2009
-
[13]
Steepest descent method s for multicriteria optimization
J¨ org Fliege and Benar Fux Svaiter. Steepest descent method s for multicriteria optimization. Mathematical Methods of Operations Research , 51(3):479–494, August 2000
2000
-
[14]
Complexity of gradient descent for mul- tiobjective optimization
J¨ org Fliege, Ismael Vaz, and Luis Nunes Vicente. Complexity of gradient descent for mul- tiobjective optimization. Optimization Methods and Software , 34(5):949–959, 2019
2019
-
[15]
An external penalty-type method for multicriteria
Ellen H Fukuda, LM Gra˜ na Drummond, and Fernanda MP Raupp. An external penalty-type method for multicriteria. TOP, 24:493–513, 2016
2016
-
[16]
A barrier-type method for multiobjective optimization
Ellen H Fukuda, LM Gra˜ na Drummond, and Fernanda MP Raupp. A barrier-type method for multiobjective optimization. Optimization, 69(11):2471–2487, 2020. 20
2020
-
[17]
Globally convergent Newton-type methods for multiobjective optimization
MLN Gon¸ calves, FS Lima, and LF Prudente. Globally convergent Newton-type methods for multiobjective optimization. Computational Optimization and Applications , 83(2):403–434, 2022
2022
-
[18]
Max L. N. Gon¸ calves, Geovani Nunes Grapiglia, and Jefferson G on¸ calves Melo. An adap- tive line-search-free multiobjective gradient method and its iterat ion-complexity analysis. Optimization Online https://optimization-online.org/? p=33379, 30/01/2026
2026
-
[19]
An adaptive trust-reg ion method without function evaluations
Geovani N Grapiglia and Gabriel FD Stella. An adaptive trust-reg ion method without function evaluations. Computational Optimization and Applications , 82(1):31–60, 2022
2022
-
[20]
Complexity of a class of first-order objective-function-free optimization algorithms
Serge Gratton, Sadok Jerad, and Philippe L Toint. Complexity of a class of first-order objective-function-free optimization algorithms. Optimization Methods and Software , pages 1–31, 2024
2024
-
[21]
Complexity of adagrad and other first- order methods for nonconvex optimization problems with bounds co nstraints
Serge Gratton, Sadok Jerad, and Philippe L Toint. Complexity of adagrad and other first- order methods for nonconvex optimization problems with bounds co nstraints. arXiv preprint arXiv:2406.15793, 2024
2024 arXiv
-
[22]
Multilevel objective-function-free optimization with an application to neural networks training
Serge Gratton, Alena Kopaniˇ c´ akov´ a, and Philippe L Toint. Multilevel objective-function-free optimization with an application to neural networks training. SIAM Journal on Optimiza- tion, 33(4):2772–2800, 2023
2023
-
[23]
S2MPJ and CUTEst optimizatio n problems for Matlab, Python and Julia
Serge Gratton and Philippe L Toint. S2MPJ and CUTEst optimizatio n problems for Matlab, Python and Julia. Optimization Methods and Software , pages 1–33, 2025
2025
-
[24]
Stochastic multi-objective op timization: a survey on non-scalarizing methods
Walter J Gutjahr and Alois Pichler. Stochastic multi-objective op timization: a survey on non-scalarizing methods. Annals of Operations Research , 236(2):475–499, 2016
2016
-
[25]
ASMOP: Additional sampling stochastic trust region method for multi-objective problems
Nataˇ sa Krklec Jerinki´ c and Luka Ruteˇ si´ c. ASMOP: Additional sampling stochastic trust region method for multi-objective problems
-
[26]
Adam: a method for stochastic optimization
Diederik P Kingma. Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014
2014 arXiv
-
[27]
Improved front stee pest descent for multi-objective optimization
Matteo Lapucci and Pierluigi Mansueto. Improved front stee pest descent for multi-objective optimization. Oper. Res. Lett. , 51(3):242–247, 2023
2023
-
[28]
A limited memory Quasi-N ewton approach for multi-objective optimization
Matteo Lapucci and Pierluigi Mansueto. A limited memory Quasi-N ewton approach for multi-objective optimization. Computational Optimization and Applications , 85(1):33–73, 2023
2023
-
[29]
Effective front-descent algorithms with convergence guarantees
Matteo Lapucci, Pierluigi Mansueto, and Davide Pucci. Effective front-descent algorithms with convergence guarantees. arXiv preprint arXiv:2405.08450 , 2024
2024 arXiv
-
[30]
The stochastic multi-gradient algorithm for multi- objective optimization and its application to supervised machine learn ing
Suyun Liu and Luis Nunes Vicente. The stochastic multi-gradient algorithm for multi- objective optimization and its application to supervised machine learn ing. Annals of Oper- ations Research, 339(3):1119–1148, 2024
2024
-
[31]
A derivat ive-free approach to constrained multiobjective nonsmooth optimization
Giampaolo Liuzzi, Stefano Lucidi, and Francesco Rinaldi. A derivat ive-free approach to constrained multiobjective nonsmooth optimization. SIAM Journal on Optimization , 26(4):2744–2774, 2016
2016
-
[32]
Adaptive bound op timization for online convex optimization
H Brendan McMahan and Matthew Streeter. Adaptive bound op timization for online convex optimization. arXiv preprint arXiv:1002.4908 , 2010. 21
2010 arXiv
-
[33]
Margherita Porcelli, Giovanni Seraghiti, and Philippe L. Toint. pru nAdag: an adaptive pruning-aware gradient method. Computational Optimization and Applications , 93(1):85– 119, 2026
2026
-
[34]
Decomposed descent methods in multiobjective optimization
Jana Thomann. Decomposed descent methods in multiobjective optimization. Master’s thesis, Technische Universit¨ at Ilmenau, 2015
2015
-
[35]
A trust region approach for multi-objective heterogeneous optimization
Jana Thomann. A trust region approach for multi-objective heterogeneous optimization. PhD thesis, Technische Universit¨ at Ilmenau, 2019. Technische Universit¨ at Ilmenau, Dissertation, 2019
2019
-
[36]
A trust-region algorithm for heterogeneous multi- objective optimization
Jana Thomann and Gabriele Eichfelder. A trust-region algorithm for heterogeneous multi- objective optimization. SIAM Journal on Optimization , 29(2):1017–1047, 2019
2019
-
[37]
Lecture 6.5-rmsprop, cou rsera: Neural networks for machine learning
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop, cou rsera: Neural networks for machine learning. University of Toronto, Technical Report , 6, 2012
2012
-
[38]
Some bounds for the logarithmic function
Flemming Topsøe. Some bounds for the logarithmic function. Inequality theory and appli- cations, 4:137, 2007
2007
-
[39]
Kely D. V. Villacorta, Paulo R. Oliveira, and Antoine Soubeyran. A t rust-region method for unconstrained multiobjective problems with applications in satisficing processes. Journal of Optimization Theory and Applications , 160(3):865–889, 2014
2014
-
[40]
Adagrad stepsizes : Sharp convergence over nonconvex landscapes
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes : Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research , 21(219):1–30, 2020
2020
-
[41]
ADADELTA: an adaptive learning rate method
Matthew D Zeiler. ADADELTA: an adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012. 22
2012 arXiv
-
[2006]
Chapter 4: Linear Models for Classification
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.