A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Efficiently samples sequences without replacement for machine learning models.
SGD without replacement decouples into curvature-following and flatness-regularizing steps.
Paper closes convergence gap for SGD without replacement.
Sampling without replacement speeds up optimization in minimax problems.
The well-known Gumbel-Max trick for sampling from a categorical distribution can be extended to sample elements without replacement. We show how to implicitly apply this 'Gumbel-Top-' trick on a factorized distribution over sequences, allowing to draw exact samples without replacement using a Stochastic Beam Sea…
New sketches for weighted sampling without replacement improve accuracy and efficiency.
The paper introduces methods to quantify uncertainty in sampling without replacement.
New estimator reduces variance in discrete random variables.
Stochastic gradient methods for machine learning and optimization problems are usually analyzed assuming data points are sampled \emph{with} replacement. In practice, however, sampling \emph{without} replacement is very common, easier to implement in many cases, and often performs better. In this paper, we provide comp…
New research disproves a key conjecture in optimization.
We introduce a variant of Shepp's classical urn problem in which the optimal stopper does not know whether sampling from the urn is done with or without replacement. By considering the problem's continuous-time analog, we provide bounds on the value function and in the case of a balanced urn (with an equal number of ea…
We study stochastic gradient descent {\em without replacement} (\sgdwor) for smooth convex functions. \sgdwor is widely observed to converge faster than true \sgd where each sample is drawn independently {\em with replacement} \cite{bottou2009curiously} and hence, is more popular in practice. But it's convergence prope…
Optimal algorithms for online convex optimization with random order.
Randomized algorithms that base iteration-level decisions on samples from some pool are ubiquitous in machine learning and optimization. Examples include stochastic gradient descent and randomized coordinate descent. This paper makes progress at theoretically evaluating the difference in performance between sampling wi…
Crowdsourcing platforms are now extensively used for conducting subjective pairwise comparison studies. In this setting, a pairwise comparison dataset is typically gathered via random sampling, either \emph{with} or \emph{without} replacement. In this paper, we use tools from random graph theory to analyze these two ra…
A ravel is a spatial graph which is non-planar but contains no non-trivial knots or links. We characterize when a Montesinos tangle can become a ravel as the result of vertex closure with and without replacing some number of crossings by vertices.
RLFA estimates misstated monetary fraction with weighted sampling without replacement.
Differential privacy is a useful tool to build machine learning models which do not release too much information about the training data. We study the Rényi differential privacy of stochastic gradient descent when each training example is sampled without replacement (also known as cyclic SGD). Cyclic SGD is typically f…
Program synthesis has emerged as a successful approach to the image parsing task. Most prior works rely on a two-step scheme involving supervised pretraining of a Seq2Seq model with synthetic programs followed by reinforcement learning (RL) for fine-tuning with real reference images. Fully unsupervised approaches promi…
While machine learning has achieved remarkable results in a wide variety of domains, the training of models often requires large datasets that may need to be collected from different individuals. As sensitive information may be contained in the individual's dataset, sharing training data may lead to severe privacy conc…
Stochastic Gradient Descent underperforms on some problems, contrary to expectations.
This paper studies the convergence behaviour of dictionary learning via the Iterative Thresholding and K-residual Means (ITKrM) algorithm. On one hand it is proved that ITKrM is a contraction under much more relaxed conditions than previously necessary. On the other hand it is shown that there seem to exist stable fixe…
Let (M,g) be a smooth compact Riemannian manifold without boundary of dimension n>=6. We prove that {align*} \|u\|_{L^{2^*}(M,g)}^2 \le K^2\int_M\{|\nabla_g u|^2+c(n)R_gu^2\}dv_g +A\|u\|_{L^{2n/(n+2)}(M,g)}^2, {align*} for all u\in H^1(M), where 2^*=2n/(n-2), c(n)=(n-2)/[4(n-1)], R_g is the scalar curvature, $K^{-1}=\i…
Improved convergence for VIPs with SEG-RR, a variant of SEG with random reshuffling.
New convergence bounds for shuffling-based SGD methods in distributed learning.
We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algor…
Paper improves CI and CS for bounded means using betting and mixtures.
New insights into privacy guarantees for subsampled mechanisms under composition.
Knots without 2-torsion have minimal Khovanov homology rank.
Differentiable pipeline replaces non-differentiable CAE components for shape optimization.
Enhances mixture models with classifier-defined weights.
Formulates a Dueling Bandits problem for eliciting Kemeny rankings.
New research shows CI in few-shot learning is misleading due to sampling with replacement.
New algorithm optimizes PAC-Bayes bound without surrogate loss.
Extracts invariant features to predict Y without confounding by Z, using conditional independence and optimal transport.
The paper develops methods to estimate POMDPs from partial information.
A long-standing problem in the theory of stochastic gradient descent (SGD) is to prove that its without-replacement version RandomShuffle converges faster than the usual with-replacement version. We present the first (to our knowledge) non-asymptotic solution to this problem, which shows that after a "reasonable" numbe…
We develop the fundamental theorem of asset pricing in a probability-free infinite-dimensional setup. We replace the usual assumption of a prior probability by a certain continuity property in the state variable. Probabilities enter then endogenously as full support martingale measures (instead of equivalent martingale…
When building a unified vision system or gradually adding new capabilities to a system, the usual assumption is that training data for all tasks is always available. However, as the number of tasks grows, storing and retraining on such data becomes infeasible. A new problem arises where we add new capabilities to a Con…
This paper and its companion arXiv:1002.4564 have been replaced by arXiv:1602.05139. We give a general simple definition of JSJ decompositions by means of a universal maximality property. The JSJ decomposition should not be viewed as a tree (which is not uniquely defined) but as a canonical deformation space of trees. …
I show the equivalence between a model of financial contagion and the threshold model of global cascades proposed by Watts (2002). The model financial network comprises banks that hold risky external assets as well as interbank assets. It is shown that a simple threshold model can replicate the size and the frequency o…
New priors improve Bayesian neural networks without cooling.
Harmonic maps intersect all minimal surfaces with bounded curvature.
Spatial graphs study tangle replacement with equivalence classes.
We introduce new symplectic cut-and-paste operations that generalize the rational blowdown. In particular, we will define -replaceable plumbings to be those that, heuristically, can be symplectically replaced by Euler characteristic 4-manifolds. We will then classify 2-replaceable linear plumbings, construct 2-r…
Post-hoc explanations improve CNNs by replacing final linear layer with k-means classifier.
This is an up-to-date introduction to and overview of the Minimum Description Length (MDL) Principle, a theory of inductive inference that can be applied to general problems in statistics, machine learning and pattern recognition. While MDL was originally based on data compression ideas, this introduction can be read w…
Recent advances in optimization theory have shown that smooth strongly convex finite sums can be minimized faster than by treating them as a black box "batch" problem. In this work we introduce a new method in this class with a theoretical convergence rate four times faster than existing methods, for sums with sufficie…