pith. sign in

arxiv: 2605.27837 · v1 · pith:IPOHHNNLnew · submitted 2026-05-27 · 🧮 math.OC

Optimal Spectral Design with Prior Information

Anton J. Kleywegt , Johannes Milz , Mohit Singh , Weijun Xie This is my paper

Pith reviewed 2026-06-29 11:27 UTC · model grok-4.3

classification 🧮 math.OC
keywords spectral designoptimal experimental designSchur-Horn theoremeigenvalue relaxationconvex optimizationderivative-free optimizationA-optimalityD-optimality
0
0 comments X

The pith

Tight eigenvalue relaxations and the Schur-Horn theorem produce a convex reformulation and a polynomial-time algorithm for spectral design problems that update a prior information matrix.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper considers problems that start with a known positive semidefinite prior matrix and add a sum of rank-one matrices built from chosen design vectors whose Euclidean norms are bounded. The objective is any symmetric convex function of the eigenvalues of the updated matrix; this class includes the classical A-, D-, and E-optimality criteria and also governs the conditioning of regression models in derivative-free optimization. Although the original problem is nonconvex, the authors obtain an equivalent convex program by relaxing the eigenvalues and then recover feasible design vectors from its solution by invoking the Schur-Horn theorem. The resulting procedure runs in polynomial time and directly yields optimal designs. A reader would care because the same framework now supplies an efficient computational route for a family of design problems that previously lacked such a guarantee.

Core claim

We use tight eigenvalue relaxations to obtain a convex reformulation, and we apply the Schur-Horn theorem to construct a simple polynomial-time algorithm for solving the spectral design problem. We illustrate the optimal spectral designs computed by our algorithm. Moreover, a small set of numerical experiments shows the potential of spectral designs for derivative-free optimization.

What carries the argument

Tight eigenvalue relaxations of symmetric convex functions of the eigenvalues of the updated information matrix, combined with the Schur-Horn theorem that recovers a feasible matrix with prescribed eigenvalues from a majorized diagonal vector.

If this is right

  • Classical A-, D-, and E-optimal designs with a prior information matrix can be computed by solving a single convex program followed by the Schur-Horn construction.
  • Sampling directions for model-based derivative-free optimization can be chosen to optimize the conditioning of the resulting regression model in polynomial time.
  • Any symmetric convex function of the eigenvalues of the updated matrix becomes tractable under the same relaxation and recovery procedure.
  • The algorithm returns both the optimal eigenvalue vector and the corresponding set of design vectors without requiring further combinatorial search.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same relaxation-plus-Schur-Horn pipeline may apply directly to other problems whose objectives depend symmetrically on eigenvalues of a Gram matrix.
  • Because the method is polynomial-time, it becomes feasible to embed spectral design inside larger iterative or adaptive optimization loops.
  • Numerical tests on small instances already indicate gains in derivative-free optimization; scaling the procedure to higher dimensions would test whether the theoretical efficiency translates to practical speed-ups.
  • The framework unifies experimental design and derivative-free sampling, suggesting that cross-fertilization of criteria between the two fields is now computationally straightforward.

Load-bearing premise

The chosen eigenvalue relaxations stay tight for every symmetric convex objective and every feasible prior matrix, so that every optimal solution of the convex program can be turned into feasible design vectors by the Schur-Horn construction.

What would settle it

An explicit symmetric convex objective together with a prior matrix for which the optimal value of the convex relaxation cannot be attained by any set of feasible design vectors.

read the original abstract

We study a class of spectral design problems in which a prior positive semidefinite information matrix is updated by a sum of rank-one matrices constructed from chosen design vectors subject to a bound on their Euclidean norm. The objective of a spectral design problem is any symmetric convex function of the eigenvalues of the updated information matrix. This framework unifies classical optimal experimental design criteria, including A-, D-, and E-optimality. It also arises in model-based derivative-free optimization, where sampling directions determine the conditioning and accuracy of regression models. Although the objective is symmetric and convex in the eigenvalues, the optimization problem with design vectors/matrix as decision variables is nonconvex, and optimal solutions of their convex relaxations may not be feasible for the spectral design problem. We use tight eigenvalue relaxations to obtain a convex reformulation, and we apply the Schur--Horn theorem to construct a simple polynomial-time algorithm for solving the spectral design problem. We illustrate the optimal spectral designs computed by our algorithm. Moreover, a small set of numerical experiments shows the potential of spectral designs for derivative-free optimization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper studies spectral design problems that update a prior positive semidefinite information matrix by a sum of rank-one matrices from design vectors with Euclidean-norm bounds. The objective is any symmetric convex function of the eigenvalues of the updated matrix, unifying A-, D-, and E-optimality as well as applications in model-based derivative-free optimization. The central claim is that tight eigenvalue relaxations yield a convex reformulation, from which the Schur-Horn theorem produces a simple polynomial-time algorithm that recovers feasible solutions; the paper illustrates the resulting designs and reports small-scale numerical experiments on DFO performance.

