AI conference papers

AI conference paper library

Search papers from 30+ top conferences, including NeurIPS, ICLR, ICML, CVPR, ACL and AAAI. Filter by keyword, then open any paper for its abstract, authors and links.

COLT 2026

Learning Ising Models from Evolutions (Extended Abstract)

Jason Gaitonde, Ankur Moitra, Elchanan Mossel

In this work, we revisit the problem of learning the structure and parameters of an Ising model from dynamics. While the problem of learning from i.i.d. samples has been intensively studied in several communities, recent work has considered learning from temporally correlated samples arising from some stochastic process. However, all prior work studied this problem in the synthetic observation model that assumes knowledge of internal steps of the standard algorithm for generating samples, which goes far beyond what we should expect to naturally observe from the system evolution in important physics and network applications. Extending these algorithmic guarantees to more realistic observation models has been an important direction highlighted in recent work (Bresler, Gamarnik, Shah IEEE Trans. Inf. Theory 2018, Gaitonde, Moitra, Mossel STOC 2025). We give the first efficient algorithm for learning from the natural continuous-time observation model where we only observe the actual evolution of the state of the system, as opposed to usually unobservable details like failed update attempts of sites. For Ising models with maximum degree d, our algorithm first recovers the graph structure in 𝗉𝗈𝗅𝗒(d)· n^2log n time, which qualitatively matches the state-of-the-art even in the cleaner i.i.d. setting, and then estimates the parameters in additional O(2^d· n) time. Our analysis is based on a new family of cycle statistics, which crucially remains measurable for any stochastic process, and in fact succeeds more generally for a broad family of reversible, single-site Markov chains that includes both the Glauber dynamics and the Metropolis chain.

COLT 2026

Toward Simultaneously Optimal Regret in U-Calibration

Rafael Frongillo, Haipeng Luo, Nishant A Mehta, Jon Schneider

U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal O(√(T)) regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur Ω(√(T)) regret instead of the optimal O(log T) regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves Õ(√(T)) regret for every bounded proper loss and O(log T) regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using self-concordant noise. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.

COLT 2026

Space-Efficient Language Generation in the Limit

Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, Ola Svensson

We initiate a resource-aware theory of language generation in the limit under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language K and must eventually output a hallucination-free hypothesis language L ⊆ K while omitting at most Δ strings of K. We focus on 𝒞_s,k, the collection of languages recognized by DFAs with at most s states over an alphabet of size k, as the natural hypothesis class for memory-bounded learners. In the exponential-space regime, we prove that a learner can exactly identify the target K. Under a stricter memory budget, we characterize the strongest possible generation guarantees. In particular, we present a streaming algorithm using poly(s,k) space that converges to a hypothesis with generation gap Δ = O(k^2s-2). Moreover, the learned hypothesis captures every string in K of length at least 2s-1. We complement this result with a near-matching lower bound through a reduction from a standard communication complexity problem. Specifically, achieving generation gap Δ≤ k^(1-ε)s requires k^Ω(ε s) memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.

COLT 2026

Optimal Reconstruction from Linear Queries

Yuval Filmus, Shay Moran, Elizaveta Nesterova

We study the problem of reconstructing an unknown point in ℝ^d from approximate linear queries. This setting arises naturally in applications ranging from low-dimensional remote sensing and signal recovery to high-dimensional data analysis and privacy-sensitive inference. Our main goal is to characterize the optimal reconstruction error as a function of the number of queries T, the ambient dimension d, and the noise parameter δ. We first analyze the limit T →∞ and show that the optimal reconstruction error converges to the explicit value √(2d/(d+1)) δ, which plays a role analogous to the Bayes optimal error in supervised learning. When the dimension is fixed, we show that the excess error above this limit decays doubly exponentially fast as T →∞, a rate that is significantly faster than those typically encountered in learning curves. When the dimension grows, we show that a number of queries on the order of exp(d) is necessary and sufficient to achieve vanishing excess error. Finally, we introduce and analyze an improper variant of the reconstruction problem. From a technical perspective, our main contribution is a generalization of Jung’s theorem (1901). The classical theorem bounds the maximum possible radius of a set of diameter 1 and characterizes extremal bodies. Our generalization provides a robust variant that characterizes near-extremal bodies and is proved via geometric and dynamical arguments exploiting symmetry and Lie group actions.

