Randomized Sparse Matrix Compression for Large-Scale Constrained Optimization in Cancer Radiotherapy
Authors: Shima Adeli
Mojtaba Tefagh
Gourav Jhanwar
Masoud Zarepisheh
Venue: NeurIPS 2024 poster (2024)
Keywords: Sparsification
Cancer Radiotherapy
Optimization
Randomization
Sketching
Primary area: machine_learning_for_healthcare
TL;DR: This paper presents a novel algorithm for generating a randomized sparse sketch of a large matrix, with novel application in solving the large-scale optimization problems arising in cancer radiotherapy.

Abstract: Radiation therapy, treating over half of all cancer patients, involves using specialized machines to direct high-energy beams at tumors, aiming to damage cancer cells while minimizing harm to nearby healthy tissues. Customizing the shape and intensity of radiation beams for each patient leads to solving large-scale constrained optimization problems that need to be solved within tight clinical time-frame. At the core of these challenges is a large matrix that is commonly sparsified for computational efficiency by neglecting small elements. Such a crude approximation can degrade the quality of treatment, potentially causing unnecessary radiation exposure to healthy tissues—this may lead to significant radiation-induced side effects—or delivering inadequate radiation to the tumor, which is crucial for effective tumor treatment. In this work, we demonstrate, for the first time, that randomized sketch tools can effectively sparsify this matrix without sacrificing treatment quality. We also develop a novel randomized sketch method with desirable theoretical guarantees that outperforms existing techniques in practical application. Beyond developing a novel randomized sketch method, this work emphasizes the potential of harnessing scientific computing tools, crucial in today's big data analysis, to tackle computationally intensive challenges in healthcare. The application of these tools could have a profound impact on the lives of numerous cancer patients. Code and sample data available at https://github.com/PortPy-Project/CompressRTP

Randomized Sparse Matrix Compression for Large-Scale Constrained Optimization in Cancer
Radiotherapy
Shima Adeli'
Mojtaba Tefagh Gourav Jhanwar"
Masoud Zarepisheh
Sharif University of Technology
University of Edinburgh
Memorial Sloan Kettering Cancer Center
Abstract
Radiation therapy, treating over half of all cancer patients, involves using special- ized machines to direct high-energy beams at tumors, aiming to damage cancer cells while minimizing harm to nearby healthy tissues. Customizing the shape and intensity of radiation beams for each patient leads to solving large-scale constrained optimization problems that need to be solved within tight clinical time-frame. At the core of these challenges a large matrix that commonly sparsified for com- putational efficiency by neglecting small elements. Such a crude approximation can degrade the quality of treatment, potentially causing unnecessary radiation exposure healthy tissues-tie this may lead to significant radiation-inducet side ef- fects-or delivering inadequate radiation to the tumor, which crucial for effective tumor treatment. In this work, demonstrate, for the first time, that randomized sketch tools can effectively sparsify this matrix without sacrificing treatment qual- ity. We also develop novel randomized sketch method with desirable theoretical guarantees that outperforms existing techniques in practical application. Beyond developing novel randomized sketch method, this work emphasizes the potential harnessing scientific computing tools, crucial in today's big data analysis, to tackle computationally intensive challenges in healthcare. The application of these tools could have a profound impact on the lives of numerous cancer patients. Code and sample data available at https://github.com//Poo Proppo/ooPPypppeee//oornessrTTT
Introduction
In 2020, an estimated 18.1 million new cancer cases and about 9.9 million cancer-related deaths reported globally [22]. Radiation therapy (RT) integral cancer treatment, utilized in approximately half of all cases, either alone or in combination with other treatments like surgery or chemotherapy (22). RT involves using specialized machines to direct high-energy radiation beams at tumors, with the primary goal of destroying cancer cells while minimizing damage to healthy tissues. This process requires precise optimization of machine parameters, such as beam shapes and angles, tailored to each patient's unique anatomy. It involves solving large-scale, constrained, non-linear optimization problems swiftly within clinical time constraints 22 [9] The urgency of this task is heightened in modern online adaptive radiotherapy techniques, where rapid solution is essential since patients remain immobilized on the treatment couch during preparation [[2]. Delays not only compromise patient comfort but can also affect treatment outcomes, as any rapid anatomical changes (e.g., bladder filling in prostate cancer) can render treatment plans based on initial anatomy sub-optimal. Thus, quickly solving these optimization problems is crucial.
"Conrspondence to mtefagh@sharif.cmmm edu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

