COLT 2025 论文列表

Consider a d-uniform random hypergraph on n vertices in which hyperedges are included iid so that the average degree is n^δ. The projection of a hypergraph is a graph on the same n vertices where an edge connects two vertices if and only if they belong to some hyperedge. The goal is to reconstruct the hypergraph given its projection. An earlier work of Bresler, Guo, and Polyanskiy (COLT 2024) showed that exact recovery for d=3 is possible if and only if δ < 2/5. This work completely resolves the question for all values of d for both exact and partial recovery and for both cases of whether multiplicity information about each edge is available or not. In addition, we show that the reconstruction fidelity undergoes an all-or-nothing transition at a threshold. In particular, this resolves all conjectures from Bresler, Guo, and Polyanskiy (COLT 2024).

In average reward Markov decision processes, state-of-the-art algorithms for regret minimization follow a well-established framework: They are model-based, optimistic and episodic. First, they maintain a confidence region from which optimistic policies are computed using a well-known subroutine called Extended Value Iteration (EVI). Second, these policies are used over time windows called episodes, each ended by the Doubling Trick (DT) rule or a variant thereof. In this work, without modifying EVI, we show that there is a significant advantage in replacing the doubling trick by another simple rule, that we call the Vanishing Multiplicative rule (VM). When managing episodes with VM, the algorithm’s regret is, both in theory and in practice, as good if not better than with DT while the one-shot behavior is greatly improved. More specifically, the management of bad episodes (when sub-optimal policies are being used) is much better under VM than DT by making the regret of exploration logarithmic rather than linear. These results are made possible by a new in-depth understanding of the contrasting behaviors of confidence regions during good and bad episodes.

Surprisingly, recent work has shown that gradient descent can be accelerated without using momentum—just by judiciously choosing stepsizes. An open question raised by several papers is whether this phenomenon of stepsize-based acceleration holds more generally for constrained and/or composite convex optimization via projected and/or proximal versions of gradient descent. We answer this in the affirmative by proving that the silver stepsize schedule yields analogously accelerated rates in these settings. These rates are conjectured to be asymptotically optimal among all stepsize schedules, and match the silver convergence rate of vanilla gradient descent (Altschuler and Parrilo, 2024, 2025), namely O(ε^-log_ρ 2) for smooth convex optimization and O(κ^log_ρ 2log 1/ε) under strong convexity, where ε is the precision, κ is the condition number, and ρ = 1 + √(2) is the silver ratio. The key technical insight is the combination of recursive gluing—the technique underlying all analyses of gradient descent accelerated with time-varying stepsizes—with a certain Laplacian-structured sum-of-squares certificate for the analysis of proximal point updates.

We consider a model for explainable AI in which an explanation for a prediction h(x)=y consists of a subset S’ of the training data (if it exists) such that all classifiers h’ ∈ that make at most b mistakes on S’ predict h’(x)=y. Such a set S’ serves as a proof that x indeed has label y under the assumption that (1) the true target function h^⋆ belongs to , and (2) the set S contains at most b noisy or corrupted points. For example, if b=0 and is the family of linear classifiers in ℝ^d, and if x lies inside the convex hull of the positive data points in S (and therefore every consistent linear classifier labels x as positive), then Carathéodory’s theorem states that x in fact lies inside the convex hull of d+1 of those points. So, a set S’ of size d+1 could be released as an explanation for a positive prediction, and would serve as a short proof of correctness of the prediction under the assumption of perfect realizability. In this work, we consider this problem more generally, for general hypothesis classes and general values b≥ 0. We define the notion of the robust hollow star number of (which generalizes the standard hollow star number), and show that it precisely characterizes the worst-case size of the smallest certificate achievable, and analyze its size for natural classes. We also consider worst-case distributional bounds on certificate size, as well as distribution-dependent bounds that we show tightly control the sample size needed to get a certificate for any given test example. In particular, we define a notion of the certificate coefficient _x of an example x with respect to a data distribution and target function h^⋆, and prove matching upper and lower bounds on sample size as a function of _x, b, and the VC dimension d of .