COLT 2026

Defensive Generation

Gabriele Farina, Juan Carlos Perdomo

We study the problem of efficiently producing, in an online fashion, generative models of scalar, multiclass, and vector-valued outcomes that cannot be falsified on the basis of the observed data and a pre-specified collection of computational tests. Our contributions are twofold. First, we expand on connections between online high-dimensional multicalibration with respect to an RKHS and recent advances in expected variational inequality problems, enabling efficient algorithms for the former. We then apply this algorithmic machinery to the problem of outcome indistinguishability. Our procedure, Defensive Generation, is the first to efficiently produce online outcome indistinguishable generative models of non-Bernoulli outcomes that are unfalsifiable with respect to infinite classes of tests, including those that examine higher-order moments of the generated distributions. Furthermore, our method runs in near-linear time in the number of samples and achieves the optimal, vanishing 1/√(T) rate for generation error.

COLT 2026

Tight Sample Complexity Bounds for Entropic Best Policy Identification

Amer Essakine, Claire Vernade

We study best-policy identification for finite-horizon risk-sensitive reinforcement learning under the entropic risk measure. Recent work established a constant gap in the exponential horizon dependence between lower and upper bounds on the number of samples required to identify an approximately optimal policy. Precisely, known lower bounds scale in Ω(exp(|β|H)) where H is the horizon of the MDP, while the state-of-the-art upper bound achieves at best O(exp(2|β|H)) (Mortensen and Talebi, 2025) using a generative model. We show that this extra exponential factor can be traced to overly loose concentration control for exponential utilities. To close this open gap, we revisit the analysis of this problem through a forward-model-based algorithm building on KL-based exploration bonuses that we adapt to the entropic criterion. The improvement we get is due to two main novel technical innovations. We leverage the smoothness properties of the exponential utility to derive sharper concentration bounds, and we propose a new stopping rule that exploits further this tightness to obtain a sample complexity that matches the lower bound.

COLT 2026

The Sample Complexity of Multiclass and Sparse Contextual Bandits

Liad Erez, Fan Chen, Alon Cohen, Tomer Koren, Yishay Mansour, Shay Moran, Alexander Rakhlin

We study contextual bandits in the stochastic i.i.d. setting, where a learner observes contexts drawn from an unknown distribution, selects actions from a finite set 𝒜, and aims to identify an approximately optimal policy from a given class based on bandit feedback. Motivated by the important special case of bandit multiclass classification with zero-one rewards, we focus on the s-sparse setting in which, for every context, the underlying reward vector has L_1-norm at most s ≪ |𝒜|. Our main result is the design of algorithms that, with probability at least 1-δ, output an ε-optimal policy compared to policy class Π using O( ( s/ε^2 + |𝒜|/ε) log|Π|/δ) samples. We further extend this bound to general Natarajan classes and complement it with a matching lower bound (up to logarithmic factors), thereby closing a substantial gap left by prior work (Erez et al., 2024a,b; Erez and Koren, 2025), which incurred an additional Θ(|𝒜|^9) dependence. We obtain these results via two complementary approaches. First, we analyze contextual bandits through the lens of contextual decision making with structured observations, designing an exploration-by-optimization algorithm whose sample complexity is governed by the decision-estimation coefficient (DEC; Foster et al., 2021, 2022). We show that, with s-sparse rewards, the induced model class admits a sharp DEC bound that scales with s and directly yields the optimal rate. Since this approach is largely information-theoretic and involves solving complex min-max optimization problems, we also develop a second, more specialized algorithmic method based on a low-variance exploration technique. This approach leads to concrete, tractable algorithms and naturally extends to contextual combinatorial semi-bandits, leading to improved sample complexity guarantees for bandit multiclass list classification.

COLT 2026

Leveraging Similarities in Multi-Armed Bandits

