New lower bounds for gradient methods in strongly convex finite-sum optimization.
problem Developing tight lower bounds for randomized gradient methods in finite-sum optimization.
method Deriving tight lower complexity bounds for SAG, SAGA, SVRG, SARAH, and related methods.
result Tight matches between lower bounds and upper bounds for various methods under specific conditions.
Lower bound for complexity of finding flex points on cubic curves.
problem Finding flex points on cubic plane curves.
method Bounding the Schwarz genus of a cover associated to the problem.
result Lower bound for topological complexity close to optimal.
Lower bounds for geodesically convex optimization show curvature negatively impacts complexity.
problem Understanding the impact of curvature on the query complexity of geodesically convex optimization.
method Building on recent lower bounds, the study proposes and proves new lower bounds for various settings of geodesically convex optimization.
result Negative curvature is detrimental to the complexity of geodesically convex optimization.
We establish a lower bound on the complexity orientable locally orientable geometric 3-orbifolds in terms of Delzant's T-invariants of their orbifold-fundamental groups, generalizing previously known bounds for complexity of 3-manifolds.
Lower bounds and upper bounds on sample complexity for identifying linear dynamical systems.
problem Identifying an unknown linear dynamical system with limited data.
method Sample complexity lower and upper bounds, persistent excitation condition, active learning algorithm.
result Lower and upper bounds share the same dependency on key problem parameters.
Paper establishes first instance-dependent lower bound for PAC reinforcement learning.
problem Identifying near-optimal policies in tabular MDPs with minimal samples.
method Proposes instance-dependent lower bound for sample complexity.
result Lower bound closely matches PEDEL algorithm's sample complexity.
Paper tightens lower bounds on decentralized training complexity.
problem Understanding and optimizing iteration complexity in decentralized training.
method Proved a tight lower bound on iteration complexity and proposed DeTAG algorithm.
result DeTAG achieves the theoretical lower bound with only a logarithmic gap.
Lower bound on stretch factor for periodic maps.
problem Finding a lower bound on stretch factors for periodic maps.
method Using core characteristic of end-periodic homeomorphisms, we derive a lower bound on the Handel-Miller stretch factor.
result The derived bound is sharp and measures topological complexity.
We prove a general connection between the communication complexity of two-player games and the sample complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from com…
Improved lower bounds on 2-bridge link complexity.
problem Finding minimal triangulations of 2-bridge link complements.
method Explicit angle structures and volume estimates.
result Explicit lower bounds on link complexity.
Paper finds at least 6 fixed points for a specific circle action on a 10D manifold.
problem Finding the minimum number of fixed points for a circle action on a 10D almost complex manifold.
method Established a lower bound by showing the non-existence of a circle action with 4 fixed points.
result There are at least 6 fixed points for a circle action on a 10D compact almost complex manifold.
This paper sets a lower bound for sample complexity in inverse reinforcement learning.
problem Finding a reward function that generates a desired optimal policy in MDPs.
method Information-theoretic lower bound using geometric construction and Fano's inequality.
result An O(nlogn) sample complexity lower bound for IRL problems. Lower bounds found for nonconvex-strongly-concave min-max optimization problems.
problem Finding stationary points in nonconvex-strongly-concave min-max optimization.
method Provided lower bounds for first-order oracle complexity.
result Lower bounds of Ω(√κε⁻²) for deterministic oracles and Ω(√κε⁻² + κ¹/₃ε⁻⁴) for stochastic oracles.
The study sets limits on the complexity of Klein geometries.
problem Understanding the complexity of Klein geometries.
method Simple upper and lower bounds for the order of Klein geometries.
result Established upper and lower bounds for the order of Klein geometries.
The paper sets information-theoretic lower bounds for neural networks' parameter recovery and excess risk.
problem Establishing sample complexity lower bounds for neural network parameters and excess risk.
method Using information-theoretic tools, the paper proves lower bounds by constructing a generative network.
result Proves information-theoretic lower bounds for exact parameter recovery and positive excess risk.
Paper establishes lower bounds for finite-sum optimization problems using novel construction methods.
problem Lower complexity bounds for finite-sum optimization problems with various component functions.
method Developed novel approach to construct hard instances and analyzed PIFO algorithms.
result Established lower complexity bounds for convex-concave and nonconvex-strongly-concave objectives.
Given a sequence of complete(compact or noncompact) Kähler manifolds Min with bisectional curvature lower bound and noncollapsed volume, we prove that the pointed Gromov-Hausdorff limit is homeomorphic to a normal complex analytic space. The complex analytic structure is the natural "limit" of complex structure of …
New method achieves optimal sample complexity without warm-start in bilevel optimization.
problem Optimizing smooth objective functions with fixed point constraints in meta-learning and equilibrium models.
method Fixed point iterations at lower-level and projected inexact gradient descent at upper-level.
result Achieves near optimal sample complexity O(ε−2) and ildeO(ε−1) samples. In this short note we determine the greatest lower bounds on Ricci curvature for all Fano T-manifolds of complexity one, generalizing the result of Chi Li. Our method of proof is based on the work of Datar and Székelyhidi, using the description of complexity one special configurations given by Ilten and Süß.
New lower bounds for bilevel optimization with first-order oracles.
problem Complexity of bilevel optimization with first-order oracles.
method Development of hard instances and proof of lower bounds.
result Nontrivial lower bounds for first-order zero-respecting algorithms.
Lower bounds for PL 4-manifolds with boundary are improved.
problem Estimating PL 4-manifolds with boundary.
method Proved inequalities for regular genus and gem-complexity.
result Improved lower bounds for PL 4-manifolds with boundary.
New algorithm for multi-fidelity bandits reduces costs and improves regret.
problem Optimizing decisions with varying costs and accuracy in multi-fidelity bandits.
method Cost complexity bounds, algorithmic framework, elimination-based algorithm.
result New regret definition and matching upper and lower bounds for elimination-based algorithm.
In three-dimensional computational topology, the theory of normal surfaces is a tool of great theoretical and practical significance. Although this theory typically leads to exponential time algorithms, very little is known about how these algorithms perform in "typical" scenarios, or how far the best known theoretical…
Paper establishes new lower bounds for MDPs with changing transition kernels.
problem Minimizing sample complexity and regret in non-stationary MDPs.
method Developed novel lower bounds and constructed hard MDPs.
result Proved Ω((H3SA/ε2)log(1/δ)) sample complexity lower bound. Unified framework for lower bounds in interactive decision making.
problem Challenges in interactive decision making, especially bandits and reinforcement learning.
method Interactive Fano method and Fractional Covering Number.
result Unified characterization of learnability for stochastic bandit problems and tight lower bounds for interactive decision making.
The paper introduces gapped scale-sensitive dimensions to improve learning rate bounds.
problem Improving lower bounds on rates of convergence in statistical and online learning.
method Introducing and analyzing gapped scale-sensitive dimensions for function classes.
result Gapped dimensions lead to stronger lower bounds on offset Rademacher averages.
We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution-specific upper and lower bounds on…
Study on Kähler manifolds shows rigidity of eigenvalues with positive Ricci bound.
problem Optimal rigidity results for eigenvalues on Kähler manifolds with positive Ricci lower bound.
method Established optimal rigidity results for eigenvalues on Kähler manifolds with positive Ricci lower bound.
result Complex projective space is the only Kähler manifold with the largest multiplicity of the first eigenvalue.
New methods solve complex optimization problems without strong convexity assumptions.
problem Complex bilevel optimization problems with minimax lower-level structures.
method Penalty-based first-order methods for bilevel minimax optimization.
result Achieves ε-KKT point with improved oracle complexity. The paper sets lower bounds for sampling non-log-concave distributions using Fisher information.
problem Understanding the complexity of sampling non-log-concave distributions.
method Proves two lower bounds using Fisher information in the context of sampling.
result Lower bounds on the complexity of sampling non-log-concave distributions, ruling out high-accuracy algorithms.
Smooth finite-sum optimization has been widely studied in both convex and nonconvex settings. However, existing lower bounds for finite-sum optimization are mostly limited to the setting where each component function is (strongly) convex, while the lower bounds for nonconvex finite-sum optimization remain largely unsol…
New SQ lower bounds show learning mixtures of bounded covariance Gaussians is hard.
problem Learning mixtures of Gaussians with bounded covariance matrices is hard.
method Statistical Query (SQ) lower bounds.
result Any SQ algorithm requires complexity at least dΩ(1/ε) for learning mixtures of bounded covariance Gaussians. Lower bounds on query complexity for reconstructing private learner's training data.
problem Query complexity of reconstructing private learner's training data.
method Minimax analysis, Rényi DP, Metric DP framework.
result First known lower bounds on adversary's query complexity for various DP learners.
The paper studies privacy-protected BAI with fixed confidence, deriving lower bounds and proposing an adaptive algorithm.
problem Privacy-protected Best Arm Identification (BAI) in data-sensitive applications.
method Derives lower bounds on sample complexity, proposes AdaP-TT algorithm with Laplace noise, and validates with experiments.
result AdaP-TT matches the sample complexity lower bound up to constants in the high-privacy regime.
Uniform bounds for Green's function on Kähler manifolds derived from complex Monge-Ampère equations.
problem Uniform bounds for Green's function on Kähler manifolds.
method Auxiliary Monge-Ampère equations, non-linear proof.
result Uniform lower bounds for the Green's function on Kähler manifolds.
Paper finds a lower bound for estimating low-rank matrices in logistic regression.
problem Estimating low-rank coefficient matrices in logistic regression.
method Derives a minimax lower bound on the risk.
result The bound depends on matrix dimensions, rank, and sample size.
We show that the correction terms in Heegaard Floer homology give a lower bound to the the genus of one-sided Heegaard splittings and the Z2--Thurston norm. Using a result of Jaco--Rubinstein--Tillmann, this gives a lower bound to the complexity of certain closed 3--manifolds. As an application, we compute…
The standard interpretation of importance-weighted autoencoders is that they maximize a tighter lower bound on the marginal likelihood than the standard evidence lower bound. We give an alternate interpretation of this procedure: that it optimizes the standard variational lower bound, but using a more complex distribut…
In Kähler-Einstein case of positive scalar curvature and even complex dimension, an improved lower bound for the first eigenvalue of the Dirac operator is given. It is shown by a general construction that there are manifolds for which this new lower bound itself is the first eigenvalue.
Study on scalar curvature bounds and manifold topological complexity.
problem Understanding the topological complexity of manifolds with scalar curvature constraints.
method Introduced a small scale index theorem to establish bounds for Gromov's simplicial norm.
result Upper bound for Gromov's simplicial norm established in terms of scalar curvature, volume, and injectivity radius.
The paper extends statistical estimation techniques under differential privacy.
problem Establishing sample complexity bounds for estimation tasks under differential privacy.
method Proposes analogues of Le Cam's method, Fano's inequality, and Assouad's lemma under central differential privacy.
result Optimal sample complexity bounds for discrete distribution estimation under total variation and ℓ2 distances. Study near-optimal bounds for learning Gaussian halfspaces with random noise.
problem Learning general halfspaces with Gaussian distribution and random classification noise.
method Established nearly-matching algorithmic and SQ lower bounds, developed a computationally efficient learning algorithm.
result Sample complexity of learning algorithm is O(d/ε+d/(max{p,ε})2), SQ lower bound is Ω(d1/2/(max{p,ε})2). In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution p over a poset is monotone if, for any pair of domain elements x and y such that x⪯y, p(x)≤p(y). To understand the sample complexity of this problem, we intro…
The study analyzes batched methods for early stopping in stochastic multi-armed bandits.
problem Early stopping in stochastic multi-armed bandits with fixed confidence.
method Instance-dependent lower bounds and a general batched algorithm with upper bounds.
result Upper and lower bounds on the number of batches and sample complexity.
Optimal multi-fidelity best-arm identification reduces cost with better accuracy.
problem Finding the best arm with highest mean reward at minimum cost.
method Gradient-based approach with asymptotically optimal cost complexity.
result Asymptotically optimal cost complexity compared to existing methods.
Optimizes energy of mappings from complex projective spaces.
problem Finding energy-minimizing mappings between complex projective spaces and Riemannian manifolds.
method Establishes optimal lower bounds for energy functionals and characterizes optimal mappings.
result Optimal lower bounds for energy functionals are characterized for mappings from real and complex projective spaces.
PCA-Net combines PCA and neural networks for operator approximation, with new bounds on complexity.
problem Developing approximation theory for PCA-Net architecture.
method Combines PCA and neural networks, derives universal approximation results and lower bounds on complexity.
result PCA-Net can overcome the curse of parametric complexity for specific operators.
New SQ lower bound shows complexity nearly matches known upper bound for smoothed agnostic learning.
problem Smoothed agnostic learning of halfspaces under subgaussian distributions.
method Statistical Query (SQ) lower bound using moment-matching hard distribution and linear programming duality.
result First non-trivial lower bound on complexity nearly matches known upper bound.