Two seminal papers–Alon, Livni, Malliaris, Moran (STOC 2019) and Bun, Livni, and Moran (FOCS 2020)–established the equivalence between online learnability and globally stable PAC learnability in binary classification. However, Chase, Chornomaz, Moran, and Yehudayoff (STOC 2024) recently showed that this equivalence does not hold in the agnostic setting. Specifically, they proved that in the agnostic setting, only finite hypothesis classes are globally stable learnable. Therefore, agnostic global stability is too restrictive to capture interesting hypothesis classes. To address this limitation, Chase et al. introduced two relaxations of agnostic global stability. In this paper, we characterize the classes that are learnable under their proposed relaxed conditions, resolving the two open problems raised in their work. First, we prove that in the setting where the stability parameter can depend on the excess error (the gap between the learner’s error and the best achievable error by the hypothesis class), agnostic stability is fully characterized by the Littlestone dimension. Consequently, as in the realizable case, this form of learnability is equivalent to online learnability. As part of the proof of this theorem, we strengthen the celebrated result of Bun et al. by showing that classes with infinite Littlestone dimension are not stably PAC learnable, even if we allow the stability parameter to depend on the excess error. For the second relaxation proposed by Chase et al., we prove that only finite hypothesis classes are globally stable learnable even if we restrict the agnostic setting to distributions with small population loss.

The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the design of efficient algorithms but also limit their reach and relevance. Towards addressing this, we prove a distributional-lifting theorem: This upgrades a learner that succeeds with respect to a limited distribution family 𝒟 to one that succeeds with respect to any distribution D^⋆, with an efficiency overhead that scales with the complexity of expressing D^⋆ as a mixture of distributions in 𝒟. Recent work of Blanc, Lange, Malik, and Tan considered the special case of lifting uniform-distribution learners and designed a lifter that uses a conditional sample oracle for D^⋆, a strong form of access not afforded by the standard PAC model. Their approach, which draws on ideas from semi-supervised learning, first learns D^⋆ and then uses this information to lift. We show that their approach is information-theoretically intractable with access only to random examples, thereby giving formal justification for their use of the conditional sample oracle. We then take a different approach that sidesteps the need to learn D^⋆, yielding a lifter that works in the standard PAC model and enjoys additional advantages: it works for all base distribution families, preserves the noise tolerance of learners, has better sample complexity, and is simpler.

We consider the basic problem of learning an unknown partition of n elements into at most k sets using simple queries that reveal information about a small subset of elements. Our starting point is the popular and well-studied pairwise same-set queries which ask if a pair of elements belong to the same class. It is well-known that non-adaptive (fully parallel) algorithms require Θ(n^2) queries, while adaptive (fully sequential) algorithms require Θ(nk) queries, and the best known algorithm uses k-1 rounds of adaptivity. Many variations of this problem have been studied over the last two decades in multiple disciplines due to its fundamental nature and connections to clustering, active learning, and crowd-sourcing. In many of these applications, it is of paramount interest to reduce adaptivity, a.k.a the number of rounds, while minimizing the query complexity. In this paper, we give a complete characterization of the deterministic query complexity of this problem as a function of the number of rounds, r, which interpolates smoothly between the non-adaptive and adaptive settings: for any constant r ≥ 1, the query complexity is Θ(n^1+1/2^r-1k^1-1/2^r-1). Additionally, our algorithm only needs O(loglog n) rounds to attain the optimal O(nk) query complexity, which is a double-exponential improvement over prior works when k is a polynomial in n. Next, we consider two natural generalizations of pair-wise queries to general subsets S of size at most s: (1) weak subset queries which return the number of classes intersected by S, and (2) strong subset queries which return the entire partition restricted on S. Once again in crowd sourcing applications, queries on large sets may be prohibitive. For non-adaptive algorithms, we show Ω(n^2/s^2) strong queries are needed. In contrast, perhaps surprisingly, we show that there is a non-adaptive randomized algorithm using weak queries that matches this bound up to log-factors for all s ≤√(n). More generally, we obtain nearly matching upper and lower bounds for algorithms using weak and strong queries in terms of both the number of rounds, r, and the query size bound, s.

