# Stability of subnanometer MoS wires under realistic environment

Dominike A. P. de Deus  Instituto Federal de Educação, Ciência e Tecnologia de
Goiás, Departamento de Áreas Acadêmicas, Campus Jataí, Orminda Vieira de
Freitas 775, 75804714 Jataí, Goiás, Brazil  Daniel F. Souza  Instituto Federal
do Amazonas, 69020-120, Manaus, AM, Brazil  Andréia L. da Rosa  Instituto de
Física, Universidade Federal de Goiás, Campus Samambaia, 74690-900, Goiânia,
Goiás, Brazil  Bremen Center for Computational Materials Science, University
of Bremen, Am Fallturm 1, 28359, Bremen, Germany  Renato B. Pontes  Instituto
de Física, Universidade Federal de Goiás, Campus Samambaia, 74690-900,
Goiânia, Goiás, Brazil  Th. Frauenheim  Bremen Center for Computational
Materials Science, University of Bremen, Am Fallturm 1, 28359 Bremen, Germany
Shenzhen Computational Science and Applied Research Institute, Shenzhen, China
Beijing Computational Science Research Center, Beijing, China
<EMAIL_ADDRESS>
###### Abstract

We carried out first-principles density functional theory calculations of
hydrogen and oxygen adsorption and diffusion on subnanometer MoS nanowires.
The nanowires are robust against adsorption of hydrogen. On the other hand,
interaction with oxygen shows that the nanowires can oxidize with a small
barrier. Our results open the path for understanding the behavior of MoS
nanowires under realistic environment.

###### keywords:

MoS nanowires, DFT, NEB

+55 62 35211122 xx

##  1 Introduction

The discovery of graphene has attracted the interest of the scientific
community in other low-dimensional materials, such as transition-metal
dichalcogenides (TMDCs), which exhibit novel physical and chemical properties
with promising applications in nanotechnology1, 2, 3. In particular, single-
layered MoS2 posses a sizebale electronic band gap of 1.8 eV, which may be
useful for applications in high-end electronics, spintronics, optoelectronics,
energy-harvesting, flexible electronics, and biomedicine 4, 5, 6.

Recently transition metal chalcogenide (TMC) subnanometer nanowires have been
fabricated by ion and electron beam techniques in MoS2 layers 7, 8. Contrary
to single-layered MoS2, MoS nanowires show metalic behavior 9. Such wires
under tensile strain undergo a phase transformation is observed in the MoS NWs
which results in tension-induced hardening in their tensile modulus 10.
Furthermore, topological states in one-dimensional MoS nanowires have been
proposed 11.

For several nanoscale applications, the interaction of nanostructures with the
environment is very important, since it provides information on their
stability against degradation. Usually two-dimensional MoS2 exhibits unique
surface effects but the interaction with hydrogen is limited by the amount of
active sites 12. Although hydrogen molecules diffuse on MoS2 monolayers with a
high energy barrier of 6.56 eV, their diffusion can be facilitated by applying
strain which then reduces the diffusion barrier to 0.57 eV 13. Reactivity can
further be improved via doping with transition metals 14. More recent results
claim that oxygen strongly interacts with defective MoS2 layers, enhancing
their photoluminescence properties due to dissociation of O2 on sulphur
vacancies 15.

Although the interaction of MoS2 monolayers with oxygen and hydrogen has been
largely explored, investigations of MoS nanowires under realistic environments
are still missing. In this paper we perfrom first-principles calculations
density functional theory calculations of hydrogen and oxygen adsorption and
difusion on subnanometer MoS nanowires. We show that the nanowires have
sizeable interaction with atomic hydrogen. However, dissociation of hydrogen
molecules is hindered by a high enegy barrier and unfavourable orientation of
orbitals. On the other hand, oxidation of MoS wires may take place with a
small diffusion barrier of oxygen atoms.

##  2 Computational details

The calculations are performed using density-functional theory (DFT) 16, 17,
as implemented in the Vienna ab initio simulation package (VASP) 18, The
electron-ion interactions are taken into account using the Projector Augmented
Wave (PAW) method. We employ the generalized gradient approximation (GGA-PBE)
19 to describe the interaction between valence electrons. The Kohn-Sham
orbitals are expanded in a plane wave basis set with an energy cutoff of 500
eV. The Brillouin Zone is sampled according to the Monkhorst-Pack method using
a (1$\times$1$\times$8) k-points mesh. In order to determine the diffusion and
reaction barriers we have performed CI-NEB 20, 21 calculations with seven
images to search the minimum-energy reaction paths and saddle points between
the initial state and final state configurations.

##  3 Results and discussion

###  3.1 Pristine nanowires

Mo and S atoms in pristine MoS nanowires are arranged by stacking of
triangular layers rotated 180o along the nanowire axial direction, with three
S atoms located at the vertices of the triangles and three Mo atoms located
between the S atoms, as seen in Fig. 1. The calculated equilibrium lattice
parameter along the axis wire is 4.39 Å. Contrary to single-layered MoS2,
pristine MoS nanowires show metallic behavior, as seen in Fig. 1(a). At
$\Gamma$ point the states with character $d_{\rm x^{2}}$ cross the Fermi
level. Localized states with $d_{\rm z^{2}}$ character lie around 0.25 eV
above the Fermi level, as seen in Fig. 1(b). In Fig. 1(c1) and (c2) (empty
states) and (c3) and (c4) (occupied states) we show the orbital projected
charge density in pristine wires. The empty states lie along the wire growth
direction. We discuss the importance of orbital orientation later on.

Figure 1:  Relaxed geometry of an isolated MoS nanowire with lattice parameter
$a_{\rm 0}$ along the wire growth direction. Electronic band structure of
pristine MoS nanowire. a) Orbital decomposed band structure, b) Orbital Mo-$d$
decomposed band structure and c1)-c4) band projected charge density. Blue are
empty states (0.4 eV above the Fermi level) and red are occupied states (0.4
eV below the Fermi level, which is set at zero).

In order to understand the strength between MoS wires and hydrogen/oxygen we
have calculated the adsorption energy according to:

$E_{\rm ads}=E_{\rm MoS-ad}-E_{\rm MoS}-\sum_{i}{N_{i}\mu_{i}},$ (1)

where EMoS-ad and EMoS are the total energies of the MoS supercell with and
without the adsorbate (hydrogen or oxygen). Ni and $\mu_{i}$ are the number
and chemical potencial of hydrogen and oxygen in gas phase.

Table 1: Adsorption energy Eads and diffusion/dissociation barrier $\Delta{\rm E}$ of hydrogen and oxygen on MoS nanowires. adsorbate |  $\%$ (ML) | Eads (eV) |  $\Delta{\rm E}$ (eV)
---|---|---|---
H on S | $\nicefrac{{1}}{{12}}$ | -0.55 |
H on Mo | $\nicefrac{{1}}{{12}}$ | -0.30 |
H on S | $\nicefrac{{1}}{{24}}$ | -0.80 |
H on Mo | $\nicefrac{{1}}{{24}}$ | -0.60 |
H2 | $\nicefrac{{1}}{{12}}$ | -0.006 |
H2 | $\nicefrac{{1}}{{24}}$ | -0.005 |
H | $\nicefrac{{1}}{{24}}$ |  | 0.35
H2 | $\nicefrac{{1}}{{12}}$ |  | 2.60
H2 | $\nicefrac{{1}}{{24}}$ |  | 1.10
O on S | $\nicefrac{{1}}{{12}}$ | 0.58 |
O on Mo | $\nicefrac{{1}}{{12}}$ | -0.22 |
O on S | $\nicefrac{{1}}{{24}}$ | -0.19 |
O on Mo | $\nicefrac{{1}}{{24}}$ | -0.50 |
O2 | $\nicefrac{{1}}{{12}}$ | 0.09 |
O2 | $\nicefrac{{1}}{{24}}$ | -0.25 |
O | $\nicefrac{{1}}{{24}}$ |  | 0.42
O2 | $\nicefrac{{1}}{{24}}$ |  | 0.20

We have considered adsorption of atomic and molecular hydrogen/oxygen.
Concentrations of $\nicefrac{{1}}{{12}}$ and $\nicefrac{{1}}{{24}}$ monolayers
(ML) which correspond to $(1\times 1\times 2)$ and $(1\times 1\times 1)$ unit
cells, respectively, have been used. The results for the adsorption energy are
shown in Table 1. For atomic hydrogen, coverages of $\nicefrac{{1}}{{12}}$ ML
shows that adsorption of atomic hydrogen atom has the lowest energy on a
sulphur atom. This energy is higher by 0.25 eV than adsorption on a Mo atom.
Smaller coverages of $\nicefrac{{1}}{{24}}$ ML have a similar behavior. For
hydrogen concentration of $\nicefrac{{1}}{{24}}$ ML, S-H bond length is
$d_{\rm S-H}$= 1.36 Å. The relaxed structure is shown in Fig. 2(a). Atomic
hydrogen prefers to be at ontop position, with the nanowire structure barely
affected by the hydrogen atom. Charge density difference calculated according
to $\Delta\rho=\rho_{\rm MoS-H}-\rho_{\rm MoS}-\rho_{\rm H}$ is shown in Fig.
2(b) with the nanowire structure barely affected by the hydrogen atom. Total
charge density with views along and perpendicular to the wire growth direction
is shown in Fig. 2(c) and (d).

Figure 2:  a) Relaxed structure of atomic hydrogen on MoS wires, b) charge
difference $\rho$, c) total charge density (cut parallel) and d) cut
perpendicular to the growth direction. Coverage of $\nicefrac{{1}}{{24}}$ ML.

To corroborate with this picture we show the band structure of atomic hydrogen
adsorbed on MoS nanowire for $\nicefrac{{1}}{{24}}$ ML coverage. a) orbital pr
ojected band structure, b) PDOS on Mo-d, c) PDOS on S-p and d) PDOS on H-s in
Fig.3.

In order to further understand this behavior we have calculated the
corresponding orbital projected band structure. The states comes from Mo
$d_{\rm z^{2}}$ (red) and $d_{\rm xz}$ (blue) and Mo $d_{\rm xy}$ (green)
orbitals. Fig. 4 reveals states with $d_{\rm z^{2}}$ character around the
Fermi level which are shifted downwards in energy compared to the ones in
pristine wires. The H-S bond has major contributions for the PDOS at -0.4 eV
in Figs. 4(b)-(d).

Figure 3:  Band structure of atomic hydrogen adsorbed on MoS nanowire for
$\nicefrac{{1}}{{24}}$ ML coverage. a) orbital projected band structure, b)
PDOS on Mo-d, c) PDOS on S-p and d) PDOS on H-s.

Orbital projected charge density of atomic hydrogen on MoS nanowire at
$\nicefrac{{1}}{{24}}$ ML coverage. Close to the Fermi level we identified
Mo-$d_{\rm xy}$ (a1) and (b1), Mo-$d_{\rm xz}$ (a2) and (b2) and Mo-$d_{\rm
z^{2}}$ (a3) and (b3). In c) we show the projected band structure
corresponding to these states.

Figure 4:  Orbital projected charge density of atomic hydrogen on MoS nanowire
for $\nicefrac{{1}}{{24}}$ ML coverage. a1) and b1) Mo-$d_{\rm xy}$, a2) and
b2) Mo-$d_{\rm xz}$, a3) and b3) Mo-$d_{\rm z^{2}}$ and c) projected band
structure corresponding to states shown in a) and b). The Fermi level is set
at zero.

The transition state along the considered path shown in Fig. 5 has the
hydrogen adsorbed at the ontop position of a Mo atom. The dissociation barrier
is 0.35 eV, as it can be seen in Fig.5 (j). By increasing the hydrogen
coverage to $\nicefrac{{1}}{{12}}$ ML the barrier is 2.60 eV (not shown). As a
matter of comparison, usual barriers for atomic hydrogen are usually a few meV
0.05-0.3 eV, on hcp(0001), fcc(111) and bcc(110) metal surfaces 22, 5, which
is consistent with our results at low coverages.

Table 1 shows that contrary to atomic hydrogen, the adsorption energy of
molecular hydrogen is only 6.00 meV. Furthermore, negligible difference is
found for hydrogen concentrations of $\nicefrac{{1}}{{24}}$ and
$\nicefrac{{1}}{{12}}$ ML. In order to further understand this behavior, we
have calculated the dissociation barrier of hydrogen along the path shown in
Fig. 5(a)-(i). Barrier of 1.10 eV.

Figure 5:  a)- i) Minimum-energy reaction path and j) diffusion barrier for
atomic hydrogen on MoS nanowire for $\nicefrac{{1}}{{24}}$ ML coverage.

Figure 6:  Dissociation barrier of a hydrogen molecule on MoS nanowire for
$\nicefrac{{1}}{{24}}$ ML coverage. Band structure and PDOS corresponding to
the most stable state shown a).

The band structure of the most stable state in Fig. 6(a) is shown in Fig.
6(b).

####  3.1.1 Oxygen adsorption

Figure 7:  Minimum-energy reaction path for atomic oxygen atom on MoS nanowire
with hydrogen adsorbed on Mo-S bridge for $\nicefrac{{1}}{{24}}$ ML coverage.

Atomic oxygen atom adsorbs at a bridge position as shown in Fig.7(a). Starting
from this configuration, Fig. 7(a)-(i) show the minimum energy path with a
diffusion barrier of 0.42 eV. The transition state corresponds to the oxygen
atom close to an ontop position. The band structure corresponding to Fig.
7(a)) is shown in Fig. 8(j).

