ALT 2026 Papers

We conduct a comprehensive analysis of the discrete-time exponential-weights dynamic with a constant step size on all general-sum and symmetric 2 × 2 normal-form games, i.e. games with 2 pure strategies per player, and where the ensuing payoff tuple is of the form (A,A^⊤) (where A is the 2 × 2 payoff matrix corresponding to the first player). Such symmetric games commonly arise in real-world interactions between “symmetric" agents who have identically defined utility functions — such as Bertrand competition and multi-agent performative prediction, and display a rich multiplicity of equilibria despite the seemingly simple setting. Somewhat surprisingly, we show through a first-principles analysis that the exponential weights dynamic, which is popular in online learning, converges in the last iterate for such games regardless of initialization with an appropriately chosen step size. For certain games and/or initializations, we further show that the convergence rate is in fact exponential and holds for any step size. We illustrate our theory with extensive simulations and applications to the aforementioned game-theoretic interactions. In the case of multi-agent performative prediction, we formulate a new “mortgage competition" game between lenders (i.e. banks) who interact with a population of customers, and show that it fits into our framework.

In lifelong learning, a learner faces a sequence of tasks with shared structure and aims to identify and leverage it to accelerate learning. We study the setting where such structure is captured by a common representation of data. Unlike multi-task learning or learning-to-learn, where tasks are available upfront to learn the representation, lifelong learning requires the learner to make use of its existing knowledge while continually gathering partial information in an *online* fashion. In this paper, we consider a generalized framework of lifelong representation learning. We propose a simple algorithm that uses multi-task empirical risk minimization as a subroutine and establish a sample complexity bound based on a new notion we introduce—the *task-eluder dimension*. Our result applies to a wide range of learning problems involving general function classes. As concrete examples, we instantiate our result on classification and regression tasks under noise.

The goal of *graph inference* is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruction, verification, and property testing are all special cases of graph inference. In this work, we study graph inference using an oracle that returns the *effective resistance* (ER) distance between a given pair of vertices. Effective resistance is a natural notion of distance that arises from viewing graphs as electrical circuits, and has many applications. However, it has received little attention from a graph inference perspective. Indeed, although it is known that any n-vertex graph can be uniquely reconstructed by making all n2 = Θ(n^2) possible ER queries, very little else is known. We address this and show a number of fundamental results in this model, including: 1. O(n)-query algorithms for testing whether a graph is a tree; deciding whether two graphs are equal assuming one is a subgraph of the other; and testing whether a given vertex (or edge) is a cut vertex (or cut edge). 2. Property testing algorithms, including for testing whether a graph is vertex-biconnected and whether it is edge-biconnected. We also give a reduction that shows how to adapt property testing results from the well-studied bounded-degree model to our model with ER queries. This yields ER-query-based algorithms for testing k-connectivity, bipartiteness, planarity, and containment of a fixed subgraph. 3. Graph reconstruction algorithms. We highlight two k-query (provably minimal) algorithms for recovering an entire graph with k missing edge weights: an exact algorithm with an exponential running time for unweighted graphs, and an approximate numerical algorithm with polynomial running time for weighted graphs. We also give a simple, O(k^2)-query, polynomial-time algorithm for this problem. Additionally, we give an algorithm for reconstructing a graph from a low-width tree decomposition. We additionally compare the relative power of ER queries and shortest path queries, which are closely related and better studied. Interestingly, we show that the two query models are incomparable in power.

In recent years, self-supervised representation learning (SSL) has become an important learning paradigm and a crucial component of foundation models. SSL-based training pipelines are typically formalized as a sequence of two tasks—a pretext task that learns representations from large amounts of augmented unlabeled data, and a downstream task, where a simple model is fit on the learned representations with the help of little labeled data. The strong empirical performance of SSL-based pipelines for prominent joint embedding loss functions is not yet well explained in theory due to two main reasons: a lack of non-vacuous generalization bounds for the models learned in the pretext task, and a lack of practically computable transfer bounds that describe how generalization bounds derived for the pretext task transfer to the downstream task. In this work, we first derive non-vacuous PAC Bayesian generalization bounds for models optimized in the pretext task with prominent joint embedding SSL loss functions (VICReg, Barlow Twins, and Spectral Contrastive loss), accounting for their non-i.i.d. nature. Next, we provide the first practically computable transfer bounds for our considered loss functions by formally proving a surrogate relation that upper bounds the downstream squared L2 loss by the SSL pretext loss and a more accurate measure for the influence of the chosen augmentations than in previous work. In addition, our theoretical analysis identifies effective hyperparameter choices, thereby reducing the need for extensive hyperparameter tuning and offering principled guidance for model selection. We empirically validate our theoretical findings on CIFAR-10 and MNIST datasets.

