Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations
Authors: Edward Raff
Amol Ashish Khanna
Fred Lu
Venue: NeurIPS 2023 poster (2023)
Keywords: Sparsity
Differential Privacy
Regression
TL;DR: We improve the efficiency of the Frank-Wolfe method for sparse differentially private regression on sparse high dimensional datasets.

Abstract: To the best of our knowledge, there are no methods today for training differentially private regression models on sparse input data. To remedy this, we adapt the Frank-Wolfe algorithm for $L_1$ penalized linear regression to be aware of sparse inputs and to use them effectively. In doing so, we reduce the training time of the algorithm from $\mathcal{O}( T D S + T N S)$ to $\mathcal{O}(N S + T \sqrt{D} \log{D}  + T S^2)$, where $T$ is the number of iterations and a sparsity rate $S$ of a dataset with $N$ rows and $D$ features. Our results demonstrate that this procedure can reduce runtime by a factor of up to $2,200\times$, depending on the value of the privacy parameter $\epsilon$ and the sparsity of the dataset.

Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations
Edward Raff" Booz Allen Hamilton waff_edvard@bah.cm com
Amol Khanna" Booz Allen Hamilton
Fred Lu Booz Allen Hamilton fu_ffre@bahh.om com
khanna_am amo momo@bbhh.. com
Abstract
To the best of our knowledge, there are methods today for training differentially private regression models on sparse input data. To remedy this, we adapt the Frank-Wolfe algorithm for L1 penalized linear regression to be aware of sparse inputs and to use them effectively. In doing so, we reduce the training time the algorithm from OTDS + S) to O + TVD D log D + T where T' is the number of iterations and sparsity rate S of a dataset with N rows and features. Our results demonstrate that this procedure can reduce runtime by a factor of up to 2, x00x, depending the value of the privacy parameter and the sparsity of the dataset.
1 Introduction
Differential Privacy (DP) is currently the most effective tool for machine learning practitioners and researchers to ensure the privacy of the individual data used in model construction. Given parameters and 6, on any datasets 'D and D' differing private randomized algorithm A satisfies Pr [A(D) E O] S exp(c) Pr [A(D') E O + 5 for any O C (A)
example, an (approximately) differentially
[ Note that lower values of and 6 correspond to stronger privacy.
While DP has had many successes in industry and government, DP-based machine learning methods have made little progress for sparse high-dimensional problems 3 5 We believe that this issue arises because, to the best of our knowledge, given a dataset with D features and a training algorithm with T iterations, all current iterative DP regression algorithms require least O(TD) training complexity, as shown in Table 1} This makes it impractical to use these algorithms on any dataset with large number of features. Our solution to this problem is take already existing algorithuss, and remove all redundant computations with mathematically equivalent steps. This ensures that, by construction, retain all proofs of correctness but end with faster version of the same method.
Table 1: A summary of prior methods for solving L1 regularized Logistic Regression, which do not take advantage of sparsity in the input data.
Method
Complexity
Frank- Wolfe Methods
6
O(TND) O(TNDM) O(TND) O(TND) O(TNDM)
ADMM
[10
Iterative Gradient Hard Thresholding Methods
9
Coordinate Descent
13
Mirror Descent
"Co-first authors for equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We are interested in creating differentialy private machine learning algorithm which scales to sparse datasets with high values of D, we look toward the LASSO regularized logistic regression model 14]. Specifically, given a dataset (x1,..., XN) E RDD which can be represented as design matrix X NxD, {Ui,..., UN E {0, 1), and a maximum In norm X, we wish solve
N
1
W arg min WERP: [wwl N L(w x;)
Σ i=1
where L() is the loss function. In this paper, we will use the logistic loss to avoid exploiting any closed-form updates/solutions in the linear case, but our results are still applicable linear regression. To do so with DP, we use the Frank-Wolfe algorithm as it well studied for L1 constrained optimization and regularly used in DP literature properly initialized. its solutions will have at most T nonzero coefficients for T training iterations. Though DP noise can reduce accuracy and cause increased density of solutions through suboptimal updates, when considering problems with more than I million features, we are unlikely to perform 1 million iterations, so benefit is still obtained 17
[S] [6]. Trank-Wolff is also desirable because when
We develop the first sparse-dataset friendly Frank- Wolfe algorithm to remediate the problem of no sparse algorithms for high-dimensional DP regression. Because sparse-efficien Frank-Wolfe algo- rithm does not exist today even for non-private problems, our work proceeds in three contributions:
1. We analyze the numerical updates of the Frank-Won algorithm separate the task into (a) "queue maintenance" for determining the next coordinate to update and (b) sparse updates of the solution and intermediate variables. If the average column sparsity of X is S. < D and the average row sparsity of X is S, < N, we show for the first time that Frank Wolfe can update its solution in S,S. work per iteration.
2. We show that in the non-prin con-private case, the queue to select the next coordinate can be maintained in (l log D) time, but is cache-unfriendly.
3. Finally, we develop new Big-Step Little-Step Sampler for DP Wolfe that can be maintained and sampled from in OVVD log D) time.
We test our algorithm on high-dimensional problems with up to 8.4 million datapoints and 20 million features on a single machine and find speedups ranging from 10x to 2, x00 that of the standard DP Frank-Woll Wolfe method. Critically, our approach is mathematically equivalent, and so retains all prior proof's of correctness.
The remainder of our work is organized as follows. In section 2 we will review related work in more detail and discuss the lack of sparse dataset algorithms for Frank- Wolfe and DP. Next, we develop the nonprivate and DP variants of our sparse-friendly Frank- Wolle in /eeetttnn 3 In ssscttiionn 4 we demonstrate the empirical correctness of our algorithm, a speedup in runtime for the DP case, and new state-of-the-an accuracy in high-dimensional logistic regression. Finally, we conclude in section 5
2 Related Work
As best as we can find, no works have specifically considered a sparse-dataset efficient Frank-Wolfe algorithm. Additionally, we find that work studying L Leegulllrrde DP regression has not reached any high-dimensional problems. Our work is the first to show that Frank- Wolfe iterations can be done with complexity sub-linear in D for sparse datasets. It also produces a sparse weight vector.
For DP regression, the addition of noise each variable has limited exploration of sparse datasets. Most works study only one regression problem with less than 100 dense variables or are entirely theoretical with no empirical results IT 10 6 [8] 19]. To the best of our knowledge, the largest scale attempt for high-dimensional logistic regression with DP is by Iyengar et al., who introduce an improved objective perturbation method for maintaining DP with convex optimization [6]. This required using L-BFGS, which is O(D) complexity for sparse data and produces completely dense solution vectors w 20 In addition, Wang & Gu attempted to train an algorithm on the RCV1 I dataset but with worse results and similar big-O) complexity to lyengar et al. [1]. While Jain & Thakurta claim to tackle the URL dataset with 20M variables, their solution does so by sub-sampling just 0.29% of the data for training and 0.13% of the data for validation, making the results suspect and

---

non-scalable [21]. Lastly, a larger survey by Jayaraman & Evans shows no prior work considering the sparsity of DP solutions and all other works tackling datasets with less than 5000 features [2]. In contrast, our work does no sub-sampling and directly takes advantage of dataset sparsity in training high-dimensional problems. Our use of the Frank-Wolfe algorithm also means our solution is sparse, with no more than T non-zero coefficients for T iterations.
In addition to no DP regression algorithm handling sparse datasets, we cannot find literature that improves upon the O(D) dependency of Frank-Wolfe on sparse data. Many prior works have noted this dependence as a limit its scalability. and column sub-sampling approaches are one method that has been used to mitigate that cost (23 TS 24]. Others have looked at distributed Map-Reduce
implementations [25] or adding momentum terms [26] as means of scaling the Wolle
algorithm. However, our method is the first to address dataset sparsity directly within the Frank-Wond
algorithm, and can generally be applied to these prior works with additional derivations for new steps. Other methods that apply to standard regression, use the L2 penalty [27] 28 would require modification to use our approach. Similarly, pruning methods 29 may require adaption to account for the privacy impact.
Of particular note is [0] which tackles sub-linear scaling in the number of rows N when N >> D, but is primarily theoretical. Their work is the first to introduce the idea of "queue maintenance" that we similarly leverage in this work. Despite a conceptually similar goal of using a priority queue to accelerate the algorithm, [30] relies on maximum inner product search, where our queues are of a fundamentally different structure.
To the best of our knowledge, the COPT library is the only Frank- implementation that makes any effort support sparse datasets but is still ((D) iteration complexity, so we base our comparison against its approach [31]. No DP regression library we are aware of supports sparse datasets [32].
3 Methods
Throughout this section, sparsity refers to an algorithm's 's awareness and efficiency of handling input data which contains mostly zero values. We will first review the only current method for using Frank- Wolfe with sparse data and establish its inefficiency. We will then detail how to produce generic framework for a sparse dataset efficient Frank- Wolfe algorithm using a queuing structure to select the next coordinate update. Having established sparse friendly framework, we will show how obtain ONNS, T||w"|lo Ilo log D + SS)) complexity for the non-private Frank-Wor Fibonacei heap, where w' is the solution at convergence. Then replace the Fibonacci heap with sampling structure to create DP Frank-Wolfe algorithm with O(NS, + T TVD log D S.) complexity.
algorithm by using
Algorithm 1 Standard Sparse- Aware Frank- Wolfe
3.1 Frank- Iterations in sub-O(D) Time
1: Wo f- 0
The only work we could find of any pparse-inpur aware Wolle implementation is the COPT li- brary, which contains two simple optimizations: it pre-computes re-used dense vector (i.e., all values are non-zero) and it uses sparse matrix format for computing the vector-matrix product X w (3I] The details are abstracted into Algorithm I where each line has a comment on the algorithmic complexity of each step. Note to make the algorithm DP, we have
2: y <- XTy
O(NS.)
3: for \ =1 7 - do
4: V: + -ww
(NN)))
q VL(v:)
O(N)
Z, t- XT qi
O(N).)
7: a t 2; y
O(D)
Aly /LyST log I
arg min, at + Lap
No
added +Lap
XL / (0g(1/8)
to draw noise from
O(D)
Ne
d, Wt
O(D)
zero-mean Laplacian distribution with the specified scale, where is the constraint parameter and L is the L1 Lipschitz constant of the loss function C(.). If a non mon--rivate Frank- Wolfe implementation is desired, this value can be ignored.
10: (1) + d(1) - - sign
(1)))
at
(1)
0(1)
11: gt = - de)
O(D)
12: Ti F2
0(1)
13: w = w. + ne
((D)
14: end for
In this and other pseudo-codes, we explicitly write out all intermediate computations as they are impor-
15: Output WT
3

---

tant for enabling sparse updates. y is an intermediate variable for the labels in the gradient of a linear problem that is pre-computed once and reused. is a temporary variable. q and a are the gradients with respect to each row and column respectively. v the dot product of each row with the weight vector, and is the update direction. The iteration subscript will be dropped when unnecessary for clarity. The superscript (j) denotes updating the j "th coordinate of a vector and leaving others unaltered.
While lines 2, 4, and 6 of the algorithm exploit the sparsity of the data, this only reduces the complexity to ((NS.) plus an additional dense ((D) work for lines 7 through 13 and O(N) work for line 5. This results in final complexity of O(TN Sc + T DD). For high dimensional problems, especially when N' & D, this is problematic in scaling up a Frank- Wolfe based solver.
To derive a Frank- algorithm that is more efficient on sparse datasets, we will assume there is an abstract priority queuing structure Q that returns the next coordinate to update j for each iteration. We will detail how to design Q to use this algorithm in non-private and DP cases in the following two sections.
Sparse w, Updates
Algorithm 2 Fast Awarse-Aware Frank-Wolfe for Linear Models
In line 13 of of|Aoooiihhm I] if we ignore the change
1: w <- 0
coordinate j of d,, we can write Wt+1 = We W.
2: Wm f 1
which can be re-written as Wx+1 = (1 - 1/) Wr. If we represent the weight Wx+1 = w Wm with a co-associated multiplicative scalar Wm. we can alter Wm 6 Wm (1 - 7t) to have the same effect as alter- ing all D variables implicitly. Then the 7th coordinate can be updated individually, allowing line 13 Af gorithm to run in (11) time. We will use the same trick to represent V. V Wm as it has the same multiplicative scale.
3: 9 0
4: y + X
O(NS.)
scale +
LNO
2 ST (og(1
6: Q + Priority Queue or Sampling Algo-
rithm
7: for t = 1 to T - 1 do
if 1 then
9: v + Xw
((NS))
10:
q f VL(v)
O(N)
11:
X q
O(NS))
Sparse a and v Updates
12:
a + z
O(D)
13: Q.add(i, |a
scale) V j E
The dot product scores V. and column gradients at are intrinsically connected in their sparsity patterns. When the 5th value of w, is altered, multiple values of V. change, which propagates changes to the gradients Qg However, the elements {i} of V. that change are only those where rows {i} in X use feature j. Let d, represent a perturbation to the j'th update direction. Each row that uses the j'th feature will then be alter the variable ((() by -n [i, j]. This lets handle line 10 sparsely.
[I,..., D}
O(D)
14: end if
15:
+ Q.getNext()
Select coordinate
to update
16: d t - sign (ali)
(())
17: Ir t g d a15)
(1)
18: To = i+2
(())
19: wm + wm (1 - 11)
20: wi)) + w((i mi Wm
21: x 5(1 me) + (
Each row {i} that changes in Ve propagates to the values in q. We can represent the change in gradient value between iterations as y, which can then be used to sparsely update the a values by noting that X q would change only by the non-zero columns of X(i. So we can compute the update a by :(ē By updating a directly, we do not need account for the contribution of y after the first iteration.
22: for all rows of X with feature j do
(
23:
g(1) + 5(1) + nid x[ii Wm
((1)
24:
7 7 V[(wm ((()) g(5)
(1)
25:
((1) + -li) +
((1)
26:
a + a + [i.
(S.)
27:
ğ + Ā + y X [i,
w Wm
O (Sa)
28:
end for
Sparse di Updates
29: Quuddate (k,, [a( scale) V k gradi-
ents updated
The final variable of interest the Frank- Wolfe con- vergence gap 9. = -a, d, Instead of recomputing this every iteration, we can keep a base value ğ that is altered based on both of the prior two insights.
30:
end for
31: Output w
When W.n is updated, we re-scale by (1 Th) and add na (1), the change in the dot product
4

---

-a, dj caused by just the jth coordinate update. After the sparse a updates, I is again updated by y x(i,;
Fast Frank-Wolfe Framework
The final procedure that forms the foundation for our results is given in Algorithm 2 The scale variable holds the noise parameter required for DP and can be ignored for non-private traming. Lines 6, 13, 15, and 30 require abstract priority queue that is populated with values proportional each feature's 's gradient. This mechanism is different in the non-private and private cases, and we will detail them in the following two sections.
The first iteration of Algorithm performs the same calculations as Algorithm but for all subsequent iterations, values will be updated in sparse fashion.
Lines 16-21 update the multiplicative Wm variables and perform the single coordinate updates to w and g. all taking (1) time to complete. Lines 22-29 handle the updates for a and v. which requires looping over the rows that use feature j. which we expect have ((S,) complexity. Within the loop, we use one row of the matrix to perform a sparse update which we expect to have O(Sz) complexity. The gradients a (*) that get updated by this loop are updated in the priority queue Q in (1) time per update, so they do not alter the final complexity. The final complexities of our algorithm are now
dependent on the complexity of Q.getNext(), which will differ in the non private and private cases.
3.2 Algorithmically Efficient Non-Private Frank-Wolfe
We first analyze the complexity of the non-private Frank- Wolfe algorithm, though our ultimate goal is to make the private case more efficient. The algorithm we detail in the non- con-private case will be of superior big-O complexity and perform significantly less FLOPs than the standard Wolle implementation but will not be faster in practice due to constant factor overheads which we will explain.
The primary insight in building an algorithmically- faster non-prin non-private algorithm is to use Fibonacci Heap, which allows for (log D) removal complex- ity and amortized (1) insertion and decreasekey operations. We use the negative magnitude as the key decrease key j whenever [a) increases, and ignore cases
Algorithm 3 Fibonacci Heap Frank-Wolfe Queue Maintenance
1: function GETNEXT(
2:
-+-11
Assume (-(-
returns -00
repeat
in the min-heap. Our insight is that
4:
c Q.pop()
Ollog D)
5:
if [a(e] >> | then
where | decreases. This means the negative pri- ority is an upper bound on true gradient magnitude. This is favorable because the vast majority of updates to the queue are intrinsically of a magnitude too small to be selected (hence why the solution is sparse) and so even with an inflated magnitude are never top of the queue.
j +-c c
7: end if
until | > (Q.peekProoitty)
Re-insert removed items using prior-
ities (e....)
10: Output j
11:
end function
These stale gradients will cause some items to reach the top of the queue incorrectly, which is easy to resolve as detailed in |Algorithm 3) The current item is popped off the queue, and compared against the current best coordinate j. This loop continues until the top of the queue has a smaller priority than the current gradient magnitude at)) Because the stale magnitude can only be larger than the true gradient, once we satisfy this condition it must be the case
12:
function UPDATE(Í. v)
13:
Vear + Current priority of item i
14:
if -f-rrer > - then
Min-Heap ((1)
15: QdecreassKey(i, v)
16: end if
17:
end function
that no item in the queue can have a higher priority. Thus, the procedure is correct.
The number of items we expect to have to consider must be proportional to the number of non-zero coefficients in the weight vector. This gives final complexity of getNext O[] (lo) for the number of non-zeros in the final solution, multiplied by the (log(D)) cost per pop () call, giving a final complexity of O(NS. + T[ lo log D + S.)
'There are multiple ways to implement this, but we find naive re- re-iteration over the loop to update based on the tinal values the fastest due to reduced memory overheads.
5

---

While this is of superior algorithmic complexity compared to the standard Frank- Wolfe implementa- tion, it has been long known that Fibonacci heaps have high constant-factor overheads that prevent their practical use [3 34 We still find the result useful in being the first to demonstrate faster iteration speed, as well as a deterministic case to verify the correctness of our approach. For this reason we will use Algorithh t show that our method converges at the same rate and with fewer FLOPs compared to the standard Frank-We -Wolfe implementation, as it does not suffer from the ran- domness required for differential privacy Our concern about this inefficiency is limited, as many faster algorithms exist for non-private LASSO regression that are orders of magnitude faster than using Frank- Wolfe [35 36 37,, so other tools can suffice. However, tools for nigh-dimensional and sparse DP LASSO regression exist except for the Frank- Wolfe method, which we make more efficient in the next section.
3.3 Algorithmically Efficient Differentially Private Frank-Wolf
For our DP Frank Wolfe algorithm, we con- vert from the Laplacian mechanism orig- inally used by Talwar et al. to the Ex-
Algorithm 4 Big-Step Little-Step Exponential Sampler
1: function GETNEXT()
2: -+0
ponential Mechanism (38]. Rather than adding noise to each gradient and selecting
3:
o + @xexp(v() 2x.)
4: log'Tw
log ((0.))
the maximum, in the exponential mecha- nism each coordinate j is given a weight x exp
exp vlt) -25
c+0
6: while e < N do
2An where u(j) the score of the jth item and Au is the sensitivity (39
eu(p))
7:
X f- 1ng2((0.1) logT=
8: while exp (cle mod IvN 23 -0 < Xw do
This poses two challenges:
N X (exp (cle mod [vN]) -3.) 0)
9:
1. We need to select a weighted ran- dom sample from D options in sub-O(D) time to pick the corrdi- nate j to maintain the DP of the exponential mechanism.
10:
o+
11:
ct [NJ mod IVN
12:
end while
13:
while exp (v(c) 2④x)
<
X do
O OVN
2.
We need to do this while avoiding the numeric instability of raising a gradient to an exponential, which will overflow for relatively small gradient magnitudes.
14:
X + X - -epp (vlc) - 233))
15:
o + o exp (v(r) - -25.)
16:
e ++++1
17:
end while
18:
if < N then
19:
jtc
We tackle both of these issues by adapting
20:
c+c
the A-ExpJ algorithm of [40]. and use their
21:
tw f- exp (exp -2)) llogT
naming conventions to make comparison
casier. This algorithm works on stream 22:
logIT + exp (v5) -2x))
((t.)()
of items with weights Wi, and in ((1)
23:
j mod IVN + 0 then
space can produce valid weighted sample
24:
o o+0
from the stream. It does so by computing 25:
else
randomized threshold Th and process-
26:
o--o o-o exp (v(5) 23)
ing samples until the cumulative weights
27:
end if
L, wi Tw, which the final item in the sum becomes the new sample. A new
28: end if
29: end while
value of Ta is computed, and the process
30: end function
continues until the stream is empty. This process requires generating only (log D) random thresholds for a stream of D items.
31: function UPDATE((, 2)
32: Veur + current priority of item
33: ke k+i mod [VN]
We exploit the fact that we have known and fixed set of D items to develop a new version of this algorithm that can be up- dated in constant time, is numerically sta-
34: c(k) < c(k) log (1 venr oli-) + e
35: 25: +- zy: + log (1 2ar oy ev-25)
36: end function
'e note that there can be mild disagreement on update order caused by numerical differences in brute-force recalculation of Algorithm I and the updates of Alggorihhm 2 but we observe issues with this.

---

ble for wide range of weights, and can draw a new sample in log D) time. The key idea is to form large groups of variables and keeping track of their collective weight. the group's weight is smaller than Tw. then the entire group can be skipped to perform a "Big-Step". If the group's weight is larger than Tw. then the members of the group must be inspected individually to form "Linte-Steps"" For this reason we term our sampler the "Big-Step Little-Step" sampler, and this procedure is shown in Algorrthh 4
The scale of gradients can change by four or more orders of magnitude due to the evolution of the gradient during training and the exponentiation of the Exponential Mechanism. For this reason, all logic is implemented at log scale, and a total log-sum-weight zσ is tracked. Every exponentiation of a log-weight then subtracts this value, performing the log-sum-exy trick to keep the sample weights in numerically stable range" [
Similarly, each group has group log-sum weight, and we denote the vector of the group weights as There are vD groups that each group has vD members. On lines 34 and 35 of Algorithm 4 log-sum-exp update is used to update the group sum c(*) and total sum 2g (which are already log-scale since there was no exponentiation on line 30 of Algoorti 2). In both cases we always expect the group sum to be larger, and so we use c(*) and zy as the maximal values to normalize by in each update. Lines 31 and 32 select the "Big-Step" group to update for the change in weight of the i'th item.
Lines 8-12 and 13-17 perform the same loop at two different scales. 8-12 perform big steps over groups, and must handle that the starting position could be the middle of group from a previous iteration, making it partial group. For this reason, there is a "group offset" o that subtracts the weight of items already visited in the group. Once a Big-Step made, on line 11 the position is incremented by the group size modulo the current position, so that each step starts at the beginning of the next group regardless of starting position, handling the case of starting from a previous little step's 's location. Then lines 13-17 perform little steps within a group, and it is known that a new item must be found in the little group, otherwise, lines 8-12 would have repeated due to having a sum smaller than Tw..
The remainder of lines 2-5 and 18-30 work as the standard A-ExpJ algorithm, except each calculation. is done at scale or exponentiated if an item is needed at a non-log scale, for example on line 2
Each of the log(D) (D) random variates needed by Algorithm 4 corresponds to the selection of new current sample. In the worst cases, each of these samples will helong to a different group, necessitating exploring O (log D) groups each of size / D by construction, giving a total sampling complexity of OVDD log D). Just as with the Fibonacei Heap, the update procedure is O(1) per update, and so the final DP-FW complexity becomes O(NS. T log D + TS, As we will demonstrate in our results, this provides significant speedups over the standard Frank- Wolfe for sparse datasets. This is because, by design, the /lgoorihh 4 proceduuee is very cache friendly, performing linear scans over vD items at time making pre-fetching very easy, and thus has only Ollog D) cache-misses when performing Little-Step transitions.
4 Results
Table 2: Datasets used for evaluation. We focus on cases that are high-dimensional and sparse.
Having derived a sparsity-aware framework for implementing Frank-Wolfe iterations in time proportional to the sparsity of the data, we will now demonstrate the effectiveness of our results. Since our goal is to support faster training with sparse datasets, we focus on high-dimensional problems listed in Table 2 where D 2 N. Note that to the best of our knowledge, the RCVI dataset at
Datuset
N
D
RCVI
20,242
47,236
20 Newsgroups Binnary "News20"
19,996
1,355,191
Malicious URLs, "URL" Webh Spam Corpus, "Weh" KDD2010 (Algebra), "KDDA"
1,39
3,231.961
350,000
16,609, 143
8,407,752
20,216,830
*Very small weights will still underflow, hut by definition this happens when their probability to be selected is several orders of magnitude lower and thus are astronomically unlikely to be chosen anyway. Adding a small 10 value guarantees a chance to be selected and maintains DP via technically adding more noise than necessary.
'We note that the double exponentiation on this line is correct and numerically stable. The first exponentiation will produce value in the range of (0, 1] for the second exponentiation to use per the A-ExpJ algorithm
7

---

D = 47k is the highest-dimee dithees-dimessoonll dataset any prior work has used to train a DP logistic regression model [16], and its D is 428x smaller than the largest D we consider.
Our results will first focus on the non-private Frank- Wolfe due to its deterministic behavior and clear convergence criteria via the Frank-Wolfe gap o This will allow show clearly that we reduce the total number of floating point operations per second (FLOPs) required, though we note that in practice the runtime remains similar due cache inefficiency.
After establishing that Algorithm 2) requires fewer FLOPs, we turn to testing the DP version leveraging Big-Step Little-Step Sampler Algorithm 4, showing speedups ranging from 10x to 2, x that of the standard DP Frank Wolfe algorithm when training a model on sparse datasets.
Due to the computational requirements of running all tests, we fix the total number of iterations T = 4, 000 and maximum L1 norm for the Lasso constraint be X datasets. This value produces highly accurate models in all non-private cases, and the goal of our work is not to perform nyper-parameter tuning to demonstrate that we have taken an already known algorithm with established convergence rates and made each iteration more efficient. All experiments were run on a machine with CPU cores (though only one core was used), and 128GB of RAM. The total runtime for all experiments took approximately I week and exploring larger datasets was limited purely by insufficient RAM to load larger datasets in memory. Our code was written in Java due to the need for explicit looping, and implemented using the JSAT library [36]. When comparing Algorithm and our improved Algorithm 2] the latter will be prefixed with "-Fast" in the legend to denote the difference.
in all tests across all
4.1 Non-Private Results
We first begin by looking at the convergence gap Ir over each iteration confirm that we are converging to the same solution, which is shown in Figure I Of note, it is often impossible to distinguish between the standard and our fast Frank- Wolfe implementations because they take the exact same steps. Differences that occur are caused by nearly equal gradients between variables and are observable via inspection of gs- all cases, the solutions returned achieve identical accuracy on the test datasets.
Alg.
Alg. 2 + Alg. 3
10a
10a
Convergence Gap St
100
100
1
10
10
10-4
10a
10
102
103
10a
10
102
103
Iteration
Iteration
KDDA
URL-
RCVI-Fast
KDDA
Figure 1: Convergence gap gr (y-axis, same scale for both plots) as the number of iterations increases (x-axis), showing that our Algoortti 2 (dotted lines) converges to the same solutions as Algorithh I with minor differences due to numerical floating point changes (i.e., both plots look nearly identical, the desired behavior). This shows our new approach maintains solution quality.
In Algorithm 2 the updating in differences can cause catastrophic cancellation due to the zig-zag zag behavior of Frank- Frank-Wolfe iterates (updating the same coordinate j multiple times with differing
'In the DP case is especially noisy and hard to leverage meaningfully, often starting lower and increasing. This makes it pon-infen innforrrrteeve measure

---

signs on each update). resulting in similar magnitude sign changes that result in slightly different results numerically compared to re-compuing the entire gradient from scratch. Choosing an adaptive stepsize 'it may alleviate this issue in future work.
Next, we empirically validate the [[I]=* llo)
FLOPs(Alg LY/FLOPS(AIg & 3)
103
number of times we must query the Fibonacci Heap for selecting the next iterate. The ratio of
the number of times we must pop an item from
the Heap against the value of w llo is plotted over training iterations in Appendix Figure 3 We can see in all cases the ratio is < 3, and so few calls to the heap are necessary.
10a
Finally, look the convergence rate Ie as a function of the number of FLOPs required to obtain it, shown in Figure It clear that we
10a
avoid orders of magnitude more operations than naïve implementation of Frank-Wolf would normally require, providing the foundation for our faster DP results in the next section. Unfor- tunately, the Fibonacci Heap has poor caching behavior, resulting no meaningful difference in runtime for the sparse case.
10
100
10
102
10
Iteration
URI
KDDA
4.2 Differentially Private Results
Figure 2:
The y-axis (larger is better) shows how many times fewer FLOPs our Alg. 2 + Alg 3 needs compared to the original Frank-Wolf (Alg. 1). The x-axis is how many iterations into training have been performed. Note that in all cases the dif- ference is difficult to differentiate reaching 1,000 iterations as we reduce the number of FLOPs by orders of magnitude per iteration.
Having established that Algorithm avoids many floating point operations by exploiting sparseness in the training data, we now turn to training DP versions of the normal and our faster Frank- Wolfe algorithms. The total speedup in the runtime of our Algorithm 2] ovver/Aloorithm 1 shown in Table 3] As can be seen, our results range from a 10x speedup for the URL dataset at the low end, up to 2, x speedup for the KDDA and URL datasets at 0.1. In addition ablated using Algorithm 2 with the brute force noisy-max as an ablation, which shows smaller speedups. This demonstrates that the combination of Algorithms 2 and are necessary get our results.
Table 3: How many times faster our Algorithm 2 Algorithm 4 over the standard FW implementation. In addition, just Algorithm 2 using the noisy-max sampling is included as an ablation, showing that both Alg. 4 & 2 combined are necessary obtain maximum speed.
E1
60.1
Dataset
Alg. 2+4
Alg.
Alg. 2+4
Alg, 2
News20
81.69
17.83
93.51
19.05
URL
9.99
1.02
2451.80
95.58
RCVI
19.44
1.36
20.37
1.82
Web
581.25
21.24
537.65
20.79
KDAA
1239.64
206.50
2245.56
368.96
We note that the speedup of our method is function of the sparsity of informative and non- informaaiie features. This is more noticeable on the URL dataset which jumps from a 10x speedup to 2, 400 speedup when moving from E down features that are highly informative, and the remaining features are all sparse. When a feature is dense, there is no advantage to using Alg. 2 & 4, and so no benefit is obtained. At the lower noise level of e = 1, the denser (and thus slower) informative features are selected more frequently, resulting in longer total runtime. As the noise increase with e = 0.1, the sparser non-informative features are selected more often, which reduces the average amount of work per update. This phenomena occurs in most datasets as denser features intrinsically have more opportunities to be discriminative, but uniquely pronounced on the URL datasct.
0. This is because the URL dataset has 200 dense

---

This is ultimately a desirable property of our method, as large values of e > 10 are effectively not private, and so faster methods of non-private training should be used instead. Our Oug/Aihg 2 with the Big-Step-Liitle-SSee amount of privacy increases.
Sampler of Algorithm 4) will increase in its effective utility as the desired
Table 4: Even at high privacy e = 0.1 we obtain non-triwe trivirivill Accuracy and AUC on most datasets by using 7 400, 000 iterations. Because the datasets high dimensional, we still obtain sparse solutions (rightmost column).
Dataset
Accuracy (%)
AUC (%)
Sparsity (%)
RCVI
90.53
97.29
5.81
News20
92.37
98.65
75.19
URL
73,23
82.60
89.44
Web
75,42
92.51
99.90
KDDA
85.25
53.31
85.30
As our final test to highlight the utility and importance of our approach, we re-run each dataset using 5000 with T 400, 000 iterations at real-world useful 0.1. As shown Table 4 this results in non-trivial accuracy and AUC for all datasets but KDDA, and is only possible by performing hundreds of thousands training iterations. Iyengar al. 16 show the best prior results at 0.1 for RCV1 64.2% accuracy, and in fact, we trail the non-private accuracy of 93.5% by only 3% points (note as well that their solution has 0% sparsity). This is made possible by simply performing far more iterations, which computationally intractable with prior methods. We also note that we obtain significant sparsity on the higher dimensional datasets News20, URL, Web, and KDDA due to the fact that T < D for each of them, and the Frank- Woofe will by construction have number of non-zero coefficients < T.
5
Conclusion
We have developed the first DP training procedure that, for sparse input dataset, obtains a training complexity that is sub-linear in the total number of features D at O(NS + TVDDog log D + Sc). Testing on multiple high-dimensional datasets, we obtain up to 2, 200 speedup, with increasing efficiency as the value of decreases. Using this speed efficiency, we show non-trivial accuracy and privacy at e = 0.1 for 352x more features than ever previously attempted and improve accuracy compared to prior work by absolute 26.3%.
References
[1] Cynthia Dwork. Differential privacy. In 33rd International Colloquium on Automata, Languages and Programming, part II (ICALP 2006), volume 4052 of Lecture Notes in Computer Science, pages 1-12, July 2006.
[2] Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. Privacy: Theory meets Practice on the Map. In 2008 IEEE 24th International Conference on Data Engineering, pages 277-286, April 2008. 2375-026X.
doi: 10. 10.1100//CD 4497436. ISSN:
[3] Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Scunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad. LinkedIn's 's Audience Engagements API: A Privacy preserving Data Analytics System Scale, November 2020. URL http://arxiv org/abs/ http//bb/2002..5555 arXiv:2002.0583 [cs].
[4] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized Aggregatable Ordinal Response. Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS 14, pages 1054-1067 New York, NY, USA, November 2014. Association for Computing Machinery. ISBN 978- -4083-9-50--9 10.1145/260026726666222 URL https: ://p:::///oi.. /oi. org 10. 2660267 2660348
doi:
10

---

[5] Amol Khanna, Vincent Schaffer, Gamze Gürsoy, and Mark Gerstein. Privacy preserving model training for disease prediction using federated learning with differential privacy. In 2022 44th Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC), pages 1358-1361. IEEE, 2022.
[6] Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly optimal private lasso. Advances in Neural Information Processing Systems, 28, 2015.
[7] Raef Bassily, Cristobal Guzman, and Anupama Nandi. Non-euclidean differentially private stochastic convex optimization. Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 474 499. PMLR, 15-19 Aug 2021.
[8] Hilal Asi. Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimiza- tion: Optimal rates in geometry. In ICML, 2021. URL https://arxiv. http://aaxivv....a////// hatg//bb/2200 2b03 2103 01516
[9] Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41 ACM SIGMOD- SIGACT-SIGAT Symposium on Principles of Database Systems, PODS '22, page 227-236, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392600, doi: (0.114//5117044354441 URL https::/doi..ooo 10. 11...11111141743522421111
[10] Puyu Wang and Hai Zhang. Differential privacy for sparse classificatton leamingg, Nearocompul- ing, 375:91-101, January 2020. ISSN 0925-2312. doi: 10. 10.1016/j..euccom22111...
URL
[11] Lingxiao Wang and Quanquan Gu. Differentially Private Iterative Gradient Hard Thresholding for Sparse Learning. pages 3740-3747, 2019. doi: 10.249633ijcai22219/559 URL https
//www. w/wp.jjcaa.ooggproceeieieeeeeeie httpa/////...o.cceaa////////////
[12] Lingxiao Wang and Quanquan Gu. A knowledge transfer framework for differentially private sparse learning. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):6235 6242, April 2020. doi: 10. 10.1669/aaai.voo v34:04.6694 URL httpa://doi..rgg///// v34104.600 6090
/aaai
[13] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private Convex Empirical Risk Mini- mization and High-dimensional Regression. In Proceedings the 25th Annual Conference Learning Theory, pages 25.1 1-21.40. JMLR Workshop and Conference Proceedings, June 2012. URL htkLLtttps//prrceddnng mlr. www.prresssseee v23 wiferll..efee.. html
ISSN: 1938-7228.
[14] Robert Tibshirani. Regression Shrinkage and Selection Via the Lasso. Journal of the Royal Statistical Society, Series B, 58(1)88877 1994.
[15] Immanuel M. Bomze, Francesco Rinaldi, and Damiano Zeffiro. Frank Wolfe and friends: a journey into projection free first-order optimization methods. 4OR, 19(3):313 345, September 2021. ISSN 1614-2411.
doi: 10.1007//10088-000 02200022888210---..... URL hhttp::///d/ org/10
1007/s10288 0010022888021---000011 0049-00433-
[16] Roger Iyengar, Joseph P. Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards Practical Differentially Private Convex Optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pages 299-316, May 2019, doi: 10.1109//P.2019.00000 ISSN: 2375-1207.
[17] Amol Khanna, Fred Lu, and Edward Raff. Sparse private lasso logistic regression. arXiv preprint arXiv:2304. 12429, 2023.
[18] K. S. Sesh Kumar and Mare Peter Deisenroth. Differentially Private Empirical Risk Minimiza- tion with Sparsity-Inducing Norms, May 2019. URI. orgg/bs////r/ 04873 MrXiv:1905.0488 [cs, stat].

---

[19] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private Convex Empirical Risk Mini- mization and High-dimensional Regression. Shie Mannor, Nathan Srebro, and Robert C Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 25. 25.1-25.40, Edinburgh, Scotland, 2012. JMLR Workshop and Conference Proceedings. URI.http:/ htinttp://proceedingg .mlr....r...... wwt.ssmww...reeeeeeeeeeeeeeeeeee press/v233 https////////fff///e htte/iifer11.. html Series Title: Proceedings of Machine Learning Research.
[20] Dong C Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programmingg. (5()):503-528. 1989. ISSN 1436-4646. doi: 10.1007/BF01589116 URL /atpss/////d ort::////ooooooo///ooooooo 10. 1007 10000/F118800
[21] Prateek Jain and Abhradeep Guha Thakurta. (Near) Dimension Independent Risk Bounds for Differentially Private Learning. In Proceedings of the 31st International Conference on Machine Learning, pages 476-484. PMLR, January 2014. URL URL htttp:://proceeedeeee
mlr, prress/
v32/jain14 html
ISSN: 1938-7228.
[22] Bargav Jayaraman and David Evans. Evaluating Differentially Private Machine Learning in Prac- tice. In 28th /USENIX] Security Symposium (/ [/USENIX] Security 19), pages 1895-1912, Santa Clara, CA, August 2019. (USENIX) Association. ISBN 978-1-939133-06-99 URL hhtps
// /www. usenix org/ conf erence/ satpaaiixxecccrrttttt//ereeeeeee
jayaraman
[23] Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block CoordiCooee Frank-Wolfe Optimization for Structural SVMs. In Proceedings of the 30th International
Conference on Machine Learning, pages 53-61. PMLR, February 2013. URL https:// proceedings mlr. pwwps/e/w/eacceeee//ee julienlllnennnne html ISSN: 1938-7228.
[24] Thomas Kerdreux, Fabian Pedregosa, and Alexandre d' Aspremont. Frank- Wolfe with Sub- sampling Oracle. In Proceedings of the 35th International Conference on Machine Learn- ing, pages 2591 16000. PMLR, July 2018. |ttps://s/// wtw.oooeddngs....rprssss///// press/v80/ kerdreux18a 1
ISSN: 2640-3498.
[25] Armin Moharrer and Stratis Ioannidis. Distributing Frank-Wolfe via Map-Reduce Proceedings of the Twenty-Sevente International Joint Conference on Artificial Intelligence (1JCAI-18), pages 5334-5338, 2018. doi: 10.24963/iccii22118774 URL wtt.http::. htt/:/ww.j..... majjaai.oo org/
proceedings/2018/74
[26] Bingcong Li, Alireza Sadeghi, and Georgios Giannakis. Heavy ball momentum for conditional gradient. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 21244-21255. Curran Associates, Inc., 2021.
[27] Tyler LeBlond, Joseph Munoz, Fred Lu, Maya Fuchs, Elliott Zaresky- -iilkiams,, Edward Raff, and Brian Testa. Probing the transition to dataset-level privacy in ml models using an output- specific and data-resolved privacy profile. In Proceedings of the 16th ACM Workshop Artificial Intelligence and Security (AlSec '23), 2023.
(28) Fred Lu, Joseph Munoz, Maya Fuchs, Tyler LeBlond, Elliott Fiieskk-Willimss,, Edward Raff, Francis Ferraro, and Brian Testa. A general framework for auditing differentially private machine learning. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 4165-4176. Curran Associates, Inc., 2022.
[29] Amol Khanna, Fred Lu, and Edward Raff. The challenge of differentially private screening rules. In 2nd AdvML Frontiers Workshop at 40th International Conference on Machine Learning. 2023.
[30] Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava. Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 5576 5569. Curran Associates, Inc., 2021.
[31] Fabian Pedregosa and Low Kian Seong. //zenodo. org/ http///oorr//2233333.
Openopt/Copt: V0.4, June 2018. URI. https
12

---

[32] Naoise Holohan, Stefano Braghin, Pó1 Mac Aonghusa, and Killiaa Levacher, Difiprivlib: The IBM Differential Privacy Library, July 2019. URL htttp::/aaaxiv..rr/abb///////// arXiv:1907.0222 .0.444 [es].
[33] Douglas W. Jones. An empirical comparison of priority-queue and event-set implementations. Communications of the ACM, 29(4): 3011 April 1986. ISSN 0001-0782. doi: 145/544/
5686. URL wtttts://pttoo.oe org 10. 1145/ 5684. 5686
[34] Daniel H. Larkin, Siddhartha Sen, and Robert E. Tarjan. A Back-to-Basics Empirical Study of Priority Queues. In 2014 Proceedings of the Meeting on Algorithm Engineering and Experi- ments (ALENEX), Proceedings, pages 61-72. Society for Industrial and Applied Mathematics, December 201 3. doi: 10. 10.1137/7 1137/ 978161 19731997777.... URL httts:://ppbbs siam. org / abs/10. 1137 / 99111/1.997811119399998.
[35] Rong-En Fan, Kai- Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. LIBLIN- EAR: A Library for Large Linear Classification. The Journal of Machine Learning Research, 9: 1871-1874, 2008
[36] Edward Raff. JSAT: Java Statistical Analysis Tool, Library for Machine Learning, Journal of Machine Learning Research, 18(23):1-5, 2017. URL
16 htm
[37] Guo-Xun Yuan, Kai-Wei Chang, Cho-Jui Hsieh, and Chih-Jen Lin. A Comparison of Optimiza- tion Methods and Software for Large-scale L1 L1-regularized Linear Classification. The Journal of Machine Learning Research, 11:3 11:3183-3234, 2010.
[38] Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly Optimal Private LASSO. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL Abstarttt.....
[39] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensi- tivity in Private Data Analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Lecture Notes in Computer Science, pages 265-284, Berlin, Heidelberg, 2006. Springer. ISBN 978-3-540-32732-5. doi: 10. 10.1007/1681188_11111
[40] Pavlos S. Efraimidis and Paul G. Spirakis. Weighted random sampling with reser- voir. Information Processing Letters, 97(5):181-185, March 2006. ISSN 00200190. doi: 10.1016//.ip..2005.111 11.003. URL httts:://iikkngghtt/ walssvvier.com/retrreeeeeee $002001900500298X
[41] Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Interna- tional Conference on Machine Learning, pages 427-435, 2013.
[42] Shai Shalev-Shwartz. Online learning online convex optimization. Foundations and Trends in Machine Learning, 4(2): 2012.
[43] Raghav Bhaskar, Srivatsan Laxman, Adam Smith, and Abhradeep Thakurta. Discovering frequent patterns in sensitive data. Proceedings of the 16th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '10, page 503-512, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9781 450300551. doi: 10. 1145/
1835804. 1835869.
13

---

A
Additional Results
2.5
Queue Pops/ I |wo
1.5
0.5
100
10a
102
103
Iteration
New2DDFFo Fret
JRL-Past
RCVI-Fast
KDDA-Ful
Wib-Fist
Figure 3: The ratio of items popped from Fibonacci Heap over the non-zeros in the final solution (y-axis) over the number of iterations (x-axis) empirically demonstrates that Algorithm does not need to consider all D possible features select the correct iterate.
10a
100
Convergence
10-2
10
109
10
10
10
1047
FLOPS
New20
URL
RCVI
KDDA
New
RCVI-Fas
Figure 4: The number of floating point operations (x-axis) against the convergence gap Sr (y-axis), showing that [Algorithm (solid lines) reduces the required numerical steps by multiple orders of magnitude over the original Frank-Wolfe Algorithm (dashed lines).
B Proofs of Correctness
Because our method is a direct translation of Frank-Wolfe to equivalent mathematical steps, all prior proofs apply our version of the algorithm. We repeat/sketch the proofs here for further confidence in the correctness of the method.
14

---

B.1 Utility/Error Bounds
We provide a proof sketch that our algorithm's utility is near-optimal below which follows that of 38].
Let L be defined in the paper: the Lipschitz constant of the loss function with respect to the L norm. Let S be the number of vertices of the constraint region, which we denote C. Let be the scaling factor of the L ball to achieve the constraint region C. Then for loss with upper bound c (me))// iterations, we
on the curvature constant defined in running Algorithm for T [LA)a73 have
= D)= - (LA)/1 log(n) (SS) log(1/6) (ne)2/3
E L ((wwio, D)] min L(w; D)
WEC
To prove this statement, we use Lemma 5 and Theorem from [41]. Lemma states that at each step of the Frank-Wolfe algorithm, inexact gradient can be used so long its score is within to that of the true minimum vertex. (38] computed the value of к and showed that with probability 1 1- this occurs over all steps. Then Theorem in [4] stated that if Lemma 5 holds, an exact bound on the overall loss holds. Thus follows that with probability
ç. this statement holds. Finally, 338 used standard learning theory arguments to convert the bound in probability to one in expectation. Plugging in the desired value of T finishes the proof. Note that this proof not affected by our sparse-aware framework. Indeed, the algorithm presented in (38 is simply algorithm [41] in our paper with dense calculations. (Lines 7-13 of our Algorithm calculate scores for the exponential mechanism, like line in Algorithm 2 of (38). Line 15 in algorithm corresponds to line 4 of Algorithm 2 in (38). Lines 16-21 of our algorithm correspond to line 5 of Algorithm 2 in [38 For that reason, at every iteration, our updates equivalent that of (38).
Note that F can be upper bounded for logistic regression. See
17 for details.
Finally, using fingerprinting codes argument, Theorem 3.1 of 38 showed that under weak condi- tions, an optimal DP-learning algorithm AA has
E E[C(A(D): D) - min L(w; D)] = n/3
WEC
For this reason, the utility bound provided above is nearly-optimal.
B.2 Privacy Accounting
Here we prove that our algorithm is (c, DD. First, note that the sensitivity of each update step is LA where L is the Lipschitz constant of the loss function with respect to the L1 norm and the sealing factor of the L1 ball achieve the constraint region C. This is done using Lemma 2.6 from [2], in which we directly bound
Ks. VWWw; D)) - (s. VL(w;
where 8 is any vertex of the C. Now that we know the sensitivity, we use the advanced com- position theorem for pure differential privacy to find that 2 /2T log(1/6). Rearranging, Thus, composing T exponential mechanisms with privacy é' produces a final
(1/(/8) result which is (e, 8D- In our algorithm, use the Laplace distribution to implement the report noisy maximum version of the exponential mechanism at every iteration 43 Thus our algorithm (c, DDP
15


Reviews:
[{"review_id": "5qX6grMOQb", "reviewer": "Reviewer_LVpw", "summary": "This paper studies DP regression problem when the data is $\\ell_1$-sparse and aims to improve the computational efficiency. Specifically, they consider LASSO regularized logistic regression model and sparse aware Frank-Wolfe algorithm. The proposed method computes mathematical equivalent results as in the original algorithms but computationally much more efficient for large sparse datasets. The experiments confirm that the proposed methods are significant faster than existing methods.", "questions": "Please see weakness", "limitations": "This paper has not addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper provides a practical tool for DP regression on large sparse datasets. Prior works on sparse regressions are either purely theoretical or non-scalable. As far as I know, this is the first paper that focus on the computational efficiency.\n2. This paper is well-written and clearly states its contribution.", "weaknesses": "This paper does not discuss any utility guarantees in terms of its theoretical dependence on $d, \\lambda, L, \\varepsilon, n$. I am uncertain about the performance of sparse-aware DP Frank-Wolfe on this problem. Previous work [1] is known to be near-optimal in terms of utility. If the proposed method is sub-optimal, accelerating a sub-optimal algorithm may be of less interest.\n\n[1] Cai, T.T., Wang, Y., and Zhang, L. (2021). The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5), 2825-2850.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We should have made the DP bounds more explicit, thank you for bringing this to our attention. Please note that our algorithm's utility is near-optimal. We provide a proof sketch below which follows that of [1]. \n\nLet $L$ be defined as in the paper: the Lipschitz constant of the loss function with respect to the $L_1$ norm. Let $S$ be the number of vertices of the constraint region, which we denote $\\mathcal{C}$. Let $\\lambda$ be the scaling factor of the $L_1$ ball to achieve the constraint region $\\mathcal{C}$. Then for a loss with upper bound $\\Gamma_{\\mathcal{L}}$ on the curvature constant as defined in [2], running Algorithm 2 for $T = \\frac{\\Gamma_{\\mathcal{L}}^{2/3}(n\\epsilon)^{2/3}}{(L\\lambda)^{2/3}}$ iterations, we have \n\n$$\\mathbb{E}[\\mathcal{L}(\\mathbf{w}^{priv}; D)] - \\min_{\\mathbf{w} \\in \\mathcal{C}} \\mathcal{L}(\\mathbf{w}; D) = \\mathcal{O} \\left( \\frac{\\Gamma_{\\mathcal{L}}^{1/3}(L\\lambda)^{2/3}\\log(n \\lvert S \\rvert) \\sqrt{\\log (1/\\delta)}}{(n\\epsilon)^{2/3}} \\right).$$\n\nTo prove this statement, we use Lemma 5 and Theorem 1 from [2]. Lemma 5 states that at each step of the Frank-Wolfe algorithm, an inexact gradient can be used so long as its score is within $\\kappa$ to that of the true minimum vertex. [1] computed the value of $\\kappa$ and showed that with probability $1 - \\xi$, this occurs over all steps. Then Theorem 1 in [2] stated that if Lemma 5 holds, an exact bound on the overall loss holds. Thus it follows that with probability $1 - \\xi$, this statement holds. Finally, [1] used standard learning theory arguments to convert the bound in probability to one in expectation. Plugging in the desired value of $T$ finishes the proof. Note that this proof is not affected by our sparse-aware framework. Indeed, the algorithm presented in [1] is simply algorithm [2] in our paper with dense calculations. (Lines 7-13 of our Algorithm 2 calculate scores for the exponential mechanism, like line 3 in Algorithm 2 of [1]. Line 15 in our algorithm corresponds to line 4 of Algorithm 2 in [1]. Lines 16-21 of our algorithm correspond to line 5 of Algorithm 2 in [1].) For that reason, at every iteration, as our updates are equivalent to that of [1]. \n\nNote that $\\Gamma_{\\mathcal{L}}$ can be upper bounded for logistic regression. See [3] for details. \n\nFinally, using a fingerprinting codes argument, Theorem 3.1 of [1] showed that under weak conditions, an optimal DP-learning algorithm $\\mathcal{A}$ has \n\n$$\\mathbb{E}[\\mathcal{L}(\\mathcal{A}(D); D) - \\min_{\\mathbf{w} \\in \\mathcal{C}} \\mathcal{L}(\\mathbf{w}; D)] = \\widetilde{\\Omega} \\left( \\frac{1}{n^{2/3}} \\right).$$\n\nFor this reason, the utility bound provided above is nearly-optimal. \n\n[1] Talwar, Kunal, Abhradeep Guha Thakurta, and Li Zhang. \"Nearly optimal private lasso.\" Advances in Neural Information Processing Systems 28 (2015).\n\n[2] Jaggi, Martin. \"Revisiting Frank-Wolfe: Projection-free sparse convex optimization.\" International conference on machine learning. PMLR, 2013.\n\n[3] Khanna, Amol, Fred Lu, and Edward Raff. \"Sparse Private LASSO Logistic Regression.\" arXiv preprint arXiv:2304.12429 (2023). "}, {"review_id": "NipC8nNpQT", "reviewer": "Reviewer_Fgow", "summary": "This paper proposes new private variants of the Frank-Wolfe algorithm that takes advantage of the sparsity in the data. The proposed methods are shown to significantly speed up Frank-Wolfe algorithm in a multitude of tasks while still achieving similar accuracy.", "questions": "- In Algorithm 1, what do we need $g_t$ for? It isn't used anywhere else in the algorithm. Based on the experiment, seems like the authors want to output $g_t$ as the convergence gap, then the algorithm should output both $w_T$ and $g_t$?\n\n- I'm a bit confused about the statement in line 139. Isn't $\\bar v_t^{(i)} = \\sum_{j=1}^dX^{i,j}w_t^{j}$. Thus, when 1 single coordinate of $w_t$ changes, every $\\bar v_t^{(i)}$ will also change?\n\n- Can the author explain how using $\\gamma$ to update allow us to not use $\\bar y$ anymore?\n\n- What are $\\textbf{c}$ and $z_\\Sigma$ in Algorithm 4? Those 2 are used without being defined.\n\n- What is the sparsity of the data used in the experiments?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The authors make an effort to explain a lot of what is going on in their algorithm.\n\n- Since the result of the paper is about reducing computational complexity, I appreciate that the author denotes the complexity of every operation in their algorithms.\n\n- The proposed method seems to do well in practice. The speed-up is quite significant.", "weaknesses": "- Even though I appreciate the effort the author put in to explain their algorithms, I still feel like the explanation is very confusing. The paper would really benefit if the author can add a bit more discussion in the appendix to make things a bit clearer.\n\n- Some of the technical terms are used in the paper before being defined properly. For example, the term FLOPs is used in line 187 but only is defined in line 319.  Or the Fibonacci Heap is used without even having a few sentences defining what it is. Again, I think the author should consider having more discussions in the appendix.\n\n- Section 3.3 presents a private algorithm without having a Theorem showing that the algorithm is $\\epsilon$-DP.\n\n- Figure 1 and 2 are very confusing. For example, in the caption of Figure 1, it says that Algorithm 2 is the dotted line but every line is a dotted line. The legend of the chart also does not have either Algorithm 2 or Algorithm 1.\n\n- The authors use the phrase \"handle something sparsely\" often but it is a bit unclear what it means. Maybe explain it in the beginning or say something like \"allow us to handle the update in 1 dimension\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We believe, if accepted for the conference, the historical extra camera-ready page will greatly improve the readability of the manuscript and allow us to have more detailed exposition. Please see below for the answers to your questions, which we will incorporate into the revision. \n\n> what do we need $g_t$ for?\n\n$g_t$ is a measure of the convergence gap. Once $g_t = 0$, the algorithm has completely converged at the function minima. Use of $g_t$ is desirable in non-DP settings to confirm that a sufficiently good quality solution has been reached, and to confirm that the implementation is indeed converging. As Figure 1 shows, we converge to the solution at the same rate as the original dense Frank-Wolf formation. In the DP case, $g_t$ becomes noisy and is not as useful. \n\n>line 139 \n\nWe must be precise about the sparsity patterns. Every $\\bar v_t^{(i)}$ **where** $X^{i,j} \\neq 0$, will change. Because most values are equal to 0, the majority of $\\bar v_t^{(i)}$ will not change. Otherwise, the reviewer is correct in the definition. To restate, only one value of $j$ in $\\boldsymbol{w}^{(j)}$ will change each iteration (the others are handled by our scaling factor). In most high-dimensionsal regression problems (like all the ones we have used), most coordinates $j$ are unused by most columns $i$, and so the update of $\\boldsymbol{\\bar v}$ can be done in a sparse fashion. \n\n>how using  $\\gamma$  to update allow us to not use  $\\bar y$ anymore\n\nNote that in Algorithm 1, the values of $\\boldsymbol{\\bar y}$ are fixed during each iteration, and do not change. $\\boldsymbol{\\bar y}$ only impacts the algorithm by offsetting the values stored in $\\boldsymbol{\\bar \\alpha}$. Because Alg. 2 updates $\\boldsymbol{\\bar \\alpha}$ sparsely for the amount of change that occurs, and the value of $\\boldsymbol{\\bar y}$ will never change, then we can ignore the $\\boldsymbol{\\bar y}$ factor after the initialization of line 12 in Alg. 2. \n\n>What are $\\boldsymbol c$  and $z_\\Sigma$ in Algorithm 4?\n\n$\\boldsymbol c$ was defied on lines 280-281. There are $\\lfloor \\sqrt{D} \\rfloor$ groups of variables in Alg 4, and so $\\boldsymbol c$ is a vector of size  $\\lfloor \\sqrt{D} \\rfloor$. The $j$'th value $\\boldsymbol{c}^{(j)}$ contains the cumulative weight of all variables contained in the $j$'th group. It is used to skip the $j$'th group if it's cumulative weight is smaller than the current step size, allowing us to perform a \"Big Step\". \n\n$z_\\Sigma$ was defined on line 282. It is the cumulative weight of all variables being sampled from (i.e., $z_\\Sigma = \\mathop{LogSumExp}( \\boldsymbol{c}) = \\log \\left( \\sum_{j=1}^{\\lfloor \\sqrt{D} \\rfloor}  \\exp\\left(\\boldsymbol{c}^{(j)}\\right) \\right)$. It is necessary as the normalizing constant so that we ensure our sample is a proper weighted uniform random sample. \n\nPlease note Alg. 4 uses $N$ instead of $D$ to match the notation of the original A-ExpJ paper, since the page limit of NeurIPS prevents us from a more thorough explanation in text. \n\n>What is the sparsity of the data used in the experiments?\n\nThese datasets are highly sparse, see the below table for % of non-zero values. \n\n| Dataset | % of non zero values |\n|---|---|\n| RCV1 | 1.5% |\n| News20 | 0.03% |\n| URL | 0.004% |\n| Web | 0.022% |\n| KDDA | 0.00018% |\n\n>add a bit more discussion in the appendix\n\nWe will add a brief explanation and intro in the appendix for each major section to ensure the accessibility of the work. \n\n> used in the paper before being defined\n\nWe scoped our assumption of background too narrowly, and we will go through the paper again to ensure this does not remain in the revised manuscript. \n\nFLOP: is *F*loating *P*oint *Op*erations, normally taken to be the number of multiplications, divisions, and other more expensive functional primitives (e.g., computing the $\\exp$ is a single instruction in modern hardware). Counting the FLOPs provides a standardized and hardware-independent way of quantifying the amount of expensive computations being performed, as floating-point operations are generally many times more expensive than other integer operations. \n\nFibonacci Heap: A classic heap data structure for inserting, finding-the-minimum, and removing-the-minimum value from the data structure. The Fibonacci heap is relatively unique in supporting a decrease-key function that allows altering the value of an item already in the heap. All operations on a Fibonacci heap can be performed in amortized $O(1)$ time, with the exception of removal that takes $O(\\log n)$ time. Using the decrease-key operation allows us to devise the queue maintenance strategy of Algorithm 3. \n\n>a private algorithm without having a Theorem\n\nPlease see our reply to reviewer LVpw, which provides a proof. Our method is mathematically equivalent to the original Alg 1., and so all proofs of Alg 1 still apply to Alg 2 + 4, but reviewer feedback has made it clear that making this more explicit would aid in understanding the equivalence and validity. \n\n>Figure 1 and 2 are very confusing\n\nPlease see the 1-page attachment the adds new versions of these figures, we hope it clarifies your concern. \n\n> handle something sparsely\n\nWe will revise the manuscript to make explicit that what we mean by this is: if the original data $X^{i, j}$ has a value equal to zero, then as few operations as possible should occur involving the $i$ and $j$ values as the zero values will have no impact on the solution. We do not prove a minimum number of operations, but show for the first time it is sub $O(D)$ via the existence of our method. \n\n"}, {"review_id": "8iidKzHbVO", "reviewer": "Reviewer_Vyxf", "summary": "The paper presents an approach to train differentially private regression models on sparse input data. It leverages a modified version of the Frank-Wolfe algorithm to reduce the training time significantly by making the algorithm sensitive to sparse inputs.The algorithmic complexity is improved from the standard linear complexity to sub-linear. The authors have used their proposed method on multiple high-dimensional datasets improving the accuracy by 26.3% compared to previous methods.", "questions": "Could you please clarify how the proposed algorithm ensures compliance with the Differential Privacy (DP) condition? Are there any alternative privacy accounting methods that may potentially enhance the overall performance? For example, better privacy accounting [1], using GDP/RDP [2] or tighter compostion theorems [3].\n\nThe authors suggest that their implementation requires fewer FLOPs compared to the standard Frank-Wolfe approach. Does this reduction in FLOPs translate directly to a commensurate speed increase, or is computational efficiency still constrained by factors such as RAM and cache access? Could you elaborate on the current computational bottlenecks?\n\nThe experimentation appears to have been conducted using a single core. Would there be any potential benefits, such as efficiency or performance improvements, if this method were to be adapted for multicore processing?\n\nCan this method be extended beyond LASSO Regularized Logistic Regression? If not, what's the main challenge?\n\n[1]: Altschuler, J., & Talwar, K. (2022). Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 35, 3788-3800.\n\n[2] Liu, Y., Sun, K., Jiang, B., & Kong, L. (2022). Identification, amplification and measurement: A bridge to gaussian differential privacy. Advances in Neural Information Processing Systems, 35, 11410-11422.\n\n[3] Kairouz, P., Oh, S., & Viswanath, P. (2015, June). The composition theorem for differential privacy. In International conference on machine learning (pp. 1376-1385). PMLR.", "limitations": "See weakness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is eloquently written, with algorithms clearly delineated and accompanied by ample commentary. The proposed algorithm showcases its versatility across various scenarios, offering a remarkable improvement in performance.", "weaknesses": "The paper does not provide proven error bounds, and all theoretical results appear to revolve around the concept of speed optimization. It remains unclear whether this speed enhancement comes at the expense of accuracy. Additionally, the lack of released code poses a challenge to reproducibility.\n\nPrivacy accounting is implict and lacking, the authors didn't directly explain how does their algorithm satisfy the DP condition (advanced compostion?).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Could you please clarify how the proposed algorithm ensures compliance with the Differential Privacy (DP) condition?\n\nThe original Alg. 1 has already been proven to be DP. Our work makes no changes that alter what is computed, and only avoids performing redundant calculations (i.e., multiplication by 0 gets 0), and thus all profs are still applicable. The reviewer's questions helped us realize this is not sufficient, see the below proof for additional confidence: \n\nHere we prove that our algorithm is $(\\epsilon, \\delta)$-DP. \n\nFirst, note that the sensitivity of each update step is $\\frac{L\\lambda}{n}$, where $L$ is the Lipschitz constant of the loss function with respect to the $L_1$ norm and $\\lambda$ is the scaling factor of the $L_1$ ball to achieve the constraint region $\\mathcal{C}$. This is done using Lemma 2.6 from [1], in which we directly bound \n\n$$\\lvert \\langle s, \\nabla \\mathcal{L}(\\mathbf{w}; D) \\rangle  - \\langle s, \\nabla \\mathcal{L}(\\mathbf{w}; D') \\rangle \\rvert$$\n\nwhere $s$ is any vertex of the $\\mathcal{C}$. Now that we know the sensitivity, we can use the advanced composition theorem for pure differential privacy to find that $\\epsilon = 2\\epsilon'\\sqrt{2T \\log (1/\\delta)}$. Rearranging, $\\epsilon' = \\frac{\\epsilon}{\\sqrt{8T \\log (1/\\delta)}}$. Thus, composing $T$ exponential mechanisms with privacy $\\epsilon'$ produces a final result which is $(\\epsilon, \\delta)$-DP. In our algorithm, we use the Laplace distribution to implement the report noisy maximum version of the exponential mechanism at every iteration [2]. Thus our algorithm is $(\\epsilon, \\delta)$-DP. \n\n[1] Shalev-Shwartz, Shai. \"Online learning and online convex optimization.\" Foundations and Trends® in Machine Learning 4.2 (2012): 107-194.\n\n[2] Bhaskar, Raghav, et al. \"Discovering frequent patterns in sensitive data.\" Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010.\n\n>Are there any alternative privacy... \n\nOur algorithm works by composing a number of $(\\epsilon', 0)$-DP steps to produce an $(\\epsilon, \\delta)$-DP algorithm with advanced composition, where $\\epsilon'$ is chosen appropriately [4]. Composing $(\\epsilon', 0)$-DP steps with the advanced composition theorem is tight [5]. \n\nThe works provided in this review address composition under different settings. [1] describes the setting in which privacy parameters are to be computed after training with Gaussian noise. This is common in DP deep learning systems. In our work, we set $(\\epsilon, \\delta)$ and $T$ prior to training, so accounting is not necessary. [2] describes Gaussian/Reyni differential privacy, which provides a tighter privacy composition when composing multiple $(\\epsilon, \\delta)$-DP algorithms. In our case, we compose multiple $(\\epsilon, 0)$-DP algorithms, in which case the advanced composition theorem is tight. Finally, [3] describes a tight composition theorem for $(\\epsilon, \\delta)$-DP. Since wer are not composing $(\\epsilon, \\delta)$-DP steps, this is not necessary. \n\nWe will ensure to cite these papers in our work and explain why using advanced composition to compose multiple $(\\epsilon, 0)$-DP steps is tight. \n\n[4] Bhaskar, Raghav, et al. \"Discovering frequent patterns in sensitive data.\" Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010.\n\n[5] Near, Joseph P., and Chiké Abuah. \"Programming Differential Privacy.\" (2021).\n\n\n>Does this reduction in FLOPs translate directly \n\nThe reviewer is correct that it is not a one-to-one translation in FLOPs reduction to speedup, we will make this more explicit in the revision. \n\nFor the non-private case, _we obtain no speedups_, as the Fibonacci heap is highly cache inefficient. The numerous cache misses cause the program to hit the canonical \"memory wall\", meaning our throughput is completely IO bound on main-memory access. This is true of the standard FW in Alg. 1, and so has almost identical runtime. This was mentioned on line 372. \n\nWe are not concerned about the lack of speedup in the non-private case, because much faster algorithms than FW already exist in this scenario (e.g., Liblinear is several hundred times faster in our testing). \n\nIn the DP case, Alg. 1 is always compute bound, and our Alg. 2 + 4 combination vacillates between compute and memory bound on a per-iteration basis due to fairly atypical memory access patterns. Different dimensions have different sparsity patterns, resulting in cache misses, and different ratios of compute-to-memory accesses. This is the cause of higher speedups at lower $\\epsilon$ we mentioned, due to avoiding the compute-bound by highly non-informative sparser features that are selected more often at high privacy. \n\n> ...if this method were to be adapted for multicore processing? \n\nNot directly, as many parts are memory bound and multiple threads polling memory would only increase this issue, while also adding synchronization overhead. Other prior works on parallelizing FW might be adaptable, but because we do less work, this is unclear as the ratio of work-per-thread will change dramatically. \n\n> Can this method be extended beyond [LR]? \n\nYes, this method should work for any FW optimizable objective (LR, Linear Regression, Hinge-loss SVM, Gambler's loss, etc). \n"}, {"review_id": "DJ5XGFD1eU", "reviewer": "Reviewer_d4md", "summary": "This paper studies how to equip differential priavate (DP) Frank Wolfe (FW) with the ability to cope with sparse data. The key insights are the proper priority queue data structures for handling the FW subproblem. To this end, a Fibonacci queue is proposed for non DP cases, and a big-step little-step sampler is designed for DP cases. The complexities of proposed approaches has improved dependence on N and D. Numerical results also suggests embracing sparsity fastens practical performance on large datasets. ", "questions": "See weakness.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(+) The proposed data structures are useful for handling sparse data for DP-FW. It provides a much better computation complexity with improved N and D dependence.\n\n(+) Empirically, the smart use of these data structures leads to significantly faster performance that is up to 20x - 30x. Here I am comparing Alg. 2 + 4 with Alg. 2, since Alg. 2 is possibly a more reasonable benchmark if hopes to advance FW with sparsity.\n\n(+) The numerical improvement tends to be more significant given a smaller $\\epsilon$. This is helpful for settings with high requirement on privacy. ", "weaknesses": "1.On the highlevel, this work focuses on developing efficient data structures for solving FW subproblem (in DP setting). Comparison with other data structures, such as those locality sensitive hashing ones https://arxiv.org/abs/2111.15139, is missing. \n\n2.Can the proposed method benefit other FW approaches, such as https://arxiv.org/abs/2110.04243\n\n3.The assertion in line 19 should be demonstrated more carefully.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your key points that we will answer below and incorporate into the revision. We hope they satisfy your concerns, please let us know if we can further clarify anything. \n\nWe respectfully note that our method is more than $20-30\\times$ faster, as Alg. 2 is one of our contributions in this work. The purpose of Table 2 was to perform an ablation experiment to show that both Alg. 2 and Alg. 4 are important individually and together to obtain our speedups, which at a real-world privacy value of $\\epsilon = 0.1$ range from $20\\times$ up to $2451\\times$ faster. \n\n>as those locality sensitive hashing ones https://arxiv.org/abs/2111.15139, is missing.\n\nThank you for this highly related work we were unaware of. We will include it in the revision and related work for comparison and a more complete scope of literature. \n\n2111.15139 tackles a very different setting from our own: they are focused on $N > D$, and non-private regression. We reached out to the authors during the rebuttal period who confirmed two further issues in performing a comparison. \n\nFirst, quoting the authors, \"I believe it is possible to state that our [2111.15139] paper focused on the setting where d= log N\", due to the LSH algorithm's domain of effectiveness being in situations where $D << N$. \n\nSecond, the authors confirmed that no code was written for the paper and it is a theoretical work. Indeed, the manuscript does not state which of multiple possible data structures should be used for the maximum inner product search. While we made our own attempt in the time available, it does not yet work, and indeed, there are no baselines to compare against to know what is an expected speedup. \n\nAdditionally, the paper is focused on the non-private case, meaning we would need to invent a new DP maxIPS data structure to use in our desired DP scenario. We suspect this alone would constitute a whole new paper of work and results. \n\nOther important differences include that the paper does not address sparsity in $D$, and more completely, their big-O complexity is $O(D + D N^\\rho)$ where $\\rho \\in (0, 1)$ is a factor dependent on the maxIPS structure's efficiency on the current data. This thus does not tackle the $O(D)$ iteration cost we are concerned with in sparse data scenarios. In addition, if $T$ is the number of iterations needed to converge, their work proves they need $O(T/c^{2})$ iterations, an increase based on a maxIPS dependent constant $c \\in (0, 1)$. The tradeoff between more iterations but faster per-iteration time would be another non-trivial factor. \n\nThat said, the work is highly important in establishing a different approach to \"queue maintenance\" as we described in our work, by instead transforming the representation of the data, labels, and iterates, to accommodate the maxIPS data structures. They are also tackle the larger $N$ case instead of large & sparse $D$ of our own. \n\nWe will synthesize these points into our revised related work and framing of our contribution. \n\n>benefit other FW approaches\n\nOur approach should be able to benefit many other FW approaches, but we can't state that it will work for _all_ other FW solvers. For the cited example of 2110.04243, we see that it should be a fairly direct application of our method to integrate with their own, with a few extra derivations of sparse updates for the added momentum term. We will cite and add this discussion to our related work, thank you. \n\n> line 19\n\nThe reviewer's point is well taken. To avoid ambiguity we will revise Line 19 as a statement to ``all \\textit{iterative} DP regression algorithms we are aware of''. We provide a table listing the training complexity of iterative private training procedures for high dimensional regression. Please note that the statement can be refined to $\\mathcal{O}(TND)$ for non-sparse aware algorithms. \n\n| Method | Complexity |\n|:---:|:---:|\n| Frank-Wolfe Methods [1, 2, 3, 4] | $\\mathcal{O}(TND)$ |\n| ADMM [5] | $\\mathcal{O}(TNDM)$ |\n| Iterative Gradient Hard Thresholding Methods [4, 6, 7] | $\\mathcal{O}(TND)$ |\n| Coordinate Descent [8] | $\\mathcal{O}(TND)$ |\n| Mirror Descent [3] | $\\mathcal{O}(TNDM)$ |\n\nNote that $M$ represents an iterative parameter which is greater than or equal to $1$. Methods with $M$ have a double-for loop and thus have two iterative parameters ($T$ and $M$). \n\nWe thank the reviewer for this comment and will insert this table into the final version of our paper. \n\n[1] Talwar, Kunal, Abhradeep Guha Thakurta, and Li Zhang. \"Nearly optimal private lasso.\" Advances in Neural Information Processing Systems 28 (2015).\n\n[2] Bassily, Raef, Cristóbal Guzmán, and Anupama Nandi. \"Non-euclidean differentially private stochastic convex optimization.\" Conference on Learning Theory. PMLR, 2021.\n\n[3] Asi, Hilal, et al. \"Private stochastic convex optimization: Optimal rates in l1 geometry.\" International Conference on Machine Learning. PMLR, 2021.\n\n[4] Hu, Lijie, et al. \"High dimensional differentially private stochastic optimization with heavy-tailed data.\" Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. 2022.\n\n[5] Wang, Puyu, and Hai Zhang. \"Differential privacy for sparse classification learning.\" Neurocomputing 375 (2020): 91-101.\n\n[6] Wang, Lingxiao, and Quanquan Gu. \"Differentially private iterative gradient hard thresholding for sparse learning.\" 28th International Joint Conference on Artificial Intelligence. 2019.\n\n[7] Wang, Lingxiao, and Quanquan Gu. \"A knowledge transfer framework for differentially private sparse learning.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.\n\n[8] Mangold, Paul, et al. \"High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n"}]

Author rebuttal:
Per the rebuttal instructions, we could include one page of a PDF file with any new plots or figures. Toward Reviewer Fgow's concern, we have a new version of Figure 1 and Figure 2 in the attached PDF, displayed as Figure 4 & 5 in the PDF file. 

Figure 4 replaces Figure 1, and we plot both the normal FW (Alg 1.) and our improvement in the non-DP case (Alg 2 + 3) side by side, showing that they are identical, which is the desired outcome. We have changed none of the underlying mathematics of the FW algorithm, and so we converge to the same solutions (barring floating-point differences). 

Figure 5 replaces Figure 2. We plot how many times fewer cumulative FLOPs are performed by iteration $T$ on the x-axis. At $T=1$ we perform basically the same number of flops due to initial setup, but each subsequent iteration performs sparse updates that need far fewer FLOPs, resulting in multiple orders of magnitude reduction in FLOPs as the number of iterations increases. 

Meta-review: This paper studies LASSO regularized logistic regression with differential privacy and assumes that the data is 
L1-sparse. The paper designs a more computationally efficient algorithm based on Frank-Wolfe, The experiments show that the proposed methods are significantly faster than existing approaches and, in particular, are practical even at large scale.
Decision: Accept (poster)