Figure 8:  Band structure of atomic oxygen on MoS for the lowest energy
structure shown in Fig. 7.

At $\nicefrac{{1}}{{12}}$ ML oxygen concentration as shown in Fig. 8 a) side
view) and b) top view we have an endothermic reaction, as seen from Table 1.
Interestingly enough, by decreasing the oxygen concentration to
$\nicefrac{{1}}{{24}}$ ML, the reaction turns out to be exothermic. The band
structure is shown in Fig. 10(c). The more stable structure for an oxygen
molecule shows a small magnetic moment due to outwards relaxation of nearby Mo
atoms. The presence of the O2 molecule near a Mo atom introduces O-$p_{\rm z}$
states close to the $\Gamma$ and X points. Furthermore, the valence band
maximum (VBM) has mainly Mo-$d_{\rm z^{2}}$ character, whereas the conduction
band minimum (CBM) shows mixed O-$p_{\rm z}$, Mo-$d_{\rm xz}$ and Mo-$d_{\rm
yz}$ states, as seen in Fig. 10(d).

Figure 9:  Minimum-energy reaction path for molecular oxygen on MoS nanowire
at bridge position at $\nicefrac{{1}}{{12}}$ ML coverage. Figure 10:
Electronic band structure and PDOS of the most stable configuration shown in
Fig. 9.

##  4 Conclusion

In this paper we perfrom first-principles calculations density functional
theory calculations of hydrogen and oxygen adsorption and difusion on
subnanometer MoS nanowires. We show that the nanowires have sizeable
interaction with atomic hydrogen, but little with hydrogen molecules.
Furthemore, oxidation of MoS nanowires is feasible and occurs with a small
barrier.

We acknowledge the financial support from the Brazilian Agency CNPq under
grant number 313081/2017-4 and 305335/2020-0 and German Science Foundation
(DFG) under the program FOR1616. The calculations have been performed using
the computational facilities of Supercomputer Santos Dumont at LNCC, QM3
cluster at the Bremen Center for Computational Materials Science CENAPAD-SP at
Unicamp and LaMCAD at UFG.

## References

  * Chhowalla et al. 2013 Chhowalla, M.; Shin, H. S.; Eda, G.; Li, L.-J.; Loh, K. P.; Zhang, H. The chemistry of two-dimensional layered transition metal dichalcogenide nanosheets. _Nature Chem._ 2013, _5_ , 263–275
  * Wang et al. 2012 Wang, Q. H.; Kalantar-Zadeh, K.; Kis, A.; Coleman, J. N.; Strano, M. S. Electronics and optoelectronics of two-dimensional transition metal dichalcogenides. _Nature Nanotechn._ 2012, _7_ , 699–712
  * Choi et al. 2017 Choi, W.; Choudhary, N.; Han, G. H.; Park, J.; Akinwande, D.; Lee, Y. H. Recent development of two-dimensional transition metal dichalcogenides and their applications. _Mater. Today_ 2017, 116
  * Manzeli et al. 2017 Manzeli, S.; Ovchinnikov, D.; Pasquier, D.; Yazyev, O. V.; Kis, A. 2D transition metal dichalcogenides. _Nat. Rev. Mater._ 2017, _2_ , 17033
  * Koverga et al. 2021 Koverga, A. A.; Flórez, E.; J.-Orozco, C.; Rodriguez, J. A. Spot the difference: hydrogen adsorption and dissociation on unsupported platinum and platinum-coated transition metal carbides. _Phys. Chem. Chem. Phys._ 2021, 20255–20267
  * Chowdhury et al. 2020 Chowdhury, T.; Sadler, E. C.; Kempa, T. J. Progress and Prospects in Transition-Metal Dichalcogenide Research Beyond 2D. _Chem. Rev._ 2020, _120_ , 12563–12591
  * Lin et al. 2014 Lin, J. et al. Metallic Nanowires with Self-Adaptive Contacts to Semiconducting Transition-Metal Dichalcogenide Monolayers. _Nat. Nanotechnol._ 2014, _9_ , 436–442
  * Liu et al. 2013 Liu, X.; Xu, T.; Wu, X.; Zhang, Z.; Yu, J.; Qiu, H.; Hong, J.-H.; Jin, C.-H.; Li, J.-X.; Wang, X.-R.; Sun, L.-T.; Guo, W. Top–down fabrication of sub-nanometre semiconducting nanoribbons derived from molybdenum disulfide sheets. _Nature Comm._ 2013, _4_ , 1776
  * Souza et al. 2019 Souza, D. F.; Rosa, A. L.; Venezuela, P.; Padilha, J. E.; Fazzio, A.; Pontes, R. B. Structural evolution and the role of native defects in subnanometer MoS nanowires. _Phys. Rev. B_ 2019, _100_ , 235416
  * Ying et al. 2020 Ying, P.; Zhang, J.; Zhou, J.; Liang, Q.; Zhong, Z. Mechanical behaviors of MoS nanowires under tension from molecular dynamics simulations. _Comp. Mat. Sci._ 2020, _179_ , 109691
  * Jin and Liu 2020 Jin, K.-H.; Liu, F. 1D Topological Phase in Transition-Metal Monochalcogenides Nanowires. _Nanoscale_ 2020, _12_ , 14661–14667
  * Niu et al. 2021 Niu, S.; Cai, J.; Wang, G. Two-dimensional MOS2 for hydrogen evolution reaction catalysis: The electronic structure regulation. _Nano Research_ 2021, _14_ , 1985–2002
  * Koh et al. 2012 Koh, E. W. K.; Chiu, C. H.; Lim, Y. K.; Zhang, Y.-W.; Pan, H. Hydrogen adsorption on and diffusion through MoS2 monolayer: First-principles study. _International Journal of Hydrogen Energy_ 2012, _37_ , 14323
  * B.Zhao et al. 2017 B.Zhao,; L.L.Liu,; D.Cheng, G.; T.Li,; N.Qi,; Chen, Z. Q.; Tang, Z. Interaction of O2 with monolayer MoS2: Effect of doping and hydrogenation. _Materials and Design_ 2017, _113_ , 1–8
  * Wang and Paulus 2021 Wang, K.; Paulus, B. Toward a Comprehensive Understanding of Oxygen on MoS2: From Reaction to Optical Properties. _J. Phys. Chem. C_ 2021, _125_ , 19544–19550
  * Hohenberg and Kohn 1964 Hohenberg, P.; Kohn, W. Inhomogeneous Electron Gas. _Phys. Rev._ 1964, _136_ , B864–B871
  * Kohn and Sham 1965 Kohn, W.; Sham, L. J. Self-Consistent Equations Including Exchange and Correlation Effects. _Phys. Rev._ 1965, _140_ , A1133–A1138
  * Kresse and Joubert 1999 Kresse, G.; Joubert, D. From ultrasoft pseudopotentials to the projector augmented-wave meth od. _Phys. Rev. B_ 1999, _59_ , 1758–1775
  * Perdew et al. 1996 Perdew, J. P.; Burke, K.; Ernzerhof, M. Generalized Gradient Approximation Made Simple. _Phys. Rev. Lett._ 1996, _77_ , 3865–3868
  * Henkelman and Jónsson 2000 Henkelman, G.; Jónsson, H. Improved tangent estimate in the nudged elastic band method for finding minimum energy paths and saddle points. _J. Chem. Phys._ 2000, _113_ , 9978–9985
  * Henkelman and Jónsson 2000 Henkelman, G.; Jónsson, H. A climbing image nudged elastic band method for finding saddle points and minimum energy paths. _J. Chem. Phys._ 2000, _113_ , 9901–9904
  * Kristinsdóttir and Skúlason 2012 Kristinsdóttir, L.; Skúlason, E. A systematic DFT study of hydrogen diffusion on transition metal surfaces. _Surf. Sci._ 2012, _606_ , 1400–1404


# Gradient descent globally solves average-case non-resonant physical design
problems

Rahul Trivedi<EMAIL_ADDRESS>Max-Planck-Institut für Quantenoptik,
Hans-Kopfermann-Str. 1, 85748 Garching, Germany.

###### Abstract

Optimization problems occurring in a wide variety of physical design problems,
including but not limited to optical engineering, quantum control, structural
engineering, involve minimization of a simple cost function of the state of
the system (e.g. the optical fields, the quantum state) while being
constrained by the physics of the system. The physics constraints often makes
such problems non-convex and thus only locally solvable, leaving open the
question of finding the globally optimal design. In this paper, I consider
design problems whose physics is described by bi-affine equality constraints,
and show that under assumptions on the stability of these constraints and the
physical system being non-resonant, gradient descent globally solves a typical
physical design problem. The key technical contributions of this paper are (i)
outline a criteria that ensure the convergence of gradient descent to an
approximate global optima in the limit of large problem sizes, and (ii) use
random matrix theory to outline ensembles of physically motivated problems
which, on an average, satisfy this convergence criteria.

##  I Introduction

Optimization-based design methodologies have been successfully adapted and
applied to solving a wide variety of physical design problems, including but
not limited to photonics design Molesky  _et al._ (2018); Su  _et al._
(2018a); Piggott  _et al._ (2019); Su  _et al._ (2018b); Piggott  _et al._
(2017); Sapra  _et al._ (2019), device-level designs for quantum technologies
Roslund and Rabitz (2009); Lucarelli (2018); Werschnik and Gross (2007); Li
_et al._ (2017); Zhu and Rabitz (1998), and structural engineering Rozvany
(2009); Wang  _et al._ (2003, 2003); Hassani and Hinton (2012). The physics of
these system are mathematically captured by bi-affine equality constraints,
i.e. constraints of the form $h(x,\theta)=0$ where $h$ is affine in $x$ for
fixed $\theta$ and affine in $\theta$ for fixed $x$, relating the system state
($x$) to the design parameters ($\theta$). The design problem is captured by a
cost function of the system state $x$, which is to be minimized with respect
to the parameters $\theta$ while enforcing these constraints. In practice, the
bi-affine equality constraint allow for an efficient evaluation of the
gradient of the cost function with respect to the design parameters Giles and
Pierce (2000); Bakr and Nikolova (2004); Park  _et al._ (1996); Dong  _et al._
(2004); Soliman  _et al._ (2004), and thus local optimization algorithms such
as gradient descent Ruder (2016) of quasi-Newton methods Gill and Murray
(1972) can be used to solve them locally. However, the bi-affine constraints
also makes the optimization problem non-convex, and hence hard to solve
globally. While the locally optimized result suffices for many applications,
it leaves open the question of how much more improvement in the device
performance can be gained by searching for the global optima.

One prominent approach to answering this question has been to provide lower
bounds on the cost function that captures the device performance and is being
optimized — while the optimization problem itself is non-convex and hard to
solve globally, such bounds can often be computed efficiently by solving a
convex problem. Several approaches to setting up this convex problem and
calculating these lower bounds using physically motivated convex relaxations
Miller  _et al._ (2016); Shim  _et al._ (2019); Venkataram  _et al._ (2020);
Molesky  _et al._ (2020, 2019) or by an application of Lagrange duality
Angeris  _et al._ (2019); Kuang  _et al._ (2020); Kuang and Miller (2020);
Zhang  _et al._ (2021) have been recently pursued. In many problems of
interest, these lower bounds, computed numerically, are reasonably close to
the locally optimized results and thus indicate that the design is near
globally-optimal Zhang and Miller (2020); Kern  _et al._ (2020). However,
there is no general theoretical guarantee for the lower bounds obtained by
these methods to be tight (i.e. close to the global optima), and consequently
they do not always allow for a quantitative assessment of the optimality of
the locally optimized design.

In this paper, I pursue a different approach for assessing the optimality of
local optimization algorithms — I theoretically analyze the convergence of the
gradient descent algorithm when applied to a physical design problem. The
results indicate that gradient descent efficiently solves a typical physical
design problem i.e. it comes within a specified accuracy of the global optima
in a number of steps that only scale polynomially with the problem size. There
are two parts to the main result — first, I provide a set of conditions on the
physical design problem which guarantee this convergence result. Next, I
analyze physically motivated distributions of bi-affine design problems and
show that a member of this ensemble, on average, satisfies these conditions
and thus is expected to be efficiently solvable by gradient descent. While
this work is, to the best of my knowledge, the first rigorous study of
convergence of gradient descent for physical design problems, it shares
techniques with similar analysis of local optimization algorithms when applied
to non-convex problems arising in training of deep neural networks Allen-Zhu
_et al._ (2019a, b, a), neural-tangent kernels Jacot  _et al._ (2021) and
dynamical models of time-series data Hardt  _et al._ (2018).

##  II Notation

For $v\in\mathbb{R}^{n}$, I will denote by $\|{v}\|_{p}$ its $l^{p}$ norm, and
for simplicity use $\|{v}\|$ for its $l^{2}$ norm. For a matrix
$M\in\mathbb{R}^{n\times m}$, I will denote by $\|{M}\|_{p}$ the induced
$l^{p}$ norm i.e.
$\|{M}\|_{p}=\sup_{v\in\mathbb{R}^{m}\setminus\\{0\\}}\|{Mv}\|_{p}/\|{v}\|_{p}$.
I will denote by $I_{n}$ the $n\times n$ identity matrix. I will denote by
$\|{M}\|_{\textnormal{max}}$ the maximum magnitude element of $M$ i.e.
$\|{M}\|_{\textnormal{max}}=\max_{i\in[n],j\in[m]}|M_{i,j}|$. I will often
write the vector, $0^{n}$ (i.e. vector with all elements 0), simply as 0, and
the dimensionality of the vector will be evident from the context.

