• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Oracle Complexity Separation in Convex Optimization
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
November 17, 2026
Physicists Show How a Solvent Shapes the Response of Drug Molecules
Many drug molecules can switch between different three-dimensional shapes. Using a mathematical model of ibuprofen dissolved in supercritical CO₂, researchers from HSE University and the Institute of Solution Chemistry of the Russian Academy of Sciences have shown that the solvent can make these molecules appear to respond unusually slowly. The molecules themselves continue to change shape rapidly, but their surroundings rearrange much more slowly, and this lag shows up in the measurements. The study has been published in The Journal of Chemical Physics. 
November 10, 2026
Physicists Train AI to Optimise Particle Beams in Accelerators
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science and the Budker Institute of Nuclear Physics at the Siberian Branch of the Russian Academy of Sciences have developed RLABC (Reinforcement Learning for Accelerator Beamline Control), a framework that uses reinforcement learning to identify optimal settings for a particle accelerator. In a computer simulation, RLABC optimised the accelerator's parameters to achieve a particle transmission rate of 70%. The study has been published in Computer Physics Communications.
November 9, 2026
'Organ-on-a-Chip Technology Could Eliminate the Need for Animal Testing'
The Laboratory of Molecular Physiology at the HSE Faculty of Biology and Biotechnology investigates how molecular regulators known as microRNAs control gene expression and contribute to the development of diseases, including cancer, viral and inflammatory conditions, and pregnancy complications. At HSE University, researchers develop organ-on-a-chip models: miniature devices containing living cells that mimic the functions of human organs, such as the placenta and intestines. These models help researchers understand how diseases develop and how drugs affect them. HSE News Service spoke with Evgeny Knyazev, Head of the Laboratory.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Oracle Complexity Separation in Convex Optimization

Journal of Optimization Theory and Applications. 2022. Vol. 193. No. 1-3. P. 462–490.
Ivanova A., Dvurechensky P., Vorontsova E., Pasechnyuk D., Gasnikov A., Dvinskikh D., Tyurin A.

Many convex optimization problems have structured objective functions written as a sum of functions with different oracle types (e.g., full gradient, coordinate derivative, stochastic gradient) and different arithmetic operations complexity of these oracles. In the strongly convex case, these functions also have different condition numbers that eventually define the iteration complexity of first-order methods and the number of oracle calls required to achieve a given accuracy. Motivated by the desire to call more expensive oracles fewer times, we consider the problem of minimizing the sum of two functions and propose a generic algorithmic framework to separate oracle complexities for each function. The latter means that the oracle for each function is called the number of times that coincide with the oracle complexity for the case when the second function is absent. Our general accelerated framework covers the setting of (strongly) convex objectives, the setting when both parts are given through full coordinate oracle, as well as when one of them is given by coordinate derivative oracle or has the finite-sum structure and is available through stochastic gradient oracle. In the latter two cases, we obtain accelerated random coordinate descent and accelerated variance reduced methods with oracle complexity separation.

