## 4 Proposed Solution
### Main Characteristics of the Multi-Agent Gradient Descent Algorithm (MAGD)
Given \(N_{t}\) agents at iteration \(t\), the per-iteration complexity is:

\[T(t)=O(d\cdot N_{t}). \tag{5}\]

For a single agent \((N_{t}=1,\text{ for all iterations})\) over \(t_{\text{max}}\) iterations, the total complexity is:

\[\sum_{t=0}^{t_{\text{max}}-1}T(t)=t_{\text{max}}\cdot T(t)=t_{\text{max}}\cdot d. \tag{6}\]

For a constant number of agents \(N\) across all iterations:

\[\sum_{t=0}^{t_{\text{max}}-1}T(t)=t_{\text{max}}\cdot T(t)=t_{\text{max}}\cdot d \cdot N. \tag{7}\]

In MAGD, the number of agents \(N_{t}\) at iteration \(t\) decreases exponentially as \(t\to t_{\text{max}}\). Agents with costs worse than the mean are removed after every \(T_{\text{red}}\) iterations (convergence-based reduction is omitted because it cannot be reliably expected.). Assuming a fixed reduction factor \(r\in(0,1]\), representing the fraction of agents retained, the number of agents after each reduction step can be approximated as:

\[N_{k}= \begin{cases}N_{0}\cdot r^{k},&\text{if }N_{k}>1,\\ 1,&\text{otherwise},\end{cases}  \tag{8}\]

where \(k\in\{0,1,2,\dots,\lfloor t_{\text{max}}/T_{\text{red}}\rfloor\}\) corresponds to reduction steps. For each interval \(t\in[k\cdot T_{\text{red}},(k+1)\cdot T_{\text{red}})\), the number of agents \(N_{k}\) remains constant. The total duration per interval is:

\[T_{k}=T_{\text{red}}\cdot d\cdot N_{k}. \tag{9}\]

With \(\lfloor t_{\text{max}}/T_{\text{red}}\rfloor\) intervals, the total time complexity is:

\[\sum_{k=0}^{\lfloor t_{\text{max}}/T_{\text{red}}\rfloor-1}T_{k}=d\cdot T_{ \text{red}}\cdot\sum_{k=0}^{\lfloor t_{\text{max}}/T_{\text{red}}\rfloor-1}N _{k}. \tag{10}\]Substituting \(N_{k}\) from Equation (8) into Equation (10), we obtain:

\[T\approx d\cdot T_{\text{red}}\cdot\sum_{k=0}^{\lfloor t_{\max}/T_{\text{red}} \rfloor-1}N_{0}\cdot r^{k}. \tag{11}\]

The summation \(\sum_{k=0}^{\lfloor t_{\max}/T_{\text{red}}\rfloor-1}N_{0}\cdot r^{k}\) is a geometric series:

\[\sum_{k=0}^{\lfloor t_{\max}/T_{\text{red}}\rfloor-1}N_{0}\cdot r^{k}= \begin{cases} N_{0}\cdot\frac{1-r^{\lfloor t_{\max}/T_{\text{red}}\rfloor}}{1-r},&r<1,\\ N_{0}\cdot\lfloor t_{\max}/T_{\text{red}}\rfloor,&r=1.\end{cases}  \tag{12}\]

Assuming \(r<1\), the series converges to:

\[\sum_{k=0}^{\lfloor t_{\max}/T_{\text{red}}\rfloor-1}N_{0}\cdot r^{k}=N_{0} \cdot\frac{1-r^{\lfloor t_{\max}/T_{\text{red}}\rfloor}}{1-r}. \tag{13}\]

Substituting Equation (13) into Equation (11), the final time complexity is:

\[O(d,N_{0},t_{\max})=d\cdot T_{\text{red}}\cdot N_{0}\cdot\frac{1-r^{\lfloor t _{\max}/T_{\text{red}}\rfloor}}{1-r}. \tag{14}\]

For \(t_{\max}\gg T_{\text{red}}\), where \(r^{\lfloor t_{\max}/T_{\text{red}}\rfloor}\to 0\), this simplifies to:

\[O(d,N_{0},t_{\max})=d\cdot T_{\text{red}}\cdot N_{0}\cdot\frac{1}{1-r}. \tag{15}\]

Assuming \(N_{0}\gg\frac{1}{1-r}\) the time complexity further simplifies to:

\[O(d,N_{0},t_{\max})=d\cdot t_{\max}\cdot N_{0}. \tag{16}\]

Because \(T_{red}=\rho\cdot t_{max}\), where \(\rho\in(0,1]\). When \(t_{\max}\gg N_{0}\), or \(d\gg N_{0}\), the time complexity becomes:

\[O(d,t_{\max})=d\cdot t_{\max}. \tag{17}\]

A comparison of (6) and (17) reveals that, as \(t_{\max}\gg N_{0}\), or \(d\gg N_{0}\), the time complexity of MAGD converges to that of a single-agent algorithm. #### 4.2.2 Space Complexity

Each agent requires \(O(d)\) space to store its position, gradient, moments, and auxiliary variables. At iteration \(t\), the total space complexity is:

\[\text{Space}(d,N_{t})=O(d\cdot N_{t}). \tag{18}\]

For the maximum number of agents \(N_{0}\), the maximum space complexity is:

\[\text{Space}_{\max}(d,N_{0})=O(d\cdot N_{0}). \tag{19}\]

From Equation (8), as \(t\to t_{\max}\), \(N_{t}\to 1\). Therefore, the final space complexity can be expressed as:

\[\text{Space}(d)=O(d). \tag{20}\]

Exponential Decay of Storage

While the space complexity of MAGD is \(\text{Space}(d)=O(d)\), indicating no significant penalty for larger initial agent counts \(N_{0}\) in terms of Big-O notation, a practical penalty exists.