Information-based complexity of linear operator equations

By Arkadi S. Nemirovsky. 1992

Subfields: Numerical Methods & Scientific Computing, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Numerical Methods & Scientific Computing

In Algorithms & Complexity

Citations in the corpus

A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, methodology): “Note that sublinear lower bounds have been proven for saddle-point problems by Nemirovsky (1992); Ne-mirovski (2004); Chen et al. (2014); Ouyang and Xu (2018), but they are outside the scope of this paper since we focus on linear convergence bounds.”
Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems (2004, methodology): “Let B be an arbitrary \flrst order" method for solving saddle point problems of the outlined type, i.e., a method which is given b, X, Y in advance, while having no direct access to A; however, B has an access to an \oracle" which, given on input a vector x, returns the vector Ax. It turns out [ 9 ]”
Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems (2020, methodology): “Using lower bounds for non-smooth convex minimization (Nemirovsky (1992)) as a black box, Nemirovski (2004) gives a lower bound of Ω(1 /T ) for ﬁrst-order methods for the smooth convex-concave saddle point problem; this is achieved by, for instance, the EG algorithm with averaged iterates.”
On lower complexity bounds for large-scale smooth convex optimization (2013, background): “ially, tight lowercomplexity bounds are known only in the case when X is Euclidean ball and f is convex function with Lipschitz continuous gradient. Lower bounds here come from least-squares problems [2, 3], and the underlying techniques for generating “hard instances” heavily utilize the rotational”
Linear Lower Bounds and Conditioning of Differentiable Games (2019, background): “Nemirovsky (1992) gives a lower bound in O(1/t) for a limited number of steps. Ouyang and Xu (2018) also leverage Krylov subspace techniques, and show lower bounds in O(1/t) in the monotone case and O(1/t(2)) in the strongly monotone case, assuming the number of iterations is less than half the dime”
Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence (2020, methodology): “We note that the convergence guarantees obtained by our scalar algorithm are optimal in all settings (non-smooth, smooth, and stochastic), as they match known lower bounds for convex optimization and saddle-point problems (Nemirovsky and Yudin 1983; Nemirovsky 1992; Ouyang and Xu 2021).”
Optimal Primal-Dual Methods for a Class of Saddle Point Problems (2013, background): “b) There exists b ∈ Y , where Y is a convex compact set of R for some m > 0, and a linear bounded operatorK, such that for any first-order method, the rate of convergence for solving min x∈X max y∈Y 〈Kx, y〉− J(y) := min x∈X max y∈Y 〈Kx− b, y〉 is at most O (LK/N) [31, 28].”
Dual extrapolation and its applications to solving variational inequalities and related problems (2007, background): “3) Note that from the view point of informational based complexity this estimate cannot be improved (see [2]).”