EFFICIENT METHODS IN CONVEX PROGRAMMING

By Arkadi Nemirovski. 2007

173 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Trust Region Policy Optimization (2015, background): “With an oracle that gives us subgradients, there are upper bounds on complexity that do not depend on dimensionality d of the underlying space [7].”
A Survey on Multi-Task Learning (2017, methodology): “[18] employ an optimal first-order optimization method in [19] to solve it.”
Hybrid Deterministic-Stochastic Methods for Data Fitting (2011, methodology): “Although the O (1 /k 2 ) rate is sub-linear, it is substantially faster than the optimal O (1 / √ k ) achievable by methods that use noisy gradient information [24, § 14.1].”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “Here, the performance of SGD (actually stochastic subgradient decent) depends on the second moment G2 = E[G(2)i ] [12].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “If the center of the smallest ellipsoid containing the new candidate set is replaced by its center of gravity, then an improved bound holds [167] (with p2 replaced by p in the complexity bound); however, this algorithm is not implemented in practice as there is no known efficient algorithm to find t”
A Primer on Monotone Operator Methods (2015, background): “By judiciously choosing points to evaluate and accumulating the cutting planes, one can localize a small set in which x⋆ must lie in [29,65,68,73,78,91,92,95,107,108].”
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (2015, unknown): “33”
Multi-Task Feature Learning Via Efficient l2, 1-Norm Minimization (2009, methodology): “In this paper, we propose to solve the 2,1-norm regularized problem using the first-order black-box methods [14, 16], which evaluate at each iteration the function value and (sub)gradient only.”
Large-scale sparse logistic regression (2009, methodology): “3.2 The Nemirovski s Line Search Scheme To address the problem that L is usually unknown in advance, Nemirovski [24] proposed a line search scheme for determining Lk (see Algorithm 1).”
A multi-task learning formulation for predicting disease progression (2011, methodology): “One of the key steps in AGM is the computation of the proximal operator associated with the .2,1-norm regularization.”
Information-theoretic lower bounds on the oracle complexity of convex optimization (2009, methodology): “In addition to the original text NY [4], we refer the reader to the book by Nesterov [3], and the lecture notes by Nemirovski [5] for background.”
Integrating low-rank and group-sparse structures for robust multi-task learning (2011, methodology): “5.4 Numerical Studies on APM We conduct numerical studies on APM in comparison with PM for solving RMTL in terms of the computation time (in seconds) and the iteration number.”
Adaptive Restart for Accelerated Gradient Schemes (2012, background): “For strongly convex functions an alternative to choosing the optimal value of q in Algorithm 1 is to use restarting, [3, 11, 15, 16, 20].”
On Similarity Preserving Feature Selection (2013, methodology): “By using the Nesterov’s method in constrained optimization [25], [26], [27], the second one globally solves the constrained optimization problem and selects features accordingly.”
On the Oracle Complexity of First-Order and Derivative-Free Algorithms for Smooth Nonconvex Minimization (2012, methodology): “Worst-case complexity analysis for optimization methods probably really started with Nemirovski and Yudin (1983), where the notion of oracle (or black-box) complexity was introduced.”
Lower bounds for finding stationary points I (2017, result): “While essentially present in previous work, our technique abstracts away and generalizes the central arguments in many lower bounds [35, 34, 45, 4].”
Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization (2010, methodology): “C.1 Background on mirror descent Mirror descent is a generalization of (projected) stochastic gradient descent, first introduced by Nemirovski and Yudin [5]; here we follow a more recent presentation of it due to Beck and Teboulle [23].”