Khaled Eldowa, Thibaud Rahier, Augustin Cablant, Panayotis Mertikopoulos, Pierre Gaillard

In many online learning and bandit problems, the actions we consider possess inherent similarities–for instance because they share latent traits, tags, or hierarchical structure. We study online learning with a similarity-structured action set, encoded by a rooted tree whose leaves are the actions and whose levels quantify how closely two actions are related. The loss sequence is assumed tree-compatible: losses of similar actions are constrained to be close. We establish an impossibility result showing that usual one-point bandit feedback cannot, in general, leverage range or tree-induced similarity, even under very strong similarity constraints. We then provide a unified set of algorithms which adapt to a wide range of richer feedback models, from semi-bandit feedback down to multi-point bandit protocols, including the minimal two-point feedback setting. We show these algorithms exhibit best-of-both-worlds guarantees and provably exploit action similarities by replacing the number of actions K by a similarity-aware effective number of actions K_eff in the regret bounds. As an application, we show that under two-point feedback, it is possible to achieve √(T) regret in Lipschitz bandits when d ≤ 2.

COLT 2026

Theoretical Compression Bounds for Wide Multilayer Perceptrons

Houssam El Cheairi, David Gamarnik, Rahul Mazumder

Pruning and quantization techniques have been broadly successful in reducing the number of parameters needed for large neural networks, yet theoretical justification for their empirical success falls short. We consider a randomized greedy compression algorithm for pruning and quantization post-training and use it to rigorously show the existence of pruned/quantized subnetworks of multilayer perceptrons (MLPs) with competitive performance. We further extend our results to structured pruning of MLPs and convolutional neural networks (CNNs), thus providing a unified analysis of pruning in wide networks. Our results are free of data assumptions, and showcase a tradeoff between compressibility and network width. The algorithm we consider bears some similarities with Optimal Brain Damage (OBD) and can be viewed as a post-training randomized version of it. The theoretical results we derive bridge the gap between theory and application for pruning/quantization, and provide a justification for the empirical success of compression in wide multilayer perceptrons.

COLT 2026

The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network

Abhigyan Dutta, Itay Safran, Paul Valiant

We study the approximation of the median of d inputs using ReLU neural networks. We present depth-width tradeoffs under several settings, culminating in a constant-depth, linear-width construction that achieves exponentially small approximation error with respect to the uniform distribution over the unit hypercube. By further establishing a general reduction from the maximum to the median, our results break a barrier suggested by prior work on the maximum function, which indicated that linear width should require depth growing at least as loglog d to achieve comparable accuracy. Our construction relies on a multi-stage procedure that iteratively eliminates non-central elements while preserving a candidate set around the median. We overcome obstacles that do not arise for the maximum to yield approximation results that are strictly stronger than those previously known for the maximum itself.

COLT 2026

Relatively Smart: A New Approach for Instance-Optimal Learning

Shaddin Dughmi, Alireza F. Pour

We revisit the framework of Smart PAC learning, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the marginal distribution on unlabeled data. Prior work has shown that such marginal-by-marginal guarantees are possible for “most” marginals, with respect to an arbitrary fixed and known measure, but not more generally. We discover that this failure can be attributed to an “indistinguishability” phenomenon: There are marginals which cannot be statistically distinguished from other marginals that require different learning approaches. In such settings, semi-supervised learning cannot certify its guarantees from unlabeled data, rendering them arguably non-actionable. We propose relatively smart learning, a new framework which demands that a supervised learner compete only with the best “certifiable” semi-supervised guarantee. We show that such modest relaxation suffices to bypass the impossibility results from prior work. In the distribution-free setting, we show that the One-Inclusion Graph learner is relatively smart up to squaring the sample complexity, and show that no supervised learning algorithm can do better. For distribution-family settings, we show that relatively smart learning can be impossible or can require idiosyncratic learning approaches, and its difficulty can be non-monotone in the inclusion order on distribution families.

COLT 2026

Online Realizable Regression and Applications for ReLU Networks

Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

