Pith. sign in

REVIEW 4 major objections 5 minor 62 references

On the Benefits of Accelerated Optimization in Robust and Private Estimation

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Acceleration in optimization is claimed to reduce privacy and robustness noise by cutting the number of iterations, yielding strictly better statistical rates.

desk verdict The private-ERM flagship theorem is not proven as written: the proof leans on a false vector sub-Gaussian tail bound, but the paper's other rates and the acceleration transfer are real and worth a referee's time. read the letter →

arxiv 2506.03044 v1 pith:JO4MAD3B submitted 2025-06-03 math.ST cs.LGstat.MLstat.TH

Laurentiu Andrei Marchis , Po-Ling Loh This is my paper
classification math.STcs.LGstat.MLstat.TH MSC 62F3562J0590C25
keywords differentialprivacyFrank-WolfeNesterovaccelerationheavy-tailedrobustnessgeometricmedianofmeansexcessempiricalriskminimaxestimationlinearregression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper argues that accelerating optimization is not merely a computational speed-up but a statistical improvement in private and heavy-tailed robust estimation, because the noise injected for privacy or robustness accumulates with the number of iterations. Its main evidence is a series of rate comparisons: a relaxed accelerated Frank-Wolfe method, run on a strongly convex constraint set with a tailored learning rate and a lower bound on gradient norms, achieves excess empirical risk of order $1/(n\varepsilon)$ for fixed-ball GLMs and near-optimal $\widetilde{\Theta}(1/n^{2/3})$ in the Lasso-type regime with only $T\asymp\log n$ iterations, whereas the non-accelerated Frank-Wolfe baseline needs polynomially many iterations and pays with worse rates. The same mechanism improves heavy-tailed linear regression error from $1/n^{1/6}$ to $1/n^{1/5}$ in well-conditioned problems, and from roughly $1/n^{1/9}$ to $1/n^{1/4}$ in ill-conditioned ones at the cost of a small bias term. For smooth convex losses over $\mathbb{R}^p$, Nesterov momentum improves the private excess risk from $\widetilde{O}(1/n^{1/5}+1/(n^{1/2}\varepsilon))$ to $\widetilde{O}(1/n^{2/5}+1/(n\varepsilon^2))$. Read sympathetically, the paper's central truth is that acceleration transfers the burden of many cheap noisy steps to a few accurate ones, and that iteration count is itself a statistical resource.

What carries the argument

The central object is the relaxed and accelerated Frank-Wolfe iteration over an $\alpha_C$-strongly convex constraint set, with an $\ell_2$ ball of radius $D$ being $1/D$-strongly convex. Algorithm 1 chooses $v_t$ that nearly minimizes the noisy linear objective and updates $\theta_{t+1}=(1-\eta)\theta_t+\eta v_t$ with the tailored learning rate $\eta=\min\{1,\alpha_C r/(4\beta_L)\}$; its convergence is governed by the contraction factor $c=\max\{1/2,1-\alpha_C r/(8\beta_L)\}$. A strictly positive uniform lower bound $r\leq\|\nabla F(\theta)\|_2$ on the constraint set converts the usual sublinear Frank-Wolfe rate into an exponential one, with the relaxation error entering only linearly in $\Delta$. This exponential contraction is what makes $T\asymp\log n$ possible, and because the Gaussian noise variance in the private algorithm and the geometric median-of-means error in the robust algorithm scale with $T$, the logarithmic iteration count is what produces the improved statistical rates. The gradient-descent half of the paper uses Nesterov's momentum update $x_{t+1}=x_t+\lambda(x_t-x_{t-1})-\eta g(\cdot)$ over $\mathbb{R}^p$, whose quadratic $1/T^2$ convergence for smooth convex functions turns into the $n^{2/5}$ excess-risk terms.

What would settle it

Run Algorithm 3 on the lower-bound dataset construction of Proposition 2 with the ball radius $D$ chosen so that $D\geq\|\theta^*\|_2$, making the gradient vanish at $\theta^*$ inside the constraint set; if the $\widetilde{\Theta}(1/n^{2/3})$ excess risk is still achieved with $T\asymp\log n$, the gradient lower bound is not load-bearing, while if the rate degrades to the sublinear Frank-Wolfe rate, the assumption is essential.

Watch

Extended reading notes

Core claim