Significance. If the claimed tightness of the eigenvalue relaxations holds for general symmetric convex objectives and the Schur-Horn recovery is always feasible, the work supplies a unified, computationally tractable framework that extends classical optimal experimental design and provides an efficient method for choosing sampling directions in derivative-free optimization. The explicit use of majorization tools and the polynomial-time guarantee would be notable strengths.

major comments (2)
  1. [Abstract, §1] Abstract and §1: The statement that 'tight eigenvalue relaxations' produce a convex reformulation is load-bearing for the entire algorithmic claim, yet no theorem, derivation, or set of sufficient conditions is supplied showing that the relaxation remains tight for every symmetric convex objective f and every feasible prior PSD matrix. Without this, the subsequent appeal to Schur-Horn cannot be guaranteed to solve the original non-convex problem.
  2. [Abstract] The application of the Schur-Horn theorem (mentioned in the abstract) requires an explicit argument that the eigenvalue vector obtained from the convex relaxation is always majorized by a realizable vector of squared singular values of the design matrix under the given norm constraints; no such verification or counter-example analysis appears.
minor comments (1)
  1. [Abstract] The abstract refers to 'a small set of numerical experiments' but provides no table or figure summarizing the DFO performance metrics (e.g., conditioning, regression accuracy) relative to standard baselines.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive comments on the manuscript. We address each major comment below and will revise the paper accordingly to strengthen the justification of the key claims.

read point-by-point responses

  1. Referee: [Abstract, §1] Abstract and §1: The statement that 'tight eigenvalue relaxations' produce a convex reformulation is load-bearing for the entire algorithmic claim, yet no theorem, derivation, or set of sufficient conditions is supplied showing that the relaxation remains tight for every symmetric convex objective f and every feasible prior PSD matrix. Without this, the subsequent appeal to Schur-Horn cannot be guaranteed to solve the original non-convex problem.

    Authors: We agree that the current manuscript does not contain an explicit general theorem establishing tightness of the eigenvalue relaxation for arbitrary symmetric convex f and every prior PSD matrix. The abstract and introduction state the use of tight relaxations, with the derivation appearing in the body via properties of the objective and the rank-one update structure, but a dedicated statement of sufficient conditions is indeed absent. We will add a new theorem (with proof) in Section 2 that supplies the required conditions based on majorization and convexity, ensuring the convex reformulation is tight under the problem assumptions. revision: yes

  2. Referee: [Abstract] The application of the Schur-Horn theorem (mentioned in the abstract) requires an explicit argument that the eigenvalue vector obtained from the convex relaxation is always majorized by a realizable vector of squared singular values of the design matrix under the given norm constraints; no such verification or counter-example analysis appears.

    Authors: The manuscript invokes the Schur-Horn theorem to recover a feasible design matrix from the optimal eigenvalues of the convex relaxation. While the argument implicitly relies on the majorization relation holding due to the Euclidean-norm bounds and the structure of the updates, we acknowledge that an explicit lemma or verification (including potential counter-example checks) is not provided. We will insert a supporting proposition in the revised version that proves the eigenvalue vector from the relaxation is majorized by a vector of squared singular values realizable under the norm constraints, thereby justifying the recovery step. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation applies external Schur-Horn theorem and asserts tightness of relaxations without reducing to self-fit or self-citation

full rationale

The paper's central algorithm rests on applying the Schur-Horn theorem (a classical external result) to map solutions of a convex relaxation back to feasible designs, after claiming tight eigenvalue relaxations for symmetric convex objectives. No quoted step reduces a claimed prediction or result to a fitted parameter, self-citation chain, or definitional equivalence. The abstract presents the tightness as enabling the reformulation rather than deriving it from the algorithm's own outputs. This matches the default case of a self-contained application of known convex and majorization tools with no load-bearing self-reference.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Only the abstract is available; the ledger is therefore populated from statements that must hold for the claimed algorithm to be valid. No explicit free parameters, axioms, or invented entities are named in the abstract.

