ALT 2026 Papers

High-probability guarantees in stochastic optimization are often obtained only under strong noise assumptions such as sub-Gaussian tails. We show that such guarantees can also be achieved under the weaker assumption of bounded variance by developing a stochastic proximal point method. This method combines a proximal subproblem solver, which inherently reduces variance, with a probability booster that amplifies per-iteration reliability into high-confidence results. The analysis demonstrates convergence with low sample complexity, without restrictive noise assumptions or reliance on mini-batching.

In Online Convex Optimization (OCO), when the stochastic gradient has a finite variance, many algorithms provably work and guarantee a sublinear regret. However, limited results are known if the gradient estimate has a heavy tail, i.e., the stochastic gradient only admits a finite 𝗉-th central moment for some 𝗉∈(1,2]. Motivated by it, this work examines different old algorithms for OCO (e.g., Online Gradient Descent) in the more challenging heavy-tailed setting. Under the standard bounded domain assumption, we establish new regrets for these classical methods without any algorithmic modification. Remarkably, these regret bounds are fully optimal in all parameters (can be achieved even without knowing 𝗉), suggesting that OCO with heavy tails can be solved effectively without any extra operation (e.g., gradient clipping). Our new results have several applications. A particularly interesting one is the first provable and optimal convergence result for nonsmooth nonconvex optimization under heavy-tailed noise without gradient clipping.

We consider infinite-horizon γ-discounted (linear) constrained Markov decision processes (CMDPs) where the objective is to find a policy that maximizes the expected cumulative reward subject to expected cumulative constraints. Given access to a generative model, we propose to solve CMDPs with a primal-dual framework that can leverage any black-box unconstrained MDP solver. For linear CMDPs with feature dimension d, we instantiate the framework by using mirror descent value iteration () <cit.> an example MDP solver. We provide sample complexity bounds for the resulting CMDP algorithm in two cases: (i) relaxed feasibility, where small constraint violations are allowed, and (ii) strict feasibility, where the output policy is required to exactly satisfy the constraint. For (i), we prove that the algorithm can return an ϵ-optimal policy with high probability by using Õ(d^2/(1-γ)^4ϵ^2) samples. For (ii), we show that the algorithm requires Õ(d^2/(1-γ)^6ϵ^2ζ^2) samples, where ζ is the problem-dependent Slater constant that characterizes the size of the feasible region. Furthermore, we prove a lower-bound of Ω(d^2/(1-γ)^5ϵ^2ζ^2) for the strict feasibility setting. We note that our upper bounds under both settings exhibit a near-optimal dependence on d, ϵ, and ζ. Finally, we instantiate our framework for tabular CMDPs and show that it can be used to recover near-optimal sample complexities in this setting.

We study the problem of opportunistic approachability: a generalization of Blackwell approachability where the learner would like to obtain stronger guarantees (i.e., approach a smaller set) when their adversary limits themselves to a subset of their possible action space. <cit.> introduced this problem in 2014 and presented an algorithm that guarantees sublinear approachability rates for opportunistic approachability. However, this algorithm requires the ability to produce calibrated online predictions of the adversary’s actions, a problem whose standard implementations require time exponential in the ambient dimension and result in approachability rates that scale as O(T^-1/d). In this paper, we present an efficient algorithm for opportunistic approachability that achieves a rate of O(T^-1/3) that bypasses the need for an online calibration subroutine. Moreover, in the case where the dimension of the adversary’s action set is at most two, we show it is possible to obtain the optimal rate of O(T^-1/2).

The study of self-normalized processes plays a crucial role in a wide range of applications, from sequential decision-making to econometrics. While the behavior of self-normalized concentration has been widely investigated for scalar-valued processes, vector-valued processes remain comparatively underexplored, especially outside of the sub-Gaussian framework. In this contribution, we provide concentration inequalities for self-normalized processes with light tails beyond sub-Gaussianity, including Bernstein-type, Bennett-type, and empirical Bennett-type inequalities. We illustrate the relevance of our results in the context of online linear regression, with applications in (kernelized) linear bandits.

