Publications associées à 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