For two vectors $u,v\in\mathbb{R}^{n}$, $u\odot v\in\mathbb{R}^{n}$ is their
elementwise product defined by $(u\odot v)_{i}:=u_{i}v_{i}\ \forall\ i\in[n]$.
Given a function $f:\text{dom}(f)\subset\mathbb{R}\to\mathbb{R}$ and a vector
$v\in\text{dom}(f)^{n}$, $f(v)$ will denote a vector obtained on applying $f$
entry-wise to $f$.

I will use the computer science notation for asymptotic behaviour of
sequences. Given a sequence $\\{a_{n}\in\mathbb{R}^{+}:n\in\mathbb{N}\\}$.
$a_{n}\leq O(f(n))$ for some $f:\mathbb{N}\to\mathbb{R}^{+}$ if $\exists c>0$
such that $a_{n}\leq cf(n)$ as $n\to\infty$. $a_{n}<o(f(n))$ for some
$f:\mathbb{N}\to\mathbb{R}^{+}$ if $\forall c>0$, $a_{n}<cf(n)$ as
$n\to\infty$. In particular, $n^{o(1)}$ will be used to denote a function
whose growth is slower than $n^{\alpha}$ for any $\alpha>0$.
$a_{n}\geq\Omega(f(n))$ for some $f:\mathbb{N}\to\mathbb{R}^{+}$ if $\exists
c>0$ such that $a_{n}\geq cf(n)$ as $n\to\infty$. $a_{n}=\Theta(f(n))$ if
$a_{n}\leq O(f(n))$ and $a_{n}\geq\Omega(f(n))$.

##  III Summary of results

I first introduce a definition of a physical design problem, along with some
terminology that I use throughout this paper. I introduce an abstract
definition of a _physical system_ , and a _physical design problem_.

###### Definition 1

A _physical system_ with state size $n$ and parameter size $m$ is a map
$\varphi:\textnormal{dom}(\varphi)\to\mathbb{R}^{n}$ specified by a tuple
$(A,B,b)$ where $A\in\mathbb{R}^{n\times n}$, $B\in\mathbb{R}^{n\times m}$,
$b\in\mathbb{R}^{n}$ and

$\textnormal{dom}(\varphi)=\\{\theta\in\mathbb{R}^{m}|A+\textnormal{diag}(B\theta)\textnormal{
is invertible}\\},$

and $\forall\theta\in\mathbb{R}^{m}$,

$\varphi(\theta)=(A+\textnormal{diag}(B\theta))^{-1}b.$

$A$ is the physics matrix, $B$ is the selection matrix and $b$ is the source
vector corresponding to the physical system.

###### Definition 2

Given a physical system $\varphi\equiv(A,B,b)$ of state size $n$, and a vector
$c\in\mathbb{R}^{n}$, the _adjoint system_ is a map
$\textnormal{ad}[\varphi]:\textnormal{dom}(\varphi)\times\mathbb{R}^{n}\to\mathbb{R}^{n}$
such that $\forall\theta\in\mathbb{R}^{m}$,

$\textnormal{ad}[\varphi](\theta,c)=(A+\textnormal{diag}(B\theta))^{-\textnormal{T}}c.$

###### Definition 3

A physical design problem of state size $n$ and parameter size $m$ is
specified by a tuple $(f,c,\varphi)$ where $f:\mathbb{R}\to\mathbb{R}$ is the
cost function, $c\in\mathbb{R}^{n}$ is the overlap vector, $\varphi$ is a
physical system of state size $n$ and parameter size $m$ and it corresponds to
solving the following constrained optimization problem:

$\displaystyle\underset{\begin{subarray}{c}\theta\in\textnormal{dom}(\varphi)\end{subarray}}{\textnormal{minimize}}$
$\displaystyle f(c^{\textnormal{T}}\varphi(\theta)),$

To solve this problem using local optimization algorithm, it is essential to
be able to efficiently compute the gradient of the cost function. It is well
known that this can be done using the the maps corresponding to the physical
system and the adjoint system Giles and Pierce (2000); Bakr and Nikolova
(2004); Park  _et al._ (1996); Dong  _et al._ (2004); Soliman  _et al._
(2004). This is made explicit in the following lemma, which can be
straightforwardly proved using the chain rule.

###### Lemma 1

For a physical design problem $(f,c,\varphi)$, then for the map
$f(c^{\textnormal{T}}\varphi(\cdot)):\textnormal{dom}(\varphi)\to\mathbb{R}$,
the gradient at $\theta\in\textnormal{dom}(\varphi)$ is given by

$\nabla_{\theta}f(c^{\textnormal{T}}\varphi(\theta))=-f^{\prime}(c^{\textnormal{T}}\varphi(\theta))B_{\varphi}^{\textnormal{T}}(\varphi(\theta)\odot\textnormal{ad}[\varphi](\theta,c)).$

Algorithm 1 Gradient descent for solving a physical design problem

0: A physical design problem $(f,c,\varphi)$, an initial set of design
parameters $\theta_{0}\in\mathbb{R}^{m}$, a gradient descent step size
$\eta\in(0,\infty)$ and number of gradient descent steps $T\in\mathbb{N}$.

0: The optimized design parameters $\theta^{*}\in\mathbb{R}^{m}$.
Initialisation :

If $\theta_{0}\notin\textnormal{dom}(\varphi)$, then declare FAIL, else set
$x_{0}=\varphi(\theta_{0})=(A_{\varphi}+\textnormal{diag}(B_{\varphi}\theta))^{-1}b_{\varphi}$.
LOOP Process

for $t=1$ to $T-1$ do

Compute the adjoint state
$a_{t-1}=\varphi^{\textnormal{adj}}_{c}(\theta_{t-1})$.

Compute the gradient
$g_{t-1}=-f^{\prime}(c^{\textnormal{T}}x_{t-1})\big{(}\varphi^{\textnormal{adj}}_{c}(\theta_{t-1})\odot\varphi(\theta_{t-1})\big{)}$

Perform the gradient descent step $\theta_{t}:=\theta_{t-1}-\eta g_{t-1}$.

if ($\theta_{t}\notin\textnormal{dom}(\varphi)$) then

Declare FAIL.

end if

end for

return $\theta_{T}$

Throughout this paper, I will be interested in performing an analysis of
gradient descent (explicitly described in algorithm 1) not for one specific
problem instance, but for problem instance with large state sizes. More
formally, I will consider a family of physical design problems with larger and
larger state sizes and assess how gradient descent performs on a specific
instance of this family.

###### Definition 4

A _family of physical design problems_ is a sequence
$\\{(f,c_{n},\varphi_{n}):n\in\mathbb{N}\\}$ of physical design problems,
where $(f,c_{n},\varphi_{n})$ is a physical design problem of state size $n$
and the cost function $f:\mathbb{R}\to\mathbb{R}$ is independent of $n$.

I next introduce a set of conditions on a given family of physical design
problems, which will be central to the analysis of the convergence of gradient
descent. These conditions are expressed in terms of the scalings of the
spectrum of the physics matrix with the state size of the physical system, as
well as on the norms of the source and overlap vectors. The definition I
provide below makes concrete the physical expectation that the norm of the
physics matrix of systems encountered in practice only grows polynomially with
the state size of the system, and typically the source and overlap vectors
only affect a constant number of state variables and hence have norms upper
bounded by a constant. I also assume a condition on the initial gradient of
the cost function — since in practice the initial design is picked randomly
and is thus not locally optimal, we assume that the initial gradient of the
cost function is large (i.e. lower bounded by a function that grows
polynomially with the state size).

###### Definition 5

A family of physical design problems
$\\{(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n})):n\in\mathbb{N}\\}$ is said
to satisfy the $(\alpha,\gamma)$-asymptotic convergence conditions if

  * (a)

$f$ is $L-$Lipschitz smooth111A differentiable function
$f:\mathbb{R}^{D}\to\mathbb{R}$ is $L-$Lipschitz smooth if $\|{\nabla
f(x)-\nabla f(y)}\|\leq L\|{x-y}\|$, $\mu-$strongly convex 222A function
$f:\mathbb{R}^{D}\to\mathbb{R}$ is $\mu-$strongly convex if $f(y)\geq
f(x)+\nabla f(x)^{\textnormal{T}}(y-x)+\sigma\|{x-y}\|^{2}/2$. and is bounded
from below i.e. $f^{*}=\min_{x\in\mathbb{R}}f(x)>-\infty$.

  * (b)

$\|{A_{n}^{-1}}\|_{2}\leq O(n^{\gamma})$,

  * (c)

$\|{B_{n}}\|_{\infty},\|{B_{n}}\|_{1},\|{B_{n}}\|_{2}\leq O(1)$,

  * (d)

$\|{b_{n}}\|_{\infty},\|{b_{n}}\|_{1}\leq O(1)$,

  * (e)

$\|{c_{n}}\|_{\infty},\|{c_{n}}\|_{1}\leq O(1)$,

  * (f)

$\|{B_{n}^{\textnormal{T}}(A_{n}^{-1}b_{n}\odot
A_{n}^{-\textnormal{T}}c_{n})}\|_{2}^{2}\geq\Omega(n^{\alpha+\gamma})$ and

  * (g)

$|c_{n}^{\textnormal{T}}A_{n}^{-1}b_{n}|\leq O(1)$.

Typical physical design problems are expected to be non-resonant i.e. the
state vector is expected to not become very large during the optimization
trajectory. It is empirically observed in many settings that local
optimization algorithms perform very well when applied to such non-resonant
design problems, while resonant design problems are usually much harder to
solve. This consideration has to be accounted for in the analysis of gradient
descent — the next definition that I provide makes the intuition behind a non-
resonant design mathematically precise, and will be another important
ingredient in the analysis of the optimality of gradient descent.

######  Definition 6 (Non-resonant design parameters)

Given a family of physical design problems
$\mathcal{F}=\\{(f,c_{n},\varphi_{n}):n\in\mathbb{N}\\}$, a sequence of design
parameters $\\{\theta_{n}\in\textnormal{dom}(\varphi_{n}):n\in\mathbb{N}\\}$
is said to be non-resonant with respect to the family $\mathcal{F}$ if
$\|{\varphi_{n}(\theta_{n})}\|_{\infty}\leq O(n^{o(1)})$ and
$\|{\textnormal{adj}[\varphi_{n}](\theta_{n},c_{n})}\|_{\infty}\leq
O(n^{o(1)})$.

I now present the first result of this paper — a family of physical design
problems is efficiently solvable by gradient descent, under the assumption
that the design parameters generated during the algorithm are non-resonant, if
it satisfies the asymptotic convergence conditions.

###### Theorem 1

Let $\mathcal{F}:=\\{(f,c_{n},\varphi_{n}):n\in\mathbb{N}\\}$ be a family of
physical design problems that satisfies the $\alpha,\gamma-$asymptotic
convergence conditions (definition 5) with $\alpha>1/4,\gamma<3\alpha$, and
for $n\in\mathbb{N}$, let
$\Theta_{n}=\\{\theta_{n}^{1},\theta_{n}^{2}\dots\theta_{n}^{T_{n}}\\}$ be the
design parameters generated by gradient descent (algorithm 1) under the
assumption that it does not fail when applied on $(f,c_{n},\varphi_{n})$ with
step size $\eta_{n}\leq O(n^{-3\gamma+\alpha-1})$ for $T_{n}$ steps starting
with initial design of $\theta_{n}^{0}=0$. If all the sequences
$\\{\theta_{n}\in\Theta_{n}:n\in\mathbb{N}\\}$ are non-resonant with respect
to $\mathcal{F}$, then
$f(c_{n}^{\textnormal{T}}\varphi_{n}(\theta_{n}^{T_{n}}))-f^{*}\leq\varepsilon$
for $T_{n}$ chosen such that
$T_{n}=\Theta(n^{1-2(\alpha-\gamma)}\log(\varepsilon^{-1}))$.

In the next two propositions, I provide families of design problems which are
constructed by choosing the physics matrices randomly from a distribution. By
analyzing an average-case problem picked from these distributions, I show that
it satisfies the asymptotic convergence conditions. The first family of
problem is one in which the inverse of the physics matrix is a matrix from the
random gaussian ensemble, and this example is inspired from wave design
problems Molesky  _et al._ (2018); Su  _et al._ (2018a); Piggott  _et al._
(2019); Su  _et al._ (2018b), where often the initial design is a random
scattering media whose properties are known to be captured by random matrices
Kogan and Kaveh (1995).

###### Problem 1

Given a cost function $f:\mathbb{R}\to\mathbb{R}$ being an $L-$Lipschitz
smooth and $\mu-$strongly convex function that is bounded from below, define a
family of physical design problems
$\mathcal{F}:=\\{(f,c_{n},\varphi_{n}\equiv(A_{n}:=G_{n}^{-1},B_{n}:=I_{n},b_{n})):n\in\mathbb{N}\\}$
where

  * •

$\|{b_{n}}\|_{\infty},\|{b_{n}}\|_{1},\|{c_{n}}\|_{\infty},\|{c_{n}}\|_{1}=\Theta(1)$
and,

  * •

$G_{n}\in\mathbb{R}^{n\times n}$ is a matrix where each entry is independently
drawn from the standard normal distribution.

###### Proposition 1

For the problem of state size $n$,
$(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n}))$, picked from the family of
problems defined in problem 1, it is true that

  1. (a)