The paper claims that the iteration count of an optimization algorithm is a statistical resource: privacy noise (Gaussian mechanism under advanced composition) and robustness noise (geometric median-of-means gradient estimators) both grow with the number $T$ of iterations, so an accelerated method reaching the same optimization accuracy in fewer steps can use less noise and yields sharper excess-risk and parameter-error bounds. Concretely, for empirical risk minimization over an $\ell_2$ ball with a uniform gradient lower bound, the accelerated relaxed Frank-Wolfe algorithm with $\eta=\min\{1,\alpha_C r/(4\beta_L)\}$ and $T\asymp\log n$ attains expected excess empirical risk $\lesssim (\sqrt{p}+p\|C\|_2)\|C\|_2\sqrt{p}\log^{3/2}(n)\log(\log n/\delta)/(n\varepsilon)$, and in the regime $p\asymp m^2$, $n\asymp m^3/\log m$ with $D\asymp 1/\sqrt{p}$ this is $\widetilde{\Theta}(1/n^{2/3})$, minimax over the class $\mathcal{S}^\alpha_n$, while the non-accelerated Frank-Wolfe algorithm reaches the same rate only with $T=\Theta(n^{4/9})$ iterations. In heavy-tailed linear regression, the accelerated Frank-Wolfe method improves the $\ell_2$ error from $\widetilde{O}((1+\sigma^2)^{1/2}/n^{1/6})$ to $\widetilde{O}((1+\sigma^2)^{1/2}/n^{1/5})$ when $\Sigma$ is well-conditioned, and in the ill-conditioned case it trades a vanishing bias $c_K$ for a rate $\widetilde{O}((1+\sigma^2)^{1/2}/(c_K^{1/4}n^{1/4})+c_K+c_K^{1/2})$ with $T\asymp\log(n)/c_K^2$. For smooth convex risks over $\mathbb{R}^p$, differentially private Nesterov acceleration achieves excess risk $\widetilde{O}(1/n^{2/5}+1/(n\varepsilon^2))$ with $T=n^{1/5}$, improving over projected gradient descent's $\widetilde{O}(1/n^{1/5}+1/(n^{1/2}\varepsilon))$.

Load-bearing premise

The load-bearing premise is that the loss gradient never vanishes on the constraint set, which in parametric problems forces the practitioner to know the true parameter's norm, or the covariance structure, closely enough to place the constraint ball's boundary just outside the true parameter.

Editorial extensions

If this is right

  • If the central claim is right, private ERM over $\ell_2$ balls can run with $T\asymp\log n$ iterations instead of $T\asymp(n\varepsilon)^{2/3}$, giving a near-optimal $\widetilde{\Theta}(1/n^{2/3})$ excess empirical risk in the Lasso-type regime with the privacy budget spread over far fewer steps.
  • For GLMs with a constraint ball that grows toward $\theta^*$, accelerated Frank-Wolfe attains $\widetilde{O}(1/(n^{4/5}\varepsilon))$ excess empirical risk and $\widetilde{O}(1/\sqrt{n}+1/(n^{2/5}\sqrt{\varepsilon}))$ parameter error, improving on the non-accelerated $\widetilde{O}(1/(n\varepsilon)^{2/3})$ privacy cost.
  • In heavy-tailed linear regression with well-conditioned covariance, the accelerated estimator improves the $\ell_2$ error rate from $1/n^{1/6}$ to $1/n^{1/5}$ while keeping the same $(1+\sigma^2)^{1/2}$ dependence on the noise variance.
  • In the ill-conditioned ridge setting, acceleration cuts the iteration count from $T=n^{1/3}$ to $T\asymp\log(n)/c_K^2$ and improves the $n$-dependence from $1/n^{1/9}$ to $1/n^{1/4}$, at the price of an extra $c_K^{1/2}$ bias term that vanishes as conditioning improves.
  • For smooth convex model-free risks, Nesterov momentum improves private excess risk from $\widetilde{O}(1/n^{1/5}+1/(n^{1/2}\varepsilon))$ to $\widetilde{O}(1/n^{2/5}+1/(n\varepsilon^2))$, so acceleration matters in non-strongly-convex settings, while for strongly convex risks it only changes constant factors.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The iteration-count argument suggests a broader prediction the paper leaves implicit: any differentially private or robust iterative method whose noise variance grows with $T$ should inherit a similar benefit from acceleration, for instance private SGD with momentum or private ADMM variants.
  • The uniform gradient lower bound is checkable on a given dataset, so a practical extension would be to verify $\inf_{\theta\in C}\|\nabla L(\theta,D_n)\|_2$ before committing to the accelerated schedule, and to inflate the ball radius when the check fails; the paper does not discuss such a monitoring rule.
  • In the parametric settings, the knowledge assumptions such as $\|\theta^*\|_2-D\asymp n^{-2/5}$ could be replaced by a pilot-sample estimate of $\|\theta^*\|_2$, with the estimation error entering the rate; whether the resulting adaptive procedure preserves the improved $n$-dependence is an open testable question.
  • The ill-conditioned accelerated bound's $c_K^{1/2}$ bias term suggests an adaptive selection rule: use accelerated Frank-Wolfe only when $c_K$ is small relative to $n^{-1/4}$, and fall back on non-accelerated Frank-Wolfe otherwise, a recommendation the authors leave implicit.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies whether accelerated first-order methods improve statistical guarantees in differentially private and heavy-tailed robust estimation. It analyzes two families: a relaxed accelerated Frank-Wolfe method (Algorithm 3) on strongly convex constraint sets, and Nesterov-style accelerated gradient descent (Algorithm 5) over R^p. The headline results are: a private empirical-risk bound of order (√p+pD)D√p log^{3/2}(n)/(nε) with only T≍log(n) Frank-Wolfe iterations and a claimed eΘ(1/n^{2/3})-minimax rate over a class S^α_n; GLM rates of 1/(n^{4/5}ε) and 1/(nε) in expanding and fixed ℓ₂-balls; heavy-tailed linear-regression rates of about 1/n^{1/5} in the well-conditioned case and 1/(c_K^{1/4}n^{1/4})+c_K+c_K^{1/2} in the ill-conditioned case; and model-free smooth-risk rates of 1/n^{2/5}+1/(nε²) under Nesterov acceleration. The paper includes detailed proofs, comparisons with Talwar et al. [52] and Prasad et al. [46], and simulations.