Realizable online regression can behave very differently from online classification. Even without any margin or stochastic assumptions, realizability may enforce horizon-free (finite) cumulative loss under metric-like losses, even when the analogous classification problem has an infinite mistake bound. We study realizable online regression in the adversarial model under losses that satisfy an approximate triangle inequality (approximate pseudo-metrics). Recent work of Attias et al., 2023 shows that the minimax realizable cumulative loss is characterized by the scaled Littlestone/online dimension 𝔻_onl, but this quantity can be difficult to analyze. Our main contribution is a generic potential method that upper bounds 𝔻_onl by a concrete Dudley-type entropy integral that depends only on covering numbers of the hypothesis class under the induced sup pseudo-metric. For an hypothesis class ℋ, we define an entropy potential Φ(ℋ)=∫_0^diam(ℋ)log N(ℋ,ε) dε, where N(ℋ,ε) is the ε-covering number of ℋ under the sup pseudo metric sup_x ℓ(f(x),g(x)), and show that for every c-approximate pseudo-metric loss it holds that 𝔻_onl(ℋ)≤ O(c ·Φ(ℋ)). In particular, polynomial metric entropy implies Φ(ℋ)<∞ and hence a horizon-free realizable cumulative-loss bound with transparent dependence on effective dimension. We illustrate the method on two families. For the class ℋ_L of all L-Lipschitz functions on [-1,1]^d under the loss ℓ_q(y,y’)=|y-y’|^q, we establish a sharp phase transition: if q>d then 𝔻_onl(ℋ_L)=Θ_d,q(L^d), and the bound is achievable efficiently, whereas if q≤ d then 𝔻_onl(ℋ_L)=∞. Complementing these metric-specific results, for any continuous loss with ℓ(y,y)=0, the loss along realizable sequences in ℋ_L satisfies ℓ(ŷ_t,y_t)→ 0 as t→∞. As a second application, we study bounded-norm k-ReLU networks over [-1,1]^d with squared loss and highlight a regression–classification separation: realizable online classification is impossible already for k=2,d=1 under 0/1 loss, yet realizable regression admits finite total loss, including a O(k^2) cumulative-loss upper bound, a matching lower bound up to polylogarithmic factors, and an efficient O(1) guarantee for a single ReLU (k=1) independent of the input dimension d. Assuming Gap-ETH, we also rule out efficient proper online learners that achieve realizable accumulated loss o(d) for any constant k≥ 2.

COLT 2026

Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees

Daniil Dmitriev, Zhihan Huang, Yuting Wei

Diffusion models over discrete spaces have recently shown striking empirical success, yet their theoretical foundations remain incomplete. In this paper, we study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation, with a focus on τ-leaping-based samplers. We establish sharp convergence guarantees for attaining ε accuracy in Kullback-Leibler (KL) divergence for both uniform and masking noising processes. For uniform discrete diffusion, we show that τ-leaping achieves an iteration complexity of order Õ(d/ε), with d the ambient dimension of the target distribution, eliminating linear dependence on the vocabulary size S and improving existing bounds by a factor of d; moreover, we establish a matching algorithmic lower bound showing that linear dependence on the ambient dimension is unavoidable in general. For masking discrete diffusion, we introduce a modified τ-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity, termed the effective total correlation, which is bounded by d log S but can be sublinear or even constant for structured data. As a consequence, the sampler provably adapts to low-dimensional structure without prior knowledge or algorithmic modification, yielding sublinear convergence rates for various practical examples (such as hidden Markov models, image data, and random graphs). Our analysis requires no boundedness or smoothness assumptions on the score estimator beyond control of the score entropy loss.

COLT 2026

Rate-optimal community detection near the KS threshold via node-robust algorithms

Jingqiu Ding, Yiding Hua, Kasper Lindberg, David Steurer, Aleksandr Storozhenko