With probability $1-2\exp{(-\varepsilon^{2}/2)}$, $\|{A_{n}^{-1}}\|_{2}\leq
2\sqrt{n}+\varepsilon$,

  2. (b)

$\textnormal{E}(\|{B_{n}^{\textnormal{T}}(A_{n}^{-1}b_{n}\odot
A_{n}^{-\textnormal{T}}c_{n})}\|)_{2}^{2}\geq\Omega(n)$,

  3. (c)

$\textnormal{E}(|c_{n}^{\textnormal{T}}A_{n}^{-1}b_{n}|^{2})\leq O(1)$,

and consequently, this family of problems on an average satisfies the
$(1/2,1/2)-$asymptotic convergence conditions.

Proposition 1 thus shows that theorem 1 is applicable on average for a design
problem drawn from the distribution of problems defined in problem 1, and thus
guarantees an average case convergence of gradient descent.

The second family of problems is one in which I fix the scaling of the
singular values of the physics matrix with the state size, and generate the
left and right singular vectors randomly — the physical motivation behind this
construction is that the scaling of the spectrum of the physics matrix with
the problem size is often fixed by the derivative operators and boundary
conditions appearing in the physical laws, while the precise singular vectors
depend on the details of the (initial and randomly chosen) design parameters.
Under some assumptions on the scalings of the singular values with the problem
size, the asymptotic convergence conditions (definition 5) are shown to be
satisfied on an average.

###### Problem 2

Given a cost function $f:\mathbb{R}\to\mathbb{R}$ being an $L-$Lipschitz
smooth and $\mu-$strongly convex function that is bounded from below and
$\gamma\geq 1/2$, define a family of physical design problems
$\\{(f,c_{n},\varphi_{n}\equiv(A_{n}:=R_{n}\textnormal{diag}(s_{n})Q_{n}^{\textnormal{T}},B_{n}:=I_{n},b_{n})):n\in\mathbb{N}\\}$
where

  * •

$\|{b_{n}}\|_{\infty},\|{b_{n}}\|_{1},\|{c_{n}}\|_{\infty},\|{c_{n}}\|_{1}=\Theta(1)$,

  * •

$s_{n}\in(0,\infty)^{n}$ with $\|{1/s_{n}}\|_{\infty}\leq O(n^{\gamma})$ and
$\|{1/s_{n}}\|=\Theta(n)$,

  * •

$R_{n},Q_{n}\in\mathbb{R}^{n\times n}$ are drawn uniformly at random from the
Haar measure over orthogonal matrices.

###### Proposition 2

For the problem of state size $n$,
$(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n}))$, picked from the family of
problems defined in problem 2,

  1. (a)

$\|{A_{n}^{-1}}\|_{2}\leq O(n^{\gamma})$,

  2. (b)

$\textnormal{E}(\|{B_{n}^{\textnormal{T}}(A_{n}^{-1}b_{n}\odot
A_{n}^{-\textnormal{T}}c_{n})}\|)_{2}^{2}\geq\Omega(n)$,

  3. (c)

$\textnormal{E}(|c_{n}^{\textnormal{T}}A_{n}^{-1}b_{n}|^{2})\leq O(1)$,

and consequently, this family of problems on an average satisfies the
$1-\gamma,\gamma$-asymptotic convergence conditions.

Consequently using theorem 1, it follows that for $\gamma\in[1/2,3/4)$, a
design problem drawn from the distribution of design problems defined in
problem 1 on an average is efficiently solvable by gradient descent.

Finally, I show that under some further assumptions on the physics matrix of
the physical system, it can shown that all the designs generated during the
gradient descent algorithm are non-resonant, and consequently gradient descent
can be shown to converge to the global optima without the any additional
assumptions on the gradient descent trajectory.

###### Theorem 2

Let
$\mathcal{F}:=\\{(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n})):n\in\mathbb{N}\\}$
be a family of physical design problems that satisfies the
$\alpha,\gamma-$asymptotic convergence conditions (definition 5) with
$\alpha>1/2,\gamma<3\alpha$, and also satisfies
$\|{A_{n}^{-1}}\|_{\textnormal{max}}\leq O(n^{o(1)})$, then gradient descent
when applied on $(f,c_{n},\varphi_{n})$, if it does not fail, produces a
design $\theta_{n}^{*}$ such that
$f(c^{\textnormal{T}}\varphi_{n}(\theta_{n}^{*}))-f^{*}\leq\varepsilon$ in
$T=\Theta(n^{1-2(\alpha-\gamma)}\log(\varepsilon^{-1}))$ steps.

The remainder of this paper is devoted to detailed proofs of these statements
— the proof of theorem 1 is provided in section IV.1, section IV.2 is
dedicated to the proofs of propositions 1 and 2 and the proof of theorem 2 is
provided in section IV.3.

##  IV Detailed Proofs

###  IV.1 Convergence of gradient descent

I begin by establishing an asymptotic property concerning the stability of a
physical system — the object of interest here is to study how a physical
system behaves when the design parameters are perturbed slightly.

###### Lemma 2

Let $\\{\varphi_{n}\equiv(A_{n},B_{n},b_{n}):n\in\mathbb{N}\\}$ be a sequence
of physical systems which satisfies $\|{B_{n}}\|_{\infty}\leq O(1)$ and
$\|{A^{-1}}\|_{2}\leq O(n^{\gamma})$ for some $\gamma>0$, then for all
sequences $\\{\theta_{n}\in\textnormal{dom}(\varphi_{n}):n\in\mathbb{N}\\}$
such that $\|{\theta_{n}}\|_{\infty}\leq O(n^{o(1)-\alpha-\gamma})$ for some
$\alpha>0$, $\|{(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}}\|_{2}\leq
O(n^{\gamma})$.

_Proof_ : It follows straightforwardly that for $n\in\mathbb{N}$,

$\displaystyle(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}=$
$\displaystyle\qquad
A_{n}^{-1}-A_{n}^{-1}\textnormal{diag}(B_{n}\theta_{n})(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}.$

From the triangle inequality, I obtain that

$\displaystyle\|{(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}}\|_{2}\leq\|{A_{n}^{-1}}\|_{2}+$
$\displaystyle\qquad\|{A_{n}^{-1}}\|_{2}\|{B_{n}\theta_{n}}\|_{\infty}\|{(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}}\|_{2}.$

By assumption, $\|{A_{n}^{-1}}\|_{2}\leq O(n^{\gamma})$ for $\gamma>0$, and
$\|{B_{n}\theta_{n}}\|_{\infty}\leq\|{B_{n}}\|_{\infty}\|{\theta_{n}}\|_{\infty}\leq
O(n^{o(1)-\gamma-\alpha})$. Therefore,

$\big{(}1-O(n^{o(1)-\alpha})\big{)}\|{(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}}\|_{2}\leq
O(n^{\gamma}),$

from which the lemma statement follows. $\square$

For completeness, I provide an additional lemma with some standard properties
of Lipschitz continuous and strongly convex functions that I will use in the
following proofs.

###### Lemma 3

Let $f:\mathbb{R}\to\mathbb{R}$ be a twice-differentiable, $L-$Lipschitz
smooth and $\mu-$strongly convex function such that
$f^{*}=\min_{x\in\mathbb{R}}f(x)\geq-\infty$, then

  1. (a)

$\forall x,y\in\mathbb{R}$,

$f(x)\leq f(y)+\nabla f(y)(x-y)+\frac{L}{2}|x-y|^{2}.$

  2. (b)

$\forall x\in\mathbb{R}$,

$2\mu\big{(}f(x)-f^{*}\big{)}\leq|\nabla f(x)|^{2}.$

  3. (c)

$\forall x\in\mathbb{R}$,

$|f^{\prime}(x)|^{2}\leq\frac{2L^{2}}{\mu}(f(x)-f^{*}).$

_Proof_ :

  1. (a)

Since a $L-$Lipschitz smooth function by definition satisfies
$|f^{\prime}(x)-f^{\prime}(y)|\leq L|x-y|\ \forall x,y\in\mathbb{R}$, it
follows that $\forall x\in\mathbb{R},\ |f^{\prime\prime}(x)|\leq L$. From
Taylor’s theorem, it follows that

$\displaystyle f(x)=$ $\displaystyle\quad
f(y)+f^{\prime}(y)(x-y)+\frac{1}{2}\int_{y}^{x}f^{\prime\prime}(s)(x-s)ds.$

Since $\forall s\in[x,y],\ f^{\prime\prime}(s)\leq|f^{\prime\prime}(s)|\leq
L$, it follows that

$\displaystyle f(x)\leq
f(y)+f^{\prime}(y)(x-y)+\frac{L}{2}\int_{y}^{x}(x-s)ds$
$\displaystyle\qquad=f(y)+f^{\prime}(y)(x-y)+\frac{L}{2}|x-y|^{2}.$

  2. (b)

Since $f$ is $\mu-$strongly convex, $\forall x,y\in\mathbb{R}$

$f(x)\geq f(y)+f^{\prime}(y)(x-y)+\frac{\mu}{2}|x-y|^{2}.$

and hence $\forall y\in\mathbb{R}$

$\min_{x\in\mathbb{R}}f(x)\geq\min_{x\in\mathbb{R}}\bigg{(}f(y)+f^{\prime}(y)(x-y)+\frac{\mu}{2}|x-y|^{2}\bigg{)},$

from which it follows that $\forall y\in\mathbb{R}$

$f^{*}\geq f(y)-\frac{1}{2\mu}|f^{\prime}(y)|^{2}.$

  3. (c)

Let $x^{*}=\text{argmin}_{x\in\mathbb{R}}f^{*}$. I note that from stationarity
conditions, $f^{\prime}(x^{*})=0$. From the $L-$Lipschitz continuity, it
follows that $|f^{\prime}(x)|^{2}\leq L^{2}(x-x^{*})^{2}\ \forall\
x\in\mathbb{R}$. Furthermore, from strong convexity of $f$, it follows that
$\forall x\in\mathbb{R}$,

$f(x)\geq f^{*}+\frac{\mu}{2}|x-x^{*}|^{2}.$

Therefore, $\forall\ x\in\mathbb{R}$, $|f^{\prime}(x)|^{2}\leq
2L^{2}/\mu(f(x)-f^{*})$ $\square$.

Next, I analyze the gradient descent algorithm (algorithm 1). The next three
lemmas characterize the decrease in the cost function on taking a gradient
descent step.

###### Lemma 4

Let $(f,c,\varphi\equiv(A,B,b))$ be a physical design problem, and let $f$ be
$L-$Lipschitz smooth, then $\forall\theta\in\textnormal{dom}(\varphi)$ and
$\eta>0$ such that
$\theta^{\prime}:=\theta-\eta\nabla_{\theta}f(c^{\textnormal{T}}\varphi(\theta))\in\textnormal{dom}(\varphi)$,

$\displaystyle f(c^{\textnormal{T}}\varphi(\theta^{\prime}))\leq
f(c^{\textnormal{T}}\varphi(\theta))-\eta(f^{\prime}(c^{\textnormal{T}}\varphi(\theta))^{2}\times$
$\displaystyle\qquad\qquad\big{(}\|{B^{\textnormal{T}}v(\theta)}\|_{2}^{2}+\varepsilon_{1}(\theta,\theta^{\prime})+\eta\varepsilon_{2}(\theta,\theta^{\prime})\big{)},$

where $v(\theta):=\varphi(\theta)\odot\textnormal{ad}[\varphi](\theta,c)$

$\displaystyle\varepsilon_{1}(\theta,\theta^{\prime}):=\textnormal{ad}[\varphi](\theta,c)^{\textnormal{T}}\textnormal{diag}(BB^{\textnormal{T}}v(\theta))(\varphi(\theta^{\prime})-\varphi(\theta)),$
(1a)
$\displaystyle\varepsilon_{2}(\theta,\theta^{\prime}):=-\frac{L}{2}\big{(}\textnormal{ad}[\varphi](\theta,c)^{\textnormal{T}}\textnormal{diag}(BB^{\textnormal{T}}v(\theta))\varphi(\theta^{\prime})\big{)}^{2}.$
(1b)

_Proof_ : Since $f$ is $L-$Lipschitz smooth, it follows that

$\displaystyle f(c^{\textnormal{T}}\varphi(\theta^{\prime}))\leq
f(c^{\textnormal{T}}\varphi(\theta))+f^{\prime}(c^{\textnormal{T}}\varphi(\theta))c^{\textnormal{T}}(\varphi(\theta^{\prime})-\varphi(\theta))+$
$\displaystyle\qquad\qquad\frac{L}{2}\big{(}c^{\textnormal{T}}(\varphi(\theta)-\varphi(\theta^{\prime})\big{)}^{2}.$
(2)

Furthermore, since

$\varphi(\theta^{\prime})-\varphi(\theta)=-(A+\textnormal{diag}(B\theta))^{-1}\textnormal{diag}(B(\theta^{\prime}-\theta))\varphi(\theta^{\prime}),$

I obtain that

$\displaystyle c^{\textnormal{T}}(\varphi(\theta^{\prime})-\varphi(\theta))$
$\displaystyle=-\textnormal{ad}[\varphi](\theta,c)^{\textnormal{T}}\varphi(\theta^{\prime})$
$\displaystyle=-\eta
f^{\prime}(c^{\textnormal{T}}\varphi(\theta))\textnormal{adj}[\varphi](\theta,c)^{\textnormal{T}}\textnormal{diag}(BB^{\textnormal{T}}v(\theta))\varphi(\theta^{\prime}).$
(3)

Expressing
$\varphi(\theta^{\prime})=\varphi(\theta)+(\varphi(\theta^{\prime})-\varphi(\theta))$,
I obtain that

$\displaystyle
c^{\textnormal{T}}(\varphi(\theta^{\prime})-\varphi(\theta))=-\eta
f^{\prime}(c^{\textnormal{T}}\varphi(\theta))\big{(}\|{B^{\textnormal{T}}v(\theta)}\|^{2}+$
$\displaystyle\qquad\qquad\textnormal{adj}[\varphi](\theta,c)^{\textnormal{T}}\textnormal{diag}(BB^{\textnormal{T}}v(\theta))(\varphi(\theta^{\prime})-\varphi(\theta))\big{)}.$
(4)

Substituting Eqs. IV.1 and IV.1 into the Eq. IV.1, I obtain the lemma
statement. $\square$.

###### Lemma 5

Consider a family of physical design problems
$\mathcal{F}:=\\{(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n})\\}$ satisfying
the $\alpha,\gamma$-asymptotic convergence conditions (definition 5). Let
$\eta>0$, and let
$\\{\theta_{n}\in\textnormal{dom}(\varphi_{n}):n\in\mathbb{N}\\}$ be a
sequence non-resonant with respect to $\mathcal{F}$ with
$\|{\theta_{n}}\|_{\infty}\leq O(n^{o(1)-\alpha-\gamma})$. Furthermore,
suppose that the sequence
$\\{\theta_{n}^{\prime}:=\theta_{n}-\eta\nabla_{\theta}f(c^{\text{T}}_{n}\varphi_{n}(\theta_{n})):n\in\mathbb{N}\\}$
satisfies $\|{\theta_{n}^{\prime}}\|_{\infty}\leq O(n^{o(1)-\alpha-\gamma})$,
then $|\varepsilon_{1}(\theta_{n},\theta_{n}^{\prime})|\leq
O(n^{o(1)+\gamma-\alpha+1/2})$, where $\varepsilon_{1}$ is defined in lemma 4.

_Proof_ : From the definition of $\varepsilon_{1}$ it follows that $\forall
n\in\mathbb{N}$,

$\displaystyle|\varepsilon_{1}(\theta_{n},\theta_{n}^{\prime})|\leq\sqrt{n}\|{\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n})^{\textnormal{T}}\textnormal{diag}(B_{n}B_{n}^{\textnormal{T}}v_{n}(\theta_{n}))}\|_{\infty}\times$
$\displaystyle\qquad\qquad\|{\varphi_{n}(\theta_{n}^{\prime})-\varphi_{n}(\theta_{n})}\|_{2},$
(5)

