Information-based complexity of linear operator equations

DOI10.1016/0885-064X(92)90013-2zbMath0758.65044OpenAlexW2082569121MaRDI QIDQ1194382

Arkadi Nemirovski

Publication date: 27 September 1992

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(92)90013-2

zbMATH Keywords

complexityoptimalityHilbert spacesbounded operatorslinear operator equationsconjugate gradient methodscomplexity boundsChebyshev methodssuboptimal methods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical solutions to equations with linear operators (65J10) Equations and inequalities involving linear operators, with vector unknowns (47A50) Complexity and performance of numerical algorithms (65Y20)

Related Items (28)

Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation ⋮ On lower iteration complexity bounds for the convex concave saddle point problems ⋮ Dual extrapolation and its applications to solving variational inequalities and related problems ⋮ Simple and Optimal Methods for Stochastic Variational Inequalities, II: Markovian Noise and Policy Evaluation in Reinforcement Learning ⋮ Generalizing the Optimized Gradient Method for Smooth Convex Minimization ⋮ Exact worst-case convergence rates of the proximal gradient method for composite convex minimization ⋮ Primal–dual accelerated gradient methods with small-dimensional relaxation oracle ⋮ Convergence of a Constrained Vector Extrapolation Scheme ⋮ Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization ⋮ Accelerated schemes for a class of variational inequalities ⋮ An optimal gradient method for smooth strongly convex minimization ⋮ Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods ⋮ Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods ⋮ Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games ⋮ Efficient first-order methods for convex minimization: a constructive approach ⋮ Golden ratio algorithms for variational inequalities ⋮ Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems ⋮ On lower complexity bounds for large-scale smooth convex optimization ⋮ The exact information-based complexity of smooth convex minimization ⋮ Gamblets for opening the complexity-bottleneck of implicit schemes for hyperbolic and parabolic ODEs/PDEs with rough coefficients ⋮ Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions ⋮ Some worst-case datasets of deterministic first-order methods for solving binary logistic regression ⋮ Nearly optimal first-order methods for convex optimization under gradient norm measure: an adaptive regularization approach ⋮ Distributed and consensus optimization for non-smooth image reconstruction ⋮ On the oracle complexity of smooth strongly convex minimization ⋮ Minimal residual algorithm and matrix-vector information ⋮ Efficient Algorithms for Distributionally Robust Stochastic Optimization with Discrete Scenario Support ⋮ Fully polynomial time \((\Sigma,\Pi)\)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs

Cites Work

• Unnamed Item
• Unnamed Item
• On the optimality of Krylov information
• On optimality of Krylov's information when solving linear operator equations
• On the Convergence of the Conjugate Gradient Method for Singular Linear Operator Equations

This page was built for publication: Information-based complexity of linear operator equations