@inproceedings{MartinezRubioWirthPokutta2023, author = {Mart{\´i}nez-Rubio, David and Wirth, Elias and Pokutta, Sebastian}, title = {Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond}, volume = {195}, booktitle = {Proceedings of Machine Learning Research}, pages = {1 -- 35}, year = {2023}, abstract = {It has recently been shown that ISTA, an unaccelerated optimization method, presents sparse updates for the ℓ1-regularized undirected personalized PageRank problem (Fountoulakis et al., 2019), leading to cheap iteration complexity and providing the same guarantees as the approximate personalized PageRank algorithm (APPR) (Andersen et al., 2006). In this work, we design an accelerated optimization algorithm for this problem that also performs sparse updates, providing an affirmative answer to the COLT 2022 open question of Fountoulakis and Yang (2022). Acceleration provides a reduced dependence on the condition number, while the dependence on the sparsity in our updates differs from the ISTA approach. Further, we design another algorithm by using conjugate directions to achieve an exact solution while exploiting sparsity. Both algorithms lead to faster convergence for certain parameter regimes. Our findings apply beyond PageRank and work for any quadratic objective whose Hessian is a positive-definite 푀-matrix.}, language = {en} } @article{HunkenschroederPokuttaWeismantel2022, author = {Hunkenschr{\"o}der, Christoph and Pokutta, Sebastian and Weismantel, Robert}, title = {Optimizing a low-dimensional convex function over a high-dimensional cub}, journal = {SIAM Journal on Optimization}, year = {2022}, language = {en} } @inproceedings{MacDonaldBesanconPokutta2022, author = {MacDonald, Jan and Besan{\c{c}}on, Mathieu and Pokutta, Sebastian}, title = {Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{TsujiTanakaPokutta2022, author = {Tsuji, Kazuma and Tanaka, Ken'ichiro and Pokutta, Sebastian}, title = {Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} } @inproceedings{WaeldchenHuberPokutta2022, author = {W{\"a}ldchen, Stephan and Huber, Felix and Pokutta, Sebastian}, title = {Training Characteristic Functions with Reinforcement Learning: XAI-methods Play Connect Four}, booktitle = {Proceedings of the International Conference on Machine Learning}, year = {2022}, language = {en} }