where
$v_{n}(\theta_{n})=\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n})\odot\varphi_{n}(\theta_{n})$.
Since the sequence $\\{\theta_{n}:n\in\mathbb{N}\\}$ is non-resonant,
$\|{\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n})^{\textnormal{T}}\textnormal{diag}(B_{n}B_{n}^{\textnormal{T}}v_{n}(\theta_{n}))}\|_{\infty}\leq
O(n^{o(1)})$. Furthermore, $\forall n\in\mathbb{N}$

$\displaystyle\|{\varphi_{n}(\theta_{n})-\varphi_{n}(\theta_{n}^{\prime})}\|_{2}\leq$
$\displaystyle\qquad\|{(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}}\|_{2}\|{B_{n}(\theta_{n}-\theta_{n}^{\prime})}\|_{\infty}\|{\varphi_{n}(\theta_{n}^{\prime})}\|_{2}$

It follows from lemma 2 that
$\|{(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}}\|_{2}\leq O(n^{\gamma})$
and
$\|{\varphi_{n}(\theta_{n}^{\prime})}\|_{2}\leq\|{(A_{n}+\textnormal{diag}(B_{n}\theta_{n}))^{-1}}\|_{2}\sqrt{\|{b}\|_{\infty}\|{b}\|_{1}}\leq
O(n^{\gamma})$. Finally,
$\|{B_{n}(\theta_{n}-\theta_{n}^{\prime})}\|_{\infty}\leq\|{B}\|_{n}(\|{\theta_{n}}\|_{\infty}+\|{\theta_{n}^{\prime}}\|_{\infty})\leq
O(n^{o(1)-\alpha-\gamma})$ and thus
$\|{\varphi_{n}(\theta_{n}^{\prime})-\varphi_{n}(\theta_{n})}\|_{2}\leq
O(n^{o(1)+\gamma-\alpha})$. Using these estimates the lemma statement follows.

###### Lemma 6

Consider a family of physical design problems
$\mathcal{F}:=\\{(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n}))\\}$ satisfying
the $\alpha,\gamma-$asymptotic convergence conditions (definition 5). Let
$\eta>0$ and $\\{\theta_{n}\in\textnormal{dom}(\varphi_{n}):n\in\mathbb{N}\\}$
be a sequence non-resonant with respect to $\mathcal{F}$ with
$\|{\theta_{n}}\|_{\infty}\leq O(n^{o(1)-\alpha-\gamma})$. Furthermore,
suppose that the sequence
$\\{\theta_{n}^{\prime}:=\theta_{n}-\eta\nabla_{\theta}f(c_{n}^{\textnormal{T}}\varphi_{n}(\theta_{n})):n\in\mathbb{N}\\}$
satisfies $\|{\theta_{n}^{\prime}}\|_{\infty}\leq O(n^{o(1)-\alpha-\gamma})$,
then $|\varepsilon_{2}(\theta_{n},\theta_{n}^{\prime})|\leq
O(n^{o(1)+4\gamma})$, where $\varepsilon_{2}$ is defined in lemma 4.

_Proof_ : I note that $\forall n\in\mathbb{N}$,
$|\varepsilon_{2}(\theta_{n})|\leq
L/2\|{\textnormal{adj}[\varphi_{n}](\theta_{n},c_{n})}\|\|{\varphi_{n}(\theta_{n})}\|\|{B_{n}B_{n}^{\textnormal{T}}v_{n}(\theta_{n})}\|_{\infty}$,
where, as in lemma 5,
$v_{n}(\theta_{n}):=\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n})\odot\varphi_{n}(\theta_{n})\
\forall\ n\in\mathbb{N}$. It follows from lemma 2 and the observation that
$\|{b}\|\leq\sqrt{\|{b}\|_{1}\|{b}\|_{\infty}}\leq O(1)$ that
$\|{\varphi_{n}(\theta_{n})}\|\leq O(n^{\gamma})$. Similarly,
$\|{\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n})}\|\leq O(n^{\gamma})$.
Furthermore,
$\|{B_{n}B_{n}^{\textnormal{T}}}\|_{\infty}\leq\|{B_{n}}\|_{\infty}\|{B_{n}}\|_{1}\leq
O(1)$ and since $\\{\theta_{n}:n\in\mathbb{N}\\}$ is non-resonant,
$\|{\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n})}\|_{\infty}\leq
O(n^{o(1)})$. From these estimates, the lemma statement follows.

###### Lemma 7

Consider a family of physical design problems
$\mathcal{F}:=\\{(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n}))\\}$ satisfying
the $\alpha,\gamma$-asymptotic convergence conditions (definition 5) with
$3\alpha>\gamma$ and $\|{A_{n}^{-\textnormal{T}}c_{n}}\|_{\infty}\leq
O(n^{o(1)})$. Let
$\\{\theta_{n}\in\textnormal{dom}(\varphi_{n}):n\in\mathbb{N}\\}$ be a
sequence non-resonant with respect to $\mathcal{F}$ such that
$\|{\theta_{n}}\|_{\infty}\leq O(n^{o(1)-\alpha-\gamma})$, then
$\|{B_{n}^{\textnormal{T}}(\varphi_{n}(\theta_{n})\odot\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n}))}\|^{2}\geq\Omega(n^{\alpha+\gamma})$.

_Proof_ : For notational convenient, let
$v_{n}(\theta)=\varphi_{n}(\theta)\odot\textnormal{ad}[\varphi_{n}](\theta,c_{n})\
\forall\theta\in\textnormal{dom}(\varphi_{n}),\ n\in\mathbb{N}$. I first upper
bound $\|{B_{n}^{\textnormal{T}}(v_{n}(\theta_{n})-v_{n}(0))}\|$. Notice that

$\|{B_{n}^{\textnormal{T}}(v_{n}(\theta_{n})-v_{n}(0))}\|\leq\|{B_{n}}\|_{2}\|{v_{n}(\theta_{n})-v_{n}(0)}\|.$

Furthermore,

$\displaystyle\|{v_{n}(\theta_{n})-v_{n}(0)}\|\leq$
$\displaystyle\qquad\|{\varphi_{n}(\theta_{n})}\|_{\infty}\|{\text{ad}[\varphi_{n}](\theta_{n},c_{n})-\text{ad}[\varphi_{n}](0,c_{n})}\|+$
$\displaystyle\qquad\|{\textnormal{ad}[\varphi_{n}](0,c_{n})}\|_{\infty}\|{\varphi_{n}(\theta_{n})-\varphi_{n}(0)}\|.$

Note that since $\\{\theta_{n}:n\in\mathbb{N}\\}$ is non-resonant,
$\|{\varphi_{n}(\theta_{n})}\|_{\infty}\leq O(n^{o(1)})$ and by assumption
$\|{\textnormal{ad}[\varphi_{n}](0,c_{n})}\|_{\infty}=\|{A_{n}^{-\textnormal{T}}c_{n}}\|_{\infty}\leq
O(n^{o(1)})$. Furthermore, $\forall n\in\mathbb{N}$

$\|{\varphi_{n}(\theta_{n})-\varphi_{n}(0)}\|\leq\|{A_{n}^{-1}}\|_{2}\|{B_{n}\theta_{n}}\|_{\infty}\|{\varphi_{n}(\theta_{n})}\|.$

I note that by assumption $\|{A_{n}^{-1}}\|_{2}\leq O(n^{\gamma})$,
$\|{B_{n}\theta_{n}}\|\leq O(n^{o(1)-\alpha-\gamma})$ and
$\|{\varphi_{n}(\theta_{n})}\|\leq\|{(A_{n}+\text{diag}(B_{n}\theta_{n}))^{-1}}\|_{2}\|{b_{n}}\|\leq
O(n^{\gamma})$. Consequently,
$\|{\varphi_{n}(\theta_{n})-\varphi_{n}(0)}\|\leq O(n^{o(1)+\gamma-\alpha})$.
Similarly,
$\|{\text{ad}[\varphi_{n}](\theta_{n},c_{n})-\text{ad}[\varphi_{n}](0,c_{n})}\|\leq
O(n^{o(1)+\gamma-\alpha})$, which yields

$\|{B_{n}^{\text{T}}(v_{n}(\theta_{n})-v_{n}(0))}\|\leq
O(n^{o(1)+\gamma-\alpha}).$

Finally, I note that from the triangle inequality

$\|{B_{n}^{\text{T}}v_{n}(\theta_{n})}\|\geq\|{B_{n}^{\text{T}}v_{n}(0)}\|-\|{B_{n}^{\text{T}}(v_{n}(\theta_{n})-v_{n}(0))}\|.$

Since, by assumption,
$\|{B_{n}^{\text{T}}v_{n}(0)}\|\geq\Omega(n^{(\alpha+\gamma)/2})$ and
$\gamma<3\alpha$, I obtain that
$\|{B_{n}^{\text{T}}v_{n}(\theta_{n})}\|\geq\Omega(n^{(\alpha+\gamma)/2})$,
from which the lemma statement follows. $\square$.

Theorem 1 (Restated) _Let
$\mathcal{F}:=\\{(f,c_{n},\varphi_{n}):n\in\mathbb{N}\\}$ be a family of
physical design problems that satisfies the $\alpha,\gamma-$asymptotic
convergence conditions (definition 5) with $\alpha>1/4,\gamma<3\alpha$, and
for $n\in\mathbb{N}$, let
$\Theta_{n}=\\{\theta_{n}^{1},\theta_{n}^{2}\dots\theta_{n}^{T_{n}}\\}$ be the
design parameters generated by gradient descent (algorithm 1) under the
assumption that it does not fail when applied on $(f,c_{n},\varphi_{n})$ with
step size $\eta_{n}\leq O(n^{-3\gamma+\alpha-1})$ for $T_{n}$ steps starting
with initial design of $\theta_{n}^{0}=0$. If all the sequences
$\\{\theta_{n}\in\Theta_{n}:n\in\mathbb{N}\\}$ are non-resonant with respect
to $\mathcal{F}$, then
$f(c_{n}^{\textnormal{T}}\varphi_{n}(\theta_{n}^{T_{n}}))-f^{*}\leq\varepsilon$
for $T$ chosen such that
$T_{n}=\Theta(n^{1-2(\alpha-\gamma)}\log(\varepsilon^{-1}))$._

_Proof_ : Consider the trajectory
$\\{\theta_{n}^{1}\dots\theta_{n}^{T_{n}}\\}$ generated by gradient descent
when applied for $T_{n}$ steps on the problem $(f,c_{n},\varphi_{n})$ starting
from $\theta_{n}^{0}=0$ and with step size $\eta_{n}$. I will first analyze
the final cost function achieved under the assumption that $\forall
t\in[T_{n}]$, $\|{\theta_{n}^{t}}\|_{\infty}\leq O(n^{o(1)-\alpha-\gamma})$,
and show that it can be made $\varepsilon-$close to $f^{*}$ after
$T_{n}=\Theta(n^{1-2(\alpha-\gamma)}\text{log}(\varepsilon^{-1}))$ gradient
descent steps. Then, I will show that this assumption is valid for all
gradient descent steps.