Hu and M ehta [2024] posed an open problem: what is the optimal instance-dependent rate for the stochastic decision-theoretic online learning (with K actions and T rounds) under ε-differential privacy? Before, the best known upper bound and lower bound are O(log K/Δ_min + log Klog T/ε) and Ω(log K/Δ_min + log K/ε) (where Δ_min is the gap between the optimal and the second actions). In this paper, we partially address this open problem by having two new results. First, we provide an improved upper bound for this problem O(log K/Δ_min + log^2K/ε), which is T-independent and only has a log dependency in K. Second, to further understand the gap, we introduce the deterministic setting, a weaker setting of this open problem, where the received loss vector is deterministic. At this weaker setting, a direct application of the analysis and algorithms from the original setting still leads to an extra log factor. We conduct a novel analysis which proves upper and lower bounds that match at Θ(log K/ε).

We study the problem of learning a low-degree spherical polynomial of degree ℓ_0 = Θ(1) ≥ 1 defined on the unit sphere in ℝ^d by training an over-parameterized two-layer neural network (NN) with channel attention in this paper. Our main result is the significantly improved sample complexity for learning such low-degree polynomials. We show that, for any regression risk ϵ∈ (0,1), a carefully designed two-layer NN with channel attention and finite width trained by the vanilla gradient descent (GD) requires the lowest sample complexity of n ≍Θ(d^ℓ_0/ϵ) with high probability, in contrast with the representative sample complexity Θ(d^ℓ_0maxϵ^-2,log d), where n is the training data size. Moreover, such sample complexity is not improvable since the trained network renders a sharp rate of the nonparametric regression risk of the order Θ(d^ℓ_0/n) with high probability. On the other hand, the minimax optimal rate for the regression risk with a kernel of rank Θ(d^ℓ_0) is Θ(d^ℓ_0/n), so that the rate of the nonparametric regression risk of the network trained by GD is minimax optimal. The training of the two-layer NN with channel attention is a two-stage process. In stage one, a novel and provable learnable channel selection algorithm, as a learnable harmonic-degree selection process, is employed to select the ground truth channel number in the target function, ℓ_0, among the initial L ≥ℓ_0 channels in its activation function in the first layer with high probability. Such learnable channel selection is performed by efficient one-step GD on both layers of the NN, which achieves the goal of feature learning in learning low-degree polynomials. In stage two, the second layer of the network is trained by standard GD using the activation function with selected channels. To the best of our knowledge, this is the first time a minimax optimal risk bound is obtained by training an over-parameterized but finite-width neural network with feature learning capability to learn low-degree spherical polynomials.

We introduce the Smoothed Online Optimization for Target Tracking (SOOTT) problem, a new framework that integrates three key objectives in online decision-making under uncertainty: (1) tracking cost for following a dynamically moving target, (2) adversarial perturbation cost for withstanding unpredictable disturbances, and (3) switching cost for penalizing abrupt changes in decisions. This formulation captures real-world scenarios, such as elastic and inelastic workload scheduling in AI clusters, where operators must balance long-term service-level agreements for elastic workloads, like LLM training, against sudden demand spikes for inelastic workloads, like real-time inference. We first present BEST, a robust algorithm with provable competitive guarantees for SOOTT. To enhance practical performance, we introduce CoRT, a learning-augmented variant that incorporates untrusted black-box predictions (e.g., from ML models) into its decision process. Our theoretical analysis shows that CoRT strictly improves over BEST when predictions are accurate, while maintaining robustness under arbitrary prediction errors. We validate our approach through a case study on workload scheduling, demonstrating that both algorithms effectively balance trajectory tracking, decision smoothness, and resilience to external disturbances.

Stochastic gradient descent (SGD) is the main algorithm behind a large body of work in machine learning. In many cases, constraints are enforced via projections, leading to projected stochastic gradient algorithms. In recent years, a large body of work has examined the convergence properties of projected SGD for non-convex losses in asymptotic and non-asymptotic settings. Strong quantitative guarantees are available for convergence measured via Moreau envelopes. However, these results cannot be compared directly with work on unconstrained SGD, since the Moreau envelope construction changes the gradient. Other common measures based on gradient mappings have the limitation that convergence can only be guaranteed if variance reduction methods, such as mini-batching, are employed. This paper presents an analysis of projected SGD for non-convex losses over compact convex sets. Convergence is measured via the distance of the gradient to the Goldstein subdifferential generated by the constraints. Our proposed convergence criterion directly reduces to commonly used criteria in the unconstrained case, and we obtain convergence without requiring variance reduction. We obtain results for data that are independent, identically distributed (IID) or satisfy mixing conditions (L-mixing). In these cases, we derive asymptotic convergence and O(N^-1/3) non-asymptotic bounds in expectation, where N is the number of steps. In the case of IID sub-Gaussian data, we obtain almost-sure asymptotic convergence and high-probability Õ(N^-1/5) non-asymptotic bounds. In particular, these are the first non-asymptotic high-probability bounds for projected SGD with non-convex losses.