Publications related to Log semiring

Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization

Volkan Cevher, Kimon Antonakopoulos, Efstratios Panteleimon Skoulakis, Leello Tadesse Dadi, Ali Kavis

We propose an adaptive variance-reduction method, called AdaSpider, for minimization of L-smooth, non-convex functions with a finite-sum structure. In essence, AdaSpider combines an AdaGrad-inspired [Duchi et al., 2011, McMahan & Streeter, 2010], but a fai ...

2022

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

Convergences of Regularized Algorithms and Stochastic Gradient Methods with Random Projections

Volkan Cevher, Junhong Lin

We study the least-squares regression problem over a Hilbert space, covering nonparametric regression over a reproducing kernel Hilbert space as a special case. We rst investigate regularized algorithms adapted to a projection operator on a closed subspace ...

2020

Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms

Volkan Cevher, Junhong Lin

We study generalization properties of distributed algorithms in the setting of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We first investigate distributed stochastic gradient methods (SGM), with mini-batches and multi-passes o ...

2020

On the Size of K-Cross-Free Families

János Pach, Andrei Kupavskii, Istvan Tomon

Two subsets A,B of an n-element ground set X are said to be crossing, if none of the four sets AB, A\B, B\A and X(AB) are empty. It was conjectured by Karzanov and Lomonosov forty years ago that if a family F of subsets of X does not contain k pairwise cr ...

SPRINGER HEIDELBERG2019

Stable high-order randomized cubature formulae in arbitrary dimension

Fabio Nobile, Giovanni Migliorati

We propose and analyse randomized cubature formulae for the numerical integration of functions with respect to a given probability measure μ defined on a domain Γ⊆ℝ^d, in any dimension d. Each cubature formula is conceived to be exact on a given finite dim ...

2022

Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms

Volkan Cevher, Junhong Lin

We study generalization properties of distributed algorithms in the setting of nonparametric regression over a reproducing kernel Hilbert space (RKHS). We first investigate distributed stochastic gradient methods (SGM), with mini-batches and multi-passes o ...

2018

Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets

Fabio Nobile, Giovanni Migliorati

We analyze the stability and accuracy of discrete least squares on multivariate polynomial spaces to approximate a given function depending on a multivariate random variable uniformly distributed on a hypercube. The polynomial approximation is calculated s ...

2015

Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations

Fabio Nobile, Giovanni Migliorati, Erik Gustaf Bogislaw Von Schwerin

We analyse the problem of approximating a multivariate function by discrete least-squares projection on a polynomial space starting from random, noise-free observations. An area of possible application of such technique is Uncertainty Quantification (UQ) f ...

2014

Approximation of Quantities of Interest in Stochastic PDEs by the Random Discrete $L^2$ Projection on Polynomial Spaces

Fabio Nobile, Giovanni Migliorati, Erik Gustaf Bogislaw Von Schwerin

In this work we consider the random discrete

L^2

projection on polynomial spaces (hereafter RDP) for the approximation of scalar quantities of interest (QOIs) related to the solution of a partial differential equation model with random input parameters. ...

Siam Publications2013

Perturbation Theory Of The Cosmological Log-Density Field

Julien Lesgourgues, Xin Wang

The matter density field exhibits a nearly lognormal probability density distribution after entering into the nonlinear regime. Recently, it has been shown that the shape of the power spectrum of a logarithmically transformed density field is very close to ...

2011

The Complexity of Renaming

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Omega(k) process steps for deterministic renaming into ...

Ieee Computer Soc Press, Customer Service Center, Po Box 3014, 10662 Los Vaqueros Circle, Los Alamitos, Ca 90720-1264 Usa2011

Optimal-Time Adaptive Strong Renaming, with Applications to Counting

Seth Gilbert, Dan Alistarh, Morteza Zadimoghaddam

We give two new randomized algorithms for tight renaming, both of which work against an adaptive adversary. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of