betaFeedback

WorksMathematics

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_p Geometries

Abstract

We consider the fundamental problem of parallel stochastic convex optimization (SCO), whose aim is to approximately minimize a convex objective when given the ability to query a moment-bounded stochastic gradient oracle multiple times in parallel per round. Whereas most previous results have focused on the variance-bounded Euclidean (ℓ2\ell_2-norm) setting, meaning the objective is Lipschitz with respect to the ℓ2\ell_2-norm over an ℓ2\ell_2-bounded feasible set in Rd\mathbb{R}^d, in this work we study parallel SCO in ℓp\ell_p settings for 2≤p<∞2 \le p < \infty under a heavy-tailed noise model. We begin by introducing a new class of ℓp\ell_p-optimal-distance-convergence (ODCp_p) algorithms, drawing on prior stochastic bias-reduced techniques [ACJ+21], which combine with multilevel Monte Carlo methods to efficiently estimate the optimum of uniformly convex objectives. As a consequence of our ODCp_p algorithms, we first establish rates for projection-efficient ℓp\ell_p-Lipschitz optimization, composite convex minimization, and efficient ℓp\ell_p-proximal point estimation. Combining our ODCp_p algorithms with a new ℓp\ell_p-generalized Gaussian-based stochastic gradient estimator (pp-GREG), we provide two efficient ℓp\ell_p parallel algorithms, EpochDA and ℓp\ell_p-AC-SA, which achieve optimization error ε>0ε> 0 with at most O~(dp2p+2ε−pp+1)\tilde{O}(d^{\frac{p}{2p + 2}} ε^{-\frac{p}{p + 1}}) query depth, improving upon the sequential heavy-tailed stochastic query depth of O(ε−p)O(ε^{-p}) for ε≤O~(d−1/(2p))ε\leq \tilde{O}(d^{-1/(2p)}). We also establish dimension-dependent lower bounds of Ω(min⁡{ε−p,dp/(3p−2)})Ω\bigl(\min\{ε^{-p},d^{p/(3p-2)}\}\bigr) adaptive rounds for nonsmooth convex optimization over a subset of the unit ℓp\ell_p ball. Our results improve upon the Ω(min⁡{ε−p,ε2/3d1/3})Ω(\min\{ε^{-p},ε^{2/3}d^{1/3}\}) bounds of [DG19], when adapted to the same feasible set.

Introduction

Stochastic methods are an essential part of modern optimization, with applications spanning machine learning, statistics, and theoretical computer science. The foundational work of Nemirovski and Yudin [38] introduced the oracle model for convex optimization, whereby the goal is to understand, for a particular oracle class, how many queries are needed to minimize a function to sufficient accuracy. Often considered in the case of stochastic convex optimization (SCO) is the stochastic first-order oracle, which for a convex function f:Rd→Rf : \mathbb{R}^{d} \to\mathbb{R} queried at a point xx, provides an unbiased estimate of the subgradient with bounded qq-th moment (q∈(1,2]q \in(1,2]), that is, ∇^f(x)\widehat{\nabla} f(x) such that E[∇^f(x)]∈∂f(x)\mathbb{E}[\widehat{\nabla} f(x)] \in\partial f(x) and E[∥∇^f(x)∥qq]≤σq\mathbb{E}[\lVert\widehat{\nabla} f(x)\rVert_{q}^{q}] \le\sigma^{q} for σ>0\sigma> 0.