The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components, which is one of the most basic and fundamental graph parameters. Formally, we consider the problem of reconstructing an n-node m-edge graph with oracle queries of the following form: provided with a subset of vertices, the oracle returns the number of connected components in the induced subgraph. We show Θ(m log n/log m) queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that Ω(n^2) non-adaptive queries are required, even when m = O(n). We also provide an O(mlog n + nlog^2 n) query algorithm using only two rounds of adaptivity.

SHAP is one of the most popular local feature-attribution methods. Given a function f and an input x ∈ℝ^d, it quantifies each feature’s contribution to f(x). Recently, SHAP has been increasingly used for global insights: practitioners average the absolute SHAP values over many data points to compute global feature importance scores, which are then used to discard “unimportant” features.

Metric embeddings are a widely used method in algorithm design, where generally a "complex" metric is embedded into a simpler, lower-dimensional one. Historically, the theoretical computer science community has focused on bi-Lipschitz embeddings, which guarantee that every pairwise distance is approximately preserved. In contrast, alternative embedding objectives that are commonly used in practice avoid bi-Lipschitz distortion; yet these approaches have received comparatively less study in theory. In this paper, we focus on Multi-dimensional Scaling (MDS), where we are given a set of non-negative dissimilarities {d_i,j}_i,j∈[n] over n points, and the goal is to find an embedding {x_1,…,x_n}⊂ℝ^k that minimizes OPT = min_x_1,…,x_n𝔼_i,j∈[n][ (1-x_i - x_j/d_i,j)^2 ]. Despite its popularity, our theoretical understanding of MDS is extremely limited. Recently, Demaine et al. gave the first approximation algorithm with provable guarantees for this objective, which achieves an embedding in constant-dimensional Euclidean space with cost OPT + ϵ in n^2 · 2^poly(Δ/ϵ) time, where Δ is the aspect ratio of the input dissimilarities. For metrics that admit low-cost embeddings, Δ scales polynomially in n. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on Δ: for constant-dimensional Euclidean space, we achieve a solution with cost O(logΔ)·OPT^Ω(1) + ϵ in time n^O(1)· 2^poly(log(Δ)/ϵ). Our algorithms are based on a novel geometry-aware analysis of a conditional rounding of the Sherali-Adams LP hierarchy, allowing us to avoid the exponential dependency on the aspect ratio that would typically result from this rounding.

We show that Thompson sampling has a Bayesian regret of at most Õ(√(n)) for 1-dimensional bandit convex optimisation where n is the time horizon and no assumptions are made on the loss function beyond convexity, boundedness and a mild Lipschitz assumption. For general high-dimensional problems we show that Thompson sampling can fail catastrophically. More positively, we show that Thompson sampling has Bayesian regret of Õ(d^2.5√(n)) for generalised linear bandits with an unknown convex monotone link function. Lastly, we prove that the standard information-theoretic machinery can never give a bound on the regret in the general case that improveson the best known bound of Õ(d^1.5√(n)).

Recent advances (Sherman, 2017; Sidford and Tian, 2018; Cohen et al., 2021) have overcome the fundamental barrier of dimension dependence in the iteration complexity of solving ℓ_∞ regression with first-order methods. Yet it remains unclear to what extent such acceleration can be achieved for general ℓ_p smooth functions. In this paper, we propose a new accelerated first-order method for convex optimization under non-Euclidean smoothness assumptions. In contrast to standard acceleration techniques, our approach uses primal-dual iterate sequences taken with respect to differing norms, which are then coupled using an implicitly determined interpolation parameter. For ℓ_p norm smooth problems in d dimensions, our method provides an iteration complexity improvement of up to O(d^1-2/p) in terms of calls to a first-order oracle, thereby allowing us to circumvent long-standing barriers in accelerated non-Euclidean steepest descent.

