This work accelerates gradient descent with anytime convergence guarantees.
problem Improving the convergence rate of gradient descent methods.
method Proposes a stepsize schedule for gradient descent that achieves anytime convergence rates.
result Gradient descent can achieve convergence rates of O ( T − 1.119 ) O(T^{-1.119}) O ( T − 1.119 ) for any stopping time T T T . The paper solves open questions in computable PAC learning, providing a complete landscape.
problem Understanding the boundaries and capabilities of computable PAC learning.
method Analyzing and constructing decidable hypothesis classes with different sample complexities and Littlestone dimensions.
result A complete understanding of CPAC learnability, answering open questions and confirming conjectures.
Open problem: fixed-budget best arm identification complexity.
problem Understanding the complexity of identifying the best arm in a fixed budget setting.
method Analyzing existing results and conjectures in the fixed-confidence setting.
result Open questions remain about the fixed-budget setting.
Paper settles sample complexity for learning from multiple distributions.
problem Learning from multiple data distributions with a hypothesis class of bounded VC dimension.
method Introduced an algorithm with sample complexity of O((d+k)ε^-2)·(k/ε)^o(1).
result Algorithm matches lower bound up to sub-polynomial factor.
Novel approach to universal online learning for bounded losses, closing open problems.
problem Characterizing processes for universal online learning under non-i.i.d. conditions.
method Characterization of processes admitting strong and weak universal learning, introduction of optimistically universal learning rule.
result Introduction of a novel 1NN algorithm that is optimistically universal for bounded losses.
Learning linear predictors with the logistic loss---both in stochastic and online settings---is a fundamental task in machine learning and statistics, with direct connections to classification and boosting. Existing "fast rates" for this setting exhibit exponential dependence on the predictor norm, and Hazan et al. (20…
Local regularization fails in transductive learning for some multiclass problems.
problem Whether local regularization can learn all transductive multiclass problems.
method Provided a negative answer by exhibiting a specific multiclass problem.
result Local regularization cannot learn all transductive multiclass problems.
CoLT assesses neural posterior estimates by detecting discrepancies across conditioning inputs.
problem Validating neural posterior estimates from limited data.
method Conditional Localization Test (CoLT) learns a localization function to detect strong deviations.
result CoLT provides rigorous guarantees and practical scalability for comparing true and neural posterior distributions.
We present an efficient second-order algorithm with O ~ ( 1 η T ) \tilde{O}(\frac{1}η\sqrt{T}) O ~ ( η 1 T ) regret for the bandit online multiclass problem. The regret bound holds simultaneously with respect to a family of loss functions parameterized by η η η , for a range of η η η restricted by the norm of the competitor. The family of loss funct…
A primary concern of excessive reuse of test datasets in machine learning is that it can lead to overfitting. Multiclass classification was recently shown to be more resistant to overfitting than binary classification. In an open problem of COLT 2019, Feldman, Frostig, and Hardt ask to characterize the dependence of th…
We study the algorithmic problem of estimating the mean of heavy-tailed random vector in R d \mathbb{R}^d R d , given n n n i.i.d. samples. The goal is to design an efficient estimator that attains the optimal sub-gaussian error bound, only assuming that the random vector has bounded mean and covariance. Polynomial-time solutio…
Memory-constrained algorithms need superlinear memory for efficient convex optimization.
problem Efficiently minimizing convex functions with limited memory.
method Analyzing first-order algorithms with superlinear memory constraints.
result Superlinear memory is necessary for optimal performance in convex optimization.
This work proves lower bounds on a greedy teaching set construction algorithm.
problem Characterize the best-case teaching dimension of a concept class.
method A greedy algorithm that iteratively adds points to the teaching set to restrict the concept class the most.
result Lower bounds on the performance of the greedy approach for small k, extending up to k ≤ c*d for small constant c.
Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state of the art methods. In this paper, we …
New algorithm reduces sample complexity for multi-distribution learning.
problem Achieving data-efficient multi-distribution learning with robustness and fairness.
method Proposes a novel algorithm with sample complexity (d+k)/varepsilon^2 for Vapnik-Chervonenkis (VC) dimension d, matching lower bounds.
result Algorithm matches best-known lower bound and resolves open problems in COLT 2023.
GP-UCB resolves sublinear regret for kernelized bandits.
problem Minimizing regret in kernelized bandit problems.
method Using a new regularization technique for kernel ridge estimators, improving GP-UCB's sublinear regret rate.
result GP-UCB achieves nearly optimal sublinear regret for the Matérn kernel.
New sampling and identity-testing methods for mixtures of distributions that don't satisfy approximate tensorization of entropy.
problem Sampling and identity-testing for mixtures of distributions that don't satisfy approximate tensorization of entropy.
method Fast mixing of Glauber dynamics and efficient identity-testers in the coordinate-conditional sampling access model.
result Efficient identity-testers for mixtures of ATE distributions in the coordinate-conditional sampling access model.
New algorithm reduces regret in online portfolio and quantum state learning.
problem Efficiently learning portfolios and quantum states online with minimal regret.
method BISONS algorithm for online portfolio selection, SCHRODINGER'S BISONS for quantum states, with polylogarithmic regret.
result First efficient algorithm with polylogarithmic regret for online portfolio selection and quantum states.
Quadratic memory is essential for optimal convex optimization queries.
problem Optimal query complexity for convex optimization and feasibility problems.
method Lower bounds on query complexity for convex optimization and feasibility problems.
result Center-of-mass algorithms are Pareto-optimal for both convex optimization and feasibility problems.
Random exploration optimizes Bayesian optimization with optimal error rates and computational efficiency.
problem Optimizing Gaussian Process models in Bayesian optimization.
method Random sampling from a distribution in an infinite dimensional Hilbert space, with domain shrinking and order-optimal regret guarantees.
result Achieves optimal error rates and computational efficiency in both noise-free and noisy settings.
In this paper, we prove a conjecture published in 1989 and also partially address an open problem announced at the Conference on Learning Theory (COLT) 2015. With no unrealistic assumption, we first prove the following statements for the squared loss function of deep linear neural networks with any depth and any widths…
A simple linear algebraic explanation of the algorithm in "A Spectral Algorithm for Learning Hidden Markov Models" (COLT 2009). Most of the content is in Figure 2; the text just makes everything precise in four nearly-trivial claims.
The paper explores how to reduce classification tasks to optimization problems in Euclidean space.
problem Understanding the minimum dimension needed for reducing classification tasks to optimization problems.
method Developed a generalization of the Borsuk-Ulam Theorem to analyze the expressivity of reductions.
result The minimum Euclidean dimension required can be exponentially larger than the VC dimension, even for slightly non-trivial reductions.
Paper shows TD learning without projection converges robustly.
problem Investigate convergence of TD learning with linear approx.
method Simple unprojected TD(0) with novel self-bounding property.
result TD(0) converges with rate O ~ ( 1 / T ) \widetilde{\mathcal{O}}(1/\sqrt{T}) O ( 1/ T ) . We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of n n n objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the to…
Study on list learning with noisy data, showing limits and some learnable cases.
problem Learning from noisy data in a list learning context.
method Inspired by coding theory, extends list learning model to study sparse conjunctions and parities/majors.
result Sparse conjunctions can be efficiently list learned under certain conditions, but parities and majors cannot be efficiently learned.
New algorithm tackles self-selection bias in estimating linear regressors.
problem Estimating k k k linear regressors with self-selection bias in d d d dimensions. method First local convergence algorithm for self-selection, reducing to coarsening problem.
result Improves running time of previous algorithms by a poly(d, k, 1/ε) factor.
Long horizon reinforcement learning is as hard as short horizon learning.
problem Understanding the difficulty of long horizon reinforcement learning problems.
method Introduced new concepts: ε-net for optimal policies and Online Trajectory Synthesis algorithm.
result Proved that sample complexity scales logarithmically with the planning horizon, refuting the conjecture.
Efficient algorithm for contextual bandits with first-order guarantees.
problem Adapting to low noise in contextual bandits.
method Reduction to online regression with logarithmic loss.
result Optimal and efficient first-order guarantees for contextual bandits.
New algorithm reduces regret in private online learning with optimal gap-dependent rate.
problem Optimal gap-dependent regret rate for private stochastic decision-theoretic online learning.
method Horizon-free pure-DP algorithm with exponential block partitioning and softmax selection.
result Explicit regret bound of 1000 ⋅ ( log K Δ min + log K ε ) 1000 \cdot (\frac{\log K}{Δ_{\min}}+\frac{\log K}{\varepsilon}) 1000 ⋅ ( Δ m i n l o g K + ε l o g K ) . In this paper, we study the generalization properties of online learning based stochastic methods for supervised learning problems where the loss function is dependent on more than one training sample (e.g., metric learning, ranking). We present a generic decoupling technique that enables us to provide Rademacher compl…
Improved private learning of halfspaces with reduced sample complexity.
problem Private learning of halfspaces with reduced sample complexity.
method Iterative algorithm for solving linear feasibility problem, improving state-of-the-art results.
result Sample complexity reduced to d 2.5 ⋅ 2 log ∗ ∣ G ∣ d^{2.5} \cdot 2^{\log^*|G|} d 2.5 ⋅ 2 l o g ∗ ∣ G ∣ , improving d 2 d^2 d 2 factor. Improved sampling from non-log-concave distributions with polynomial query complexity.
problem Sampling from distributions with non-log-concave densities efficiently.
method Combining Ornstein-Uhlenbeck process assumptions and polynomial moment conditions.
result Polynomial query complexity improvement over previous methods.
Efficiently estimates linear models robust to corrupted data.
problem Learning linear models under adversarial corruption and minimal distributional assumptions.
method Develops a polynomial relaxation of independence to achieve optimal convergence rate.
result Achieves optimal convergence rate of ε 2 − 2 / k ε^{2-2/k} ε 2 − 2/ k for k k k -hypercontractive distributions. A new bandit problem where experiments can be interrupted if results are not promising.
problem Interruptible multi-armed bandit problem with a threshold for cumulative reward.
method Formalized survival regret, identified key components (regret and probability of ruin), derived lower bounds and optimal policies.
result No policy can achieve sublinear survival regret, but optimal policies minimize survival regret in a Pareto sense.
Improved single-pass streaming MAB regret bound to O(K^1/3T^2/3).
problem Minimize regret in single-pass streaming multi-armed bandits with sublinear memory.
method Improved regret lower bound to Ω(K^1/3T^2/3) and upper bound to O(K^1/3T^2/3).
result Achieved tight regret bound of O(K^1/3T^2/3) for algorithms with o(K) memory.
We consider the problem of unconstrained online convex optimization (OCO) with sub-exponential noise, a strictly more general problem than the standard OCO. In this setting, the learner receives a subgradient of the loss functions corrupted by sub-exponential noise and strives to achieve optimal regret guarantee, witho…
We propose a hypergraph-based active learning scheme which we term H S 2 HS^2 H S 2 , H S 2 HS^2 H S 2 generalizes the previously reported algorithm S 2 S^2 S 2 originally proposed for graph-based active learning with pointwise queries [Dasarathy et al., COLT 2015]. Our H S 2 HS^2 H S 2 method can accommodate hypergraph structures and allows one to ask bo…
Simplifies online learning with consistent oracle to fewer mistakes.
problem Online learning with computationally intractable Littlestone dimension computation.
method Novel algorithm making at most O ( 256 d ) O(256^d) O ( 25 6 d ) mistakes, simpler proof. result No algorithm can make less than 3 d 3^d 3 d mistakes. New bounds show complex neural networks need many queries to learn.
problem Learning non-polynomial activation functions with Gaussian marginals.
method Gradient boosting procedure to amplify lower bounds on SQ dimension of neural networks.
result Statistical-query lower bounds for ReLU regression with 2 n c ε 2^{n^c} ε 2 n c ε queries. Improved bounds on combining hypothesis classes for binary functions.
problem Understanding how to combine hypothesis classes for binary functions.
method Established upper bounds on Littlestone and threshold dimensions for combined classes.
result Upper bounds are nearly tight and give exponential improvements.
New algorithms estimate parameters of Gaussian and non-Gaussian distributions from truncated samples.
problem Estimating distributional parameters from truncated samples.
method Polynomial time algorithms for exponential families and simple sets.
result Efficient algorithms for estimating parameters of various distributions from truncated samples.
New bounds on SGD's final iterate convergence rate in constant dimension.
problem Characterize the convergence rate of SGD's final iterate in constant dimension.
method Proved lower bounds of Ω ( log d / T ) Ω(\log d/\sqrt{T}) Ω ( log d / T ) and Ω ( log d / T ) Ω(\log d/T) Ω ( log d / T ) for non-smooth Lipschitz convex and strongly convex functions respectively. result First general dimension dependent lower bound on SGD's final iterate convergence rate.
Open problems in billiards and optics from a workshop.
problem Open problems in billiards and geometric optics.
method Collection of open problems from a workshop.
result No specific key result mentioned; collection of problems.
Chebyshev polynomials analyze Czech enterprises' stock dynamics.
problem Analyzing stock dynamics of enterprises not following normal distribution.
method Chebyshev polynomial decomposition of stock time series.
result Allows effective analysis of stock dynamics without variance and correlation.
Study on computing and estimating calibration distance, showing hardness and efficiency.
problem Computing and estimating calibration distance under different assumptions.
method Efficient algorithm for exact computation, polynomial-time approximation scheme; sample-based estimation for upper bounds.
result The problem becomes NP-hard when assumptions are removed, but efficient algorithms exist under certain conditions.
Open problems on surfaces with boundary and constant mean curvature.
problem Open problems on compact constant mean curvature surfaces with boundary.
method Survey of current status of open problems.
result Collection of open problems in the theory of surfaces.
Recalls intrinsically harmonic forms and open problems.
problem Open problems related to intrinsically harmonic forms.
method Recalling definitions and known results.
result Clarification of intrinsically harmonic forms and open questions.