An additional line of work, initiated by Nemirovski [36], has further considered the setting of parallel convex optimization, in which we may query an oracle multiple times in parallel for each round of interaction, and where we denote the query depth as the total number of such rounds. While several works have studied first-order methods for parallel settings in the Euclidean (ℓ2\ell_{2}-norm) case [BJL${}^{+}$19, CJJ${}^{+}$23, DBW12], meaning ff is Lipschitz continuous with respect to the ℓ2\ell_{2}-norm over an ℓ2\ell_{2}-bounded feasible set, parallel SCO has been less explored in non-Euclidean settings that deal with ℓp\ell_{p} geometries for 2≤p<∞2 \le p < \infty. For the p=∞p = \infty case, Nemirovski [36] established Ω((dln⁡(2Kd))1/3ln⁡(1/ε))\Omega\left(\left(\frac{d}{\ln(2Kd)}\right)^{1/3}\ln(1/\varepsilon)\right) lower bounds on the number of rounds required to achieve an ε\varepsilon-accurate solution, where KK denotes the number of parallel queries in each round, while Diakonikolas and Guzmán [18] provided lower bounds of the form Ω(min⁡{ε−p,ε2/3d1/3})\Omega(\min\{\varepsilon^{-p},\varepsilon^{2/3}d^{1/3}\}) for p≥2p \ge2.{^1} Meanwhile, work by Chakrabarty, Graur, Jiang, and Sidford [12] presented algorithms that achieve O(d1/3ε−2/3)O(d^{1/3}\varepsilon^{-2/3}) parallel stochastic query depth for ℓ∞\ell_{\infty}-Lipschitz convex problems, based on leveraging additional Gaussian smoothing for this setting, thereby matching the lower bounds for constant accuracy, though their results rely on stronger bounded second-moment (i.e., variance) assumptions that are standard when analyzing stochastic first-order methods. Moreover, ℓp\ell_{p}-based optimization methods have been shown to be broadly useful across a variety of contexts including training deep neural networks [LBL${}^{+}$25, MFS26, Pet26], pp-norm diffusion and flow problems [5, 21, 29, 32], and stochastic optimization under heavy-tailed noise assumptions [20 SBZ${}^{+}$26, VYB${}^{+}$22].

In this work, we study parallel stochastic ℓp\ell_{p}-Lipschitz convex optimization under bounded qq-th moment assumptions (for q=pp−1q = \frac{p}{p-1}), for which we provide new query depth complexities that improve upon previous sequential results for certain ranges of solution accuracy. Underlying our results are two key technical contributions:

  1. First, we introduce a class of ℓp\ell_{p}-optimal-distance-convergence (ODCp_{p}) algorithms, which we then show may be used to efficiently estimate the optimum of uniformly convex objectives. Although initially inspired by ideas on stochastic bias-reduced gradient methods [ACJ${}^{+}$21], we show how extending this type of approach to generalized ℓp\ell_{p}-based Moreau envelopes leads to several technical complications that need to be addressed, including the fact that the gradient function for the generalized Moreau envelope is a nonlinear mapping.

  1. Second, we develop and analyze a new ℓp\ell_{p}-generalized Gaussian reweighting scheme for gradient estimation, which broadly extends previous approaches based on standard Gaussian convolution. As a result of these tools, we are able to handle several basic challenges that arise when attempting to estimate the gradients of these ℓp\ell_{p}-based Moreau envelopes that are central to our techniques.