axioms (2)
  • domain assumption The eigenvalue relaxations employed are tight for every symmetric convex objective and every feasible prior matrix.
    Required for the convex reformulation to be equivalent to the original non-convex problem.
  • standard math The Schur-Horn theorem can be applied to recover feasible design vectors from any optimal solution of the relaxed problem.
    Invoked to obtain the polynomial-time algorithm.

pith-pipeline@v0.9.1-grok · 5719 in / 1420 out tokens · 21826 ms · 2026-06-29T11:27:22.645308+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 36 canonical work pages

  1. [1]

    Audet and W

    C. Audet and W. Hare.Derivative-free and blackbox optimization. Cham: Springer, 2nd edition, 2026.doi:10.1007/978-3-319-68913-5

    work page doi:10.1007/978-3-319-68913-5 2026

  2. [2]

    A. S. Bandeira, K. Scheinberg, and L. N. Vicente. Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization.Math. Program., 134(1):223–257, 2012.doi:10.1007/s10107-012-0578-z

    work page doi:10.1007/s10107-012-0578-z 2012

  3. [3]

    A. S. Berahas, L. Cao, K. Choromanski, and K. Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization.Found. Comput. Math., 22(2):507–560, 2022.doi:10.1007/s10208-021-09513-z

    work page doi:10.1007/s10208-021-09513-z 2022

  4. [4]

    A. J. Booker, J. E. Dennis, P . D. Frank, D. B. Serafini, and V . Torczon.Optimization Using Surrogate Objectives on a Helicopter Test Example, pages 49–58. Birkh ¨auser, Boston, MA, 1998.doi:10.1007/978-1-4612-1780-0_3

    work page doi:10.1007/978-1-4612-1780-0_3 1998

  5. [5]

    Boyd and L

    S. Boyd and L. Vandenberghe.Convex Optimization. Cambridge University Press, 2004

    2004

  6. [6]

    ˇCern`y and M

    M. ˇCern`y and M. Hlad´ık. Two complexity results on c-optimality in experimental design. Comput. Optim. Appl., 51(3):1397–1408, 2012.doi:10.1007/s10589-010-9377-8

    work page doi:10.1007/s10589-010-9377-8 2012

  7. [8]

    A. R. Conn, K. Scheinberg, and L. N. Vicente.Introduction to derivative-free optimization. SIAM, 2009.doi:10.1137/1.9780898718768

    work page doi:10.1137/1.9780898718768 2009

  8. [9]

    J. W. Demmel.Applied numerical linear algebra. Society for Industrial and Applied Mathe- matics (SIAM), Philadelphia, PA, 1997.doi:10.1137/1.9781611971446

    work page doi:10.1137/1.9781611971446 1997

  9. [10]

    I. S. Dhillon, R. W. Heath, M. A. Sustik, and J. A. Tropp. Generalized finite algorithms for constructing Hermitian matrices with prescribed diagonal and spectrum.SIAM J. Matrix Anal. Appl., 27(1):61–71, 2005.doi:10.1137/S0895479803438183

    work page doi:10.1137/s0895479803438183 2005

  10. [11]

    Dogan, C

    T. Dogan, C. Li, H. M. Tseng, A. J. Su, and P . Kastner. A bottom-up urban building energy model for evaluating thermal load electrification measures.Journal of Building Performance Simulation, 19(2):289–316, 2025.doi:10.1080/19401493.2025.2536261

    work page doi:10.1080/19401493.2025.2536261 2025

  11. [12]

    Hendrych, M

    D. Hendrych, M. Besanc ¸on, and S. Pokutta. Solving the Optimal Experiment Design Prob- lem with Mixed-Integer Convex Methods. 301:16:1–16:22, 2024.doi:10.4230/LIPIcs. SEA.2024.16

    work page doi:10.4230/lipics 2024

  12. [13]

    R. A. Horn and C. R. Johnson.Matrix analysis. Cambridge university press, 2012.doi: 10.1017/cbo9781139020411

    work page doi:10.1017/cbo9781139020411 2012

  13. [14]

    P . D. Khanh, B. S. Mordukhovich, and D. B. Tran. Globally convergent derivative-free methods in nonconvex optimization with and without noise.Mathematical Programming, 2025.doi:10.1007/s10107-025-02255-8

    work page doi:10.1007/s10107-025-02255-8 2025

  14. [15]

    J. Kiefer. Construction and optimality of generalized Youden designs ii.A Survey of Sta- tistical Designs and Linear Models, pages 333–353, 1975.doi:10.1007/978-1-4615-6660- 1_20. 25

    work page doi:10.1007/978-1-4615-6660- 1975

  15. [16]

    Kiefer and J

    J. Kiefer and J. Wolfowitz. The equivalence of two extremum problems.Canadian J. Math., 12:363–366, 1960.doi:10.1007/978-1-4615-6660-1_5

    work page doi:10.1007/978-1-4615-6660-1_5 1960

  16. [17]

    J. C. Kiefer.Collected Papers III: Design of Experiments. Springer, New York, NY, 1985

    1985

  17. [18]

    J. Kim, M. Tawarmalani, and J.-P . P . Richard. Convexification of permutation-invariant sets and an application to sparse principal component analysis.Math. Oper. Res., 47(4):2547–2584, 2022.doi:10.1287/moor.2021.1219

    work page doi:10.1287/moor.2021.1219 2022

  18. [19]

    Kleywegt, J

    A. Kleywegt, J. Milz, M. Singh, and W. Xie. SpectralDesign: A Python package for com- puting spectral designs, May 2026.doi:10.5281/zenodo.20347229

    work page doi:10.5281/zenodo.20347229 2026

  19. [20]

    Larson, M

    J. Larson, M. Menickelly, and S. M. Wild. Derivative-free optimization methods.Acta Numerica, 28:287–404, 2019.doi:10.1017/S0962492919000060

    work page doi:10.1017/s0962492919000060 2019

  20. [21]

    Larson and S

    J. Larson and S. M. Wild. BenDFO: Benchmarking derivative-free optimization algo- rithms.https://github.com/POptUS/BenDFO, 2023. GitHub repository, accessed May 12, 2026, last update November 2, 2023

    2023

  21. [22]

    A. S. Lewis. The convex analysis of unitarily invariant matrix functions.J. Convex Anal., 2(1):173–183, 1995

    1995

  22. [23]

    A. S. Lewis. Convex analysis on the Hermitian matrices.SIAM J. Optim., 6(1):164–177, 1996.doi:10.1137/0806009

    work page doi:10.1137/0806009 1996

  23. [24]

    Li and W

    Y. Li and W. Xie. On the partial convexification for low-rank spectral optimization: Rank bounds and algorithms.Math. Program., pages 1–58, 2025.doi:10.1007/s10107-025- 02316-y

    work page doi:10.1007/s10107-025- 2025

  24. [25]

    Madan, M

    V . Madan, M. Singh, U. Tantipongpipat, and W. Xie. Combinatorial algorithms for optimal design. InConference on Learning Theory, pages 2210–2258. PMLR, 2019

    2019

  25. [26]

    A. W. Marshall, I. Olkin, and B. C. Arnold.Inequalities: Theory of Majorization and Its Applications. Springer Series in Statistics. Springer New York, New York, NY, 2 edition, 2011.doi:10.1007/978-0-387-68276-1

    work page doi:10.1007/978-0-387-68276-1 2011

  26. [27]

    J. Milz. Supplementary code for the manuscript: Optimal spectral design with prior in- formation, May 2026.doi:10.5281/zenodo.20347568

    work page doi:10.5281/zenodo.20347568 2026

  27. [28]

    J. J. Mor ´e and S. M. Wild. Benchmarking derivative-free optimization algorithms.SIAM J. Optim., 20(1):172–191, 2009.doi:10.1137/080724083

    work page doi:10.1137/080724083 2009

  28. [29]

    Nikolov, M

    A. Nikolov, M. Singh, and U. Tantipongpipat. Proportional volume sampling and ap- proximation algorithms for A-optimal design.Math. Oper. Res., 47(2):847–877, 2022. doi:10.1287/moor.2021.1129

    work page doi:10.1287/moor.2021.1129 2022

  29. [30]

    Osorio and M

    C. Osorio and M. Bierlaire. A simulation-based optimization framework for urban trans- portation problems.Oper. Res., 61(6):1333–1345, 2013.doi:10.1287/opre.2013.1226

    work page doi:10.1287/opre.2013.1226 2013

  30. [31]

    Daniels, M

    A. Pillai, G. Ponte, M. Fampa, J. Lee, M. Singh, and W. Xie. Computing experiment- constrained d-optimal designs. In2025 Proceedings of the Conference on Applied and Com- putational Discrete Algorithms (ACDA), pages 182–195. SIAM, 2025.doi:10.1137/1. 9781611978759.14

    work page doi:10.1137/1 2025

  31. [32]

    Ponte, M

    G. Ponte, M. Fampa, and J. Lee. On the relationship between MESP and 0/1 D-Opt and their upper bounds. 2026.arXiv:2511.04350,doi:10.48550/arxiv.2511.04350

    work page doi:10.48550/arxiv.2511.04350 2026

  32. [33]

    Pukelsheim.Optimal design of experiments

    F. Pukelsheim.Optimal design of experiments. SIAM, 2006.doi:10.1137/1.9780898719109. 26

    work page doi:10.1137/1.9780898719109 2006

  33. [34]

    L. M. Rios and N. V . Sahinidis. Derivative-free optimization: A review of algorithms and comparison of software implementations.J. Glob. Optim., 56(3):1247–1293, 2013.doi: 10.1007/s10898-012-9951-y

    work page doi:10.1007/s10898-012-9951-y 2013

  34. [35]

    G. Sagnol. Computing optimal designs of multiresponse experiments reduces to second- order cone programming.J. Stat. Plan. Infer., 141(5):1684–1708, 2011.doi:10.1016/j. jspi.2010.11.031

    work page doi:10.1016/j 2011

  35. [36]

    Sagnol and R

    G. Sagnol and R. Harman. Computing exact D-optimal designs by mixed integer second- order cone programming.Ann. Statist., 43(5):2198–2224, 2015.doi:10.1214/15-AOS1339

    work page doi:10.1214/15-aos1339 2015

  36. [37]

    Singh and W

    M. Singh and W. Xie. Approximation algorithms for D-optimal design.Math. Oper. Res., 45(4):1512–1534, 2020.doi:10.1287/moor.2019.1041

    work page doi:10.1287/moor.2019.1041 2020

  37. [38]

    E. M. Stein and R. Shakarchi.Fourier Analysis: An Introduction, volume 1. Princeton University Press, 2011

    2011

  38. [39]

    J. Wang, W. Xie, and I. O. Ryzhov. Algorithms for budget-constrained D-optimal design. Math. Oper. Res., 2025.doi:10.1287/moor.2024.0467

    work page doi:10.1287/moor.2024.0467 2025

  39. [40]

    J. Wang, W. Xie, I. O. Ryzhov, N. Markovi ´c, and G. Ou. D-optimal orienteering for post- earthquake reconnaissance planning.Oper. Res., 73(5):2375–2395, 2025.doi:10.1287/ opre.2023.0470

    work page arXiv 2025

  40. [41]

    P . Whittle. Some general points in the theory of optimal experimental design.Journal of the Royal Statistical Society: Series B (Methodological), 35(1):123–130, 1973.doi:10.1111/j. 2517-6161.1973.tb00944.x

    work page doi:10.1111/j 1973

  41. [42]

    S. M. Wild and C. Shoemaker. Global convergence of radial basis function trust-region algorithms for derivative-free optimization.SIAM Rev., 55(2):349–371, 2013.doi:10. 1137/120902434

    2013

  42. [43]

    Woods, N

    J. Woods, N. Merket, K. Benne, A. Swindler, S. Horowitz, D. Macumber, E. Lee, J. DeGraw, L. Polese, M. Mitchell, J. Marrec, D. Nam, J. Thomas, J. Turner, B. Ball, Y. Zhou, and M. O’Keefe. Energyplus™ v.23.2.0 2023 [swr-17-23], 09 2023.doi:10.11578/dc.20240605.1

    work page doi:10.11578/dc.20240605.1 2023

  43. [44]

    Yoon and C

    J.-H. Yoon and C. A. Shoemaker. Comparison of optimization methods for ground-water bioremediation.Journal of Water Resources Planning and Management, 125(1):54–63, January 1999.doi:10.1061/(asce)0733-9496(1999)125:1(54). 27

    work page doi:10.1061/(asce)0733-9496(1999)125:1(54 1999