Publications related to Approximate Steepest Coordinate Descent

Modelling and design of CMOS SPAD sensors for quantum random number generation

Modern digital connectivity has necessitated the creation of robust methods for securely storing and transferring data. At the heart of all security infrastructure is the random number generator (RNG). While random numbers find use in a variety of applicat ...

EPFL2023

On the Double Descent of Random Features Models Trained with SGD

Volkan Cevher, Fanghui Liu

We study generalization properties of random features (RF) regression in high dimensions optimized by stochastic gradient descent (SGD) in under-/overparameterized regime. In this work, we derive precise non-asymptotic error bounds of RF regression under b ...

2022

Automatic Content Curation of Visual Heritage

Mathieu Salzmann, Nicolas Henchoz, Delphine Ribes Lemay, Frédéric Kaplan, Valentine Bernasconi

Digitization and preservation of large heritage induce high maintenance costs to keep up with the technical standards and ensure sustainable access. Creating impactful usage is instrumental to justify the resources for long-term preservation. The Museum fü ...

2021

Collaborative Sampling in Generative Adversarial Networks

Alexandre Massoud Alahi, Yuejiang Liu, Parth Ashit Kothari

The standard practice in Generative Adversarial Networks (GANs) discards the discriminator during sampling. However, this sampling method loses valuable information learned by the discriminator regarding the data distribution. In this work, we propose a co ...

2020

Multivariate extremes over a random number of observations

Simone Padoan, Stefano Rizzelli

The classical multivariate extreme-value theory concerns the modeling of extremes in a multivariate random sample, suggesting the use of max-stable distributions. In this work, the classical theory is extended to the case where aggregated data, such as max ...

WILEY2021

Multilevel weighted least squares polynomial approximation

Fabio Nobile

Weighted least squares polynomial approximation uses random samples to determine projections of functions onto spaces of polynomials. It has been shown that, using an optimal distribution of sample locations, the number of samples required to achieve quasi ...

2020

Rethinking Sampling in Parallel MRI: A Data-Driven Approach

Volkan Cevher, Baran Gözcü, Thomas Sanchez

In the last decade, Compressive Sensing (CS) has emerged as the most promising, model-driven approach to accelerate MRI scans. CS relies on the key sparsity assumption and proposes random sampling for data acquisition. The practical CS approaches in MRI em ...

IEEE2019

Some Proofs of Conditional and Joint Biases in RC4 Stream Cipher

Subhadeep Banik

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifi- cations and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 ...

2018

Theoretical Understanding of Some Conditional and Joint Biases in RC4 Stream Cipher

Subhadeep Banik

In this paper we present proofs for the new biases in RC4 which were experimentally found and listed out (without theoretical justifications and proofs) in a paper by Vanhoef et al. in USENIX 2015. Their purpose was to exploit the vulnerabilities of RC4 in ...

IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG2018

Signatures of selection and environmental adaptation across the goat genome post-domestication

Stéphane Joost, Estelle Rochat

Background: Since goat was domesticated 10,000 years ago, many factors have contributed to the differentiation of goat breeds and these are classified mainly into two types: (i) adaptation to different breeding systems and/or purposes and (ii) adaptation t ...

2018

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

Quasi-random numbers for copula models

Mathieu Jacques David Cambou

The present work addresses the question how sampling algorithms for commonly applied copula models can be adapted to account for quasi-random numbers. Besides sampling methods such as the conditional distribution method (based on a one-to-one transformatio ...

Springer2017

Faster Coordinate Descent via Adaptive Importance Sampling

Volkan Cevher, Dmytro Perekrestenko, Martin Jaggi

Coordinate descent methods employ random partial updates of decision variables in order to solve huge-scale convex optimization problems. In this work, we introduce new adaptive rules for the random selection of their updates. By adaptive, we mean that our ...

PMLR2017

Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification

Divesh Aggarwal

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a weak random source x with min-entropy k and a uniformly random seed Y of length d, and ...

Ieee2016

A Comment on “Computational Complexity of Stochastic Programming Problems”

Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann

Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Mathematical Programming A, 106(3):423–432, 200 ...

Springer Heidelberg2016

Optimization of mesh hierarchies in multilevel Monte Carlo samplers

Fabio Nobile, Erik Gustaf Bogislaw Von Schwerin

We perform a general optimization of the parameters in the multilevel Monte Carlo (MLMC) discretization hierarchy based on uniform discretization methods with general approximation orders and computational costs. We optimize hierarchies with geometric and ...

2016

Compressive Spectral Clustering

Pierre Vandergheynst, Rémi Gribonval, Gilles Puy, Nicolas Tremblay

Spectral clustering has become a popular technique due to its high performance in many contexts. It comprises three main steps: create a similarity graph between N objects to cluster, compute the first k eigenvectors of its Laplacian matrix to define a fea ...

2016

Error Analysis of the Dynamically Orthogonal Approximation of Time Dependent Random PDEs

Fabio Nobile, Eleonora Musharbash

In this work we discuss the dynamically orthogonal (DO) approximation of time dependent partial differential equations with random data. The approximate solution is expanded at each time instant on a time dependent orthonormal basis in the physical domain ...

2015

Convergence of quasi-optimal Stochastic Galerkin methods for a class of PDES with random coefficients

Fabio Nobile, Lorenzo Tamellini

In this work we consider quasi-optimal versions of the Stochastic Galerkin method for solving linear elliptic PDEs with stochastic coefficients. In particular, we consider the case of a finite number

N

of random inputs and an analytic dependence of the s ...

2014

Efficiency of random search procedures along the silicon cluster series Sin (n=5-10, 15 and 20)

Anne-Clémence Corminboeuf, Fabrice Avaltroni

The efficiency of the simplest isomeric search procedure consisting in random generation of sets of atomic coordinates followed by density functional theory geometry optimization is tested on the silicon cluster series (Si-5-10,Si-15,Si-20). Criteria such ...

Wiley-Blackwell2011