We study high-dimensional random geometric graphs (RGGs) of edge-density p with vertices uniformly distributed on the d-dimensional torus and edges inserted between sufficiently close vertices with respect to an L_q-norm. In this setting, we focus on distinguishing an RGG from an Erdős–Rényi graph if both models have the same marginal edge probability p. So far, most results in the literature considered either spherical RGGs with L_2-distance or toroidal RGGs under L_∞-distance. However, for general L_q-distances, many questions remain open, especially if p is allowed to depend on n. The main reason for this is that RGGs under L_q-distances can not easily be represented as the logical AND of their 1-dimensional counterparts, as is the case for L_∞ geometries. To overcome this difficulty, we devise a novel technique for quantifying the dependence between edges based on a modified version of Edgeworth expansions. Our technique yields the first tight algorithmic upper bounds for distinguishing toroidal RGGs under general L_q norms from Erdős–Rényi graphs for any fixed p and q. We achieve this by showing that the signed triangle statistic can distinguish the two models when d≪ n^3p^3 for the whole regime of edge probabilities c/n<p<1. Additionally, our technique yields an improved information-theoretic lower bound for this task, showing that the two distributions converge in total variation whenever d=Ω̃(n^3p^2), which is just as strong as the currently best known lower bound for spherical RGGs in case of general p from Liu et al. [STOC’22]. Finally, our expansions allow us to tightly characterize the spectral properties of toroidal RGGs both under L_q-distances for fixed 1 ≤ q < ∞, and L_∞-distance. We find that these are quite different for q<∞ vs. q=∞. Our results partially resolve a conjecture of Bangachev and Bressler [COLT ’24] and prove that the distance metric, rather than the underlying space, is responsible for the observed differences in the behavior of high-dimensional spherical and toroidal RGGs.

Online learning algorithms are widely used in strategic multi-agent settings, including repeated auctions, contract design, and pricing competitions, where agents adapt their strategies over time. A key question in such environments is how an optimizing agent can best respond to a learning agent to improve its own long-term outcomes. While prior work has developed efficient algorithms for the optimizer in special cases—such as structured auction settings or contract design—no general efficient algorithm is known. In this paper, we establish a strong computational hardness result: unless 𝖯 = 𝖭𝖯, no polynomial-time optimizer can compute a near-optimal strategy against a learner using a standard no-regret algorithm, specifically Multiplicative Weights Update (MWU). Our result proves an Ω(T) hardness bound, significantly strengthening previous work that only showed an additive Θ(1) impossibility result. Furthermore, while the prior hardness result focused on learners using fictitious play—an algorithm that is not no-regret—we prove intractability for a widely used no-regret learning algorithm. This establishes a fundamental computational barrier to finding optimal strategies in general game-theoretic settings.

Adversarially robust PAC learning has proved to be challenging, with the currently best known learners relying on improper methods based on intricate compression schemes, resulting in sample complexity exponential in the VC-dimension. A series of follow up work considered a slightly relaxed version of the problem called adversarially robust learning with tolerance and achieved better sample complexity in terms of the VC-dimension. However, those algorithms were either improper and complex, or required additional assumptions on the hypothesis class ℋ. We prove, for the first time, the existence of a simpler learner that achieves a sample complexity linear in the VC-dimension without requiring additional assumptions on ℋ. Even though our learner is improper, it is “almost proper" in the sense that it outputs a hypothesis that is “similar" to a hypothesis in ℋ. We also use the ideas from our algorithm to construct a semi-supervised learner in the tolerant setting. This simple algorithm achieves comparable bounds to the previous (non-tolerant) semi-supervised algorithm, but avoids the use of intricate subroutines from previous works, and is “almost proper."

