Powered by OpenAIRE graph
Found an issue? Give us feedback


The Complexity of Dynamic Matrix Problems
Funder: European CommissionProject code: 101039914 Call for proposal: ERC-2021-STG
Funded under: HE | HORIZON-AG Overall Budget: 1,439,410 EURFunder Contribution: 1,439,410 EUR

Modern data analysis and optimization rely on our ability to process rapidly evolving dynamic datasets, often involving matrix operations in very high dimensions. Dynamic data structures enable fast information-retrieval on these huge databases by maintain- ing implicit information on the underlying data. As such, understanding the power and limitations of dynamic (matrix) data structures is a fundamental question in theory and practice. Despite decades of research, there are still very basic dynamic problems whose complexity is (exponen- tially) far from understood – Bridging this gap is one of the centerpieces of this proposal. The second theme of this proposal is advancing the nascent role of dynamic data structures in continuous optimization. For over a century, the traditional focus of optimization research was on minimizing the rate of convergence of local-search methods. The last ∼3 years have witnessed the dramatic potential of dynamic data structures in reducing the cost-per-iteration of (Newton type) optimization algorithms, proclaiming that the bottleneck to accelerating literally thousands of algorithms, is efficient maintenance of dynamic matrix functions. This new framework is only at its early stages, but already led to breakthroughs on decade-old problems in computer science. This proposal will substantially develop this interdisciplinary theory, and identifies the mathematical machinery which would lead to ultra-fast first and second-order convex optimization. In the non-convex setting, this proposal demonstrates the game-changing potential of dynamic data structures and algebraic sketching techniques in achieving scalable training and inference of deep neural networks, a major challenge of modern AI. Our program is based on a novel connection of Kernel methods and compressed sensing techniques for approximate matrix multiplication.

Data Management Plans
Powered by OpenAIRE graph
Found an issue? Give us feedback

Do the share buttons not appear? Please make sure, any blocking addon is disabled, and then reload the page.

All Research products
<script type="text/javascript">
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=corda_____he::f37d077c779d160ed3d6cfc3a00d3fea&type=result"></script>');
For further information contact us at helpdesk@openaire.eu

No option selected