I note with this assumption and the assumption that gradient descent algorithm
generates a trajectory that is non-resonant, lemmas 4-7 are applicable. From
lemmas 5 and 7, it is easy to see that if $\alpha>1/4$, then $\forall
t\in\\{0,1,2\dots T_{n}-1\\}$,

$\|{B_{n}^{\text{T}}(\varphi_{n}(\theta_{n}^{t})\cdot\text{ad}[\varphi_{n}](\theta_{n}^{t},c_{n})}\|^{2}+2\varepsilon_{1}(\theta_{n}^{t},\theta_{n}^{t+1})\geq\Omega(n^{\alpha+\gamma}).$

Similarly, choosing $\eta_{n}\leq O(n^{-3\gamma+\alpha-1})$, it follows from
lemmas 6 and 7 that $\forall t\in\\{0,1,2\dots T_{n}-1\\}$

$\|{B_{n}^{\text{T}}(\varphi_{n}(\theta_{n}^{t})\cdot\text{ad}[\varphi_{n}](\theta_{n}^{t},c_{n})}\|^{2}+2\varepsilon_{2}(\theta_{n}^{t},\theta_{n}^{t+1})\geq\Omega(n^{\alpha+\gamma}).$

Consequently, from lemma 4, I obtain that $\forall t\in[T_{n}]$

$f(c_{n}^{\text{T}}\varphi_{n}(\theta_{t}^{n}))\leq
f(c_{n}^{\text{T}}\varphi_{n}(\theta^{t-1}_{n}))-\eta_{n}f^{\prime}(c_{n}^{\text{T}}\varphi_{n}(\theta_{n}^{t-1}))^{2}\Omega(n^{\alpha+\gamma}),$

From lemma 3b it follows that

$f(c_{n}^{\text{T}}\varphi_{n}(\theta_{t}^{n}))-f^{*}\leq(f(c_{n}^{\text{T}}\varphi_{n}(\theta_{t-1}^{n}))-f^{*})(1-\eta_{n}\Omega(n^{\alpha+\gamma})).$

where $f^{*}=\min_{x\in\mathbb{R}}f(x)$. Noting that, from lemma 3b along with
asymptotic convergence condition (g), it follows that

$\displaystyle f(c_{n}^{\text{T}}\varphi_{n}(\theta_{0}^{n}))-f^{*}$
$\displaystyle=f(c_{n}^{\text{T}}A_{n}^{-1}b_{n})-f^{*}$
$\displaystyle\leq\frac{L}{2}\big{(}c_{n}^{\text{T}}A_{n}^{-1}b_{n}-x^{*})^{2}$
$\displaystyle\leq O(1),$

where $x^{*}=\textnormal{argmin}_{x\in\mathbb{R}}f(x)$ and therefore

$f(c_{n}^{\text{T}}\varphi_{n}(\theta_{T_{n}}^{n}))-f^{*}\leq
O(1)(1-\eta_{n}\Omega(n^{\alpha+\gamma}))^{T_{n}}.$

Consequently, using
$T_{n}=\Theta(n^{1-2(\alpha-\gamma)}\text{log}(\varepsilon^{-1}))$, I obtain
that
$f(c_{n}^{\text{T}}\varphi_{n}(\theta^{n}_{T_{n}}))-f^{*}\leq\varepsilon$.

Next, I verify that the assumption $\|{\theta_{n}^{t}}\|_{\infty}\leq
O(n^{o(1)-\alpha-\gamma})$ holds for all $t\in[T_{n}]$. I notice that for all
$t\in[T_{n}]$, the norm of $\theta_{n}^{t}$ can be upper bounded by the sum of
norms of gradients in the previous steps, multiplied by the step size. Using
lemma 1

$\displaystyle\|{\theta_{n}^{t}}\|_{\infty}\leq$
$\displaystyle\eta_{n}\sum_{t^{\prime}=0}^{t-1}|f^{\prime}(c_{n}\varphi_{n}(\theta_{n}^{t^{\prime}}))|\|{B_{n}^{\text{T}}(\varphi_{n}(\theta_{n}^{t^{\prime}})\odot\text{ad}[\varphi_{n}](\theta_{n}^{t^{\prime}},c_{n}))}\|_{\infty}.$

Furthermore, using the fact that $\|{B_{n}}\|_{1}\leq O(1)$, and that the
gradient descent trajectory is assumed to be non-resonant,
$\|{B_{n}^{\text{T}}(\varphi_{n}(\theta_{n}^{t})\odot\text{ad}[\varphi_{n}](\theta_{n}^{t},c_{n}))}\|_{\infty}\leq
O(n^{o(1)})$ $\forall t\in[T_{n}]$. Furthermore, from lemma 3(c), it follows
that

$\displaystyle|f^{\prime}(c_{n}\varphi_{n}(\theta_{n}^{t^{\prime}}))|$
$\displaystyle\leq(2L^{2}/\mu)^{1/2}(f(c_{n}^{\text{T}}\varphi_{n}(\theta_{n}^{t^{\prime}}))-f^{*}))^{1/2}$
$\displaystyle\leq O(1)(1-\eta_{n}\Omega(n^{\alpha+\gamma}))^{t^{\prime}/2}.$

Therefore,

$\displaystyle\|{\theta_{n}^{t}}\|_{\infty}$
$\displaystyle\leq\eta_{n}O(n^{o(1)})\sum_{t^{\prime}=0}^{t-1}(1-\eta_{n}\Omega(n^{\alpha+\gamma}))^{t^{\prime}/2}$
$\displaystyle\leq\frac{\eta_{n}O(n^{o(1)})}{1-(1-\eta_{n}\Omega(n^{\alpha+\gamma}))^{1/2}}$
$\displaystyle\leq O(n^{o(1)-\alpha-\gamma}).$

This completes the proof of the lemma $\square$.

###  IV.2 Analysis of random family of physical design problems

Problem 1 (Restated) _Given a cost function $f:\mathbb{R}\to\mathbb{R}$ being
an $L-$Lipschitz smooth and $\mu-$strongly convex function that is bounded
from below, define a family of physical design problems
$\mathcal{F}:=\\{(f,c_{n},\varphi_{n}\equiv(A_{n}:=G_{n}^{-1},B_{n}:=I_{n},b_{n})):n\in\mathbb{N}\\}$
where_

  * •

$\|{b_{n}}\|_{\infty},\|{b_{n}}\|_{1},\|{c_{n}}\|_{\infty},\|{c_{n}}\|_{1}=\Theta(1)$_and,_

  * •

$G_{n}\in\mathbb{R}^{n\times n}$_is a matrix where each entry is independently
drawn from the standard normal distribution._

Proposition 1 (Restated) _For the problem of state size $n$,
$(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n}))$, picked from the family of
problems defined in problem 1, it is true that_

  1. (a)

_With probability_ $1-2\exp{(-\varepsilon^{2}/2)}$, $\|{A_{n}^{-1}}\|_{2}\leq
2\sqrt{n}+\varepsilon$,

  2. (b)

$\textnormal{E}(\|{B_{n}^{\textnormal{T}}(A_{n}^{-1}b_{n}\odot
A_{n}^{-\textnormal{T}}c_{n})}\|)_{2}^{2}\geq\Omega(n)$_,_

  3. (c)

$\textnormal{E}(|c_{n}^{\textnormal{T}}A_{n}^{-1}b_{n}|^{2})\leq O(1)$_,_

_and consequently, this family of problems on an average satisfies the
$1/2,1/2-$asymptotic convergence conditions._

_Proof_ :

  1. (a)

This is a standard result in random matrix theory, for e.g. see Ref. Davidson
and Szarek (2001).

  2. (b)

It follows from straightforward computation that

$\displaystyle\textnormal{E}(\|{B_{n}^{\textnormal{T}}(A_{n}^{-1}b_{n}\odot
A_{n}^{-\textnormal{T}}c_{n})}\|)_{2}^{2}$
$\displaystyle\qquad=\text{E}(\|{G_{n}b_{n}\odot
G_{n}^{\text{T}}c_{n}}\|^{2})$
$\displaystyle\qquad=n\|{b_{n}}\|^{2}\|{c_{n}}\|^{2}+\|{b_{n}\odot
c_{n}}\|^{2}.$

Noting that $\|{b_{n}}\|^{2}\geq\|{b_{n}}\|_{\infty}^{2}\geq\Omega(1)$ and
$\|{c_{n}}\|^{2}\geq\|{c_{n}}\|_{\infty}^{2}\geq\Omega(1)$, the lemma
statement follows.

  3. (c)

I note that.

$\displaystyle\text{E}(|c_{n}^{\text{T}}A_{n}^{-1}b_{n}|^{2})$
$\displaystyle=\text{E}\big{(}c_{n}^{\text{T}}G_{n}b_{n}b_{n}^{\text{T}}G_{n}^{\text{T}}c_{n}\big{)}$
$\displaystyle=\|{c_{n}}\|^{2}\|{b_{n}}\|^{2}.$

Since $\|{b_{n}}\|^{2}\leq\|{b_{n}}\|_{1}^{2}\leq O(1)$ and
$\|{c_{n}}\|^{2}\leq\|{c_{n}}\|_{1}^{2}\leq O(1)$, the lemma statement
follows. $\square$

Problem 2 (Restated) _Given a cost function $f:\mathbb{R}\to\mathbb{R}$ being
an $L-$Lipschitz smooth and $\mu-$strongly convex function that is bounded
from below and $\gamma\geq 1/2$, define a family of physical design problems
$\\{(f,c_{n},\varphi_{n}\equiv(A_{n}:=R_{n}\textnormal{diag}(s_{n})Q_{n}^{\textnormal{T}},B_{n}:=I_{n},b_{n})):n\in\mathbb{N}\\}$
where_

  * •

$\|{b_{n}}\|_{\infty},\|{b_{n}}\|_{1},\|{c_{n}}\|_{\infty},\|{c_{n}}\|_{1}=\Theta(1)$_,_

  * •

$s_{n}\in(0,\infty)^{n}$_with_ $\|{1/s_{n}}\|_{\infty}\leq O(n^{\gamma})$ and
$\|{1/s_{n}}\|=\Theta(n)$,

  * •

$R_{n},Q_{n}\in\mathbb{R}^{n\times n}$_are drawn uniformly at random from the
Haar measure over orthogonal matrices._

###### Lemma 8

Let $M=R\ \textnormal{diag}(v)Q^{\text{T}}\in\mathbb{R}^{d\times d}$, where
$R,Q$ are orthogonal matrices drawn independently from the Haar random measure
over the set of $d\times d$ orthogonal matrices, and $b,c\in\mathbb{R}^{d}$,
then

$\textnormal{E}\big{(}(c^{\textnormal{T}}Mb)^{2}\big{)}=\frac{1}{d^{2}}\|{v}\|^{2}\|{b}\|^{2}\|{c}\|^{2}.$

_Proof_ : Provided in appendix A.

###### Lemma 9

Let $M=R\ \textnormal{diag}(v)Q^{\text{T}}\in\mathbb{R}^{d\times d}$, where
$R,Q$ are orthogonal matrices drawn independently from the Haar random measure
over the set of $d\times d$ orthogonal matrices, and $b,c\in\mathbb{R}^{d}$,
then

$\textnormal{E}\big{(}\|{Mb\odot
M^{\textnormal{T}}c}\|^{2}\big{)}=\|{b}\|^{2}\|{c}\|^{2}\|{v}\|^{4}\Omega\bigg{(}\frac{1}{d^{3}}\bigg{)}.$

_Proof_ : Provided in appendix A.

Proposition 2 (Restated) _For the problem of state size $n$,
$(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n}))$, picked from the family of
problems defined in problem 2,_

  1. (a)

$\|{A_{n}^{-1}}\|_{2}\leq O(n^{\gamma})$_,_

  2. (b)

$\textnormal{E}(\|{B_{n}^{\textnormal{T}}(A_{n}^{-1}b_{n}\odot
A_{n}^{-\textnormal{T}}c_{n})}\|)^{2}\geq\Omega(n)$_,_

  3. (c)

$\textnormal{E}(|c_{n}^{\textnormal{T}}A_{n}^{-1}b_{n}|^{2})\leq O(1)$_,_

_and consequently, this family of problems on an average satisfies the
$1-\gamma,\gamma$-asymptotic convergence conditions. _

_Proof_ :

  * (a)

This follows straightforwardly by noting that $\|{R_{n}}\|=\|{Q_{n}}\|=1\
\forall\ n\in\mathbb{N}$ and
$\|{\text{diag}(s_{n})^{-1}}\|=\|{1/s_{n}}\|_{\infty}\leq O(n^{\gamma})$.

  * (b)

Using lemma 9, it immediately follows that

$\displaystyle\text{E}(\|{B_{n}^{\text{T}}(A_{n}^{-1}b_{n}\odot
A_{n}^{-\text{T}}c_{n})}\|^{2})$
$\displaystyle\qquad\geq\|{b_{n}}\|^{2}\|{c_{n}}\|^{2}\|{1/s_{n}}\|^{4}\Omega(n^{-3}).$

Noting that
$\|{b_{n}}\|^{2}\|{c_{n}}\|^{2}\geq\|{b_{n}}\|_{\infty}^{2}\|{c_{n}}\|_{\infty}^{2}\geq\Omega(1)$
and $\|{1/s_{n}}\|^{4}\geq\Omega(n^{4})$, the lemma statement follows.

  * (c)

Using lemma 8, it follows that