Significance. If the main theorems were correct, the paper would make a useful contribution by showing that reducing the iteration count has a direct statistical benefit through smaller privacy noise or gradient-estimation error. The comparisons in Tables 1 and 2 are informative, and the authors are explicit about their assumptions. The proof structure is largely coherent, and the lower-bound construction in Section 3.1.2 is a meaningful adaptation of the fingerprinting argument. However, the flagship distribution-free result (Theorem 2) and its minimax corollary rest on a false high-dimensional sub-Gaussian tail bound (Lemma 15). This is a load-bearing gap that must be repaired before the central claims can be accepted. The additional assumptions requiring knowledge of ||θ*||₂ or the spectral structure of Σ are clearly stated but materially limit the practical scope of the claimed improvements.

major comments (4)
  1. [Appendix A.4, Lemma 15; used in Appendix D.1.1 (Theorem 2)] Lemma 15 is false for p>2, and the proof of Theorem 2 depends on it. For X∼N(0,σ²I_p), Definition A.5 holds, but the inequality P(||X||₂>t)≤4p e^{-t²/(8σ²)} cannot hold for moderate t. With p=100, σ²=1, and t=√(8 log(4000))≈8.14, the right-hand side is 0.1, while ||X||₂ concentrates near √p=10, so the left-hand side is approximately 0.99. The failure grows with p. In Appendix D.1.1, Lemma 15 is used to define the event Ω bounding the Gaussian noise ξ_t; with the correct Gaussian tail, ||ξ_t||₂ is of order σ_ξ√p plus a √log T term, not σ_ξ√log(pT). The final rate in Theorem 2 may be salvageable by replacing Lemma 15 with a χ² or coordinatewise tail bound, but the proof as written is invalid. Since Theorem 2 is the basis for the minimax optimality claim in Section 3.1.3, this is a load-bearing issue, not a cosmetic one.
  2. [Lemma 15; also used in Appendix D.1.3 (Theorem 4) and Lemma 35] The same false tail bound is used in the proof of Theorem 4 and in Lemma 35, which support the GLM and the model-free AGD results. In those places the dimension p is treated as an absolute constant, so replacing Lemma 15 with a correct bound would change the final rates only by absolute constants. But the manuscript's proofs are not correct as written. The authors should replace every use of Lemma 15 with a valid p-dimensional tail bound and re-derive the corresponding constants and logarithmic factors. At minimum, the proof of Theorem 2 must be rewritten, and the other occurrences should be audited.
  3. [Section 3.1.3] The minimax statement in Section 3.1.3 should be qualified. The upper bound in Theorem 2 applies only to datasets satisfying the gradient lower bound inf_{θ∈C} α_C||∇L(θ,D_n)||₂/β_L ≥ S₁, and the class S^α_n is defined by exactly that condition. The lower bound in Theorem 3 is over a larger class, and Proposition 2 shows that the lower-bound datasets can be embedded in S^α_n, so the matching statement is internally coherent. However, the phrase 'nearly optimal up to logarithmic factors' for ridge regression is over the custom class S^α_n, not over the standard class of bounded datasets with ||x||∞≤1, |y|≤1. If the gradient lower bound fails, for example when D≥||θ*||₂ so the empirical gradient vanishes inside C, Theorem 1's exponential contraction does not apply and the stated rates are not available. The authors should make this limitation more prominent.
  4. [Theorems 5, 9, and 11] The accelerating benefit in Sections 3.2 and 3.3 requires choosing the constraint-set radius D or the ridge penalty γ_C within an asymptotically shrinking window around unknown quantities. Theorem 5 requires ||θ*||₂-D≍1/n^{2/5}; Theorem 9 requires ||θ*||₂-D≍1/n^{1/5}; and Theorem 11 requires γ_C∈[c_K/4,c_K/2] and a ball radius between two expressions involving Σ and θ*. Since the goal is to estimate θ*, the practitioner must know the norm or the eigen-decomposition of Σ to an accuracy that matches the target rate. This does not make the statements internally inconsistent, and the conclusion acknowledges the assumption for the Frank-Wolfe lower bound, but it is a substantial limitation on the practical claims. The paper should state explicitly that Theorems 5, 9, and 11 are existence-type guarantees under oracle knowledge of ||θ*||₂ or the spectral structure, and should discuss whether the required gaps can be chosen data-dependently without destroying privacy or robustness.