We study community detection in the symmetric k-stochastic block model, where n nodes are evenly partitioned into k clusters with intra- and inter-cluster connection probabilities p and q, respectively. Our main result is a polynomial-time algorithm that achieves the optimal misclassification rate exp(-(1 ± o(1)) C/k), where C = (√(pn) - √(qn))^2, whenever C ≥ K k^2 log k for some universal constant K, matching the Kesten–Stigum (KS) threshold up to a log k factor. Notably, this rate holds even when an adversary corrupts an η≤exp(-(1 ± o(1)) C/k) fraction of the nodes. To the best of our knowledge, this optimal error rate was previously only attainable either via computationally inefficient procedures (Zhang and Zhou, 2015) or via polynomial-time algorithms that require strictly stronger assumptions such as C ≥ K k^3 (Gao et al., 2017). In the node-robust setting, the best known algorithm requires the substantially stronger condition C ≥ K k^102 (Liu and Moitra, 2022). Our results close this gap by providing the first polynomial-time algorithm that achieves the optimal error rate near the KS threshold in both settings. Our work has two key technical contributions: (1) we robustify majority voting via the Sum-of-Squares framework, (2) we develop a novel graph bisectioning algorithm via robust majority voting, which allows us to significantly improve the misclassification rate to 1/poly(k) for the initial estimation near the KS threshold.

COLT 2026

Minimax optimal differentially private synthetic data for smooth queries

Rundong Ding, Yiyun He, Yizhe Zhu

Differentially private synthetic data enables the sharing and analysis of sensitive datasets while providing rigorous privacy guarantees for individual contributors. A central challenge is to achieve strong utility guarantees for meaningful downstream analysis. Many existing methods ensure uniform accuracy over broad query classes, such as all Lipschitz functions, but this level of generality often leads to suboptimal rates for statistics of practical interest. Since many common data analysis queries exhibit smoothness beyond what worst-case Lipschitz bounds capture, we ask whether exploiting this additional structure can yield improved utility. We study the problem of generating (ε,δ)-differentially private synthetic data from a dataset of size n supported on the hypercube [-1,1]^d, with utility guarantees uniformly for all smooth queries having bounded derivatives up to order k. We propose a polynomial-time algorithm that achieves a minimax error rate of O_k,d(n^-min1, k/d), up to a log(n) factor. This characterization uncovers a phase transition at k=d. Our results generalize the Chebyshev moment matching framework of (Musco et al., 2025; Wang et al., 2016) and strictly improve the error rates for k-smooth queries established in (Wang et al., 2016). Moreover, we establish the first minimax lower bound for the utility of (ε,δ)-differentially private synthetic data with respect to k-smooth queries, extending the Wasserstein lower bound for ε-differential privacy in (Boedihardjo et al., 2024).

COLT 2026

Online Convex Optimization with Sublinear Noisy Probes

Simone Di Gregorio, Anupam Gupta, Stefano Leonardi, Matteo Russo

We study Online Convex Optimization (OCO) over a convex set K⊆ℝ^d, where in each round t the learner selects x_t∈ K and then observes a convex loss f_t:K→[0,1], with the goal of minimizing regret to the best fixed decision in hindsight. We introduce a unified probing model that generalizes two recent lines of work: sublinear best-expert queries in the experts setting, and pairwise (comparison-based) feedback available every round in OCO. In our framework, the learner has a budget of k≤ T pairwise probes; on a probed round it may query two points and learn which one has smaller loss. Our main result shows that even a sublinear and noisy probe budget can provably improve worst-case regret in the full feedback OCO regime. With k δ-noisy pairwise probes, we obtain: _T ≤ O(min{√(dTln T),; dTln T/k|1-2δ|}), which is tight (up to logarithmic factors in T) across T, k and δ. Specifically regarding the noise parameter δ∈ [0,1], the regret guarantee smoothly degrades as the oracle response approaches a coin flip, i.e., δ is close to 1/2. When applying the same techniques to a finite K for the prediction with d experts setting, the resulting rates are instead completely tight in all parameters, including d. Our analysis gives a streamlined treatment of pairwise probing in OCO by quantifying the benefit of probing via a variance reduction effect, combined with a second-order (variance-based) analysis of Continuous Exponential Weights.

COLT 2026

A Quasi-Polynomial Time Mean Estimator Under Mean-Shift Contamination with Unknown Covariance