$\displaystyle\text{E}\big{(}(c_{n}^{\text{T}}A_{n}^{-1}b_{n})^{2}\big{)}=\frac{1}{n^{2}}\|{c_{n}}\|^{2}\|{b_{n}}\|^{2}\|{1/s_{n}}\|^{2}.$

Since
$\|{c_{n}}\|^{2}\|{b_{n}}\|^{2}\leq\|{c_{n}}\|_{1}^{2}\|{b_{n}}\|_{1}^{2}\leq
O(1)$, and $\|{1/s_{n}}\|^{2}\leq O(n^{2})$, the lemma statement follows.
$\square$

###  IV.3 Provably non-resonant problems

###### Lemma 10

Let $\\{\varphi_{n}\equiv(A_{n},B_{n},b_{n}):n\in\mathbb{N}\\}$ be a sequence
of physical systems which satisfies $\|{b_{n}}\|_{1}\leq O(1)$,
$\|{B_{n}}\|_{\infty}\leq O(1)$, $\|{A_{n}^{-1}}\|_{\textnormal{max}}\leq
O(n^{o(1)})$ and $\|{A^{-1}}\|_{2}\leq O(n^{\gamma})$ for some $\gamma<1/2$,
then $\forall$ sequences
$\\{\theta_{n}\in\textnormal{dom}(\varphi_{n}):n\in\mathbb{N}\\},\\{c_{n}\in\mathbb{R}^{n}:n\in\mathbb{N}\\}$
such that $\|{\theta_{n}}\|_{\infty}\leq O(n^{o(1)-1})$ and
$\|{c_{n}}\|_{1}\leq O(1)$, $\|{\varphi_{n}(\theta_{n})}\|_{\infty}\leq
O(n^{o(1)})$ and
$\|{\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n})}\|_{\infty}\leq
O(n^{o(1)})$.

_Proof_ : It follows straightforwardly that for $n\in\mathbb{N}$,

$\displaystyle\varphi_{n}(\theta_{n})=A_{n}^{-1}b_{n}-A_{n}^{-1}\textnormal{diag}(B_{n}\theta_{n})\varphi_{n}(\theta_{n}).$

Consequently,

$\displaystyle\|{\varphi_{n}(\theta_{n})}\|_{\infty}\leq\|{A_{n}^{-1}b_{n}}\|_{\infty}+\|{A_{n}^{-1}\textnormal{diag}(B_{n}\theta_{n})\varphi_{n}(\theta_{n})}\|_{\infty}$
$\displaystyle\qquad\leq\|{A_{n}^{-1}}\|_{\textnormal{max}}\|{b_{n}}\|_{1}+\sqrt{n}\|{A_{n}^{-1}}\|_{2}\|{B_{n}\theta_{n}}\|_{\infty}\|{\varphi_{n}(\theta_{n})}\|_{\infty}.$

By assumption, $\|{A_{n}^{-1}}\|_{2}\leq O(n^{\gamma})$ for $\gamma<1/2$, and
$\|{B_{n}\theta_{n}}\|_{\infty}\leq\|{B_{n}}\|_{\infty}\|{\theta_{n}}\|_{\infty}\leq
O(n^{o(1)-1})$. Therefore,

$\big{(}1-O(n^{o(1)+\gamma-1/2})\big{)}\|{\varphi_{n}(\theta_{n})}\|_{\infty}\leq
O(n^{o(1)}),$

from which it follows that $\|{\varphi_{n}(\theta_{n})}\|\leq O(n^{o(1)})$. A
similar analysis yields
$\|{\textnormal{ad}[\varphi_{n}](\theta_{n},c_{n})}\|_{\infty}\leq
O(n^{o(1)})$. $\square$

Theorem 2 (Restated) _Let
$\mathcal{F}:=\\{(f,c_{n},\varphi_{n}\equiv(A_{n},B_{n},b_{n})):n\in\mathbb{N}\\}$
be a family of physical design problems that satisfies the
$\alpha,\gamma-$asymptotic convergence conditions (definition 5) with
$\alpha>1/2,\gamma<3\alpha$, and also satisfies
$\|{A_{n}^{-1}}\|_{\textnormal{max}}\leq O(n^{o(1)})$, then gradient descent
when applied on $(f,c_{n},\varphi_{n})$, if it does not fail, produces a
design $\theta_{n}^{*}$ such that
$f(c^{\textnormal{T}}\varphi_{n}(\theta_{n}^{*}))-f^{*}\leq\varepsilon$ in
$T=\Theta(n^{1-2(\alpha-\gamma)}\log(\varepsilon^{-1}))$ steps._

_Proof_ : This theorem can be proved by repeating the analysis in the proof of
theorem 1, and noting from lemma 10 that the assumption that the gradient
descent trajectory $\\{\theta_{n}^{1},\theta_{n}^{2}\dots\\}$ obtained for the
problem $(f,c_{n},\varphi_{n})$ satisfies $\|{\theta_{n}^{t}}\|_{\infty}\leq
O(n^{\alpha+\gamma})$ implies that the trajectory is also non-resonant.
$\square$

##  V Conclusion and open problems

In conclusion, this work provides rigorous evidence for local optimization
algorithms being efficient at solving physical design problems. I show that,
under some assumptions on the physics of the system, non-resonant physical
design problems are efficiently solvable by gradient descent. Furthermore, I
also outline random ensembles of physical design problems which are, on an
average, efficiently solvable by local optimization algorithms.

This work, while being a first step towards theoretically understanding the
complexity of typical physical design problems, leaves several questions open.
One question is to better characterize when a physical design problem is
resonant — in this analysis, I need to assume that gradient descent avoids
resonant designs in order to show that it globally solves the design problem.
While theorem 2 makes some progress in this direction, it would be interesting
to more carefully analyze the gradient descent trajectory and obtain a set of
weaker conditions on the design problems under which gradient descent avoids
resonant devices. Another interesting direction would be to study the
optimality of gradient descent on specific design problems, or ensembles of
design problems, appearing in practical settings using the tools introduced in
this paper. Finally, extending the analysis introduced in this paper to other
optimization algorithms (such as quasi-Newton methods like BFGS, L-BFGS, or
method of moving asymptotes), would also go a long way in making the rigorous
results practically relevant.

###### Acknowledgements.

I thank Shivam Garg, Logan Su, Geunho Ahn and Alex White for useful
discussion. I acknowledge support from Max Planck Harvard Research Center for
Quantum Optics (MPHQ) postdoctoral fellowship.

## References

  * Molesky  _et al._ (2018) S. Molesky, Z. Lin, A. Y. Piggott, W. Jin, J. Vucković, and A. W. Rodriguez, Nature Photonics 12, 659 (2018).
  * Su  _et al._ (2018a) L. Su, A. Y. Piggott, N. V. Sapra, J. Petykiewicz, and J. Vuckovic, Acs Photonics 5, 301 (2018a).
  * Piggott  _et al._ (2019) A. Y. Piggott, E. Y. Ma, L. Su, G. H. Ahn, N. V. Sapra, D. J. Vercruysse, A. M. Netherton, A. S. Khope, J. E. Bowers, and J. Vučković, arXiv preprint arXiv:1911.03535 (2019).
  * Su  _et al._ (2018b) L. Su, R. Trivedi, N. V. Sapra, A. Y. Piggott, D. Vercruysse, and J. Vučković, Optics express 26, 4023 (2018b).
  * Piggott  _et al._ (2017) A. Y. Piggott, J. Petykiewicz, L. Su, and J. Vučković, Scientific reports 7, 1 (2017).
  * Sapra  _et al._ (2019) N. V. Sapra, D. Vercruysse, L. Su, K. Y. Yang, J. Skarda, A. Y. Piggott, and J. Vučković, IEEE Journal of Selected Topics in Quantum Electronics 25, 1 (2019).
  * Roslund and Rabitz (2009) J. Roslund and H. Rabitz, Physical Review A 79, 053417 (2009).
  * Lucarelli (2018) D. Lucarelli, Physical Review A 97, 062346 (2018).
  * Werschnik and Gross (2007) J. Werschnik and E. Gross, Journal of Physics B: Atomic, Molecular and Optical Physics 40, R175 (2007).
  * Li  _et al._ (2017) J. Li, X. Yang, X. Peng, and C.-P. Sun, Physical review letters 118, 150503 (2017).
  * Zhu and Rabitz (1998) W. Zhu and H. Rabitz, The Journal of Chemical Physics 109, 385 (1998).
  * Rozvany (2009) G. I. Rozvany, Structural and multidisciplinary optimization 37, 217 (2009).
  * Wang  _et al._ (2003) M. Y. Wang, X. Wang, and D. Guo, Computer methods in applied mechanics and engineering 192, 227 (2003).
  * Hassani and Hinton (2012) B. Hassani and E. Hinton,  _Homogenization and structural topology optimization: theory, practice and software_ (Springer Science & Business Media, 2012).
  * Giles and Pierce (2000) M. B. Giles and N. A. Pierce, Flow, turbulence and combustion 65, 393 (2000).
  * Bakr and Nikolova (2004) M. H. Bakr and N. K. Nikolova, IEEE Transactions on Microwave Theory and Techniques 52, 554 (2004).
  * Park  _et al._ (1996) I.-h. Park, I.-G. Kwak, H.-B. Lee, S.-Y. Hahn, and K.-S. Lee, IEEE transactions on magnetics 32, 1242 (1996).
  * Dong  _et al._ (2004) J. Dong, K. K. Choi, and N. H. Kim, J. Mech. Des. 126, 527 (2004).
  * Soliman  _et al._ (2004) E. A. Soliman, M. H. Bakr, and N. K. Nikolova, IEEE transactions on microwave theory and techniques 52, 589 (2004).
  * Ruder (2016) S. Ruder, arXiv preprint arXiv:1609.04747 (2016).
  * Gill and Murray (1972) P. E. Gill and W. Murray, IMA Journal of Applied Mathematics 9, 91 (1972).
  * Miller  _et al._ (2016) O. D. Miller, A. G. Polimeridis, M. H. Reid, C. W. Hsu, B. G. DeLacy, J. D. Joannopoulos, M. Soljačić, and S. G. Johnson, Optics express 24, 3329 (2016).
  * Shim  _et al._ (2019) H. Shim, L. Fan, S. G. Johnson, and O. D. Miller, Physical Review X 9, 011043 (2019).
  * Venkataram  _et al._ (2020) P. S. Venkataram, S. Molesky, W. Jin, and A. W. Rodriguez, Physical Review Letters 124, 013904 (2020).
  * Molesky  _et al._ (2020) S. Molesky, P. S. Venkataram, W. Jin, and A. W. Rodriguez, Physical Review B 101, 035408 (2020).
  * Molesky  _et al._ (2019) S. Molesky, W. Jin, P. S. Venkataram, and A. W. Rodriguez, Physical Review Letters 123, 257401 (2019).
  * Angeris  _et al._ (2019) G. Angeris, J. Vuckovic, and S. P. Boyd, ACS Photonics 6, 1232 (2019).
  * Kuang  _et al._ (2020) Z. Kuang, L. Zhang, and O. D. Miller, Optica 7, 1746 (2020).
  * Kuang and Miller (2020) Z. Kuang and O. D. Miller, Physical Review Letters 125, 263607 (2020).
  * Zhang  _et al._ (2021) H. Zhang, Z. Kuang, S. Puri, and O. D. Miller, Physical Review Letters 127, 110506 (2021).
  * Zhang and Miller (2020) L. Zhang and O. D. Miller, ACS Photonics 7, 3116 (2020).
  * Kern  _et al._ (2020) C. Kern, O. D. Miller, and G. W. Milton, Physical Review Applied 14, 054068 (2020).
  * Allen-Zhu  _et al._ (2019a) Z. Allen-Zhu, Y. Li, and Z. Song, in  _International Conference on Machine Learning_ (PMLR, 2019) pp. 242–252.
  * Allen-Zhu  _et al._ (2019b) Z. Allen-Zhu, Y. Li, and Y. Liang, Advances in neural information processing systems (2019b).
  * Jacot  _et al._ (2021) A. Jacot, F. Gabriel, and C. Hongler, in  _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ (2021) pp. 6–6.
  * Hardt  _et al._ (2018) M. Hardt, T. Ma, and B. Recht, Journal of Machine Learning Research 19, 1 (2018).
  * Kogan and Kaveh (1995) E. Kogan and M. Kaveh, Physical Review B 52, R3813 (1995).
  * Davidson and Szarek (2001) K. R. Davidson and S. J. Szarek, Handbook of the geometry of Banach spaces 1, 131 (2001).
  * Collins and Śniady (2006) B. Collins and P. Śniady, Communications in Mathematical Physics 264, 773 (2006).
  * Collins and Matsumoto (2009) B. Collins and S. Matsumoto, Journal of Mathematical Physics 50, 113516 (2009).

##  Appendix A Proof of lemmas

This proof requires a basic integration formula with respect to the Haar
measure over the orthogonal matrices. Given that $O\in\mathbb{R}^{n\times n}$
is an orthogonal matrix drawn randomly from the Haar measure, this integration
formula allows us to express $\text{E}(O_{i_{1},j_{1}}O_{i_{2},j_{2}}\dots
O_{i_{2k},j_{2k}})$ in terms of the orthogonal Wein-garten function Collins
and Śniady (2006); Collins and Matsumoto (2009). This function is difficult to
evaluate in closed form for a general $k$, but for my purposes $k=2$ will
suffice. For completeness, I provide this integration formula, and specialize
it to $k=2$ and then provide a proof of proposition 2(b).