We briefly describe the mathematical modeling of radiotherapy treatment (see [22 19 for more details). The patient's body is discretized into small three-dimensional voxels (indexed by i 1...., m.), and each radiation beam is discretized into small two-dimensional beamlets (indexed by j = -,...., n)) The radiation dose delivered to each voxel from each beamlet j with unit intensity is precalculated and represented by aij, forming matrix A 4 commonly referred to as the dose inftuence matrix. This matrix is typically large, containing about 100,000 to 500,000 rows corresponding to the patient's s voxels, and 1,000 to 20,000 columns representing the beamlets of the radiotherapy machine [T.] Our objective is to optimize the intensities of the beamlets, denoted by æ, in order to achieve desired radiation dose, Ar, that is delivered to the patient's body. For the tumor voxels, we aim to achieve a radiation dose that approximates the dose prescribed by a physician while for healthy voxels we aim to minimize the radiation dose much possible. The optimization problem can be described in the following general form:
minimize subject to
(A(A)) + f1(
g(Ax) < 0
h(x) S.
where, fo(Az) measures the quality and 'goodness' of the radiation dose Ar, (x) assesses the quality of the beamlet intensities. The functions and h represent constraints on the dose received by the voxels and the intensities of the beamlets, respectively. Various formulations for these functions have been suggested in existing research [17]; however, the following quadratic optimization problem has arguably been the most commonly used formulation [2219]
minimize subject to
EvE3 Eier, (w] max(A2x 002 + w" max(d" - A22, + ||
A S d'aar Vs E 8,i L, (Mean(A')) S deaan Vs 5 x2 0,
where, S represents the set of structures (i.e., organs, tumors), including tumor and healthy structures, and La represents the set of voxels belonging to structure s. The first term in the objective function is two-sided quadratic function penalizing the radiation overdose/underrdos with the penalty weight wi /w", where the radiation overdose/underdosee is defined as a delivered radiation dose, A xx exceeding/below the prescribed dose, d", for each structure & E 5. For tumor-affiliated structures, the prescribed dose is given by radiation oncologist. For healthy structures, the prescribed dose is zero, d= = 0, and there is no underdose penalty, w = 0. The second term in the objective function, fi ||P=|]2, aims to penalize variations in intensities across neighboring beamlets to promote smoothness in beamlet intensities for enhanced radiation delivery (each row of matrix P has value of and -1 for two neighboring beamlets). The first/second set of constraints impose maximum/mean dose constraints to satisfy the maximum/mean dose limits defined by a clinical protocol for each structure E S, and the last constraint is physical non-negativity constraint on the beamlet intensities. The overdosecundeeross penalty weights w /w" need to be adjusted for each patient and various techniques have been developed to automate this process (see [2] and references therein).
We will use the second formulation (Eq. 2 for our experiments in this study. However, regardless of the specific functions chosen in Problem 1 and the technique used to adjust the problem hyper- parameters, the size and structure of matrix A are crucial in determining the computational intensity of the problem. Considering that these large-scale, non-linear, constrained optimization problems often solved using the interior-poin method with cubic computational complexity, the computational time can increase significantly with the size and density of non-zero elements in matrix A. Therefore. matrix sketching could be a compelling choice to improve the computational complexity of these problems. There has been a body of research employing matrix sketching, often using transformation matrix S, resulting in SA with a reduced number of rows, to improve the computational efficiency of the least-squares optimization problems commonly arising in machine learning applications [4 16 21]. However, these sketching techniques cannot be used where matrix A is also involved in the constraints, as is the case radiotherapy applications. Reducing the number of rows would prevent direct access to Az, which is crucial for evaluating Az) < 0 in Problem [ Thus, we explore the potential of using matrix sparsification, a specific form of matrix sketching, to substitute the dose influence matrix A with sparse matrix S to improve the computational efficiency of our

---

radiotherapy constrained optimization problems, In fact, a very simple form of matrix sparsification is currently being used in practice, where all small elements of the matrix below a predefined threshold. typically less than 0.01 x max(A), are discarded [10] This method, which we will refer to as the "naive" approach, is clearly not the most optimal solution and may adversely affect the quality of the treatment. The primary concern with this approach is that the radiation dose calculated and optimized in Problem I Juiing the modified matrix A may not accurately reflect the actual dose received by the patient. This discrepancy arises from the inherent inaccuracies introduced by the truncation of matrix A, which could potentially lead to sub-optimal treatment outcomes.
In this study, we demonstrate that using matrix sparsification techniques, primarily developed by the machine learning community, we can enjoy the computational efficiency of working with sparse matrices and still being able to solve constrained optimization problems within the clinical timeframe, without significantly compromising the integrity of the original problem that could potentially degrade the treatment quality. Matrix sparsification techniques carefully sample and scale the elements of the original dense matrix A to create a sparse sketch matrix S that minimizes || S112. Prior research predominantly utilized matrix sparsification for applications such as low-rank approximation and principal component analysis (PCA) 2 This study uniquely demonstrates the utility of matrix sparsification for efficiently addressing large-scale, constrained, nonlinear optimization challenges within constrained timeframes. We demonstrate that applying a randomized sketch to the influence matrix A in radiotherapy optimization significantly outperforms the current naive sparsification approach. To the best of our knowledge, this is the first application of matrix sparsification with a publicly available benchmark dataset, encouraging further research in this direction. Furthermore, have developed a novel randomized sketching algorithm that exhibits superior performance compared to existing techniques and is supported by theoretical guarantees for its efficacy. As formally stated in Theorem 3.6 Lemma 3.7 and Theorem 3.9 the proposed algorithm ensures a minimal impact on the constraints, objective function and the optimal points of the original optimization Problem 2
2 Related Work
In matrix sparsification, we typically aim for an unbiased approximation of matrix A by another matrix S such that A - S112 S T for a given 7 > O, while minimizing the number of nonzero entries 15 The &g norm of the difference between A and S serves as a measure of this error, a choice that has been justified in the literature (2) for various applications. The sparsification techniques proposed in the literature fall into two categories. The first involves randomly scaling each matrix entry independently. Specifically, for an entry a.y it is scaled to a:y/Pij with probability Piy. or set to zero otherwise I x 15). This process increases the magnitude of certain matrix entries and zeros out others, resulting in sparse matrix. Importantly, the resulting matrix serves as an unbiased estimator of the original matrix, with its entries acting as independent random variables. The probability typically follows the formula Pij cf(ar)). where e >> is universal constant. This method, first introduced by Achlioptas and McSherry (I, involves scaling each entry asj to ag//s, with probability Piy = cafy; otherwise, the entry is set to zero. This technique, referred to as fg scaling, laid a foundational basis in the domain of matrix sparsification. However, Achlioptas and McSherry [ 's approach faced limitations in theoretical guarantees and required a significant number of non-zero entries to achieve a satisfactory & norm bound. Additionally, scaling small entries could disproportionately inflate values in the resulting matrix. Building upon this, Arora et al. 3 introduced a variation focused on deterninistically retaining the largest entries in the matrix while randomly scaling the smaller ones. During the scaling phase, each matrix entry is scaled to az// with probability p= clazyl. set to zero otherwise. This method is fast in practice as it requires only a single pass over all the non-zero entries and Arora et al. [3] demonstrated that their method outperforms Achlioptas and McSherry (1 approach. However, this approach substitutes all small entrics, which are not reduced to zero, with a constant (c or -c). This could significantly affect its performance, especially when the matrix undergoes extensive sparsification.
in S 2 2
8
The second category of sparsification techniques, introduced later, involves independently sampling from the entries of A using a probability distribution p. Each sample generates a matrix filled with zeroes, except for the sampled entry. Subsequently, 8 samples are collected, and their average forms a sparse approximation. Contrary to the first approach, the entries of the resulting matrix S are not independent. Instead, S is formed by summing independent random matrices. To ensure that the resulting matrix is an unbiased estimator of A, the sampled matrix's 's entry should be at/Pit, where
3

---

Piy is derived from the probability distribution In this context, the choice of probability distribution p is critical. Drineas and Zouzias 77] introduced a technique where Ptj is proportional to az termed lg sampling, and used Bernstein inequality (20] to calculate the number of samples needed to achieve a desired accuracy. Later, Achlioptas et al. (2] introduced near-optimal probability distribution under specific conditions. Additionally, Braverman et al. developed a near-optimal method specifically
designed for numerically sparse matrices (this method belongs to the first category). While the theoretical bounds of this method closely align with those of Achlioptas et al. [2), the approach by Braverman et al. [4] is applicable to all matrices.
The primary issue with the second category of techniques is the increase in the required number of non-zero elements in the sparse matrix, which grows in proportion to the inverse square of the error, 1/72, unlike the T/T growth rate seen in the first category. This is especially problematic given that the interior point methods typically used to solve Problem [ have cubic computational complexity, which results in a cubic increase in processing time with the size of the input data. However, the second category may be preferable in applications when data is only accessible in a streaming manner. The first category necessitates access to the complete dataset. In this study, we assume that the matrix A is precomputed a -nte-intensive process that often takes as long as solving the optimization problems themselves. Theoretically, these matrices could be computed on a row-by-row basis [6], allowing the sparsification algorithm to operate concurrently, provided it can handle streaming data. Our proposed hybrid approach can, in principle, be used in a streaming manner (2)
Notations. Let a.j denote the element in the i-the row and j-th column of matrix A, and let nnz(AA) denote the number of non-zero entries in A. For matrix A. we consider the entry-wise l norm, defined as || = Σ ΣØ=1 [0:yl. and the spectral norm defined as || = |ax]]=] || Arllg Additionally, introduce A(e) E Rm=x a matrix with all zero entries except for the i-th row, which remains identical to the i-th row of A. Finally, for a vector a, we define its numerical sparsity as ns(a) = min 2 0: : ||al], I vT |||]|p] and let (s(A) denote the maximum numerical sparsity of its rows and columns.
3 Algorithm Description
In this study, we introduce an algorithm that matches the theoretical requirements of the first category for the number of non-zero elements (i.e., the growth of the non-zero elements proportional to 1/T), while outperforming existing techniques in practical experiments. Our findings reveal that this approach markedly enhances the accuracy of sparse sketches for large matrices that appear in the context of cancer radiotherapy optimization. This method can be seen as hybrid, combining advantages from both categories. We deterministically retain the largest entries, akin to the strategy suggested by Arora et al. 3 This method particularly relevant for our application, as the matrices appcaring in radiotherapy exhibit distribution closely resembling exponential curve. Consequently, the number of elements exceeding any given threshold remains significantly small relative to the total matrix size. This phenomenon occurs because radiation delivered from each individual beamlet (corresponding to a matrix column) directly deposits radiation to a limited number of voxels (corresponding matrix rows), resulting in few large matrix entries. However, radiation also scatters, delivering smaller doses to additional voxels throughout the body, leading to small values across all voxels. In contrast the approach by Arora al. (3), which involves substituting all minor non-zeroed-out entries with tt., our strategy seeks to counterbalance the effects of sparsification on row-by-row basis by redistributing the sum of all minor elements within that row. This method is designed to preserve the integrity of each row, taking into consideration the diverse distribution patterns across the matrix's 's rows. Specifically, in our application, rows corresponding to tumor voxels often exhibit higher values due to their position in the direct path ("cross-fire" of radiation, receiving more substantial doses. Applying a uniform value for all substituted entities, in this context, results in more pronounced approximation for tumor voxels, potentially compromising the accuracy of the final dose delivered to the tumor, as our results will demonstrate. After isolating the larger elements, we apply & sampling to the remaining entries in each row independently. This process generates a random matrix, essentially the aggregate of several random matrices, which more closely aligns with the practices of the second category. However, unlike conventional sampling methods (e.g., 77). our technique automatically identifies the optimal number of samples for each row, consistently less than the total number of columns, climinating the necessity for tuning sampling parameters.

---

Our method is nearly as fast as that proposed by Arora et al. B but provides superior accuracy, particularly beneficial when high levels of sparsification needed. This is crucial in our application. where approximately 96-98% sparsification is required to solve the large-scale non-linear constraint optimization problems within feasible clinical timeframe. Our algorithm, described in Algorithm / is named the Randomized Minor-value Rectification (RMR), as it preserves the larger values while rectifying a random selection of smaller values to offset those that have been zeroed out.
Algorithm 1 Randomized Minor value Rectification (RMR)
input E I I= The matrix to be sparsified, e: The threshold for sparsification
output S: The sparsified matrix
S = deep copy of
for each row in 21.,...., m do
T; = [j < [0:] S
86j 0 for all
Σ, Σ jen lais
k; = /c/c]
for = 1,2, ......... k; do
randomly select j T. (with probability proportional to la:y] and update Sij + Sef + E,/k; x sign(a;s)
end for end for
Lemma 3.1. For any matrix A E mx the number of samples taken by the RMR algorithu is bounded above by mnz(A).
The nnz(A (A) upper bound in the above lemma, which also applies to the algorithm proposed by Arora et al. [3]. may not seem interesting at first; however, the number of samples could be much larger than (nz( for other algorithms, as each entry of the matrix could be sampled multiple times. The following theorems provide the theoretical guarantees of the RMR algorithm (proof in Appendix A
In the remainder of this section, we assume that the sparse matrix S is obtained by applying Algorithm to A. Instead of solving the original optimization problem 2 directly, we substitute the dense matrix with the sparse matrix S, thereby formulating an approximated optimization problem that we refer to as the surrogate problem. Let z and zg denote arbitrary optimal points for the original and surrogate optimization problems, respectively.
Theorem 3.2 (Absolute forn error). Given mairix A E BRxx,, it can be shown that:
(a) The number of nonzero entries is less than m || /c.
(b) For any given T > 0, by setting
maxi
log mi-
3/2 max(mm,
it follows that PP [[[A- S11, 2 2 6. Corollary 3.3 (Absolute f--nrrm error). In Algorithm 7 by setting
MMmaxmm, n 1) log(mn n)
the resultant matrix S will contain no more than m + 4 4 max(m,x n log(m + n) [| /T nonzero entries, and we have [ S11, 2 r} S 1/(m + n).
Theorems 3,6 and 3.9 establish theoretical guarantees and provide bounds on the discrepancies between the original and surrogate optimization problems with respect their constraints and objective functions, respectively. In essence, applying the RMR algorithm to sparsify the matrix and subsequently solving the surrogate problem yields optrmoptimal solution the original problem.
Lemma 3.4 (Row-wise error). For every vector E IR", the probability that the absolute value of the i-th entry of the vector (A - S)x exceeds ce ||0||/ / is less than 2 exp(_c2/ + 2/2c/3)), i.c.
P {I((AA S)x)d 2 ||]||]] < exxp(-e² (4 2 2c/3)).
5

---

Note that the upper bound obtained from Lemma (3.4) is significantly tighter than the bound derived directly from Corollary (3.3). To understand this, consider the following inequality:
- S))d & (I - 2)xll2 - ||A - م|ا|||=1| < <4Vimax(ma n 1) log(m + n)]||arl22
with probability least 1 - 1/(m + n), as stated (3.3). However, we set c 5 5log(m + n), we achieve the same failure probability, but the upper bound on the enror becomes log(m + n)e[[z]]2. which is of a better order.
Lemma 3.5 (Feasibility gap). Let C E Rk be a normalized matrix where the n--ormm of each row is less than or equal to one, and assume that for an arbitrary x E IK", there exists u E IR. for which we have CSx S u. Then, with probability of 0.95, the maximum violation of any constraint in C.A I u is bounded above by (19 + 5 log m) m)el|zll2. Conversely, if C'Ar I u, then the maximum violation of any constraint in CSx S bounded above by (19 + 5 log mn)elaa122 with a probability of 0.95.
The feasible region of the optimization problem ( satisfies the assumptions of Lemma 3.5 leading to the following theorem.
Theorem 3.6 (Feasibility gap for Problem 2) An optimal point of the original problem, TA violates
each constraint of the surrogate problem by no more than (19 + log m)c[|x=112 with probability of at least 0.95. Conversely, an optimal point of the surrogate problem, æs, violates each constraint of the original problem by no more than (19 + 5 log m))e ||x with the same probability.
Lemma 3.7 (Objective function discrepancy). The absolute discrepancy between the objective functions of the original and surrogate problems does not exceed (fo(Ax) + m(1 + +e) ee)) (wf + w()) with a probability of at least 0.95, where (19 5 m)
Lemma 3.8. Suppose that for an x E IR satisfying the convex constraints h(x) S O, the maximum violation of any convex constraint 9: S 0 in the optimization problem ① is bounded above by 2 O, iee, gi(Ax)= S e. Additionally, assume there exists an interior point of the feasible set & E R that is strictly feasible by a margin of at least s > 0 for each constraint gi S O, i.e ((A)) S -8. Then,
there exists a feasible point & E Ie such that:
E (1===+++ 1|=l)
||0
all
Theorem 3.9 (Sub-optimality gap for Problem An optimal point of the surrogate problem, F,S, is near-optimal solution the original problem with probability of least 0.95, and the sub-optimality gap of (e)) where
e= =1119 + 5 log m)) max (1lr ([5sl12))
In other words, we have:
[o((Ar)) - (xs)) - [o(AA + O(e).
Remark 3.10. Note that the proof of Theorem (3.9) be generalized to any matrix approximation scheme with a bounded error norm for the general convex optimization problem ① given the key assumptions that the objective function Lipschitz continuous and that there exists a strictly feasible point with a lower bounded slackness for all approximated constraints. These assumptions are crucial. If the objective function is not Lipschitz continuous, the error in matrix approximation can significantly alter the value of the objective function, thereby drastically affecting the optimal point. Additionally, the assumption of Lemma (3.8) not satisfied and no interior point exists for the approximated constraints. the feasible set could be reduced to single point in extreme cases. Even with an arbitrarily small error approximating the constraints, the feasible set might vanish, rendering the approximated problem infeasible.
Now we conduct a comparative analysis of the performance of the RMR algorithm against the [2] and Braverman
algorithms proposed by Arora et al. [. Drineas and Zouzias 77), Achlioptas et al. 4 denoted as "AHK06", "DZ11", "AKL13", and "BKKS21" 1" respectively. Table presents the sparsity of the resulting matrix S for each considered method, adhering to the constraint
- S112 S
The computational time required to solve the constrained optimization Problem 2 is strongly correlated with the sparsity of the matrix, as also verified by our computational experiments (see Figure I). Therefore, we sparsity as a proxy for computational efficiency. Although the values

---

Table 1: Comparison of Theoretical Guarantees Across Various Algorithms.
Method
Number of non-zero elements
Failure Probability
AHK06 3
0 (vm m + || || /T)
exp(- + n))
D7
28(m n) log (v2 n)) || /72
1/(m n)
(log(n) E A /r2 + (lo((n) || /T) (os((m)ns( || / + (m) | /ns( //ns((A)/////
2
1/10
BKKS21
Not specified
RMR
m + 4 max.mmmmmmmmm.mmmmmm log(m + n) ||A||/ /T
1/(m + n)
in Table | are not directly comparable, for DZ11, AKL13, and BKKS21 the number non-zero elements scales inversely with the square of the error rate (i.e., +2). while for RMR and AHK06, is determined by the inverse of the error rate (i.e.. 1). As also confirmed by our computational experiments (Figure D. this makes RMR and AHK06 algorithms particularly beneficial at lower error rates, which is needed for our application. Furthermore, due to the dependence of the BKKS21 on the numerical sparsity of the matrix, and considering that the matrices we tested exhibit low numerical sparsity, this algorithm also performs well across various metrics. In terms of the runtime and computational complexity of the algorithms themselves, it mainly depends on the number of required samplings. For DZ11 and AKL13, the number of required samplings also depends on the error rate, while for AHK06, BKKS21, and RMR, the dependency is solely on nnz( ().. This also gives AHK06, BKKS21, and RMR an edge in runtime, particularly for small error rates, as confirmed by experiments in Figure
4 Experiments
Our objective is to illustrate that employing randomized sparse sketch of the large dose influence matrix in radiotherapy markedly surpasses the existing "naive" method used in practice, which simply sparsifies the matrix by neglecting all minor elements. Additionally, we demonstrate the superior performance of our RMR algorithm over the randomized sketch techniques introduced by Arora et al. 3 ("AHK06"), Drineas and Zouzias 7 ("DZ11"), Achlioptas et al. [2] ("AKL13") and Braverman et al. 4 ("BKKS2").
Our analysis utilized real-world data recently made publicly available through the open- source package PortPy [10]. We conducted experiments on data from 10 randomly selected lung patients, with detailed information provided in the Appendix (Table The dose influence matrices in PortPy were derived from an FDA-approved commercial treatment planning system, Varian Eclipse IM, using its Application Programming Interface (API). Further detailed information about the data can be found on PortPy's s GitHub page Furthermore, we conducted experiments using data from five prostate patients, which are not publicly available. The results of these experiments are included in the Appendix.
Dataset.
Experiment Settings. Due to the inherent randomness of all the algorithms, except the naive one, each experiment was repeated times to assess and report variations and the algorithms' robustness. Each algorithm has hyper-parameter threshold that determines the sparsity of the output matrix. To ensure a fair comparison, we ran each algorithm with various threshold values and compared the results based on different levels of sparsity in the output matrix (e.g.. runtime of algorithm I vs. algorithm 2 for sparsity levels x. y). The experiments were conducted on dual CPU system (Intel(R) Xeon(R) 6248 2.5GHz) running Windows 10 with 128 GB of RAM. For each patient, the optimization problem was solved using the penalty weights, w //w". recommended by the PortPy package [10) along with the maximum and mean dose constraints presented in Table 3 in Appendix. All optimization problems were modeled and solved using CVXPY and MOSEK 13] To report the optimality gap, we needed to solve the original optimization problems using the original matrix
A. However, we encountered limited memory errors on the PCC Consequently, we solved the original optimization problems on powerful high-performance computing (HPC) system with approximately
7

---

320 GB of memory, which was used exclusively to obtain the optimal solution FA for optimality gap comparisons.
Code availability. Our code, which includes implementations of all models and experiment config- urations, available at ohttt://gghhiilooommooooo/oooooc
4.1 Evaluation Metrics
The algorithms are compared using the following metrics:
Relative 6z-Norm Error. Defined as || 111-5112// ||A this metric, widely adopted in existing literature, indicates how closely the sparse matrix approximates the original matrix for a given level of sparsity with respect to the spectral norm.
Relative Optimally Gap. This metric quantifies the sub-optimality resulting from solving the approximated problem by measuring the relative difference between the optimal objective value of the original problem (solved on HPC) and the objective value of the original problem using the optimal solution the approximated problem. It is defined as ( (Ine))))((((Aa))+AA fo Jo(Aza)+h(za
Feasibility Gap. This metric measures how much the constraints of the original optimization problem (i.e., ((Az) I 0) are violated when solving the approximated problem. It is defined as ||max(g 0)ll2-
Relative Dose Discrepancy. This metric, which is particularly relevant in the context of radiother- apy applications, defined [AAg--S2 and quantifies the discrepancy between the radiation dose [ lla computed using the sparse optimization problem, Srs, and the actual dose received by the patient, Azs.
Runtime, This includes the runtime of the sparsification algorithms and the runtime of the con- strained optimization problems. It is worth noting that, in practice, the constrained optimization problem needs to be solved multiple times for each patient, depending on the technique used to adjust the hyper-paramete penalty weight.
Discrepancies in Dose Volume Histograms (DVH). DVH plots are two-dimensional graphs specific to radiotherapy applications and are reported in the Appendix (Figures [nd These plots, extensively used by clinicians, show how much radiation is delivered to different volumes of organs (e.g., 10 Gray is delivered to at least 30% of the esophagus). Discrepancies between these plots for Azg and Sxg are illustrated for different algorithms.
4.2 Results
Figure I proovies detailed comparisons with respect to the different levels of sparsity in the output sparse matrix for one patient. Additional comparisons for the remaining nine patients can be found in the Appendix (Figures to 6). The Naive algorithm excluded some of the plots due to its poor performance and significant deviation from other methods (impeding meaningful comparison of others). The incomplete range coverage in the plots for DZ1 I is due to this algorithm exceeding our predefined maximum time limit of 10 minutes for some of its threshold values. The standard deviation band is plotted for all metrics (over 5 runs), however, due to the robust performance of the algorithms, the bands are not visible except in the feasibility gap plot.
As demonstrated in Figure T (top-left plot), all randomized algorithms surpass the current naive approach in balancing accuracy and sparsity. Among these, AHK06, BKKS21, and RMR stand out, exhibiting superior performance. While AHK06 and BKKS21 marginally surpasses RMR in terms of the l norm, RMR significantly exceeds AHK06 and BKKS21 in terms of feasibility and optimality gaps as well as the dose discrepancy error. This further supported by reduced discrepancies among DVH plots reported in the Appendix (Figures Fnnd
In terms of computational efficiency, the naive approach unsurprisingly leads in speed due its simple implementation, with АHK06 following closely behind. However, the relatively longer runtime

---

2050
Reatve Eonorm droer 196
35
Relatve oadiaallyy qa0 193)
25
20
turlire (ewconets)
Rolethive (%)
sparafication
25
6000
Realtv dode dierspnnes 760
Splmaation runtine (scconds)
20
150
Sparal Spanal calton dighthi Sgrthmmuunnnee
00
-0
30
Ralative sparsifcation
Relative spartificaion
Relative sparsiication
Navv АHKOО
D211
A-L1S
BKX821
RMR
Figure 1: (One patient, various sparsification levels) The performance of different algorithms in terms of: relative fo-m enror, relative optimality gap, feasibility gap, relative dose discrepancy, algorithm runtime, and optimization runtime, for a lung patient.
1893
Algo 0he meder Setcc
100
Bead07
Paay
E211
Avens
PMR
Figure 2: (Ten patients, sparsification level) The performance of different algorithms in terms of: relative fz-norm error, relative optimality gap, feasibility gap, and algorithm runtime, for ten lung patients.
of the RMR algorithm should not be seen as a significant limitation. The primary computational challenge lies in solving the optimization problem which often needs to be solved multiple times for hyper-paramett tuning. For example, achieve a relative optimality gap of 35% for patient the RMR algorithm necessitates sparse matrix with 98.90% relative sparsification (approximately 2,850,000 non-zero elements), in contrast elements) required by AHK06. Consequently, solving the optimization problem with RMR's 's sparse sketch is considerably faster, taking 57 seconds, compared to 200 seconds for the sparse sketch produced by AHK06. The bottom-right plot illustrates the strong correlation between the number of non-zero elements in the matrix and the computational time the constrained optimization problem, indicating that relative sparsification serves excellent proxy for the computational time of the optimization problems.
95.05% sparsification (about 12,750,000 non-zero
Figure 2 offers high-level comparison across all patients at a fixed relative sparsity level of 98%, which can also interpreted fixed computational time for the constrained optimization problem. Confirming the results of Figure more patients, this figure demonstrates the superior performance of AHK06 terms of the & norm error and algorithm runtime, while highlighting the significant advantage of the RMR algorithm in reducing optimality and feasibility gaps.

---

HUNGSS
dose
63.0
Tumor
47
31 5
15.
Cord
0.0
Figure 3: Radiation dose maps: Naive (left). RMR (middle) and dose labels (right)
pressenss a qualitative comparison between treatment plans generated using the naive approach (left) and RMR (middle), based on the radiation dose map commonly used by clinicians. The dose map visually represents the distribution of radiation, with color-coding overlaid on a medical image. Ideally, the high-dose regions (shown in red) should conform closely to the tumor's shape, with minimal radiation spillover into surrounding healthy tissues. While clinical expertise is required for detailed interpretation, clear that using the RMR sparse matrix, as opposed to the naive sparse matrix, results in reduced radiation exposure to the right lung (visible on the left side of the figure).
4.3 Limitations and Broader Impacts
We acknowledge that this study primarily focused on leveraging advanced matrix sparsification techniques to accurately and efficiently solve the computationally intensive optimization problems in cancer radiotherapy. While we have presented dose maps and DVH figures to illustrate potential improvements in treatment plan quality, our analysis remains limited. Future studies are necessary to comprehensively evaluate the clinical benefits of our techniques. Additionally, this study was reviewed by machine learning experts who focused the technical aspects rather than the clinical implications of the study. Another limitation of this study is that the theoretical bounds for feasibility and optimality gaps are provided for the quadratic optimization problem 2 not the general problem can be proven that, by assuming Lipschitz continuity for the functions Jo and g. a small | - S ensures small feasibility and optimality gaps. However, the bounds will depend the Lipschitz constants of fo and g.
Although our work primarily focused on Intensity Modulated Radiation Therapy (IMRT) with photon radiation, a widely used treatment modality, our approach could have a much broader impact in the field of radiotherapy. This is because all treatment modalities eventually boil down solving constrained optimization problems with large and dense matrices. As technology advances and new digital machines with greater flexibility, such those allowing couch movement, become available, the resultant optimization problems are becoming larger, making efficient approximation techniques increasingly essential to solve these problems within clinical timeframes [ 11].
Conclusion
We introduced a novel and high-impact application of matrix sparsification alongside an innovative algorithm that combines desirable theoretical guarantees with superior experimental performance. Our algorithm creates a highly sparse, randomized sketch of the original dose influence matrix used in radiotherapy optimization, preserving essential information. This enables solving the scrge-scale radiotherapy optimization problems within clinically viable timeframes, ensuring minimal discrepancy between the optimized radiation dose and the actual dose received by patients. effectively tackles problem prevalent in current radiotherapy optimization caused by reliance on inaccurately sparsified matrices from the current "naive" approaches. This method holds significant promise for enhancing the quality of radiotherapy treatments.
the "garbage-in- varrage-in-garbage-ou
10

---

Acknowledgments and Disclosure of Funding
Gourav Jhanwar and Masoud Zarepisheh gratefully acknowledge funding from the MSK Cancer Center Support Grant/Core Grant from the NIH (P30 CA008748).
References
[1] Dimitris Achlioptas and Frank McSherry. Fast computation of low rank matrix approximations, In Proceedings of the Thirty-Third Anmual ACM Symposium on Theory of Computing. STOC '01, page 61 -18, New York, NY, USA, 2001. Association for Computing Machinery.
[2] Dimitris Achlioptas, Zohar S Karmin, and Edo Liberty. Near-optimal entrywise sampling for data matrices. In Advances in Neural Information Processing Systems, volume 26, pages 1573-1573. Curran Associates, Inc., 2013.
[3] Sanjeev Arora, Elad Hazan, and Satyen Kale. A fast random sampling algorithm for sparsifying matrices. In Proceedings of the 9th International Conference Approximation Algorithms for Combinatorial Optimization Problems, and 10th International Conference on Randomization and Computation, page 272-279. Springer- Verlag, 2006.
[4] Vladimir Braverman, Robert Krauthgamer, Aditya R. Krishnan, and Shay Sapir. Near-optimal entrywise sampling of numerically sparse matrices. In Mikhail Belkin and Samory Kpotufe, ed- itors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 759-773, 773. PMLR, 15-19 Aug 2021.
[5] Steven Diamond and Stephen Boyd. Cvxpy: A python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5,2011 2016.
[6] Felix C Difilippo. Forward and adjoint methods for radiotherapy planning. Medical Physics, 25 (9):1702-1710, 1998.
[7] Petros Drineas and Anastasios Zouzias. A note on element-wise matrix sparsification via matrix-valued bernstein inequality. Inf. Process. Lett., 111(8):385-383 2011.
[8] Alex Gittens and Joel A Tropp. Error bounds for random matrix approximation schemes. arXiv preprint arXiv:0911.4100. 2009.
[9] Charles Huang, Yong Yang, and Lei Xing. Fully automated noncoplanar radiation therapy treatment planning. Medical Physics, 48(1 18(11):7439-7449, 2021.
[10] Gourav Jhanwar, Mojtaba Tefagh, Vicki T Taasti, Sadegh R Alam, Seppo Tuomaala, Saad Nadeem, and Masoud Zarepisheh. Portpy: An open-source python package for planning and optimization in radiation therapy including benchmark data and algorithms. AAPM 65th Anmual Meeting & Exhibition, 2023.
[11] Angelia Landers, Daniel O' O'Connor, Dan Ruan, and Ke Sheng. Automated 4T radiotherapy treatment planning with evolving knowledge-base Medical physics, 46(9):3833-3843, 2019.
[12] H. Liu, D. Schaal, H. Curry, R. Clark, A. Magliari, Kupelian, D. Khuntia, and Beriwal. Review of cone beam computed tomography based online adaptive radiotherapy: current trend and future direction. Radiation oncology (London, England), 18(1), 2023.
[13] ApS MOSEK. Mosek optimizer api for python. Software Package, Ver. 9, 2020.
[14] Riley Murray, James Demmel, Michael W Mahoney, N Benjamin Erichson, Maksim Mel- nichenko. Osman Asif Malik, Laura Grigori, Piotr Luszezek, Michat Derezinski, Miles E Lopes, al. Randomized numerical linear algebra: A perspective on the field with an eye to software. arXiv preprint arXiv:2302. 1474, 2023.
[15] NH Nguyen, Petros Drineas, and TD Tran. Matrix sparsification via the khintchine inequality. 2009.

---

[16] Mert Pilanci and Martin J Wainwright. Iterative hessian sketch: Fast and accurate solution approximation for constrained leaat-squares. Journal of Machine Learning Research, 17(53):
1-38, 2016.
[17] H Edwin Romeijn, James F Dempsey, and Jonathan Gi. A unifying framework for multi- criteria fluence map optimization models. Physics in Medicine & Biology, 49(10):1991, 2004.
[18] H. Edwin Romeijn, Ravindra K. Ahuja, James Dempsey, and Arvind Kumar. A column generation approach radiation therapy treatment planning using aperture modulation. SIAM Journal on Optimization, 15(3):838-66,, 2005.
[19] David M. Shepard, Michael C. Ferris, Gustavo H. Olivera, and T. Rockwell Mackie. Optimizing the delivery of radiation therapy cancer patients. SIAM Review, 41(4):721-744, 1999.
[20] Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Compu- tational Mathematics, 12(4):389 434, 2011.
[21] David P Woodruff et al. Sketching tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
[22] M. Zarepisheh, L. Hong, Y. Zhou, Q. Huang. J. Yang. G. Jhanwar, H. D. Pham, P. Dursun, Zhang, M. A. Hunt, G. S. Mageras, T. Yang. Yamada, and J. O. Deasy, Automated and clinically optimal treatment planning for cancer radiotherapy. INFORMS journal on applied analytics, 52(1):69-88) 2022.
12

---

A Proofs
A.1 Proof of Lemma] 3.1
Proof. The proof proceeds through straightforward analysis. Consider that for each of matrix A, the inequality Σ; LjeT; |aiil S. e e|Ti] holds. Consequently, the number of samples k; for row i satisfies &ę & [Ta]- Furthermore, [T; is at most the count of non non-zero entries in the i-th row of A. Summing over all rows, the total number of samples indeed less than or equal nnz(A).
A.2 Proof of Theorem 3.2
We employ the following theorem and lemmas prove Theorem 3.2 The initial theorem establishes a probabilistic bound for the ES norm of the aggregate of random matrices, serving as an essential instrument in various contexts. This theorem has also been utilized by Achlioptas al. [2] and Drineas and Zouzias 7 to establish their theoretical guarantees.
Theorem A.1 (Matrxx Bernstein (20).. Suppose that X1, X2.... X, are independent, zero mean, random matrices with dimensions m n. for each S i S || 212 I almost surely and
Σ E [ x.] 1 so?
Σ E XXXX
max
then for all
2 02 lir 3
X,
27
$ (m + n) exp
1=1
Lemma A.2. Suppose that [01 we' a positive semi-definite matrix.
U2
Un] is vector.
Then the matrix M
[|ll| diag([en), //22//...... |vrl)
Proof. is sufficient to prove that for every vector that
[2]
Inl x Mx 2 0. Notice
x T Mx = |ll|i Σ pollo uv)
lus|
los
> 0.
The last inequality is a result of Cauchy-Schwarz inequality because we can set V 2 0, and a; /v/,, for v; 0 and / /us|z,, in the below Cauchy-Schwee Schwarz incquality:
|0 for
2
Σ
agbs
a
b2
Lemma A.3. Let on 022..... Oen be positive real numbers, U1 02,.... Um E R and M E RRxx If
M' = M -mm 0,,20 is positive semi-definite matrix then || < |
Proof. Since M is positive semi-definite matrix, || sup x M' Note that
x M' = TT
Mr
(x T u;) S TMx
Mxl S |M
since M is a symmetric matrix. Hence ||M' $ 1|
Now, we offer proof for Theorem 3.2
13

---

Proof. Let M, = Ej== |syو and define E; {|ayal | i a:yl ct. As per Algorithm the sum of the elements in E, equals M; E. Consequently, the cardinality of E, denoted by | at most (M, - 23 Additionally, the number of samples is [,./e]. Therefore, the number of nonzero entries in the i-th row is less than M,/E + 1. Consequently, the total number of non-zero (nnz) entries in S is less than m + Ex=1 M,/c = m + [|All//e.
Assume that in the i-th row and during the t-th iteration of the redistribution step in Algorithm [ index j is selected. Let Sie represent an m x n matrix characterized by a single non-zero entry, sign(a:)) E, located in the i-th row and j-th column. Now, let us zero out all entries of A that
are greater than in absolute value and call the new matrix A, and define r. the i-th row of Á. It becomes apparent that Σ; = ||rill Consequently, we have
S
A+
S
Then
A-
A(D)
Stt
(i)
Sit
(A()
Sia)
ki
Ni
ki
Y=1
1=1
==1
1=1
1=1
and given that
E [Sial = lårgl
sign( (d=j) = A.jr
Ej
we have E [St]] = A(o) Now denote (A(e) Stt) by Xi. Since Xx has just one nonzero row, X T has just one nonzero entry which is on its diagonal. This entry is equal to
(ag - sagn(()))))
+
Σ
a
1 k
(Iril12 22a + 2'
b.
for some S j S n. Therefore ||seel2= = (1)ra 112 - 2/aigl Ln + >>?)/
Also
2²
[Ira 2 2/ai, D. + 23)
(223) = V2e,
k
V Σラ
and due to Theorem A.1 one can let R = V2c.
Note that
m
m
ΣΣ E [ x = Σ k& xxI
so we just need to calculate k.F [x]] X.1
which is equal to
K
ATo
(T)
(A() - -Sa)
(AT - [T - E [S A + +E(STSA))
12
k
K (-ATo) A(o) +E [STSAA)
(-rarT T + E Sa))
k;
Recall that S₁ has just one nonzero entry, therefore S Sa is a diagonal matrix. Also
E [STSal,
Dx [
Σj
From Lemma A.2
one can deduce that Σm Ehs [X]] X is a positive semi-definite matrix and
from Lemma A.3 its spectral norm is less than or equal to the spectral norm of > IE [S /k, which is diagonal matrix and
m
m
m
Σ
E [T
aayle S me?
k
ki
15
14

---

Hence
E
E [ Xtt
S <me..
According to Theorem A.1 there should also be an upper bound for - Ex= [x
Similarly,
1 - (-A())
[X 1
+ (S
The resulting matrix consists of just a nonzero entry, the ii-th entry of which is equal to (-11r; 2, 3/k: 2 0. Therefore >m
[x diagonal matrix. Then
(-11ril12 xX}
E
15i5
k;
2
max 18is
71
(n
1)E Σ₁
max ssis
S (n - 1)e²
So let 2 max(m,,)) 1)62.
Building on Theorem A. the derivation of Theorem 3.2 becomes a straightforward computation. We need have
(m + n) exp
max(m,, n - 1)e² +
/ZeT 3
Thus
m + n2 8
m + n2
V2
72
log
max(m, n 1)e² + log
=
0.
8
3
2
The above equation has just one non-negative root. Therefore
log
2
m+n
2r2
log
max (m, n - 1)72
log
/21
9
2 log
m
max (m, 1)
1
9 max m. 1-
-
loye
3/2 1V22mx(mm1) 1)
A.3 Proof of Corollary 3.3
Proof. Notice that /1 v1+c-1 2 Ve/2 for every 2 16/9. In Theorem 3.2 let 5 = 1/(m + n).
Then we have
9 max m.
-1)
9 max (m, -
max (amaxxxmnnn--- n1
log
2 log on +x))
2 logt m+n)
3v mm
max 1)
3 max(m, n
4 max(m,, n log + n)
since 9 max(m,, n 1)/(2 + n)) 2 16/9. Therefore based on Theorem 3.2 the result follows.
A.4 Proof of Lemma 3.4
We apply the Bernstein inequality to establish the result.
15

---

Theorem A.4 (Bernstein inequality). Let Xi...., Xn be independent zero-mean random variables. Suppose that Xx|] M almost surely, for all i. Then, for all positive T,
X
eexp
[X
+
MT 3
Now we present a proof for Lemma 3.4
Proof. Analogous to the proof of Theorem 3.2 we define the Xa matrices. Let v." be the i-th row of
XRt. From the proof of Theorem 3.2 the i-th row of A S is given by Σ V. and E [u.'|
Then, for each x E R", we have E M/ x] = 0 and
E (v. x)]] = E x
T x yeue
= E [tr (x" yeV, x)] = E [tr (axx yeVe )]
Lr (R [arx' T vev. ])
tr (xx EE [Mey ]).
Based on the proof of Theorem 3.2 we know that E (e9e diagonal matrix and the jj-th entry of it equals رريا [C, Hence,
(-rar + V)/k2, where Y is
E
(ve
x²)
27
tr xx ran + xx Y)
k?
Ir
x T
rit x + x Ya))
R?
n
((r x)² +
+
Σ
1=1
Therefore,
hx
Ue x)²
1
-
(r,Tx))
(r. x)
Σ
j=l
1
2
Σ
22 0501zقي + Σ
Σ
[azānl(1 + x7)
ki
ISjelšn
18jsisn
(3 )ign(
15j<iSn
lazjaa [2 + x2
1sj<lsn
2c Σ Σ lhal
Σ
S 2c |1112.
Also, 1v, x| < l1vell2 ||0:|/ and
ll
1
(ass Eysign(ar)))
+
Σ
(Ira 1
2/
E. + Σ3)
k?
1
2
(2>??
/2c.
16

---

Now according to Theorem
A.4
we have
Rx
x2
U1
2
cxp
2c² 11:11 +
/2e||=ll
Setting cc || results in
7²
- c
2 eex
2
2ex
2x
|x]|
4 2/2c
3
thereby completing the proof.
A.5 Proof of Lemma 3.5
Proof. Let da and dy denote Ax and Sx, respectively. In Lemma 3.4 if we let c = 19 + 5 log m, then have
c
cc2
2 exp
S exx
exx
4
2v
4e
2//2r 3
+ 2
- 19
5 5
exp
4 + 2v2
0.05
Thus
PP (I(da ds)a (19 + 5 5 m) m)rll= 0.05 Applying the union bound, with probability 1 m
0.95, we have
|| - dsllo < (19 + 5 log (
Now, if c is any arbitrary row C, have ||c||a < Therefore,
c (dd ddss S cell(da - ds)d <
Jalllda dsloo S IIlda - dslloo
which proves the result.
A.6 Proof of Lemma 3.7
Proof. Consider
fo(Ax) = ΣΣ (wi max(A7x -d",0² + w max(d" A3x,0)3),
SEB VEL.
which is the term dependent Ar in the objective function of the optimization problem Note that the remaining part of the objective function is independent of and hence is unaffected by the approximation.
Let (19 + log m) m|[[|=/12. For all E 5 and i Js, we have:
max d², 0) 2 max ( d) > max max(AŞr d²,
Similarly, we have:
- dd d) < ( v max max(AŞx -
d d², te.
Therefore.
max - d', 0) max(Se - d,, 00) See
and,
max(A; d", d²,0) + max d',0)l < max(AA2 d²,0) +
17

---

Altogether, we have that
max d', d02 - max - d,, d,,0)² - e(2max(Açç d), + te).
By a similar argument, we have that
max(d" - A2x,0)2 max(d" - -5 0) - c(2 - A²x, c).
In conclusion,
(So(Ar) Jo(Ss)) <
Σ (m e) + w maxxxdd - -Aix; + +e))
sE8,EE1
Σ
(max(Axx- + + + (max(d" - A2a, + + ++))
sE8,EI,
c(fo(Ax)
Σ
(wi, "t (1 + e))
sES,iEL,
$ <e(fo(Aa) m(1 + é)
Σ (w) + +w= w"))
Thus, summary, for any arbitrary x E R", we have that
[o((A)) fo(Sx)) e(fo(Ax) + m(1 e)
Σ
(w.. + w ))
sES
with probability at least 0.95.
A.7 Proof of Lemma 3.8
Proof. It suffices to consider:
8 - + (1 (1- e
x.
8
s
For each convex constraint 9: S O,
(:(A))
9i (A
c -x + (1
- )x)
e
91
(AT) + (1- 6)
(i(A
s
c (-s) (1- E
5)
8
$ 0.
Additionally,
||x
2
e # +
(1
5)ar m)
8
(x 8)
0
T||
5
|||0|| + ||=|].
This completes the proof.
A.8 Proof of Theorem
3.9
Proof. Let & = min(min, min, (d)Mss))) )- Then, satisfies the assumptions of Lemma
3.8 for the approximated optimization problem. Therefore, with a probability of 0.95, there exists
18

---

feasible point of the approximated optimization problem 2 E R" such that I -All S E|[=A|l-
(o(Ams) + fa <
m +
Σ (w + w=))
SE$
m +
Σ (wf + +w=)
sE8
I + + m(1 +
2 (we + w
.ES
+ +c(fo(ARA) + m(1 e)
(w + +
#ES
S f(ra) +(e)
fo f O
The first and third lines follow from Lemma (3.7). the second line follows from the optimality of as for the approximated optimization problem, and the forth line follows from {|ı=al| = O Finally, the last line follows from the Lipschitz continuity of the objective function over the feasible set which
bounded. Altogether, the sub-optimality of the solution to the approximated optimization problem is (e))
B Additional Experimental Results
Dataset and problem formulation. presents data for randomly selected lung patients, detailing the number of rows (i.e., patient's voxels), columns (i.e., machine's beamlets), and the count of non-zero elements. Each patient received a prescribed radiation dose of 60 Gray. The treatment plans involved 9 manually selected radiation beams, chosen by an expert clinical physicist and tailored each patient's anatomy. Table 3 presents the maximum and mean dose constraints used in the optimization problem All the data have been downloaded from PortPy
Table 2: Data size summary for the 10 patients in the study.
Number of voxels (matrix rows, m)
Number of beamlets (matrix columns, n)
Number of non-zeros (nnz(A)
1
381,343
2,095
257,833,896
2
336,384
2,397
281,798,395
3
438,138
1,704
211,556,826
4
324,926
1,501
135,431,085
292,120 5
1,185
91,472,882
365,469 6
1,545
170,601,422
7
281,860
1,924
201,124,333
8
284,296
1,074
83,910,465
9 354,925
1,261
102,218,449
10
385,600
1.517
143,582.667
Optimization Runtime for Full and RMR Sparse Matrices. Table provides comparison between the optimization runtime when using the full matrix and when employing the RMR sparse ma- trix with 98% sparsity. The optimization using the full matrix was performed on a high-peeformance computing (HPC) system with approximately 320 GB of memory, while the RMR sparse matrix optimization was conducted on system with 128 GB of RAM. Despite the more advanced hardware for the full matrix, the results demonstrate significant improvements in optimization time with the RMR sparse matrix, especially in digner-dimensional cases. Additionally, the execution time of the RMR algorithm is reported, indicating the overhead introduced by the sparsification process.
19

---

Table 3: Recommended clinical dose bounds for lung cancer patients.
Structure
Dose constraint (Gray)
Tumor (PTV)
max dose <
Esophagus
max dose I 66
mean dose - 34
Heart
max dose v
mean dose v 27
Cord
max dose v 50
Lungs
max dose - 66
Nevertheless, the total computational cost remains substantially lower compared the full matrix approach. The primary computational bottleneck in this application stems from the optimization problem, where the computational time increases cubically with respect to the size of the input matrix. In contrast, the computational time for the RMR algorithm grows linearly.
Comparison of Optimization Runtime Using the Full Matrix vs. the RMR Sparse Matrix Table 4:
(98% Sparsity) and RMR Algorithm Runtime
Full Matrix
RMR Sparse Matrix
RMR Algorithm Execution Time (s)
Optimization Time (s)
Optimization Time (s)
1
2826
87.25
48.77
2
3212
122.5
46.80
3
2147
45.84
50.30
4
1277
53.30
32.78
5
870
32.17
25.33
6
1447
58.25
38.26
7
1492
81.47
33.65
8
714
29.18
23.88
9
838
33.20
29.95
10
1303
51.66
36.59
Ten patients, fixed sparsification level. Table presents presents the performance of different algorithms in terms of relative f2-norm error, algorithm runtime, feasibility gap, and relative optimality gap for ten lung patients with fixed sparsification level of 98%. This table provides a detailed expansion of the results shown Figure 2 Better scores are highlighted in bold for easier visual comparison. Standard deviations are provided for all algorithms, except the naive algorithm, which deterministic. As can be readily seen, the AHK06 algorithm excels in terms of fo-norm error, while the RMR algorithm consistently outperforms in terms of feasibility and optimality gaps. The naive algorithm is the fastest due to its simple implementation.
Nine patients, various sparsification levels. Figures 4to expands the comparisons made for single patient in Figure [ to nine additional patients. These figures confirm that the results observed for one patient are consistent across other patients.
Dose Volume Histogram (DVH) comparisons. A DVH is a two-dimensional plot used in radio- therapy depict the distribution of radiation dose within the tumor and the surrounding normal tissues (Figures] and Each structure has its own curve the DVH, where the horizontal axis
20

---

represents the dose, and the vertical axis indicates the percentage of the volume receiving at least that dose. For instance, in the top-left figure for the lungs (i.e., left and right lungs), the solid line intersects the point (20,10), signifying that 10% of the lungs receives at least a 10 Gy radiation dose. By illustrating the volume of tissue exposed to various dose levels, DVHs help clinicians assess the uniformity and adequacy of dose coverage to the tumor and ensure that surrounding healthy tissues are spared as much as possible. This visualization is crucial for comparing and optimizing treatment plans, enabling effective tumor control while minimizing adverse effects on normal tissues.
Figures and showease three DVH plots: the naive approach (left), representing current practice; the AHK06 algorithm (middle), representing the most competitive existing approach; and the proposed RMR algorithm (right). each plot, dashed lines illustrate the approximated radiation dose. Srg. used in the optimization problem 2 while solid lines depict the actual radiation dose, Azg. While clinical expertise necessary to fully interpret these curves, the gap between the solid and dashed lines indicates the discrepancies resulting from using the approximated matrix S in the optimization problem [ with a smaller gap being preferred. It is readily apparent that the gap is much smaller, especially for the tumor, when using the RMR algorithm, where the solid and dashed lines are closely aligned and often overlap, making the dashed lines nearly invisible.
Previously, we focused exclusively lung patients; we now examine the results for five different prostate patients. As shown in HanureSaandT0 the results are largely consistent with those for lung patients, with only a few minor differences. The proposed RMR method demonstrates a shorter runtime than AHK06 across all five patients. At high sparsity levels, such as 99%, however, AKLI3 outperforms RMR in terms of the relative εy-norm metric. Additionally, DZ11 exhibits higher feasibility gap at lower sparsity levels, indicating that additional samples do not reduce the feasibility gap for this method expected. Table [S] reveals that the dose influence matrices for prostate patients are considerably denser than those for lung patients, accounting for some observed differences in results. Finally, Figure 11 presents the DVH plots for these five patients, with three DVH plots for each patient: the left plot represents the naive approach, the middle plot shows the AHK06 algorithm, and the right plot displays the RMR algorithm. These findings consistent with those observed for lung patients, except in the naive approach, which appears to outperform AHK06. This suggests that prior sparsification methods may not consistently outperform the naive approach within this application.
Prostate Patients.
Table 5: Data size summary for the 5 prostate patients.
Number of voxels (matrix rows, m)
Number of beamlets (matrix columns, n)
Number of non-zeros (nnz(A))
1
119,587
3,555
241,300,640
2
130,296
2,978
243,867,050
3
126,941
3,753
310,181,024
4
128,867
3,848
348.771,625
5
132,089
3,983
355.875,426
Table 6: Recommended clinical dose bounds for prostate cancer patients.
Structure
Dose constraint (Gray)
Tumor (PTV)
max dose I 77.2
Rectum
max dose < 71.6
mean dose I 25
Bladder
max dose < 75
21

---

Table 7: The performance of different algorithms in terms of relative é2-norm error, algorithm runtime, feasibility gap, and relative optimality gap for ten lung patients with fixed sparsification level of
98%.
2
3
4
5
6
7
8
9
10
Naive
27.22
22.24
21.62
28.08
25.47
24.11
19.2
26.18
27.38
28.18
8.64
6.77
7.55
10.09
11.23
9.06
6,48
10.78
10.82
10.2
Relative E2-norm (%
AHK06
#0.03
#0.01
#0.01
=0.08
#0.02
#0.02
=0.02
=0.02
#0.04
#0.4
14.43
11.27
13.68
16.42
18.14
15.03
10.53
16.99
17.39
17.39
DZ11
#0.30
10.32
#0.25
=0.28
#0.21
#0.07
#0.23
+0.23
#0.17
#033
12.27
10.02
12.39
14.78
16.17
13.88
10.57
16.12
15.46
14.74
AKLI3
+0.02
+0001
+0.03
+0.01
+0.05
+0.03
+0.02
+0.04
+0.03
+0.03
8.79
6.76
7.95
10.75
11.81
9.20
6.43
11.23
11.01
10.54
BKKS21
+0.02
+0.01
+0.01
#0.05
+0.09
#0.02
#0.01
+0.03
#0.04
#0.02
9.32
7.03
8.31
11.34
11.86
9.70
7.02
11.73
11.38
11.42
RMR
10.05
10001
+000
#0.01
#0.05
#0.01
#0.02
10.01
10.03
1007
Naive
21.84
24.7
18.31
10.42
6.11
12.30
14.05
5.24
9.59
13.23
46.91
53.33
40.19
24.02
14.73
27.94
30.69
12.63
21.90
30.06
Runtime (seconds)
АHK06
10.11
#0.19
10.06
#0.04
#0.04
#0.09
#0.66
+0.04
#0.05
1004
3.3e2
4.3e2
3.3e2
1.0e2
68.09
1.9e2
3.2e2
51.53
84.56
1.2e2
DZ11
1.7
22.00
#2.35
#0.77
#0.42
#0.36
1.00
#0.44
#0.58
#0.95
57.51
60.71
48.54
30.54
18.99
38.10
39.88
17.06
26.42
34.13
AKLI3
0.38
+.552
+0.36
+0.05
+0.12
+0.06
+0.23
+.0.8
+0.19
+0002
78.79
85.07
67.96
40.93
28.28
49.28
51.35
24.36
37.80
51.13
BKKS21
+0.14
+.224
+0.17
#0.12
+0.26
+0.44
+0.03
+0.07
+0.24
#0111
48.77
46.80
50.30
32.78
25.33
38.26
33.65
23.88
29.95
36.59
RMR
0004
0.04
1133
#0.03
10.03
#0.17
#0.02
10.19
#0.07
1003
Naive
1.3e4
6.2e3
7.9e3
7.6e3
2.8e3
5.1e3
3.6e3
4.9e3
6.1e3
8.2e3
0.06
0.40
0.09
0.34
0.15
0.61
0.04
0.16
0.27
0.28
AHK06
#0.04
10.16
+0.05
#0.21
10.14
#0.26
10.04
10.10
10.16
10.17
Feasibility gap
1.98
5.83
1.10
3.20
3.60
3.61
0.57
2.28
2.23
3.03
DZ11
#0.64
1.05
#0.26
#1.55
#0.62
#0.57
#0.10
#0.72
+1.05
1144
0.48
1.03
0.16
0.49
0.99
0.97
0.21
0.26
0.25
0.30
AKLI3
0.166
0.25
+0.14
+0.33
+0.48
+0.27
+0006
+0.30
+0.17
+0.21
0.02
0.26
0.07
0.05
0.04
0.43
0.03
0.06
0.08
0.07
BKKS21
+-0.33
0.09
+.0.4
+0.03
+.044
+0002
+004
+0006
+0006
+.08
0.00
0.39
0.05
0.04
0.00
0.45
0.04
0.00
0.10
0.01
RMR
+0.01
+0.08
+0.02
+0.02
+0.00
+0.8
+0.02
+0.00
+0.0
1.01
Naive
1.2e4
5.0e3
7.2e3
1.5e4
8.1e3
4.3e3
3.7e3
1.2e4
1.4e4
1.3e4
1.8c2
1.2c2
1.5c2
2.7c2
3.0c2
1.3c2
1.0c2
3.3e2
3.5c2
2.5c2
AHK06
Optimality gap (%)
+3.80
+3.69
#4.50
15.99
11.6
17.97
10.85
11..4
1191
17.72
3.6e2
3.0e2
3.0e2
4.3e2
5.6e2
2.2e2
2.9e2
4.7e2
5.3e2
4.6e2
DZ11
10.8
+633
+6.59
+26.8
11733
#6.84
1121
+12.6
#32.7
226.4
3.5e2
3.0e2
4.4e2
6.8e2
1.0e3
3.7e2
3.0e2
9.2e2
9.7e2
7.4e2
AKLI3
#7.67
10.2
+27.7
+68.5
#72.4
#22.7
117.
#51.8
112e2
+60.2
98.86
65.79
74.98
1.4e2
1.4e2
54.88
62.29
1.5e2
1.8e2
1.4e2
BKKS21
1.04
+.063
+2.52
+6166
+.9.2
+2.91
1.84
+3.40
10.9
+2.43
18.89
13.91
11.61
25.59
21.18
9.44
11.58
23.20
32.81
26.86
RMR
+0.30
+0.24
10.38
1148
+1.1
11.75
=0.22
10.78
1163
10.31
22

---

Reurie optiaaly SPP (5)
14
800
018
12
Relathe cation
Sporsfiction dlporth urrtire (20c0150)
Reattive apanniliaaiion
Retstive spariitcaioon
600
Optinrzzinn rurtin Soconddt
10.0
7.5
T1e seive cation 196)
Touative spatinattioonn (96)
(eelative apanddiciio (S)
4.0
2.5
3.0
2.6
10
2.0
15
8.5
10
22
1.0
0.5
0.0
55
87
50
85
66
58
83
56
57
Relriie spantiicationn (%)
Spor Feation gorthm runtrr (Sccorid))
Rebeiin spandicatinn
(telative aparccicatioonn
1:5
15
600
100
88
25
32
97
50
20
93
56
92
59
93
56
57
Rebrive spanttcationn (7)
Rebatke oparafication (5)
Reielive sparsiication (5)
3300
nort ero0 (10
35
Bee optimality (ep (50
32
730
Rousve.s foreee
Fasablity
160
15
Spa oittttonn aggrthn nuntome (tnordde)
spansfication
8000
Opt tottttato surdine (enardde))
Baotten doow deeceperry
1:0
80
37
Nahe AH1K2
D211
ARLIS
BKXC21
RMR
Figure 4: (Various sparsification levels, Lung patients 2-4) The performance of different algorithms terms of: relative & nnom eитоr, relative optimality gap. feasibility gap, relative dose discrepancy. algorithm runtime, and optimization runtime, for patients 2 (first two rows), (second two rows), and 4 (third two rows).
23

---

Foentriiy
18
140
Roatred,
spantticationn (7)
runtina (secomos)
(5)
Oytimu centrr (secommd))
13
Spar cocion argottim mantttntttttttoo
130
16
60
10
14
spartPication (75)
22.00
40
oytmoality
80
10
Relrtive spartMtctionn (7)
Epars Raaloo agorthm turtine (sccomss)
Relative spantiicaton
Relative spansiication
1961
500
140
85
80
10
34
Reeerive spantiicttonn (%)
Relatho spandicatinn
Reelatiee spansiicaiion
30
Robabve Lymom (6)
22
Dalative syptnse pap
by SPC
1:00
16
Reletton cp (%)
Rebeive spaediiaiion (%)
Flaedion
Rwbriee apaiiiiation (8)
17.2
(oocudss)
Balabve Goe Gonuenn
12.5
1.40
119
25
7.5
25
80
08
56
16
95
94
59
96
95
96
25
sparsileaaion
spars
Navv A+4000
0211
AKL1S
BK4401
RVR
Figure 5: (Various sparsification levels, Lung patients 5-7) The performance of different algorithms terms of: relative -nom error, relative optimality gap, feasibility gap, relative dose discrepancy, algorithm runtime, and optimization runtime, for patients 5 (first two rows), 6 (second two rows), and 7 (third two rows).

---

12
Feeebilly grp
18
optirallyy
18
10
17
98
95
56
58
93
95
92
Rebeiis spanrilcsiion (%)
Sparoffiat akgofiten r.r2me (5000143)
Relation xpandiictonn (8)
Relative apaend Ecation (86)
300
Ostmteaamn (perzond)))
18
10
57
98
85
66
58
95
67
99
Relative sparsilcationn (%)
Ralativ spuraficaton (%)
Relittvve Feationiaiion (50
4000
(5))
10
Booone geo
ootimaliityy
200
15
10
86
60
99
Relazie sparsflcation (95)
Spanii cation slpor Bio Luntin (sooords)
spanaficatin
aparsi
Optim (swcondd))
18
100
15
70
10
29
97
15
96
59
95
56
97
25
Relativo sparsitcction (75)
sparsficatio
40
Redbba optraadyyyyyoo Emp (5)
Roubee Lumm eroa
90
800
25
10
soorsiicction
Spand catonn gag.gggmmm po rurtine (mmcordd)
Rolativo scatinllatton
sparsillation
oeton mue (socomdd))
140
23
20
60
10
Relative scondtication
Relattve Ecation
Raterive spartfication
Nake AHAOE
D211
BRX5221
Figure 6: (Various sparsification levels, Lung patients 8-10) The performance of different algorithms in terms of: relative & -nomm етror, relative optimality gap, feasibility gap, relative dose discrepancy, algorithm runtime, and optimization runtime, for patients 8 (first two rows), (second two rows), and 10 (third rows).
25

---

230
100
303
Volumme Traetaon (N)
Dosi 1091
Dose 19g))
Dcea 10y1
130
100
100
Voluma fraction
Viuum Tractton
Doce 30y)
Done 19y0
Doien 05y1
100
1.00
30
02-
Vatume Traddon P50
Vatume fracdon
Dose:
1ay1
130
30
60
Volume Fractin
00
Volume Fraccion
30
Whure Freciin 196
60
40
80
10
18
Tumor (PTV)
Lungs
Esophagus
Heart
Cord
Figure 7: (DVH discrepancies, Lung patients 1-5) The discrepancies Dose Volume Histogram (DVH) plots for patients 1 to 5, from top to bottom, respectively. The plots compare the results of the naive approach (left), AHK06 (middle), and the RMR method (right). In each plot, dashed lines represent the approximated radiation dose, S2g, while solid lines depict the actual radiation dose, Axg. smaller gap between the dashed and solid lines is preferred, indicating a more accurate dose approximation. Note that for RMR, the solid and dashed lines often overlap, making the dashed lines nearly invisible.
26

---

230
100
110
30
Voluma fraction (N4)
Viumm fracton (961
Doce 30y)
Done 165
Doien d5y)
190
1.00
02-
Valume Tracdon 15
Vature Traddon P5
10y)
Dase (ay)
130
Voume fractinn (30
80
Dosie
Vouum fractinn (40
80
60-
Dose
1.0
08
60
Volume or on
66
valume Frack
Turar (PTV)
Lungs
Esaphagus
Heart
Cord
Figure 8: (DVH discrepancies, Lung patients 6-10) The discrepancies in Dose Volume Histogram (DVH) plots for patients 6 to 10, from top to bottom, respectively. The plots compare the results of naive approach (left), AHK06 (middle), and the RMR method (right). In each plot, dashed lines represent the approximated radiation dose, Sagg, while solid lines depict the actual radiation dose, Axg. smaller gap between the dashed and solid lines is preferred, indicating a more accurate dose approximation. Note that for RMR, the solid and dashed lines often overlap, making the dashed lines nearly invisible.
27

---

Orgectin Vatun
+150
19
18
420
15
Relathe cation
S30 Sottsic algott urrtne (poc0r50)
Reative spansilcaaion
Relstive sparsiication
240
17.5
Optimrzooonn rurtin Decondts
15.0
120
-12
60
32
80
Iteatiee cation 196)
Touative apatinitationn (96)
(eelstio spandficiion (%)
E, nom (84)
Peaelity gho
05
87
94
95
56
58
95
95
90
97
Rebriiv spantiicationn (%)
Spanrfration algorbin cuttime (iccords)
Rebeiin spandicatin
Reelalie apaind (5)
150
120
25
00
25
27
22
93
96
2B
08
25
95
57
50
Relaive spansfication (%)
sparaficatin
aparsa
17.5
15.0
Pearielty.o QP9
12.5
22
Orgactia
8:0
10.0
Saldve
7.5
Relative oparaficaaion
Rebiiie aparaiizaion
Fodarie apana Ecation (%)
17.1
0.00
16.2
1.20
100
12.5
10.2
70
35
06
$6 Rebative spatiiftattonn (%)
96
66
56
96
98
69
Reartiv spareficatto (%)
Rabritee sparsiication (5)
BKK0201
RMR
Figure 9: (Various sparsification levels, Prostate patients 1-3) The performance of different algorithms in terms of: relative fn-morm error, relative optimality gap, feasibility gap. relative dose discrepancy, algorithm runtime, and optimization runtime, for patients (first two rows), (second two rows), and 3 (third two rows).
28

---

7500
Saaiioe----oooo (S6)
14
10
Okyerdev Ville
22.0
000
12
18
50
57
18
30
16
27
59
96
05
27
52
natero (sooords
alve up apatiilcatioon (46
Relative sparsftcatin
1240
17.5
Octhlamnnn tuntine (pcoodd))
100
15.0
Spartfaation awgothmn olgottmnnntteeee
120
118
3.0
80
2.5
15
37
othe cation
Recative spattilicatioo
Relative sparsifiation
fadattow Cemtam (60
12
25
32
Obpeckvv Vakae
22
0:20
10
1:00
85
66
S8
98
55
05
58
55.
46
21
50
Relatiive opartMfcation (%)
Relatio spars foctioncion (%)
Ro Relurtre spatoiicction (5)
Rolttv dos dacoppare (10)
17.8
(ucoria))
16.0
1:3
12.4
8.
2.8
20
Navs A-1005
DC11 ARL13
BKA521
1947
Figure 10: (Various sparsification levels, Prostate patients 4-5) The performance of different al- gorithms in terms of: relative -n-mm error, relative optimality gap, feasibility gap. relative dose discrepancy, algorithm runtime, and optimization runtime, for patients 4 (first two rows), 5 (second two rows).
29

---

290
100
100
VSsu Tractton (N6)
Doce 30v)
Done 1690
Doiee d5ys
190
140
30
02-
Voture Tradton P50
Traddon
1021
Dose10y
100
10
Volume Fraction
Done
fracion
40
48
Volama
35y)
Volume Tradtinn (S)
Vilume
10c)
(0y)
Turar (PTV)
Rectum
Bladdeer
Figure 11: (DVH discrepancies, Prostate patients 1-5) The discrepancies in Dose Volume Histogram (DVH) plots for patients 1 to 5, from top bottom, respectively. The plots compare the results of the naive approach (left), AHK06 (middle), and the RMR method (right). In each plot, dashed lines represent the approximated radiation dose, Sæy, while solid lines depict the actual radiation dose. Axg. A smaller gap between the dashed and solid lines is preferred, indicating more accurate dose approximation. Note that for RMR, the solid and dashed lines often overlap, making the dashed lines nearly invisible.
30

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: separate section address the limitations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips.com hwtps/cccppbcccccceeceeeeee
Cooeeeoddemsssseeeeee /ttc: www.oniccccccyicccoooooocicicipi for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Given the nature the study, there is no training and test dataset. Instead, the problem formulation and relevant hyper-parannn apper-parameters thoroughly explained.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
33

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Our computing resource specifications are provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///wwrp..cccaaaaa/a//aacaaa
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: There is designated section.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not anticipate any misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
35

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does release new assets. Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The research has used existing publicly available datasets.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [No]
Justification: Although this research included human subjects, it posed no risk, as was retrospective and conducted in silico (i.e., simulation mode). The lung patient dataset is publicly available, and GJ and MZ. obtained IRB approval (16-422A(6) for access to the prostate dataset used in the appendix.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
36


Reviews:
[{"review_id": "9nK88OG7yB", "reviewer": "Reviewer_rbxv", "summary": "I am not an expert on the optimization method for this paper. I am selected as a reviewer due to my medical image analysis and oncology image processing research background. First of all, in my opinion (my confidence is 3 out of 5), NeurIPS is not the right conference venue for this work. The problem of dose planning and optimization is very critical after tumor and organ-at-risk contouring. NeurIPS in my understanding is not an numeric optimization conference? \n\nSecond, the indication of the proposed optimization method is very cirtical to patient safety in treating cancer patients. Again, the validity and utility of the proposed method need to be examined very carefully and professionally at a professional society. NeurIPS may not be the right place for this work.", "questions": "as above", "limitations": "as weakness", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper presented a Novel Matrix Sparsification Algorithm which is used to solve the important problem in cancer/tumor radiation therapy dose map. I am not an expert on this particular direction. The developed method seems reasonable and solid but I have no confidence on judging this aspect.\n\nThe problem of optimzing the radiation therapy treatment dose map is of ultimate importance since it directly impacts cancer patient treatment outcome (benefits or harms).", "weaknesses": "1, NeurIPS may not be the right conference venue for this work. The problem of dose planning and optimization is very critical after tumor and organ-at-risk contouring. NeurIPS in my understanding is not an numeric optimization conference? \n\n2, From the clinical aspects, the indication of the proposed optimization method is very cirtical to patient safety in treating cancer patients. Again, the validity and utility of the proposed method need to be examined very carefully and professionally at a professional clinical society, like ASTRO. NeurIPS may not be the right place for this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for dedicating time to review our paper.  Our responses to your comments are provided below.\n\n**Summary:**\n\n> I am not an expert on the optimization method for this paper. I am selected as a reviewer due to my medical image analysis and oncology image processing research background. First of all, in my opinion (my confidence is 3 out of 5), NeurIPS is not the right conference venue for this work. The problem of dose planning and optimization is very\ncritical after tumor and organ-at-risk contouring. NeurIPS in my understanding is not an numeric optimization conference?\nSecond, the indication of the proposed optimization method is very cirtical to patient safety in treating cancer patients. Again, the validity and utility of the proposed method need to be examined very carefully and professionally at a professional society. NeurIPS may not be the right place for this work.\n\n**Strengths And Weaknesses:**\n\n> **Strengths:** The proposed method is easy to implement.\n\n> **Weaknesses:** \n> 1, NeurIPS may not be the right conference venue for this work. The problem of dose planning and  optimization is very critical after tumor and organ-at-risk contouring. NeurIPS in my understanding is not an numeric optimization\nconference?\n\n> 2, From the clinical aspects, the indication of the proposed optimization method is very cirtical to patient safety in treating cancer patients. Again, the validity and utility of the proposed method need to be examined very carefully and professionally at a professional clinical society, like ASTRO. NeurIPS may not be the right place for this work.\n\nThe contributions of this work is twofold: \n\n1) **Introduction of a New Sparsification Algorithm:**  This work presents a novel sparsification algorithm equiped with theoretical guarantees and superior computational performance compared to (AKL13: NeurlPS) and two other comptetive technqiues that used as benchmarks in (AKL13: NeurlPS).  \n\n2) **Novel Application in Healthcare**: This work presents an impactful application of sparsification methods in the healthcare sector.\n\nThis interdisciplinary project emerged from a collaboration between ML/AI scientists at a university and medical physics experts at a hospital. It was inspired by a real-world problem with the hospital's in-house treatment planning system, which currently employs naive sparsification. This system is integrated with the FDA-approved Eclipse system and used in daily clinical practice, however, it leads to concerning discrepancies in dose calculations (these details have been removed from the manuscript for the anonimity reasons). As demonstrated, these issues can be effectively tackled using advanced sparsification techniques developed within the ML/AI community. \n\nWe believe this work is particularly suited for presentation at ML/AI conferences for the following reasons: \n\n1) Randomized matrix sketching has been an active area of research withing ML/AI community and most of the previous sparsification algorithms have been published in ML/AI conferences; this work not only introduces a new algorithm with theoretical gaurantees but also presents a novel application with superior computational performances.\n\n2)  This work has the potential to raise awareness within the ML/AI community about this crucial application, sparking a new wave of research and collaboration that could significantly benefit the medical community, much as the ML/AI community has already enhanced the field of medical imaging.\n\nRegarding patient safety and validation, we acknowledge the need for more detailed discussion in our manuscript. We will address this in the revised version. In short, the full validation of these techniques involves multiple stages and typically spans several years, including:\n\n1) **Dosimetric Comparisons**: Currently, this work includes dosimetric comparisons using tools like DVH plots in the Appendix. We can also add color-coded dose distribution maps in the Appendix to enhance the validation.\n\n2) **Quality Assurance in Plan Delivery**: This step requires physical measurements using phantoms to ensure that the simulated radiation dose in the FDA-approved treatment planning system aligns with the dose actually delivered to the patient. \n\n3) **Clinical Deployment and Controlled Trials**: The ultimate validation of this techniques will involve their deployment in clinical settings followed by controlled, randomized clinical trials to rigorously assess their impact on patient outcomes.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RpEF920E6g", "reviewer": "Reviewer_oYrg", "summary": "The paper titled \"Randomized Minor-value Rectification: A Novel Matrix Sparsification Technique for Solving Constrained Optimizations in Cancer Radiation Therapy\" presents a novel algorithm for matrix sparsification, aimed at improving computational efficiency in the optimization problems associated with cancer radiation therapy. The authors introduce the Randomized Minor-value Rectification (RMR) algorithm, which effectively sparsifies large matrices used in radiation therapy without significantly compromising treatment quality. The RMR algorithm retains the largest matrix entries deterministically and applies a randomized approach to the minor entries, ensuring minimal impact on the optimization constraints and objective function.", "questions": "1. Can the authors elaborate on why specific baseline methods (e.g., AHK06, DZ11, AKL13) were chosen for comparison? What advantages do these techniques offer for evaluating the effectiveness of the RMR algorithm in matrix sparsification?\n\n2. How does the RMR algorithm perform in more diverse and dynamic real-world settings, such as different cancer types or treatment modalities? Are there plans to test the algorithm in more varied environments?\n\n3. What potential challenges could arise regarding the scalability of the RMR algorithm for very large datasets or real-time applications? How does the algorithm handle computational and communication overhead in such scenarios?\n\n4. Can the authors provide more details on the optimization process for fixed-point representations and its impact on overall performance and accuracy of matrix sparsification?\n\n5. What are the potential ethical considerations or privacy concerns associated with the proposed method, particularly in using sensitive health data for optimization problems? How does the RMR algorithm address these concerns?", "limitations": "1. Potential challenges and mitigation strategies for deploying the RMR algorithm in real-world settings, particularly regarding data diversity and environmental variability.\n\n2. Discussing the ethical implications and privacy concerns related to continuous monitoring and optimization in high-stakes healthcare applications. This includes addressing the implications of using sensitive patient data and the potential impact of optimization decisions on different demographic groups.\n\n3. Further exploring the trade-offs between computational efficiency and treatment accuracy, particularly in scenarios where rapid solution times are crucial for clinical decision-making.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "### Originality:\n\nThe RMR algorithm introduces a unique combination of deterministic and randomized approaches to matrix sparsification, specifically tailored for the constraints of cancer radiation therapy optimization. The paper's emphasis on practical application in a critical healthcare domain, such as radiation therapy, highlights the potential impact of the proposed method on improving patient outcomes.\n\n### Quality:\n\nThe paper provides a thorough explanation of the RMR algorithm, including its theoretical guarantees and detailed proofs of its effectiveness. \n\n### Clarity:\n\nThe paper is well-organized, with a clear structure that guides the reader through the problem statement, related work, methodology, experimental setup, and results.\n\n\n### Significance:\n\nThe proposed RMR algorithm addresses a critical challenge in radiation therapy by enabling the rapid and accurate solution of large-scale constrained optimization problems within clinical timeframes. By improving computational efficiency without sacrificing treatment quality, the RMR algorithm has the potential to significantly impact the field of radiotherapy and improve the outcomes for cancer patients.", "weaknesses": "### Novelty:\n\nWhile the combination of deterministic and randomized approaches in the RMR algorithm is innovative, a more detailed comparison with existing sparsification methods on both theoretical and practical grounds would further highlight the unique contributions of the proposed method. The paper could benefit from a deeper discussion on the limitations of the proposed approach, particularly in scenarios with extreme data heterogeneity or limited overlap in matrix entries.\n\n### Experimental Validation:\n\nThe experimental validation primarily relies on controlled datasets from lung cancer patients. Including more diverse real-world testing scenarios would provide a more comprehensive assessment of the RMR algorithm's effectiveness and generalizability. Additional details on the characteristics of the datasets and how they were partitioned and used in experiments would enhance the transparency and reproducibility of the results.\n\n### Technical Details:\n\nSome aspects of the RMR algorithm, such as the optimization process for fixed-point representations and the derivation of error bounds, could be explained in greater detail to enhance clarity and understanding. The choice of evaluation metrics and their suitability for different types of sparsification problems could be discussed more extensively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for dedicating time to review our paper. Our responses to your comments are provided below.\n\n## Weaknesses:\n\n### Novelty:\n\n> While the combination of deterministic and randomized ...\n\n### Experimental Validation:\n\n> The experimental validation ...\n\nRegarding data heterogeneity, we have evaluated the RMR algorithm on both publicly available lung cancer patient data and internal datasets that include other cancer types such as prostate and spine. These internal datasets, sourced from our collaborating hospital, are not publicly available. However, we can include performance results of the RMR technique on these datasets in the revised manuscript to demonstrate its consistent effectiveness across diverse data sets, should the reviewers find this addition valuable (please refer to Figure 2 and Table 1 in the 1-page PDF file provided with our responses).\n\nUnfortunately, we're not entirely sure what is meant by 'limited overlap in matrix entries.' We would be happy to provide clarification if you could elaborate on this point.\n\n\n### Technical Details:\n\n> Some aspects of ...\n\nThanks for bringing this to out attention. We acknowledge the need for more explanation on these issues and will include them on the revised version. \n\n**Questions:**\n\n> 1.  Can the authors ...\n\nAs noted in the paper (page 3), sparsification algorithms can be classified into two distinct categories. To the best of our knowledge, the algorithms AHK06 and AKL13 offer the best theoretical bounds for the first and second categories, respectively. DZ11 is also a very well-known algorithm within the second category. We will provide further clarification on these classifications and their respective algorithms in the revised version of the manuscript.\n\n> 2.  How does the RMR algorithm ...\n\nAlready addressed above.\n    \n>3.  What potential challenges ...\n\nGenerally, the computational bottleneck in this application stems from the optimization problem, where the computational time increases cubically with respect to the size of the input matrix. In contrast, the computational time for the RMR algorithm grows linearly. Thus, it is crucial to have a sparsification algorithm that yields sparser matrices within a given error tolerance, particularly for real-time applications. We have demonstrated that the RMR algorithm surpasses existing techniques in producing sparser matrices for a specified error threshold. We hope this significant application will ignite a new wave of research in matrix sketching within the ML/AI community and foster accelerated innovation in future techniques. \n\n> 4.  Can the authors provide ...\n\nIntuitively, this approach ensures that the sum of elements in each row remains consistent between the original matrix and its sparsified version. This is intended to maintain nearly the same total radiation exposure to each voxel in both the original and sparsified matrices.\n\nA bit more mathematical justification is that the sparsification algorithms aim to approximate a matrix A by a sparse matrix B while keeping the spectral norm of A-B, defined as below, minimal:\n\n$$ ||A-B||_2 = sup_{||x||_2 \\leq 1} ||(A-B)x||_2 $$\n\nMinimizing the spectral norm effectively minimizes the maximum l2-norm of errors (i.e., $||(A-B)x||_2$) over the unit sphere (i.e., $||x||_2\\leq1$). However, given that the intensities x are non-negative (i.e., $x\\geq0$), it is crucial to focus on minimizing the maximum error within the non-negative part of the unit sphere. Our fixed-point approach means that: $Ae=Be$, where e is a vector of all ones (it also implies $A\\alpha e=B \\alpha e$, for any scalar alpha). This ensures that the l2-norm error is zero (i.e., $||(A-B)x||_2=0$) for  $x=\\alpha e$, meaning the l2-norm is zero on each point on the line conneting the zero origin to $e$ in the non-negaive part of the unit sphere.  Considering the symmetry of this quadrant, this strategy is optimal for minimizing the maximum error when the error is permitted to be zero along a specific line. We can specifically demonstrate that this approach reduces the norm of $||A-B||_2$ by a factor of $\\sqrt \\frac{n-1}{n}$, where n is the dimension of the space to which x belongs.\n\n\n> 5.  What are the potential ...\n \nThe RMR algorithm and its associated optimization processes utilize influence matrix data, which represents the simulated radiation doses delivered to various parts of a patient's body by different segments of the machine (i.e., beamlets). The publicly available influence matrices used in this study are accessible on the open-source [PortPy website](https://github.com/PortPy-Project/PortPy). While this data itself is not sensitive, it originates from CT images, which are sensitive due to their potential to identify patients (it's mainly a concern for head-and-neck and brain dataset that include facial images). Therefore, researchers must strictly adhere to confidentiality protocols, detailed for example in the [NIH Data Usage Policies and Restrictions](https://www.cancerimagingarchive.net/data-usage-policies-and-restrictions/). Additionally, researchers in hospitals, like our collaborators, are required to obtain Institutional Review Board (IRB) approval for using internal patient datasets. \n\n**Limitations:**\n\n> 1.  Potential challenges ...\n   \nAlready addresed above.\n \n> 2.  Discussing the ethical ...\n\nAlready addresed above.   We will clarify in the manuscript. \n\n> 3.  Further exploring the ...\n\nWe acknowledge the importance of this issue. Although we attempted to address it by plotting error on the y-axis and sparsity on the x-axis in Figure 1, we are committed to expanding our analysis in the revision by plotting computational time on the x-axis against several clinically important metrics—such as mean radiation dose to the heart and lungs, and minimum dose to the tumor—on the y-axis.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BLjsfxVgIS", "reviewer": "Reviewer_C2Tr", "summary": "In this work, the focus is on doing matrix sparsification with its application focussed on Cancer Radiation therapy. \n\nThe authors propose a novel algorithm for matrix sparsification which is faster than most other algorithms and simultaneously has a lower feasibility gap and lower optimality gap. \n\nAn interesting feature of the presented algorithm is how the authors explicitly contain the effects of sparsification by making sure the total radiation dose to every voxel (each row in the matrix) as characterized by the sparse matrix remains close to the characterization by the full dose influence matrix.  The authors show the effectiveness of their approach both from empirical results and from the relevant theoretical deductions.", "questions": "This work combines the two ways of doing matrix sparsification. However, the motivation for using the second category is not clear. the authors state that the second category methods require a larger number of non-zero elements, which is a negative feature of them. The sole argument given for the second category is “the second category may be preferable in applications when data is only accessible in a streaming manner”.  It will be useful to have a concrete example. At the very least, it should be made more clear how/why the second category methods work when data is accessible in a streaming manner.", "limitations": "The authors have provided the limitations with adequate depth.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "For a given error, their method allows for a lower nnz (non-zero elements in the matrix), which is better than second-category sparsification methods (but similar to first-category sparsification methods). \n\nHowever,  their method is superior to the first category sparsification methods as well when it comes to feasibility and optimality gap, which they show empirically and theoretically.\n\nThe improved optimality and feasibility can be traced to an interesting feature in their algorithm which they explain nicely. Their algorithm accounts for the effects of sparsification, or, in their words, “preserves the integrity of each row”. For each row, ie, for each voxel, the total radiation dose remains almost the same between the original dose influence matrix and its sparsified version. Additionally, they explain the utility of this aspect of their work for tumor cells (L168-L175) which looks quite compelling.\n\nTheir sampling procedure is time-efficient, in the sense that for each row, one does not need to sample a column many times, as is done in some of the first-category sparsification methods.", "weaknesses": "I do not find any serious weakness.  However, the reviewer does not have the required expertise to check the validity of theorem proofs done in the manuscript. Reviewer leaves this aspect to other reviewers. \n\nIt will be useful to know the optimization runtime when using the original matrix A. Also, it will be useful to know what the acceptable level of relative sparsification RMR achieves, acceptable in terms of the discussed metrics like (relative l2-norm, relative dose discrepancy, etc).\n\nL178-L180: “However, unlike conventional sampling methods, our technique\n179 automatically identifies the optimal number of samples for each row, consistently less than the total\n180 number of columns, eliminating the necessity for tuning sampling parameters”. Please provide a reference of techniques where sampling hparams require a role. \n\nAuthors could work on English at a few places like L184, L66, etc. In L66, “We will use Problem 2..” could be rephrased to “We will use the second formulation (Eq. 2) ”\n\nIn Figure 1, the blue curve is not visible in several sub-plots. The authors are requested to change the line style or something of their preference so that all overlapping plots are simultaneously visible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for dedicating time to review our paper. Our responses to your comments are provided below.\n\n**Weaknesses:**\n\n>It will be useful to know the optimization runtime when using the original matrix A. Also, it will be useful to know what the acceptable level of relative sparsification RMR achieves, acceptable in terms of the discussed metrics like (relative l2-norm, relative dose discrepancy, etc).\n\nWe acknowledge the importance of reporting optimization runtimes when employing the original matrix A. Initially, we omitted this information due to the necessity of running these computations on alternate hardware configurations to address memory constraints. To address this issue, we will add the following table in the Appendix that details the optimization runtimes and explicitly notes the hardware variations used in different experiments. As can be seen, the optimization using the full matrix is about 20 times slower than using the sparse matrix, despite the full matrix optimization problem being performed on a more powerful server.\n\nRegarding the acceptable level of sparsification, clinicians typically assess the level of dose discrepancy by visually inspecting the Dose Volume Histogram (DVH) plots (Figures 6 and 7 in Appendix B). According to our clinical collaborators, the discrepancy is clinically insignificant when the RMR algorithm is applied at a 98% sparsification level, which correlates with a relative dose discrepancy of 2-3%. \n\n| Patient number | Optimization runtime using the full matrix (s) | Optimization runtime using the RMR sparse matrix (s) | RMR algorithm runtime (s)|\n|--|--|--|--|\n| 1 | 2826 | 87.25 | 48.77 |\n| 2 | 3212 | 122.5 | 46.80 |\n| 3 | 2147 | 45.84 | 50.30 |\n| 4 | 1277 | 53.30 | 32.78 |\n| 5 | 870 | 32.17 | 25.33 |\n| 6 | 1447 | 58.25 | 38.26 |\n| 7 | 1492 | 81.47 | 33.65 |\n| 8 | 714 | 29.18 | 23.88 |\n| 9 | 838 | 33.20 | 29.95 |\n| 10 | 1303 | 51.66 | 36.59 |\n\n>L178-L180: “However, unlike conventional sampling methods, our technique  automatically identifies the optimal number of samples for each row, consistently less than the total number of columns, eliminating the necessity for tuning sampling parameters”. Please provide a reference of techniques where sampling hparams require a role.\n\nSure! We will add this to the final version. For instance, [DZ11] algorithm has two hyperparameters: the sparsification threshold and the number of samples. \n\n> Authors could work on English at a few places like L184, L66, etc. In L66, “We will use Problem 2..” could be rephrased to “We will use the second formulation (Eq. 2) ”\n\nThank you for bringing this to our attention. We will ensure that a professional editor from our department reviews and refines the language in the final manuscript.\n\n> In Figure 1, the blue curve is not visible in several sub-plots. The authors are requested to change the line style or something of their preference so that all overlapping plots are simultaneously visible.\n> \nThanks for pointing this out. We will fix it.\n\n**Questions:**\n\n> This work combines the two ways of doing matrix sparsification. However, the motivation for using the second category is not clear. the authors state that the second category methods require a larger number of non-zero elements, which is a negative feature of them. The sole argument given for the second category is “the second category may be preferable in applications when data is only accessible in a streaming manner”. It will be useful to have a concrete example. At the very least, it should be made more clear how/why the second category methods work when data is accessible in a streaming manner.\n\nThank you for pointing this out. In Appendix D of [AKL13], the paper that proposed a second category scheme, an explanation is provided on how sampling methods work when data is accessible in a streaming manner. We will also include this explanation in the revised version. The other usage of the second category in our work pertains to the theoretical guarantee based on Bernstein's inequality, as contributed in the theoretical analysis by [DZ11] and [AKL13].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6NHnnRma05", "reviewer": "Reviewer_hEqB", "summary": "The authors optimize the optimization problem in radiation treatment planning via sparsifying the design matrix generated from beamlines and dose delivery map.", "questions": "* Can you show the radiation dose maps? \n* Is there any dependency on the type of the beamlets?", "limitations": "Are well addressed.", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The authors make an effort to formalize the problem\n* Sparsifying the matrix seems to be a valid approximation", "weaknesses": "* It would have been helpful to show images / the spatial prediction\n* One could argue: Observing that sparse representations can be used for the specific application. I is not necessarily an important contribution to a broader ML / optimization audience. \n* The manuscript feels a bit \"raw\" and would benefit from further polishing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for dedicating time to review our paper. Our responses to your comments are provided below.\n\n**Weaknesses:**\n\n> -   It would have been helpful to show images / the spatial prediction\n\nWe can enhance the comparisons by including representative slices of the 3D dose distribution, as demonstrated in the attached PDF file (please refer to Figure 1 in the 1-page PDF file provided with our responses). While interpreting these data demands some clinical expertise, it is evident that utilizing the RMR sparse matrix, as opposed to a naive sparse matrix, results in reduced radiation exposure to the right lung (visible on the left side of the figure). We initially decided to focused on using 2D Dose Volume Histogram (DVH) plots in our comparisons (see Appendix B), as these are widely utilized by clinicians and effectively summarize the 3D dose information in condensed 2D plots.\n\n\n> -   One could argue: Observing that sparse representations can be used for the specific application is not necessarily an important contribution to a broader ML / optimization audience.\n> -   The manuscript feels a bit \"raw\" and would benefit from further polishing.\n\nThe contributions of this work is twofold: \n\n1) **Introduction of a New Sparsification Algorithm:**  This work presents a novel sparsification algorithm equiped with theoretical guarantees and superior computational performance compared to (AKL13: NeurlPS) and two other comptetive technqiues that used as benchmarks in (AKL13: NeurlPS).  \n\n2) **Novel Application in Healthcare**: This work presents an impactful application of sparsification methods in the healthcare sector.\n\nThis interdisciplinary project emerged from a collaboration between ML/AI scientists at a university and medical physics experts at a hospital. It was inspired by a real-world problem with the hospital's in-house treatment planning system, which currently employs naive sparsification. This system is integrated with the FDA-approved Eclipse system and used in daily clinical practice, however, it leads to concerning discrepancies in dose calculations (these details have been removed from the manuscript for the anonimity reasons). As demonstrated, these issues can be effectively tackled using advanced sparsification techniques developed within the ML/AI community. \n\nWe believe this work is particularly suited for presentation at ML/AI conferences for the following reasons: \n\n1) Randomized matrix sketching has been an active area of research withing ML/AI community and most of the previous sparsification algorithms have been published in ML/AI conferences; this work not only introduces a new algorithm with theoretical gaurantees but also presents a novel application with superior computational performances.\n\n2)  This work has the potential to raise awareness within the ML/AI community about this crucial application, sparking a new wave of research and collaboration that could significantly benefit the medical community, much as the ML/AI community has already enhanced the field of medical imaging.\n\n\n**Questions:**\n\n>-   Can you show the radiation dose maps?\n\nYes, as demostrated in the 1-page .pdf document in our responses.\n\n>-   Is there any dependency on the type of the beamlets?\n\nThe beamlets are 2D elements of a uniform type, and their primary correlation derives from the fact that radiation emitted from neighboring beamlets—those in close physical proximity—results in similar and correlated radiation doses to the patient's body.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
The attached PDF file includes two figures and one table:
Figure 1: The dose map provided in response to Reviewer 4 (hEqB).
Figure 2 and Table 1: The results for a prostate case provided in response to Reviewer 2 (oYrg).

Meta-review: The submission presents a radiotherapy planning optimization strategy based on sparsified optimization.  This generated diverging opinions among the reviewers based on the relevance of optimization (primary concern of reviewer rbxv) and the radiotherapy planning task (primary concern of reviewer hEqB) for the NeurIPS community.  In principle, I am of the opinion that both sparse matrix optimization and radiotherapy planning can fall within the areas of interest for the conference.  Therefore, the criteria should be: theoretical and empirical rigor, appropriate limitations discussion with respect to clinical implications, and inclusion of relevant results.  In each of these areas, it appears that the submission can be considered acceptable and interesting to (a subset of) the NeurIPS community.  I therefore on the balance recommend acceptance based on the two positive reviews, the inadmissibility of the arguments of reviewer rbxv about optimization being off topic, and the comments from reviewer hEqB stating that their concerns are primarily about the topic of the submission and not its soundness.  The ethical reviews have largely not found issues, but highlighted additional opportunities for improving significance reporting.  Reviewer hEqB has requested that dose map information be included in a camera ready version.  I also request that the authors very carefully review the limitations section and highlight that the review process was performed for the ML/AI community, and is not a clinical review.  Any further work towards clinical application should be subject to appropriate validation studies focused on clinical effectiveness and potential negative impacts of the plans selected by the sparse optimization strategy.
Decision: Accept (poster)