Anton Rodomanov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Anton Rodomanov has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Yurii Nesterov
Corvinus Centre for Operations Research at Corvinus Institute for Advanced Studies, Corvinus University of Budapest, 1093 Budapest, Hungary
5 shared publications - Nikita Doikov
Machine Learning and Optimization Laboratory (MLO) École Polytechnique Fédérale de Lausanne (EPFL) Switzerland
1 shared publication
Latest Publications
- Open Access
Gradient Methods for Stochastic Optimization in Relative Scale
We propose a new concept of a relatively inexact stochastic subgradient and present novel first-order methods that can use such objects to approximately solve convex optimization problems in relative scale. An important example where relatively inexact subgradients naturally arise is given by the Power or Lanczos algorithms for computing an approximate leading eigenvector of a symmetric positive semidefinite matrix. Using these algorithms as subroutines in our methods, we get new optimization schemes that can provably solve certain large-scale Semidefinite Programming problems with relative accuracy guarantees by using only matrix-vector products.
Open AccessGradient Methods for Stochastic Optimization in Relative Scale
We propose a new concept of a relatively inexact stochastic subgradient and present novel first-order methods that can use such objects to approximately solve convex optimization problems in relative scale. An important example where relatively inexact subgradients naturally arise is given by the Power or Lanczos algorithms for computing an approximate leading eigenvector of a symmetric positive semidefinite matrix. Using these algorithms as subroutines in our methods, we get new optimization schemes that can provably solve certain large-scale Semidefinite Programming problems with relative accuracy guarantees by using only matrix-vector products.
- Open Access
Polynomial Preconditioning for Gradient Methods
We study first-order methods with preconditioning for solving structured nonlinear convex optimization problems. We propose a new family of preconditioners generated by symmetric polynomials. They provide first-order optimization methods with a provable improvement of the condition number, cutting the gaps between highest eigenvalues, without explicit knowledge of the actual spectrum. We give a stochastic interpretation of this preconditioning in terms of coordinate volume sampling and compare it with other classical approaches, including the Chebyshev polynomials. We show how to incorporate a polynomial preconditioning into the Gradient and Fast Gradient Methods and establish the corresponding global complexity bounds. Finally, we propose a simple adaptive search procedure that automatically chooses the best possible polynomial preconditioning for the Gradient Method, minimizing the objective along a low-dimensional Krylov subspace. Numerical experiments confirm the efficiency of our preconditioning strategies for solving various machine learning problems.
Open AccessPolynomial Preconditioning for Gradient Methods
We study first-order methods with preconditioning for solving structured nonlinear convex optimization problems. We propose a new family of preconditioners generated by symmetric polynomials. They provide first-order optimization methods with a provable improvement of the condition number, cutting the gaps between highest eigenvalues, without explicit knowledge of the actual spectrum. We give a stochastic interpretation of this preconditioning in terms of coordinate volume sampling and compare it with other classical approaches, including the Chebyshev polynomials. We show how to incorporate a polynomial preconditioning into the Gradient and Fast Gradient Methods and establish the corresponding global complexity bounds. Finally, we propose a simple adaptive search procedure that automatically chooses the best possible polynomial preconditioning for the Gradient Method, minimizing the objective along a low-dimensional Krylov subspace. Numerical experiments confirm the efficiency of our preconditioning strategies for solving various machine learning problems.
- Open Access
- 14 June 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 199 (1-2) , 305-341
Subgradient ellipsoid method for nonsmooth convex problems
In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimensionality of the problem is sufficiently large. For generating accuracy certificates in our algorithm, we propose an efficient technique, which ameliorates the previously known recipes (Nemirovski in Math Oper Res 35(1):52–78, 2010).
- 14 June 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 199 (1-2) , 305-341
Open AccessSubgradient ellipsoid method for nonsmooth convex problems
In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimensionality of the problem is sufficiently large. For generating accuracy certificates in our algorithm, we propose an efficient technique, which ameliorates the previously known recipes (Nemirovski in Math Oper Res 35(1):52–78, 2010).
- Open Access
- 8 February 2021
- Published by Springer Nature in Mathematical Programming
- Vol. 194 (1-2) , 159-190
Rates of superlinear convergence for classical quasi-Newton methods
We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular, for the well-known DFP and BFGS methods, we obtain the rates of the form $$(\frac{n L^2}{\mu ^2 k})^{k/2}$$ and $$(\frac{n L}{\mu k})^{k/2}$$ respectively, where k is the iteration counter, n is the dimension of the problem, $$\mu $$ is the strong convexity parameter, and L is the Lipschitz constant of the gradient.- 8 February 2021
- Published by Springer Nature in Mathematical Programming
- Vol. 194 (1-2) , 159-190
Open AccessRates of superlinear convergence for classical quasi-Newton methods
We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular, for the well-known DFP and BFGS methods, we obtain the rates of the form $$(\frac{n L^2}{\mu ^2 k})^{k/2}$$ and $$(\frac{n L}{\mu k})^{k/2}$$ respectively, where k is the iteration counter, n is the dimension of the problem, $$\mu $$ is the strong convexity parameter, and L is the Lipschitz constant of the gradient. - Open Access
- 9 January 2021
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 188 (3) , 744-769
New Results on Superlinear Convergence of Classical Quasi-Newton Methods
We present a new theoretical analysis of local superlinear convergence of classical quasi-Newton methods from the convex Broyden class. As a result, we obtain a significant improvement in the currently known estimates of the convergence rates for these methods. In particular, we show that the corresponding rate of the Broyden–Fletcher–Goldfarb–Shanno method depends only on the product of the dimensionality of the problem and the logarithm of its condition number.
- 9 January 2021
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 188 (3) , 744-769
Open AccessNew Results on Superlinear Convergence of Classical Quasi-Newton Methods
We present a new theoretical analysis of local superlinear convergence of classical quasi-Newton methods from the convex Broyden class. As a result, we obtain a significant improvement in the currently known estimates of the convergence rates for these methods. In particular, we show that the corresponding rate of the Broyden–Fletcher–Goldfarb–Shanno method depends only on the product of the dimensionality of the problem and the logarithm of its condition number.
- Open Access
- 27 March 2020
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 185 (2) , 303-326
Smoothness Parameter of Power of Euclidean Norm
In this paper, we study derivatives of powers of Euclidean norm. We prove their Hölder continuity and establish explicit expressions for the corresponding constants. We show that these constants are optimal for odd derivatives and at most two times suboptimal for the even ones. In the particular case of integer powers, when the Hölder continuity transforms into the Lipschitz continuity, we improve this result and obtain the optimal constants.
- 27 March 2020
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 185 (2) , 303-326
Open AccessSmoothness Parameter of Power of Euclidean Norm
In this paper, we study derivatives of powers of Euclidean norm. We prove their Hölder continuity and establish explicit expressions for the corresponding constants. We show that these constants are optimal for odd derivatives and at most two times suboptimal for the even ones. In the particular case of integer powers, when the Hölder continuity transforms into the Lipschitz continuity, we improve this result and obtain the optimal constants.