minor comments (5)
  1. [Appendix D.1.1] In the definition of the event Ω in the proof of Theorem 2, the displayed condition reads ||ξ_t||₂ ≥ ...; it should be ≤, since the subsequent argument bounds the norm from above.
  2. [Theorem 15] Theorem 15 states that Nesterov's AGD is run with η=2/τ_u, but Theorem 14 and its proof use η=1/τ_u. This appears to be a typo, but as written the theorem statement is inconsistent with the proof it relies on.
  3. [Section 5, Figure 7 caption] The caption says 'We compare Nesterov's AGD (Theorem 15) to projected GD (Lemma 33)', but the text in Section 5 and the figure list say Figure 7 compares Theorem 9 with Theorem 8, both for Frank-Wolfe methods. The caption should be corrected.
  4. [Remark 5] The sentence 'if we want to beat the cost of privacy term in [14], we need to pick ϵ < eO(1/n^{6/5})' appears to have the inequality direction reversed; comparing 1/(n^{2/5}√ϵ) with 1/(nε) gives ϵ ≥ eO(1/n^{6/5}), not ϵ smaller. The authors should clarify.
  5. [Lemma 3] The phrase 'with probability at least 1−eζ‘' contains a formatting error and should read 'with probability at least 1−eζ'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the rates are derived from explicit assumptions with independent lower-bound arguments; the gradient lower-bound assumption is a stated limitation, not a fitted or self-referential input.

full rationale

The paper's main derivations are self-contained in the sense that the upper bounds follow from explicit smoothness, gradient lower-bound, noise, and privacy-composition calculations, while the lower bounds are independent fingerprinting or minimax arguments. The minimax claim in Section 3.1.3 defines the class S^alpha_n by the same gradient lower-bound condition used in Theorem 2, but this does not make the rate circular: Proposition 2 verifies, by an explicit calculation, that the hard dataset from Theorem 3 lies in that class, and the lower bound itself comes from a separate privacy argument adapted from [52]. Choosing D, r, q, and T by balancing competing terms in the bounds is legitimate analysis tuning, not fitting the claimed rate into an input. The paper also openly states that removing the gradient lower bound is open, and the heavy-tailed and GLM results rely on externally cited gradient-estimator and optimization results. A separate, non-circular correctness concern exists: Lemma 15 is a dimension-sensitive sub-Gaussian tail bound and the proof of Theorem 2 as written uses it to control the Gaussian noise; this affects the rigor of the proof as currently stated, but it is not a reduction of the conclusion to its own assumptions, so it does not raise the circularity score.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

No new physical or probabilistic entities are introduced. The main construction is the dataset class S^α_n in Section 3.1.3, which selects datasets satisfying the method's gradient-lower-bound condition, and the assumed knowledge of ||θ*||₂ or the eigen-structure of Σ used to set the algorithm's balls and penalties. All estimators, including the geometric median-of-means and the Gaussian mechanism, come from prior literature.