Traditional reinforcement learning usually assumes either episodic interactions with resets or continuous operation to minimize average or cumulative loss. While episodic settings have many theoretical results, resets are often unrealistic in practice. The infinite-horizon setting avoids this issue but lacks non-asymptotic guarantees in online scenarios with unknown dynamics. In this work, we move towards closing this gap by introducing a reset-free framework called the *periodic* framework, where the goal is to find *periodic policies*: policies that not only minimize cumulative loss but also return the agents to their initial state distribution after a fixed number of steps. We formalize the problem of finding optimal periodic policies and identify sufficient conditions under which it is well-defined for tabular Markov decision processes. To evaluate algorithms in this framework, we introduce the periodic regret, a measure that balances cumulative loss with the terminal law constraint. We then propose the first algorithms for computing periodic policies in two multi-agent settings and show they achieve sublinear periodic regret of order Õ(T^3/4). This provides the first non-asymptotic guarantees for reset-free learning in the setting of M homogeneous agents, for any M > 1.

Designing online algorithms with machine learning predictions is a recent approach that extends beyond the worst-case paradigm for various practically relevant online problems, such as scheduling, caching, and clustering. While most previous learning-augmented algorithms focus on integrating the predictions of a single oracle, we study the design of online algorithms with multiple prediction sources (experts). To go beyond the performance guarantee of the popular static best expert in hindsight benchmark, we introduce a new benchmark that can be viewed as a linear combination of predictions that evolve over time. We present competitive algorithms in the new dynamic benchmark for 0-1 online covering problems with a performance guarantee of O(log K) if the objective is linear and O(ln(K)) ·λ/(1-μln(K)) if the objective is non-linear, where K is the number of experts and (λ, μ) are parameters of the objective function. Our approach gives a new perspective on combining multiple algorithms in an online manner (a central subject in the online algorithm research community) using machine learning techniques.

While Adam is one of the most effective optimizer for training large-scale machine learning models, a theoretical understanding of how to optimally set its momentum factors, β_1 and β_2, remains largely incomplete. Prior works have shown that Adam can be seen as an instance of Follow-the-Regularized-Leader (FTRL), one of the most important class of algorithms in online learning. The prior analyses in these works required setting β_1 = √(β_2), which does not cover the more practical cases with β_1 ≠√(β_2). We derive novel, more general analyses that hold for both β_1 ≥√(β_2) and β_1 ≤√(β_2). In both cases, our results strictly generalize the existing bounds. Furthermore, we show that our bounds are tight in the worst case. We also prove that setting β_1 = √(β_2) is optimal for an oblivious adversary, but sub-optimal for an non-oblivious adversary.

We address the general task of learning with a set of candidate models that is too large to have a uniform convergence of empirical estimates to true losses. While the common approach to such challenges is SRM (or regularization) based learning algorithms, we propose a novel learning paradigm that relies on stronger incorporation of empirical data and requires less algorithmic decisions to be based on prior assumptions. We analyze the generalization capabilities of our approach and demonstrate its merits in several common learning assumptions, including similarity of close points, clustering of the domain into highly label-homogeneous regions, Lipschitzness assumptions of the labeling rule, and contrastive learning assumptions. Our approach allows utilizing such assumptions without the need to know their true parameters a priori.

We introduce the large average subtensor problem: given an order-p tensor over ℝ^N×⋯× N with i.i.d. standard normal entries and a k∈ℕ, algorithmically find a k×⋯× k subtensor with a large average entry. This generalizes the large average submatrix problem, a key model closely related to biclustering and high-dimensional data analysis, to tensors. For the submatrix case, <cit.> explicitly highlight the regime k=Θ(N) as an intriguing open question. Addressing the regime k=Θ(N) for tensors, we establish that the largest average entry concentrates around an explicit value E_max, provided that the tensor order p is sufficiently large. Furthermore, we prove that for any γ>0 and large p, this model exhibits multi Overlap Gap Property (m-OGP) above the threshold γ E_max. The m-OGP is a rigorous barrier for a broad class of algorithms exhibiting input stability. These results hold for both k=Θ(N) and k=o(N). For smaller values of k, we also propose a polynomial-time algorithm that finds a subtensor with an average entry of order Θ_p(1/√(p))E_max. In particular, the m-OGP is asymptotically sharp: onset of the m-OGP and the algorithmic threshold match as p grows. Our results show that while the case k=Θ(N) remains open for submatrices, it can be rigorously analyzed for tensors in the large p regime. This is achieved by interpreting the model as a Boolean spin glass and drawing on insights from recent advances in the Ising p-spin glasses.