Ilias Diakonikolas, Jingyi Gao, Giannis Iakovidis, Daniel M. Kane, Sihan Liu, Thanasis Pittas

We study the algorithmic problem of robust Gaussian mean estimation in the mean-shift contamination model with unknown covariance. Specifically, we are allowed to draw samples from a statistical mixture of an unknown target Gaussian 𝒩(μ, Σ) (with weight at least 1-α), and arbitrary unknown mean-shifts of it, i.e., 𝒩(μ_i, Σ)_i, and the goal is to estimate μ up to any desired accuracy ϵ in ℓ_2-norm. In the special case where Σ is known to be the identity, prior work gave an algorithm with a near-optimal sample complexity of poly(d,2^ϵ^-2) and sample-polynomial time. In this work, we provide a quasi-polynomial time algorithm with sample complexity 2^poly(log d/ϵ) in the more general unknown covariance case, markedly improving upon the only previously known estimator for this setting that incurs exponential runtime.

COLT 2026

Linear Regression under Missing or Corrupted Coordinates

Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Jasper C.H. Lee, Thanasis Pittas

We study multivariate linear regression under Gaussian covariates in two settings where data may be erased or corrupted by an adversary subject to a coordinate-wise budget. In the incomplete data setting, an adversary may inspect the dataset and delete entries in up to an η-fraction of samples per coordinate, yielding a strong form of the Missing Not At Random model. In the corrupted data setting, the adversary instead replaces values arbitrarily, and the corruption locations are unknown to the learner. Despite substantial work on missing data, linear regression under such adversarial missingness remains poorly understood, even from an information-theoretic perspective. Unlike the clean setting, where the estimation error vanishes as the number of samples grows, the optimal error in these models remains bounded away from zero and depends on the problem parameters. Our main contribution is a characterization of this error, up to constant factors, over essentially the entire parameter range. Specifically, we establish novel information-theoretic lower bounds on the achievable error and show that they match the guarantees of computationally efficient algorithms. A key implication of our results is that the optimal error in the missing data setting matches that in the corruption setting, indicating that knowledge of the corruption locations provides no general advantage.

COLT 2026

High-Dimensional Gaussian Mean Estimation under Realizable Contamination

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

We study mean estimation for a Gaussian distribution with identity covariance in ℝ^d under a missing data scheme termed realizable ϵ-contamination. In this model, an adversary chooses a function r(x) taking values in [0,ϵ], and each sample x is removed independently with probability r(x). Recent work introduced this model as an intermediate-strength setting between Missing Completely At Random (MCAR), where missingness is independent of the data, and Missing Not At Random (MNAR), where missingness may depend arbitrarily on the sample values and can lead to non-identifiability. Prior work established information-theoretic upper and lower bounds for mean estimation in the realizable contamination model, but the proposed estimators require runtime exponential in the dimension, leaving open the possibility of computationally efficient algorithms in high dimensions. In this work, we establish an information–computation gap in the Statistical Query model and, as a consequence, for low-degree polynomial and polynomial-threshold-function algorithms. Specifically, we show that any such algorithm must either use substantially more samples than information-theoretically necessary or incur exponential runtime. We complement our lower bound with an algorithm whose sample–time tradeoff nearly matches our lower bound. Together, these results provide a qualitative characterization of the computational complexity of Gaussian mean estimation under realizable ϵ-contamination.

COLT 2026

Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size

Michał Dereziński, Xiaoyu Dong

We study last-iterate convergence of SGD with greedy step size over smooth quadratics in the interpolation regime, a setting which captures the classical Randomized Kaczmarz algorithm as well as other popular iterative linear system solvers. For these methods, we show that the t-th iterate attains an O(1/t^3/4) convergence rate, addressing a question posed by Attia, Schliserman, Sherman, and Koren, who gave an O(1/t^1/2) guarantee for this setting. In the proof, we introduce the family of stochastic contraction processes, whose behavior can be described by the evolution of a certain deterministic eigenvalue equation, which we analyze via a careful discrete-to-continuous reduction.

Keep browsing

More papers from top AI conferences

30+ top conferences, by conference, year, and topic.