free parameters (4)
  • constraint gap δ_n = ||θ*||₂ - D = ≍ n^{-2/5} in Theorem 5; ≍ n^{-1/5} in Theorem 9
    The ℓ2 ball radius D is chosen so the true parameter sits just outside the ball; this gap generates the lower bound r on the gradient norm and sets the final rate exponent via the trade-off in Remark 19.
  • S₁, normalized gradient lower bound = any absolute constant; figures use S₁ = 1
    Theorem 2's rate is conditional on inf_θ α_C||∇L(θ,D_n)||₂/β_L ≥ S₁; S₁ enters r = S₁β_L/α_C and hence the learning rate η and the iteration count T.
  • γ_C, ridge penalty = γ_C ∈ [c_K/4, c_K/2] with c_K = ||[P^Tθ*][(m+1):p]||₂
    In Theorem 11 the penalty is pinned to the unknown energy of θ* in the null space of Σ; the bound blows up if γ_C tends to 0 or infinity, as stated in Remark 10.
  • inner ball radius K in Theorem 11 = between ||(Σ + C₁c_K I_p)^{-1}Σθ*||₂ and ||(Σ + c_K I_p)^{-1}Σθ*||₂
    The optimization ball must sit strictly inside the constrained optimum ball; its radius controls the c_K^{1/2} bias term in the final bound.
assumptions (6)
  • domain assumption C is an α_C-strongly convex set, with ℓ2 balls being 1/D-strongly convex
    Definition 2.1 and Lemma 5; Theorem 1's exponential Frank-Wolfe rate depends on this geometry.
  • ad hoc to paper inf_{θ∈C} ||∇F(θ)||₂ ≥ r > 0
    Theorem 1 hypothesis; it excludes every problem whose unconstrained optimum lies in C and drives the choice of growing balls in Sections 3.2 and 3.3.
  • ad hoc to paper ||θ*||₂ or the eigen-structure of Σ is known well enough to set D or γ_C within the prescribed gap
    Theorems 5, 9, and 11 hypotheses; without this knowledge the balls cannot be positioned and the gradient lower bound cannot be certified.
  • domain assumption Bounded covariates and responses in the privacy sections; E[w²] < ∞ and bounded 4th moments of x in the heavy-tailed sections
    Sections 3.1 through 3.3 hypotheses; used for Lipschitzness, smoothness, and the concentration lemmas.
  • domain assumption w^(p) is sub-Gaussian with parameter σ²(p) in Proposition 1
    Condition (5) of Proposition 1; needed for the ||W||∞ tail bound used to lower-bound the gradient norm.
  • domain assumption 1 < τ_u/τ_l < 1.76 and f₁(τ_u/τ_l) < α/τ_l < f₂(τ_u/τ_l)
    Theorem 14 hypothesis; confines the strongly-convex AGD result to well-conditioned risks.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Benefits of Accelerated Optimization in Robust and Private Estimation." pith.science (2026). https://pith.science/paper/JO4MAD3B

@misc{pith2026250603044,
  author       = {Pith},
  title        = {Pith review of: On the Benefits of Accelerated Optimization in Robust and Private Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JO4MAD3B}},
  note         = {Machine review of arXiv:2506.03044}
}
abstract

We study the advantages of accelerated gradient methods, specifically based on the Frank-Wolfe method and projected gradient descent, for privacy and heavy-tailed robustness. Our approaches are as follows: For the Frank-Wolfe method, our technique is based on a tailored learning rate and a uniform lower bound on the gradient of the $\ell_2$-norm over the constraint set. For accelerating projected gradient descent, we use the popular variant based on Nesterov's momentum, and we optimize our objective over $\mathbb{R}^p$. These accelerations reduce iteration complexity, translating into stronger statistical guarantees for empirical and population risk minimization. Our analysis covers three settings: non-random data, random model-free data, and parametric models (linear regression and generalized linear models). Methodologically, we approach both privacy and robustness based on noisy gradients. We ensure differential privacy via the Gaussian mechanism and advanced composition, and we achieve heavy-tailed robustness using a geometric median-of-means estimator, which also sharpens the dependency on the dimension of the covariates. Finally, we compare our rates to existing bounds and identify scenarios where our methods attain optimal convergence.

Figures

Figures reproduced from arXiv: 2506.03044 by the authors.