By combining these techniques with recent algorithms for ℓp\ell_{p} ball-oracle acceleration [ABJS26, [13], we arrive at our improved stochastic query depth complexities for parallel ℓp\ell_p-Lipschitz SCO. In addition, we establish new dimension-dependent lower bounds that improve upon the previous results of [18], under certain ℓp\ell_p domain restrictions.

ℓp\ell_p Stochastic Bias-Reduced Gradient Methods

We begin by discussing the setting of bias-reduced gradient methods. When considering the problem of minimizing a function f:X→Rf : \mathcal{X} \to\mathbb{R} given access to a stochastic subgradient estimator ∇^f\widehat{\nabla} f that is unbiased and has bounded variance, a natural question is to ask whether this estimator can be transformed into a nearly unbiased estimator of the true minimizer x∗=argmin⁡x∈Xf(x)x_* = \operatorname*{argmin}_{x \in\mathcal{X}} f(x). For strongly convex ff, [2] showed how to do so by proposing an estimator x^∗\widehat{x}_* such that for any δ>0\delta> 0, it holds that

∥Ex^∗−x∗∥2≤δandE∥x^∗−Ex^∗∥22=O(G2μ2log⁡(Gμδ)).\left\lVert\mathbb{E}\widehat{x}_* - x_* \right\rVert_2 \le\delta\quad\text{and} \quad\mathbb{E}\left\lVert\widehat{x}_* - \mathbb{E}\widehat{x}_* \right\rVert_2^2 = O\left(\frac{G^2}{\mu^2}\log\left(\frac{G}{\mu\delta}\right)\right).

where E∥∇^f(x)∥22≤G2\mathbb{E}\lVert\widehat{\nabla} f(x)\rVert_2^2 \le G^2. Given the importance of these estimators and the extensive number of applications that these are used for such as estimating proximal points [39, 35], minimizing the maximal loss [16], and gradient-efficient composite optimization [30] and the prevalence of uniformly convex optimization contexts such as ℓp\ell_p regression [11, 1, 4, 26] and online learning [33], it is natural to ask whether such estimators can be developed for the ℓp\ell_p setting.

In this work, we first answer this in the affirmative, and provide a class of ℓp\ell_p-optimal-distance-convergence (ODCp_p) algorithms that, when combined with multilevel Monte Carlo methods [22, 7], efficiently estimate the optimum of a uniformly convex function with low bias and bounded qq-th moment in the dual ℓq\ell_q norm, where q=pp−1q = \frac{p}{p-1}. Further, we use these estimators to yield improved rates for projection-efficient ℓp\ell_p-Lipschitz optimization, derive complementary rates to [2] for composite minimization, and develop efficient methods for estimating proximal points, where the proximal point of yy is Pf,λ(y)=argmin⁡x∈Rd{f(x)+λp∥x−y∥pp}P_{f,\lambda}(y) = \operatorname*{argmin}_{x \in\mathbb{R}^d}\left\{f(x) + \frac{\lambda}{p}\lVert x-y\rVert_p^p\right\}.

In Section 3, we describe our ODCp_p algorithms, which are part of a larger set of ODC algorithms that take as input an unbiased subgradient estimator which satisfies a given moment bound, and provides a (hopefully) efficient convergence guarantee for convergence to x∗x_*. In the Euclidean setting, [3] defines an ODC algorithm to minimize a strongly convex function F=f+ψF = f + \psi, where ff is convex and ψ\psi is simple such that the algorithm’s output x=ODC⁡(∇^f,ψ,T)x = \operatorname{ODC}(\widehat{\nabla} f,\psi,T) satisfies E∥x−x∗∥22≤cG2T\mathbb{E}\lVert x-x_*\rVert_2^2 \le c\frac{G^2}{T} for some constant cc. Moreover, such algorithms are widely found in the literature [24, 41, 3]. Given the advantages that these algorithms have provided, we develop analogous ODCp_p algorithms for p≥2p \ge2, for minimizing a μ\mu-uniformly convex function F=f+ψF = f + \psi, where ff is convex. As in [2], we leverage the multilevel Monte Carlo (MLMC) technique of [7] to construct a low-bias, bounded-dual-moment estimator of the ℓp\ell_p-Moreau gradient. However, unlike in the Euclidean-case, when considering p>2p > 2, the map from the proximal point to the Moreau gradient is nonlinear. Therefore, we depart from previous analyses, by applying the MLMC construction directly to approximate the Moreau gradient, rather than first constructing a low-bias estimator of the proximal point and then using this to compute the Moreau gradient estimation. We prove that for any λ\lambda-uniformly convex function F=f+ψF = f + \psi where ff is convex and iteration budget Tmax⁡T_{\max}, our ODCp_p algorithms provide good estimators g′g' of the true gradient g∗g_* in a reasonably fast manner (see Lemma 3 for more details).

EpochDA (§ 3.1). Next, we provide a concrete ODCp_p algorithm, EpochDA (Algorithm 3), which extends Algorithm 3 of [37] to a composite setting using an ℓp\ell_p-based uniformly convex prox function, and will be useful in achieving efficient ℓp\ell_p parallel rates (see § 4 for more details). Within each epoch, it applies a dual-averaging solver to the regularized objective, incorporating stochastic gradient estimates into successive updates while controlling the iterates through the global prox function centered at xˉ\bar{x}. It uses geometrically increasing epoch lengths and decreasing step sizes, averaging the iterates at the end of each epoch to initialize the next.

Projection-Efficient ℓp\ell_p-Lipschitz Optimization (§ 3.2). In stochastic nonsmooth optimization, constrained proximal or projection computations may be substantially more expensive than stochastic subgradient evaluations [2]. In § 3.2, we study this tradeoff in the ℓp\ell_p setting for p>2p > 2, where ff is convex and accessed through an unbiased stochastic subgradient oracle ∇^f\widehat{\nabla} f. In the Euclidean setting, [2] combine Moreau envelope smoothing with accelerated gradient descent to obtain O(GR/ϵ)O(GR/\epsilon) expensive projections while retaining near-optimal stochastic subgradient complexity. For p>2p > 2, we combine our ℓp\ell_p-Moreau envelope gradient estimator with accelerated updates using pp-power regularization, inspired by [1]. Our analysis uses the smoothness of the envelope with respect to ℓp\ell_p, while all constrained updates use pp-power regularization. The resulting algorithm requires Op((GR/ϵ)2p/(p+2))O_p((GR/\epsilon)^{2p/(p+2)}) expensive constrained updates and O~p((GR/ϵ)p(p−1))\widetilde{O}_p((GR/\epsilon)^{p(p-1)}) stochastic subgradient evaluations. Thus, compared with direct stochastic mirror descent, our method reduces the number of expensive constrained updates at the cost of a larger stochastic subgradient bound.

Convex Composite Minimization (§ 3.4). We consider the convex composite optimization problem

min⁡x∈XΨ(x):=Λ(x)+f(x),\min_{x\in\mathcal{X}} \Psi(x) := \Lambda(x) + f(x),

where Λ\Lambda is (L,κ)(L,\kappa)-weakly smooth with respect to ∥⋅∥p\|\cdot\|_p, ff satisfies Assumption 1, and there exists a minimizer x∗x^* such that ∥x0−x∗∥p≤R\|x_0-x^*\|_p \le R. A closely related setting was studied in [19], who considered composite minimization with a weakly smooth component and a uniformly convex component. Their generalized AGD+ framework yields an iteration complexity of O((LRκ/ϵ)p/(κp−p+κ))O((LR^\kappa/\epsilon)^{p/(\kappa p-p+\kappa)}) when specialized to ℓp\ell_p geometry without exploiting uniform convexity. Building on the stochastic composite AGD framework of [2], we develop an ℓp\ell_p extension using Bregman proximal steps and our reduced-bias gradient estimators. Our algorithm (Algorithm 5) achieves the same dependence on ϵ\epsilon in the number of ∇Λ\nabla\Lambda evaluations, up to logarithmic factors, while allowing ff to be nonsmooth and accessed through a stochastic subgradient oracle.

ℓp\ell_p Accelerated Proximal Point Methods (Section 3.5). Here, we develop Monteiro-Svaiter-type ℓp\ell_p accelerated proximal point methods which leverage our reduced-bias Moreau envelope gradient estimators. Inspired by [2], we present a stochastic accelerated ℓp\ell_p proximal point method (Algorithm 6), that computes adaptive proximal regularization with an accelerated first-order update. At each iteration, the algorithm selects a regularization parameter (λk+1)(\lambda_{k+1}), from a designed NextLambda algorithm (Algorithm 7), and computes an acceleration weight (ak+1)(a_{k+1}), which determines the cumulative weight (Ak+1)(A_{k+1}) and the interpolation point (yk)(y_k) between the current iterate and the auxiliary sequence. We obtain the next iterate (xk+1)(x_{k+1}) by approximately solving a regularized problem centered at yky_k, with the algorithm terminating when the cumulative accelerated weight reaches a prescribed threshold or the iteration budget is exhausted.

Parallel Optimization in pp Geometries

Parallel Upper Bounds. In § 4, we consider the following problem, simplified for the purposes of the introduction. We assume that there is a convex function f:Rd→Rf:\mathbb{R}^{d}\to\mathbb{R} whose minimizer lies in an ℓp\ell_p ball of radius RR, which can be queried through a stochastic gradient oracle gg, where Eg∈∂f\mathbb{E}g\in\partial f and E∥g∥qq≤Lq\mathbb{E}\lVert g\rVert_q^q\leq L^q, for some L>0L>0. Moreover, throughout the text, unless otherwise specified, q=pp−1q=\frac{p}{p-1}. Our goal is to minimize ff up to an expected additive error ϵopt\epsilon_{\mathrm{opt}}. Furthermore, we assume a setting where multiple queries can be submitted simultaneously. Along with the query depth, we also compute the computational depth and total number of queries to the stochastic gradient oracle to characterize the efficiency of our algorithms. As in [15], the computational depth measures the parallel depth of the algorithm, assuming that each oracle query has O(1)O(1) depth, and the total number of queries refers to the total number of queries made to the stochastic gradient oracle over all rounds.

Generalized Gaussian. A key technical tool that we introduce to achieve the parallel rates for our EpochDA and ℓp\ell_p-AC-SA solvers is an ℓp\ell_p-Gaussian Reweighting for Gradient Estimation (pp-GREG) estimator. Beginning with a generalized ℓp\ell_p-norm Gaussian as studied by [8], our estimator computes an unbiased estimate of a convolution of our objective ff with this ℓp\ell_p Gaussian, which furthermore offers the potential for parallelism.

References

  1. [1][ABJS26] Deeksha Adil, Brian Bullins, Arun Jambulapati, and Aaron Sidford. Convex optimization\nwith \(p\)-norm oracles. In \(37\)th \(International\ Conference\ on\ Algorithmic\ Learning\ Theory\),\n2026. (Cited on pages 1, 2, 3, 21, and 22.)
  2. [2][ACJ+21] Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Stochastic\nbias-reduced gradient methods. \(Advances\ in\ Neural\ Information\ Processing\ Systems\),\n34:10810–10822, 2021. (Cited on pages 1, 2, 3, 11, 16, 20, 22, 25, 32, and 40.)arxiv.org/abs/2106.09481
  3. [3][AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex\noptimization: Optimal rates in \(\ell_1\) geometry. In \(International\ Conference\ on\ Machine\nLearning\), pages 393–403. PMLR, 2021. (Cited on page 2.)arxiv.org/abs/2103.01516
  4. [4][APS19] Deeksha Adil, Richard Peng, and Sushant Sachdeva. Fast, provably convergent IRLS\nalgorithm for \(p\)-norm linear regression. \(Advances\ in\ Neural\ Information\ Processing\nSystems\), 32, 2019. (Cited on page 2.)arxiv.org/abs/1907.07167
  5. [5][AS20] Deeksha Adil and Sushant Sachdeva. Faster \(p\)-norm minimizing flows, via smoothed\n\(q\)-norm problems. In \(Proceedings\ of\ the\ Fourteenth\ Annual\ ACM-SIAM\ Symposium\ on\nDiscrete\ Algorithms\), pages 892–910. SIAM, 2020. (Cited on page 1.)arxiv.org/abs/1910.10571
  6. [6][Bec17] Amir Beck. \(First-order\ methods\ in\ optimization\). SIAM, 2017. (Cited on page 8.)DOI
  7. [7][BG15] Jose H Blanchet and Peter W Glynn. Unbiased monte carlo for optimization and\nfunctions of expectations via multi-level randomization. In \(2015\ Winter\ Simulation\nConference\ (WSC)\), pages 3656–3667. IEEE, 2015. (Cited on pages 2 and 11.)DOI
  8. [8][BGN21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-Euclidean differentially\nprivate stochastic convex optimization. In \(Conference\ on\ Learning\ Theory\), pages 474–499.\nPMLR, 2021. (Cited on pages 4, 6, and 84.)arxiv.org/abs/2103.01278
  9. [9][BJL+19] Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity\nof highly parallel non-smooth convex optimization. \(Advances\ in\ neural\ information\nprocessing\ systems\), 32, 2019. (Cited on pages 1, 4, 7, and 76.)arxiv.org/abs/1906.10655
  10. [10][BS18] Eric Balkanski and Yaron Singer. Parallelization does not accelerate convex optimiza-\ntion: Adaptivity lower bounds for non-smooth convex minimization. \(arXiv\ preprint\narXiv:1808.03880\), 2018. (Cited on pages 4 and 75.)arxiv.org/abs/1808.03880
  11. [11][Bul20] Brian Bullins. Highly smooth minimization of non-smooth problems. In \(Conference\ on\nLearning\ Theory\), pages 988–1030. PMLR, 2020. (Cited on page 2.)
  12. [12][CGJS23] Deeparnab Chakrabarty, Andrei Glaur, Haotian Jiang, and Aaron Sidford. Parallel\nsubmodular function minimization. \(Advances\ in\ Neural\ Information\ Processing\ Systems\),\n36:68639–68654, 2023. (Cited on pages 1 and 64.)arxiv.org/abs/2309.04643
  13. [13][CGMR25] Juan Pablo Contreras, Cristóbal Guzmán, and David Martínez-Rubio. Non-Euclidean\nhigh-order smooth convex optimization extended abstract. In \(The\ Thirty\ Eighth\ Annual\nConference\ on\ Learning\ Theory\), pages 1330–1330. PMLR, 2025. (Cited on pages 1\nand 2.)DOI
  14. [15]Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. ReSQueing parallel and private stochastic convex optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2031–2058. IEEE, 2023. (Cited on pages 1, 4, 5, 6, 7, 47, 55, 60, and 63.)arxiv.org/abs/2301.00457
  15. [16]Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference on Learning Theory, pages 866–882. PMLR, 2021. (Cited on pages 2 and 32.)arxiv.org/abs/2105.01778
  16. [17]John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674–701, 2012. (Cited on pages 1 and 91.)
  17. [18]Jelena Diakonikolas and Cristóbal Guzmán. Lower bounds for parallel and randomized convex optimization. In Conference on Learning Theory, pages 1132–1157. PMLR, 2019. (Cited on pages 1, 2, 4, 75, 76, and 84.)arxiv.org/abs/1811.01903
  18. [19]Jelena Diakonikolas and Cristóbal Guzmán. Complementary composite minimization, small gradients in general norms, and applications. Mathematical Programming, 208(1):319–363, 2024. (Cited on pages 3, 22, and 25.)arxiv.org/abs/2101.11041
  19. [20]Ilyas Fatkhullin, Florian Hübler, and Guanghui Lan. Can sgd handle heavy-tailed noise? arXiv preprint arXiv:2508.04860, 2025. (Cited on page 1.)arxiv.org/abs/2508.04860
  20. [21]Kimon Fountoulakis, Di Wang, and Shenghao Yang. p-norm flow diffusion for local graph clustering. In International Conference on Machine Learning, pages 3222–3232. PMLR, 2020. (Cited on page 1.)arxiv.org/abs/2005.09810
  21. [22]Michael B Giles. Multilevel Monte Carlo methods. Acta numerica, 24:259–328, 2015. (Cited on page 2.)
  22. [23]Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization I: A generic algorithmic framework. SIAM Journal on Optimization, 22(4):1469–1492, 2012. (Cited on pages 59, 69, 70, and 72.)DOI
  23. [24]Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization. In Proceedings of the 24th Annual Conference on Learning Theory, pages 421–436. JMLR Workshop and Conference Proceedings, 2011. (Cited on page 2.)
  24. [26]Arun Jambulapati, Yang P Liu, and Aaron Sidford. Improved iteration complexities for overconstrained p-norm regression. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 529–542, 2022. (Cited on page 2.)arxiv.org/abs/2111.01848
  25. [27]Arun Jambulapati, Aaron Sidford, and Kevin Tian. Closing the computational-query depth gap in parallel stochastic convex optimization. In The Thirty Seventh Annual Conference on Learning Theory, pages 2608–2643. PMLR, 2024. (Cited on pages 5 and 6.)arxiv.org/abs/2406.07373
  26. [28]Jonathan Kelner, Jerry Li, Allen X Liu, Aaron Sidford, and Kevin Tian. Semi-random sparse recovery in nearly-linear time. In The Thirty Sixth Annual Conference on Learning Theory, pages 2352–2398. PMLR, 2023. (Cited on page 93.)arxiv.org/abs/2203.04002
  27. [29]Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 217–226. SIAM, 2014. (Cited on page 1.)
  28. [30]Guanghui Lan. Gradient sliding for composite optimization. Mathematical Programming, 159(1):201–235, 2016. (Cited on page 2.)arxiv.org/abs/1406.0919
  29. [32]Yang P Liu and Aaron Sidford. Faster energy maximization for faster maximum flow. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 803–814, 2020. (Cited on page 1.)arxiv.org/abs/1910.14276
  30. [33]Yunwen Lei and Ding-Xuan Zhou. Convergence of online mirror descent. Applied and Computational Harmonic Analysis, 48(1):343–373, 2020. (Cited on page 2.)
  31. [35]Renato DC Monteiro and Benar Fux Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 23(2):1092–1125, 2013. (Cited on page 2.)DOI
  32. [36]Arkadi Nemirovski. On parallel complexity of nonsmooth convex optimization. Journal of Complexity, 10(4):451–463, 1994. (Cited on page 1.)DOI
  33. [37]Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 120(1):221–259, 2009. (Cited on pages 2, 16, and 17.)
  34. [38]Arkadi Nemirovski and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983. (Cited on page 1.)
  35. [39]Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in optimization, 1(3):127–239, 2014. (Cited on page 2.)DOI
  36. [41]Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv:1109.5647, 2011. (Cited on page 2.)DOI
  37. [43][Ver22] Roman Vershynin. High-dimensional probability. Cambridge University Press, 2022. (Cited on page 10.)
  38. [44][VYB+22] Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 65–102. PMLR, 02–05 Jul 2022. (Cited on pages 1, 5, and 6.)arxiv.org/abs/2202.11632
  39. [45][Ză83] C Zălinescu. On uniformly convex functions. Journal of Mathematical Analysis and Applications, 95(2):344–374, 1983. (Cited on page 21.)DOI

Paper details

vlnc:W_92b2kcj6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT 5.6, Claude

View statement
Looking for related papers…
Contents