We propose a framework which generalizes “decision making with structured observations" from Foster et al. (2023) by allowing robust (i.e. multivalued) models. In this framework, each model associates each decision with a convex set of probability distributions over outcomes. Nature can choose distributions out of this set in an arbitrary (adversarial) manner, that can be non-oblivious and depend on past history. The resulting framework offers much greater generality than classical bandits and reinforcement learning, since the realizability assumption becomes much weaker and more realistic. We then derive a theory of regret bounds for this framework, which extends the “decision-estimation coefficients" of Foster et al. (2023). Although our lower and upper bounds are not tight, they are sufficient to fully characterize power-law learnability. We demonstrate this theory in two special cases: robust linear bandits (previously studied in Kosoy (2024)) and tabular robust online reinforcement learning (previously studied in Tian et al. (2021)). In both cases, we derive regret bounds that improve state-of-the-art (except that we do not address computational efficiency).

We extend the framework of augmented distribution testing (Aliakbarpour, Indyk, Rubinfeld, and Silwal, NeurIPS 2024) to the differentially private setting. This captures scenarios where a data analyst must perform hypothesis testing tasks on sensitive data, but is able to leverage prior knowledge (public, but possibly erroneous or untrusted) about the data distribution. We design private algorithms in this augmented setting for three flagship distribution testing tasks, uniformity, identity, and closeness testing, whose sample complexity smoothly scales with the claimed quality of the auxiliary information. We complement our algorithms with information-theoretic lower bounds, showing that their sample complexity is optimal (up to logarithmic factors).

This paper is about the recent notion of computably probably approximately correct learning, which lies between the statistical learning theory where there is no computational requirement on the learner and efficient PAC learning where the learner must be polynomially bounded. Examples have recently been given of hypothesis classes which are PAC-learnable but not computably PAC-learnable, but these hypothesis classes can be viewed as unnatural or non-canonical. We use the on-a-cone machinery from computability theory to prove that, under certain assumptions on the hypothesis class, any “natural” hypothesis class which is learnable must be computably learnable.

Model-free methods for reinforcement learning (RL), particularly Q-learning, have gained popularity in practice because of their simplicity and flexibility, and underlie most successful modern deep RL algorithms. However, the sample complexity and regret bounds for these approaches have often lagged behind their model-based counterparts, especially in the average reward setting. Our work addresses this gap. We present a simple, optimistic Q-learning algorithm for regret minimization in a tabular RL setting that encompasses both average reward and episodic settings. Our contributions include new modeling, algorithm design, and regret analysis techniques. Our first and foremost contribution is a natural modeling assumption that generalizes the episodic and ergodic MDP settings and provides a more practically applicable formulation. We consider the class of MDPs where there is an "upper bound H on the time to visit a frequent state s_0", either in expectation or with constant probability. The upper bound H is assumed to hold under all feasible policies (stationary or non-stationary) and is known to the RL agent, although the identity of the frequent state s_0 may not be known. This assumption is naturally satisfied by the episodic settings since the terminal state is visited after every set of H steps, and also by the ergodic MDP settings that assume bounded worst-case hitting time H for all states. Furthermore, as we demonstrate using several examples from queuing admission control and inventory management, it allows for significantly more modeling flexibility than the existing settings. A key technical contribution of our work is the introduction of an L operator defined as L v = 1/H∑_h=1^H L^h v where L denotes the Bellman operator. Under the given assumption, we show that the L operator has a strict contraction (in span) even in the average-reward setting where the discount factor is 1. Our algorithm design builds upon the Q-learning algorithm while replacing the Bellman operator with the novel operator. It uses ideas from episodic Q-learning to estimate and apply this operator iteratively. Our model-free algorithm improves the existing literature both in simplicity of algorithmic design and regret bounds. Specifically, our algorithm achieves a regret bound of Õ(H^5 S√(AT)) in the average reward setting, where S and A are the numbers of states and actions, and T is the horizon. A regret bound of Õ(H^6 S√(AT)) in the episodic setting with fixed episode length H follows as a corollary of this result. Thus, we provide a unified view of algorithm design and regret minimization in episodic and non-episodic settings, which may be of independent interest.