Research target: Mathematics
Language: English
DOI
Text on another site
Keywords: convex optimizationComplexityfirst-order methodsStochastic gradientRandom coordinate descent
Publication based on the results of:
Stochastic Algorithms in Machine Learning (2022)
Similar publications
Uniqueness of addition in Schrödinger algebras
Sosnov G., / Series arXiv "math". 2026.
We obtain a criterion for the uniqueness of addition in Schrödinger Lie algebras, applicable to both bijections and injections. This allows us to construct the first example of a Lie algebra with unique addition and a non-trivial center over a field of characteristic zero. Furthermore, a necessary and sufficient condition is established for the Schrödinger ...
Added: November 19, 2026
Uniqueness of addition in Lie rings gl_n(K) and sl_n(K)
Sosnov G., / Series math "arxiv.org". 2026.
We prove that for any Lie ring R and any commutator-preserving bijection α:gln(K)→R, the map α is additive on sln(K), where n≥2 and K is an arbitrary field. Using this result we find criteria for Lie rings gln(K) and sln(K) to be unique addition. We also show that any commutator-preserving injection of Lie rings β:sl2(K)→S ...
Added: November 19, 2026
Soliton turbulence within the modified Benjamin–Bona–Mahony equation
Flamarion M. V., Pelinovsky E., Physica D: Nonlinear Phenomena 2027 Vol. 500 Article 135452
In this work, we investigate soliton turbulence in the modified Benjamin–Bona–Mahony (mBBM) equation. A key advantage of this model is that it admits solitary wave solutions of both polarities while also being interpretable as a perturbation of the integrable modified Korteweg–de Vries (mKdV) equation. This framework enables a direct comparison of the main properties of soliton turbulence in ...
Added: November 18, 2026
Топология 3-многообразий, допускающих НМС-потоки с единственной седловой орбитой
Yagilev A., Pochinka O., Shubin D., Математический сборник 2026 Т. 217 № 11 С. 130–144
Рассматриваются неособые потоки Морса-Смейла (НМС-потоки) на замкнутых ориентируемых 3-многообразиях $M^3$, в предположении, что среди периодических орбит ровно одна седловая. Устанавливается, что  многообразие $M^3$ допускает такой поток  тогда и только тогда, когда оно гомеоморфно  линзовому пространству, связной сумме линзовых пространств или многообразию Зейферта вида $M(\mathbb S^2, (p_1,q_1), (p_2,q_2), (p_3,q_3))$. ...
Added: November 17, 2026
The medial septum model as a pacemaker of theta rhythm: the key role of short-term synaptic plasticity
Mysin I. E., Dubrovin S. V., Cognitive Neurodynamics 2026 Vol. 20 No. 191 P. 1–30
The hippocampal theta rhythm is crucial for memory and navigation. It is paced by parvalbumin-expressing GABAergic neurons in the medial septum. These neurons segregate into two subpopulations—Teevra and Komal cells—which fire in anti-phase bursts at theta frequency, with a stable phase shift of approximately 150 degrees, and exhibit mutual inhibition. While essential, the network mechanism ...
Added: November 14, 2026
Upper Bound for Permanent Saturation of Metric Graphs using Interval Exchange Transformations
Ермолаев Е. С., Chernyshev V. L., Skripchenko A., Journal of Nonlinear Science 2026 Vol. 36 No. 122 (2026) P. 1–37
We study upper bounds for the moment of permanent -saturation in finite metric graphs. The dynamics is generated by moving points travelling with unit speed along edges and branching into all outgoing directions whenever they reach a vertex. We first reformulate this branched dynamics in terms of birth times at vertices and prove a sufficient ...
Added: November 12, 2026
On β-function of 𝒩 = 2 supersymmetric integrable sigma models. Part II
Alfimov Mikhail, Kurakin Andrey, Journal of High Energy Physics 2026 Vol. 2026 Article 99
We continue studying regularization scheme dependence of the 𝒩 = 2 supersymmetric sigma models. In the present work the previous result for the four loop β-function is extended to the five loop order. Namely, we find the renormalization scheme, in which the fifth loop contribution is completely eliminated, while the fourth loop contribution is represented ...
Added: November 12, 2026
Kripke Completeness For Predicate Modal Logics Of Bounded Alternativity: First Steps
Shehtman V. B., Shkatov D., Review of Symbolic Logic 2026 Vol. 19 No. 4 P. 859–882
We study Kripke completeness for predicate modal logics with propositional axioms of bounded alternativity corresponding to the condition on Kripke frames that every world sees at most n worlds. We prove that minimal predicate modal logics with axioms of bounded alternativity, as well as their extensions with the axiom of reflexivity, are strongly Kripke complete, whereas the ...
Added: November 12, 2026
On flexibility of trinomial varieties
Ignatev M., Vilkin T., Mediterranean Journal of Mathematics 2026 Vol. 23 No. 2 Article 70
Trinomial varieties are affine varieties given by a system of equations consisting of polynomials with three terms. Such varieties are total coordinate spaces of normal varieties with torus action of complexity one. For an affine variety X, we consider the subgroup SAut(X) of the automorphism group generated by all algebraic subgroups isomorphic to the additive ...
Added: November 12, 2026
Линейные отображения, сохраняющие матрицы с n или n − 1 различными собственными значениями
Maksaev A., Promyslov V., Тишутин П. С., Записки научных семинаров ПОМИ РАН 2026 Т. 554 С. 218–235
Let K be an algebraically closed field and let ℰₖ be the set of n × n matrices over K with exactly k distinct eigenvalues. Previously, the classification of linear maps T: Mₙ(K) → Mₙ(K) satisfying T(ℰₙ) ⊆ ℰₙ was obtained for invertible maps over fields of characteristic 0. In this paper, the classification is ...
Added: November 11, 2026
Nonexistence of Energy Function for Surface Diffeomorphisms with Nontrivial Basic Sets of Serpentine Geometric Type
Barinova M., Tirskaya Karina, Владикавказский математический журнал 2026 Vol. 28 No. 3 P. 25–43
In this paper, the problem of the existence of an energy function for discrete dynamical systems defined by structurally stable diffeomorphisms is studied. For the considered class of dynamical systems, such a function is defined as a continuous function that decreases along the orbits of the system outside the non-wandering set and remains constant on ...
Added: November 11, 2026
О статистических свойствах наилучших диофантовых приближений
Illarionov A., Математический сборник 2026 Т. 217 № 11 С. 56–87
Let $b(\alpha;T)$ be the number of best simultaneous Diophantine approximations with common denominator $\le T$ to the point $\alpha \in {\Bbb R}^n$. We derive asymptotic formulas for the mean value of this quantity (averaging is performed over all rational points of the form $\alpha = (k_1/N,\ldots, k_n/N)$, $N\le R$), as well as for its mathematical ...
Added: November 10, 2026
К теореме Гудмана-Штрауса
Vereshchagin N., Математический сборник 2026 Т. 217 № 10 С. 3–46
Теорема Гудмана-Штрауса утверждает, что для “почти всякой” подстановки семейство подстановочных замощений софично, т.е. может быть задано локальными правилами для некоторой раскраски плиток. Условия на подстановку, гарантирующие софичность, довольно сложные. В настоящей работе мы предлагаем версию теоремы Гудмана-Штрауса с более простыми условиями на подстановку. Хотя эти условия достаточно ограничительны, мы показываем, что в сочетании с двумя простыми приемами (взятием достаточно ...
Added: November 10, 2026
Dispersionless modified DKP hierarchy as the Yang-Baxter equation
Zabrodin A., Journal of Mathematical Physics 2026 Vol. 67 No. 10 Article 103505
We show that the dispersionless version of the modified DKP hierarchy originally defined as the limit of relations for the tau-function of the Hirota-Miwa type has an equivalent reformulation as the Yang-Baxter equation for Baxter's R-matrix of Boltzmann weights for the 8-vertex model. ...
Added: November 9, 2026
MFL-ScrollNet: Recurrent Sliding-Window Detection for Panoramic Pipeline Magnetic Flux Leakage Images
Aleksei Samarin, Belous F., Торопов А. Г. et al., Technologies 2026 Vol. 14 No. 11 P. 1–21
Abstract Automated interpretation of magnetic flux leakage (MFL) data is central to condition assessment of long-distance oil and gas pipelines. Yet, full-resolution panoramas are difficult to process without either suppressing small anomalies through resizing or fragmenting elongated objects at sliding-window boundaries. We propose MFL-ScrollNet, a recurrent sliding-window detector that formulates panoramic analysis as an ordered sequence ...
Added: November 8, 2026
Обобщение матричной теоремы о деревьях для пар деревьев
Retinsky V., Функциональный анализ и его приложения 2026 Т. 60 № 4 С. 83–100
Приведено обобщение матричной теоремы о деревьях на случай перечисления пар остовных деревьев. Это обобщение включает в качестве частных случаев и унифицирует сразу несколько известных ранее результатов, в частности классическую теорему Кирхгофа, теорему Масбаума–Вайнтроба о перечислении 3-деревьев, а также аналог матричной теоремы о деревьях для перечисления 4-элементов Кирхгофа. ...
Added: November 5, 2026
Спаривания на алгебре рядов Лорана над кольцом
Levashev V., Математические заметки 2026 Т. 120 № 5 С. 843–846
Пусть 𝐴 – коммутативное ассоциативное кольцо с единицей и 𝐴((𝑡)) = 𝐴[[𝑡]][𝑡−1] – кольцо рядов Лорана над 𝐴. Алгебра 𝐴((𝑡)) имеет естественную топологию, где 𝐴 – подмодули вида 𝑡𝑚𝐴[[𝑡]] образуют базу окрестностей нуля. Пусть также Ω1𝐴((𝑡))/𝐴 – модуль кэлеровых 1-дифференциалов 𝐴((𝑡)) над 𝐴. ...
Added: November 5, 2026
Spectral structure of the mixed Hessian of the dispersionless Toda τ-function
Алексеев О. В., Letters in Mathematical Physics 2026 Vol. 116 No. 5 Article 132
We study the mixed Hessian of the dispersionless Toda \(\tau\)-function for the one-harmonic \(s\)-fold symmetric conformal map \(f(w)=r\bigl(w+\zeta w^{1-s}\bigr)\), where \(r>0\) is the exterior conformal radius and \(\zeta>0\) is the dimensionless shape parameter. This Hessian is the susceptibility matrix generated by the inverse conformal map. Our spectral statements are formulated for its weighted symmetry-block realizations ...
Added: November 5, 2026
Introduction to Complexity Theory for Big History
David J. L., Grinin L. E., Korotayev A., , in: Complexity in Universal Evolution. A Big History Perspective.: Springer, 2026. Ch. 2 P. 29–90.
This chapter explores the role of complexity dynamics in Big History through an integrative theoretical framework that spans physical, chemical, biological, social, cognitive, and civilizational domains. Building on foundational work in systemstheory,thermodynamics,andevolutionarytheory,thechapterarguesthat complexity can serve as a conceptual bridge across disciplines. By examining how complexity emerges, is sustained, and transforms across thresholds, as well as ...
Added: August 10, 2026
Complexity in Universal Evolution. A Big History Perspective
David J. L., Leonid Grinin, Korotayev A., Springer, 2026.
Complexity is widely acknowledged as a foundational and pivotal concept in Big History, offering a unifying lens through which to examine the emergence and development of systems—from particles and galaxies to life, civilizations, and beyond. Yet, despite its centrality, major gaps remain in how we define, measure, and interpret complexity across different phases and scales. ...
Added: August 7, 2026
Exploring New Frontiers in Vertical Federated Learning: the Role of Saddle Point Reformulation
Beznosikov A., Kormakov G., Grigorievskiy A. et al., Journal of Optimization Theory and Applications 2026 Vol. 209 Article 18
The objective of Vertical Federated Learning (VFL) is to collectively train a model using features available on different devices while sharing the same users. This paper focuses on the saddle point reformulation of the VFL problem via the classical Lagrangian function. We first demonstrate how this formulation can be solved using deterministic methods.More importantly, we explore various stochastic modifications to ...
Added: June 17, 2026
On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
Borodich E., Gasnikov A., Kovalev D., , in: Volume 267: International Conference on Machine Learning, 13-19 July 2025, Vancouver Convention Center, Vancouver, CanadaVol. 267.: [б.и.], 2025. P. 5045–5100.
Added: November 18, 2025
Navigating Complexity in Big History. Exploring Periodization Across Cosmic and Biosocial Dimensions
David J. L., L. Grinin, Korotayev A., Springer, 2025.
In the editors’ introduction (Chapter 1), the effort to periodize is placed within the historical context along with considerations from complexity science. Subsequent chapters explore various aspects of periodization and complexity by (a) identifying symmetrical cosmic and biosocial trends, (b) testing rigor and criteria for evaluating periodization, (c) attempting to integrate different approaches through multiple ...
Added: May 12, 2025
Solving Convex Min-Min Problems with Smoothness and Strong Convexity in One Group of Variables and Low Dimension in the Other
Gladin E., Alkousa M., Gasnikov A., Automation and Remote Control 2021 Vol. 82 P. 1679–1691
The article deals with some approaches to solving convex problems of the min-min type with smoothness and strong convexity in only one of the two groups of variables. It is shown that the proposed approaches based on Vaidya’s method, the fast gradient method, and the accelerated gradient method with variance reduction have linear convergence. It ...
Added: November 29, 2024
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit