?
Learning supervised pagerank with gradient-based and gradient-free optimization methods
P. 4914–4922.
Bogolubsky L., Dvurechensky P., Gasnikov A., Gusev G., Nesterov Y., Raigorodsky A., Tikhonov A., Zhukovskii M.
In this paper, we consider a non-convex loss-minimization problem of learning Supervised PageRank models, which can account for features of nodes and edges. We propose gradient-based and random gradient-free methods to solve this problem. Our algorithms are based on the concept of an inexact oracle and unlike the state-of-the-art gradient-based method we manage to provide theoretically the convergence rate guarantees for both of them. Finally, we compare the performance of the proposed optimization methods with the state of the art applied to a ranking task.
In book
NY: Curran Associates, 2016.
Yudin N., Gasnikov A., Компьютерные исследования и моделирование 2024 Т. 16 № 7 С. 1829–1840
We propose a family of Gauss–Newton methods for solving optimization problems and systems of nonlinear equations based on the ideas of using the upper estimate of the norm of the residual of the system of nonlinear equations and quadratic regularization. The paper presents a development of the «Three Squares Method» scheme with the addition of ...
Added: December 29, 2024
Schechtman S., Tiapkin D., Muehlebach M. et al., , in: Proceedings of Machine Learning Research: Volume 195: The Thirty Sixth Annual Conference on Learning Theory, 12-15 July 2023, Bangalore, IndiaVol. 195: The Thirty Sixth Annual Conference on Learning Theory, 12-15 July 2023, Bangalore, India.: PMLR, 2023. P. 1228–1258.
We consider the problem of minimizing a non-convex function over a smooth manifold M. We propose a novel algorithm, the Orthogonal Directions Constrained Gradient Method (ODCGM), which only requires computing a projection onto a vector space. ODCGM is infeasible but the iterates are constantly pulled towards the manifold, ensuring the convergence of ODCGM towards M. ...
Added: December 1, 2023
Anikin A., Gasnikov A., Gornov A. et al., Optimization Methods and Software 2022 Vol. 37 No. 3 P. 907–935
Over the last two decades, the PageRank problem has received increased interest from the academic community as an efficient tool to estimate web-page importance in information retrieval. Despite numerous developments, the design of efficient optimization algorithms for the PageRank problem is still a challenge. This paper proposes three new algorithms with a linear time complexity ...
Added: October 30, 2022
Suvorov A., Петренко А. А., Аликин А. В., Информационные технологии и вычислительные системы 2021 № 4 С. 100–110
The article is devoted to solving the problems of search engine optimization of single-page applications built based on modern technologies of reactive JavaScript, including such JavaScript-frameworks as React, Angular, Vue, which allow developers to quickly create and scale interactive applications. However, such single page application is a complex area with a huge number of nuances ...
Added: November 16, 2021
Gorbunov E., Burlachenko K., Li Z. et al., , in: Proceedings of the 38th International Conference on Machine Learning (ICML 2021)Vol. 139.: PMLR, 2021. Ch. 139 P. 3788–3798.
Added: October 25, 2021
Danilova M., Dvurechensky P., Gasnikov A. et al., / Series arXiv:2012.06188 "arXiv:2012.06188". 2020.
Motivated by recent increased interest in optimization algorithms for non-convex optimization in application to training deep neural networks and other optimization problems in data analysis, we give an overview of recent theoretical results on global performance guarantees of optimization algorithms for non-convex optimization. We start with classical arguments showing that general non-convex problems could not ...
Added: October 25, 2021
Tupitsa N., Dvurechensky P., Gasnikov A. et al., Journal of Inverse and Ill-posed problems 2021 Vol. 29 No. 5 P. 721–739
We consider alternating minimization procedures for convex and non-convex optimization problems with the vector of variables divided into several blocks, each block being amenable for minimization with respect to its variables while maintaining other variables' blocks constant. In the case of two blocks, we prove a linear convergence rate for alternating minimization procedure under the ...
Added: September 29, 2021
Eduard Gorbunov, Bibi A., Sener O. et al., , in: Proceedings of the 8th International Conference on Learning Representations (ICLR 2020).: ICLR, 2020. P. 1–28.
We consider the problem of unconstrained minimization of a smooth objective function in $\mathbb{R}^d$ in setting where only function evaluations are possible. We propose and analyze stochastic zeroth-order method with heavy ball momentum. In particular, we propose, SMTP, a momentum version of the stochastic three-point method (STP) Bergou et al. (2019). We show new complexity ...
Added: December 7, 2020
Bergou E. H., Eduard Gorbunov, Richtarik P., SIAM Journal on Optimization 2020 Vol. 30 No. 4 P. 2726–2749
In this paper we consider the unconstrained minimization problem of a smooth function in $\mathbb{R}^n$ in a setting where only function evaluations are possible. We design a novel randomized derivative-free algorithm---the stochastic three points (STP) method---and analyze its iteration complexity. At each iteration, STP generates a random search direction according to a certain fixed probability law. Our ...
Added: November 10, 2020
Guminov S., Nesterov Y., Dvurechensky P. et al., Doklady Mathematics 2019 Vol. 99 No. 2 P. 125–128
A new version of accelerated gradient descent is proposed. The method does not require any a priori information on the objective function, uses a linesearch procedure for convergence acceleration in practice, converge according to well-known lower bounds for both convex and nonconvex objective functions, and has primal-dual properties. A universal version of this method is ...
Added: October 31, 2020
Nesterov Y., Gasnikov A., Guminov S. et al., Optimization Methods and Software 2021 Vol. 36 No. 4 P. 773–810
In this paper, a new variant of accelerated gradient descent is proposed. The proposed method does not require any information about the objective function, uses exact line search for the practical accelerations of convergence, converges according to the well-known lower bounds for both convex and non-convex objective functions, possesses primal–dual properties and can be applied ...
Added: August 4, 2020
Ustyuzhanin A., Баранов А. С., Ratnikov F. et al., Journal of Instrumentation 2017 Vol. 12 No. 5 P. 1–8
The SHiP experiment is designed to search for very weakly interacting particles beyond the Standard Model which are produced in a 400 GeV/c proton beam dump at the CERN SPS. An essential task for the experiment is to keep the Standard Model background level to less than 0.1 event after 2× 1020 protons on target. In the beam ...
Added: February 26, 2018
Pardalos P. M., Žilinskas A., Žilinskas J., Springer, 2017.
Recent results on non-convex multi-objective optimization problems and methods are presented in this book, with particular attention to expensive black-box objective functions. Multi-objective optimization methods facilitate designers, engineers, and researchers to make decisions on appropriate trade-offs between various conflicting goals. A variety of deterministic and stochastic multi-objective optimization methods are developed in this book. Beginning ...
Added: September 29, 2017
Дробышевский М., Коршунов А., Turdakov D. Y., Proceedings of the Institute for System Programming of the RAS 2016 Vol. 28 No. 6 P. 153–170
В статье представлены новые алгоритмы расчета модулярности для направленных взвешенных графов с пересекающимися сообществами. Рассматриваются несколько подходов для вычисления модулярности и их расширения. Учитывая вычислительную сложность известных подходов, предлагаются два параллельных расширения, масштабируемых на графы с более 104 вершин. ...
Added: August 28, 2017