Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation

A. Tsyganov; E. Frolov; S. Samsonov; M. Rakhuba

doi:10.1609/aaai.v40i31.39802

АБВ
АБВ
АБВ

Обычная версия сайта

Priority areas

by year

Subject

News

July 20, 2026

Scientists Create Open Dataset for Studying Concentration

A team of Russian researchers, including scientists from HSE University–St Petersburg, has developed the first open multimodal dataset containing recordings of brain activity, heart function, and video observations to help researchers understand what happens in the human brain during deep concentration. In the future, the dataset could accelerate the development of neural interfaces, rehabilitation technologies, and AI systems. The article has been published in Scientific Data.

July 20, 2026

‘Science Is Universal-It Knows No Borders

Fuad Aleskerov, Tenured Professor and Director of the International Centre of Decision Choice and Analysis at HSE University, together with his colleagues, has developed methods of network analysis in bibliometrics that have made it possible to identify patterns in the appearance and citation of publications in academic journals, as well as their influence on each other. When one or a number of studies are frequently cited by a wide range of journals, this is an indicator that the research is of high quality. By contrast, extensive cross-citation within a limited group of journals increases the likelihood of identifying a network of predatory publications.

July 20, 2026

Scientists Propose Method for More Efficient Resource Use in Machine Learning

An international group of researchers, including mathematicians from the AI and Digital Science Institute at the HSE Faculty of Computer Science, has provided a theoretical justification for a simple and computationally efficient method of estimating uncertainty in Stochastic Gradient Descent (SGD). The paper has been published on the scientific preprint server arXiv.org and presented at AISTATS 2026.

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

Publications

?

Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation

P. 26010–26018.

Tsyganov A., Frolov E., Samsonov S., Rakhuba M.

In this paper, we propose new randomized algorithms for estimating the two-to-infinity and one-to-two norms in a matrixfree setting, using only matrix-vector multiplications. Our methods are based on appropriate modifications of Hutchinson’s diagonal estimator and its Hutch++ version. We provide oracle complexity bounds for both modifications. We further illustrate the practical utility of our algorithms for Jacobianbased regularization in deep neural network training on image classification tasks. We also demonstrate that our methodology can be applied to mitigate the effect of adversarial attacks in the domain of recommender systems.

Keywords: randomized algorithms

In book

Proceedings of the AAAI Conference on Artificial Intelligence. AAAI-26: AAAI Technical Track on Planning, Routing, and Scheduling; AAAI Technical Track on Reasoning under Uncertainty; AAAI Technical Track on Search and Optimization. Main Track, volume 40 no. 43

American Association for Artificial Intelligence (AAAI) Press, 2026.

A randomized coordinate descent method with volume sampling

Rodomanov A., Kropotov D., SIAM Journal on Optimization 2020 Vol. 30 No. 3 P. 1878–1904

We analyze the coordinate descent method with a new coordinate selection strategy, called volume sampling. This strategy prescribes selecting subsets of variables of certain size proportionally to the determinants of principal submatrices of the matrix, which bounds the curvature of the objective function. In the particular case when the size of the subsets equals one, ...

Added: July 29, 2020