Figure 2
Figure 2. We compare Theorem 5 with Lemma 10, using Algorithms 3 and 2. The plot shows the log excess empirical risk vs. n. We can see that Algorithm 3 does better than Algorithm 2 (cf. Remark 4), and larger ϵ leads to faster con￾vergence [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗
Figure 3
Figure 3. We compare Nesterov’s AGD (Theo￾rem 13) with projected GD (Theorem 12) using Algorithm 5 and the pseudo-Huber loss (with q = 1 5 , see Appendix C). The plot displays log(∥θT − θ ∗∥2) vs. n. Nesterov’s AGD outper￾forms projected GD (cf. Remark 13), and larger ϵ accelerates convergence. By the smoothness of the risk (cf. Lemma 26), we can further deduce a bound on R(θT ) − R(θ ∗ ) [PITH_FULL_IMAGE:figures/full_fig_p0… view at source ↗
Figure 6
Figure 6. We compare Theorem 11 with Theorem 10, using Algorithms 3 and 2. The plot shows ∥θT − θ ∗∥2 vs. n. As predicted by Theorems 11 and 10, the error plateaus at non-zero levels due to the cK term. The non-accelerated ver￾sion converges more slowly but ultimately incurs less error, while the accelerated version reaches its plateau faster [PITH_FULL_IMAGE:figures/full_fig_p024_6.png] view at source ↗
Figures from the paper (2 more)
Figure 7
Figure 7. Figure 7: We compare Nesterov’s AGD (Theo￾rem 15) to projected GD (Lemma 33). The plot shows log(∥θT −θ ∗∥2) versus n. We observe that Algorithm 3 outperforms Algorithm 2. 24 [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]
Figure 8
Figure 8. Figure 8: 1 − √ 1 x −  x−1 x+12 for x ≥ 1 and x ′′ ∈ (11, 12) It is interesting to note the linear convergence rate here, which also matches how projected gradient descent converges if we do not ask for strong convexity, whereas Nesterov’s method converges quadratically in the…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

62 extracted references · 51 canonical work pages

  1. [52]

    Talwar, A

    K. Talwar, A. Thakurta, and L. Zhang. Nearly optimal private Lasso.Advances in Neural Information Processing Systems, 28, 2015

    work page 2015

  2. [46]

    Prasad, A

    A. Prasad, A. S. Suggala, S. Balakrishnan, and P. Ravikumar. Robust estimation via robust gradient estimation.Journal of the Royal Statistical Society Series B: Statistical Methodology, 82(3):601–627, 2020

    work page 2020

  3. [1]

    Abadi, A

    M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016

    work page 2016

  4. [2]

    H. Asi, V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Optimal rates inℓ 1 geometry. InInternational Conference on Machine Learning, pages 393–403. PMLR, 2021

    work page 2021

  5. [3]

    Bakshi and A

    A. Bakshi and A. Prasad. Robust linear regression: Optimal rates in polynomial time. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 102–115, 2021

    work page 2021

  6. [4]

    Balakrishnan, S

    S. Balakrishnan, S. S. Du, J. Li, and A. Singh. Computationally efficient robust sparse estimation in high dimensions. InConference on Learning Theory, pages 169–212. PMLR, 2017

    work page 2017

  7. [5]

    Balle and Y.-X

    B. Balle and Y.-X. Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. InInternational Conference on Machine Learning, pages 394–403. PMLR, 2018

    work page 2018

  8. [6]

    Barreto, O

    M. Barreto, O. Marchal, and J. Arbel. Optimal sub-Gaussian variance proxy for truncated gaussian and exponential random variables.arXiv preprint arXiv:2403.08628, 2024

    arXiv 2024

Show all 62 references
  1. [7]

    J. T. Barron. A general and adaptive robust loss function. InProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4331–4339, 2019

    2019

  2. [8]

    Bassily, V

    R. Bassily, V. Feldman, K. Talwar, and A. Thakurta. Private stochastic convex optimization with optimal rates.Advances in Neural Information Processing Systems, 32, 2019

    2019

  3. [9]

    Bassily, C

    R. Bassily, C. Guzm´ an, and A. Nandi. Non-Euclidean differentially private stochastic convex optimiza- tion. InConference on Learning Theory, pages 474–499. PMLR, 2021

    2021

  4. [10]

    Bassily, A

    R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: efficient algorithms and tight error bounds. In2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464–473. IEEE, 2014

    2014

  5. [11]

    Beck and M

    A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183–202, 2009

    2009

  6. [12]

    Boucheron, G

    S. Boucheron, G. Lugosi, and O. Bousquet. Concentration inequalities. InSummer School on Machine Learning, pages 208–240. Springer, 2003

    2003

  7. [13]

    S. Bubeck. Convex optimization: Algorithms and complexity.Foundations and Trends®in Machine Learning, 8(3-4):231–357, 2015. 88

    2015

  8. [14]

    T. T. Cai, Y. Wang, and L. Zhang. The cost of privacy in generalized linear models: Algorithms and minimax lower bounds.arXiv preprint arXiv:2011.03900, 2020

    2011 arXiv

  9. [15]

    T. T. Cai, Y. Wang, and L. Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.The Annals of Statistics, 49(5):2825–2850, 2021

    2021

  10. [16]

    Diakonikolas, G

    I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, and A. Stewart. Robust estimators in high- dimensions without the computational intractability.SIAM Journal on Computing, 48(2):742–864, 2019

    2019

  11. [17]

    J. Duchi. Lecture notes for Statistics 311 / Electrical Engineering 377.URL: https://stanford. edu/class/stats311/Lectures/full notes. pdf. Last visited on, 2:23, 2016

    2016

  12. [18]

    Duchi, E

    J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization.Journal of Machine Learning Research, 12(7), 2011

    2011

  13. [19]

    Dwork, G

    C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010

    2010

  14. [20]

    Feldman, T

    V. Feldman, T. Koren, and K. Talwar. Private stochastic convex optimization: Optimal rates in linear time. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 439–449, 2020

    2020

  15. [21]

    Garber and E

    D. Garber and E. Hazan. Faster rates for the Frank-Wolfe method over strongly-convex sets. In International Conference on Machine Learning, pages 541–549. PMLR, 2015

    2015

  16. [22]

    F. R. Hampel. The influence curve and its role in robust estimation.Journal of the American Statistical Association, 69(346):383–393, 1974

    1974

  17. [23]

    Hoeffding

    W. Hoeffding. Probability inequalities for sums of bounded random variables.The Collected Works of Wassily Hoeffding, pages 409–426, 1994

    1994

  18. [24]

    P. J. Huber. Robust regression: Asymptotics, conjectures and monte carlo.The Annals of Statistics, pages 799–821, 1973

    1973

  19. [25]

    P. J. Huber. Robust estimation of a location parameter. InBreakthroughs in Statistics: Methodology and Distribution, pages 492–518. Springer, 1992

    1992

  20. [26]

    Iyengar, J

    R. Iyengar, J. P. Near, D. Song, O. Thakkar, A. Thakurta, and L. Wang. Towards practical differentially private convex optimization. In2019 IEEE Symposium on Security and Privacy (SP), pages 299–316. IEEE, 2019

    2019

  21. [27]

    M. Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. InInternational Con- ference on Machine Learning, pages 427–435. PMLR, 2013

    2013

  22. [28]

    Jain and A

    P. Jain and A. G. Thakurta. (Near) dimension independent risk bounds for differentially private learning. InInternational Conference on Machine Learning, pages 476–484. PMLR, 2014

    2014

  23. [29]

    C. Jin, P. Netrapalli, R. Ge, S. M. Kakade, and M. I. Jordan. A short note on concentration inequalities for random vectors with sub-Gaussian norm.arXiv preprint arXiv:1902.03736, 2019

    1902 arXiv

  24. [30]

    C. Jin, K. Zhou, B. Han, J. Cheng, and T. Zeng. Efficient private sco for heavy-tailed data via averaged clipping.Machine Learning, 113(11):8487–8532, 2024

    2024

  25. [31]

    Kairouz, S

    P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. InInternational Conference on Machine Learning, pages 1376–1385. PMLR, 2015. 89

    2015

  26. [32]

    Kamath, V

    G. Kamath, V. Singhal, and J. Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pages 2204–2235. PMLR, 2020

    2020

  27. [33]

    D. P. Kingma and J. Ba. Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014

    2014 arXiv

  28. [34]

    J. M. Kohler and A. Lucchi. Sub-sampled cubic regularization for non-convex optimization. InInter- national Conference on Machine Learning, pages 1895–1904. PMLR, 2017

    1904

  29. [35]

    N. Kuru, S. Ilker Birbil, M. Gurbuzbalaban, and S. Yildirim. Differentially private accelerated opti- mization algorithms.SIAM Journal on Optimization, 32(2):795–821, 2022

    2022

  30. [36]

    K. A. Lai, A. B. Rao, and S. Vempala. Agnostic estimation of mean and covariance. In2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 665–674. IEEE, 2016

    2016

  31. [37]

    E. L. Lehmann and G. Casella.Theory of Point Estimation. Springer Science & Business Media, 2006

    2006

  32. [38]

    Lerasle and R

    M. Lerasle and R. I. Oliveira. Robust empirical mean estimators.arXiv preprint arXiv:1112.3914, 2011

    2011 arXiv

  33. [39]

    X. Liu, P. Jain, W. Kong, S. Oh, and A. S. Suggala. Near optimal private and robust linear regression. arXiv preprint arXiv:2301.13273, 2023

    2023 arXiv

  34. [40]

    X. Liu, W. Kong, and S. Oh. Differential privacy and robust statistics in high dimensions. InConference on Learning Theory, pages 1167–1246. PMLR, 2022

    2022

  35. [41]

    Lugosi and S

    G. Lugosi and S. Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5):1145–1190, 2019

    2019

  36. [42]

    S. Minsker. Geometric median and robust estimation in banach spaces.Bernoulli, 21(4):2308–2335, 2015

    2015

  37. [43]

    Nesterov.Introductory Lectures on Convex Optimization: A Basic Course, volume 87

    Y. Nesterov.Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2013

    2013

  38. [44]

    Pensia, V

    A. Pensia, V. Jog, and P.-L. Loh. Robust regression with covariate filtering: Heavy tails and adversarial contamination.Journal of the American Statistical Association, pages 1–12, 2024

    2024

  39. [45]

    S. Pokutta. The Frank-Wolfe algorithm: A short introduction.Jahresbericht der Deutschen Mathematiker-Vereinigung, 126(1):3–35, 2024

    2024

  40. [47]

    Richt´ arik and M

    P. Richt´ arik and M. Tak´ aˇ c. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function.Mathematical Programming, 144(1):1–38, 2014

    2014

  41. [48]

    Schmidt, N

    M. Schmidt, N. Roux, and F. Bach. Convergence rates of inexact proximal-gradient methods for convex optimization.Advances in Neural Information Processing Systems, 24, 2011

    2011

  42. [49]

    Shang, T

    F. Shang, T. Xu, Y. Liu, H. Liu, L. Shen, and M. Gong. Differentially private ADMM algorithms for machine learning.IEEE Transactions on Information Forensics and Security, 16:4733–4745, 2021

    2021

  43. [50]

    Smith, A

    A. Smith, A. Thakurta, and J. Upadhyay. Is interaction necessary for distributed private learning? In 2017 IEEE Symposium on Security and Privacy (SP), pages 58–77. IEEE, 2017

    2017

  44. [51]

    S. Song, K. Chaudhuri, and A. D. Sarwate. Stochastic gradient descent with differentially private updates. In2013 IEEE Global Conference on Signal and Information Processing, pages 245–248. IEEE, 2013. 90

    2013

  45. [53]

    Tieleman

    T. Tieleman. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 4(2):26, 2012

    2012

  46. [54]

    S. Vadhan. The complexity of differential privacy.Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pages 347–450, 2017

    2017

  47. [55]

    A. W. Van Der Vaart and J. A. Wellner.Weak Convergence. Springer, 1996

    1996

  48. [56]

    M. J. Wainwright.High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019

    2019

  49. [57]

    D. Wang, M. Ye, and J. Xu. Differentially private empirical risk minimization revisited: Faster and more general.Advances in Neural Information Processing Systems, 30, 2017

    2017

  50. [58]

    Wang and C.-J

    P.-W. Wang and C.-J. Lin. Iteration complexity of feasible descent methods for convex optimization. The Journal of Machine Learning Research, 15(1):1523–1548, 2014

    2014

  51. [59]

    S. J. Wright and B. Recht.Optimization for Data Analysis. Cambridge University Press, 2022

    2022

  52. [60]

    X. Wu, F. Li, A. Kumar, K. Chaudhuri, S. Jha, and J. Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. InProceedings of the 2017 ACM International Conference on Management of Data, pages 1307–1322, 2017

    2017

  53. [61]

    Zhang, K

    J. Zhang, K. Zheng, W. Mou, and L. Wang. Efficient private erm for smooth objectives.arXiv preprint arXiv:1703.09947, 2017

    2017 arXiv

  54. [62]

    Zhang, Z

    M. Zhang, Z. Shen, A. Mokhtari, H. Hassani, and A. Karbasi. One sample stochastic Frank-Wolfe. In International Conference on Artificial Intelligence and Statistics, pages 4012–4023. PMLR, 2020. 91

    2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.