Problem Complexity and Method Efficiency in Optimization

By J. Darzentas. 1983

How researchers see this paper

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

In Mathematical Optimization

Citations in the corpus

Sustainable AI: Environmental Implications, Challenges and Opportunities (2021, background): “Developing efﬁcient training algorithms is a long-time objective of research in optimization and numerical meth-ods [58].”
On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, methodology): “Despite this, the lower bound holds even if we do not restrict at all the domain in which we are allowed to query - i.e., it can even be all of Rd. Proof The proof technique is inspired by a lower bound which appears in Arias-Castro et al. (2011), in the different context of compressed sensing.”
Compatible Value Gradients for Reinforcement Learning of Continuous Deep Policies (2015, background): “The black-box model for optimization was introduced in (Nemirovski and Yudin, 1983), see (Raginsky and Rakhlin, 2011) for a recent exposition.”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “Stochastic gradient descent (SGD) (Robbins & Monro, 1951; Nemirovski & Yudin, 1978; 1983; Nemirovski et al., 2009; Hardt et al., 2016; Gower et al., 2019; 2020; Loizou et al., 2020) is the workhorse for training supervised machine learning problems.”
A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, methodology): “Interestingly, the examples we end up using have a spectrum similar to the one of the matrix Nesterov uses in the proofs of his lower bounds in Nesterov (2014). The choice of the spectrum of the Jacobian of the vector field was indeed the choice of interpolation points.”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “A fundamental advancement in the use of iterate averaging came with the work of Polyak [122], which was subsequently advanced with Juditsky [123]; see also the work of Ruppert [130] and Nemirovski and Rudin [104].”
A Theory of Multiple-Source Adaptation with Limited Target Labeled Data (2020, methodology): “Hence, the convergence guarantees of the min-max mirror descent algorithm (Nemirovski and Yudin, 1983) do not hold directly.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “If ¯ σ 2 > 0 the convergence rate is asymptotically dominated by the ﬁrst term, which cannot be further improved for stochastic methods (Nemirovsky & Yudin, 1983).”
Robust Aggregation for Federated Learning (2019, methodology): “Robust median-of-means approaches were introduced in [53], with more recent work in [27, 39, 42, 43, 49].”
Agnostic Federated Learning (2019, methodology): “When the loss function (cid:96) is convex, the AFL minmax optimization problem above can be solved using projected gradient descent or other instances of the generic mirror descent algorithm (Nemirovski and Yudin, 1983).”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “[20] Arkadii Nemirovski, David Borisovich Yudin, and Edgar Ronald Dawson.”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, methodology): “This idea is studied in Alon et al. (1999), Jerrum et al. (1986), Lerasle and Oliveira (2011), Minsker et al. (2015), Nemirovskii et al. (1983), and has been applied to bandit and least square regression problems (Bubeck et al., 2013, Kogler and Traxler, 2016, Lugosi and Mendelson, 2016) as well as…”
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, background): “However, no guarantee better then (8) can be ensured for gradient-based methods Nemirovsky and Yudin (1983), and we thus may still get a polynomial dependence on the sample size.”
Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming (2013, methodology): “On the other hand, these developments, motivated by complexity theory in convex optimization [24], concerned the convergence properties of SA methods during a ﬁnite number of iterations.”