Zobrazeno 1 - 10
of 76
pro vyhledávání: '"Loho, Georg"'
We present a polynomial-time reduction from max-average constraints to the feasibility problem for semidefinite programs. This shows that Condon's simple stochastic games, stochastic mean payoff games, and in particular mean payoff games and parity g
Externí odkaz:
http://arxiv.org/abs/2411.09646
Autor:
Hertrich, Christoph, Loho, Georg
Neural networks with piecewise linear activation functions, such as rectified linear units (ReLU) or maxout, are among the most fundamental models in modern machine learning. We make a step towards proving lower bounds on the size of such neural netw
Externí odkaz:
http://arxiv.org/abs/2411.03006
We consider a binary classifier defined as the sign of a tropical rational function, that is, as the difference of two convex piecewise linear functions. The parameter space of ReLU neural networks is contained as a semialgebraic set inside the param
Externí odkaz:
http://arxiv.org/abs/2403.11871
We unify the study of quotients of matroids, polymatroids, valuated matroids and strong maps of submodular functions in the framework of Murota's discrete convex analysis. As a main result, we compile a list of ten equivalent characterizations of quo
Externí odkaz:
http://arxiv.org/abs/2403.07751
Symmetric strategy improvement is an algorithm introduced by Schewe et al. (ICALP 2015) that can be used to solve two-player games on directed graphs such as parity games and mean payoff games. In contrast to the usual well-known strategy improvement
Externí odkaz:
http://arxiv.org/abs/2309.02223
We prove that the set of functions representable by ReLU neural networks with integer weights strictly increases with the network depth while allowing arbitrary width. More precisely, we show that $\lceil\log_2(n)\rceil$ hidden layers are indeed nece
Externí odkaz:
http://arxiv.org/abs/2302.12553
A set function can be extended to the unit cube in various ways; the correlation gap measures the ratio between two natural extensions. This quantity has been identified as the performance guarantee in a range of approximation algorithms and mechanis
Externí odkaz:
http://arxiv.org/abs/2209.09896
Autor:
Loho, Georg, Skomra, Mateusz
We extend the fundamentals for tropical convexity beyond the tropically positive orthant expanding the theory developed by Loho and V\'egh (ITCS 2020). We study two notions of convexity for signed tropical numbers called 'TO-convexity' (formerly 'sig
Externí odkaz:
http://arxiv.org/abs/2206.13919
We develop a new `subspace layered least squares' interior point method (IPM) for solving linear programs. Applied to an $n$-variable linear program in standard form, the iteration complexity of our IPM is up to an $O(n^{1.5} \log n)$ factor upper bo
Externí odkaz:
http://arxiv.org/abs/2206.08810
We initiate the study of positive-tropical generators as positive analogues of the concept of tropical bases. Applying this to the tropicalization of determinantal varieties, we develop criteria for characterizing their positive part. We focus on the
Externí odkaz:
http://arxiv.org/abs/2205.14972