arXiv research

New private algorithms for online learning improve regret in high privacy regimes.

Lazy Gradient Descent outperforms existing polytope algorithms in pseudo-regret.

Counterfactual regret minimization (CFR) is the most popular algorithm on solving two-player zero-sum extensive games with imperfect information and achieves state-of-the-art performance in practice. However, the performance of CFR is not fully understood, since empirical results on the regret are much better than the …

Stochastic principal component analysis (SPCA) has become a popular dimensionality reduction strategy for large, high-dimensional datasets. We derive a simplified algorithm, called Lazy SPCA, which has reduced computational complexity and is better suited for large-scale distributed computation. We prove that SPCA and …

Gradient descent can find better tensor decompositions than lazy training in over-parameterized settings.

ABC algorithms involve a large number of simulations from the model of interest, which can be very computationally costly. This paper summarises the lazy ABC algorithm of Prangle (2015), which reduces the computational demand by abandoning many unpromising simulations before completion. By using a random stopping decis…

In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate $O\left(\frac{1}{\varepsilon^2}\right)$ improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of Hazan an…

We study Bayesian optimal control of a general class of smoothly parameterized Markov decision problems. Since computing the optimal control is computationally expensive, we design an algorithm that trades off performance for computational efficiency. The algorithm is a lazy posterior sampling method that maintains a d…

We discuss the approximation of the value function for infinite-horizon discounted Markov Reward Processes (MRP) with nonlinear functions trained with the Temporal-Difference (TD) learning algorithm. We first consider this problem under a certain scaling of the approximating function, leading to a regime called lazy tr…

Quantum machine learning faces 'laziness' and 'barren plateaus', but noise can mitigate the latter.

Unified formula for training dynamics of linear networks combining lazy and balanced regimes.

Clapping reduces memory usage in distributed optimization by reusing data samples.

Lazy neural networks are vulnerable to adversarial attacks.

A new method simulates a lazy version of a Markov chain for empirical inference.

Study introduces a new investment strategy model using lazy factor and probability weights.

Lazy, perfectly informed investors trade infrequently due to costs.

Transformers capture combinatorial tasks with bounded error and logarithmic sample dependence.

Deep networks prioritize easier examples over harder ones, leading to faster training.

Grokking occurs when neural networks transition from lazy to rich training dynamics, fitting initial features before generalizing.

Study shows optimal model performance at critical level of feature learning.

Study on network-valued processes with asynchronous updates, proving consistency in community and changepoint estimation.

Study on rich regime training in deep learning, finding active parameters in bottom layers.

We present a new algorithm based on an gradient ascent for a general Active Exploration bandit problem in the fixed confidence setting. This problem encompasses several well studied problems such that the Best Arm Identification or Thresholding Bandits. It consists of a new sampling rule based on an online lazy mirror …

We propose a new scalable algorithm for holistic linear regression building on Bertsimas & King (2016). Specifically, we develop new theory to model significance and multicollinearity as lazy constraints rather than checking the conditions iteratively. The resulting algorithm scales with the number of samples $n$ in th…

New method converts and optimizes sampling schedules for generative models.

We propose a framework for solving high-dimensional Bayesian inference problems using \emph{structure-exploiting} low-dimensional transport maps or flows. These maps are confined to a low-dimensional subspace (hence, lazy), and the subspace is identified by minimizing an upper bound on the Kullback--Leibler divergence …

dSMC improves parallel processing of state-space models.

We explore how neural networks train to zero loss, focusing on initial scale.

ExDAG solves DAG learning problems with low structural Hamming distance.

A method learns common bias for multiple low-variance tasks without hyper-parameter tuning.

Study on adversarial robustness in neural networks across initialization and training phases.

Transformers learn rich in-context dependencies efficiently.

Quantum RL algorithm achieves logarithmic regret for exploration.

Analyzes neural networks using linear models to understand their behavior.

LAZO reduces query complexity and variance in ZO methods.

New method trains shallow neural networks with subquadratic width scaling.

New method for causal discovery in high dimensions with confounder blanket assumption.

LazyDINO efficiently solves high-dimensional Bayesian inverse problems with fast and scalable solutions.

Two distinct limits for deep learning have been derived as the network width $h\rightarrow \infty$, depending on how the weights of the last layer scale with $h$. In the Neural Tangent Kernel (NTK) limit, the dynamics becomes linear in the weights and is described by a frozen kernel $Θ$. By contrast, in the Mean-Field …

Auto-CEI improves LLM reasoning by balancing assertiveness and conservativeness.

Mirror flow in shallow neural networks shows similar implicit bias to gradient flow, with key differences in curvature penalties.

Use simplified layerwise linear models to understand neural dynamics.

The issue of computing (co)homology generators of a cell complex is gaining a pivotal role in various branches of science. While this issue can be rigorously solved in polynomial time, it is still overly demanding for large scale problems. Drawing inspiration from low-frequency electrodynamics, this paper presents a ph…

Exact solutions reveal how unbalanced initializations promote rapid feature learning in neural networks.

Deep networks generalize well even when they fit training data perfectly, thanks to overparametrization.

We consider online learning problems where the aim is to achieve regret which is efficient in the sense that it is the same order as the lowest regret amongst K experts. This is a substantially stronger requirement that achieving $O(\sqrt{n})$ or $O(\log n)$ regret with respect to the best expert and standard algorithm…

Study on how adversarial training affects neural network kernels and robustness.

Functional AD for Weil algebra computations.