A fundamental problem in statistics is estimating the shape matrix of an Elliptical distribution. This generalizes the familiar problem of Gaussian covariance estimation, for which the sample covariance achieves optimal estimation error. For Elliptical distributions, Tyler proposed a natural M-estimator and showed strong statistical properties in the asymptotic regime, independent of the underlying distribution. Numerical experiments show that this estimator performs very well, and that Tyler’s iterative procedure converges quickly to the estimator. Franks and Moitra recently provided the first distribution-free error bounds in the finite sample setting, as well as the first rigorous convergence analysis of Tyler’s iterative procedure. However, their results exceed the sample complexity of the Gaussian setting by a log^2 d factor. We close this gap by proving optimal sample threshold and error bounds for Tyler’s M-estimator for all Elliptical distributions, fully matching the Gaussian result. Moreover, we recover the algorithmic convergence even at this lower sample threshold. Our approach builds on the operator scaling connection of Franks and Moitra by introducing a novel ‘pseudorandom’ condition, which we call ∞-expansion. We show that Elliptical distributions satisfy ∞-expansion at the optimal sample threshold, and then prove a novel scaling result for inputs satisfying this condition.

The contextual dueling bandit problem models adaptive recommender systems, where at each step the algorithm presents a set of items to the user, and the user’s choice reveals their preference. This setup is well suited for implicit choices users make when navigating a content platform, but does not capture other possible comparison queries. Motivated by the fact that users provide more reliable feedback after consuming items, we propose a new bandit model that can be described as follows. The algorithm recommends one item per time step; after consuming that item, the user is asked to compare it with another item chosen from the user’s consumption history. Importantly, in our model, this comparison item can be chosen without incurring any additional regret, potentially leading to better performance. However, the regret analysis is challenging because of the temporal dependency in the user’s history. To overcome this challenge, we first show that the algorithm can construct informative queries provided the history is rich, i.e., satisfies a certain diversity condition. We then show that a short initial random exploration phase is sufficient for the algorithm to accumulate a rich history with high probability. This result, proven via matrix concentration bounds, yields O(√(T)) regret guarantees. Additionally, our simulations show that reusing past items for comparisons can lead to significantly lower regret than only comparing between simultaneously recommended items.

We study the problem of learning vector-valued linear predictors: these are prediction rules parameterized by a matrix that maps an m-dimensional feature vector to a k-dimensional target. We focus on the fundamental case with a convex and Lipschitz loss function, and show several new theoretical results that shed light on the complexity of this problem and its connection to related learning models. First, we give a tight characterization of the sample complexity of Empirical Risk Minimization (ERM) in this setting, establishing that Ω(k/ε^2) examples are necessary for ERM to reach ϵ excess (population) risk; this provides for an exponential improvement over recent results by Magen and Shamir (2024) in terms of the dependence on the target dimension k, and matches a classical upper bound due to Maurer (2016). Second, we present a black-box conversion from general d-dimensional Stochastic Convex Optimization (SCO) to vector-valued linear prediction, showing that any SCO problem can be embedded as a prediction problem with k=Θ(d) outputs. These results portray the setting of vector-valued linear prediction as bridging between two extensively studied yet disparate learning models: linear models (corresponds to k=1) and general d-dimensional SCO (with k=Θ(d)).

To what extent is it possible to visualize high-dimensional data in two- or three-dimensional plots? We reframe this question in terms of embedding n-vertex graphs (representing the neighborhood structure of the input points) into metric spaces of low doubling dimension d in such a way that keeps neighbors close and non-neighbors far. This notion of neighbor preservation can be understood as a weaker embedding constraint than near-isometry, yet it is similarly as demanding in terms of how the minimum required dimension scales with the number of points. We show that for an overwhelming fraction of graphs, d = Θ(log n) is both necessary and sufficient for neighbor preservation. Even sparse regular graphs, which encode a much simpler class of neighborhood structures, typically require d= Ω(log n / loglog n). The landscape changes dramatically when embedding into normed spaces: general graphs become exponentially harder to embed, requiring d=Ω(n), while sparse regular graphs continue to admit d = O(log n). Finally, we study the implications of these results for visualizing data with intrinsic cluster structure. We show that graphs produced from a planted partition model with k clusters on n points typically require d=Ω(log n) even when the cluster structure is salient. These results challenge the aspiration that constant-dimensional visualizations can faithfully preserve neighborhood structure.