######  Definition 7 (Pairing)

For $n\in\mathbb{N}$, denoted by $\mathcal{P}_{2n}$, is an unordered tuple of
$n$ unordered tuples with two elements,
$((i_{1},j_{1}),(i_{2},j_{2})\dots(i_{n},j_{n}))$ where all $i_{1},i_{2}\dots
i_{n},j_{1},j_{2}\dots j_{n}$ are distinct and $\in[2n]$. The set of all
pairings over $[2n]$ will be denoted by $\mathcal{P}_{2n}$.

Remarks:

  * •

It is important to emphasize the simply reordering the tuples in a pairing, or
the the two elements inside the tuple, does not generate a different pairing.
For instance, the pairing $((1,2),(3,4),(5,6))$ over $[6]$ is the same as the
pairing $((3,4),(2,1),(6,5))$.

  * •

As an explicit and important example for the following calculations, the set
$\mathcal{P}_{4}$ has three distinct elements, $((1,2),(3,4))$,
$((1,3),(2,4))$, $((1,4),(2,3))$.

######  Definition 8 (Pairing delta function $\Delta^{p}_{i_{1},i_{2}\dots
i_{2n}}$)

Given a pairing
$p=((k_{1},r_{1}),(k_{2},r_{2})\dots(k_{n},r_{n}))\in\mathcal{P}_{2n}$, and
indices $i_{1},i_{2}\dots i_{2n}$ from some set $\mathcal{I}$, then

$\Delta^{p}_{i_{1},i_{2}\dots
i_{2n}}=\prod_{s=1}^{n}\delta_{i_{k_{s}},i_{r_{s}}},$

where $\delta_{i,j}=1$ if $i=j$ and $0$ if $i\neq j$ is the Kronecker delta
function.

######  Definition 9 (Loop function $\textnormal{loop}(p_{1},p_{2})$)

Let $p_{1},p_{2}\in\mathcal{P}_{2k}$ be two pairings. Construct a graph with
vertices $\\{1,2,3\dots 2k\\}$ with edges on all the pairings in $p_{1}$ or
$p_{2}$, then $\textnormal{loop}(p_{1},p_{2})$ is the number of connected
components in the graph.

######  Definition 10 (Orthogonal wein-garten function
$\textnormal{Wg}_{k}^{O(d)}(p_{1},p_{2})$)

Given $\mathcal{P}_{2k}=\\{p_{1},p_{2}\dots\\}$, let
$G_{k}^{d}\in\mathbb{R}^{|\mathcal{P}_{2k}|\times|\mathcal{P}_{2k}|}$ be a
matrix with elements $(G_{k}^{d})_{i,j}=d^{\textnormal{loop}(p_{i},p_{j})}$,
then the $\textnormal{Wg}_{k}^{O(d)}(p_{i},p_{j})=[(G_{k}^{d})^{-1}]_{i,j}$.

###### Lemma 11

For $d>1$ and for $p_{1},p_{2}\in\mathcal{P}_{4}$,

$\displaystyle\textnormal{Wg}_{2}^{O(d)}(p_{1},p_{2})=\begin{cases}\frac{1}{d^{2}-1}&\text{
if }p_{1}=p_{2},\\\ -\frac{1}{d(d^{2}-1)}&\text{ if }p_{1}\neq
p_{2}.\end{cases}$

_Proof_ : Explicitly,
$\mathcal{P}_{4}=\\{p_{1}:=((1,2),(3,4)),p_{2}:=((1,3),(2,4)),p_{3}:=((1,4),(2,3))\\}$.
I can now calculate the loop function, and it follows that
$\text{loop}(p_{i},p_{j})=2$ if $i=j$ else $1$ and thus

$G_{2}^{d}=\begin{bmatrix}d^{2}&d&d\\\ d&d^{2}&d\\\
d&d&d^{2}\end{bmatrix}\implies\big{(}G_{2}^{d}\big{)}^{-1}=\frac{1}{d^{2}-1}\begin{bmatrix}1&-1/d&-1/d\\\
-1/d&1&-1/d\\\ -1/d&-1/d&1\end{bmatrix}.$

Identifying the weingarten function with these matrix elements, the lemma
statement follows $\square$.

######  Lemma 12 (Integration w.r.t. Haar measure over $O(d)$ from Ref.
Collins and Matsumoto (2009))

Let $R$ be a matrix drawn uniformly at random from the Haar measure over the
set of $d\times d$ orthogonal matrices, then for all $k\in\mathbb{N}$,

$\text{E}\big{[}R_{i_{1},j_{1}}R_{i_{2},j_{2}},R_{i_{3},j_{3}}\dots
R_{i_{2k},j_{2k}}\big{]}=\sum_{p_{1},p_{2}\in\mathcal{P}_{2k}}\textnormal{Wg}^{O(d)}_{k}(p_{1},p_{2})\Delta^{p_{1}}_{i_{1},i_{2}\dots
i_{2k}}\Delta^{p_{2}}_{j_{1},j_{2}\dots j_{2k}}.$

Lemma 8 (Restated) _Let $M=R\
\textnormal{diag}(v)Q^{\text{T}}\in\mathbb{R}^{d\times d}$, where $R,Q$ are
orthogonal matrices drawn independently from the Haar random measure over the
set of $d\times d$ orthogonal matrices, and $b,c\in\mathbb{R}^{d}$, then_

$\textnormal{E}\big{(}(c^{\textnormal{T}}Mb)^{2}\big{)}=\frac{1}{d^{2}}\|{v}\|^{2}\|{b}\|^{2}\|{c}\|^{2}.$

_Proof_ : Explicitly writing out the expectation value,

$\textnormal{E}((c^{\text{T}}Mb)^{2})=\textnormal{E}\bigg{(}\sum_{i,j,k\in[d]^{2}}\prod_{l=1}^{2}v_{k_{l}}c_{i_{l}}b_{j_{l}}R_{i_{l},k_{l}}Q_{j_{l},k_{2}}\bigg{)}=\sum_{i,j,k\in[d]^{2}}\bigg{(}\prod_{l=1}^{2}v_{k_{l}}c_{i_{l}}b_{j_{l}}\bigg{)}\textnormal{E}\big{(}R_{i_{1},k_{1}}R_{i_{2},k_{2}}\big{)}\text{E}\big{(}Q_{j_{1},k_{1}}Q_{j_{2},k_{2}}\big{)}.$

From lemma 12, it follows that

$\textnormal{E}(R_{i_{1},k_{1}}R_{i_{2},k_{2}})=\frac{1}{d}\delta_{i_{1},i_{2}}\delta_{k_{1},k_{2}},\text{
and
}\textnormal{E}(Q_{j_{1},k_{1}}Q_{j_{2},k_{2}})=\frac{1}{d}\delta_{j_{1},j_{2}}\delta_{k_{1},k_{2}},$

and consequently,

$\text{E}\big{(}(c^{\text{T}}Mb)^{2}\big{)}=\frac{1}{d^{2}}\|{v}\|^{2}\|{b}\|^{2}\|{c}\|^{2}.$

and thus the lemma statement follows $\square$.

Lemma 9 (Restated)_Let $M=R\
\textnormal{diag}(v)Q^{\text{T}}\in\mathbb{R}^{d\times d}$, where $R,Q$ are
orthogonal matrices drawn independently from the Haar random measure over the
set of $d\times d$ orthogonal matrices, and $b,c\in\mathbb{R}^{d}$, then_

$\textnormal{E}\big{(}\|{Mb\odot
M^{\textnormal{T}}c}\|^{2}\big{)}=\|{b}\|^{2}\|{c}\|^{2}\|{v}\|^{4}\Omega(d^{-3}).$

_Proof_ : It is easily follows that

$\displaystyle\textnormal{E}\big{(}\|{Mb\odot
M^{\textnormal{T}}c}\|^{2}\big{)}=\sum_{i\in[n]}\sum_{j,k,l,m\in[n]^{2}}v_{j_{1}}v_{j_{2}}v_{k_{1}}v_{k_{2}}\text{E}\big{(}R_{i,j_{1}}R_{i,j_{2}}R_{l_{1},k_{1}}R_{l_{2},k_{2}}\big{)}\text{E}\big{(}Q_{m_{1},j_{1}}Q_{m_{2},j_{2}}Q_{i,k_{1}}Q_{i,k_{2}}\big{)}b_{m_{1}}b_{m_{2}}c_{l_{1}}c_{l_{2}}.$

From lemma 12, it follows that

$\displaystyle\text{E}\big{(}R_{i,j_{1}}R_{i,j_{2}}R_{l_{1},k_{1}}R_{l_{2},k_{2}}\big{)}=\sum_{p_{1},p_{2}\in\mathcal{P}_{4}}\text{Wg}^{O(d)}_{4}(p_{1},p_{2})\Delta^{p_{1}}_{i,i,l_{1},l_{2}}\Delta^{p_{2}}_{j_{1},j_{2},k_{1},k_{2}},$
$\displaystyle\text{E}\big{(}Q_{m_{1},j_{1}}Q_{m_{2},j_{2}}Q_{i,k_{1}}Q_{i,k_{2}}\big{)}=\sum_{p_{1}^{\prime},p_{2}^{\prime}\in\mathcal{P}_{4}}\text{Wg}^{O(d)}_{4}(p_{1}^{\prime},p_{2}^{\prime})\Delta^{p_{1}^{\prime}}_{m_{1},m_{2},i,i}\Delta^{p_{2}^{\prime}}_{k_{1},k_{2},j_{1},j_{2}}.$

I first evaluate the summation

$\displaystyle
f(p_{1},p_{1}^{\prime},v):=\sum_{j,k\in[d]^{2}}\sum_{p_{2},p_{2}^{\prime}\in\mathcal{P}_{4}}v_{j_{1}}v_{j_{2}}v_{k_{1}}v_{k_{2}}\text{Wg}_{4}^{O(d)}(p_{1},p_{2})\text{Wg}_{4}^{O(d)}(p_{1}^{\prime},p_{2}^{\prime})\Delta^{p_{2}}_{j_{1},j_{2},k_{1},k_{2}}\Delta^{p_{2}^{\prime}}_{j_{1},j_{2},k_{1},k_{2}}.$

I note from definition 8

$\sum_{j,k\in[d]^{2}}v_{j_{1}}v_{j_{2}}v_{k_{1}}v_{k_{2}}\Delta^{p_{2}}_{j_{1},j_{2},k_{1},k_{2}}\Delta^{p_{2}^{\prime}}_{k_{1},k_{2},j_{1},j_{2}}=\begin{cases}\|{v}\|_{4}^{4}&\text{
if }p_{2}\neq p_{2}^{\prime},\\\ \|{v}\|^{4}&\text{ if
}p_{2}=p_{2}^{\prime}.\end{cases}$

Consequently, it follows that

$\displaystyle
f(p_{1},p_{1}^{\prime},v)=\big{(}\|{v}\|^{4}-\|{v}\|_{4}^{4}\big{)}\sum_{p\in\mathcal{P}_{4}}\text{Wg}_{4}^{O(d)}(p_{1},p)\text{Wg}_{4}^{O(d)}(p_{1}^{\prime},p)+\|{v}\|_{4}^{4}\bigg{(}\sum_{p\in\mathcal{P}_{4}}\text{Wg}_{4}^{O(d)}(p_{1},p)\bigg{)}\bigg{(}\sum_{p\in\mathcal{P}_{4}}\text{Wg}_{4}^{O(d)}(p_{1}^{\prime},p)\bigg{)}.$

Using the explicit formula for the Weingarten functions from from lemma 11, it
follows that

$\chi(p_{1},p_{1}^{\prime},v)=\begin{cases}\chi_{\text{eq}}(v)&\text{ if
}p_{1}=p_{1}^{\prime},\\\ \chi_{\text{ueq}}(v)&\text{ if }p_{1}\neq
p_{1}^{\prime}.\end{cases},$

where

$\displaystyle\chi_{\text{eq}}(v)=\frac{d^{2}+2}{d^{2}(d^{2}-1)^{2}}\|{v}\|^{4}-\frac{4d-2}{d^{2}(d^{2}-1)^{2}}\|{v}\|_{4}^{4},$
$\displaystyle\chi_{\text{ueq}}(v)=-\frac{2d-1}{d^{2}(d^{2}-1)^{2}}\|{v}\|^{4}+\frac{d^{2}-2d+3}{d^{2}(d^{2}-1)^{2}}\|{v}\|_{4}^{4}$

I note that

$\displaystyle\text{E}\big{(}\|{Mb\odot M^{\text{T}}c}\|^{2}\big{)}$
$\displaystyle=\sum_{p_{1},p_{1}^{\prime}\in\mathcal{P}_{4}}\sum_{\begin{subarray}{c}i\in[n],\\\
l,m\in[n]^{2}\end{subarray}}b_{m_{1}}b_{m_{2}}c_{l_{1}}c_{l_{2}}\Delta^{p_{1}}_{i,i,l_{1},l_{2}}\Delta^{p_{1}^{\prime}}_{m_{1},m_{2},i,i}\chi(p_{1},p_{1}^{\prime},v)$
$\displaystyle=\chi_{\text{eq}}(v)\big{(}d\|{b}\|^{2}\|{c}\|^{2}+2\|{b\odot
c}\|^{2}\big{)}+6\chi_{\text{ueq}}(v)\|{b}\|^{2}\|{c}\|^{2}.$

Using the expressions for $\chi_{\text{eq}}(v),\chi_{\text{uneq}}(v)$, we
prove the lemma statement. $\square$.