Lower Bounds for Parallel and Randomized Convex Optimization
From MaRDI portal
Publication:4969036
zbMath1497.68222arXiv1811.01903MaRDI QIDQ4969036
Jelena Diakonikolas, Cristóbal Guzmán
Publication date: 5 October 2020
Full work available at URL: https://arxiv.org/abs/1811.01903
Convex programming (90C25) Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items
Vaidya's method for convex stochastic optimization problems in small dimension ⋮ Lower bounds for non-convex stochastic optimization ⋮ Generalized Momentum-Based Methods: A Hamiltonian Perspective
Cites Work
- Unnamed Item
- Unnamed Item
- On lower complexity bounds for large-scale smooth convex optimization
- Sharp uniform convexity and smoothness inequalities for trace norms
- On parallel complexity of nonsmooth convex optimization
- An Algorithm for Variable Density Sampling with Block-Constrained Acquisition
- Randomized Smoothing for Stochastic Optimization
- Preserving Statistical Validity in Adaptive Data Analysis
- Smooth Optimization with Approximate Gradient
- Optimal methods of smooth convex minimization
- The best constants in the Khintchine inequality
- Accelerated Methods for NonConvex Optimization
- Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
- High-Dimensional Statistics
- Area-convexity, l ∞ regularization, and undirected multicommodity flow
- Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
- Optimal Affine-Invariant Smooth Minimization Algorithms
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
- On first-order algorithms forl1/nuclear norm minimization
- A new approach to computing maximum flows using electrical flows