In this work, we develop a collection of novel methods for the entropic-regularised optimal transport problem, which are inspired by existing mirror descent interpretations of the Sinkhorn algorithm used for solving this problem. These are fundamentally proposed from an optimisation perspective: either based on the associated semi-dual problem, or based on solving a non-convex constrained problem over subset of joint distributions. This optimisation viewpoint results in non-asymptotic rates of convergence for the proposed methods under minimal assumptions on the problem structure. We also propose a momentum-equipped method with provable accelerated guarantees through this viewpoint, akin to those in the Euclidean setting. The broader framework we develop based on optimisation over the joint distributions also finds an analogue in the dynamical Schrödinger bridge problem.

Transformer-based models demonstrate a remarkable ability for *in-context learning* (ICL), where they can adapt to unseen tasks from a few prompt examples without parameter updates. Notably, recent research has provided insight into how the Transformer architecture can perform ICL, showing that the optimal *linear self-attention* (LSA) mechanism can implement one step of gradient descent for linear least-squares objectives when trained on random linear regression tasks. Building upon this understanding, we investigate ICL for *nonlinear* function classes. We first prove that LSA is inherently incapable of outperforming linear predictors on nonlinear tasks, thereby highlighting a hard expressivity barrier for attention-only models. To overcome this limitation, we analyze a Transformer block consisting of LSA and feed-forward layers inspired by the *gated linear units* (GLU), which is a standard component in modern Transformer architectures. We show that this block achieves nonlinear ICL by implementing one step of gradient descent on a polynomial kernel regression loss. Furthermore, our analysis reveals that the expressivity of a single such block is inherently limited by its dimensions. We then show that a deep Transformer can overcome this bottleneck by distributing the computation of richer kernel functions across multiple blocks, effectively performing block-coordinate descent in a high-dimensional feature space that a single block cannot represent. Our findings highlight that the feed-forward layers provide a crucial and scalable mechanism by which Transformers can express nonlinear representations for ICL.

We consider a generalization of the celebrated Online Convex Optimization (OCO) framework with adversarial online constraints. In this problem, an online learner interacts with an adversary sequentially over multiple rounds. At the beginning of each round, the learner chooses an action from a convex decision set. After that, the adversary reveals a convex cost function and a convex constraint function. The goal of the learner is to minimize the cumulative cost while satisfying the constraints as tightly as possible. We present two efficient algorithms with simple modular structures that give universal dynamic regret and cumulative constraint violation bounds, improving upon state-of-the-art results. While the first algorithm, which achieves the optimal regret bound, involves projection onto the constraint sets, the second algorithm is projection-free and achieves better violation bounds in rapidly varying environments. Our results hold in the most general case when both the cost and constraint functions are chosen arbitrarily, and the constraint functions need not contain any common feasible point. We establish these results by introducing a general framework that reduces the constrained learning problem to an instance of the standard OCO problem with specially constructed surrogate cost functions.

Ranking items is a central task in many information retrieval and recommender systems. User input for the ranking task often comes in the form of ratings on a coarse discrete scale. We ask whether it is possible to recover a fine-grained item ranking from such coarse-grained ratings. We model items as having scores and users as having thresholds; a user likes an item if the score exceeds the threshold, and dislikes it otherwise. Although all users implicitly agree on the total item order, estimating that order is challenging when both the scores and the thresholds are latent. Under our model, any ranking method naturally partitions the n items into bins; the bins are ordered, but the items inside each bin are still unordered. Users arrive sequentially, and every new user can be queried to refine the current ranking. We prove that achieving a near-perfect ranking, measured by Spearman distance, requires Θ(n^2) users (and therefore Ω(n^2) queries). This is significantly worse than the O(nlog n) queries needed to rank either from comparisons or from ratings with known user thresholds; the gap reflects the additional queries needed to estimate each user’s latent threshold. Our bound also quantifies the impact of a mismatch between the score and threshold distributions via a quadratic divergence factor. To show the tightness of our results, we provide a ranking algorithm whose query complexity matches our bound up to a logarithmic factor. Our work reveals a tension in online ranking: diversity in thresholds is necessary to merge coarse ratings from many users into a fine-grained ranking, but this diversity has a cost if the thresholds are a priori unknown.

Conformal predictors provide set or functional predictions that are valid under the assumption of randomness, i.e., under the assumption of independent and identically distributed data. The question asked in this paper is whether there are predictors that are valid in the same sense under the assumption of randomness and that are more efficient than conformal predictors. The answer is that the class of conformal predictors is universal in that only limited gains in predictive efficiency are possible. The previous work in this area has relied on the algorithmic theory of randomness and so involved unspecified constants, whereas this paper’s results are much more practical. They are also shown to be optimal in some respects.